Why exploit the pattern?
In a system , a tridiagonal matrix couples each unknown only to its immediate neighbors. Such systems arise, for example, in the curvature equations of a natural cubic spline. General elimination is still possible, but storing all entries hides the pattern: in exact arithmetic, eliminating one row changes only the next row. We can store and process three diagonals instead.
Write for the subdiagonal entry in row (), for the diagonal, and for the superdiagonal (). Thus the equations are
with the nonexistent first and last terms omitted. Assume . Our derivation uses exact arithmetic; a nonzero pivot makes the formulas legal, but does not by itself certify an accurate floating-point result.
Eliminate one neighbor at a time
Set and . For , provided , define
The transformed row is , with no superdiagonal term in the final row. If every is nonzero, back substitution gives
Each step has a fixed number of arithmetic operations. For another right-hand side with the same matrix, retain the multipliers and pivots, recompute only , and back substitute. The proposition below makes both the shape of the transformed rows and the operation count precise.
Proposition 3.3.1
(Elimination stays inside the band)
Let be tridiagonal and suppose are nonzero. After the rows have been processed in order, row of the transformed system is (with no term in the last row), and no entry outside the three diagonals has become nonzero. If also , factorization, the forward sweep and back substitution together use exactly arithmetic operations, and the data occupy storage.
Proof
(Induction on the processed rows)
For the claim is the first equation with , . Assume it holds for row . That row then contains only and , in columns and , and the untouched row contains in columns . Subtracting times row from row cancels the entry in column , replaces by and by , and leaves column alone, because row has no entry there. No other row is touched. This proves the claimed form of row , and no off-band entry is ever created.
For the count, each of the elimination steps uses one division for , one multiplication and one subtraction for , and the same for : five operations. Back substitution uses one division for and one multiplication, one subtraction and one division for each of the other unknowns. The total is . Only the vectors and the computed are stored.
The same computation can be read as a factorization, which is the form in which software stores it.
Concept lensStructural
Elimination as a product of two bidiagonal matrices
Let be unit lower bidiagonal with subdiagonal entries , and let be upper bidiagonal with diagonal and superdiagonal . Multiplying out,
so . The forward sweep for is exactly the solution of , and back substitution solves . Reusing the factorization for a new right-hand side therefore means two bidiagonal solves, and because .
Theorem 3.3.2
(When the pivots exist)
Let be the leading principal submatrix, and set , . If are nonzero, the elimination pivots up to are defined and . If in addition , all pivots are nonzero and the algorithm gives the unique solution. In particular this holds for a real symmetric positive definite matrix.
Proof
(Determinant recurrence and inherited definiteness)
Expanding the tridiagonal determinant along its last row gives for , with . Division by and induction yield . The row operations are reversible whenever their pivots are nonzero; the final triangular system then has a unique solution. If is symmetric positive definite, every is positive definite: extend a nonzero vector in by zeros and apply the definition. Its determinant is positive, for instance by the spectral theorem, so every pivot exists and is positive.
Proof X-ray
Where each determinant hypothesis is spent
The key move is to notice that the pivot recurrence and the determinant recurrence are the same three-term relation: if , then
The hypothesis is used exactly once, to make nonzero so that step may divide by it. Hence are what the factorization needs, while is needed only for the first division of back substitution. The formulas telescope to . For the positive definite case the only extra idea is that restricting the quadratic form to vectors supported on the first coordinates gives the form of , so positivity is inherited by every leading block at once.
Symmetry gives more structure. Put and let have unit diagonal and subdiagonal . If the preceding pivots are nonzero, with , the recurrence reads
For a symmetric positive definite matrix all . Equivalently for the lower bidiagonal . Positive pivots are a property proved from positive definiteness; they should not be assumed for an arbitrary symmetric matrix.
A complete calculation
Worked example 3.3.3
(Three coupled unknowns)
Solve
The pivots are , , and . The multipliers are , ; hence , , and . Back substitution yields , , and . Direct multiplication confirms .
The matrix is positive definite: for nonzero ,
Thus its positive pivots were guaranteed before we calculated them. The calculation also shows what to reuse if a new arrives: the three pivots and two multipliers depend on , not on .
Worked example 3.3.4
(The factors of the same matrix)
The matrix of the previous example is symmetric, with . Its multipliers give , , and its pivots give . Multiplying out entry by entry:
This reproduces . As a further check, , which agrees with the leading determinants , , and with .
Worked example 3.3.5
(Edge case: all pivots defined, last pivot zero)
Take . Here , so the theorem says is defined, and indeed , . The factorization with , exists, but back substitution fails at its first step . For the transformed last equation is and there are infinitely many solutions; for it is and there are none. The condition in the theorem is exactly what excludes this case.
What the structure does not promise
Counterexample mode
A nonsingular matrix can have a zero first pivot
The tridiagonal matrix has determinant , so its system has a unique solution for every right-hand side. Yet , and the displayed recurrence cannot begin. Exchanging the two rows permits elimination. In larger tridiagonal systems, row pivoting can create extra fill and needs an algorithm that accounts for it. Nonsingularity alone does not justify unpivoted elimination.
Common mistake
(Symmetric does not mean positive pivots)
The recurrence looks as if it should keep the pivots positive, but it does not. For one gets and . The factorization exists, but has a negative entry, so and the bidiagonal factor are not real. Positive pivots, and hence , follow from positive definiteness, which must be checked separately.
Even when all exact pivots exist, a tiny pivot can magnify rounding errors. Positive definiteness prevents zero pivots in exact arithmetic but does not guarantee a small condition number. For example, is positive definite for , yet its two-norm condition number is when . A small residual is therefore best interpreted with a conditioning estimate. Linear complexity is a statement about work, not an accuracy certificate; overflow, underflow, input error and arithmetic rounding still matter.
Practice with solutions
Quick check
(For diagonal and sub- and superdiagonal entries , find the pivots. Explain why they are positive without relying only on the calculation.)
Write the quadratic form as a sum of squares.
Solution · Answer
, , and . The quadratic form is , which is positive for nonzero . Positive definiteness therefore guarantees positive pivots.
Quick check
(Solve the system in the first worked example again with , reusing its factorization.)
Only the forward sweep for and back substitution need to be repeated.
Solution · Answer
With and , the new transformed right-hand side is . Back substitution gives , , . Multiplication by returns .
Quick check
(A student says that every nonsingular tridiagonal matrix has nonzero leading principal determinants. Explain the error and say what stronger condition above suffices.)
Look at the counterexample in the previous section.
Solution · Answer
The swap matrix in the counterexample has determinant but first leading determinant zero. Nonsingularity says only . Symmetric positive definiteness is sufficient because every leading principal submatrix is positive definite and has positive determinant.