Motivation
Many computational problems are not solved in one step. A nonlinear model is replaced by a sequence of linear models, and each large linear system may itself need an iterative solver. Treating these layers separately makes it possible to ask sensible questions: Is the nonlinear model locally accurate? How accurately should each linear system be solved? Does a small residual imply a small error? Here we develop answers for Newton's method and symmetric positive-definite systems, then extend the same ideas to equations whose unknown is a matrix.
The earlier scalar Newton and stationary-iteration discussion is useful preparation. We will not assume that a method converges globally merely because it has an attractive local error estimate. The initial point, the conditioning of the Jacobian, and the cost of the linear solves all matter.
Definitions
Definition 1.2.1
(Newton step and residual)
Let be differentiable. At , if is nonsingular, the Newton step solves
For a linear system and an approximation , the residual is . The error satisfies if is the exact solution.
The Newton equation sets the first-order model to zero. It is a linear equation to solve, not an instruction to form explicitly. If is singular, the displayed step may be undefined or nonunique. A small linear residual controls the error only in conjunction with information about and the norms used.
For , the th Krylov space is . Its vectors can be formed using matrix-vector products without storing a dense inverse. If the space stops growing, the method has reached an invariant subspace; an implementation must treat such a breakdown according to the particular algorithm.
Main results
Theorem 1.2.2
(Local quadratic convergence of Newton's method)
Suppose is continuously differentiable near a zero , is invertible, and is Lipschitz there: . For sufficiently close to , all Newton steps are defined and
for a constant independent of .
Proof
(A uniform inverse bound and an integral remainder)
By continuity of and invertibility of , there is a ball about in which is invertible and . This follows, for instance, from the Neumann series applied to when its norm is below one. For , the integral form of the first-order expansion gives
The Lipschitz condition bounds the norm of the right side by . Since , the next error is , giving . Choose the initial ball small enough that this bound maps it into itself; induction establishes the result. Neither the size of that ball nor convergence from an arbitrary starting point follows from the theorem.
Proof X-ray
Why a nonlinear proof needs a uniform inverse bound
The proof combines two estimates of different kinds. The integral identity is pure calculus: it writes the linearization defect exactly, and the Lipschitz condition turns it into , because and are evaluated at points a distance apart. That quadratic quantity is then multiplied by , so the second estimate must be a bound at the current iterate, not at the root. Invertibility of alone gives no number at nearby points; continuity of together with the Neumann series supplies one on a ball.
The step that closes the argument is the choice of the radius of that ball, shrunk if necessary so that . Then , so the next iterate lies in the same ball and both bounds are available again; the theorem's constant is . Without invertibility of the bound can fail: for the root is double and Newton's iteration converges only linearly.
Theorem 1.2.3
(Conjugate-gradient minimization)
If is real symmetric positive definite (SPD), the exact-arithmetic conjugate-gradient iterate minimizes over . Its residual is orthogonal to that Krylov space. In at most steps it reaches , unless it has already terminated earlier.
Proof
(Energy minimization along A-orthogonal directions)
The quadratic satisfies . Minimizing over an affine subspace requires its gradient to be orthogonal to every direction in the subspace; strict positive definiteness makes the minimizer unique. Conjugate gradient constructs mutually -orthogonal nonzero search directions spanning successive Krylov spaces and chooses the exact line minimizer along each; the resulting gradient is orthogonal to their span. This establishes the stated minimization. At most nonzero mutually -orthogonal vectors exist; if the Krylov space ceases to grow earlier, it is invariant under . Since is invertible, then belongs to that invariant space, so the exact solution is already in the affine space. The finite-step claim is an exact-arithmetic result: roundoff destroys exact orthogonality.
More explicitly, . Since for , the update preserves every earlier condition . The new exact line minimization enforces . Thus orthogonality holds for every direction used so far, rather than only the latest one.
Proof X-ray
How k line searches add up to one k-dimensional minimization
The identity is the hinge: it replaces the error, which involves the unknown , by the computable quadratic , whose gradient is . Positive definiteness makes a norm, so the minimizer over an affine subspace exists and is unique, and it makes each line search well defined. The real idea is -orthogonality. A step along changes the gradient by , which is orthogonal to every earlier , so earlier line minimizations are not undone and one-dimensional searches deliver the minimizer over the whole -dimensional space. The argument closes by counting: nonzero -orthogonal vectors are linearly independent, so there are at most of them, and an earlier stall means an invariant space that already contains .
Worked examples
Worked example 1.2.4
(A two-variable Newton step)
For at , the residual is zero. At , and . Solving gives , hence . The step does not solve the quadratic equation exactly; its purpose is to remove the linearized residual. Starting close to , whose Jacobian determinant is , satisfies the local theorem's invertibility requirement.
Worked example 1.2.5
(One conjugate-gradient step)
Let , , . Then and the exact line-minimizing step is . Thus and , which is orthogonal to . The exact solution is . A second exact-arithmetic CG step reaches it; the first does not generally minimize Euclidean error, but minimizes the -norm error over the line .
Worked example 1.2.6
(A small Sylvester equation)
Solve for , , . The entry is , giving . This entrywise decoupling relies on both matrices already being diagonal in the chosen bases. If , the corresponding entry may be incompatible or undetermined; a unique solution is not automatic.
Methods and reasoning
Damping and inexact steps
Full Newton steps can fail far from a root. A damped step replaces by with ; a line search can choose using a merit function such as . It needs a stated acceptance rule and hypotheses to obtain a convergence theorem; damping is not a universal guarantee.
Large systems are often solved only approximately. Write the linear solve residual as . With , the update gives , and therefore
With the same local assumptions as above, a bound gives a linear-error contribution proportional to , in addition to the quadratic term. Fixed nonzero forcing generally permits only linear local convergence; making tend to zero can recover superlinear behavior under suitable bounds. To retain quadratic convergence it is sufficient locally to make , or equivalently when the local Jacobian bounds make residual and error comparable. Solving early systems far more accurately than the nonlinear model warrants may waste work.
Preconditioning and stopping
For SPD , choose an SPD preconditioner that is cheap to solve with. The transformed system
is SPD; practical preconditioned CG applies without explicitly computing a square root. A useful makes the transformed spectrum better clustered, but constructing and applying it has a cost. Naively applying ordinary CG to as though it were Euclidean-symmetric is not justified: that matrix need not be symmetric, even when and are SPD.
If eigenvalues of lie in , then and . These formulas show what the residual can certify when spectral information is known. For and , the residual norm is but the error is . Relative residuals should be interpreted with conditioning, data scale and desired accuracy; a stopping rule should also avoid solving far beyond discretization or measurement error.
Matrix equations and vectorization
With column-major vectorization, . Thus becomes
The identity follows by inspecting one entry, or by expanding in matrix-unit basis elements. It turns the solvability question into a question about one large matrix.
Theorem 1.2.7
(Unique solvability of the Sylvester equation)
Let and . The equation has a unique solution for every if and only if for every eigenvalue of and every eigenvalue of .
Proof
(Triangularize both factors of the Kronecker sum)
By the vectorization identity, the equation is the linear system with , so unique solvability for every is equivalent to being nonsingular. Take Schur forms and with unitary and upper triangular; the diagonal of lists the eigenvalues of , which are those of . With , the mixed-product rule gives
Both Kronecker products in the bracket are upper triangular, and the diagonal entry belonging to the pair is . A triangular matrix is nonsingular exactly when all its diagonal entries are nonzero.
Counterexample mode
Invertible coefficients do not make a Sylvester equation solvable
It is tempting to think that is uniquely solvable whenever and are both invertible. Take and , both invertible. The entrywise equations are , and . For the matrix of ones, the equation reads , so no solution exists. For , the other entries are , and , while is arbitrary, so solutions exist but are not unique. The correct hypothesis is the eigenvalue-sum condition of the theorem, which concerns and jointly.
Explicitly forming the large Kronecker matrix is often unnecessary: an iterative method can apply directly, preserving matrix structure. Nonsymmetric matrix equations call for methods such as GMRES rather than assuming the SPD theorem applies.
CG recurrence and its assumptions
For clarity, start with , , and . While , the exact-arithmetic recurrence is
If the new residual is nonzero, set and . Positive definiteness makes whenever . If , stop: the exact solution has been found and the next quotient would be unnecessary. The recurrence achieves the minimization theorem without storing all earlier basis vectors in exact arithmetic. In floating-point arithmetic, the recursively updated residual can drift from the explicitly recomputed ; checking the latter when convergence appears to have been reached is a useful diagnostic.
A small example also illustrates the purpose of preconditioning. For , choosing makes the transformed matrix the identity, so one exact CG step suffices. But this idealized preconditioner is only useful when applying is cheap; choosing the entire original matrix does not reduce the difficulty of a general solve. A practical preconditioner balances spectral improvement, memory and application cost.
Concept lensAlgebraic
Conjugate gradient as a best polynomial
Since lies in and , the error is for a polynomial of degree at most with . The minimization theorem therefore says
If has distinct eigenvalues, all positive, the polynomial vanishes on the spectrum, so exact CG terminates in at most steps. With the transformed matrix is and .
A nonsymmetric alternative
For a general nonsymmetric matrix, GMRES searches the same affine Krylov space but chooses the iterate minimizing the Euclidean residual norm, rather than the energy norm used by CG. Its usual Arnoldi construction orthogonalizes a new matrix-vector product against the existing basis, so storage and work grow with the number of unrestarted steps. Restarting limits storage but can slow convergence or cause stagnation. A residual-minimization property alone does not overcome ill-conditioning: the earlier relation still governs the difference between residual and forward error. This distinction is particularly relevant to nonsymmetric operators arising after discretization or preconditioning.
Common misconceptions
A residual is an equation defect, not intrinsically a forward-error estimate; the relation is what connects the two. Three further mistakes are specific to the methods of this section.
Common mistake
(A local quadratic rate is not a global guarantee)
Newton's quadratic rate describes iterates that are already sufficiently near a regular root. It does not guarantee that a root exists, that the iteration converges from an arbitrary initial value, or that the ball of the theorem is large. CG's finite termination is likewise a statement about exact arithmetic and SPD matrices.
Common mistake
(Running ordinary CG on the preconditioned product)
Even when and are SPD, is generally not symmetric: for and , . Ordinary CG applied to it has no minimization theorem. Preconditioned CG works instead with the SPD matrix , equivalently with the inner product , in which is self-adjoint, and it only ever applies .
Common mistake
(Multiplying a Sylvester equation by an inverse)
Multiplying on the left by gives , which still has inside a two-sided product; no one-sided multiplication isolates unless additional structure is used. The equation must be treated as a linear system in all entries of , through vectorization or a structured solver.
Quick check
Quick check
(Why can have real positive eigenvalues when it is not symmetric, for SPD and ?)
Look for a similarity transformation to a symmetric matrix.
Solution · Answer
, so is similar to the SPD matrix and has the same eigenvalues, which are real and positive. The similarity does not make the Euclidean eigenvectors of orthogonal.
Exercises
Exercise 1.2.8
(For , compute the Newton step at and verify that its linearized residual vanishes.)
Foundation
Solution · Answer
At , and the Jacobian is . The step solves , , giving . Substitution gives .
Exercise 1.2.9
(For , and , verify that the first CG residual from the example is orthogonal to , and calculate its Euclidean norm.)
Foundation
Solution · Answer
, so and .
Exercise 1.2.10
(Solve when , , and is the matrix of ones.)
Foundation
Solution · Answer
Each entry satisfies , so and . All four sums are nonzero, so by the solvability theorem the solution is unique.
Exercise 1.2.11
(Give an example where has residual norm but error norm one, and explain what extra information permits a forward-error bound.)
Core
Solution · Answer
Take , , and . The exact solution is zero, the error norm is one, and the residual has norm . If a positive lower bound for the smallest singular value is known, then ; here and the bound is attained.
Further study
Globalized Newton methods, nonsymmetric Krylov solvers, finite-precision loss of orthogonality, preconditioner construction and large sparse Sylvester algorithms need their own analyses. These notes establish selected tools, not an exhaustive numerical linear algebra course.