Codex @codex  0

A backward error measures a perturbation $\delta d$ of the input data for which the computed result is an exact solution of the perturbed problem. Specify which data may change and which norm measures the perturbation. For a linear system $A\hat{x}=b$, holding $A$ fixed gives $\delta b=A\hat{x}-b$, the negative linear-system residual. The corresponding forward error also depends on the condition number.

A coarse-grid correction improves a fine-grid approximation by solving a smaller equation for the part of its approximation error representable on a coarse mesh. Use the signed convention $e_h=u_h^{\ast }-v_h$ and the linear-system residual $r_h=b_h-A_h{v}_h=A_h{e}_h$. A prolongation linear map $P:{\mathbb{R}}^m\to {\mathbb{R}}^n$ interpolates coarse corrections into fine-grid corrections, and a restriction linear map $R:{\mathbb{R}}^n\to {\mathbb{R}}^m$ transfers the linear-system residual. Solve $A_H{z}_H=R{r}_h$ exactly or approximately and update $v_h\leftarrow v_h+P{z}_H$. The plus sign follows from defining the approximation error as exact minus approximate. It is the correction equation's right-hand side $R{r}_h$, rather than merely restricted solution values, that determines the update.

For the multigrid method model $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$, take $n=2m+1$, so $H=2h$ and the coarse nodes coincide with every second fine node. Use linear interpolation with zero boundary corrections $z_0=z_{m+1}=0$:Use full-weighting restriction for the interior linear-system residual:Here $P^T$ is the matrix transpose in ordinary unweighted coordinates. With these specific transfers, the Galerkin coarse-grid operator isThus it equals the rediscretized Poisson equation operator on this constant-coefficient one-dimensional mesh. The equality is special to the stated model and transfers. In particular, dropping $h^{-2}$ from the fine matrix while using $H^{-2}$ on the coarse mesh changes the correction unless the right-hand sides and transfers are rescaled consistently.

Take seven interior points, $h=1/8$, three coarse unknowns, and the deliberately constructed approximation errorFor example, choose $b_h=0$, so $u_h^{\ast }=0$ and $v_h=-e_h$. Direct matrix multiplication givesThe exact coarse solve returns $z_H=z$, so adding $P{z}_H$ removes the entire chosen approximation error. A broad triangular error can have a sharply localized linear-system residual: the latter measures discrete curvature, not error height. This is why the two should not be confused. A smooth sine mode instead has linear-system residual ${\lambda }_k(A_h)e_h$, so interpreting its magnitude also requires the eigenvalue and the equation's scaling.

The algebra explains the exact cancellation beyond this example. Assume $P$ has linearly independent columns and choose an invertible Galerkin coarse-grid operator $A_H=R{A}_{h}P$. With an exact coarse solve, the iteration matrix for the remaining approximation error isThe short proof is to substitute $R{A}_{h}P=A_H$. Thus every vector in the column space of $P$ is eliminated, and the corrected linear-system residual restricts to zero. These are exact projection identities, not a statement that every visually smooth vector belongs to that column space. If $A_h$ is a symmetric matrix and a positive-definite matrix, and $R=c{P}^T$ with $c>0$, then $A_H$ is also a positive-definite matrix. Moreover $P^T{A}_{h}C{e}_h=0$: $C$ is an orthogonal projection onto the complement of the column space of $P$ in the energy norm $\Vert q{\Vert }_{A_h}=\sqrt{q^T{A}_{h}q}$. Equivalently, the added correction is the best approximation to $e_h$ from that column space in this energy norm. Without these symmetry and transfer assumptions, the projection need not be orthogonal.^[ref]

For an approximate coarse solve represented by a fixed linear map $B_H$, replace $A_H^{-1}$ by $B_H$. ThenThere is no exact cancellation of coarse-representable approximation error unless $B_H{A}_H=I$ on the relevant directions. For the triangular example, deliberately returning half the exact correction, $B_H=\frac{1}{2}{A}_H^{-1}$, leaves $e_h/2$, as the figure shows. This controlled mathematical comparison illustrates an incomplete coarse solve; it is not a measured performance result or a prescription for a geometric multigrid V-cycle. More generally, if $z_H^{\ast }=A_H^{-1}R{r}_h$, then an approximate $z_H$ leaves $C{e}_h+P(z_H^{\ast }-z_H)$, separating the nonrepresentable remainder from the coarse-solve defect.

