- Step one-select the maximum absolute value to be a new pivot.
- Step Two- Write the proper permutation matrix p12 that causes the swap.
- Step Three-Create an elimination matrix M1.
- Step Four-make a swap between row 2 and row 3.
- Step Five-Find the final upper matrix.
- Step Six-Find the value of the lower matrix L.
- Step Seven-Check that PA=L*U.
Solved example for LU decomposition-partial pivoting.
LU decomposition-partial pivoting is an important subject. Partial pivoting is a technique used to avoid errors due to small pivots or in the case of zero pivots, since we cannot divide on zero. We have a matrix A with a dimension of (3×3).
For the given example it is required to perform LU decomposition-partial pivoting.
Step one-select the maximum absolute value to be a new pivot.
Wen checking the first column of the given matrix, the pivot value for the first column is -2, we will select the maximum absolute value of (6,3), which are the two values that exist below the pivot.
The maximum absolute value is 6. We will swap the second row to be in the position of the first row. The first row will move to be in place of the second row. We will rewrite the matrix and call it A’.
We can get the values of U11, U12, and U13 as equal to the new values of a11,a12, and a13 in the new matrix A’.
Step Two- Write the proper permutation matrix p12 that causes the swap.
We have swapped r2 to be r1, so the matrix A is being multiplied by P12, which is the permutation matrix that swaps r1 to r2 and r1 to r2.
The multiplication will be on the left side of matrix A as shown in the next slide image. Check that the multiplication of p12 by A will give the exact values of Matrix A’.
Step Three-Create an elimination matrix M1.
In order to create the elimination matrix M1, we want the value of a21 to be equal to zero to create the upper matrix.
To do this we will multiply the first row by (-a21/a11) and add it to row 2. The value of the multiplication factor is(+ 1/3).
Similarly, we want the a31 value to be=0, so we multiply the first row by(-a31/a11 )and add to r3. the multiplication factor is (-1/2).
A new matrix will be formed as (6 – 6 7, 0 0 4/3, 0 -5 1/2).
The elimination matrix will be a (3×3) matrix and it is written as M1 and located at the left of P12.
The M1 matrix is ( 1 0 0, 1/3 1 0,-1/2 0 1). We will check that the M1 by A’ will lead to matrix B which is (6 – 6 7, 0 0 4/3, 0 -5 1/2). As we can see the sequence of operations is considered as A followed to the left by P12 and followed again by M1 as we can see in the next slide image.
Step Four-make a swap between row 2 and row 3.
As we can observe that the second pivot (intersection of row 2 with column 2) is zero, we can not proceed to complete the U matrix, not possible to divide by zero, we will swap between row 3 to be as row 2 and vice versa.
So we will use permutation matrix P23 to do this operation. The new matrix will be a 3×3 matrix and written as ( 6 -6 7, 0 -5 1/2, 0 0 4/3). The sequence of operations will be as (P23M1P12*A).
Step Five-Find the final upper matrix.
Due to the previous operation, the upper matrix is formed as a 3×3 matrix and can be expressed as ( 6 -6 7, 0 -5 1/2, 0 0 4/3). This U matrix is a part of LU decomposition-partial pivoting. Check that the multiplication of P23*M1*P12*A) will lead to the new matrix ( 6 -6 7, 0 -5 1/2, 0 0 4/3).
Step Six-Find the value of the lower matrix L.
We have the LHS as (P23)*(M1P12A) is equal to the RHS U. To get the lower matrix L which is a part of LU decomposition-partial pivoting, we will multiply both sides by I, which is nothing but(P23*P23)in our previous post, we find that (P23) is the inverse of itself.
We will write two brackets to be multiplied by each other. The first bracket is (P23*M1P23), while the second bracket is(P23*P12*A) which is nothing But PA or the permutation matrix by the original matrix A, Where P is (P23*P12). If we divide both sides by (P23M1P23), we will have PA=the inverse of (P23M1P23) U. Then the L matrix is the inverse of (P23M1P23).
We will multiply the three matrices P23*M1*P23, where P23 is (1 0 0, 0 0 1,0 1 0)*M1 ( 1 0 0, 1/3 1 0,-1/2 0 1). We take the inverse of the product of P23M1P23 and get the final value of the lower matrix.
Step Seven-Check that PA=L*U.
It is better to check as a part of LU decomposition-partial pivoting that the product of PA=LU. We can check that both sides are equal, please refer to the next slide image.
This is a link for the pdf file used in the illustration of this post.
This is a link to the next post, which is How to get x1,x2,x3-using Gaussian-partial pivot?
Link to Omni calculator-LU Decomposition Calculator.
Another calculator to use is Calculator for matrices.