Motivation
A linear system appears when a model is discretized, coefficients are fitted, or several constraints must be satisfied at once. The equations alone do not tell us whether a computed vector is accurate. We need both a method for solving them and a way to judge sensitivity to perturbations. In this unit is a real square matrix, and vector and matrix norms are compatible unless stated otherwise.
Elimination and pivoting
Gaussian elimination replaces a system by an equivalent upper triangular system in exact arithmetic. At column , subtract a multiple of row from each lower row to eliminate its column- entry. Once the triangular system is obtained, back substitution starts with its last equation and proceeds upward. Division requires nonzero pivots. If a pivot is zero, exchanging rows may allow the process to continue even when the original matrix is nonsingular.
Worked example 3.1.1
(A zero pivot)
For instance,
has a zero first pivot in its original ordering. Exchange the equations: , . Back substitution gives , . A zero pivot in a particular ordering therefore does not by itself imply singularity.
Definition 3.1.2
(Partial pivoting and )
Partial pivoting chooses, among the rows at or below the current pivot, an entry of largest absolute value in the current column and moves its row to the pivot position. If all such entries are zero, the matrix is singular; this cannot occur for a nonsingular square matrix. With row interchanges recorded by a permutation matrix , elimination yields , where is unit lower triangular and upper triangular. Solve , then . For multiple right-hand sides, one factorization can be reused.
Why choose a large pivot? The multipliers have magnitude at most one under partial pivoting, reducing one source of error amplification. This is not a universal guarantee of tiny error: entries in the evolving matrix can still grow, and an ill-conditioned problem remains sensitive. Partial pivoting is a practical safeguard, not a cure for every conditioning problem.
Residual and error
Definition 3.1.3
(Residual and condition number)
Let be nonsingular, the exact solution of , and a computed vector. Its residual is . For a vector norm and a compatible matrix norm, the condition number of is .
Because ,
Hence . If , then gives the relative bound
The norm used in the condition number must match the norm used for the residual and error. The bound can be pessimistic, but it correctly warns that a small relative residual need not imply a small relative error when is large. It assumes exact evaluation of the residual; a rounded computed residual itself has error.
Worked example 3.1.4
(Residual and error)
As a concrete counterexample, let , and . The exact solution is and . In the infinity norm the relative residual is , but the relative error is . Here , and the bound permits exactly this outcome. The second equation is satisfied almost in absolute terms while its solution component is entirely wrong.
Data perturbations
Suppose is fixed, changes to , and is the new solution. Subtraction gives . Taking norms and using proves
provided . This worst-case bound allows perturbations in any direction; it does not assert that every perturbation is amplified by the full condition number. Perturbing as well requires a different bound and a smallness condition ensuring that the perturbed matrix remains nonsingular.
Scaling affects numerical interpretation. Changing units changes the coordinates and may change a normwise condition number; it does not magically add information to the data. Examine the actual measurement uncertainty and the variables of interest rather than quoting a condition number without its norm and scaling.
A second elimination calculation
Worked example 3.1.5
(Partial pivoting on a system)
Consider and . Partial pivoting exchanges the rows first because . The multiplier in the second row is , producing the triangular system and . Back substitution yields and . The corresponding factors are
Multiplying gives , which checks both the multiplier and the row ordering. One must also apply the permutation to the right-hand side; solving instead of would solve a different system. Explicitly forming is unnecessary for solving this system: triangular solves use the factorization directly. The inverse remains useful in analysis, where its norm describes sensitivity.
For a singular example, has dependent rows. With , infinitely many solutions satisfy ; with , the equations contradict each other. Thus singularity can mean either nonuniqueness or inconsistency, depending on the right-hand side. No finite ordinary inverse-based condition number exists for a singular matrix.
Norms and a perturbation in the matrix
Proposition 3.1.6
(Induced norm)
The induced matrix norm is . It implies . For the infinity vector norm, this induced norm equals the maximum absolute row sum. The condition number is at least one for a nonsingular matrix because . A condition number of one is best in this normwise sense, although other error measures and componentwise sensitivities may tell a different story.
Now suppose the matrix and right-hand side both change. Let , where and is nonsingular. Rearrangement gives
Proposition 3.1.7
(Perturbed system)
If , then is invertible and . Thus the perturbed system has a unique solution and, for ,
Proof
(Neumann series, then the error identity)
Put , so . Since , the partial sums of form a Cauchy sequence; the series converges to some with . Telescoping gives , and the same holds with the factors in the other order, so . Hence is a product of invertible matrices, and the perturbed system has a unique solution .
Applying to the rearranged identity gives
Since , also . Divide by and use in the form . Factoring out gives the stated bound.
Proof X-ray
Which hypothesis keeps the perturbed problem solvable
The argument has two logically separate jobs. The condition makes the Neumann series converge, which first establishes that the perturbed system has a unique solution. Only after this existence step may we multiply the error identity by the inverse and estimate its norm. The additional assumption is needed for the relative-error ratios, rather than for invertibility. A large condition number concerns amplification of admissible data errors; it does not invalidate the algebraic solution identity.
The denominator matters: if the perturbation can reach a singular matrix, no uniform finite bound of this form follows. The condition is sufficient, not necessary; some larger perturbations still leave the matrix invertible. This calculation also explains why matrix uncertainty matters even if the right-hand side is known exactly.
Counterexample mode
A tiny relative perturbation can reach a singular matrix
It is tempting to replace the hypothesis by “the relative perturbation of the matrix is small”. Take and . In the infinity norm , yet is singular, and has no solution. The theorem's hypothesis fails exactly: has norm one. The correct smallness condition is , which follows from because .
A scaling example
Worked example 3.1.8
(Scaling)
Let and . The solution is and . Multiplying the first equation by changes the displayed matrix to the identity, whose infinity-norm condition number is one. This does not alter the exact solution, but it changes the meaning of an equally sized absolute perturbation to the two displayed right-hand-side components. If uncertainty is known in the original physical units, it must be transformed along with the equations before comparing bounds. Scaling may improve numerical behavior while the original measurements still constrain accuracy.
Backward error for a computed solution
The residual also admits a backward interpretation. Given and , the same vector is the exact solution of . Thus , when , measures the size of a right-hand-side perturbation that explains the computed result. It need not be the smallest backward error if changes to are also allowed. The distinction matters when the entries of and have different uncertainties or units.
Worked example 3.1.9
(Backward and forward error of a computed vector)
For example, let , , and . Then and . In the infinity norm the right-hand-side backward error is . The exact solution is , so the relative infinity-norm forward error is . Because and , the condition number is and the residual bound gives at most , consistent with the observed error. A bound does not have to be attained to be useful.
Why elimination preserves the system
Swapping equations, multiplying an equation by a nonzero scalar, and adding a multiple of one equation to another are reversible row operations. Applying the same operation to the coefficient matrix and right-hand side preserves the solution set. Each operation corresponds to multiplication by an invertible elementary matrix. A product of such matrices turns into ; rearranging this product, with row swaps recorded, leads to a factorization of the form . The order matters: row exchanges made after earlier elimination steps must be reflected in the stored multipliers when constructing .
A triangular system with nonzero diagonal has a unique solution. The last equation determines the last unknown, and induction determines each preceding unknown. If a zero diagonal is encountered, the elementary back-substitution formula cannot divide by it; the resulting system must instead be examined for consistency and free variables. A software routine should report singularity or numerical difficulty, not quietly divide by a tiny or zero pivot and present the result as reliable.
Conditioning is not the same as a poor algorithm
For , the problem is perfectly conditioned in any induced norm. An algorithm that intentionally returns nevertheless has a large error, showing that good conditioning alone says nothing about an arbitrary method. Conversely, a stable solve of an ill-conditioned system can produce an answer with a small backward error and a much larger forward error. The latter may be unavoidable given uncertain input data. This separation is useful when deciding whether to improve the algorithm, obtain more accurate measurements, or change the problem formulation.
The last exercise below uses the diagonal matrix so that both the error direction and its amplification can be seen directly. The second coordinate of is small, and an absolute perturbation of is a tenth of that coordinate. Dividing by the corresponding diagonal coefficient produces a solution change of . The normwise relative residual instead compares with the largest component of , namely one. Consequently the normwise measure can obscure a large relative perturbation in an individual component. When components have different scales, a componentwise analysis may better reflect the underlying measurement model. Whichever scale is chosen, state clearly how it corresponds to the actual data.
Common mistakes
Common mistake
(Forgetting to permute the right-hand side)
With the factors of the pivoted example, solving instead of gives and then . This vector solves , : the system with its right-hand side left in the original order while the rows of were exchanged. The correct solution is obtained only after is permuted to .
Common mistake
(Dividing by a tiny pivot without exchanging rows)
Exact elimination may be valid while its floating-point version fails. For with , the exact solution has both components within of one. Without a row exchange, binary double precision uses the multiplier , rounds and both to , obtains , and then . Partial pivoting exchanges the rows first, the multiplier becomes , and both components come out as one to working accuracy.
Summary
Elimination and back substitution solve a nonsingular square system in exact arithmetic; partial pivoting selects a large available pivot and records row exchanges in . A reusable factorization requires applying the same permutation to each right-hand side. In finite arithmetic, a small pivot, intermediate growth, and rounding require attention even when exact elimination is valid.
The residual tells us how closely a candidate satisfies the stated equations and provides a right-hand-side backward error. The condition number bounds how strongly perturbations can affect the solution in a specified norm. A small residual together with a large condition number may still allow substantial forward error. The condition bound is a worst-case statement, not a prediction that every error direction is amplified equally.
When comparing two systems, record units and scaling as well as the matrix and norm. Rescaling an equation changes the normwise description of perturbations; it does not alter the physical measurements that produced the data. For uncertain data, interpret each numerical result in light of those uncertainties before attaching significance to its printed digits.
Exercises
Quick check
(Solve , by elimination and check the residual.)
Eliminate from the second equation.
Solution · Answer
Subtract twice the first equation from the second: , then . Both equations hold, so .
Quick check
(For , calculate .)
Compute the row sums of and of .
Solution · Answer
The infinity norm is the largest absolute row sum: and , so .
Quick check
(A computed vector has residual zero in exact arithmetic for nonsingular . What can be concluded?)
Use .
Solution · Answer
Since and is nonsingular, . This conclusion assumes an exact zero residual; a rounded residual reported as zero does not establish it.
Quick check
(For and , consider . Compute the exact solution, residual, relative infinity-norm residual and relative infinity-norm error. Compare the error with the condition-number bound, and state why the residual is a backward error for a perturbation of alone.)
Compute first.
Solution · Answer
The exact solution is . We have , so . As , the relative residual is . The error is , so its relative infinity norm is . Since and , the condition-number bound is and is attained here. Finally, , so exactly solves the system with right-hand side perturbed by . This backward statement is valid even though the forward error is one hundred times the relative residual.