Tridiagonal matrix algorithm

Remarks

The proof is an induction on $i$. If $\abs{c'_{i-1}} < 1$, then $\abs{b_i - a_i c'_{i-1}} \ge \abs{b_i} - \abs{a_i} > \abs{c_i} \ge 0$, so the denominator is nonzero and $\abs{c'_i} < 1$. The forward sweep is Gaussian elimination without pivoting, which keeps the tridiagonal shape, and it computes the LU decomposition of $A$ with bidiagonal factors; the second sweep is back substitution. For diagonally dominant or symmetric positive definite matrices, the algorithm is also numerically stable. Without such a hypothesis a denominator can vanish even when $A$ is invertible: for $b_1 = 0$, $c_1 = 1$, $a_2 = 1$, $b_2 = 0$, the matrix $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is invertible but the first step divides by $0$. Example: the system $2x_1 - x_2 = 1$, $-x_1 + 2x_2 = 1$ is diagonally dominant by rows; the algorithm gives $c'_1 = -1/2$, $d'_1 = 1/2$, $d'_2 = (1 + 1/2)/(2 - 1/2) = 1$, so $x_2 = 1$ and $x_1 = 1/2 + 1/2 = 1$.

Going deeper

For a student

The algorithm is Gaussian elimination specialized to tridiagonal matrices, with no fill-in and no pivoting. Strict diagonal dominance is a simple condition that guarantees it never divides by zero. The finite difference matrix of $-u'' = f$, with rows $(-1, 2, -1)$, is only weakly diagonally dominant, but it is symmetric positive definite, and the algorithm works for it too. For tridiagonal systems that are not diagonally dominant, one uses Gaussian elimination with partial pivoting on the band instead.