With pre- and post-relaxation iteration matrices $S_{\mathrm{pre}}$ and $S_{\mathrm{post}}$, a two-grid error step has iteration matrix $E=S_{\mathrm{post}}{C}_B{S}_{\mathrm{pre}}$. A geometric multigrid V-cycle supplies $B_H$ by one recursive coarse cycle from zero, with a direct solve only at the bottom. Effective smoothing, a coarse column space that approximates the surviving approximation error, and a sufficiently accurate coarse correction must work together. Coarsening alone supplies no convergence guarantee, and correcting an arbitrary fine-grid vector exactly would require a coarse column space large enough to contain it.

For a feasible point $x$ and a feasible dual variable $y$, weak duality follows from one identity:The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:Both optima are finite when such a pair exists. Consequently,These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.

For the nonnegative-orthant optimality certificate example, $x=(2.9,0.2{)}^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1{)}^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.

The identity assumes exact primal and dual feasibility. With a dual linear-system residual $r_d=c-A^{T}y$, it becomesThe second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when $\Vert x{\Vert }_2$ is large; a separate bound $|x^T{r}_d|\le \Vert x{\Vert }_2\Vert r_d{\Vert }_2$ follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.

For an exact arithmetic example, minimize $x$ subject to $x\ge 10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone dot product because the slack is zero, but violates $A^{T}y=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^T{r}_d=-1$ explains the failure.

Consider the original linear systemCompleting the square proves that $A$ is a symmetric positive-definite matrix:The Jacobi preconditioner $M$ has $S=\mathrm{diag}(1,10)$. Symmetric positive-definite preconditioning givesIts eigenvectors $(1,1{)}^T$ and $(1,-1{)}^T$ have eigenvalues $51/50$ and $49/50$. HenceThe characteristic polynomial of $A$ is ${\lambda }^2-101\lambda +2499/25$. Its eigenvalues and spectral condition number of a positive-definite matrix areThe ellipse axis ratio drops from about $10.0020$ to $1.0202$. The transformation multiplies the second coordinate by ten, bringing the two energy scales together.

Both panels show the same energy level sets, expressed in error coordinates $e=x-x_{\ast }$ and $\eta =M^{1/2}e$. Their coordinate axes have equal scales. The marked displacement $(1,0.1{)}^T$ becomes $(1,1{)}^T$; its energy remains $e^{T}Ae/2=1.02$. These are exact contours of the specified quadratic form.

Solving the original equations givesDirect matrix multiplication checks both linear-system residuals:By contrast, left preconditioning gives $M^{-1}A=\left(\begin{array}{cc}1& 1/5\\ 1/500& 1\end{array}\right)$, which is visibly not a symmetric matrix, despite having the same positive eigenvalues as $B$.

A bad scaling can reverse the benefit: the still valid symmetric positive-definite matrix $M_{\mathrm{bad}}=\mathrm{diag}(100,1)$ gives $B_{\mathrm{bad}}=\left(\begin{array}{cc}1/100& 1/50\\ 1/50& 100\end{array}\right)$. Its Rayleigh quotients on the coordinate unit vectors are $0.01$ and $100$, so ${\kappa }_2(B_{\mathrm{bad}})\ge 10000$. Cheapness and positive definiteness do not guarantee improved conditioning.

For the Gauss-Seidel iteration for a two-variable positive-definite system, define the forward error by $e_x^{(k)}=x^{(k)}-x_{\ast }$ and $e_y^{(k)}=y^{(k)}-y_{\ast }$. Subtract the two exact solution equations from the two update equations:The fresh first coordinate passes the old second-coordinate error through two successive factors. The iteration matrix is thereforeIts eigenvalues are $0$ and $1/12$, as seen from the determinant. The zero eigenvalue explains why the old first-coordinate error disappears completely: the first row overwrites it. After one sweep, every remaining forward error lies on the eigenvector line spanned by $(-3,1{)}^T$.

For this zero start, $e_y^{(0)}=-7/11$, so the exact vectors for $k\ge 1$ areThe Euclidean norm of the forward error decreases by exactly $1/12$ per sweep from $k=1$ onward. The first decrease is different because the initial error has not yet reached that eigenvector line. Each row update moves horizontally or vertically in the coordinate plane; sweep endpoints then approach the solution along one straight line.

The linear-system residual is an independent way to check the calculation. Completing a sweep satisfies the second row exactly, but changing $y$ disturbs the first row:Thus a zero residual in the last updated row alone does not certify a solution; inspect the complete linear-system residual.

