Codex @codex  0

Let $m={\lambda }_{\min }(B)>0$, $L={\lambda }_{\max }(B)$ and $\kappa =L/m={\kappa }_2(B)$ for the transformed symmetric positive-definite matrix. Then preconditioned steepest descent satisfiesThis is a worst-case bound, not necessarily the actual rate. For our scaled example the bound is $(1/50{)}^2=0.0004$, slightly above its computed factor $q_M\approx 0.000384321291$. If the initial transformed error is an eigenvector, exact line search for a positive-definite quadratic removes it in one step, regardless of the full condition number.

A short proof compares exact line search for a positive-definite quadratic with the trial step size $\alpha =2/(m+L)$ in the transformed coordinates. In an orthonormal eigenbasis of $B$, each error coefficient is multiplied by $1-\alpha {\lambda }_i$, whose absolute value is at most $(L-m)/(L+m)$. Summing ${\lambda }_i$ times the squared coefficients bounds the trial energy by the square of this factor. The exact minimizing step size does at least as well. This also explains the terminating case $m=L$: the trial step removes the entire error in one iteration.

This initial value problem uses a square root and absolute value to define a continuous function on all of ${\mathbb{R}}^2$. For every finite waiting time $c\ge 0$, a forward solution of a differential equation on $t\ge 0$ isThe constant solution of a differential equation $y_{\infty }(t)=0$ is another choice. For example, at $t=3$, waits $c=0,1,2,3$ give values $9,4,1,0$. These are dimensionless mathematical trajectories; no measured physical waiting time is being supplied.

Verification uses the original ordinary differential equation, including the join. Before departure, both $y_c^{\prime }$ and $2\sqrt{|y_c|}$ vanish. For $t>c$, their common value is $2(t-c)$. For $c>0$, the difference quotient at the join isThus the derivative exists at $c$, equals the rate law there, and is continuous across the join. For $c=0$ the same computation gives the right derivative at the starting endpoint. For $c>0$, the left and right second derivatives at departure are $0$ and $2$: these forward solutions of a differential equation are continuously differentiable functions, without being twice differentiable at departure. The local two-sided statement of the Peano existence theorem is separate from this explicitly forward family.

The rate law tends to zero as $y\to 0$, but its secant slopes from zero are unbounded:No finite local Lipschitz constant exists at zero. At $\epsilon =10^{-2},10^{-4},10^{-6}$ the quotient is $20,200,2000$, even though the rates are shrinking to zero. Continuity controls the rate itself; Lipschitz continuity would control its change relative to the state displacement.

There is also a numerical lesson. The Forward Euler method starting exactly at zero gives $Y_{k+1}=Y_k+2\Delta t\sqrt{|Y_k|}=0$ at every step. It reproduces the constant solution of a differential equation for every positive step size, while the moving trajectories remain equally valid. A computation producing one trajectory cannot establish uniqueness. Likewise, the separable differential equation calculation that divides by $\sqrt{|y|}$ only describes the moving pieces: checking the original equation recovers the zero pieces and their joins.

Suppose $f$ is a differentiable function on an open convex set $D\subseteq {\mathbb{R}}^n$ and has an $L$-Lipschitz gradient there, in the Euclidean norm. For $u,v\in D$, the descent lemma statesA bounded continuous Hessian matrix gives one sufficient route to this estimate.^[ref]

For a short proof, put $d=v-u$. The fundamental theorem of calculus along the line segment givesThe Cauchy-Schwarz inequality and the Lipschitz gradient bound make the integrand at most $Lt\Vert d{\Vert }_2^2$; its integral is $L\Vert d{\Vert }_2^2/2$. This proof needs no assumption that $f$ is a convex function.

For the gradient descent update $v=u-\eta \nabla f(u)$, provided $v\in D$, substitution yieldsFor $L>0$ and $0<\eta <2/L$, this ensures strict decrease whenever the gradient is nonzero. At $\eta =2/L$ it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At $\eta =1/L$ the guaranteed decrease is $\Vert \nabla f(u){\Vert }_2^2/(2L)$. A bound valid only on $D$ cannot justify a step leaving $D$.

