Gradient descent ($x_{k+1}=x_k-\eta \nabla f(x_k)$)

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 this nonsymmetric matrix, consider the formal residual update $r^{+}=r-(r^{T}r)/(r^{T}Ar)Ar$, with nonzero $r=(x,y{)}^T$. Put $D=2x^2-2xy-2y^2$ and $B=5x^2+4xy+3y^2$. Algebra gives $r^{+}=(B/D)(-y,x{)}^T$ when $D\ne 0$. But $B+D=7(x+y/7{)}^2+6y^2/7>0$ and $B-D=3(x+y{)}^2+2y^2>0$. Hence $B>|D|$ and $\Vert r^{+}\Vert >\Vert r\Vert$ for every defined nonzero step. At $D=0$, the quotient is undefined. Thus the iteration cannot converge to zero linear-system residual from any nonzero initial residual. This concrete divergence proof distinguishes failure of an algorithm from mere failure to meet a sufficient theorem's hypotheses.

Let $A$ be real symmetric, let $b$ be a unit eigenvector satisfying $Ab=\lambda b$, and use scalar step sizes ${\alpha }_n$. The gradient of the displayed cubic polynomial function isOn the eigenline, $\nabla h(tb)=3\lambda t^{2}b$, so a gradient descent update remains on that same line and obeys the scalar recurrence in the title. Induction proves invariance for every iterate starting on the line, including an iterate that reaches zero. This is a statement about the geometry of the updates, not a convergence theorem: when $\lambda \ne 0$, the restriction $h(tb)=\lambda t^3$ is unbounded below in one direction.

The number of optimization epochs needed to meet a stated accuracy criterion. Comparisons must specify the work counted by an optimization epoch, the accuracy measure, and whether a random method is controlled in expectation or with a stated probability. Counting coordinate partial derivatives is useful for comparing randomized block coordinate descent with gradient descent, but need not match elapsed computation time.

Target: gradient-descent.bigb, under Stochastic gradient descent.

A unit of work corresponding to one full pass through the components used to measure an iterative method. For coordinate descent in $n$ coordinates, count $n$ coordinate partial derivative evaluations as an optimization epoch: updates on blocks of size $m$ require $n/m$ updates per optimization epoch. For stochastic gradient descent on a finite sum of losses, a common different convention counts one evaluation of every loss component. The convention must be specified. Random sampling with replacement need not visit every component during one such unit of work.

Target: gradient-descent.bigb, under Gradient descent.

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.

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.

Gradient ascent seeks a maximum by stepping along the gradient of a differentiable objective. It is gradient descent applied to $-J$. Taylor expansion gives $J(x+\eta \nabla J)=J(x)+\eta \Vert \nabla J{\Vert }^2+O({\eta }^2)$, so sufficiently small positive steps improve the objective when the gradient is nonzero. Line search, projection onto admissible controls, and noise-aware gradient estimates are common practical modifications; a local stationary result need not be globally optimal.

Stochastic gradient descent updates parameters using an unbiased or approximate gradient computed from one observation or a mini-batch rather than the complete data set.

Suppose a fixed-step size stochastic gradient descent iteration satisfiesand $f$ has a global minimizer $x^{\ast }$. Taking expectations and forming a telescoping sum proves the displayed bound with ${\Delta }_0=f(X^0)-f(x^{\ast })$ and deterministic $X^0$. The Cauchy-Schwarz inequality then bounds the averaged, or the best, expected gradient Euclidean norm by $\sqrt{M+2L{\Delta }_0/k}$. This is a guarantee of stationarity in the indicated senses, rather than a last-iterate convergence assertion. The additive $M$ is a stochastic gradient noise floor.

Target: real-analysis.bigb, under Strongly convex function.

A residual accuracy level in a bound for stochastic gradient descent with a fixed step size and nonvanishing gradient noise. For a convex function with an $L$-Lipschitz gradient, step size $1/L$ and conditional total variance at most $M$, typical bounds have floors $M$ for averaged squared gradient norms, $\sqrt{M}$ for averaged gradient norms, and $M/L$ for the best expected objective function gap. Such floors are upper bounds depending on the analysis and assumptions, rather than claims that these exact values are attained or that every last iterate converges.

Target: gradient-descent.bigb, under Stochastic gradient descent.

Projected stochastic gradient descent takes a stochastic-gradient step and then projects the result onto a closed feasible set. For a convex set $C$ it has the form $x_{s+1}={\Pi }_C(x_s-{\eta }_s{G}_s)$.