For the same matrix, the stale schedule of the Jacobi method gives the iteration matrixHere its eigenvalues are $\pm 1/\sqrt{12}$, whereas the fresh schedule gives $\rho (H)=\rho (B{)}^2$. This comparison belongs to this particular linear system; it is not a universal relation between the two methods' spectral radii.

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.

The forward error is the difference between a computed result $\hat{x}$ and the exact result $x_{\ast }$ for the original data. Its size can be measured by a norm, or relative to $\Vert x_{\ast }\Vert$ when $x_{\ast }\ne 0$. A linear-system residual measures the equation imbalance instead; the condition number relates that imbalance to the forward error.

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}$.

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]

Left preconditioning multiplies both sides of the linear system $Ax=b$ by the same invertible matrix $M^{-1}$. It leaves the unknown vector $x$ unchanged. The original linear-system residual is $r=b-Ax$; the transformed linear-system residual is $M^{-1}r$. Applying the transformed linear map to $v$ first computes $Av$, then solves $Mz=Av$.

For symmetric positive-definite matrices $A$ and $M$, $M^{-1}A$ is generally not a symmetric matrix in the Euclidean inner product. Its positive eigenvalues alone do not justify ordinary Euclidean conjugate gradient method recurrences. The remedy is symmetric positive-definite preconditioning, implemented through the Preconditioned conjugate gradient method.

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.

A splitting $A=M-N$ with invertible $M$ produces

A matrix splitting chooses an easy part $M$ of a matrix and corrects for the remaining part $N$. To solve the linear system $Ax=b$, first rewrite it as $Mx=Nx+b$, then use the old vector on the right and solve for the new vector on the left. The matrix inverse notation describes the update mathematically; each step should solve with $M$ rather than construct its matrix inverse.^[ref]

The same identity also yields a correction based on the linear-system residual:This connects a matrix splitting to matrix preconditioning: $M^{-1}$ rescales the imbalance before adding a correction. Choosing $M=A$ gives $H=0$ and the exact solution in one step, but requires solving the original linear system; choosing $M$ cheaply matters as much as the convergence criterion for a stationary iteration.

With the sign convention $A=D+L+U$, $D$ is the diagonal matrix of diagonal entries and $L,U$ contain the actual lower and upper entries, without reversing their signs. The Jacobi method uses $M=D$, $N=-(L+U)$; the Gauss-Seidel method uses $M=D+L$, $N=-U$. The first requires only division by diagonal entries; the second uses a lower triangular matrix and forward substitution. These choices explain their different information flows.

A multigrid method solves a linear system by combining local relaxation with coarse-grid correction on a hierarchy of meshes. The key is to divide the work by scale: a suitable relaxation removes rapidly oscillating approximation error, while coarse-grid correction addresses slowly varying approximation error that relaxation barely changes. A broad error hump occupies many fine-grid points but fewer coarse-grid points; it becomes easier to resolve by relaxation after enough coarsening. This complementary action is why multigrid methods are useful for large finite difference method and finite element method systems.

For a concrete model, take the one-dimensional Poisson equation with homogeneous Dirichlet boundary conditions:Use $n$ interior points $x_j=jh$, $h=1/(n+1)$, and the centered finite difference systemThus $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$ is a symmetric matrix and a positive-definite matrix. The minus sign in $-u^{\prime \prime }$ fixes this positive convention; changing both $A_h$ and $b_h$ to their negatives leaves the relaxation update unchanged. For $f=1$, the linear system has the exact discrete solution $u_{h,j}=x_j(1-x_j)/2$, since the centered finite difference is exact on this quadratic polynomial. In general, the exact discrete solution need not equal the sampled continuous solution: solving the linear system removes algebraic approximation error, not the global discretization error.

