Tridiagonal matrix algorithm/Derivation

The derivation of the Tridiagonal matrix algorithm involves manually performing some specialized Gaussian elimination in a generic manner.

Suppose that the unknowns are $x_{1},\ldots ,x_{n}$, and that the equations to be solved are:

${\begin{array}{lcl}b_{1}x_{1}+c_{1}x_{2}=d_{1}\qquad &;&\ i=1\\a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i}\qquad &;&\ i=2,\ldots ,n-1\\a_{n}x_{n-1}+b_{n}x_{n}=d_{n}\qquad &;&\ i=n\\\end{array}}\,$

Consider modifying the second ($i=2$) equation with the first equation as follows:

$({\mbox{equation 2}})\cdot b_{1}-({\mbox{equation 1}})\cdot a_{2}$

which would give:

$(a_{2}x_{1}+b_{2}x_{2}+c_{2}x_{3})b_{1}-(b_{1}x_{1}+c_{1}x_{2})a_{2}=d_{2}b_{1}-d_{1}a_{2}\,$

$(b_{2}b_{1}-c_{1}a_{2})x_{2}+c_{2}b_{1}x_{3}=d_{2}b_{1}-d_{1}a_{2}\,$

and the effect is that $x_{1}$ has been eliminated from the second equation. Using a similar tactic with the modified second equation on the third equation yields:

$(a_{3}x_{2}+b_{3}x_{3}+c_{3}x_{4})(b_{2}b_{1}-c_{1}a_{2})-((b_{2}b_{1}-c_{1}a_{2})x_{2}+c_{2}b_{1}x_{3})a_{3}=d_{3}(b_{2}b_{1}-c_{1}a_{2})-(d_{2}b_{1}-d_{1}a_{2})a_{3}\,$

$(b_{3}(b_{2}b_{1}-c_{1}a_{2})-c_{2}b_{1}a_{3})x_{3}+c_{3}(b_{2}b_{1}-c_{1}a_{2})x_{4}=d_{3}(b_{2}b_{1}-c_{1}a_{2})-(d_{2}b_{1}-d_{1}a_{2})a_{3}\,$

This time $x_{2}$ was eliminated. If this procedure is repeated until the $n^{th}$ row; the (modified) $n^{th}$ equation will involve only one unknown, $x_{n}$. This may be solved for and then used to solve the $(n-1)^{th}$ equation, and so on until all of the unknowns are solved for.

Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may instead be defined recursively:

${\tilde {a}}_{i}=0\,$

${\tilde {b}}_{1}=b_{1}\,$

${\tilde {b}}_{i}=b_{i}{\tilde {b}}_{i-1}-{\tilde {c}}_{i-1}a_{i}\,$

${\tilde {c}}_{1}=c_{1}\,$

${\tilde {c}}_{i}=c_{i}{\tilde {b}}_{i-1}\,$

${\tilde {d}}_{1}=d_{1}\,$

${\tilde {d}}_{i}=d_{i}{\tilde {b}}_{i-1}-{\tilde {d}}_{i-1}a_{i}\,$

To further hasten the solution process, ${\tilde {b}}_{i}$ may be divided out (if there's no division by zero risk), the newer modified coefficients notated with an asterisk will be:

$a'_{i}=0\,$

$b'_{i}=1\,$

$c'_{1}={\frac {c_{1}}{b_{1}}}\,$

$c'_{i}={\frac {c_{i}}{b_{i}-c'_{i-1}a_{i}}}\,$

$d'_{1}={\frac {d_{1}}{b_{1}}}\,$

$d'_{i}={\frac {d_{i}-d'_{i-1}a_{i}}{b_{i}-c'_{i-1}a_{i}}}\,$

This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:

${\begin{array}{lcl}x_{i}+c'_{i}x_{i+1}=d'_{i}\qquad &;&\ i=1,\ldots ,n-1\\x_{n}=d'_{n}\qquad &;&\ i=n\\\end{array}}\,$

The last equation involves only one unknown. Solving it in turn reduces the next last equation to one unknown, so that this backward substitution can be used to find all of the unknowns:

$x_{n}=d'_{n}\,$

$x_{i}=d'_{i}-c'_{i}x_{i+1}\qquad ;\ i=n-1,n-2,\ldots ,1$