A solution is more than a small residual
To solve numerically, we need an algorithm, an estimate of its computational cost, and a way to judge what its output means. The exact mathematical system may be sensitive to tiny changes in its data. Separately, an algorithm may introduce avoidable error while working on otherwise benign data. These two effects are called conditioning and stability and should not be conflated.
Throughout, is an real matrix unless stated otherwise. A nonsingular has a unique exact solution . In practice, explicitly forming is usually unnecessary: factor and solve triangular systems instead. A computed vector has residual , so
The residual measures how well the computed vector satisfies the supplied equations. It is also the exact perturbation to the right-hand side: . It is not itself the forward error .
Gaussian elimination and LU
Suppose elimination can be performed without row exchanges or zero pivots. Subtracting multiples of each pivot row from rows below it produces an upper triangular matrix . Collect the multipliers in a unit lower triangular matrix ; then . Solve by forward substitution and by backward substitution. For example,
With , forward substitution gives and back substitution gives . The factorization costs on the order of arithmetic operations for a dense matrix; each subsequent right-hand side costs on the order of operations. Therefore factor once when solving many systems with the same coefficient matrix.
A nonsingular matrix may still have a zero leading pivot: is its own inverse. Row exchanges handle this case. Partial pivoting selects a largest-magnitude available entry in the current column as the next pivot, exchanges rows, and continues. Its factorization is , where is the accumulated permutation. Solve , then . Pivoting also avoids dividing by an unnecessarily tiny pivot, although it does not guarantee small error for every matrix: element growth during elimination can still be large.
Counterexample mode
A nonsingular matrix need not have an LU factorization
Claim: every nonsingular matrix factors as with unit lower triangular and upper triangular. Take , with . If , the entry gives , and then the entry gives , a contradiction. For a nonsingular , an LU factorization exists exactly when the leading principal minors of orders are nonzero; exchanging rows gives .
A later pivot must carry the earlier multipliers
Worked example 2.1.1
(Partial pivoting with stored multipliers)
Consider partial pivoting in exact arithmetic for
In column 1 the largest magnitude is , so there is no exchange. The multipliers below the pivot are and . Subtracting each multiplier times row 1 from its row gives
In the remaining part of column 2, the entry is larger in magnitude than , so exchange rows 2 and 3. The active rows become and . At the same time exchange their already stored column-1 multipliers: now belongs to row 2 and to row 3. The next multiplier is ; subtracting half of row 2 from row 3 leaves . Thus
Check the row histories rather than just memorizing the rule:
Had we left the old multipliers in place, row 2 of the resulting product would be , not , so would fail. The multiplier records how its current row was changed by an earlier pivot row; it must travel with that row. Only the entries already stored in columns before the current pivot are swapped in ; swapping entire rows of the completed unit-triangular would move its diagonal ones and destroy its form.
More generally, at stage , select a largest-magnitude entry among rows in column . Exchange the corresponding active rows and the previously stored entries in columns , and update for the exchange matrix (start with ). Then divide each entry below the pivot by it and subtract that multiplier times the pivot row from the active row. If the largest available entry is zero, do not divide: the active column cannot supply a pivot. For a square matrix this signals singularity in exact elimination. These statements describe exact arithmetic; rounding and growth require their own analysis.
Common mistake
(Using b instead of Pb in the forward solve)
After the forward solve must use . For the matrix above and , solving and then gives and . The second row of is , not , so this vector is not a solution.
Quick check
(Use the factors above to solve . Why is the first right-hand side in the two triangular solves , rather than ?)
Write down first.
Solution · Answer
The swap gives . Forward substitution in gives ; back substitution in gives . The equation is what the factors represent, so would solve a different system unless .
How the triangular solves work
The compact notation , followed by , hides the order in which the unknowns become available. Let be lower triangular with every diagonal entry nonzero. Row contains only , so forward substitution calculates
An empty sum is zero, so the first step is . Inductively, all terms on the right have already been determined. Each row then has exactly one possible value of ; this proves both existence and uniqueness. For an upper triangular with nonzero diagonal, the last row is the starting point, and backward substitution similarly gives
A dense solve evaluates products in each triangular system, plus subtractions and at most divisions; a unit diagonal eliminates those divisions. Thus two solves cost , after the factorization is available. These counts concern arithmetic operations in exact arithmetic, not the cost of reading data or an accuracy guarantee. In floating-point arithmetic each solve also rounds.
Worked example 2.1.2
(Use a row permutation and two triangular solves)
Suppose elimination has already produced , where exchanges the first and third rows and
Since , the first right-hand side is , not . Forward substitution yields , , and . Starting with the last row of , we obtain , , and . Thus . We can check without constructing : and ; since is invertible, .
A zero diagonal entry makes the displayed division invalid and the triangular matrix singular. It does not mean that every corresponding system is inconsistent: has infinitely many solutions, while changing the right-hand side to gives none. Pivoting is a way to avoid a zero pivot when an appropriate row is available during factorization; it is not permission to divide by zero in a triangular solve.
Quick check
(Solve , then , for the matrices below.)
Solution · Answer
Forward substitution gives , , . Backward substitution gives , , . In particular, the right-hand side for the second solve is , not the original vector.
For a real symmetric positive definite matrix, a more specialized factorization is with lower triangular and positive diagonal. Positive definiteness means for every nonzero real . At each step the required diagonal square root is positive; for instance
Symmetry alone is not enough: is symmetric but cannot equal , since . For complex Hermitian positive definite matrices the transpose is replaced by the conjugate transpose.
History of an idea
Rounding error as a mathematical question
In his 1948 paper on rounding errors in matrix processes, Alan Turing studied errors in several methods for linear equations and matrix inversion, including elimination. His analysis illustrates that counting arithmetic operations and assessing the accuracy of their finite-precision results are separate questions. The present residual and condition-number discussion uses modern notation and does not attribute those definitions to that paper.
Condition numbers and error bounds
Use a vector norm and its induced matrix norm.
Definition 2.1.3
(Condition number)
Let be nonsingular, with a vector norm and its induced matrix norm fixed. The condition number of is .
Theorem 2.1.4
(Residual bound for the forward error)
Let be nonsingular, with , and let have residual . Then
Proof
(Residual identity and the bound on b)
Since , we have . Since , we have . Multiplying the two inequalities gives the stated bound.
The bound may overestimate the actual error, but shows why a small relative residual alone cannot promise a small relative forward error. For , , and , the exact solution is and . In the Euclidean norm the relative residual is approximately while the relative forward error is . Here .
For a perturbation to the right-hand side alone, gives and the same relative bound with in place of . A perturbation to needs an additional qualification: if in an induced matrix norm, then is invertible by the convergent Neumann series. Without a condition of this kind a small change can make a nearly singular matrix singular.
An algorithm is called backward stable when its computed answer is the exact solution to a nearby problem, with a controlled perturbation relative to the data under an explicitly stated error model. A backward-stable method can still have a large forward error when the problem is ill-conditioned. Conversely, a well-conditioned problem can be harmed by an unstable algorithm. The statement “the residual is small” needs a scale and does not by itself certify either assertion.
Nearly dependent equations
Worked example 2.1.5
(A perturbation that tends to zero but moves the solution)
Consider
Subtracting the first equation from the second gives , so the exact solution is . If the second entry of increases by , the new solution is . The data perturbation tends to zero with , but the solution change remains . This does not contradict continuity at a fixed nonsingular matrix: the matrices also vary and approach a singular matrix.
For interpreted as an approximate solution of the original system, . Direct calculation gives
The general residual bound permits relative forward error up to here; the actual error is 1, illustrating that a worst-case bound need not be sharp. At the relative residual is approximately , but the relative forward error is still 1. Partial pivoting cannot remove the sensitivity of this problem, even though it can improve the stability of elimination.
Iterative methods and stopping
For large sparse systems, factorization can create many new nonzero entries. An alternative is to split , with easy to solve against, and iterate
Assume is nonsingular so that the iteration is defined. When is nonsingular, the exact solution is a fixed point. The error satisfies and hence . Thus convergence for every starting vector holds precisely when , equivalently when its spectral radius . A convenient sufficient condition is in any induced norm. The spectral-radius condition is decisive even when a particular norm of exceeds one; transient growth can occur before eventual convergence.
For Jacobi iteration, write with diagonal, strict lower and strict upper parts and take . Every diagonal entry must be nonzero. For and ,
Starting at zero gives after one step. The iteration matrix has infinity norm , so it converges from every initial vector; the exact fixed point is . Gauss–Seidel uses newly computed components immediately: . Its iteration matrix is different, and one should not assume convergence merely because Jacobi converges without checking hypotheses.
A practical stopping test often uses for , alongside a maximum iteration count. A very small step alone can signal stagnation rather than accuracy. Conditioning determines how a residual translates to forward error, and finite precision eventually limits attainable accuracy.
Common mistake
(A small step is not a small error)
Consider the scalar equation with the splitting , , so and the exact solution is . From the first step is : the step has size , but the error is . In general , so when is close to a small step can hide a large error.
Practice with solutions
Quick check
(Factor as without pivoting and solve .)
Solution · Answer
and . Forward substitution gives ; back substitution gives .
Quick check
(For the data below, calculate the residual and the exact forward error.)
Solution · Answer
; the exact solution is , so .
Quick check
(For the Jacobi example below, show convergence in the infinity norm and calculate the second iterate from zero.)
Solution · Answer
has . Substitution into the update gives .
Joint perturbation of the matrix and the right-hand side
In practice the matrix and the data are rarely exact at the same time. We therefore ask how far the solution can move when both and are perturbed.
Setting. Let be nonsingular, , and , so . Suppose . Write where the matrix norm is induced by the same vector norm used below, and set , . Assume .
Theorem 2.1.6
(Joint perturbation of matrix and right-hand side)
Under these assumptions, is invertible and
Proof
(Neumann series, absorption and the bound on b)
Since , the earlier result makes invertible, so is invertible and is uniquely determined. Subtracting gives , so
Because , moving the last term left yields , and is exactly the hypothesis, so we may divide. Finally, gives . This is the only place where enters.
Proof X-ray
Where each assumption is used
The proof has three moves. First, gives , hence invertibility of and so the very existence of . Second, subtracting gives an equation in which also appears on the right through ; the term is absorbed on the left, and dividing by needs that factor to be positive. Third, is used once, to turn into ; the term with needs no such step because cancels.
The bound is an exact-arithmetic worst case. It says nothing about rounding, and the error measured in a particular instance may be much smaller.
Worked example 2.1.7
(A perturbation that attains the bound)
Use the -norm with , , , , and . Then , , , , and , so the bound is . Solving gives , so and the actual relative error is . The bound is attained.
Counterexample mode
Dropping the smallness hypothesis on the perturbation of A
A tempting claim is that whenever is small, the perturbed system has a nearby solution. Take , and in the -norm. Then is as small as we like, but and is singular. The system requires and has no solution. The repair is the theorem's hypothesis : smallness of must be measured against , not against .
Quick check
(Take , , and in the -norm. Compute the bound and the actual error.)
Compute , and first.
Solution · Answer
Here , , and the bound is . However, gives , so the actual error is . The two perturbations cancel, which a worst-case bound cannot detect.