Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Derivation of the conjugate gradient method
open-in-new
<h2 id="conjugate-direction">Conjugate direction</h2> <p>The conjugate gradient method can be seen as a special case of the conjugate direction method applied to minimization of the quadratic function </p> f ( x ) = x T A x − 2 b T x . {\displaystyle f({\boldsymbol {x}})={\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}{\text{.}}} <p>which allows us to apply geometric intuition. </p> <h3>Line search</h3> <p>Geometrically, the quadratic function can be equivalently presented by writing down its value at every point in space. The points of equal value make up its contour surfaces, which are concentric <a href="/facts/Ellipsoid/pe9vm0Sh">ellipsoids</a> with the equation x T A x − 2 b T x = C {\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}=C} for varying C {\displaystyle C} . As C {\displaystyle C} decreases, the ellipsoids become smaller and smaller, until at its minimal value, the ellipsoid shrinks to their shared center. </p><p>Minimizing the quadratic function is then a problem of moving around the plane, searching for that shared center of all those ellipsoids. The center can be found by computing A − 1 {\displaystyle {\boldsymbol {A}}^{-1}} explicitly, but this is precisely what we are trying to avoid. </p><p>The simplest method is greedy <a href="/facts/Line_search/GQWhNEsR">line search</a>, where we start at some point x 0 {\displaystyle {\boldsymbol {x}}_{0}} , pick a direction p 0 {\displaystyle {\boldsymbol {p}}_{0}} somehow, then minimize f ( x 0 + p 0 α 0 ) {\displaystyle f({\boldsymbol {x}}_{0}+{\boldsymbol {p}}_{0}\alpha _{0})} . This has a simple closed-form solution that does not involve matrix inversion: α 0 = p 0 T ( b − A x 0 ) p 0 T A p 0 {\displaystyle \alpha _{0}={\frac {{\boldsymbol {p}}_{0}^{\mathrm {T} }({\boldsymbol {b}}-{\boldsymbol {Ax}}_{0})}{{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {p}}_{0}}}} Geometrically, we start at some point x 0 {\displaystyle {\boldsymbol {x}}_{0}} on some ellipsoid, then choose a direction and travel along that direction, until we hit the point where the ellipsoid is minimized in that direction. This is not necessarily the minimum, but it is progress towards it. Visually, it is moving along a line, and stopping as soon as we reach a point tangent to the contour ellipsoid. </p><p>We can now repeat this procedure, starting at our new point x 1 = x 0 + α 0 p 0 {\displaystyle {\boldsymbol {x}}_{1}={\boldsymbol {x}}_{0}+\alpha _{0}{\boldsymbol {p}}_{0}} , pick a new direction p 1 {\displaystyle {\boldsymbol {p}}_{1}} , compute α 1 {\displaystyle \alpha _{1}} , etc. </p><p>We can summarize this as the following algorithm: </p><p>Start by picking an initial guess x 0 {\displaystyle {\boldsymbol {x}}_{0}} , and compute the initial residual r 0 = b − A x 0 {\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{0}} , then iterate: </p> α i = p i T r i p i T A p i , x i + 1 = x i + α i p i , r i + 1 = r i − α i A p i {\displaystyle {\begin{aligned}\alpha _{i}&={\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\text{,}}\\{\boldsymbol {x}}_{i+1}&={\boldsymbol {x}}_{i}+\alpha _{i}{\boldsymbol {p}}_{i}{\text{,}}\\{\boldsymbol {r}}_{i+1}&={\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {Ap}}_{i}\end{aligned}}} <p>where p 0 , p 1 , p 2 , … {\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } are to be picked. Notice in particular how the residual is calculated iteratively step-by-step, instead of anew every time: r i + 1 = b − A x i + 1 = b − A ( x i + α i p i ) = r i − α i A p i {\displaystyle {\boldsymbol {r}}_{i+1}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{i+1}={\boldsymbol {b}}-{\boldsymbol {A}}({\boldsymbol {x}}_{i}+\alpha _{i}{\boldsymbol {p}}_{i})={\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {A}}{\boldsymbol {p}}_{i}} It is possibly true that α i = 0 {\displaystyle \alpha _{i}=0} prematurely, which would bring numerical problems. However, for particular choices of p 0 , p 1 , p 2 , … {\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } , this will not occur before convergence, as we will prove below. </p> <h3>Conjugate directions</h3> <p>If the directions p 0 , p 1 , p 2 , … {\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } are not picked well, then progress will be slow. In particular, the gradient descent method would be slow. This can be seen in the diagram, where the green line is the result of always picking the local gradient direction. It zig-zags towards the minimum, but repeatedly overshoots. In contrast, if we pick the directions to be a set of mutually conjugate directions, then there will be no overshoot, and we would obtain the global minimum after n {\displaystyle n} steps, where n {\displaystyle n} is the number of dimensions. </p> <p>The concept of conjugate directions came from classical geometry of ellipse. For an ellipse, two semi-axes center are mutually conjugate with respect to the ellipse iff the lines are parallel to the tangent bounding parallelogram, as pictured. The concept generalizes to <i>n</i>-dimensional ellipsoids, where <i>n</i> semi-axes t 0 p 0 , … , t n − 1 p n − 1 {\displaystyle t_{0}{\boldsymbol {p}}_{0},\dots ,t_{n-1}{\boldsymbol {p}}_{n-1}} are mutually conjugate with respect to the ellipsoid iff each axis is parallel to the tangent bounding <a href="/facts/Parallelepiped/Qn7cDgSr">parallelepiped</a>. In other words, for any i {\displaystyle i} , the tangent plane to the ellipsoid at c + t i p i {\displaystyle {\boldsymbol {c}}+t_{i}{\boldsymbol {p}}_{i}} is a hyperplane spanned by the vectors { p j : j ≠ i } {\displaystyle \{{\boldsymbol {p}}_{j}:j\neq i\}} , where c {\displaystyle {\boldsymbol {c}}} is the center of the ellipsoid. </p><p>Note that we need to scale each directional vector p i {\displaystyle {\boldsymbol {p}}_{i}} by a scalar t i {\displaystyle t_{i}} , so that c + t i p i {\displaystyle {\boldsymbol {c}}+t_{i}{\boldsymbol {p}}_{i}} falls exactly on the ellipsoid. </p><p>Given an ellipsoid with equation x T A x − 2 b T x = C {\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}=C} for some constant C {\displaystyle C} , we can translate it so that its center is at origin. This changes the equation to x T A x = C ′ {\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}=C'} for some other constant C ′ {\displaystyle C'} . The condition of tangency is then: ( t i p i + p j d t j ) T A ( t i p i + p j d t j ) = C ′ + O ( d t j 2 ) , ∀ i ≠ j {\displaystyle (t_{i}{\boldsymbol {p}}_{i}+{\boldsymbol {p}}_{j}dt_{j})^{\mathrm {T} }{\boldsymbol {A}}(t_{i}{\boldsymbol {p}}_{i}+{\boldsymbol {p}}_{j}dt_{j})=C'+O(dt_{j}^{2}),\quad \forall i\neq j} that is, p i T A p j = 0 {\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{j}=0} for any i ≠ j {\displaystyle i\neq j} . </p><p>The conjugate direction method is imprecise in the sense that no formulae are given for selection of the directions p 0 , p 1 , p 2 , … {\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } . Specific choices lead to various methods including the conjugate gradient method and <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>. </p> <h3>Gram–Schmidt process</h3> <p>We can tabulate the equations that we need to set to zero: </p> <table><tbody><tr><th></th><td>0</td><td>1</td><td>2</td><td>3</td><td> ⋯ {\displaystyle \cdots } </td></tr><tr><td>0</td><td></td><td> p 0 T A p 1 {\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{1}} </td><td> p 0 T A p 2 {\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{2}} </td><td> p 0 T A p 3 {\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} </td><td> ⋯ {\displaystyle \cdots } </td></tr><tr><td>1</td><td></td><td></td><td> p 1 T A p 2 {\displaystyle {\boldsymbol {p}}_{1}^{\mathrm {T} }{\boldsymbol {Ap}}_{2}} </td><td> p 1 T A p 3 {\displaystyle {\boldsymbol {p}}_{1}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} </td><td> ⋯ {\displaystyle \cdots } </td></tr><tr><td>2</td><td></td><td></td><td></td><td> p 2 T A p 3 {\displaystyle {\boldsymbol {p}}_{2}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} </td><td> ⋯ {\displaystyle \cdots } </td></tr><tr><td> ⋮ {\displaystyle \vdots } </td><td></td><td></td><td></td><td></td><td> ⋱ {\displaystyle \ddots } </td></tr></tbody></table> <p>This resembles the problem of orthogonalization, which requires p i T p j = 0 {\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {p}}_{j}=0} for any i ≠ j {\displaystyle i\neq j} , and p i T p j = 1 {\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {p}}_{j}=1} for any i = j {\displaystyle i=j} . Thus the problem of finding conjugate axes is less constrained than the problem of orthogonalization, so the <a href="/facts/Gram%25E2%2580%2593Schmidt_process/vRNpld3t">Gram–Schmidt process</a> works, with additional degrees of freedom that we can later use to pick the ones that would simplify the computation: </p> <ul><li>Arbitrarily set p 0 {\displaystyle {\boldsymbol {p}}_{0}} .</li> <li>Arbitrarily set p 10 {\displaystyle {\boldsymbol {p}}_{10}} , then modify it to p 1 = p 10 − p 0 T A p 10 p 0 T A p 0 p 0 {\displaystyle {\boldsymbol {p}}_{1}={\boldsymbol {p}}_{10}-{\frac {{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{10}}{{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{0}}}{\boldsymbol {p}}_{0}} .</li> <li>Arbitrarily set p 20 {\displaystyle {\boldsymbol {p}}_{20}} , then modify it to p 2 = p 20 − ∑ i = 0 1 p i T A p 20 p i T A p i p i {\displaystyle {\boldsymbol {p}}_{2}={\boldsymbol {p}}_{20}-\sum _{i=0}^{1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{20}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} .</li> <li>...</li> <li>Arbitrarily set p n − 1 , 0 {\displaystyle {\boldsymbol {p}}_{n-1,0}} , then modify it to p n − 1 = p n − 1 , 0 − ∑ i = 0 n − 2 p i T A p n − 1 , 0 p i T A p i p i {\displaystyle {\boldsymbol {p}}_{n-1}={\boldsymbol {p}}_{n-1,0}-\sum _{i=0}^{n-2}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{n-1,0}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} .</li></ul> <p>The most natural choice of p k , 0 {\displaystyle {\boldsymbol {p}}_{k,0}} is the gradient. That is, p k , 0 = ∇ f ( x k ) {\displaystyle {\boldsymbol {p}}_{k,0}=\nabla f({\boldsymbol {x}}_{k})} . Since conjugate directions can be scaled by a nonzero value, we scale it by − 1 / 2 {\displaystyle -1/2} for notational cleanness, obtaining p k , 0 = r k = b − A x k {\displaystyle {\boldsymbol {p}}_{k,0}=\mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}} Thus, we have p k = r k − ∑ i = 0 k − 1 p i T A r k p i T A p i p i {\displaystyle {\boldsymbol {p}}_{k}={\boldsymbol {r}}_{k}-\sum _{i=0}^{k-1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} . Plugging it in, we have the conjugate gradient algorithm: r 0 := b − A x 0 p 0 := r 0 k := 0 do while k < n α k := p k T r k p k T A p k x k + 1 := x k + α k p k if | α k | is sufficiently small, then exit loop r k + 1 := r k − α k A p k p k + 1 := r k + 1 − ∑ i = 0 k p i T A r k + 1 p i T A p i p i k := k + 1 return x k + 1 as the result {\displaystyle {\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{do while }}k<n\\&\qquad \alpha _{k}:={\frac {\mathbf {p} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad {\text{if }}|\alpha _{k}|{\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \mathbf {p} _{k+1}:={\boldsymbol {r}}_{k+1}-\sum _{i=0}^{k}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k+1}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}\\&\qquad k:=k+1\\&{\text{return }}\mathbf {x} _{k+1}{\text{ as the result}}\end{aligned}}} Proposition. If at some point, α k = 0 {\displaystyle \alpha _{k}=0} , then the algorithm has converged, that is, ∇ f ( x k + 1 ) = 0 {\displaystyle \nabla f(\mathrm {x} _{k+1})=0} . </p><p>Proof. By construction, it would mean that x k + 1 = x k {\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}} , that is, taking a conjugate gradient step gets us exactly back to where we were. This is only possible if the local gradient is already zero. </p> <h3>Simplification</h3> <p>This algorithm can be significantly simplified by some lemmas, resulting in the conjugate gradient algorithm. </p><p>Lemma 1. p i T r j = 0 , ∀ i < j {\displaystyle \mathbf {p} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} and r i T r j = 0 , ∀ i < j {\displaystyle \mathbf {r} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} . </p><p>Proof. By the geometric construction, the tangent plane to the ellipsoid at x j {\displaystyle \mathbf {x} _{j}} contains each of the previous conjugate direction vectors p 0 , p 1 , … , p j − 1 {\displaystyle \mathbf {p} _{0},\mathbf {p} _{1},\dots ,\mathbf {p} _{j-1}} . Further, r j {\displaystyle \mathbf {r} _{j}} is perpendicular to the tangent, thus p i T r j = 0 , ∀ i < j {\displaystyle \mathbf {p} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} . The second equation is true since by construction, r 0 , r 1 , … , r j − 1 {\displaystyle \mathbf {r} _{0},\mathbf {r} _{1},\dots ,\mathbf {r} _{j-1}} is a linear transform of p 0 , p 1 , … , p j − 1 {\displaystyle \mathbf {p} _{0},\mathbf {p} _{1},\dots ,\mathbf {p} _{j-1}} . </p><p>Lemma 2. p k T r k = r k T r k {\displaystyle \mathbf {p} _{k}^{T}\mathbf {r} _{k}=\mathbf {r} _{k}^{T}\mathbf {r} _{k}} . </p><p>Proof. By construction, p k := r k − ∑ i = 0 k − 1 p i T A r k − 1 p i T A p i p i {\displaystyle \mathbf {p} _{k}:={\boldsymbol {r}}_{k}-\sum _{i=0}^{k-1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k-1}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} , now apply lemma 1. </p><p>Lemma 3. p i T A r k + 1 = { 0 , i < k − r k + 1 T r k + 1 / α k , i = k {\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k+1}={\begin{cases}0,\;i<k\\-{\boldsymbol {r}}_{k+1}^{T}{\boldsymbol {r}}_{k+1}/\alpha _{k},\;i=k\end{cases}}} . </p><p>Proof. By construction, we have r i + 1 = r i − α i A p i {\displaystyle \mathbf {r} _{i+1}=\mathbf {r} _{i}-\alpha _{i}\mathbf {Ap} _{i}} , thus r k + 1 T A p i = r k + 1 T r i − r i + 1 α i {\displaystyle {\boldsymbol {r}}_{k+1}^{T}{\boldsymbol {A}}{\boldsymbol {p}}_{i}={\boldsymbol {r}}_{k+1}^{T}{\frac {{\boldsymbol {r}}_{i}-{\boldsymbol {r}}_{i+1}}{\alpha _{i}}}} Now apply lemma 1. </p><p> Plugging lemmas 1-3 in, we have α k = r k ⊤ r k p k ⊤ A p k {\displaystyle \alpha _{k}={\frac {\mathbf {r} _{k}^{\top }\mathbf {r} _{k}}{\mathbf {p} _{k}^{\top }\mathbf {A} \mathbf {p} _{k}}}} and p k + 1 := r k + 1 + r k + 1 ⊤ r k + 1 r k ⊤ r k p k {\displaystyle \mathbf {p} _{k+1}:={\boldsymbol {r}}_{k+1}+{\frac {\mathbf {r} _{k+1}^{\top }\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\top }\mathbf {r} _{k}}}\mathbf {p} _{k}} , which is the proper conjugate gradient algorithm. </p> <h2 id="arnoldilanczos-iteration">Arnoldi/Lanczos iteration</h2> <p class="note">Further information: <a href="/facts/Arnoldi_iteration/7bnLdCgy">Arnoldi iteration</a> and <a href="/facts/Lanczos_iteration/t3n5RYKr">Lanczos iteration</a></p> <p>The conjugate gradient method can also be seen as a variant of the Arnoldi/Lanczos iteration applied to solving linear systems. </p> <h3>The general Arnoldi method</h3> <p>In the Arnoldi iteration, one starts with a vector r 0 {\displaystyle {\boldsymbol {r}}_{0}} and gradually builds an <a href="/facts/Orthonormal/JfgL1nAh">orthonormal</a> basis { v 1 , v 2 , v 3 , … } {\displaystyle \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2},{\boldsymbol {v}}_{3},\ldots \}} of the <a href="/facts/Krylov_subspace/wtr5EXn6">Krylov subspace</a> </p> K ( A , r 0 ) = s p a n { r 0 , A r 0 , A 2 r 0 , … } {\displaystyle {\mathcal {K}}({\boldsymbol {A}},{\boldsymbol {r}}_{0})=\mathrm {span} \{{\boldsymbol {r}}_{0},{\boldsymbol {Ar}}_{0},{\boldsymbol {A}}^{2}{\boldsymbol {r}}_{0},\ldots \}} <p>by defining v i = w i / ‖ w i ‖ 2 {\displaystyle {\boldsymbol {v}}_{i}={\boldsymbol {w}}_{i}/\lVert {\boldsymbol {w}}_{i}\rVert _{2}} where </p> v i = { r 0 if i = 1 , A v i − 1 − ∑ j = 1 i − 1 ( v j T A v i − 1 ) v j if i > 1 . {\displaystyle {\boldsymbol {v}}_{i}={\begin{cases}{\boldsymbol {r}}_{0}&{\text{if }}i=1{\text{,}}\\{\boldsymbol {Av}}_{i-1}-\sum _{j=1}^{i-1}({\boldsymbol {v}}_{j}^{\mathrm {T} }{\boldsymbol {Av}}_{i-1}){\boldsymbol {v}}_{j}&{\text{if }}i>1{\text{.}}\end{cases}}} <p>In other words, for i > 1 {\displaystyle i>1} , v i {\displaystyle {\boldsymbol {v}}_{i}} is found by <a href="/facts/Gram-Schmidt_orthogonalization/vRNpld3t">Gram-Schmidt orthogonalizing</a> A v i − 1 {\displaystyle {\boldsymbol {Av}}_{i-1}} against { v 1 , v 2 , … , v i − 1 } {\displaystyle \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2},\ldots ,{\boldsymbol {v}}_{i-1}\}} followed by normalization. </p><p>Put in matrix form, the iteration is captured by the equation </p> A V i = V i + 1 H ~ i {\displaystyle {\boldsymbol {AV}}_{i}={\boldsymbol {V}}_{i+1}{\boldsymbol {\tilde {H}}}_{i}} <p>where </p> V i = [ v 1 v 2 ⋯ v i ] , H ~ i = [ h 11 h 12 h 13 ⋯ h 1 , i h 21 h 22 h 23 ⋯ h 2 , i h 32 h 33 ⋯ h 3 , i ⋱ ⋱ ⋮ h i , i − 1 h i , i h i + 1 , i ] = [ H i h i + 1 , i e i T ] {\displaystyle {\begin{aligned}{\boldsymbol {V}}_{i}&={\begin{bmatrix}{\boldsymbol {v}}_{1}&{\boldsymbol {v}}_{2}&\cdots &{\boldsymbol {v}}_{i}\end{bmatrix}}{\text{,}}\\{\boldsymbol {\tilde {H}}}_{i}&={\begin{bmatrix}h_{11}&h_{12}&h_{13}&\cdots &h_{1,i}\\h_{21}&h_{22}&h_{23}&\cdots &h_{2,i}\\&h_{32}&h_{33}&\cdots &h_{3,i}\\&&\ddots &\ddots &\vdots \\&&&h_{i,i-1}&h_{i,i}\\&&&&h_{i+1,i}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {H}}_{i}\\h_{i+1,i}{\boldsymbol {e}}_{i}^{\mathrm {T} }\end{bmatrix}}\end{aligned}}} <p>with </p> h j i = { v j T A v i if j ≤ i , ‖ w i + 1 ‖ 2 if j = i + 1 , 0 if j > i + 1 . {\displaystyle h_{ji}={\begin{cases}{\boldsymbol {v}}_{j}^{\mathrm {T} }{\boldsymbol {Av}}_{i}&{\text{if }}j\leq i{\text{,}}\\\lVert {\boldsymbol {w}}_{i+1}\rVert _{2}&{\text{if }}j=i+1{\text{,}}\\0&{\text{if }}j>i+1{\text{.}}\end{cases}}} <p>When applying the Arnoldi iteration to solving linear systems, one starts with r 0 = b − A x 0 {\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{0}} , the residual corresponding to an initial guess x 0 {\displaystyle {\boldsymbol {x}}_{0}} . After each step of iteration, one computes y i = H i − 1 ( ‖ r 0 ‖ 2 e 1 ) {\displaystyle {\boldsymbol {y}}_{i}={\boldsymbol {H}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})} and the new iterate x i = x 0 + V i y i {\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i}} . </p> <h3>The direct Lanczos method</h3> <p>For the rest of discussion, we assume that A {\displaystyle {\boldsymbol {A}}} is symmetric positive-definite. With symmetry of A {\displaystyle {\boldsymbol {A}}} , the <a href="/facts/Upper_Hessenberg_matrix/vy7p7s3Y">upper Hessenberg matrix</a> H i = V i T A V i {\displaystyle {\boldsymbol {H}}_{i}={\boldsymbol {V}}_{i}^{\mathrm {T} }{\boldsymbol {AV}}_{i}} becomes symmetric and thus tridiagonal. It then can be more clearly denoted by </p> H i = [ a 1 b 2 b 2 a 2 b 3 ⋱ ⋱ ⋱ b i − 1 a i − 1 b i b i a i ] . {\displaystyle {\boldsymbol {H}}_{i}={\begin{bmatrix}a_{1}&b_{2}\\b_{2}&a_{2}&b_{3}\\&\ddots &\ddots &\ddots \\&&b_{i-1}&a_{i-1}&b_{i}\\&&&b_{i}&a_{i}\end{bmatrix}}{\text{.}}} <p>This enables a short three-term recurrence for v i {\displaystyle {\boldsymbol {v}}_{i}} in the iteration, and the Arnoldi iteration is reduced to the Lanczos iteration. </p><p>Since A {\displaystyle {\boldsymbol {A}}} is symmetric positive-definite, so is H i {\displaystyle {\boldsymbol {H}}_{i}} . Hence, H i {\displaystyle {\boldsymbol {H}}_{i}} can be <a href="/facts/LU_factorization/M13Ew8RD">LU factorized</a> without <a href="/facts/Partial_pivoting/Lo9drS0e">partial pivoting</a> into </p> H i = L i U i = [ 1 c 2 1 ⋱ ⋱ c i − 1 1 c i 1 ] [ d 1 b 2 d 2 b 3 ⋱ ⋱ d i − 1 b i d i ] {\displaystyle {\boldsymbol {H}}_{i}={\boldsymbol {L}}_{i}{\boldsymbol {U}}_{i}={\begin{bmatrix}1\\c_{2}&1\\&\ddots &\ddots \\&&c_{i-1}&1\\&&&c_{i}&1\end{bmatrix}}{\begin{bmatrix}d_{1}&b_{2}\\&d_{2}&b_{3}\\&&\ddots &\ddots \\&&&d_{i-1}&b_{i}\\&&&&d_{i}\end{bmatrix}}} <p>with convenient recurrences for c i {\displaystyle c_{i}} and d i {\displaystyle d_{i}} : </p> c i = b i / d i − 1 , d i = { a 1 if i = 1 , a i − c i b i if i > 1 . {\displaystyle {\begin{aligned}c_{i}&=b_{i}/d_{i-1}{\text{,}}\\d_{i}&={\begin{cases}a_{1}&{\text{if }}i=1{\text{,}}\\a_{i}-c_{i}b_{i}&{\text{if }}i>1{\text{.}}\end{cases}}\end{aligned}}} <p>Rewrite x i = x 0 + V i y i {\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i}} as </p> x i = x 0 + V i H i − 1 ( ‖ r 0 ‖ 2 e 1 ) = x 0 + V i U i − 1 L i − 1 ( ‖ r 0 ‖ 2 e 1 ) = x 0 + P i z i {\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {H}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})\\&={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {U}}_{i}^{-1}{\boldsymbol {L}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})\\&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i}{\boldsymbol {z}}_{i}\end{aligned}}} <p>with </p> P i = V i U i − 1 , z i = L i − 1 ( ‖ r 0 ‖ 2 e 1 ) . {\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}&={\boldsymbol {V}}_{i}{\boldsymbol {U}}_{i}^{-1}{\text{,}}\\{\boldsymbol {z}}_{i}&={\boldsymbol {L}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1}){\text{.}}\end{aligned}}} <p>It is now important to observe that </p> P i = [ P i − 1 p i ] , z i = [ z i − 1 ζ i ] . {\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}&={\begin{bmatrix}{\boldsymbol {P}}_{i-1}&{\boldsymbol {p}}_{i}\end{bmatrix}}{\text{,}}\\{\boldsymbol {z}}_{i}&={\begin{bmatrix}{\boldsymbol {z}}_{i-1}\\\zeta _{i}\end{bmatrix}}{\text{.}}\end{aligned}}} <p>In fact, there are short recurrences for p i {\displaystyle {\boldsymbol {p}}_{i}} and ζ i {\displaystyle \zeta _{i}} as well: </p> p i = 1 d i ( v i − b i p i − 1 ) , ζ i = − c i ζ i − 1 . {\displaystyle {\begin{aligned}{\boldsymbol {p}}_{i}&={\frac {1}{d_{i}}}({\boldsymbol {v}}_{i}-b_{i}{\boldsymbol {p}}_{i-1}){\text{,}}\\\zeta _{i}&=-c_{i}\zeta _{i-1}{\text{.}}\end{aligned}}} <p>With this formulation, we arrive at a simple recurrence for x i {\displaystyle {\boldsymbol {x}}_{i}} : </p> x i = x 0 + P i z i = x 0 + P i − 1 z i − 1 + ζ i p i = x i − 1 + ζ i p i . {\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i}{\boldsymbol {z}}_{i}\\&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i-1}{\boldsymbol {z}}_{i-1}+\zeta _{i}{\boldsymbol {p}}_{i}\\&={\boldsymbol {x}}_{i-1}+\zeta _{i}{\boldsymbol {p}}_{i}{\text{.}}\end{aligned}}} <p>The relations above straightforwardly lead to the direct Lanczos method, which turns out to be slightly more complex. </p> <h3>The conjugate gradient method from imposing orthogonality and conjugacy</h3> <p>If we allow p i {\displaystyle {\boldsymbol {p}}_{i}} to scale and compensate for the scaling in the constant factor, we potentially can have simpler recurrences of the form: </p> x i = x i − 1 + α i − 1 p i − 1 , r i = r i − 1 − α i − 1 A p i − 1 , p i = r i + β i − 1 p i − 1 . {\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{i-1}+\alpha _{i-1}{\boldsymbol {p}}_{i-1}{\text{,}}\\{\boldsymbol {r}}_{i}&={\boldsymbol {r}}_{i-1}-\alpha _{i-1}{\boldsymbol {Ap}}_{i-1}{\text{,}}\\{\boldsymbol {p}}_{i}&={\boldsymbol {r}}_{i}+\beta _{i-1}{\boldsymbol {p}}_{i-1}{\text{.}}\end{aligned}}} <p>As premises for the simplification, we now derive the orthogonality of r i {\displaystyle {\boldsymbol {r}}_{i}} and conjugacy of p i {\displaystyle {\boldsymbol {p}}_{i}} , i.e., for i ≠ j {\displaystyle i\neq j} , </p> r i T r j = 0 , p i T A p j = 0 . {\displaystyle {\begin{aligned}{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{j}&=0{\text{,}}\\{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{j}&=0{\text{.}}\end{aligned}}} <p>The residuals are mutually orthogonal because r i {\displaystyle {\boldsymbol {r}}_{i}} is essentially a multiple of v i + 1 {\displaystyle {\boldsymbol {v}}_{i+1}} since for i = 0 {\displaystyle i=0} , r 0 = ‖ r 0 ‖ 2 v 1 {\displaystyle {\boldsymbol {r}}_{0}=\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {v}}_{1}} , for i > 0 {\displaystyle i>0} , </p> r i = b − A x i = b − A ( x 0 + V i y i ) = r 0 − A V i y i = r 0 − V i + 1 H ~ i y i = r 0 − V i H i y i − h i + 1 , i ( e i T y i ) v i + 1 = ‖ r 0 ‖ 2 v 1 − V i ( ‖ r 0 ‖ 2 e 1 ) − h i + 1 , i ( e i T y i ) v i + 1 = − h i + 1 , i ( e i T y i ) v i + 1 . {\displaystyle {\begin{aligned}{\boldsymbol {r}}_{i}&={\boldsymbol {b}}-{\boldsymbol {Ax}}_{i}\\&={\boldsymbol {b}}-{\boldsymbol {A}}({\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i})\\&={\boldsymbol {r}}_{0}-{\boldsymbol {AV}}_{i}{\boldsymbol {y}}_{i}\\&={\boldsymbol {r}}_{0}-{\boldsymbol {V}}_{i+1}{\boldsymbol {\tilde {H}}}_{i}{\boldsymbol {y}}_{i}\\&={\boldsymbol {r}}_{0}-{\boldsymbol {V}}_{i}{\boldsymbol {H}}_{i}{\boldsymbol {y}}_{i}-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}\\&=\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {v}}_{1}-{\boldsymbol {V}}_{i}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}\\&=-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}{\text{.}}\end{aligned}}} <p>To see the conjugacy of p i {\displaystyle {\boldsymbol {p}}_{i}} , it suffices to show that P i T A P i {\displaystyle {\boldsymbol {P}}_{i}^{\mathrm {T} }{\boldsymbol {AP}}_{i}} is diagonal: </p> P i T A P i = U i − T V i T A V i U i − 1 = U i − T H i U i − 1 = U i − T L i U i U i − 1 = U i − T L i {\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}^{\mathrm {T} }{\boldsymbol {AP}}_{i}&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {V}}_{i}^{\mathrm {T} }{\boldsymbol {AV}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {H}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {L}}_{i}{\boldsymbol {U}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {L}}_{i}\end{aligned}}} <p>is symmetric and lower triangular simultaneously and thus must be diagonal. </p><p>Now we can derive the constant factors α i {\displaystyle \alpha _{i}} and β i {\displaystyle \beta _{i}} with respect to the scaled p i {\displaystyle {\boldsymbol {p}}_{i}} by solely imposing the orthogonality of r i {\displaystyle {\boldsymbol {r}}_{i}} and conjugacy of p i {\displaystyle {\boldsymbol {p}}_{i}} . </p><p>Due to the orthogonality of r i {\displaystyle {\boldsymbol {r}}_{i}} , it is necessary that r i + 1 T r i = ( r i − α i A p i ) T r i = 0 {\displaystyle {\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {r}}_{i}=({\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {Ap}}_{i})^{\mathrm {T} }{\boldsymbol {r}}_{i}=0} . As a result, </p> α i = r i T r i r i T A p i = r i T r i ( p i − β i − 1 p i − 1 ) T A p i = r i T r i p i T A p i . {\displaystyle {\begin{aligned}\alpha _{i}&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{({\boldsymbol {p}}_{i}-\beta _{i-1}{\boldsymbol {p}}_{i-1})^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\text{.}}\end{aligned}}} <p>Similarly, due to the conjugacy of p i {\displaystyle {\boldsymbol {p}}_{i}} , it is necessary that p i + 1 T A p i = ( r i + 1 + β i p i ) T A p i = 0 {\displaystyle {\boldsymbol {p}}_{i+1}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}=({\boldsymbol {r}}_{i+1}+\beta _{i}{\boldsymbol {p}}_{i})^{\mathrm {T} }{\boldsymbol {Ap}}_{i}=0} . As a result, </p> β i = − r i + 1 T A p i p i T A p i = − r i + 1 T ( r i − r i + 1 ) α i p i T A p i = r i + 1 T r i + 1 r i T r i . {\displaystyle {\begin{aligned}\beta _{i}&=-{\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&=-{\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }({\boldsymbol {r}}_{i}-{\boldsymbol {r}}_{i+1})}{\alpha _{i}{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {r}}_{i+1}}{{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}}{\text{.}}\end{aligned}}} <p>This completes the derivation. </p> <ol><li><a href="/facts/David_Hestenes/9Ml7UBqS">Hestenes, M. R.</a>; <a href="/facts/Eduard_Stiefel/fYk0NTDe">Stiefel, E.</a> (December 1952). <a href="http://nvlpubs.nist.gov/nistpubs/jres/049/6/V49.N06.A08.pdf">"Methods of conjugate gradients for solving linear systems"</a> (PDF). <i>Journal of Research of the National Bureau of Standards</i>. 49 (6): 409. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.6028%2Fjres.049.044">10.6028/jres.049.044</a>.</li> <li>Shewchuk, Jonathan Richard. "<i><a href="https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf">An introduction to the conjugate gradient method without the agonizing pain</a></i>." (1994)</li> <li>Saad, Y. (2003). "Chapter 6: Krylov Subspace Methods, Part I". <a href="https://archive.org/details/iterativemethods0000saad"><i>Iterative methods for sparse linear systems</i></a> (2nd ed.). SIAM. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89871-534-7.</li></ol> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Conjugate Direction Methods http://user.it.uu.se/~matsh/opt/f8/node5.html <a href="http://user.it.uu.se/~matsh/opt/f8/node5.html" target="_blank">http://user.it.uu.se/~matsh/opt/f8/node5.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>