in Linear Algebra recategorized by
3,235 views
8 votes
8 votes
Assume that the matrix $A$ given below, has factorization of the form $LU=PA$, where $L$ is lower-triangular with all diagonal elements equal to $1, U$ is upper-triangular, and $P$ is a permutation matrix. For

$$A = \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$$

Compute $L, U,$ and $P$ using Gaussian elimination with partial pivoting.
in Linear Algebra recategorized by
3.2k views

2 Comments

Please explain the meaning of “ Partial pivoting ” ?

1
1

Check it here. Marked my previous selected answer as wrong.

0
0

3 Answers

7 votes
7 votes
Best answer
$A = \begin{bmatrix} 2 &5 &9 \\ 4 &6 &5 \\ 8&2 &3 \end{bmatrix}$

-- Using Gaussian Elimination, we will change $A$ into upper triangular matrix $U$ and simultaneously find out elementary matrices $E_{21}$, $E_{31}$ and $E_{32}$.

-- To get the elementary matrices, we have to do the same operation on the Identity matrix as we do on the original matrix $A.$

On applying $R_2 \leftarrow R_{2} - 2R_1$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 8 &2 &3 \end{bmatrix}$

and $E_{21}$ becomes $\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix}$ $[ \because R_2 \leftarrow R_{2} - 2R_1 $ on identity matrix $I$ will give $E_{21}]$

We can write it as $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 8 &2 &3 \end{bmatrix}=$ $\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix}$* $\begin{bmatrix} 2 &5 &9 \\ 4 &6 &5 \\ 8&2 &3 \end{bmatrix} $

Now, applying $R_3 \leftarrow R_{3} - 4R_1$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &-18 &-33 \end{bmatrix}$

and $E_{31}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ -4 &0 &1 \end{bmatrix}$ $[ \because R_3 \leftarrow R_{3} - 4R_1 $ on identity matrix $I$ will give $E_{31}]$

Now, applying $R_3 \leftarrow R_{3} - \frac{18}{4}R_2$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

and $E_{32}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0&\frac{-18}{4} &1 \end{bmatrix}$ $[ \because R_3 \leftarrow R_{3} - \frac{18}{4}R_2$ on identity matrix $I$ will give $E_{32}]$

So, here,

$U= \begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix},\;\; E_{21} =\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix},\;\; E_{31} =\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ -4 &0 &1 \end{bmatrix},\;\; E_{32} =\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{-18}{4} &1 \end{bmatrix},\;\;$

Now, we can write all these things as:-

$\Rightarrow E_{32}E_{31}E_{21}(A) = U$

$\Rightarrow A = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} U$

Here, $E_{21}^{-1},\;E_{31}^{-1},\; E_{32}^{-1}$ are very simple to compute. Just do the reverse operation means in row operations where we have done subtraction , we have to do addition.

So, $\Rightarrow A = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} U$ becomes

$A= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 0 &0 &1 \end{bmatrix}*\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 4 &0 &1 \end{bmatrix}*\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{18}{4} &1 \end{bmatrix}*\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

$\Rightarrow A= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}*\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

It is the LU decomposition where $L= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}\;\;\text{and}\; U=\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

Since we have not done any row exchange, So, permutation matrix will not be changed. It will remain identity matrix $I.$

So, the answer is:-

$L= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}\;\; U=\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$ and $P= \begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{bmatrix}$
edited by

3 Comments

How are we obtaining elementary matrices ?
0
0

@Satbir

edited.

2
2
good explanation bhai :)
0
0
16 votes
16 votes

Here $LU=PA\rightarrow(1)$

Where $L=\begin{bmatrix} l_{11}&0 &0 \\ l_{21}&l_{22} &0 \\ l_{31}&l_{32} &l_{33} \end{bmatrix}$

Given that $l_{11}=l_{22}=l_{33}=1$

$L=\begin{bmatrix} 1&0 &0 \\ l_{21}&1 &0 \\ l_{31}&l_{32} &1 \end{bmatrix}$

$U=\begin{bmatrix} u_{11}&u_{12} &u_{13} \\ 0&u_{22} &u_{23} \\ 0&0 &u_{33} \end{bmatrix}$

$P=\begin{bmatrix} 1&0 &0\\ 0&1 &0 \\ 0&0 &1 \end{bmatrix}$

$A = \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$

Put the values in equation $(1),$ we get

$\begin{bmatrix} 1&0 &0 \\ l_{21}&1 &0 \\ l_{31}&l_{32} &1 \end{bmatrix}\cdot \begin{bmatrix} u_{11}&u_{12} &u_{13} \\ 0&u_{22} &u_{23} \\ 0&0 &u_{33} \end{bmatrix}=\begin{bmatrix} 1&0 &0\\ 0&1 &0 \\ 0&0 &1 \end{bmatrix}\cdot \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix} $

$\begin{bmatrix} u_{11}&u_{12} &u_{13} \\ l_{21}u_{11}&l_{21}u_{12}+u_{22} &l_{21}u_{13}+u_{23} \\l_{31}u_{11} &l_{31}u_{12}+l_{32}u_{22} &l_{31}u_{13}+l_{32}u_{23}+u_{33} \end{bmatrix}  =\begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$

