Linear Programming - LUP Decomposition

• Apr 9th 2008, 07:58 PM
tcpipmen
Linear Programming - LUP Decomposition

1 5 4 | x1 = 12
2 0 3 | x2 = 9
5 8 2 | x3 = 5

by using an LUP decomposition.
I really want to see step by step solution to get L, U and P.

regards,
• Apr 9th 2008, 09:36 PM
TheEmptySet
Quote:

Originally Posted by tcpipmen

1 5 4 | x1 = 12
2 0 3 | x2 = 9
5 8 2 | x3 = 5

by using an LUP decomposition.
I really want to see step by step solution to get L, U and P.

regards,

we will find the corrisponding elementry matrix and its inverse for each step to find and upper triangle matrix.

$\begin{bmatrix}
1 && 5 && 4 \\
2 && 0 && 3 \\
5 && 8 && 2 \\
\end{bmatrix} \mbox{ } E_1= \begin{bmatrix}
1 && 0 && 0 \\
-2 && 1 && 0 \\
0 && 0 && 1 \\
\end{bmatrix} \mbox{ } E_1^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
0 && 0 && 1 \\
\end{bmatrix}
$

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
5 && 8 && 2 \\
\end{bmatrix} \mbox{ } E_2= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
-5 && 0 && 1 \\
\end{bmatrix} \mbox{ } E_2^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
5 && 0 && 1 \\
\end{bmatrix}
$

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && -17 && -18 \\
\end{bmatrix} \mbox{ } E_3= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
0 && -1.7 && 1 \\
\end{bmatrix} \mbox{ } E_3^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
0 && 1.7 && 1 \\
\end{bmatrix}
$

So fiinally we have the upper triangle matrix

$U= \begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && 0 && -9.5\\
\end{bmatrix}$

To get L we multiply

$L= E_1^{-1}E_2^{-1}E_3^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
5 && 1.7 && 1 \\
\end{bmatrix}$
• Apr 10th 2008, 03:52 AM
Soroban
Hello, tcpipmen!

Quote:

Solve the system by using an LUP decomposition.

. . . $\begin{bmatrix}1 & 5 & 4 \\ 2 & 0 & 3 \\ 5 & 8 & 2\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} \;=\;\begin{bmatrix}12 \\ 9 \\ 5 \end{bmatrix}$

I'm not familiar with "LUP decomposition".
. . How about "Gaussian elimination"?

We have: . $\left[\begin{array}{ccc|c}1 & 5 & 4 & 12 \\ 2 & 0 & 3 & 9 \\ 5 & 8 & 2 & 5 \end{array}\right]$

$\begin{array}{c}\\ R_2-2R_1 \\ R_3-5R_1\end{array}\left[\begin{array}{ccc|c}1&5&4&12 \\ 0 & \text{-}10 & \text{-}5 & \text{-}15 \\ 0 & \text{-}17 & \text{-}18 & \text{-}55\end{array}\right]$

. . $\begin{array}{c}\\\text{-}\frac{1}{10}\!\cdot\!R_2 \\ \text{-}1\!\cdot\!R_3\end{array}\left[\begin{array}{ccc|c}1&5&4&12 \\ 0&1&\frac{1}{2} & \frac{3}{2} \\ 0 &17&18&55\end{array}\right]$

$\begin{array}{c}R_1-5R_2 \\ \\ R_3-17R_2\end{array}\left[\begin{array}{ccc|c}1 & 0 & \frac{3}{2} & \frac{9}{2} \\ 0 & 1 & \frac{1}{2} & \frac{3}{2} \\ 0 & 0 & \frac{19}{2} & \frac{59}{2} \end{array}\right]$

. . . $\begin{array}{c}\\ \\ \frac{2}{19}R_3\end{array}\left[\begin{array}{ccc|c}1 & 0 & \frac{3}{2} & \frac{9}{2} \\ 0 & 1 & \frac{1}{2} & \frac{3}{2} \\ 0 & 0 & 1 & \frac{59}{19}\end{array}\right]$

