Editing Triangular matrix (section)

==Forward and back substitution==
<!-- Section is linked from several redirects (Back substitution etc.) – please update if you change the section title -->

A matrix equation in the form <math>L\mathbf{x} = \mathbf{b}</math> or <math>U\mathbf{x} = \mathbf{b}</math> is very easy to solve by an iterative process called '''forward substitution''' for lower triangular matrices and analogously '''back substitution''' for upper triangular matrices. The process is so called because for lower triangular matrices, one first computes <math>x_1</math>, then substitutes that ''forward'' into the ''next'' equation to solve for <math>x_2</math>, and repeats through to <math>x_n</math>. In an upper triangular matrix, one works ''backwards,'' first computing <math>x_n</math>, then substituting that ''back'' into the ''previous'' equation to solve for <math>x_{n-1}</math>, and repeating through <math>x_1</math>.

Notice that this does not require inverting the matrix.

===Forward substitution===
The matrix equation ''L'''''x''' = '''b''' can be written as a system of linear equations

:<math>\begin{matrix}
  \ell_{1,1} x_1 &   &                &   &        &   &                & = &    b_1 \\
  \ell_{2,1} x_1 & + & \ell_{2,2} x_2 &   &        &   &                & = &    b_2 \\
          \vdots &   &         \vdots &   & \ddots &   &                &   & \vdots \\
  \ell_{m,1} x_1 & + & \ell_{m,2} x_2 & + & \dotsb & + & \ell_{m,m} x_m & = &    b_m \\
\end{matrix}</math>

Observe that the first equation (<math>\ell_{1,1} x_1 = b_1</math>) only involves <math>x_1</math>, and thus one can solve for <math>x_1</math> directly. The second equation only involves <math>x_1</math> and <math>x_2</math>, and thus can be solved once one substitutes in the already solved value for <math>x_1</math>. Continuing in this way, the <math>k</math>-th equation only involves <math>x_1,\dots,x_k</math>, and one can solve for <math>x_k</math> using the previously solved values for <math>x_1,\dots,x_{k-1}</math>. The resulting formulas are:
:<math>\begin{align}
  x_1 &= \frac{b_1}{\ell_{1,1}}, \\
  x_2 &= \frac{b_2 - \ell_{2,1} x_1}{\ell_{2,2}}, \\
      &\ \ \vdots \\
  x_m &= \frac{b_m - \sum_{i=1}^{m-1} \ell_{m,i}x_i}{\ell_{m,m}}.
\end{align}</math>

A matrix equation with an upper triangular matrix ''U'' can be solved in an analogous way, only working backwards.

===Applications===
Forward substitution is used in financial [[Bootstrapping (finance)|bootstrapping]] to construct a [[yield curve]].