Past exam of the numerical linear algebra and approximation course of the University of Oxford / 2008 / 2 / a

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 usesUpdate the right side by $d_1=f_1$, $d_i=f_i-{\ell }_i{d}_{i-1}$. Then back substitution givesEach 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$.