Tutorialspoint.dev

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 :



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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter