= Solution
For a <tridiagonal matrix> with subdiagonal $a_i$, diagonal $b_i$ and superdiagonal $c_i$, <banded Gaussian elimination> introduces no fill beyond the original band. The <Thomas algorithm> uses
$$
p_1=b_1,\qquad\ell_i=a_i/p_{i-1},\qquad p_i=b_i-\ell_ic_{i-1}\quad(i=2,\ldots,n).
$$
Update the right side by $d_1=f_1$, $d_i=f_i-\ell_id_{i-1}$. Then <back substitution> gives
$$
\boxed{x_n=d_n/p_n,\qquad x_i=(d_i-c_ix_{i+1})/p_i\quad(i=n-1,\ldots,1).}
$$
Each row requires only a fixed number of arithmetic operations, so both work and storage are $\boxed{O(n)}$. The assumed absence of a need for pivoting includes nonzero elimination pivots $p_i$.
Back to article page
