Linear systems and trustworthy factorization
Solve by structured factorizations, choose pivots sensibly, and verify the result with residuals rather than explicit inverses.
On this page
The question for today
What you’ll understand
- Carry out elimination with row pivoting on a small system.
- Choose between LU, Cholesky, and QR using matrix structure.
- Separate factorization cost, triangular solves, and accuracy assessment.
Linear equations sit inside nearly every advanced numerical method: a Newton step, an implicit time update, a least-squares fit, or a discretized field equation. The notation A inverse times b describes the solution but usually suggests the wrong implementation. A factorization turns one expensive matrix analysis into simpler triangular or orthogonal operations, can be reused for several right-hand sides, and exposes assumptions worth checking. This lesson follows elimination numerically and connects a fast answer with the residual and conditioning information needed to decide whether that answer is trustworthy.
Elimination reorganizes the equations
Gaussian elimination removes entries below each pivot by subtracting multiples of a pivot row. Recording these multipliers produces a lower triangular factor, while the transformed equations form an upper triangular factor. Forward and backward substitution then solve the system. For a dense n by n matrix, factorization costs on the order of n cubed operations, while each additional triangular solve costs on the order of n squared. Reuse matters when the same operator acts on many data vectors.
A zero pivot can occur even for an invertible matrix, so row exchanges are necessary. Partial pivoting selects an entry with largest available magnitude in the current column. This avoids dividing by an unnecessarily tiny pivot and bounds the corresponding multipliers. The permutations must also be applied to the right-hand side and interpreted consistently in the factorization convention. Pivoting is not the same as reordering variables: a row swap reorders equations, while a column swap changes the ordering of unknowns.
Exploit structure without assuming it
A real symmetric positive-definite matrix admits a Cholesky factorization into a lower triangular factor times its transpose. This uses symmetry and positivity to reduce work and storage. Symmetric alone is not enough: indefinite matrices require different factorizations and often pivoting. A failed Cholesky operation can indicate a violated mathematical assumption, severe rounding effects, or a data bug. Silently replacing a negative square root by zero changes the problem rather than repairing the factorization.
For overdetermined least squares, QR uses an orthogonal factor and an upper triangular factor to solve without explicitly forming the normal equations. Forming A transpose A squares the two-norm condition number when A has full column rank, which can discard accuracy. If rank is uncertain, rank-revealing factorizations or the singular value decomposition provide more information. Choose a solver from the matrix's actual dimensions and structure, not from the presence of a familiar formula in a derivation.
Residuals close the computational loop
Partial-pivoted LU is effective for a wide range of problems, but its error analysis includes a growth factor describing how large intermediate entries become. Pathological matrices can exhibit large growth, so avoid an unconditional claim that pivoting solves every stability problem. After solving, calculate a scaled residual and estimate condition numbers when accuracy matters. A tiny backward error still permits a larger forward error for an ill-conditioned operator, exactly as in the earlier diagonal example.
Iterative refinement computes a residual, solves a correction equation using the available factors, and updates the answer. Computing the residual more accurately than the factorization can make refinement particularly useful, subject to conditioning and arithmetic assumptions. Sparse systems add another design constraint: fill-in can turn zeros into stored nonzeros during factorization. Reordering can reduce this cost without changing the mathematical solution. Distinguish such structural planning from numerical pivoting, and measure memory as well as arithmetic before choosing between direct and iterative approaches.
Work it through
A row swap reveals the safe first pivot
Solve 0.01x+y=1.01 and x+y=2 using partial pivoting.
The first column has magnitudes 0.01 and 1, so swap the two equations. The first pivot is now one, and the first equation reads x+y=2.
Use multiplier 0.01 to remove x from the second equation: subtracting 0.01 times the first row leaves 0.99y=1.01−0.02=0.99. Hence the upper triangular system has pivots 1 and 0.99.
Back substitution gives y=1 and x=2−1=1. In the convention PA=LU, the lower multiplier is 0.01 and the upper matrix has rows (1,1) and (0,0.99).
Substitute into the original unswapped equations: 0.01+1=1.01 and 1+1=2, so the exact-arithmetic residual is zero. Without the swap the first multiplier would be 100; the example illustrates avoiding unnecessary intermediate amplification, not an assertion that the unswapped route must fail in binary64.
Pivot selection is an algorithmic stability decision. Validation still uses the original equations and, for inexact data, an appropriate conditioning assessment.
The living notebook
Explore the model
Interactive lab · vectors
Small components and pivot choices
Rotate the displayed vector close to vertical and compare its tiny horizontal projection with its full magnitude. Why would dividing by that tiny component amplify uncertainty? The lab contains only one vector and its projections; it does not display matrix rows, choose pivots, or execute elimination.
- x component
- 1.393
- y component
- 0.975
- Magnitude
- 1.7
Playback traces a fixed vector and its projections. Angle and magnitude set the geometry; the moving marker does not change them. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forThe projection analogy motivates avoiding tiny divisors, while a factorization and residual establish what the solver actually did.
Pause & reason
Check your understanding
Your turn
Try it yourself
Solve 2x+y=5 and 4x+3y=11 by elimination. State the multiplier, the second pivot, and the residual of your solution.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Subtract twice the first equation from the second.
Compare with the solution
Using the first row gives multiplier two and leaves y=1, so the second pivot is one. Back substitution gives x=2. Substitution gives 2(2)+1=5 and 4(2)+3=11, hence residual zero in exact arithmetic. A partial-pivoting implementation would swap first, but this exact arithmetic exercise still has a valid nonsingular elimination.
Keep the idea
Take it with you
- Factor once and solve repeatedly instead of forming an inverse.
- Pivoting and structure determine which factorization is appropriate.
- Residuals, conditioning, growth, and memory cost all belong in a reliable solver assessment.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.