Motivation
A mathematical model often ends with equations, not an answer. A discretized boundary-value problem gives a large sparse system ; an equilibrium model may instead give nonlinear equations . A solver produces an approximation, and understanding that output requires three separate questions: does the problem have a unique solution, does the algorithm converge in exact arithmetic, and how does finite precision affect the computed answer? A small residual alone answers none of these completely.
We first factor a matrix to solve one or many right-hand sides. We then study an iterative update through its error equation, and finally derive Newton's method by replacing a nonlinear function locally with its tangent. The examples are small enough to check by hand, but the same distinctions matter in large computations.
Definitions
Definition 1.1.1
(Residual, error, and conditioning)
For nonsingular , let and let be an approximation. Its error is and its residual is . Thus . In any induced norm, . When and , the relative bound is
The residual is measurable without knowing ; the error generally is not. The condition number measures sensitivity of the problem to perturbations, whereas stability describes an algorithm. Changing an algorithm cannot make an intrinsically ill-conditioned problem well conditioned, although a stable method avoids unnecessarily amplifying rounding errors.
Concept lensGeometric
Condition number as a distance to singularity
In the Euclidean norm, , the ratio of the largest to the smallest singular value. Equivalently, its reciprocal is the relative distance from to the nearest singular matrix:
For , replacing by is a relative change of . An ill-conditioned matrix is one that a small relative perturbation makes singular.
Main results
Theorem 1.1.2
(LU factorization without row exchanges)
If every leading principal submatrix of is nonsingular, elimination gives a unique factorization , where is unit lower triangular and is upper triangular. The intermediate pivots are nonzero.
Proof
(Pivots as ratios of leading minors)
At each elimination stage the pivot is the ratio of consecutive leading principal determinants, so the hypotheses make division legal. The elimination multipliers placed below the diagonal form ; reversing the elimination operations yields . If , then is simultaneously unit lower triangular and upper triangular, hence is the identity. This proves uniqueness.
The theorem does not say row exchanges are unnecessary in floating-point arithmetic. Partial pivoting selects a largest-magnitude entry in the active column and yields for a permutation matrix . Solve by forward substitution and by backward substitution. A factorization can be reused for several values, while an explicit inverse is usually unnecessary.
Theorem 1.1.3
(Convergence of a stationary iteration)
For with a fixed point , convergence to from every initial vector occurs exactly when the spectral radius . In particular, any induced norm satisfying is a sufficient condition.
Proof
(Powers of the iteration matrix)
The error satisfies , so . Jordan normal form shows that precisely when all eigenvalues have magnitude below one: powers of a Jordan block are polynomial factors in times decaying powers of its eigenvalue. Conversely, if with and , then does not tend to zero; when is complex, its real or imaginary part is a real initial error that fails to converge. The norm condition implies .
Proof X-ray
From an affine iteration to matrix powers
The fixed-point equation is used once, to cancel : the error obeys the linear recursion , and since is arbitrary, convergence from every start means exactly . Sufficiency is the real work. A Jordan block with nilpotent has -th power , a sum of finitely many terms, each a polynomial in times ; when the geometric decay beats the polynomial growth. Necessity needs only one eigenvector, plus the real-part trick when is complex. The norm condition bypasses eigenvalues entirely, which is why it is only sufficient: .
For with nonzero diagonal, Jacobi iteration uses and . A row strictly diagonally dominant matrix has , because each absolute row sum of is below one. This sufficient condition is convenient, but failure of diagonal dominance is not proof of divergence. For example, has infinity norm but .
Worked examples
Worked example 1.1.4
(Eliminate once, solve twice)
For , subtract twice row one from row two. Then
For , forward substitution gives , and backward substitution gives . For , the same factors give and . Direct multiplication checks both answers.
Worked example 1.1.5
(Jacobi error contracts)
Take and . Jacobi gives and . From , the first two iterates are and . Here ; the unique fixed point is . The error bound is geometric, though it need not be sharp at each step.
Worked example 1.1.6
(Newton approximates a square root)
For , Newton's update at a nonzero is . With , the first steps are and . If and , then
Near , the error is approximately squared at each step. This is a local statement, not a promise for every starting point.
Methods and reasoning
Newton's method replaces by . Solve and set ; one should solve this linear system rather than form the inverse Jacobian. For scalar , this gives when the derivative is nonzero. If is twice continuously differentiable near a root with , continuity bounds away from zero nearby. Taylor's theorem then gives for starts sufficiently close. The small neighborhood must also be chosen so iterates remain inside it. For a multiple root the nonzero-derivative hypothesis fails: produces , only linear convergence.
The sequence can fail even for a smooth function with simple roots. For , starting at gives , and starting at gives : the method cycles. A derivative can also vanish before a root is reached. Damping or a safeguarded bracket may help, but their guarantees require their own assumptions. A useful stopping rule examines a scaled residual and the size of the latest correction, sets an iteration limit, and reports failure when the linear solve or progress fails. A small correction can mean stagnation, not accuracy.
From a residual to an interpretable certificate
The relation can be read in two directions. First, exactly solves the perturbed right-hand-side problem . Thus measures a particular relative backward error when the matrix is held fixed. Second, the original problem maps that perturbation back into an error through . The two observations explain the condition-number bound rather than treating it as a mysterious warning. If both matrix and right-hand side are allowed to vary, a different backward-error measure must be specified; the residual alone is not its complete definition.
For example, consider with . In the Euclidean or infinity norm, . A perturbation of the second component of by changes the second component of the solution by . This is an actual sensitivity in the model, even if the linear equations are solved exactly. On the other hand, a perturbation in the first coordinate is not amplified. The condition number is a worst-case bound and need not predict every individual perturbation.
Pivoting and arithmetic cost
Consider for small nonzero . Elimination without an exchange uses multiplier and creates the entry . In finite precision, large intermediate values can cause cancellation when the solution is recovered. Exchanging the rows first uses a pivot of magnitude one and avoids this particular small divisor. The matrix is nonsingular for , so this is a numerical issue rather than a proof of nonexistence.
For a dense system, ordinary elimination takes order arithmetic operations, while each subsequent triangular solve takes order . This distinction matters when the matrix is fixed but many loads must be solved. For sparse matrices, elimination can introduce nonzeros called fill-in, and storage and cost depend on ordering as well as dimension. The simple dense count does not capture those effects. Pivoting improves practical robustness but is not a universal guarantee of small forward error for an ill-conditioned system.
Comparing Jacobi and sequential updates
Jacobi forms every component of the next vector from the old vector. Gauss–Seidel instead uses newly computed components immediately. With , its equation is . Since is lower triangular with nonzero diagonal, each step is a forward substitution; there is no need to compute its inverse. Its iteration matrix is , so the same spectral-radius criterion applies, but its convergence factor is generally different from Jacobi's.
For the preceding system, start Gauss–Seidel at zero. The first coordinate becomes ; immediately using it gives the second coordinate . The first iterate is therefore , unlike Jacobi's . This single comparison does not establish which method is always faster. Their ordering, convergence, parallelism, and cost depend on the matrix and implementation.
A posteriori bounds can make the iteration test meaningful. If , then the geometric tail yields for . Indeed, bound each subsequent step by another factor and sum the tail. This certificate requires a known contraction bound; observing a small step without it is not sufficient.
Why Newton's quadratic estimate is local
The local statement of the previous section becomes a theorem once the neighborhood is chosen with care.
Theorem 1.1.7
(Local quadratic convergence of Newton's method)
Let be twice continuously differentiable on an open interval containing a root with . Let be such that and on , and put . Let if and otherwise. If , then every Newton iterate is defined, lies in , and satisfies
In particular .
Proof
(Taylor expansion about the current iterate)
Such a exists: is continuous with , so on a small closed interval around , and the continuous function is bounded there. Suppose . Then , so and is defined. Taylor's theorem about gives a point between and , hence in , with
Dividing by and substituting the update yields
so . In particular . Induction from shows that all iterates stay in , that the error at least halves at each step, and that the quadratic bound holds throughout.
Proof X-ray
Which hypothesis keeps the iterates in the good region
The hypothesis enters only through the lower bound , and it is used twice: once to make the update defined, and once in the denominator of the error identity. The bound on controls the Taylor remainder. The expansion is taken about and evaluated at , not at , so the identity involves only the current error.
The non-obvious move is the choice . The quadratic bound alone does not stop an iterate from leaving , where and no longer apply; the factor turns it into the contraction , and that contraction is what lets the induction close. For the double root of no lower bound exists on any interval around ; the iteration still converges, but only linearly. Without the bounds, a tangent may point away from a root or be nearly horizontal.
Perturbations of the matrix
Right-hand-side perturbations are only one source of uncertainty. Suppose solves and solves . Subtraction gives
If , the triangle inequality and induced norm bound imply
This bound assumes the perturbed solution exists; the strict inequality also ensures invertibility through the convergent Neumann series for . It shows how relative error depends jointly on data perturbations and conditioning. If the denominator is close to zero, the estimate is weak; that does not prove the actual perturbation has caused a large error.
A Newton system with two unknowns
Consider , whose Jacobian is . From , the residual is . Solve : the first equation gives , and the second gives . Thus the next point is . The Jacobian determinant is ; the step is undefined on the line . A root exists at , but existence of that root alone does not guarantee convergence from an arbitrary starting pair. In an implementation, a linear-system residual should also be checked if the inner solve is approximate.
Limits of residuals and stopping rules
In large problems, computing the exact solution in order to check the error is usually as hard as the original problem, so the residual is the computable evidence. Its size must be read together with the scale of the data: multiplying the whole equation by a small constant leaves the solution unchanged but shrinks the absolute residual by the same factor. A relative residual is more meaningful when the right-hand side is nonzero, but it must still be combined with the condition number; when the right-hand side is zero, or different equations carry different physical units, a suitable scaling must be chosen separately. Recording the iteration count, the residual and the latest correction together at stopping helps to distinguish convergence from stagnation. In finite precision the computed residual is itself affected by rounding, so steady improvement cannot be expected once it reaches the rounding level.
Common misconceptions
Two mistakes recur with elimination and iteration.
Common mistake
(A zero pivot does not mean a singular matrix)
The matrix is invertible (it is its own inverse), yet ordinary elimination stops at once because the first pivot is zero. The hypothesis of the LU theorem concerns the leading principal submatrices, not invertibility; one row exchange, giving , handles this matrix.
Common mistake
(One convergent start does not prove convergence)
For and , the start converges to the fixed point , while doubles at every step. The spectral-radius theorem is a statement about every initial vector; a single successful run only tests the components present in its own initial error.
Nor does a small residual alone imply a small error; scaling and conditioning both matter, as the following example makes concrete.
Counterexample mode
A tiny residual can hide an order-one error
The false claim is that an absolute residual below guarantees an error below . Take , , and . The residual norm is but the error norm is . The repaired statement uses ; the large inverse norm is indispensable. Scaling the units of the equation can also change an absolute residual, which motivates a relative, problem-aware tolerance.
Quick check
Quick check
(If and the initial infinity-norm error is at most , what bound holds after three steps of ?)
Use and the submultiplicativity of the induced norm.
Solution · Answer
. This is a guaranteed upper bound, not necessarily the actual error.
Exercises
Exercise 1.1.8
(Factor as with unit diagonal in , then solve for .)
Foundation
Solution · Answer
Elimination uses the multiplier , giving and . Forward substitution gives ; backward substitution gives and , hence . Check: .
Exercise 1.1.9
(Find the spectral radius of . Does the iteration converge from every start?)
Foundation
Solution · Answer
The characteristic polynomial is , so the eigenvalues are . The spectral radius is , and convergence holds for every initial vector.
Exercise 1.1.10
(Apply two Newton steps to from .)
Foundation
Solution · Answer
The update is . Thus and , compared with . Both divisions are legal because the iterates are nonzero.
Exercise 1.1.11
(For , and , compute the residual and the error in the infinity norm, and explain their disparity.)
Core
Solution · Answer
Here , and . Their norms are and . Since , the bound is attained: the inverse amplifies the second coordinate by .
Further study
Sparse storage, pivot growth, backward error, nonlinear systems and preconditioned Krylov methods extend these ideas. Each requires additional hypotheses and numerical analysis; the simple examples here do not by themselves establish a production solver's stability.