Why keep the whole Krylov basis?
The preceding note explained conjugate gradients for a symmetric positive-definite matrix. Symmetry and positivity do real work there: they supply an energy norm and allow a short recurrence. A discretized transport operator or a general Newton Jacobian may have neither property. We still want to use matrix-vector products, but we need a different minimization problem and a basis construction that does not assume symmetry.
Suppose is nonsingular and we want to solve . Choose an initial approximation and form . If , stop. Otherwise set and . Throughout this note, inner products and norms are Euclidean and all algebra is in exact arithmetic. The nonsingularity assumption will be used explicitly; it is not an incidental condition.
The correction space used at GMRES step is
Trying to use these powers directly can give almost parallel vectors, even when they are algebraically independent. Arnoldi instead builds an orthonormal basis of the same space. GMRES then chooses the correction in that basis that makes the residual as small as possible. First we derive the finite-dimensional identities; floating-point stability requires additional analysis.
Arnoldi orthogonalization and its stopping condition
Definition 1.3.1
(One exact Arnoldi step)
Assume are orthonormal. Start with . For , in that order, set
Set . If it is positive, define . If it is zero, stop the basis construction: normalizing would divide by zero.
In exact arithmetic, subtracting the component in the new direction preserves orthogonality to all earlier directions. Indeed, for , the update changes by . Thus the final is orthogonal to every already constructed. Also, the earlier subtractions do not change its inner product with , so the stored coefficient is . This equality uses exact orthogonality; it should not be assumed automatically for computed floating-point vectors.
When the step does not stop, rearranging (1) gives
Write . If for , there are orthonormal vectors, so necessarily . Assemble the coefficients into the upper Hessenberg matrix : its entry is when and zero when . “Upper Hessenberg” means that only the first subdiagonal may be nonzero below the diagonal. Equations (2), column by column, become
Proposition 1.3.2
(The Arnoldi vectors span the intended space)
Under the no-breakdown assumptions just stated, the columns of form an orthonormal basis of for .
Proof
(Induction on the number of vectors)
The claim holds at . Suppose it holds at . Since , we have . Equation (1) therefore puts the next nonzero in , since the subtracted vectors also lie there. The normalized vector is orthogonal to the previous vectors, hence adds one independent direction. The space is generated by vectors, so these independent vectors in it are a basis. This proves the induction. In particular, a nonzero subdiagonal measures the arrival of a genuinely new direction.
Concept lensAlgebraic
Arnoldi as a QR factorization of the Krylov matrix
By induction, equals a positive multiple of plus a vector in , so the component of orthogonal to is a positive multiple of . Hence Arnoldi produces exactly the thin QR factorization
without ever forming . For (11), and . The Krylov matrix may be severely ill conditioned; Arnoldi delivers its orthonormal factor directly.
The residual is a small least-squares residual
Every candidate in has a unique representation . Let . Since , identity (3) gives
For any , orthonormality gives . Therefore (4) proves the exact equality
Theorem 1.3.3
(Unrestarted GMRES in exact arithmetic)
Let be nonsingular, , and suppose Arnoldi has no breakdown through step . The unique least-squares minimizer
defines , which uniquely minimizes over . Its residual satisfies
Proof
(Transfer the minimization through an isometry)
The matrix has full column rank. If , then (3) implies . Nonsingularity of and independence of the columns of give . Thus the quadratic least-squares objective is strictly convex and has a unique minimizer: its Hessian is , a positive-definite matrix. Equation (5) transfers its minimization exactly to the original affine space.
Differentiate the squared reduced objective with respect to . At the minimizer,
Using (3) and (4), equation (8) is precisely (7). Thus is perpendicular to , the image of the correction space. In general it is not perpendicular to itself. The correction is the orthogonal projection of onto .
Proof X-ray
Where nonsingularity and orthonormality enter
The proof has three moves, each with its own hypothesis. Uniqueness needs full column rank of , and that is where nonsingularity of is spent: gives , and only an injective turns this into . The transfer from the small problem to the original one is the identity (5), and its decisive ingredient is : for an arbitrary basis one would still have , but usually , so the Hessenberg relation alone is insufficient. Finally, the normal equations (8), pulled back through (3), give orthogonality of to , not to , because the residual depends on the correction only through its image under . In finite precision both (3) and orthogonality have defects, so (5) then needs a perturbation analysis or an explicitly recomputed residual.
The normal equations above establish the mathematics; they are not a recommendation to solve a least-squares problem by forming its normal matrix. A QR factorization of , often updated with plane rotations, solves the reduced problem without explicitly squaring its condition number. This note does not derive a finite-precision error bound for either implementation.
Common mistake
(Expecting the residual to be orthogonal to the Krylov space)
The Galerkin condition of conjugate gradients makes the residual orthogonal to . GMRES imposes instead. In the worked example below with , satisfies , but . Testing a GMRES code by checking would wrongly flag a correct implementation.
Since , unrestarted residual minima cannot increase with . They need not decrease strictly. This conclusion compares the minima of nested spaces and does not give a quantitative convergence rate.
What a zero Arnoldi subdiagonal means
Theorem 1.3.4
(Successful termination at an invariant Krylov space)
Let be nonsingular and . If the first zero subdiagonal is , then the GMRES iterate solves exactly. Such a always exists, so full unrestarted GMRES terminates in at most steps in exact arithmetic.
Proof
(The restriction to an invariant space is invertible)
Suppose the first zero is , after independent basis vectors have been built. Equation (2) still holds for , with no new vector, and yields
Consequently : the correction space is invariant. Since is nonsingular, its restriction to this finite-dimensional space is injective, hence surjective. Equivalently, is nonsingular: would give and then . Solve . Now
The residual norm is zero, its smallest possible value, so is the GMRES minimizer at step ; nonsingularity of makes it unique. This is a successful termination, sometimes called a happy breakdown. At the latest, after independent vectors have been constructed, no further orthogonal direction exists, so the next Arnoldi subdiagonal is zero and (10) applies.
The theorem is finite termination of full, unrestarted GMRES for a nonsingular system in exact arithmetic. It gives neither a useful iteration count for a large problem nor a floating-point promise. For a singular matrix, an invariant space need not contain a solution; one of the exercises exhibits the failure.
Worked example 1.3.5
(Termination at the first step)
Let , and . Then and , so and the remainder is zero: and . Here , the reduced equation gives , and satisfies . Breakdown at the first step happens exactly when is an eigenvector of ; nonsingularity guarantees that its eigenvalue is nonzero, so the division is legitimate.
A complete nonnormal example
Worked example 1.3.6
(Two eigenvalues equal to one, yet a poor first residual)
Let , , and
Here and . The first Arnoldi step gives
The reduced objective is . Its derivative vanishes at , so
The orthogonality condition is visible: , whereas . For , , and the residual norm is . As grows the ratio approaches one.
For the second step, . Subtracting its component along does nothing; subtracting its component along leaves zero. Thus , , , and
The final correction is , and direct multiplication gives . The first step can make almost no progress even though the second exact step solves the system.
Worked example 1.3.7
(Complete stagnation until the last step)
Let be the cyclic permutation with , , , and take , . Arnoldi gives , , , with , and every other computed entry zero, including . At step one the reduced objective is , and at step two it is , so and . At step three forces , so and . This is orthogonal, hence normal, with eigenvalues the three cube roots of unity . For any of degree at most two, , so forces : the bound (14) with predicts no progress before step three. Stagnation is therefore not only a nonnormal phenomenon.
The order of the Arnoldi basis matters in this calculation. The original matrix is upper triangular in the coordinate order , whereas is expressed in the order . A projected matrix is not obtained by copying entries without tracking the basis.
Residual polynomials and the limitation of eigenvalue pictures
Here all polynomial minimizations are over real coefficients. Any correction in can be written as for a real polynomial of degree at most . Its residual is
Conversely, every polynomial of degree at most with has this form, since is divisible by . Thus
If is diagonalizable, allowing complex and and using complex Euclidean norms for them, then
Indeed, and the norm of the diagonal matrix is ; apply the bound for each admissible and then minimize. The prefactor belongs to the chosen eigenvector matrix. For a normal matrix, an orthonormal complex eigenbasis makes it one, using the complex Euclidean norm if necessary. For a general nonnormal matrix it can be large, or the matrix may not be diagonalizable at all. Equation (14) cannot be used after silently dropping its hypotheses or its prefactor.
Counterexample mode
Vanishing at every eigenvalue need not annihilate a matrix
The matrix (11) has only the eigenvalue , counted twice. Yet for ,
The scalar condition therefore does not imply a zero residual. This matrix is not diagonalizable when and is nonnormal: the first diagonal entries of and are respectively and . Its nonzero nilpotent part satisfies , so does annihilate . This agrees with the two-step solution, while (12) quantifies the poor one-step progress. The repair is to study under stated structural hypotheses, rather than infer a general GMRES rate from eigenvalues alone.
Storage, restarting, and what a residual certifies
After unrestarted steps Arnoldi retains vectors of length . The next step takes one matrix-vector product and orthogonalization against every retained vector. This growing cost motivates restarted GMRES: use a fixed number of steps, retain the resulting approximation, and begin a new Krylov construction with its residual. Each exact cycle includes its starting approximation among its candidates, so residual norms remain nonincreasing across cycles. The earlier full-space finite-termination proof no longer applies: restarting discards directions. It can even repeat the same unproductive one-dimensional search, as the rotation exercise below shows.
Preconditioning also changes the problem being minimized. With an invertible fixed right preconditioner , write and solve . GMRES minimizes the true residual in its generated correction spaces. With left preconditioning, solve ; the minimized norm is , which need not rank approximations in the same order as . These are exact algebraic distinctions, not claims that either preconditioner is effective.
Finally, the forward error is . Hence . A residual can certify an error target only when accompanied by appropriate inverse or conditioning information.
Common mistake
(Reading a small residual as a small error)
For and the solution is . The approximation has residual norm yet error norm ; the factor is exactly what the residual does not see.
Monitor the residual relevant to the original model and balance its target against data and discretization errors. Nothing in residual minimization removes those considerations.
Practice
Exercise 1.3.8
(Set in (11). Compute the first reduced minimizer, the residual, and both and . Verify the second iterate directly.)
Foundation
Solution(3)
- 1
Minimize the reduced objective
The objective is , minimized at . Thus and .
- 2
Compute the two inner products
and .
- 3
Check the second iterate
The second iterate is , and .
Exercise 1.3.9
(Suppose Arnoldi has not broken down. Prove that would force , contradicting no breakdown. This implication does not require nonsingularity. Explain why it is consistent with successful termination when is nonsingular.)
CoreProof
Solution(4)
- 1
Translate a zero residual into the reduced system
implies .
Because: Identity (4) and orthonormality of .
- 2
Back-substitute from the last row
Key step
The last row is , so . The row above then gives . Working upwards gives every component zero. For the last row gives directly.
Because: Every subdiagonal is positive.
- 3
Reach a contradiction in the first row
The first row now reads , contradicting . Nonsingularity was not used.
- 4
Reconcile with successful termination
∎An exact solution cannot occur while all these subdiagonals are positive. For nonsingular it occurs at an invariant-space termination, where the rectangular no-breakdown system is replaced by (9).
Exercise 1.3.10
(Let , , . Compute a one-step GMRES minimizer. Explain why GMRES restarted after every single step stagnates. Then construct the two-step unrestarted solution.)
Core
Solution(3)
- 1
Run one Arnoldi step
, , , . The reduced objective is , so , , and .
- 2
Explain the stagnation of restarts
Key step
A one-step restart begins with exactly the same approximation and residual, so every cycle repeats this calculation.
- 3
Continue without restarting
and , giving . Solving yields , hence and .
Exercise 1.3.11
(Remove nonsingularity: let , , . Carry out the first Arnoldi step. Does breakdown imply a solution? Identify the exact point in the successful-termination proof that fails.)
Core
Solution(3)
- 1
Run the first Arnoldi step
and , so . The invariant space is , but maps all of it to zero.
- 2
Test the reduced and original equations
The reduced equation is , which is inconsistent. The original equation is also inconsistent, because its second row would require .
- 3
Locate the failed implication
The failed step is “the restriction is injective, hence surjective”: is singular and its restriction here is not injective. Every is a least-squares minimizer with residual , so uniqueness also fails; no minimizer has zero residual.
Exercise 1.3.12
(For (11), express as and write its residual polynomial . Give a degree-two polynomial with constant coefficient one that gives zero residual. Explain why is an admissible but generally nonminimizing degree-one choice.)
Synthesis
Solution(3)
- 1
Read off the one-step polynomial
and give exactly (12).
- 2
Annihilate the matrix
The polynomial satisfies .
- 3
Compare with the eigenvalue-vanishing choice
The choice corresponds to and has residual of norm ; for every this exceeds . Vanishing at the sole eigenvalue is therefore compatible with a worse residual than the minimizing degree-one polynomial.
Scope of this derivation
We have established an exact-arithmetic construction for nonsingular finite systems, its residual minimization, and its invariant-subspace termination. Practical orthogonality loss, reorthogonalization criteria, stable rotation updates, flexible or variable preconditioning, block methods, and large sparse matrix-equation solvers need further treatment.