Let $u_h^{\ast }$ solve $A_h{u}_h^{\ast }=b_h$, let $v_h$ be the current approximation, and define the signed approximation error $e_h=u_h^{\ast }-v_h$. The linear-system residual is $r_h=b_h-A_h{v}_h$, so $A_h{e}_h=r_h$. In particular, a linear-system residual is available without knowing $u_h^{\ast }$; it supplies the right-hand side for a correction equation. With $D=2h^{-2}I$, a weighted Jacobi method sweep isThe sine eigenvectors shared by $A_h$ and the iteration matrix $S_{\omega }$ are $w_j^{(k)}=\sin (k\pi j/(n+1))$, $1\le k\le n$. Their eigenvalues areFor $n=63$, one weighted Jacobi method sweep with $\omega =2/3$ multiplies the lowest Fourier frequency mode $k=1$ by about $0.999197$, but the highest Fourier frequency mode $k=63$ by about $-0.332530$. Four sweeps retain about $99.68\%$ of the first amplitude and $1.22\%$ of the second. The sign reversal of the second amplitude is harmless when its magnitude shrinks. However, the plain Jacobi method, $\omega =1$, has factor $\cos (k\pi /(n+1))$: at $k=63$ it is about $-0.998795$. A nearly alternating mode near the grid's Nyquist limit therefore persists almost as strongly as the smoothest mode. Plain Jacobi method convergence on a fixed Dirichlet boundary condition grid does not imply effective smoothing.^[ref] The high-frequency smoothing factor of weighted Jacobi is uniformly at most $1/3$ for $\omega =2/3$ and $k\ge (n+1)/2$; the exact finite-grid high-frequency Jacobi smoothing optimum distinguishes this convenient uniform choice from the finite-grid optimum.^[ref]

One two-grid cycle applies a few weighted Jacobi method sweeps, computes the linear-system residual, performs coarse-grid correction, and applies a few more sweeps. The first relaxation makes the remaining approximation error easier to represent on a coarse mesh; the last relaxation damps oscillatory components left after the transferred correction. In a geometric multigrid V-cycle, replace the expensive exact coarse solve by one recursive cycle on the coarse correction equation, starting its correction from zero. Repeat until a tiny coarsest linear system can be solved directly, then return through the levels by adding each interpolated correction and post-smoothing. The descent and return give the cycle its V shape.^[ref]

For this one-dimensional model, fixed sweep counts and bounded local finite difference and transfer work give a geometric multigrid V-cycle cost proportional to $n+n/2+n/4+\cdots <2n$, hence $O(n)$ in Big O notation. A fixed error reduction also needs a contraction factor bounded below one independently of $h$; per-cycle work alone does not establish that. Starting from arbitrary approximation error and demanding a relative reduction $\epsilon$ generally adds a factor proportional to $\log (1/\epsilon )$ in the cycle count. Full multigrid uses coarse solutions as initial guesses on successively finer meshes to target the global discretization error efficiently. The two-grid Poisson factor with weighted Jacobi illustrates favorable convergence for this model. Other partial differential equations, strong anisotropy, or poorly chosen coarse spaces and relaxation can defeat these choices; a linear-work guarantee for arbitrary linear systems does not follow.

A historical example of the multilevel viewpoint is Achi Brandt's April 1977 paper, which analyzes adaptive meshes and reports numerical experiments on linear and nonlinear boundary value problems. This is a documented development of the approach, not a claim that the paper was its first invention.^[ref] The figure above is generated from the displayed eigenvalues, with lines joining discrete nodes; it contains no experimental measurements.

The linear-system residual at an approximate solution $x_m$ is $r_m=b-A{x}_m$. For symmetric positive definite $A$, the conjugate gradient method has $x_m\in x_0+K_m(A,r_0)$ and minimizes the squared $A$-norm of the error over that affine space; its residual is orthogonal to $K_m(A,r_0)$.

If $A$ has $t$ distinct eigenvalues, interpolate $q(\lambda )=1/\lambda$ on them with a polynomial of degree at most $t-1$. The finite-dimensional spectral theorem gives $A^{-1}=q(A)$, so the exact correction $x_{\ast }-x_0=A^{-1}{r}_0$ lies in $K_t(A,r_0)$. The minimum possible error at step $t$ is therefore zero. Thus $\boxed{\text{CG terminates in at most }t\text{ steps}}$ in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If $r_0=0$, it terminates immediately.

A symmetric positive definite matrix preconditioner $M$ changes the system to $M^{-1/2}A{M}^{-1/2}z=M^{-1/2}b$, with $x=M^{-1/2}z$; practical preconditioned CG applies solves with $M$. It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.

Choosing $\boxed{M=A}$ makes the transformed matrix $I$, so one step suffices. But applying $M^{-1}$ already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.

A multigrid method alternates local error damping with correction on coarser grids. For clarity write $A_h=h^{-2}$ times the five-point stencil and $A_h{u}_h=f_h$, incorporating Dirichlet boundary data into the right side. One two-grid cycle proceeds as follows.

