 Solution

ID: past-exam-of-the-numerical-linear-algebra-and-approximation-course-of-the-university-of-oxford/2008/2/a/solution

For a tridiagonal matrix with subdiagonal

a_{i}

b_{i}

and superdiagonal

c_{i}

, banded Gaussian elimination introduces no fill beyond the original band. The Thomas algorithm uses

p_{1} = b_{1}, ℓ_{i} = a_{i} / p_{i - 1}, p_{i} = b_{i} - ℓ_{i} c_{i - 1} (i = 2, \dots, n) .

Update the right side by

d_{1} = f_{1}

d_{i} = f_{i} - ℓ_{i} d_{i - 1}

x_{n} = d_{n} / p_{n}, x_{i} = (d_{i} - c_{i} x_{i + 1}) / p_{i} (i = n - 1, \dots, 1) .

Each row requires only a fixed number of arithmetic operations, so both work and storage are

O (n)

. The assumed absence of a need for pivoting includes nonzero elimination pivots

p_{i}

 New to topics? Read the docs here!