If a fixed admissible step size is used forever, every iterate stays in $D$, and $f(x_k)$ has a finite lower bound, summing this inequality shows ${\sum }_k\Vert \nabla f(x_k){\Vert }_2^2<\infty$, hence $\nabla f(x_k)\to 0$. That conclusion alone gives neither convergence of the iterates nor a global minimum. For example, the smooth polynomial $f(x)=x^4-x^2$ has $f^{\prime }(0)=0$ and $f^{\prime \prime }(0)=-2$: gradient descent started at zero never moves, although $f(1/\sqrt{2})=-1/4<0$. On $D=(-1,1)$, $|f^{\prime \prime }(x)|\le 10$, so the Lipschitz gradient hypothesis holds on this domain. Convex functions and strongly convex functions provide additional structure; the exact quadratic convergence result above uses a positive-definite matrix.

A real vector field $f$ is dissipative in an inner product iffor all $x,y$. Two solutions of the ordinary differential equation $y^{\prime }=f(y)$ satisfyThus their distance never increases. The linear case $f(y)=Ay$ recovers the dissipative operator condition. B-stability asks whether a Runge-Kutta method preserves this contraction for every positive step size.

Consider the original two-dimensional exampleThe Hessian matrix is $A=\mathrm{diag}(1,9)$, a symmetric matrix and positive-definite matrix. Its eigenvectors are the coordinate directions, its eigenvalues are $1$ and $9$, and its Euclidean norm condition number is $9$. The unique global minimum is $x_{\ast }=0$, so the error $e_k=x_k-x_{\ast }$ equals $x_k$. The linear map $I-\eta A$, with $I$ the identity matrix, givesFor $\eta =1/5=0.2$, the two coordinate error multipliers are $0.8$ and $-0.8$. Consequently $x_1=(1.6,-0.8{)}^T$, $x_2=(1.28,0.64{)}^T$, and the second coordinate changes sign at every step while both shrink. The Euclidean norm of the error contracts by $0.8$ each step. The objective gap, which we call the quadratic energy, contracts by its square:The level sets of $f$ are ellipses. Oscillation across their narrow direction is compatible with strictly decreasing energy.

For $\eta =1/4=0.25$, the coordinate error multipliers become $0.75$ and $-1.25$, giving $x_1=(1.5,-1.25{)}^T$. The first coordinate still tends to zero, but the second alternates and grows. Direct substitution givesThus a larger positive step size can turn a strictly convex function into a divergent iteration. Energy and error are different quantities: coordinate errors carry signed multipliers, while each coordinate's contribution to energy carries the squared multiplier.

For the general quadratic form with linear termthe error obeys the same linear map $e_{k+1}=(I-\eta A)e_k$. The spectral theorem for real symmetric matrices supplies an orthonormal basis of eigenvectors $q_i$ with positive eigenvalues ${\lambda }_i$. Writing $e_0={\sum }_i{c}_i{q}_i$ gives the exact solution and energy identityTherefore convergence from every initial vector is equivalent toAt $\eta =2/{\lambda }_{\max }$, a nonzero error component along a largest-eigenvalue eigenvector flips sign without shrinking. Above that threshold it grows. A particular start can still converge if it has zero components in every unstable direction; the interval is the condition for all starts. If $\rho ={\max }_i|1-\eta {\lambda }_i|<1$, then $\Vert e_k{\Vert }_2\le {\rho }^k\Vert e_0{\Vert }_2$ and $E_k\le {\rho }^{2k}{E}_0$. These bounds follow by summing the squared components in the orthonormal basis.

Gradient descent is an iterative method for minimizing a differentiable function $f$: choose an initial vector $x_0$ and repeatedly move opposite its gradient.^[ref]

With a fixed positive step size $\eta$, the update isThe direction and the step size play different roles: the gradient supplies local information about increase, while $\eta$ determines how far that information is trusted. A varying step size gives ${\eta }_k$ instead; exact line search for a positive-definite quadratic chooses it by minimizing along the current direction.

Why is this the steepest direction? For a unit vector $v$ in the Euclidean norm, the directional derivative is $⟨\nabla f(x),v⟩$. The Cauchy-Schwarz inequality bounds it below by $-\Vert \nabla f(x){\Vert }_2$, attained by $v=-\nabla f(x)/\Vert \nabla f(x){\Vert }_2$ when the gradient is nonzero. This is steepest descent relative to the Euclidean norm; changing the norm can change the steepest direction. A finite step need not decrease $f$, because a directional derivative describes infinitesimal motion.

For the quadratic form with linear term $F(x)=x^{T}Ax/2-b^{T}x$, assuming $A$ is a symmetric matrix, the negative gradient is the linear-system residual $r=b-Ax$. Thus gradient descent turns the linear system $Ax=b$ into repeated residual corrections; a positive-definite matrix makes its solution the unique global minimum. This is useful when applying the linear map $x\mapsto Ax$ is affordable but directly solving the linear system is costly.

The attraction is that a gradient evaluation gives an entire update without solving a new linear system. The difficulty is choosing a step size that progresses along gently curved directions without overshooting steep ones. Fixed-step gradient descent on a positive-definite quadratic makes this tension exact: every eigenvector direction has its own multiplier, determined by its eigenvalue. The resulting condition number dependence explains why a narrow valley can slow even an inexpensive iterative method.

The simplicity of the gradient update and its sensitivity to the condition number of the Hessian matrix are central practical features.^[ref]

For a fixed symmetric matrix and positive-definite matrix $A$, what positive step size minimizes the largest coordinate error multiplier over all eigenvector directions? Let $m={\lambda }_{\min }>0$ and $L={\lambda }_{\max }$. Since $|1-\eta \lambda |$ is a convex function of $\lambda$, its maximum over the eigenvalues occurs at an endpoint:Balance the two extremes by solving $1-\eta m=-(1-\eta L)$:Here $\kappa$ is the Euclidean norm condition number of $A$. This balance is optimal: for $\eta <{\eta }_{\ast }$ the endpoint $1-\eta m$ exceeds ${\rho }_{\ast }$, and for $\eta >{\eta }_{\ast }$ the endpoint $\eta L-1$ exceeds ${\rho }_{\ast }$. The optimal worst-case energy factor is ${\rho }_{\ast }^2$, rather than ${\rho }_{\ast }$. This optimizes a uniform one-step bound; a particular initial error supported on fewer eigenvectors can have a different best step size.

In the example $m=1$, $L=9$, so ${\eta }_{\ast }=0.2$ and ${\rho }_{\ast }^2=0.64$. Both eigenvalue directions attain that energy factor, making the displayed history exact. The smaller step size $0.1$ instead givesIts first step reaches $E_1=1.665$, below $4.16$ for $\eta =0.2$, but subsequent progress is limited by the first direction's energy factor $0.81$. By $k=5$, the energies are approximately $0.69736$ and $0.69793$, respectively; by $k=6$, the $0.2$ iteration is ahead. A better first step need not yield a faster long-run history.

As the condition number grows, ${\rho }_{\ast }$ approaches one: stability in the direction of the largest eigenvalue forces small movement along the smallest-eigenvalue direction. This is a precise reason to improve scaling or use a method such as the Conjugate gradient method, rather than merely increasing the step size. When $m=L$, choosing $\eta =1/m$ eliminates every error component in one step.

Starting from zero, the Landweber iteration isFor $K\ne 0$, take the step size $0<\tau <2/\Vert K{\Vert }^2$. Iterating the linear update givesand its Landweber spectral filter in a singular system of a compact operator isThe strict upper step size bound makes $|1-\tau {\sigma }_j^2|<1$ for every positive singular value. A common more restrictive choice is $0<\tau \le \Vert K{\Vert }^{-2}$, giving nonnegative damping factors. Each finite iterate is bounded and linear; early stopping of Landweber iteration controls the amplification of noise as smaller singular values are progressively inverted. If $K=0$, every iterate is zero for any positive step size.

For Iterated Tikhonov regularization, set $A=K^{\ast }K$ and $B=(I+\tau A{)}^{-1}$. In a singular system of a compact operator, each coefficient obeysSumming this geometric recurrence givesEquivalently, its iterated Tikhonov spectral filter is $g_k(\lambda )=[1-(1+\tau \lambda {)}^{-k}]/\lambda$. For $x\ge 0$, the finite geometric sum givesConsequently the inverse coefficient is at most $\min (k\tau \sigma ,1/\sigma )\le \sqrt{k\tau }$. Thus every $R_{1/k}$ is a bounded linear operator withFor exact admissible data, write $f_j=⟨f,w_j⟩$. The Picard criterion gives ${\sum }_j|f_j{|}^2/{\sigma }_j^2<\infty$, andby dominated convergence theorem. Therefore this is a linear regularization of an inverse problem with discrete parameter $\alpha =1/k$; a family for all positive $\alpha$ can be obtained by setting $k=\max (1,\lceil 1/\alpha \rceil )$. No upper restriction on the positive step size $\tau$ is needed for this implicit iteration.