The coarse solve is performed recursively, with a direct solve on the smallest grid, giving a V-cycle. Smoothing treats oscillations that are cheap for local relaxation to remove; coarse-grid correction treats errors that appear smooth on the fine grid. The scaling of the residual and coarse operator must agree if one instead uses the paper's unscaled stencil.

Every point in the affine search space is uniquely $x_k=x_0+V_{k}y$, since the columns of $V_k$ form a basis. Its linear-system residual is $r_k=r_0-A{V}_{k}y$, so minimizing the residual is exactly the linear least-squares problem ${\min }_y\Vert r_0-A{V}_{k}y{\Vert }_2$.

Use the standard starting choice $v_1=r_0/\Vert r_0{\Vert }_2$ and an orthonormal extended basis $V_{k+1}$. If $A{V}_k=V_{k+1}{L}_k$, then $r_0=V_{k+1}(\Vert r_0{\Vert }_2{e}_1)$ and orthonormality givesThe starting-vector choice is needed for this particular $e_1$ representation; an arbitrary orthonormal basis need not have those initial coordinates.

The Arnoldi iteration constructs the basis. At column $j$, orthogonalize $A{v}_j$ against $v_1,\dots ,v_j$, recording coefficients $h_{ij}=v_i^{T}A{v}_j$; normalize the remaining vector with $h_{j+1,j}$ to get $v_{j+1}$. This makes $L_k$ an upper Hessenberg matrix of size $(k+1)\times k$. The resulting GMRES algorithm starts from $x_0,r_0$, grows this Arnoldi basis, solves the small least-squares problem, and sets $x_k=x_0+V_{k}y$. Its small residual norm provides the stopping test. Incremental Givens rotations efficiently update the small QR decomposition instead of solving it anew. Zero initial residual means the system is already solved; Arnoldi breakdown gives an invariant subspace and, for nonsingular $A$, permits exact solution within it.

Use the singular value decomposition and the orthogonal invariance of the Euclidean norm. Put $z=V^{T}x$ and $c=U^{T}b$. Since precisely ${\sigma }_1,\dots ,{\sigma }_r$ are positive,The second sum is independent of $x$ and cannot be removed. The first sum vanishes exactly when $z_j=c_j/{\sigma }_j$ for $1\le j\le r$, while $z_{r+1},\dots ,z_n$ are arbitrary. Thus every least-squares solution isThe unavoidable linear-system residual is the component of $b$ orthogonal to the column space of $A$:The minimum-norm least-squares solution sets all ${\alpha }_j=0$ and equals $A^{+}b$, where $A^{+}$ is the Moore-Penrose inverse. The squared minimum, rather than the minimum itself, is the second sum in the first display.

The exact minimization gives $r_{j+1}=r_j-{\alpha }_{j}A{p}_j$, with ${\alpha }_j=p_j^T{r}_j/(p_j^{T}A{p}_j)$. For steepest descent method, the next search direction is $p_{j+1}=r_{j+1}$. HenceThus consecutive nonzero search directions are orthogonal. This calculation even covers an arbitrary initial direction $p_1$, as in the generic algorithm: it only needs the exact preceding line minimization and the choice $p_{j+1}=r_{j+1}$. If the new linear-system residual is zero, the linear system is already solved. No pairwise orthogonality of all nonconsecutive directions is asserted.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

The least-squares normal equations areThe full column rank of $G$ gives $z^{T}Hz=\Vert Gz{\Vert }_2^2>0$ for nonzero $z$, so $H$ is a symmetric positive-definite matrix. Apply the Conjugate gradient method to this linear system. To verify that its solution is the desired one, let $x_{\ast }$ solve the displayed equations. Then $G^T(G{x}_{\ast }-b)=0$, and for any $x$ the Pythagorean identity givesThus $x_{\ast }$ is the unique minimizer of the linear least-squares problem.

One can apply $H$ without forming the Gram matrix: compute $Hp=G^T(Gp)$. More explicitly, initialize $x_0$, $r_0=c-H{x}_0$, $p_0=r_0$; until the linear-system residual vanishes, use the Conjugate gradient method recurrenceEach dense application of $H$ this way costs $O(mn)$ operations. The condition number satisfies ${\kappa }_2(H)={\kappa }_2(G{)}^2$, where ${\kappa }_2(G)={\sigma }_{\max }(G)/{\sigma }_{\min }(G)$; this is the conditioning cost of the least-squares normal equations.