Content deleted Content added
Tags: Reverted section blanking |
m Reverted edits by 219.240.68.114 (talk) (HG) (3.4.10) |
||
Line 56:
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===
| |||