Results 1 to 4 of 4

Math Help - Linear Programming - LUP Decomposition

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    6

    Linear Programming - LUP Decomposition

    please help solve the equation

    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,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by tcpipmen View Post
    please help solve the equation

    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 need to start with the given matrix
    we will find the corrisponding elementry matrix and its inverse for each step to find and upper triangle matrix.


     \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
2 && 0 && 3 \\<br />
5 && 8 && 2 \\<br />
\end{bmatrix} \mbox{ } E_1= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
-2 && 1 && 0 \\<br />
0 && 0 && 1 \\<br />
\end{bmatrix} \mbox{ } E_1^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
2 && 1 && 0 \\<br />
0 && 0 && 1 \\<br />
\end{bmatrix}<br />

     \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
0 && -10 && -5 \\<br />
5 && 8 && 2 \\<br />
\end{bmatrix} \mbox{ } E_2= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
0 && 1 && 0 \\<br />
-5 && 0 && 1 \\<br />
\end{bmatrix} \mbox{ } E_2^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
0 && 1 && 0 \\<br />
5 && 0 && 1 \\<br />
\end{bmatrix}<br />

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

    So fiinally we have the upper triangle matrix

    U= \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
0 && -10 && -5 \\<br />
0 && 0 && -9.5\\<br />
\end{bmatrix}

    To get L we multiply

    L= E_1^{-1}E_2^{-1}E_3^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
2 && 1 && 0 \\<br />
5 && 1.7 && 1 \\<br />
\end{bmatrix}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,678
    Thanks
    611
    Hello, tcpipmen!

    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} \\<br />
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]

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    I thought you just wanted the factorization :(

    Quote Originally Posted by TheEmptySet View Post
    we need to start with the given matrix
    we will find the corrisponding elementry matrix and its inverse for each step to find and upper triangle matrix.


     \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
2 && 0 && 3 \\<br />
5 && 8 && 2 \\<br />
\end{bmatrix} \mbox{ } E_1= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
-2 && 1 && 0 \\<br />
0 && 0 && 1 \\<br />
\end{bmatrix} \mbox{ } E_1^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
2 && 1 && 0 \\<br />
0 && 0 && 1 \\<br />
\end{bmatrix}<br />

     \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
0 && -10 && -5 \\<br />
5 && 8 && 2 \\<br />
\end{bmatrix} \mbox{ } E_2= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
0 && 1 && 0 \\<br />
-5 && 0 && 1 \\<br />
\end{bmatrix} \mbox{ } E_2^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
0 && 1 && 0 \\<br />
5 && 0 && 1 \\<br />
\end{bmatrix}<br />

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

    So fiinally we have the upper triangle matrix

    U= \begin{bmatrix}<br />
1 && 5 && 4 \\<br />
0 && -10 && -5 \\<br />
0 && 0 && -9.5\\<br />
\end{bmatrix}

    To get L we multiply

    L= E_1^{-1}E_2^{-1}E_3^{-1}= \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
2 && 1 && 0 \\<br />
5 && 1.7 && 1 \\<br />
\end{bmatrix}

    Sorry I will finish the problem


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

    replace with our factoriztion

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

    Lets define this matrix equation

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

    subbing into the above equation we get

    \begin{bmatrix}<br />
1 && 0 && 0 \\<br />
2 && 1 && 0 \\<br />
5 && 1.7 && 1 \\<br />
\end{bmatrix} \begin{bmatrix}<br />
y_1 \\<br />
y_2 \\<br />
y_3 \\<br />
\end{bmatrix} = \begin{bmatrix}<br />
12 \\<br />
9 \\ <br />
5 \\<br />
\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}<br />
1 && 5 && 4 \\<br />
0 && -10 && -5 \\<br />
0 && 0 && -9.5\\<br />
\end{bmatrix} \begin{bmatrix}<br />
x_1 \\<br />
x_2 \\<br />
x_3 \\<br />
\end{bmatrix} = \begin{bmatrix}<br />
12 \\<br />
-15 \\<br />
-29.5 \\<br />
\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Programming
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 6th 2010, 12:35 PM
  2. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: January 20th 2009, 02:19 PM
  3. Replies: 1
    Last Post: November 17th 2008, 03:18 AM
  4. Linear Programming
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 17th 2008, 04:51 PM
  5. linear programming Max 5A+5B
    Posted in the Business Math Forum
    Replies: 1
    Last Post: April 13th 2008, 08:24 PM

Search Tags


/mathhelpforum @mathhelpforum