LU Factorization Method in MATLAB

LU Factorization method, also known as LU decomposition method, is a popular matrix decomposing method of numerical analysis and engineering science. This method factors a matrix as a product of lower triangular and upper triangular matrices. LU method can be viewed as matrix form of Gaussian elimination to solve system of linear equation. LU factorization is a key step while computing the determinant of a matrix or inverting a matrix.

In this tutorial, we’re going to write a program for LU factorization in MATLAB, and discuss its mathematical derivation and a numerical example. You can check out our earlier tutorial where we covered a C program and algorithm/flowchart for this method.

Derivation of LU Factorization Method:

Consider a square matrix A of order N x N which is to be factored as the product of lower triangular and upper triangular matrix. The matrix A can be represented as:

A = ( a _{n, n} )

Defining matrix as:

A ⁽⁰⁾ : = A

Now, it is desired to eliminate the matrix elements below the main diagonal in the n^th column of A (n – 1) by adding to the i^th row of this matrix the n^th row multiplied by

l_{i, n} := – [ a_i,n^{(n – 1)} / [ a_n,n^{(n -1)}]

for i = n+1, . . . .. . ..  . N

This can be done by multiplying A ^{(n -1)} on the left side with the lower triangular matrix and can be represented as:

Set matrix A as:

A ⁽ⁿ⁾ := L_n A ^{(n – 1)}

After performing the (N – 1 ) steps, the lower triangular elements of the matrix are eliminated and we get the upper triangular matrix A ^{( N – 1 )} . The decomposition can be mathematically represented as:

A = L₁ ^-1 L₁ A ⁽⁰⁾ = L₁^-1 A ⁽¹⁾ = L₁ ^-1 L₂ ^-1 L₂ A ⁽¹⁾ = L₁^-1 L₂ ^-1  A ⁽²⁾ = . . . = L₁ ^-1. .  L_N-1 ^-1 A ^(N-1)

Denoting upper triangular matrix A ^{( N – 1)} by U and L = L₁ ^-1 . . .  L_N-1 ^-1.

Now, the following facts can be observed:

• Inverse of a lower triangular matrix L is again a lower triangular matrix.
• The multiplication of two lower triangular matrices is again a lower triangular matrix.

It can be said that, L is a lower triangular matrix. So, it can be written that:

Finally, we obtain:

A = LU

where, L: Lower triangular matrix and U: Upper triangular matrix. This procedure is used to write the program for LU factorization in MATLAB.

LU Factorization Method in MATLAB:

% LU Factorization MATLAB Program
% LU factorization with partial (row) pivoting
function [L,U,P]=LU_pivot(A) % declaration of function 
% L, U, and P are output of the program
% A is the input matrix or argument to the function 
A = [4 3; 6 3] % Input matrix which is to be factored 
[n,n]=size(A); % checking the size of matrix
L=eye(n); P=L; U=A; % assigning process
for k=1:n %start of loop
    [pivot m]=max(abs(U(k:n,k))); % pivoting process
    m=m+k-1;
    if m~=k % begining of scope of if statement 
        % interchange rows m and k in U
        temp=U(k,:); % assigning to temporary variable
        U(k,:)=U(m,:);
        U(m,:)=temp; % returnig the value from temp
        % interchange rows m and k in P
        temp=P(k,:); % assigning to temp 
        P(k,:)=P(m,:);
        P(m,:)=temp; % returning the value from temp
        if k >= 2 % checking the condition using if
            temp=L(k,1:k-1);
            L(k,1:k-1)=L(m,1:k-1);
            L(m,1:k-1)=temp;
        end % end of if scope
    end
    for j=k+1:n  % loop to print output 
        L(j,k)=U(j,k)/U(k,k);
        U(j,:)=U(j,:)-L(j,k)*U(k,:);
    end
end

The above MATLAB code for LU factorization or LU decomposition method is for factoring a square matrix with partial row pivoting technique. This source code is written to solve the following typical problem:

A = [ 4 3; 6 3]

If this source code of LU decomposition method is to be used for any other problem, the value of array A in the program should be changed as per requirement by strictly following MATLAB syntax.

Since, the input data are already given in the source code, the program doesn’t need any input. When the program is executed in the MATLAB workspace, the function LU_pivot( ) is called which uses matrix A as input argument and output of the program is displayed.

As the program works on partial row pivoting principle, it gives the lower triangular matrix as output. The sample output of this MATLAB program is given below:

Numerical Example in LU Factorization:

Now, let’s analyze mathematically the aforementioned program for LU Factorization method in Matlab, using the same input arguments. The question here is:

Factor the following matrix into lower triangular matrix and upper triangular matrix by using LU Factorization Method.

Solution:

The given matrix is:

We are to express this matrix as:

Solving the linear by inspection and expanding the matrix multiplication gives:

l₁₁ . u₁₁ + 0  . 0 = 4

l₁₁ . u₁₂ + 0  . u₂₂ = 3

l₂₁ . u₁₁ + l₂₂ . 0 = 6

l₁₁ . u₁₂ + l₂₂  . u₂₂ = 3

Solving above system of linear equation:

l₂₁= 0.6667

So, the lower triangular matrix, L, is:

Thus, the answer is same as that obtained from the MATLAB program for LU factorization. If you have questions regarding LU factorization, its Matlab code, or its mathematical derivation, bring them up from the comments section. You can find more Numerical Methods tutorial using Matlab here.