A random vector $G_s$ is an unbiased stochastic gradient at $x_s$ when $\mathbb{E}[G_s\mid x_s]=\nabla f(x_s)$.

For an unbiased stochastic gradient $H$ at $X$ with finite conditional second moment, expand $H=\nabla f(X)+(H-\nabla f(X))$ in the squared Euclidean norm. The cross term has zero conditional expectation, which proves the displayed identity. It separates the squared true gradient from the total conditional variance of its random estimate.

Target: gradient-descent.bigb, under Stochastic gradient descent.

A differentiable function has a $\beta$-Lipschitz gradient on a set $D$ if its gradient satisfies Lipschitz continuity there:All norms here are the Euclidean norm. The constant limits how fast the gradient changes; it is not a bound on the magnitude of the gradient. For $f(x)=(x_1^2+9x_2^2)/2$, the gradient is the linear map $x\mapsto \mathrm{diag}(1,9)x$. Its operator norm is $9$, so $\beta =9$ works globally and is sharp by taking $x-y=(0,1{)}^T$. The gradient itself is unbounded on the whole Euclidean space.

If $f$ has a continuous Hessian matrix on an open convex set $D$ and $\Vert {\nabla }^{2}f(z){\Vert }_2\le \beta$ throughout $D$, integrate that linear map along the line segment from $x$ to $y$:The operator norm bound proves the displayed Lipschitz continuity. Convexity of the domain keeps the entire line segment inside it. Bounding the Hessian matrix only at the endpoints is insufficient.

For a continuously differentiable convex function on ${\mathbb{R}}^n$ with coordinate Lipschitz continuity constants $L_i$, its block coordinate gradient is Lipschitz continuous along each corresponding coordinate subspace, with constant at most $S_{\mathcal{B}}={\sum }_{i\in \mathcal{B}}{L}_i$.

To prove this without assuming a Hessian matrix, put ${\delta }_{\mathcal{B}}={\nabla }_{\mathcal{B}}f(x)-{\nabla }_{\mathcal{B}}f(y)$. Sum the coordinate derivative bound by Bregman divergence over the block, then repeat with $x,y$ interchanged and average:If $x-y$ is supported in the block, the dot product uses only ${\delta }_{\mathcal{B}}$. The Cauchy-Schwarz inequality and cancellation of its Euclidean norm give the result, including the zero case separately. Taking the full block supplies a global Lipschitz gradient constant ${\sum }_i{L}_i$.

Target: convex-optimization.bigb, under Coordinate descent.

Suppose $f$ is a differentiable convex function with coordinate Lipschitz continuity constant $L_i>0$. Put $\varphi (u)=D_f(u,y)=f(u)-f(y)-\nabla f(y{)}^T(u-y)$, the Bregman divergence from the supporting affine function at $y$. The subgradient inequality gives $\varphi \ge 0$, and its coordinate Lipschitz constant is still $L_i$. The coordinate descent lemma with step size $1/L_i$ yieldsSince ${\partial }_i\varphi (x)={\partial }_{i}f(x)-{\partial }_{i}f(y)$, rearrangement proves the bound. Continuous differentiability suffices; a Hessian matrix is unnecessary.

Target: gradient-descent.bigb, under Lipschitz gradient.

The displayed estimate, for all $x$ and real $t$, defines a coordinate Lipschitz constant $L_i$ for the partial derivative in coordinate $i$. It implies the coordinate descent lemmaby the fundamental theorem of calculus and integration of the Lipschitz continuity estimate. Subtracting an affine function leaves these constants unchanged.

The apparently weaker estimate along the singleton negative gradient direction is equivalent when every real step size is allowed: if the initial partial derivative is nonzero, any displacement can be written $-\alpha {\partial }_{i}f(x)e_i$; if it is zero but the final partial derivative is nonzero, reverse the endpoints; if both vanish the estimate is trivial.

Target: gradient-descent.bigb, under Lipschitz gradient.

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.

For $f(x)=x^{T}Ax/2-b^{T}x$ with $A$ positive definite and residual $r=b-Ax$, exact line search along $r$ usesThe objective error contracts by

For a real symmetric positive-definite matrix $A$ and nonzero linear-system residual $r=b-Ax$, minimize $f(x+\alpha r)$ for $f(x)=x^{T}Ax/2-b^{T}x$. Differentiating with respect to $\alpha$ gives $-r^{T}r+\alpha r^{T}Ar=0$, yielding the displayed positive step. Positive definiteness makes it the unique minimum along the line. Applying the same quotient to a nonsymmetric or indefinite matrix is a formal iteration, but this minimization proof and its convergence consequences no longer apply.

