 Fixed-step gradient descent on a positive-definite quadratic

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.