LU factorization for finding inverse matrix

2.2k Views Asked by At

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!

1

There are 1 best solutions below

1
On 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$.