solving_lu

Solving (LU)x = b

Definition

Given the LU Decomposition $\mathrm{A}=\mathrm{LU}$, solving $\mathrm{Ax}=\mathrm{b}$ reduces to two triangular solves, which is efficient for multiple right-hand sides.

Intuition

Introduce an intermediate vector $\mathrm{y}=\mathrm{Ux}$ so that $\mathrm{Ly}=\mathrm{b}$. Solving $\mathrm{Ly}=\mathrm{b}$ top-to-bottom (forward substitution) and then $\mathrm{Ux}=\mathrm{y}$ bottom-to-top (back substitution) each cost only $O(n^2)$, because every triangular system has a direct formula for each unknown.

Formal Description

Write $(\mathrm{LU})\mathrm{x}=\mathrm{L}(\mathrm{Ux})=\mathrm{b}$. Set $\mathrm{y}=\mathrm{Ux}$, then:

1. Forward substitution: Solve $\mathrm{Ly}=\mathrm{b}$ for $\mathrm{y}$ (starting from the first equation).
2. Back substitution: Solve $\mathrm{Ux}=\mathrm{y}$ for $\mathrm{x}$ (starting from the last equation).

Example. With

$$\mathrm{L}=\left(\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ -1& 1& 1\end{array}\right),\mathrm{U}=\left(\begin{array}{ccc}-3& 2& -1\\ 0& -2& 5\\ 0& 0& -2\end{array}\right),\mathrm{b}=\left(\begin{array}{c}-1\\ -7\\ -6\end{array}\right),$$

forward substitution on $\mathrm{Ly}=\mathrm{b}$ gives:

$$\begin{array}{rl}{y}_1& =-1,\\ y_2& =-7+2y_1=-9,\\ y_3& =-6+y_1-y_2=2.\end{array}$$

Back substitution on $\mathrm{Ux}=\mathrm{y}$ gives:

$$\begin{array}{rl}{x}_3& =-1,\\ x_2& =-\frac{1}{2}(-9-5x_3)=2,\\ x_1& =-\frac{1}{3}(-1-2x_2+x_3)=2.\end{array}$$

Hence $\mathrm{x}=(2,2,-1{)}^{\top }$.

Each triangular solve costs $O(n^2)$, far cheaper than re-running Gaussian elimination ($O(n^3)$) for each new $\mathrm{b}$.

Applications

Standard computational method for solving Systems of Linear Equations with a fixed coefficient matrix and multiple right-hand sides (e.g., finite-element solvers, iterative refinement).

Trade-offs

• Requires the LU factorisation to already be computed; if $\mathrm{A}$ changes, the $O(n^3)$ factorisation must be redone.
• Numerical accuracy depends on whether pivoting was used during the LU phase; without pivoting, forward/back substitution can amplify errors.
• Not applicable directly if $\mathrm{A}$ is singular; the system must be analysed for consistency first.

Links

• LU Decomposition
• Systems of Linear Equations