In numerical analysis and linear algebra, LU decomposition (where ‘LU’ stands for ‘lower upper’, and also called LU factorization) factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. Computers usually solve square systems of linear equations using the LU decomposition, and it is also a key step when inverting a matrix, or computing the determinant of a matrix. The LU decomposition was introduced by mathematician Tadeusz Banachiewicz in 1938.
Let A be a square matrix. An LU factorization refers to the factorization of A, with proper row and/or column orderings or permutations, into two factors, a lower triangular matrix L and an upper triangular matrix U, A=LU.
Doolittle Algorithm :
It is always possible to factor a square matrix into a lower triangular matrix and an upper triangular matrix. That is, [A] = [L][U]
Doolittle’s method provides an alternative way to factor A into an LU decomposition without going through the hassle of Gaussian Elimination.
For a general n×n matrix A, we assume that an LU decomposition exists, and write the form of L and U explicitly. We then systematically solve for the entries in L and U from the equations that result from the multiplications necessary for A=LU.
Example :
Input :Output :
![]()
C++
// CPP Program to decompose a matrix into // lower and upper traingular matrix #include <bits/stdc++.h> using namespace std; const int MAX = 100; void luDecomposition( int mat[][MAX], int n) { int lower[n][n], upper[n][n]; memset (lower, 0, sizeof (lower)); memset (upper, 0, sizeof (upper)); // Decomposing matrix into Upper and Lower // triangular matrix for ( int i = 0; i < n; i++) { // Upper Triangular for ( int k = i; k < n; k++) { // Summation of L(i, j) * U(j, k) int sum = 0; for ( int j = 0; j < i; j++) sum += (lower[i][j] * upper[j][k]); // Evaluating U(i, k) upper[i][k] = mat[i][k] - sum; } // Lower Triangular for ( int k = i; k < n; k++) { if (i == k) lower[i][i] = 1; // Diagonal as 1 else { // Summation of L(k, j) * U(j, i) int sum = 0; for ( int j = 0; j < i; j++) sum += (lower[k][j] * upper[j][i]); // Evaluating L(k, i) lower[k][i] = (mat[k][i] - sum) / upper[i][i]; } } } // setw is for displaying nicely cout << setw(6) << " Lower Triangular" << setw(32) << "Upper Triangular" << endl; // Displaying the result : for ( int i = 0; i < n; i++) { // Lower for ( int j = 0; j < n; j++) cout << setw(6) << lower[i][j] << " " ; cout << " " ; // Upper for ( int j = 0; j < n; j++) cout << setw(6) << upper[i][j] << " " ; cout << endl; } } // Driver code int main() { int mat[][MAX] = { { 2, -1, -2 }, { -4, 6, 3 }, { -4, -2, 8 } }; luDecomposition(mat, 3); return 0; } |
Python3
# Python3 Program to decompose
# a matrix into lower and
# upper traingular matrix
MAX = 100;
def luDecomposition(mat, n):
lower = [[0 for x in range(n)]
for y in range(n)];
upper = [[0 for x in range(n)]
for y in range(n)];
# Decomposing matrix into Upper
# and Lower triangular matrix
for i in range(n):
# Upper Triangular
for k in range(i, n):
# Summation of L(i, j) * U(j, k)
sum = 0;
for j in range(i):
sum += (lower[i][j] * upper[j][k]);
# Evaluating U(i, k)
upper[i][k] = mat[i][k] – sum;
# Lower Triangular
for k in range(i, n):
if (i == k):
lower[i][i] = 1; # Diagonal as 1
else:
# Summation of L(k, j) * U(j, i)
sum = 0;
for j in range(i):
sum += (lower[k][j] * upper[j][i]);
# Evaluating L(k, i)
lower[k][i] = int((mat[k][i] – sum) /
upper[i][i]);
# setw is for displaying nicely
print(“Lower Triangular Upper Triangular”);
# Displaying the result :
for i in range(n):
# Lower
for j in range(n):
print(lower[i][j], end = “ ”);
print(“”, end = “ ”);
# Upper
for j in range(n):
print(upper[i][j], end = “ ”);
print(“”);
# Driver code
mat = [[2, -1, -2],
[-4, 6, 3],
[-4, -2, 8]];
luDecomposition(mat, 3);
# This code is contributed by mits
PHP
<?php // PHP Program to decompose // a matrix into lower and // upper traingular matrix $MAX = 100; function luDecomposition( $mat , $n ) { $lower ; $upper ; for ( $i = 0; $i < $n ; $i ++) for ( $j = 0; $j < $n ; $j ++) { $lower [ $i ][ $j ]= 0; $upper [ $i ][ $j ]= 0; } // Decomposing matrix // into Upper and Lower // triangular matrix for ( $i = 0; $i < $n ; $i ++) { // Upper Triangular for ( $k = $i ; $k < $n ; $k ++) { // Summation of // L(i, j) * U(j, k) $sum = 0; for ( $j = 0; $j < $i ; $j ++) $sum += ( $lower [ $i ][ $j ] * $upper [ $j ][ $k ]); // Evaluating U(i, k) $upper [ $i ][ $k ] = $mat [ $i ][ $k ] - $sum ; } // Lower Triangular for ( $k = $i ; $k < $n ; $k ++) { if ( $i == $k ) $lower [ $i ][ $i ] = 1; // Diagonal as 1 else { // Summation of L(k, j) * U(j, i) $sum = 0; for ( $j = 0; $j < $i ; $j ++) $sum += ( $lower [ $k ][ $j ] * $upper [ $j ][ $i ]); // Evaluating L(k, i) $lower [ $k ][ $i ] = (int)(( $mat [ $k ][ $i ] - $sum ) / $upper [ $i ][ $i ]); } } } // setw is for // displaying nicely echo " Lower Triangular" ; echo " Upper Triangular
" ; // Displaying the result : for ( $i = 0; $i < $n ; $i ++) { // Lower for ( $j = 0; $j < $n ; $j ++) echo " " . $lower [ $i ][ $j ] . " " ; echo " " ; // Upper for ( $j = 0; $j < $n ; $j ++) echo $upper [ $i ][ $j ] . " " ; echo "
" ; } } // Driver code $mat = array ( array (2, -1, -2), array (-4, 6, 3), array (-4, -2, 8)); luDecomposition( $mat , 3); // This code is contributed by mits ?> |
Output:
Lower Triangular Upper Triangular 1 0 0 2 -1 -2 -2 1 0 0 4 -1 -2 -1 1 0 0 3
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments