Þ¤pathÙ:/home/runner/work/LINMA2472/LINMA2472/Lectures/implicit.jl¨metadata€¬cell_resultsÞ1Ù$e9fd46e4-78ce-4cba-b20f-1c997c80e842Чrunning§runtimeÎƸdepends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$e9fd46e4-78ce-4cba-b20f-1c997c80e842¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚD

Interlude: Repeated linear system solve

We need to solve the system $At_k = Bt_{k-1}$ once by forward tangent, so once by entry of $s_0$ in case of forward-mode AD. We may also pre-compute $A^{-1}B$ by solving one linear system by column of $B$. In both case, we need to solve several linear system with the same $A$ matrix.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�àœ°persist_js_state·has_pluto_hook_featuresÂÙ$877c563a-2ce3-4f97-9746-7d8329c0178aЧrunning§runtimeÎ m†¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$877c563a-2ce3-4f97-9746-7d8329c0178a¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚê
Is the adjoint of the inverse equal to the inverse of the adjoint ?

For arbitrary $r, t$, we have

$$\begin{align} \langle (A^{-1})^*r, t\rangle &= \langle r, A^{-1} t\rangle\\ &= \langle A^*(A^*)^{-1} r, A^{-1} t \rangle\\ &= \langle (A^*)^{-1} r, AA^{-1} t\rangle\\ &= \langle (A^*)^{-1} r, t\rangle. \end{align}$$

Since $r, t$ are arbitrary, we have $(A^{-1})^* = (A^*)^{-1}$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿wŠ7*°persist_js_state·has_pluto_hook_featuresÂÙ$b16f6225-1949-4b6d-a4b0-c5c230eb4c7fЧrunning§runtimeÎ H¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$b16f6225-1949-4b6d-a4b0-c5c230eb4c7f¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ6

Utils

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� ¯«°persist_js_state·has_pluto_hook_featuresÂÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5bЧrunning§runtimeÎ dš¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5b¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ(my_sqrt (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„‚*R°persist_js_state·has_pluto_hook_featuresÂÙ$81deb227-a822-4857-a584-a51cc8ff51f4Чrunning§runtimeίL¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$81deb227-a822-4857-a584-a51cc8ff51f4¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ$qa (generic function with 2 methods)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w‰ÉV2°persist_js_state·has_pluto_hook_featuresÂÙ$c9603b16-113b-4e05-8517-d814b0879ab8Чrunning§runtimeÎ$Œ¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$c9603b16-113b-4e05-8517-d814b0879ab8¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ¬

Implicit function theorem

In a sense, the implicit function theorem can be thought as the mother theorem, as it can be used to prove envelope theorems, the adjoint state method and the inverse function theorem. Section 11.6 of The Elements of Differentiable Programming book

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�*x°persist_js_state·has_pluto_hook_featuresÂÙ$c3b59d62-144e-4541-9007-19187f2fea1cЧrunning§runtimeÍFí¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$c3b59d62-144e-4541-9007-19187f2fea1c¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ52×3 Matrix{Float64}: 1.0 0.0 -4.0 0.0 1.0 4.5¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„û¾à°persist_js_state·has_pluto_hook_featuresÂÙ$b23a4c1d-cf35-42e6-b286-7fbcdddfd424Чrunning§runtimeÎ 8ݸdepends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$b23a4c1d-cf35-42e6-b286-7fbcdddfd424¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ"

Inverse function theorem

We write $D f$ for the Jacobian and $D_i F$ for the Jacobian with respect to the $i$-th argument.

Assume

Then

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�HE°persist_js_state·has_pluto_hook_featuresÂÙ$cbfc0129-9361-4edb-a467-1456a1f3aeaeЧrunning§runtimeÎl<¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$cbfc0129-9361-4edb-a467-1456a1f3aeae¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ%img (generic function with 3 methods)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w‰‰ðt°persist_js_state·has_pluto_hook_featuresÂÙ$fa019742-c473-4f1d-86ce-a795edbd1f92Чrunning§runtimeÍTl¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$fa019742-c473-4f1d-86ce-a795edbd1f92¹depends_on_disabled_cells¦queued¤logs�¦output†¤body¿2×2 Matrix{Int64}: 1 2 3 4¤mimeªtext/plain¬rootassignee¡A²last_run_timestampËAÚ¿w„ÇÔ°persist_js_state·has_pluto_hook_featuresÂÙ$528326dd-1344-4baa-9edd-5b09f63669ddЧrunning§runtimeΔ´¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$528326dd-1344-4baa-9edd-5b09f63669dd¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚƒ
Can we also solve the linear system with only access to the matrix-vector product of the linear map $D_1 F(w^\star(\lambda), \lambda)$ ? (aka matrix-free inversion)

If the matrix is positive semidefinite, we can use the Conjugate Gradient method. Otherwise, GMRES or BiCGSTAB are options.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿wŠâø°persist_js_state·has_pluto_hook_featuresÂÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6Чrunning§runtimeΨ§"¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6¹depends_on_disabled_cells¦queued¤logs�¦output†¤body²0.3535533906116973¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w†¶°persist_js_state·has_pluto_hook_featuresÂÙ$d907c5d7-f517-467a-a840-f94868ad7680Чrunning§runtimeÎÕ¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$d907c5d7-f517-467a-a840-f94868ad7680¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ²

Square root example

To illustrate consider this Jax example rewriting $x^2 = a$ into $2x^2 = x^2 + a$ or $x = (x + a/x)/2$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�# °persist_js_state·has_pluto_hook_featuresÂÙ$9d883700-0959-4ccd-be50-9ee316a6077eЧrunning§runtimeγ}˜¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$9d883700-0959-4ccd-be50-9ee316a6077e¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ!P

Acknowledgements and further readings

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w‰ÂH°persist_js_state·has_pluto_hook_featuresÂÙ$23049939-1b3a-4328-b159-99c3f1470e39Чrunning§runtimeΑ.¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$23049939-1b3a-4328-b159-99c3f1470e39¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙX

AD through fixed point

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�;q°persist_js_state·has_pluto_hook_featuresÂÙ$5c39f536-346c-48bd-a3c7-acaefb849b9fЧrunning§runtimeÎ)¹¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$5c39f536-346c-48bd-a3c7-acaefb849b9f¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ,fixed_point (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„{¢õ°persist_js_state·has_pluto_hook_featuresÂÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0Чrunning§runtimeÎN¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ¢LU{Float64, Matrix{Float64}, Vector{Int64}} L factor: 2×2 Matrix{Float64}: 1.0 0.0 0.333333 1.0 U factor: 2×2 Matrix{Float64}: 3.0 4.0 0.0 0.666667¤mimeªtext/plain¬rootassignee¡F²last_run_timestampËAÚ¿w…¶á°persist_js_state·has_pluto_hook_featuresÂÙ$10ca4307-929a-4e5f-942b-5d6c0e28e2beЧrunning§runtimeÎ數depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$10ca4307-929a-4e5f-942b-5d6c0e28e2be¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚŒ

Sensitivity of a linear program

Consider the primal-dual pair of programs

$$\begin{align} \min & \,\, c^\top x & \max & \,\, b^\top y\\ Ax & = b & A^\top y & \le c\\ x & \ge 0 \end{align}$$

The Lagrangian function is

$$\mathcal{L}(x, y) = c^\top x - y^\top (Ax - b) = y^\top b - (A^\top y - c)^\top x$$

The KKT condition give

$$\begin{align} \frac{\partial \mathcal{L}}{\partial y} & = Ax - b = 0 & \Leftrightarrow \qquad Ax & = b\\ (A^\top y - c) & \perp x \ge 0 & \Leftrightarrow \qquad \text{Diag}(x)(A^\top y - c) & = 0 \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� �ª°persist_js_state·has_pluto_hook_featuresÂÙ$6f8714a1-1372-42f4-9b51-da93ef2ed4c9Чrunning§runtimeα¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$6f8714a1-1372-42f4-9b51-da93ef2ed4c9¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ’

As $L$ and $U$ are triangular, solving the linear systems $LUx = b$ can now be done by solving two simple linear systems (and permutation in case of pivoting)

  1. $Lc = b$

  2. $Ux = c$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� &«°persist_js_state·has_pluto_hook_featuresÂÙ$c1efb93f-efd8-487a-94d2-aa7ecedb61b8Чrunning§runtimeÎ V¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$c1efb93f-efd8-487a-94d2-aa7ecedb61b8¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚZ

Implicit function theorem (multivariate case)

Assume

Then there exists a neighborhood $\mathcal{V} \subseteq \mathcal{U}$ where exists $w^\star(\lambda)$ such that

$$\begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ D w^\star(\lambda) & = -D_1 F(w^\star(\lambda), \lambda)^{-1}D_2 F(w^\star(\lambda), \lambda) \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w„©æC°persist_js_state·has_pluto_hook_featuresÂÙ$64250438-9ba6-44f7-b4a0-fcd5d72f05e5Чrunning§runtimeÎfp¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$64250438-9ba6-44f7-b4a0-fcd5d72f05e5¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„J›ª°persist_js_state·has_pluto_hook_featuresÂÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6Чrunning§runtimeÎ $옸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿wƒé;y°persist_js_state·has_pluto_hook_featuresÂÙ$abee47e4-1b75-4466-908a-e14113b181abЧrunning§runtimeÍ"ù¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$abee47e4-1b75-4466-908a-e14113b181ab¹depends_on_disabled_cells¦queued¤logs�¦output†¤body²1.4142135623746899¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„Š�°persist_js_state·has_pluto_hook_featuresÂÙ$d6797e7b-fa78-4366-b88f-9925f72a5d0fЧrunning§runtimeÎ Ù¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$d6797e7b-fa78-4366-b88f-9925f72a5d0f¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ‹

Differentiating numerical procedures

Consider a program that numerically converge to solutions:

function f(x)
	while abs(error) > tol
    	y += # Make some step in the right direction
    	error = # update error
	end
	return y
end
¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�)°persist_js_state·has_pluto_hook_featuresÂÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793Чrunning§runtimeγ½È¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÛ�¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w‰­˜Ä°persist_js_state·has_pluto_hook_featuresÂÙ$40baa108-eb68-433f-9917-ac334334f198Чrunning§runtimeÎ"þ‚¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$40baa108-eb68-433f-9917-ac334334f198¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚV,

Implicit Differentiation

Benoît Legat

      ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w„qúè°persist_js_state·has_pluto_hook_featuresÂÙ$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965Чrunning§runtimeÎ �ó˜¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚq
How can we differentiate with respect to x ? Forward, reverse, something else ?
¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w‰×¬Ò°persist_js_state·has_pluto_hook_featuresÂÙ$1de5d608-dc91-4f4a-995b-3dcfad38b81cЧrunning§runtimeÎV÷¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$1de5d608-dc91-4f4a-995b-3dcfad38b81c¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ¶

Classical Gaussian elimination finds the solution for one vector only, even though the same row operations would be applied for different vectors.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�õ#°persist_js_state·has_pluto_hook_featuresÂÙ$66a8b541-b06f-403a-a45d-23461a2c539bЧrunning§runtimeÎ4:”8¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$66a8b541-b06f-403a-a45d-23461a2c539b¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w…N†°persist_js_state·has_pluto_hook_featuresÂÙ$08c4ac83-4361-41d5-b036-789c2475ff8eЧrunning§runtimeÏÊǸdepends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$08c4ac83-4361-41d5-b036-789c2475ff8e¹depends_on_disabled_cells¦queued¤logs�¦output†¤body³0.35355339061171626¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w‰€ÂL°persist_js_state·has_pluto_hook_featuresÂÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2Чrunning§runtimeÎ�«¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚÞ

Pullback operator (VJP)

The pullback operation is the adjoint of the pushforward operator:

$$\langle r, A^{-1} B t\rangle = \langle (A^{-1})^* r, B t\rangle = \langle (A^*)^{-1} r, B t\rangle = \langle B^*(A^*)^{-1} r , t\rangle$$

So the pullback operator maps $r$ to $B^*(A^*)^{-1} r$.

This means that it first solves the linear system $A^*v = r$ (possibly in a matrix-free way) and then returns $B^*v$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� hŒ°persist_js_state·has_pluto_hook_featuresÂÙ$bb4e1c20-1d24-494a-82ae-433e8ba56110Чrunning§runtimeÎ …¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$bb4e1c20-1d24-494a-82ae-433e8ba56110¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚŠ

Implicit VJP and JVP

How can we integrate implicit function in a chain of functions ? Say, $s_{k-1} = \lambda$ and $f_k(\lambda) = w^\star(\lambda)$ such that $F(w^\star(\lambda), \lambda) = 0$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�}ݰpersist_js_state·has_pluto_hook_featuresÂÙ$2b30ae9e-e537-4ad1-a25e-570709c7d517Чrunning§runtimeÎÔxb¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$2b30ae9e-e537-4ad1-a25e-570709c7d517¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚh

Implicit function theorem (univariate case)

Assume

Then there exists a neighborhood $\mathcal{V} \subseteq \mathcal{U}$ where exists $w^\star(\lambda)$ such that

$$\begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ D w^\star(\lambda) & = -\frac{D_2 F(w^\star(\lambda), \lambda)}{D_1 F(w^\star(\lambda), \lambda)} \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w„©¸™°persist_js_state·has_pluto_hook_featuresÂÙ$30afb6e9-1ce0-4004-807b-dca57b789573Чrunning§runtimeÎr*¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$30afb6e9-1ce0-4004-807b-dca57b789573¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ
Is the adjoint $A^*$ always invertible ?

As $\mathcal{X}$ and $\mathcal{Y}$ have the same dimension, this is equivalent to the $\mathrm{Ker}(A^*) = \{0\}$. Consider an arbitrary $y \in \text{Ker}(A^*)$. Since $A^*(y) = 0$, for all $x \in \mathcal{X}$, we have

$$\begin{align} \langle x, A^*(y) \rangle & = 0\\ \langle A(x), y \rangle & = 0 \end{align}$$

As this is true for all $x$, this is true in particular for $x = A^{-1}(y)$ hence we have $\langle y, y \rangle$ hence $y = 0$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿wŠ 9°persist_js_state·has_pluto_hook_featuresÂÙ$d701392f-0b25-4c27-989a-a61c23c41d9cЧrunning§runtimeÎ$ø¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$d701392f-0b25-4c27-989a-a61c23c41d9c¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyƒªattributes‚¥classÀ¥styleÙ#display: flex; flex-direction: row;£tag£div¨children“’Ú¦

Implicit relation between $x$ and $y$:

$$x^2 + y^2 = 1$$

Two possible explicit functions:

$$\begin{align} y^+(x) & = \sqrt{1 - x^2}\\ y^-(x) & = -\sqrt{1 - x^2} \end{align}$$

Does that contradict the Implicit Function Theorem (IFT) ?

Let $F(y, x) = x^2 + y^2 - 1$. Given an initial point $(x_0, y_0)$ with $x_0^2 + y_0^2 = 1$,

  • if $y_0 > 0$ then IFT holds and $y^\star(x) = y^+(x)$,

  • if $y_0 < 0$ then IFT holds and $y^\star(x) = y^-(x)$,

  • if $y_0 = 0$ then $D_1 F(y_0, x_0) = 2y_0 = 0$ so IFT does not hold.

©text/html’ƒªattributes‚¥classÀ¥style­flex-grow: 1;£tag£div¨children‘’¡ ©text/htmlÙ,application/vnd.pluto.reactdomelement+object’Û4Ž©text/html¤mimeÙ,application/vnd.pluto.reactdomelement+object¬rootassigneeÀ²last_run_timestampËAÚ¿wŠ h8°persist_js_state·has_pluto_hook_featuresÂÙ$f369cf71-6eea-4aaa-b75d-79c2629ce88eЧrunning§runtimeΣødepends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$f369cf71-6eea-4aaa-b75d-79c2629ce88e¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ-

Consider a linear map $A : \mathcal{X} \to \mathcal{Y}$ between linear spaces of the same dimension. Assume $A$ is invertible, what is the adjoint of $A^{-1}$ ?

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� N#°persist_js_state·has_pluto_hook_featuresÂÙ$0867ec30-4fd7-4338-9256-4a84215ad5aaЧrunning§runtimeÎ $å¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$0867ec30-4fd7-4338-9256-4a84215ad5aa¹depends_on_disabled_cells¦queued¤logs�¦output†¤body³0.35355339061171626¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w†'†°persist_js_state·has_pluto_hook_featuresÂÙ$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8Чrunning§runtimeÎ=Y¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ�

Pushforward operator (JVP)

Let $A = -D_1 F(w^\star(\lambda), \lambda)$ and $B = D_2 F(w^\star(\lambda), \lambda)$. Assuming the condition of the IFT holds, we have

$$A \partial w^\star(\lambda)/\partial s_0 = B \partial \lambda/\partial s_0$$

Given a forward tangent $t_{k-1} = \partial \lambda / \partial s_0$, the forward tangent $t_{k} = \partial w^\star(\lambda) / \partial s_0$ can be obtained by solving the linear system:

$$\begin{align} A t_k & = B t_{k-1}\\ t_k & = A^{-1} B t_{k-1} \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�Æ~°persist_js_state·has_pluto_hook_featuresÂÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84Чrunning§runtimeÎÀ¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚë

IFT for linear programs

The system of equation to consider for the IFT is therefore

$$F((x, y), (A, b, c)) = (Ax - b, \text{Diag}(x)(A^\top y - c))$$

We have

$$\begin{align} D_1 F & = \begin{bmatrix} A & 0\\ \text{Diag}(A^\top y - c) & \text{Diag}(x) A^\top \end{bmatrix} \end{align}$$

See OptNet: Differentiable optimization as a layer in neural networks for a generalization to quadratic objective.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� œx°persist_js_state·has_pluto_hook_featuresÂÙ$64c4e42c-e444-44f1-8318-befed7d11bb5Чrunning§runtimeÎþ߸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$64c4e42c-e444-44f1-8318-befed7d11bb5¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ

Solution: precompute the LU decomposition

LU decomposition remember the row operations to make $U$ triangular in the $L$ matrix.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� þ°persist_js_state·has_pluto_hook_featuresÂÙ$b19451b4-2a9e-4c25-888e-d72a13eb7589Чrunning§runtimeÎ/“¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$b19451b4-2a9e-4c25-888e-d72a13eb7589¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙf

Interlude: Adjoint of inverse

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w� 9Ò°persist_js_state·has_pluto_hook_featuresÂÙ$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661Чrunning§runtimeÍ&`¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661¹depends_on_disabled_cells¦queued¤logs�¦output†¤body…¦prefix¥Int64¨elements’’’¡5ªtext/plain’’¡6ªtext/plain¤type¥Array¬prefix_short ¨objectid°f98ae36d97e5048b¤mimeÙ!application/vnd.pluto.tree+object¬rootassignee¡b²last_run_timestampËAÚ¿w„Úº°persist_js_state·has_pluto_hook_featuresÂÙ$0b091706-da13-41f8-9852-4fa685a0fa95Чrunning§runtimeÎ{¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$0b091706-da13-41f8-9852-4fa685a0fa95¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ:

Example

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w�`š°persist_js_state·has_pluto_hook_featuresÂÙ$114b2603-81da-4a5c-baa1-4d95f456aeb3Чrunning§runtimeÎ×Ѹdepends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$114b2603-81da-4a5c-baa1-4d95f456aeb3¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w„�dé°persist_js_state·has_pluto_hook_featuresÂÙ$f22bfdc8-c25d-4844-98e3-08d05533ba56Чrunning§runtimeÎ :Ÿ¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$f22bfdc8-c25d-4844-98e3-08d05533ba56¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚ Q
Proof

Define $f(\lambda, w) = (\lambda, F(w, \lambda))$. The Jacobian is

$$D f(\lambda, w) = \begin{bmatrix} I & 0\\ D_2 F(w, \lambda) & D_1 F(w, \lambda) \end{bmatrix}$$

By assumption, $D_1 F(w, \lambda)$ is invertible so $\det(D f(\lambda, w)) = \det(I)\det(D_1 F(w, \lambda)) \neq 0$. By the inverse function theorem, the inverse of $f$ around $f(\lambda_0, w_0) = (\lambda_0, 0)$ is $C^2$. Let $w^\star(\lambda)$ be the second component of $f^{-1}(\lambda, 0)$: $(\lambda, w^\star(\lambda)) = f^{-1}(\lambda, 0)$. The Jacobian $D w^\star(\lambda)$ is the derivative of the second component of $f^{-1}(\lambda, 0)$ with respect to its first input so it is the block 21 in the Jacobian

$$D f^{-1}(\lambda, 0) = \begin{bmatrix} \sim & \sim\\ D w^\star(\lambda) & \sim \end{bmatrix}$$

By the inverse function theorem

$$D f^{-1}(\lambda, 0) = (D f(\lambda, w))^{-1} = \begin{bmatrix} I & 0\\ D_2 F(w, \lambda) & D_1 F(w, \lambda) \end{bmatrix}^{-1}$$

We can then use the following result:

Schur complement: If $A$ is an invertible matrix then for any matrices $M, B, C, D$ of compatible dimensions:

$$M^{-1} = \begin{bmatrix} A & B\\ C & D \end{bmatrix}^{-1} = \begin{bmatrix} \sim & \sim\\ -(M/A)^{-1}CA^{-1} & \sim \end{bmatrix}$$

where the Schur complement of the block $A$, denoted by $M/A$, is $M/A=D - CA^{-1}B$.

In our case the Schur complement of the block $I$ is $D f(\lambda, w)/I = D_1 F(w, \lambda)$, this means that

$$D w^\star(\lambda) = -D_1 F(w, \lambda)^{-1}D_2 F(w, \lambda).$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿wŠ+°persist_js_state·has_pluto_hook_featuresÂÙ$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2Чrunning§runtimeÎ~¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÙ¶
Can't we do something simpler using the solution of the fixed point and the fixed point equation ?

IFT...

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w‰×Öþ°persist_js_state·has_pluto_hook_featuresÂÙ$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88Чrunning§runtimeÎ�Ëæ¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88¹depends_on_disabled_cells¦queued¤logs�¦output†¤bodyÚÞ
Proof sketch

The proof of bijectivity and that $f$ is $C^2$ in the neighborhood of $f(w_0)$ are in Section 11.5.3 of The Elements of Differentiable Programming book. The formula for $D f^{-1}(\omega)$ is a direct consequence of the chain rule:

$$\begin{align} f \circ f^{-1}(\omega) & = \omega\\ D f(f^{-1}(\omega)) D f^{-1}(\omega) & = I. \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚ¿w‰Øº4°persist_js_state·has_pluto_hook_featuresÂÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35Чrunning§runtimeÎUA¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w†(±p°persist_js_state·has_pluto_hook_featuresÂÙ$0fc99cae-bfe4-4517-a578-453cab15d977Чrunning§runtimeÎî.¸depends_on_skipped_cellsµpublished_object_keys�§errored§cell_idÙ$0fc99cae-bfe4-4517-a578-453cab15d977¹depends_on_disabled_cells¦queued¤logs�¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚ¿w‰Øḛ̈persist_js_state·has_pluto_hook_features±published_objects€¥bonds€´cell_execution_orderÜ1Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6Ù$64250438-9ba6-44f7-b4a0-fcd5d72f05e5Ù$40baa108-eb68-433f-9917-ac334334f198Ù$d6797e7b-fa78-4366-b88f-9925f72a5d0fÙ$d907c5d7-f517-467a-a840-f94868ad7680Ù$5c39f536-346c-48bd-a3c7-acaefb849b9fÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$abee47e4-1b75-4466-908a-e14113b181abÙ$23049939-1b3a-4328-b159-99c3f1470e39Ù$c9603b16-113b-4e05-8517-d814b0879ab8Ù$b23a4c1d-cf35-42e6-b286-7fbcdddfd424Ù$0b091706-da13-41f8-9852-4fa685a0fa95Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3Ù$2b30ae9e-e537-4ad1-a25e-570709c7d517Ù$c1efb93f-efd8-487a-94d2-aa7ecedb61b8Ù$bb4e1c20-1d24-494a-82ae-433e8ba56110Ù$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8Ù$e9fd46e4-78ce-4cba-b20f-1c997c80e842Ù$fa019742-c473-4f1d-86ce-a795edbd1f92Ù$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661Ù$1de5d608-dc91-4f4a-995b-3dcfad38b81cÙ$c3b59d62-144e-4541-9007-19187f2fea1cÙ$64c4e42c-e444-44f1-8318-befed7d11bb5Ù$17f3594f-b568-416f-9a19-38bfd4d99dd0Ù$6f8714a1-1372-42f4-9b51-da93ef2ed4c9Ù$b19451b4-2a9e-4c25-888e-d72a13eb7589Ù$f369cf71-6eea-4aaa-b75d-79c2629ce88eÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2Ù$10ca4307-929a-4e5f-942b-5d6c0e28e2beÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84Ù$b16f6225-1949-4b6d-a4b0-c5c230eb4c7fÙ$66a8b541-b06f-403a-a45d-23461a2c539bÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6Ù$0867ec30-4fd7-4338-9256-4a84215ad5aaÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35Ù$08c4ac83-4361-41d5-b036-789c2475ff8eÙ$cbfc0129-9361-4edb-a467-1456a1f3aeaeÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793Ù$9d883700-0959-4ccd-be50-9ee316a6077eÙ$81deb227-a822-4857-a584-a51cc8ff51f4Ù$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965Ù$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2Ù$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88Ù$0fc99cae-bfe4-4517-a578-453cab15d977Ù$d701392f-0b25-4c27-989a-a61c23c41d9cÙ$f22bfdc8-c25d-4844-98e3-08d05533ba56Ù$528326dd-1344-4baa-9edd-5b09f63669ddÙ$30afb6e9-1ce0-4004-807b-dca57b789573Ù$877c563a-2ce3-4f97-9746-7d8329c0178a®process_status¥ready­julia_version§v1.13.4ªcell_orderÜ1Ù$40baa108-eb68-433f-9917-ac334334f198Ù$d6797e7b-fa78-4366-b88f-9925f72a5d0fÙ$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965Ù$d907c5d7-f517-467a-a840-f94868ad7680Ù$5c39f536-346c-48bd-a3c7-acaefb849b9fÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$abee47e4-1b75-4466-908a-e14113b181abÙ$23049939-1b3a-4328-b159-99c3f1470e39Ù$cb886515-1635-43d7-82fd-a2604d1e3ad6Ù$0867ec30-4fd7-4338-9256-4a84215ad5aaÙ$08c4ac83-4361-41d5-b036-789c2475ff8eÙ$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2Ù$c9603b16-113b-4e05-8517-d814b0879ab8Ù$b23a4c1d-cf35-42e6-b286-7fbcdddfd424Ù$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88Ù$2b30ae9e-e537-4ad1-a25e-570709c7d517Ù$0b091706-da13-41f8-9852-4fa685a0fa95Ù$d701392f-0b25-4c27-989a-a61c23c41d9cÙ$0fc99cae-bfe4-4517-a578-453cab15d977Ù$c1efb93f-efd8-487a-94d2-aa7ecedb61b8Ù$f22bfdc8-c25d-4844-98e3-08d05533ba56Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3Ù$bb4e1c20-1d24-494a-82ae-433e8ba56110Ù$b6f76d2d-3389-4dec-9aef-b7feeb7e0793Ù$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8Ù$e9fd46e4-78ce-4cba-b20f-1c997c80e842Ù$fa019742-c473-4f1d-86ce-a795edbd1f92Ù$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661Ù$1de5d608-dc91-4f4a-995b-3dcfad38b81cÙ$c3b59d62-144e-4541-9007-19187f2fea1cÙ$64c4e42c-e444-44f1-8318-befed7d11bb5Ù$17f3594f-b568-416f-9a19-38bfd4d99dd0Ù$6f8714a1-1372-42f4-9b51-da93ef2ed4c9Ù$528326dd-1344-4baa-9edd-5b09f63669ddÙ$b19451b4-2a9e-4c25-888e-d72a13eb7589Ù$f369cf71-6eea-4aaa-b75d-79c2629ce88eÙ$30afb6e9-1ce0-4004-807b-dca57b789573Ù$877c563a-2ce3-4f97-9746-7d8329c0178aÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2Ù$10ca4307-929a-4e5f-942b-5d6c0e28e2beÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84Ù$9d883700-0959-4ccd-be50-9ee316a6077eÙ$b16f6225-1949-4b6d-a4b0-c5c230eb4c7fÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6Ù$66a8b541-b06f-403a-a45d-23461a2c539bÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35Ù$64250438-9ba6-44f7-b4a0-fcd5d72f05e5Ù$cbfc0129-9361-4edb-a467-1456a1f3aeaeÙ$81deb227-a822-4857-a584-a51cc8ff51f4«cell_inputsÞ1Ù$e9fd46e4-78ce-4cba-b20f-1c997c80e842„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$e9fd46e4-78ce-4cba-b20f-1c997c80e842«code_foldedäcodeÚ`md""" ## Interlude: Repeated linear system solve We need to solve the system ``At_k = Bt_{k-1}`` once by forward tangent, so once by entry of ``s_0`` in case of forward-mode AD. We may also pre-compute ``A^{-1}B`` by solving one linear system by column of ``B``. In both case, we need to solve several linear system with the **same** ``A`` matrix. """Ù$877c563a-2ce3-4f97-9746-7d8329c0178a„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$877c563a-2ce3-4f97-9746-7d8329c0178a«code_foldedäcodeÚ�qa(md"Is the adjoint of the inverse equal to the inverse of the adjoint ?", md""" For arbitrary ``r, t``, we have ```math \begin{align} \langle (A^{-1})^*r, t\rangle &= \langle r, A^{-1} t\rangle\\ &= \langle A^*(A^*)^{-1} r, A^{-1} t \rangle\\ &= \langle (A^*)^{-1} r, AA^{-1} t\rangle\\ &= \langle (A^*)^{-1} r, t\rangle. \end{align} ``` Since ``r, t`` are arbitrary, we have ``(A^{-1})^* = (A^*)^{-1}``. """)Ù$b16f6225-1949-4b6d-a4b0-c5c230eb4c7f„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$b16f6225-1949-4b6d-a4b0-c5c230eb4c7f«code_foldedäcode¬md"## Utils"Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5b„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5b«code_folded¤codeÙ1my_sqrt(a) = fixed_point(x -> (x + a / x) / 2, a)Ù$81deb227-a822-4857-a584-a51cc8ff51f4„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$81deb227-a822-4857-a584-a51cc8ff51f4«code_folded¤codeÚñbegin function qa(question, answer) return @htl("
$question$answer
") end function _inline_html(m::Markdown.Paragraph) return sprint(Markdown.htmlinline, m.content) end function qa(question::Markdown.MD, answer) # `html(question)` will create `

` if `question.content[]` is `Markdown.Paragraph` # This will print the question on a new line and we don't want that: h = HTML(_inline_html(question.content[])) return qa(h, answer) end endÙ$c9603b16-113b-4e05-8517-d814b0879ab8„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$c9603b16-113b-4e05-8517-d814b0879ab8«code_foldedäcodeÚBmd""" # Implicit function theorem > *In a sense, the implicit function theorem can be thought as the mother theorem, as it can be used to prove envelope theorems, the adjoint state method and the inverse function theorem.* Section 11.6 of [The Elements of Differentiable Programming book](https://diffprog.github.io/) """Ù$c3b59d62-144e-4541-9007-19187f2fea1c„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$c3b59d62-144e-4541-9007-19187f2fea1c«code_folded¤code«rref([A b])Ù$b23a4c1d-cf35-42e6-b286-7fbcdddfd424„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$b23a4c1d-cf35-42e6-b286-7fbcdddfd424«code_foldedäcodeÚÀmd""" ## Inverse function theorem We write ``D f`` for the Jacobian and ``D_i F`` for the Jacobian with respect to the ``i``-th argument. Assume * ``f : \mathcal{W} \to \mathcal{W}`` is ``C^2`` * ``D f(w_0)`` is **invertible** Then * ``f`` is bijective from a neighborhood of ``w_0`` to a neighborhood of ``f(w_0)`` * For ``\omega`` in a neighborhood of ``f(w_0)``, ``f^{-1}`` is ``C^2`` and ``D f^{-1}(\omega) = (D f(f^{-1}(\omega)))^{-1}`` """Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$cbfc0129-9361-4edb-a467-1456a1f3aeae«code_foldedäcodeÚsbegin struct Path path::String end function imgpath(path::Path) file = path.path if !('.' in file) file = file * ".png" end return joinpath(joinpath(@__DIR__, "images", file)) end function img(path::Path, args...; kws...) return PlutoUI.LocalResource(imgpath(path), args...) end struct URL url::String end function save_image(url::URL, html_attributes...; name = split(url.url, '/')[end], kws...) path = joinpath("cache", name) return PlutoTeachingTools.RobustLocalResource(url.url, path, html_attributes...), path end function img(url::URL, args...; kws...) r, _ = save_image(url, args...; kws...) return @htl("$r") end function img(file::String, args...; kws...) if startswith(file, "http") img(URL(file), args...; kws...) else img(Path(file), args...; kws...) end end endÙ$fa019742-c473-4f1d-86ce-a795edbd1f92„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$fa019742-c473-4f1d-86ce-a795edbd1f92«code_folded¤code®A = [1 2; 3 4]Ù$528326dd-1344-4baa-9edd-5b09f63669dd„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$528326dd-1344-4baa-9edd-5b09f63669dd«code_foldedäcodeÚýqa(md"Can we also solve the linear system with only access to the matrix-vector product of the linear map ``D_1 F(w^\star(\lambda), \lambda)`` ? (aka matrix-free inversion)", md""" If the matrix is positive semidefinite, we can use the [Conjugate Gradient method](https://en.wikipedia.org/wiki/Conjugate_gradient_method). Otherwise, [GMRES](https://en.wikipedia.org/wiki/Generalized_minimal_residual_method) or [BiCGSTAB](https://en.wikipedia.org/wiki/Biconjugate_gradient_stabilized_method) are options. """)Ù$cb886515-1635-43d7-82fd-a2604d1e3ad6„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6«code_folded¤codeÙ1FiniteDifferences.central_fdm(5, 1)(my_sqrt, 2.0)Ù$d907c5d7-f517-467a-a840-f94868ad7680„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$d907c5d7-f517-467a-a840-f94868ad7680«code_foldedäcodeÚmd""" ## Square root example To illustrate consider [this Jax example](https://docs.jax.dev/en/latest/advanced-autodiff.html#example-implicit-function-differentiation-of-iterative-implementations) rewriting ``x^2 = a`` into ``2x^2 = x^2 + a`` or ``x = (x + a/x)/2`` """Ù$9d883700-0959-4ccd-be50-9ee316a6077e„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$9d883700-0959-4ccd-be50-9ee316a6077e«code_foldedäcodeÚ}md"""## Acknowledgements and further readings * Example from $(img("https://upload.wikimedia.org/wikipedia/commons/8/86/Google_JAX_logo.svg", :height => 16)) : [Implicit function differentiation of iterative implementations](https://docs.jax.dev/en/latest/advanced-autodiff.html#example-implicit-function-differentiation-of-iterative-implementations) * Chapter 11 of [The Elements of Differentiable Programming book](https://diffprog.github.io/) * See [DiffOpt.jl](https://github.com/jump-dev/DiffOpt.jl) for implicit differentiation of $(img("https://jump.dev/assets/jump-logo-with-text.svg", :height => 20)) optimization problems. """Ù$23049939-1b3a-4328-b159-99c3f1470e39„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$23049939-1b3a-4328-b159-99c3f1470e39«code_foldedäcode½md"## AD through fixed point"Ù$5c39f536-346c-48bd-a3c7-acaefb849b9f„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$5c39f536-346c-48bd-a3c7-acaefb849b9f«code_folded¤codeÙjfunction fixed_point(f, x) fx = f(x) while abs(x - fx) > 1e-6 x = fx fx = f(x) end return x endÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0«code_foldedäcode©F = lu(A)Ù$10ca4307-929a-4e5f-942b-5d6c0e28e2be„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$10ca4307-929a-4e5f-942b-5d6c0e28e2be«code_foldedäcodeÚ@md""" # Sensitivity of a linear program Consider the primal-dual pair of programs ```math \begin{align} \min & \,\, c^\top x & \max & \,\, b^\top y\\ Ax & = b & A^\top y & \le c\\ x & \ge 0 \end{align} ``` The Lagrangian function is ```math \mathcal{L}(x, y) = c^\top x - y^\top (Ax - b) = y^\top b - (A^\top y - c)^\top x ``` The KKT condition give ```math \begin{align} \frac{\partial \mathcal{L}}{\partial y} & = Ax - b = 0 & \Leftrightarrow \qquad Ax & = b\\ (A^\top y - c) & \perp x \ge 0 & \Leftrightarrow \qquad \text{Diag}(x)(A^\top y - c) & = 0 \end{align} ``` """Ù$6f8714a1-1372-42f4-9b51-da93ef2ed4c9„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$6f8714a1-1372-42f4-9b51-da93ef2ed4c9«code_foldedäcodeÙÉmd"""As ``L`` and ``U`` are triangular, solving the linear systems ``LUx = b`` can now be done by solving two simple linear systems (and permutation in case of pivoting) 1. ``Lc = b`` 2. ``Ux = c`` """Ù$c1efb93f-efd8-487a-94d2-aa7ecedb61b8„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$c1efb93f-efd8-487a-94d2-aa7ecedb61b8«code_foldedäcodeÚ”ift( "multivariate", md"``F: \mathcal{W} \times \Lambda \to \mathcal{W}``", md"``D_1 F(w_0, \lambda_0)`` is invertible", md""" ```math \begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ D w^\star(\lambda) & = -D_1 F(w^\star(\lambda), \lambda)^{-1}D_2 F(w^\star(\lambda), \lambda) \end{align} ``` """, )Ù$64250438-9ba6-44f7-b4a0-fcd5d72f05e5„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$64250438-9ba6-44f7-b4a0-fcd5d72f05e5«code_folded¤code¿using LinearAlgebra, RowEchelonÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6«code_folded¤codeÙOusing PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, PlutoTeachingToolsÙ$abee47e4-1b75-4466-908a-e14113b181ab„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$abee47e4-1b75-4466-908a-e14113b181ab«code_folded¤codeªmy_sqrt(2)Ù$d6797e7b-fa78-4366-b88f-9925f72a5d0f„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$d6797e7b-fa78-4366-b88f-9925f72a5d0f«code_foldedäcodeÚmd""" # Differentiating numerical procedures Consider a program that numerically converge to solutions: ```julia function f(x) while abs(error) > tol y += # Make some step in the right direction error = # update error end return y end ``` """Ù$b6f76d2d-3389-4dec-9aef-b7feeb7e0793„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793«code_foldedäcodeÙ img("Blondel_Rouvet_Figure_8_3")Ù$40baa108-eb68-433f-9917-ac334334f198„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$40baa108-eb68-433f-9917-ac334334f198«code_foldedäcodeÙÊ@htl("""

Implicit Differentiation

Benoît Legat

$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)Ù$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965«code_foldedäcodeÚÇqa(md"How can we differentiate with respect to `x` ? Forward, reverse, something else ?", md""" * We could throw dual numbers at it and it would work, but `f` would be twice slower with dual numbers and we would need to do it as many times as the dimension of `x`. * We could also create the expression graph to run reverse diff but the graph may be quite large as well. * Some programs may be external libraries written in Fortran or C so we can't easily run AD through it. * Instead, we could run the iteration through the end and once we get the pair `x, y`, we can see if there isn't a better way to find the derivative without rerunning the numerical iterations. This will be implicit differentiation. """)Ù$1de5d608-dc91-4f4a-995b-3dcfad38b81c„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$1de5d608-dc91-4f4a-995b-3dcfad38b81c«code_foldedäcodeÙ–md"Classical Gaussian elimination finds the solution for one vector only, even though the same row operations would be applied for different vectors."Ù$66a8b541-b06f-403a-a45d-23461a2c539b„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$66a8b541-b06f-403a-a45d-23461a2c539b«code_folded¤codeÙ/import ForwardDiff, FiniteDifferences, MooncakeÙ$08c4ac83-4361-41d5-b036-789c2475ff8e„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$08c4ac83-4361-41d5-b036-789c2475ff8e«code_folded¤codeÙ.DI.derivative(my_sqrt, DI.AutoMooncake(), 2.0)Ù$ea41e038-21d8-4321-bc17-25eab0a8cbb2„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2«code_foldedäcodeÚ´md""" ## Pullback operator (VJP) The pullback operation is the adjoint of the pushforward operator: ```math \langle r, A^{-1} B t\rangle = \langle (A^{-1})^* r, B t\rangle = \langle (A^*)^{-1} r, B t\rangle = \langle B^*(A^*)^{-1} r , t\rangle ``` So the pullback operator maps ``r`` to ``B^*(A^*)^{-1} r``. This means that it first solves the linear system ``A^*v = r`` (possibly in a matrix-free way) and then returns ``B^*v``. """Ù$bb4e1c20-1d24-494a-82ae-433e8ba56110„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$bb4e1c20-1d24-494a-82ae-433e8ba56110«code_foldedäcodeÙÕmd""" # Implicit VJP and JVP How can we integrate implicit function in a chain of functions ? Say, ``s_{k-1} = \lambda`` and ``f_k(\lambda) = w^\star(\lambda)`` such that ``F(w^\star(\lambda), \lambda) = 0``. """Ù$2b30ae9e-e537-4ad1-a25e-570709c7d517„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$2b30ae9e-e537-4ad1-a25e-570709c7d517«code_foldedäcodeÚ�ift( "univariate", md"``F: \mathbb{R} \times \mathbb{R} \to \mathbb{R}``", md"``D_1 F(w_0, \lambda_0) \neq 0``", md""" ```math \begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ D w^\star(\lambda) & = -\frac{D_2 F(w^\star(\lambda), \lambda)}{D_1 F(w^\star(\lambda), \lambda)} \end{align} ``` """, )Ù$30afb6e9-1ce0-4004-807b-dca57b789573„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$30afb6e9-1ce0-4004-807b-dca57b789573«code_foldedäcodeÚqa(md"Is the adjoint ``A^*`` always invertible ?", md""" As ``\mathcal{X}`` and ``\mathcal{Y}`` have the same dimension, this is equivalent to the ``\mathrm{Ker}(A^*) = \{0\}``. Consider an arbitrary ``y \in \text{Ker}(A^*)``. Since ``A^*(y) = 0``, for all ``x \in \mathcal{X}``, we have ```math \begin{align} \langle x, A^*(y) \rangle & = 0\\ \langle A(x), y \rangle & = 0 \end{align} ``` As this is true for all ``x``, this is true in particular for ``x = A^{-1}(y)`` hence we have ``\langle y, y \rangle`` hence ``y = 0``. """)Ù$d701392f-0b25-4c27-989a-a61c23c41d9c„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$d701392f-0b25-4c27-989a-a61c23c41d9c«code_foldedäcodeÚHhbox([ md""" Implicit relation between ``x`` and ``y``: ```math x^2 + y^2 = 1 ``` Two possible explicit functions: ```math \begin{align} y^+(x) & = \sqrt{1 - x^2}\\ y^-(x) & = -\sqrt{1 - x^2} \end{align} ``` $circle_qa """, Div(html" ", style = Dict("flex-grow" => "1")), img("Blondel_Rouvet_Figure_11_3", :height => 300), ])Ù$f369cf71-6eea-4aaa-b75d-79c2629ce88e„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$f369cf71-6eea-4aaa-b75d-79c2629ce88e«code_foldedäcodeÙ°md""" Consider a linear map ``A : \mathcal{X} \to \mathcal{Y}`` between linear spaces of the same dimension. Assume ``A`` is invertible, what is the adjoint of ``A^{-1}`` ? """Ù$0867ec30-4fd7-4338-9256-4a84215ad5aa„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$0867ec30-4fd7-4338-9256-4a84215ad5aa«code_folded¤codeÙ$ForwardDiff.derivative(my_sqrt, 2.0)Ù$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8«code_foldedäcodeÚmd""" ## Pushforward operator (JVP) Let ``A = -D_1 F(w^\star(\lambda), \lambda)`` and ``B = D_2 F(w^\star(\lambda), \lambda)``. Assuming the condition of the IFT holds, we have ```math A \partial w^\star(\lambda)/\partial s_0 = B \partial \lambda/\partial s_0 ``` Given a forward tangent ``t_{k-1} = \partial \lambda / \partial s_0``, the forward tangent ``t_{k} = \partial w^\star(\lambda) / \partial s_0`` can be obtained by solving the linear system: ```math \begin{align} A t_k & = B t_{k-1}\\ t_k & = A^{-1} B t_{k-1} \end{align} ``` """Ù$6f4e1705-22f2-4be6-9f93-cbaabf809e84„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84«code_foldedäcodeÚçmd""" ## IFT for linear programs The system of equation to consider for the IFT is therefore ```math F((x, y), (A, b, c)) = (Ax - b, \text{Diag}(x)(A^\top y - c)) ``` We have ```math \begin{align} D_1 F & = \begin{bmatrix} A & 0\\ \text{Diag}(A^\top y - c) & \text{Diag}(x) A^\top \end{bmatrix} \end{align} ``` See [OptNet: Differentiable optimization as a layer in neural networks](https://dl.acm.org/doi/abs/10.5555/3305381.3305396) for a generalization to quadratic objective. """Ù$64c4e42c-e444-44f1-8318-befed7d11bb5„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$64c4e42c-e444-44f1-8318-befed7d11bb5«code_foldedäcodeÙ’md""" ## Solution: precompute the LU decomposition LU decomposition remember the row operations to make ``U`` triangular in the ``L`` matrix. """Ù$b19451b4-2a9e-4c25-888e-d72a13eb7589„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$b19451b4-2a9e-4c25-888e-d72a13eb7589«code_foldedäcodeÙ$md"## Interlude: Adjoint of inverse"Ù$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661«code_folded¤codeªb = [5, 6]Ù$0b091706-da13-41f8-9852-4fa685a0fa95„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$0b091706-da13-41f8-9852-4fa685a0fa95«code_foldedäcode²md"""## Example"""Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$114b2603-81da-4a5c-baa1-4d95f456aeb3«code_foldedäcodeÚ­function ift(case, F_def, ift_inv, ift_eq) return md""" ## Implicit function theorem ($case case) Assume * $F_def * ``(w_0, \lambda_0)`` such that ``F(w_0, \lambda_0) = 0`` and $(ift_inv.content[].content) * ``F(w, \lambda)`` is ``C^2`` in a neighborhood ``\mathcal{U}`` of ``(w_0, \lambda_0)`` Then there exists a neighborhood ``\mathcal{V} \subseteq \mathcal{U}`` where exists ``w^\star(\lambda)`` such that $ift_eq """ end;Ù$f22bfdc8-c25d-4844-98e3-08d05533ba56„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$f22bfdc8-c25d-4844-98e3-08d05533ba56«code_foldedäcodeÚ qa(md"**Proof**", md""" Define ``f(\lambda, w) = (\lambda, F(w, \lambda))``. The Jacobian is ```math D f(\lambda, w) = \begin{bmatrix} I & 0\\ D_2 F(w, \lambda) & D_1 F(w, \lambda) \end{bmatrix} ``` By assumption, ``D_1 F(w, \lambda)`` is invertible so ``\det(D f(\lambda, w)) = \det(I)\det(D_1 F(w, \lambda)) \neq 0``. By the inverse function theorem, the inverse of ``f`` around ``f(\lambda_0, w_0) = (\lambda_0, 0)`` is ``C^2``. Let ``w^\star(\lambda)`` be the second component of ``f^{-1}(\lambda, 0)``: ``(\lambda, w^\star(\lambda)) = f^{-1}(\lambda, 0)``. The Jacobian ``D w^\star(\lambda)`` is the derivative of the second component of ``f^{-1}(\lambda, 0)`` with respect to its first input so it is the block 21 in the Jacobian ```math D f^{-1}(\lambda, 0) = \begin{bmatrix} \sim & \sim\\ D w^\star(\lambda) & \sim \end{bmatrix} ``` By the inverse function theorem ```math D f^{-1}(\lambda, 0) = (D f(\lambda, w))^{-1} = \begin{bmatrix} I & 0\\ D_2 F(w, \lambda) & D_1 F(w, \lambda) \end{bmatrix}^{-1} ``` We can then use the following result: > [**Schur complement**](https://en.wikipedia.org/wiki/Schur_complement): If ``A`` is an invertible matrix then for any matrices ``M, B, C, D`` of compatible dimensions: > ```math > M^{-1} = > \begin{bmatrix} > A & B\\ > C & D > \end{bmatrix}^{-1} = \begin{bmatrix} > \sim & \sim\\ > -(M/A)^{-1}CA^{-1} & \sim > \end{bmatrix} > ``` > where the *Schur complement* of the block ``A``, denoted by ``M/A``, is ``M/A=D - CA^{-1}B``. In our case the Schur complement of the block ``I`` is ``D f(\lambda, w)/I = D_1 F(w, \lambda)``, this means that ```math D w^\star(\lambda) = -D_1 F(w, \lambda)^{-1}D_2 F(w, \lambda). ``` """)Ù$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2«code_foldedäcodeÙvqa(md"Can't we do something simpler using the solution of the fixed point and the fixed point equation ?", md"IFT...")Ù$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88«code_foldedäcodeÚ­qa(md"**Proof sketch**", md""" The proof of bijectivity and that ``f`` is ``C^2`` in the neighborhood of ``f(w_0)`` are in Section 11.5.3 of [The Elements of Differentiable Programming book](https://diffprog.github.io/). The formula for ``D f^{-1}(\omega)`` is a direct consequence of the chain rule: ```math \begin{align} f \circ f^{-1}(\omega) & = \omega\\ D f(f^{-1}(\omega)) D f^{-1}(\omega) & = I. \end{align} ``` """)Ù$878bec4d-9d8a-4e92-9817-ddcd95bd8d35„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35«code_folded¤codeÙ%import DifferentiationInterface as DIÙ$0fc99cae-bfe4-4517-a578-453cab15d977„¨metadataƒ¨disabled©show_logsîskip_as_script§cell_idÙ$0fc99cae-bfe4-4517-a578-453cab15d977«code_foldedäcodeÚ‚circle_qa = qa(md"Does that contradict the Implicit Function Theorem (IFT) ?", md""" Let ``F(y, x) = x^2 + y^2 - 1``. Given an initial point ``(x_0, y_0)`` with ``x_0^2 + y_0^2 = 1``, * if ``y_0 > 0`` then IFT holds and ``y^\star(x) = y^+(x)``, * if ``y_0 < 0`` then IFT holds and ``y^\star(x) = y^-(x)``, * if ``y_0 = 0`` then ``D_1 F(y_0, x_0) = 2y_0 = 0`` so IFT does not hold. """);´last_hot_reload_time˱cell_dependenciesÞ1Ù$e9fd46e4-78ce-4cba-b20f-1c997c80e842„´precedence_heuristic §cell_idÙ$e9fd46e4-78ce-4cba-b20f-1c997c80e842´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$877c563a-2ce3-4f97-9746-7d8329c0178a„´precedence_heuristic §cell_idÙ$877c563a-2ce3-4f97-9746-7d8329c0178a´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$b16f6225-1949-4b6d-a4b0-c5c230eb4c7f„´precedence_heuristic §cell_idÙ$b16f6225-1949-4b6d-a4b0-c5c230eb4c7f´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5b„´precedence_heuristic §cell_idÙ$a73e6557-9fed-4a1e-9e8e-c67e500eba5b´downstream_cells_map�§my_sqrt”Ù$abee47e4-1b75-4466-908a-e14113b181abÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6Ù$0867ec30-4fd7-4338-9256-4a84215ad5aaÙ$08c4ac83-4361-41d5-b036-789c2475ff8e²upstream_cells_mapƒ¡/�¡+�«fixed_point‘Ù$5c39f536-346c-48bd-a3c7-acaefb849b9fÙ$81deb227-a822-4857-a584-a51cc8ff51f4„´precedence_heuristic §cell_idÙ$81deb227-a822-4857-a584-a51cc8ff51f4´downstream_cells_map‚¢qa˜Ù$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965Ù$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2Ù$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88Ù$0fc99cae-bfe4-4517-a578-453cab15d977Ù$f22bfdc8-c25d-4844-98e3-08d05533ba56Ù$528326dd-1344-4baa-9edd-5b09f63669ddÙ$30afb6e9-1ce0-4004-807b-dca57b789573Ù$877c563a-2ce3-4f97-9746-7d8329c0178a¬_inline_html�²upstream_cells_mapˆ°HypertextLiteral‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6¸HypertextLiteral.content�¤@htl�·HypertextLiteral.Result�¨Markdown�¦sprint�¤HTML�·HypertextLiteral.Bypass�Ù$c9603b16-113b-4e05-8517-d814b0879ab8„´precedence_heuristic §cell_idÙ$c9603b16-113b-4e05-8517-d814b0879ab8´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$c3b59d62-144e-4541-9007-19187f2fea1c„´precedence_heuristic §cell_idÙ$c3b59d62-144e-4541-9007-19187f2fea1c´downstream_cells_map€²upstream_cells_mapƒ¤rref�¡A‘Ù$fa019742-c473-4f1d-86ce-a795edbd1f92¡b‘Ù$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661Ù$b23a4c1d-cf35-42e6-b286-7fbcdddfd424„´precedence_heuristic §cell_idÙ$b23a4c1d-cf35-42e6-b286-7fbcdddfd424´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae„´precedence_heuristic §cell_idÙ$cbfc0129-9361-4edb-a467-1456a1f3aeae´downstream_cells_map…£img“Ù$d701392f-0b25-4c27-989a-a61c23c41d9cÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793Ù$9d883700-0959-4ccd-be50-9ee316a6077e£URL‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeaeªsave_image�§imgpath�¤Path‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae²upstream_cells_mapÞ°HypertextLiteral‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6¸HypertextLiteral.content�¦String�·HypertextLiteral.Result�¤@htl�µPlutoUI.LocalResource�§PlutoUI‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6£URL‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae¨joinpath�¡!�·HypertextLiteral.Bypass�¿HypertextLiteral.attribute_pair�¢in�ªstartswith�Ù&PlutoTeachingTools.RobustLocalResource�¥split�¨@__DIR__�¤Path‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae¡*�²PlutoTeachingTools‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6Ù$fa019742-c473-4f1d-86ce-a795edbd1f92„´precedence_heuristic §cell_idÙ$fa019742-c473-4f1d-86ce-a795edbd1f92´downstream_cells_map�¡A’Ù$c3b59d62-144e-4541-9007-19187f2fea1cÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0²upstream_cells_map€Ù$528326dd-1344-4baa-9edd-5b09f63669dd„´precedence_heuristic §cell_idÙ$528326dd-1344-4baa-9edd-5b09f63669dd´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$cb886515-1635-43d7-82fd-a2604d1e3ad6„´precedence_heuristic §cell_idÙ$cb886515-1635-43d7-82fd-a2604d1e3ad6´downstream_cells_map€²upstream_cells_mapƒ½FiniteDifferences.central_fdm�±FiniteDifferences‘Ù$66a8b541-b06f-403a-a45d-23461a2c539b§my_sqrt‘Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$d907c5d7-f517-467a-a840-f94868ad7680„´precedence_heuristic §cell_idÙ$d907c5d7-f517-467a-a840-f94868ad7680´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$9d883700-0959-4ccd-be50-9ee316a6077e„´precedence_heuristic §cell_idÙ$9d883700-0959-4ccd-be50-9ee316a6077e´downstream_cells_map€²upstream_cells_map„£img‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae§@md_str�¨getindex�¢=>�Ù$23049939-1b3a-4328-b159-99c3f1470e39„´precedence_heuristic §cell_idÙ$23049939-1b3a-4328-b159-99c3f1470e39´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$5c39f536-346c-48bd-a3c7-acaefb849b9f„´precedence_heuristic §cell_idÙ$5c39f536-346c-48bd-a3c7-acaefb849b9f´downstream_cells_map�«fixed_point‘Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5b²upstream_cells_map…¦isless�¡<�¡-�¡>�£abs�Ù$17f3594f-b568-416f-9a19-38bfd4d99dd0„´precedence_heuristic §cell_idÙ$17f3594f-b568-416f-9a19-38bfd4d99dd0´downstream_cells_map�¡F�²upstream_cells_map‚¢lu�¡A‘Ù$fa019742-c473-4f1d-86ce-a795edbd1f92Ù$10ca4307-929a-4e5f-942b-5d6c0e28e2be„´precedence_heuristic §cell_idÙ$10ca4307-929a-4e5f-942b-5d6c0e28e2be´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$6f8714a1-1372-42f4-9b51-da93ef2ed4c9„´precedence_heuristic §cell_idÙ$6f8714a1-1372-42f4-9b51-da93ef2ed4c9´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$c1efb93f-efd8-487a-94d2-aa7ecedb61b8„´precedence_heuristic §cell_idÙ$c1efb93f-efd8-487a-94d2-aa7ecedb61b8´downstream_cells_map€²upstream_cells_mapƒ§@md_str�¨getindex�£ift‘Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3Ù$64250438-9ba6-44f7-b4a0-fcd5d72f05e5„´precedence_heuristic§cell_idÙ$64250438-9ba6-44f7-b4a0-fcd5d72f05e5´downstream_cells_map‚­LinearAlgebra�ªRowEchelon�²upstream_cells_map€Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6„´precedence_heuristic§cell_idÙ$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6´downstream_cells_map„°HypertextLiteral“Ù$40baa108-eb68-433f-9917-ac334334f198Ù$cbfc0129-9361-4edb-a467-1456a1f3aeaeÙ$81deb227-a822-4857-a584-a51cc8ff51f4§PlutoUI’Ù$40baa108-eb68-433f-9917-ac334334f198Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae²ExperimentalLayout�²PlutoTeachingTools’Ù$40baa108-eb68-433f-9917-ac334334f198Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae²upstream_cells_map€Ù$abee47e4-1b75-4466-908a-e14113b181ab„´precedence_heuristic §cell_idÙ$abee47e4-1b75-4466-908a-e14113b181ab´downstream_cells_map€²upstream_cells_map�§my_sqrt‘Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$d6797e7b-fa78-4366-b88f-9925f72a5d0f„´precedence_heuristic §cell_idÙ$d6797e7b-fa78-4366-b88f-9925f72a5d0f´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$b6f76d2d-3389-4dec-9aef-b7feeb7e0793„´precedence_heuristic §cell_idÙ$b6f76d2d-3389-4dec-9aef-b7feeb7e0793´downstream_cells_map€²upstream_cells_map�£img‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeaeÙ$40baa108-eb68-433f-9917-ac334334f198„´precedence_heuristic §cell_idÙ$40baa108-eb68-433f-9917-ac334334f198´downstream_cells_map€²upstream_cells_map‰°HypertextLiteral‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6¸HypertextLiteral.content�Ù$PlutoTeachingTools.ChooseDisplayMode�·HypertextLiteral.Result�¤@htl�·PlutoUI.TableOfContents�§PlutoUI‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6²PlutoTeachingTools‘Ù$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6·HypertextLiteral.Bypass�Ù$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965„´precedence_heuristic §cell_idÙ$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$1de5d608-dc91-4f4a-995b-3dcfad38b81c„´precedence_heuristic §cell_idÙ$1de5d608-dc91-4f4a-995b-3dcfad38b81c´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$66a8b541-b06f-403a-a45d-23461a2c539b„´precedence_heuristic §cell_idÙ$66a8b541-b06f-403a-a45d-23461a2c539b´downstream_cells_mapƒ¨Mooncake�«ForwardDiff‘Ù$0867ec30-4fd7-4338-9256-4a84215ad5aa±FiniteDifferences‘Ù$cb886515-1635-43d7-82fd-a2604d1e3ad6²upstream_cells_map€Ù$08c4ac83-4361-41d5-b036-789c2475ff8e„´precedence_heuristic §cell_idÙ$08c4ac83-4361-41d5-b036-789c2475ff8e´downstream_cells_map€²upstream_cells_map„¯DI.AutoMooncake�­DI.derivative�¢DI‘Ù$878bec4d-9d8a-4e92-9817-ddcd95bd8d35§my_sqrt‘Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2„´precedence_heuristic §cell_idÙ$ea41e038-21d8-4321-bc17-25eab0a8cbb2´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$bb4e1c20-1d24-494a-82ae-433e8ba56110„´precedence_heuristic §cell_idÙ$bb4e1c20-1d24-494a-82ae-433e8ba56110´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$2b30ae9e-e537-4ad1-a25e-570709c7d517„´precedence_heuristic §cell_idÙ$2b30ae9e-e537-4ad1-a25e-570709c7d517´downstream_cells_map€²upstream_cells_mapƒ§@md_str�¨getindex�£ift‘Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3Ù$30afb6e9-1ce0-4004-807b-dca57b789573„´precedence_heuristic §cell_idÙ$30afb6e9-1ce0-4004-807b-dca57b789573´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$d701392f-0b25-4c27-989a-a61c23c41d9c„´precedence_heuristic §cell_idÙ$d701392f-0b25-4c27-989a-a61c23c41d9c´downstream_cells_map€²upstream_cells_map‹­Base.getindex�¢=>�®Base.Docs.HTML�¤Base�¤hbox�£img‘Ù$cbfc0129-9361-4edb-a467-1456a1f3aeae©@html_str�£Div�§@md_str�©circle_qa‘Ù$0fc99cae-bfe4-4517-a578-453cab15d977¤Dict�Ù$f369cf71-6eea-4aaa-b75d-79c2629ce88e„´precedence_heuristic §cell_idÙ$f369cf71-6eea-4aaa-b75d-79c2629ce88e´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$0867ec30-4fd7-4338-9256-4a84215ad5aa„´precedence_heuristic §cell_idÙ$0867ec30-4fd7-4338-9256-4a84215ad5aa´downstream_cells_map€²upstream_cells_mapƒ¶ForwardDiff.derivative�«ForwardDiff‘Ù$66a8b541-b06f-403a-a45d-23461a2c539b§my_sqrt‘Ù$a73e6557-9fed-4a1e-9e8e-c67e500eba5bÙ$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8„´precedence_heuristic §cell_idÙ$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$6f4e1705-22f2-4be6-9f93-cbaabf809e84„´precedence_heuristic §cell_idÙ$6f4e1705-22f2-4be6-9f93-cbaabf809e84´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$64c4e42c-e444-44f1-8318-befed7d11bb5„´precedence_heuristic §cell_idÙ$64c4e42c-e444-44f1-8318-befed7d11bb5´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$b19451b4-2a9e-4c25-888e-d72a13eb7589„´precedence_heuristic §cell_idÙ$b19451b4-2a9e-4c25-888e-d72a13eb7589´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661„´precedence_heuristic §cell_idÙ$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661´downstream_cells_map�¡b‘Ù$c3b59d62-144e-4541-9007-19187f2fea1c²upstream_cells_map€Ù$0b091706-da13-41f8-9852-4fa685a0fa95„´precedence_heuristic §cell_idÙ$0b091706-da13-41f8-9852-4fa685a0fa95´downstream_cells_map€²upstream_cells_map‚§@md_str�¨getindex�Ù$114b2603-81da-4a5c-baa1-4d95f456aeb3„´precedence_heuristic §cell_idÙ$114b2603-81da-4a5c-baa1-4d95f456aeb3´downstream_cells_map�£ift’Ù$2b30ae9e-e537-4ad1-a25e-570709c7d517Ù$c1efb93f-efd8-487a-94d2-aa7ecedb61b8²upstream_cells_map‚§@md_str�¨getindex�Ù$f22bfdc8-c25d-4844-98e3-08d05533ba56„´precedence_heuristic §cell_idÙ$f22bfdc8-c25d-4844-98e3-08d05533ba56´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2„´precedence_heuristic §cell_idÙ$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88„´precedence_heuristic §cell_idÙ$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88´downstream_cells_map€²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�Ù$878bec4d-9d8a-4e92-9817-ddcd95bd8d35„´precedence_heuristic §cell_idÙ$878bec4d-9d8a-4e92-9817-ddcd95bd8d35´downstream_cells_map�¢DI‘Ù$08c4ac83-4361-41d5-b036-789c2475ff8e²upstream_cells_map€Ù$0fc99cae-bfe4-4517-a578-453cab15d977„´precedence_heuristic §cell_idÙ$0fc99cae-bfe4-4517-a578-453cab15d977´downstream_cells_map�©circle_qa‘Ù$d701392f-0b25-4c27-989a-a61c23c41d9c²upstream_cells_mapƒ¢qa‘Ù$81deb227-a822-4857-a584-a51cc8ff51f4§@md_str�¨getindex�©shortpath«implicit.jl®last_save_timeËAÚ¿w€täç«notebook_idÙ$23532244-e374-11f1-b929-2d738f8f37cc¥nbpkgŠ­busy_packages�Ù,waiting_for_permission_but_probably_disabled§enabledðterminal_outputsŠ­LinearAlgebraÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...ªRowEchelonÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...°HypertextLiteralÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...¨MooncakeÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...§PlutoUIÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...ªnbpkg_syncÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...«ForwardDiffÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...±FiniteDifferencesÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...²PlutoTeachingToolsÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...¸DifferentiationInterfaceÚý Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_fbmdamaxbi/Manifest.toml` [deac9b47] ↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0 [29816b5a] ↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0 [14a3606d] ↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.11.5 [4536629a] ↑ OpenBLAS_jll v0.3.30+0 ⇒ v0.3.30+1 [458c3c95] ↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0 [83775a58] ↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0 [8e850ede] ↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0 Instantiating... === Precompiling... === Waiting for notebook process to start... Done. Starting precompilation...¶waiting_for_permission·restart_recommended_msgÀ´restart_required_msgÀ²installed_versions‹°HypertextLiteral¥1.0.0ªRowEchelon¥0.2.1¨Mooncake¦0.5.57§PlutoUI¦0.7.83Ù!__internal_julia_manifest_version¦1.13.4­LinearAlgebra¦stdlib¸__internal_julia_version¦1.13.4±FiniteDifferences§0.12.34«ForwardDiff¥1.4.6²PlutoTeachingTools¥0.4.7¸DifferentiationInterface¦0.7.21¯install_time_nsÎ�wg¬instantiatedípluto_version¦v1.1.0«in_temp_dirÂ