$\begin{array}{c}R_1-\frac{3}{2}R_3 \\ R_2-\frac{1}{2}R_3 \\ \\ \end{array}\left[\begin{array}{ccc|c}1 & 0 & 0 & \text{-}\frac{3}{19} \\
0 & 1 & 0 & \text{-}\frac{1}{19} \\ 0 & 0 & 1 & \frac{59}{19}\end{array}\right]$

Therefore: . $\left[\begin{array}{c}x_1\\ \\[-4mm] x_2\\ \\[-4mm]x_3 \end{array}\right] \;=\;\left[\begin{array}{c}\text{-}\frac{3}{19} \\ \\[-4mm]\text{-}\frac{1}{19} \\ \\[-4mm] \frac{59}{19}\end{array}\right]$

• Apr 10th 2008, 01:10 PM
TheEmptySet
I thought you just wanted the factorization :(
Quote:

Originally Posted by TheEmptySet
we will find the corrisponding elementry matrix and its inverse for each step to find and upper triangle matrix.

$\begin{bmatrix}
1 && 5 && 4 \\
2 && 0 && 3 \\
5 && 8 && 2 \\
\end{bmatrix} \mbox{ } E_1= \begin{bmatrix}
1 && 0 && 0 \\
-2 && 1 && 0 \\
0 && 0 && 1 \\
\end{bmatrix} \mbox{ } E_1^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
0 && 0 && 1 \\
\end{bmatrix}
$

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
5 && 8 && 2 \\
\end{bmatrix} \mbox{ } E_2= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
-5 && 0 && 1 \\
\end{bmatrix} \mbox{ } E_2^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
5 && 0 && 1 \\
\end{bmatrix}
$

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && -17 && -18 \\
\end{bmatrix} \mbox{ } E_3= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
0 && -1.7 && 1 \\
\end{bmatrix} \mbox{ } E_3^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
0 && 1 && 0 \\
0 && 1.7 && 1 \\
\end{bmatrix}
$

So fiinally we have the upper triangle matrix

$U= \begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && 0 && -9.5\\
\end{bmatrix}$

To get L we multiply

$L= E_1^{-1}E_2^{-1}E_3^{-1}= \begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
5 && 1.7 && 1 \\
\end{bmatrix}$

Sorry I will finish the problem :)

$\begin{bmatrix}
1 && 5 && 4 \\
2 && 0 && 3 \\
5 && 8 && 2 \\
\end{bmatrix} \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix} = \begin{bmatrix}
12 \\
9 \\
5 \\
\end{bmatrix}
$

replace with our factoriztion

$\begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
5 && 1.7 && 1 \\
\end{bmatrix} \begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && 0 && -9.5\\
\end{bmatrix} \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix} = \begin{bmatrix}
12 \\
9 \\
5 \\
\end{bmatrix}
$

Lets define this matrix equation

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && 0 && -9.5\\
\end{bmatrix} \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix} = \begin{bmatrix}
y_1 \\
y_2 \\
y_3 \\
\end{bmatrix}$

subbing into the above equation we get

$\begin{bmatrix}
1 && 0 && 0 \\
2 && 1 && 0 \\
5 && 1.7 && 1 \\
\end{bmatrix} \begin{bmatrix}
y_1 \\
y_2 \\
y_3 \\
\end{bmatrix} = \begin{bmatrix}
12 \\
9 \\
5 \\
\end{bmatrix}$

solving this by a forward sub we get

$y_1 =12, y_2=9-2(12)=-15, y_3=5-5(12)-1.7(-15)=-29.5$

Now subbing back into the equation for y we get

$\begin{bmatrix}
1 && 5 && 4 \\
0 && -10 && -5 \\
0 && 0 && -9.5\\
\end{bmatrix} \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix} = \begin{bmatrix}
12 \\
-15 \\
-29.5 \\
\end{bmatrix}$

Now solving this by back sub we get

$-9.5x_3=-29.5 \iff x_3=\frac{59}{19}$

$-10x_2-5(\frac{59}{19})=-15 \iff x_2 =-\frac{1}{19}$

$x_1+5(\frac{-1}{19})+4(\frac{59}{19})=12 \iff x_1=\frac{-3}{19}$

Sorry I didn't do this the first time

Good luck.