Compare each element of both side and we get,

$u_{11}= 2,u_{12}= 5,u_{13}= 9$

$l_{21}u_{11}= 4\implies l_{21}=2$

$l_{21}u_{12}+u_{22} = 6\implies u_{22}=-4$ 

$l_{21}u_{13}+u_{23}= 5\implies u_{23}=-13$

$l_{31}u_{11} = 8\implies l_{31}=4$

$l_{31}u_{12}+l_{32}u_{22} = 2\implies l_{32}=4.5$

$l_{31}u_{13}+l_{32}u_{23}+u_{33} = 3\implies u_{33}=25.5$

So, $L=\begin{bmatrix} 1&0 &0 \\ 2&1 &0 \\ 4&4.5 &1 \end{bmatrix}$

$U=\begin{bmatrix} 2&5 &9 \\ 0&-4&-13 \\ 0&0 &25.5 \end{bmatrix}$

$P=\begin{bmatrix} 1& 0&0 \\0 &1 &0 \\ 0&0 &1\end{bmatrix}$

Reference$:$ http://mathworld.wolfram.com/PermutationMatrix.html

edited by

4 Comments

how do u know P is identity?
4
4
Check the reference link attached in answer.
1
1
Here is a nice explanatory video of how to do PA = LU Decomposition

https://www.youtube.com/watch?v=f6RT4BI4S7M
1
1

I Solved it according to link provided above.Can anybofy help me where i am wrong !!!

 

0
0
3 votes
3 votes

$\textbf{Gauss Elimination with Partial Pivoting}$


To solve the system of linear equations, we can use Gauss Elimination method, Gauss Jordan Method (specially used to find the inverse of a matrix) or LU Decomposition method but the Gauss Elimination method is most popular because compared to the other methods because it has the lowest amount of computational effort.


The method which we used here is called the $\textbf{Naive Gauss Elimination}$ method (I would request you to see that method first if you don't have any idea about that method and then come to this question).

Diagonal element on the $i^{th}$ row is called 'pivot' element. Why we call it as pivot because for doing any of the row operations at the $i^{th}$ step, most important element is the diagonal element.

In partial pivoting, we interchange rows so that diagonal/pivot elements will not be zero. During this row exchanges, we make sure that in each step, we look at the entire column and the value which has the largest magnitude or we can say the largest absolute value, becomes the pivot element. There is also a full pivoting/complete pivoting where we interchange both rows and columns. Full pivoting is typically not used in Gauss elimination because the amount of overhead to interchange the columns is high compared to partial pivoting.


Now, comes to the question,


$$A = \begin{pmatrix}
2 & 5 & 9 \\
4 & 6 & 5 \\
8 & 2 & 3
\end{pmatrix}$$

$\textbf{Step 1:}$


Now, in first column, maximum absolute value is $8,$ So, interchanging the first and the third row i.e. $R_1 \leftrightarrow R_3.$ So, Now, $A_1$ and $P$ becomes:


$A_1 = \begin{pmatrix}
8 & 2 & 3 \\
4 & 6 & 5 \\
2 & 5 & 9
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$


$\textbf{Step 2:}$


Eliminate $4$ and $2$ from the first column of $A$ and so, $R_2 \leftarrow \frac{-1}{2}R_1 + R_2$ and $R_3 \leftarrow \frac{-1}{4}R_1 + R_3$. Now, $A_2$ and $P$ becomes:


$A_2 = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & \frac{9}{2} & \frac{33}{4}
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$

$\textbf{Step 3:}$


Now, in second column, maximum absolute value of $5$ and $\frac{9}{2}$ is $5$ and so, we don't need any interchanges and so, we do row operation $R_3 \leftarrow \frac{-9}{10}R_2 + R_3$ to make third row and second column as zero. So,  Now, $A_3$ and $P$ becomes:


$A_3 = U = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$

So, now, we have converted matrix $A$ into the $A_3$ which is nothing but the upper triangular matrix and if we try to summarize what we have done till now, we write the equation as:


$E_{32}E_{31}E_{21}PA = U$


And So,


$PA = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U$


Here, $E_{21},E_{31},E_{32}$ are nothing but the matrices which we got by the same row operations which we did above, on the identity matrix $I.$


So,


$E_{21} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{-1}{2} & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},$ $E_{31} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\frac{-1}{4} & 0 & 1
\end{pmatrix}$ and $E_{32} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & \frac{-9}{10} & 1
\end{pmatrix}$ 

Now, inverses of these elementary matrices are nor difficult to find, we just have to reverse signs while doing row operations, So,

$E_{21}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},$ $E_{31}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\frac{1}{4} & 0 & 1
\end{pmatrix}$ and $E_{32}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & \frac{9}{10} & 1
\end{pmatrix}$ 

So, $E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix} = L$


Hence, 
$$PA = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix} \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix} $$


Therefore, matrices $P,L$ and $U$ are:


$P= \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}, L = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix}$ and $U = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix}$

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true