For a positive-definite matrix $A$, the conjugate gradient method chooses mutually $A$-conjugate search directions. Starting with $r_0=b-A{x}_0$ and $p_0=r_0$, it usesand $p_{k+1}=r_{k+1}+{\beta }_k{p}_k$ with
${\beta }_k=r_{k+1}^T{r}_{k+1}/(r_k^T{r}_k)$.

For a symmetric positive-definite matrix, choose an orthonormal eigenbasis and write the exact solution as $x={\sum }_i{\alpha }_i{v}_i$. Starting at zero, the conjugate gradient method chooses an admissible polynomial $p(0)=1$ of degree at most the iteration count that minimizes the displayed error. The weights depend on both the eigenvalues and the solution coefficients. For two eigenvalues $1,L$, the first polynomial is $1-\eta t$, with $\eta =({\alpha }^2+{\beta }^2{L}^2)/({\alpha }^2+{\beta }^2{L}^3)$. Comparable nonzero coefficients and large $L$ give $\eta \approx 1/L$, so the high-eigenvalue error is removed first. A sufficiently tiny high-mode coefficient changes this behavior; the spectrum alone does not determine the first step.

Nonzero vectors are conjugate directions with respect to a symmetric positive-definite matrix $A$ when they are pairwise orthogonal in the inner product $⟨u,v{⟩}_A=u^{T}Av$. They need not be orthogonal in the ordinary Euclidean inner product. They are linearly independent: multiplying a vanishing linear combination by $p_j^{T}A$ isolates its $j$th coefficient times $p_j^{T}A{p}_j>0$.

Let $p_1,\dots ,p_n$ be conjugate directions for a symmetric positive-definite matrix $A$. Starting from any $x_1$, minimize $x^{T}Ax/2-b^{T}x$ successively along those full lines, stopping early if the linear-system residual $r_j=b-A{x}_j$ vanishes. The quadratic minimization along a line uses ${\alpha }_j=p_j^T{r}_j/(p_j^{T}A{p}_j)$ and gives $r_{j+1}=r_j-{\alpha }_{j}A{p}_j$.

This makes $p_j^T{r}_{j+1}=0$. For $i<j$, conjugacy preserves $p_i^T{r}_{j+1}=p_i^T{r}_j$. By mathematical induction, $r_{j+1}$ is orthogonal to all preceding search vectors. The $n$ conjugate directions are linearly independent and hence form a basis, so $r_{n+1}=0$. Thus the method reaches the unique solution of the linear system in at most $n$ steps in exact arithmetic. The conjugate gradient method generates such directions without storing a complete prescribed basis in advance.

For a symmetric positive-definite matrix $H$, the Conjugate gradient method minimizes the error in the induced weighted norm over its affine Krylov subspace. Writing the error as $p(H)e_0$ givesFor ${\lambda }_{\min }<{\lambda }_{\max }$, choose the scaled Chebyshev polynomial $p(\lambda )=T_k(({\lambda }_{\max }+{\lambda }_{\min }-2\lambda )/({\lambda }_{\max }-{\lambda }_{\min }))/T_k(({\lambda }_{\max }+{\lambda }_{\min })/({\lambda }_{\max }-{\lambda }_{\min }))$. On the spectral interval its numerator has absolute value at most one. With $\rho =(\sqrt{\kappa }+1)/(\sqrt{\kappa }-1)$, the denominator equals $({\rho }^k+{\rho }^{-k})/2\ge {\rho }^k/2$. This proves the displayed bound. If the two endpoints coincide, $H$ is a positive scalar multiple of the identity and one iteration solves the system exactly.

The residual of an approximate solution $x$ of $Ax=b$ is $r=b-Ax$. It is the unbalanced right-hand side, while the solution error is $x_{\ast }-x=A^{-1}r$. The conjugate gradient method makes residuals orthogonal to successive Krylov subspaces.

The norm of a linear-system residual, used to measure how closely an approximate solution satisfies its linear system. It differs from the solution-error norm $\Vert x_{\ast }-x\Vert$. Their relationship depends on the matrix inverse and the condition number, so a small residual alone is not a scale-free relative-error guarantee.

At iteration $m$ of the conjugate gradient method,and $r_m$ itself lies in ${\mathcal{K}}_{m+1}(A,r_0)$. These Galerkin conditions imply finite termination once the Krylov subspace becomes invariant under $A$.

