Doolittle Algorithm : LU Decomposition

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 :

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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.

Doolittle Algorithm : LU Decomposition

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

C++

Python3

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top tutorials