Tridiagonal System of Equations

A linear system whose coefficient matrix has non-zero entries only on the main diagonal and the 2 adjacent diagonals.

\begin{aligned} b_1x_1 + c_1x_2 &= d_1 \\ a_2x_1 + b_2x_2 + c_2x_3 &= d_2 \\ &\ \vdots \\ a_{n-1}x_{n-2} + b_{n-1}x_{n-1} + c_{n-1}x_n &= d_{n-1} \\ a_nx_{n-1} + b_nx_n &= d_n \end{aligned}

Here:

$a_i$: subdiagonal entries
$b_i$: main diagonal entries
$c_i$: superdiagonal entries
$d_i$: right-hand-side entries

Its matrix form is

\begin{pmatrix} b_1 & c_1 & 0 & \cdots & 0 \\ a_2 & b_2 & c_2 & \ddots & \vdots \\ 0 & a_3 & b_3 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & c_{n-1} \\ 0 & \cdots & 0 & a_n & b_n \end{pmatrix} \begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix} = \begin{pmatrix}d_1\\d_2\\\vdots\\d_n\end{pmatrix}

The missing entries are zero. The first subdiagonal entry $a_1$ and the last superdiagonal entry $c_n$ are not used.

Crout Factorization

Crout factorization writes the coefficient matrix as

A=LU,

Here, $L$ is lower triangular and $U$ has unit diagonal. For a tridiagonal matrix,

L= \begin{pmatrix} \ell_1 & 0 & \cdots & 0 \\ a_2 & \ell_2 & \ddots & \vdots \\ 0 & a_3 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ell_n \end{pmatrix}, \qquad U= \begin{pmatrix} 1 & u_1 & 0 & \cdots & 0 \\ 0 & 1 & u_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & 1 & u_{n-1} \\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix}

The factor entries are computed by

\begin{aligned} \ell_1 &= b_1, & u_1 &= \frac{c_1}{\ell_1}, \\ \ell_i &= b_i-a_i u_{i-1}, & u_i &= \frac{c_i}{\ell_i}, \quad i=2,\ldots,n-1, \\ \ell_n &= b_n-a_n u_{n-1}. \end{aligned}

The subdiagonal entries of $L$ are the original entries $a_i$ . The factorization requires every pivot $\ell_i$ to be non-zero.

Triangular Solves

After $A=LU$ , solve $A\vec{x}=\vec{d}$ by solving $L\vec{y}=\vec{d}$ and then $U\vec{x}=\vec{y}$ .

\begin{aligned} y_1 &= \frac{d_1}{\ell_1}, \\ y_i &= \frac{d_i-a_i y_{i-1}}{\ell_i}, \quad i=2,\ldots,n. \end{aligned}

Back substitution uses

\begin{aligned} x_n &= y_n, \\ x_i &= y_i-u_i x_{i+1}, \quad i=n-1,n-2,\ldots,1. \end{aligned}

The factorization, forward substitution, and back substitution each require $O(n)$ operations. The factors and working vectors require $O(n)$ storage.

Applications

Tridiagonal systems occur when a discretized equation couples each unknown only to its immediate neighbours.

Finite-difference discretization of 1-dimensional boundary-value problems.
Cubic spline interpolation.
One-dimensional diffusion and heat equations.
Electrical ladder networks.

Worked Example

Solve the tridiagonal system using Crout factorization.

\begin{aligned} 2x_1-x_2 &= 1 \\ -x_1+2x_2-x_3 &= 0 \\ -x_2+2x_3-x_4 &= 0 \\ -x_3+2x_4 &= 1. \end{aligned}

Solution Reveal Hide

The entries are

a_2=a_3=a_4=-1, \quad b_1=b_2=b_3=b_4=2, \quad c_1=c_2=c_3=-1, \quad \vec{d}=(1,0,0,1)^T

Crout factorization gives

\begin{aligned} \ell_1 &= 2, & u_1 &= -\frac12, \\ \ell_2 &= 2-(-1)\left(-\frac12\right)=\frac32, & u_2 &= -\frac23, \\ \ell_3 &= 2-(-1)\left(-\frac23\right)=\frac43, & u_3 &= -\frac34, \\ \ell_4 &= 2-(-1)\left(-\frac34\right)=\frac54. \end{aligned}

Forward substitution gives

\begin{aligned} y_1 &= \frac12, \\ y_2 &= \frac{0-(-1)(1/2)}{3/2}=\frac13, \\ y_3 &= \frac{0-(-1)(1/3)}{4/3}=\frac14, \\ y_4 &= \frac{1-(-1)(1/4)}{5/4}=1. \end{aligned}

Back substitution gives

\begin{aligned} x_4 &= 1, \\ x_3 &= \frac14-\left(-\frac34\right)(1)=1, \\ x_2 &= \frac13-\left(-\frac23\right)(1)=1, \\ x_1 &= \frac12-\left(-\frac12\right)(1)=1. \end{aligned}

Therefore,

\vec{x}=(1,1,1,1)^T