A symmetric preconditioner transforms $Ax=b$ intoThe aim is to make the transformed positive-definite matrix have clustered eigenvalues while keeping application of $P$ inexpensive.

For a positive-definite matrix $A$, choosing $P=A^{-1/2}$ gives $PA{P}^T=I$, so conjugate gradients terminates in one step. Constructing or applying the exact inverse square root is generally as expensive as solving the original system.

The order-$k$ Krylov subspace generated by $A$ and $b$ is

With zero initial guess, the generalized minimal residual method minimizes the Euclidean norm of the linear-system residual over each Krylov subspace. The Arnoldi decomposition reduces this to ${\min }_y\Vert {\tilde{H}}_{k}y-\Vert b{\Vert }_2{e}_1{\Vert }_2$, followed by $x_k=Q_{k}y$. Givens rotations solve the small problem in $O(k^2)$ operations once the decomposition is available. For an invertible matrix $A$, the same iterate minimizes the error in the weighted norm induced by $A^{T}A$, because $\Vert Ax-b{\Vert }_2=\Vert x-x_{\ast }{\Vert }_{A^{T}A}$.

One step of restarted GMRES searches along the current residual. In the displayed nonsingular system, the first residual minimization is ${\min }_{\alpha }[(1-\alpha {)}^2+(1+\alpha {)}^2]$, whose minimizer is zero. Restarting then repeats the same problem forever and never moves. Unrestarted GMRES instead solves exactly at step two, since $b,Ab$ span the entire space. Thus a smaller search-space cost can come at the price of stagnation; nonsingularity alone does not guarantee progress for one-step restarting.

Starting with $q_1=b/\Vert b{\Vert }_2$, the Arnoldi iteration constructs an orthonormal basis of successive Krylov subspaces. At step $j$, orthogonalize $A{q}_j$ against $q_1,\dots ,q_j$, and normalize the remainder as $q_{j+1}$ if it is nonzero. The coefficients form an upper Hessenberg matrix ${\tilde{H}}_k$ and satisfy $A{Q}_k=Q_{k+1}{\tilde{H}}_k$. A zero remainder means the current Krylov subspace is invariant under $A$.

For a real symmetric matrix $A$, the leading block $Q_k^{T}A{Q}_k$ of the Arnoldi decomposition is both symmetric and an upper Hessenberg matrix, hence a tridiagonal matrix. The resulting three-term recurrence is the Lanczos algorithm. If $A$ is a symmetric positive-definite matrix, its compression is too, since $y^T{Q}_k^{T}A{Q}_{k}y=(Q_{k}y{)}^{T}A(Q_{k}y)>0$ for nonzero $y$.

The factorization produced by the Arnoldi iteration, with orthonormal $Q_{k+1}$ and an upper Hessenberg matrix ${\tilde{H}}_k$. Multiplying by $Q_k^T$ identifies its leading square block as $H_k=Q_k^{T}A{Q}_k$.

For a diagonalizable finite-dimensional operator, write $v={\sum }_j{u}_j$ with nonzero $u_j$ in distinct eigenspaces of eigenvalues ${\lambda }_j$. Then $A^{r}v={\sum }_j{\lambda }_j^r{u}_j$. The Vandermonde matrix of the first $k$ powers is invertible for $k$ distinct eigenvalues, so these powers span exactly the $k$ independent components $u_j$. Thus the stabilized Krylov subspace dimension is $k$. It counts distinct spectral components, not the number of nonzero coefficients in an arbitrary eigenbasis: $A=I$, $v=e_1+e_2$ has Krylov dimension one. Equivalently it is the minimum number of eigenvectors needed when those vectors may be chosen freely.

In exact arithmetic, conjugate gradients reaches the exact solution in at most the number of distinct eigenvalues of $A$, and therefore in at most $n$ steps for an $n$-dimensional system.

The heavy-ball iteration adds momentum to gradient descent:

For $F(x)=x^{T}Ax/2-b^{T}x$ and $r_k=b-A{x}_k$,Thus $r_k$ is a polynomial in $A$ applied to the initial residual and lies in the corresponding Krylov subspace.

For $e_k=x^{\ast }-x_k$,If $A$ is diagonal with entries ${\lambda }_i$, a coordinate permutation turns this matrix into blocks

For $A=\mathrm{diag}(1,\gamma )$, $\alpha =1/\gamma$, and $\beta =(1-{\gamma }^{-1/2}{)}^2$, every error-propagation block has spectral radius at most $1-{\gamma }^{-1/2}$, and equality occurs.