I have the following matrix:
$$
A|\underline{b} = \left (
\begin{array}{lll|l}
-3 & 2 & 1 & -1 \\
1 & 0 & -1 & -1 \\
4 & -2 & 2 & -2
\end{array}
\right )
$$
I have done the LU factorization with pivoting:
$$PA = LU$$
resolving the following system:
$$\begin{cases}
U\underline{x} = \underline{y} \quad (*) \\
L\underline{y} = P\underline{b} \quad (**)
\end{cases}$$
At the end of the last step of Gaussian Elimination (step 2), the situation is (apex denotes the step number):
$$
U|\underline{y} =
\left (
\begin{array}{lll|l}
4^{(0)} & -2^{(0)} & 2^{(0)} & -2^{(0)} \\
0 & \frac{1}{2}^{(1)} & -\frac{3}{2}^{(1)} & -\frac{1}{2}^{(1)} \\
0 & 0 & 4^{(2)} & -2^{(2)}
\end{array}
\right )
$$
$$
L|\underline{b} =
\left (
\begin{array}{ccc|c}
1 & 0 & 0 & -1 \\
\frac{1}{4} & 1 & 0 & -1 \\
-\frac{3}{4} & 1 & 1 & -2
\end{array}
\right )
$$
$$
P =
\left (
\begin{array}{ccc}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{array}
\right )
$$
1) At first point, I resolve the $(**)$ with the algorithm of forward substitution. From the following system:
note the I have written the $L$ matrix, and the permuted $\underline{b}$ on the basis of the Permutation matrix $P$ :
$$\left \{
\begin{array}{lcl}
x & = & -2 & \quad (1) \\
\frac{1}{4}x +y & = & -1 & \quad (2) \\
-\frac{3}{4}x +y + z & = & -1 & \quad (3)
\end{array}
\right.$$
I obtain the vector $\underline{y}$, solution of the system:
$$\underline{y} =
\left \{
\begin{array}{lcl}
x & = & -2 \\
y & = & -\frac{1}{2} \\
z & = & -2
\end{array}
\right .$$
2) Then, I resolve the $(*)$ with the algorithm of backward substitution. From the following system:
$$\left \{
\begin{array}{rcl}
4x -2y + 2z & = & -2 & \quad (1) \\
\frac{1}{2}y -\frac{3}{2}z & = & -\frac{1}{2} & \quad (2) \\
4z & = & -2 & \quad (3)
\end{array}
\right .$$
the vector $\underline{x}$ of solutions is:
$$\underline{x} =
\left \{
\begin{array}{lcl}
x & = & -\frac{3}{2} \\
y & = & -\frac{5}{2} \\
z & = & -\frac{1}{2}
\end{array}
\right .$$
To verify, If I compute $PA$ and $LU$ they are equal:
$$PA = LU \\
PA =
\left (
\begin{array}{ccc}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{array}
\right )
\cdot
\left (
\begin{array}{lll}
-3 & 2 & 1 \\
1 & 0 & -1 \\
4 & -2 & 2
\end{array}
\right )
=
\left (
\begin{array}{lll}
4 & -2 & 2 \\
1 & 0 & -1 \\
-3 & 2 & 1
\end{array}
\right )$$
$$LU =
\left (
\begin{array}{ccc}
1 & 0 & 0 \\
\frac{1}{4} & 1 & 0 \\
-\frac{3}{4} & 1 & 1
\end{array}
\right )
\cdot
\left (
\begin{array}{lll}
4^{(0)} & -2^{(0)} & 2^{(0)} \\
0 & \frac{1}{2}^{(1)} & -\frac{3}{2}^{(1)} \\
0 & 0 & 4^{(2)}
\end{array}
\right )
=
\left (
\begin{array}{lll}
4 & -2 & 2 \\
1 & 0 & -1 \\
-3 & 2 & 1
\end{array}
\right )$$
My question is:
- how can I compute the inverse matrix using LU factorization?
Please can you help me? Many thanks!
Best Answer
You have $$ A = LU \implies A^{-1} = U^{-1}L^{-1} \implies A^{-1}I = U^{-1}L^{-1}I. $$ Writing the canonical basis for $\mathbb R^n$ as $e_1, e_2, \ldots, e_n$, you have $$ \begin{pmatrix}A^{-1}e_1 &A^{-1}e_2 &\cdots &A^{-1}e_n \end{pmatrix} = \begin{pmatrix}U^{-1}L^{-1}e_1 &U^{-1}L^{-1}e_2 &\cdots &U^{-1}L^{-1}e_n \end{pmatrix}, $$ therefore you can solve $n$ linear systems of the form $LUx = e_i$ (forward + backward substitutions) and find the columns of $A^{-1}$. Remark that when solving $Ly = e_i$, the solution $y$ will satisfy $y_k = 0$ for $k = 1, \ldots, i-1$, thus simplifying the solution of the system.
Final comment: In general, knowing the inverse of a matrix $A$ is not crucial, but knowing its action $b \mapsto A^{-1}b$ is. Computing the $LU$ factorization allows fast evaluations of this map, as solving $Ax = b$ (i.e., $x = A^{-1} b$) has a cost of solving two linear systems with forward/backward substitution (total cost $\mathcal O(n^2)$). This is particularly helpful if you need to solve $M$ linear systems with $M$ different r.h.s. but with the same matrix $A$.