Problem with LU decomposition

Question

I have this matrix: $$ A =\begin{bmatrix}1 & -2 & 3\\ 2 & -4 & 5 \\ 1 & 1 & 2\end{bmatrix} $$ After I decomposit it, I get: $$ L = \begin{bmatrix}1 & 0 & 0\\1 & 1 & 0\\ 2 & 0 & 1 \end{bmatrix}\\ U = \begin{bmatrix} 1 & -2 & 3\\ 0 & 3 & -1\\ 0 & 0 & -1\end{bmatrix}\\ P = \begin{bmatrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\\\end{bmatrix} $$ Now I need to solve $Ax=b$ using: $b_1 = \begin{bmatrix}2\\0\\1 \end{bmatrix}$ and $b_2 = \begin{bmatrix}-1\\1\\-1 \end{bmatrix}$

But I'm stuck and don't know how to permute the vectors and every time I try I get a different result...

As I checked in Octave, the solution of $Ax=b_1$ is: $x_1 = \begin{bmatrix}-8\\1\\4 \end{bmatrix}$, but I can't get that solution.

Can you please explain me how to get this done? Thank you!

Answer 1

All of your work is correct for $A = PLU$.

Now, we want to solve $Ax = b$ for $b_1$ and $b_2$, so we use forward and back substitution as:

$$Ly = Pb, Ux = y$$

Forward substitution yields:

$$Ly = \begin{bmatrix}1 & 0 & 0\\1 & 1 & 0\\ 2 & 0 & 1 \end{bmatrix}\begin{bmatrix}y_1\\y_2\\y_3 \end{bmatrix}=Pb = \begin{bmatrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\\\end{bmatrix}\begin{bmatrix}2\\0\\1 \end{bmatrix} = \begin{bmatrix}2\\1\\0 \end{bmatrix} \implies y = \begin{bmatrix}2\\-1\\-4 \end{bmatrix}$$

Next, we use back substitution to solve $Ux = y$, yielding:

$$Ux = \begin{bmatrix} 1 & -2 & 3\\ 0 & 3 & -1\\ 0 & 0 & -1\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=y=\begin{bmatrix}2\\-1\\-4 \end{bmatrix} \implies \begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix} = \begin{bmatrix}-8\\1\\4 \end{bmatrix}$$

Rinse and repeat for $b_2$, yielding:

$$x_2 = \begin{bmatrix}6\\-1\\-3 \end{bmatrix}$$

Answer 2

Vectors $b_1$ and $b_2$ need to be multiplied by the permutation matrix $P$ and then just do a Gauss Elimination to solve $$ Lx = b\\ Ux = y $$

Answer 3

Vandenberghe seems to gives the algorithms given by the other two answers. Are you sure your reference material does not have such algorithms in the text?

http://www.seas.ucla.edu/~vandenbe/103/reader.pdf