Scribd
Upload
689 views6 pages

Cholesky Method

This document discusses the Cholesky decomposition method for solving systems of linear equations. It begins with an introduction that defines the Cholesky decomposition as factorizing a real symmetric positive definite matrix A into the product of an upper triangular matrix U and its transpose. It then provides the algorithm for computing the Cholesky decomposition of a matrix A to obtain the upper triangular matrix U. Finally, it includes a MATLAB code that implements the Cholesky decomposition method.

Uploaded by

Zohaib Altaf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
689 views6 pages

Cholesky Method

This document discusses the Cholesky decomposition method for solving systems of linear equations. It begins with an introduction that defines the Cholesky decomposition as factorizing a real symmetric positive definite matrix A into the product of an upper triangular matrix U and its transpose. It then provides the algorithm for computing the Cholesky decomposition of a matrix A to obtain the upper triangular matrix U. Finally, it includes a MATLAB code that implements the Cholesky decomposition method.

Uploaded by

Zohaib Altaf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Assignment No.

Cholesky Decomposition Method


Subject: Numerical Methods

Submitted By: -

Zohaib Altaf – 195108


Zain Javed – 195105
1. INTRODUCTION
In linear algebra, a matrix decomposition or matrix factorization is a factorization of a
matrix into a product of matrices. There are many different matrix decompositions. One of them
is Cholesky Decomposition. The Cholesky factorization (or Cholesky decomposition) of
an n × n real symmetric positive definite matrix A has the form;

[A] = [U]T [U]

Where, U is an n × n real upper triangular matrix with positive diagonal elements. For
example, a 3 × 3 matrix U for a given 3 × 3 matrix A can be written as;
𝑎11 𝑎12 𝑎13
𝑎
[𝐴] = [ 21 𝑎22 𝑎23 ]
𝑎31 𝑎32 𝑎33
𝑢11 𝑢12 𝑢13
[𝑈] = [ 0 𝑢22 𝑢23 ]
0 0 𝑢33

This factorization is mainly used as a first step for the numerical solution of linear
equations of the form;
[A] [X] = [B] (1)

Where, A is a symmetric positive definite matrix. Such systems arise often in physics
applications, where A is positive definite due to the nature of the modeled physical phenomenon.
The matrix U is found using following formulas;

𝑖−1
2
𝑢𝑖𝑖 = √𝑎𝑖𝑖 − ∑ 𝑢𝑘𝑖
𝑘=1

𝑎𝑖𝑗 − ∑𝑖−1
𝑘=1 𝑢𝑘𝑖 𝑢𝑘𝑗
𝑢𝑖𝑗 =
𝑢𝑖𝑖

Once matrix U is known the equation (1) can be written as;

[U]T [U] [X] = [B] (2)


If we assume;

[Y] = [U] [X] (3)


Then, equation (2) becomes;

[U]T [Y] = [B] (4)

Which can be solved for Y and later equation (3) can be solved for X.
2. ALGORITHM
Input:
A symmetric positive definite matrix A whose elements are denoted by aij for 1 ≤ (i,j) ≤ n,
where n is the length of the matrix A.
Output:
The upper triangular matrix U whose elements are denoted by uij for 1 ≤ (i,j) ≤ n, where n
is the length of the matrix A.
Steps:

1. Set 𝑢11 = √𝑎11


𝑎1𝑗
2. For j=2 to n, set 𝑢1𝑗 =
𝑢11

3. For all i from 2 to n, set

𝑖−1
2
𝑢𝑖𝑖 = √𝑎𝑖𝑖 − ∑ 𝑢𝑘𝑖
𝑘=1

4. For all j from j=i+1 to j=n, set

𝑎𝑖𝑗 − ∑𝑖−1
𝑘=1 𝑢𝑘𝑖 𝑢𝑘𝑗
𝑢𝑖𝑗 =
𝑢𝑖𝑖

5. Output uij for i=1…, n and j=1…,n.

Stop.
3. CODE
% CHOLESKY DECOMPOSITION TO SOLVE A SYSTEM OF LINEAR EQUATIONS
clear
clc

flag=1;
while flag==1
Matrix=input('Enter a positive definite symmetric matrix of order n x n
like [6 15 55; 15 55 225; 55 225 979]: \n');
A=Matrix
[m,n] = size( A );
U = zeros( n, n );
K=eig(A)
for i=1:n
for j=1:n
if A(i,j)==A(j,i) && K(i,1)>=0
flag=2;
else
flag=1;
disp('Please use a symmetric positive definite matrix
only')
break
end
end
if flag == 1
break
end
end
end

for i=1:n
U(i, i) = sqrt(A(i, i) - U(:, i)'*U(:, i));
for j=(i + 1):n
U(i, j) = (A(i, j) - U(:,i)'*U(: ,j))/U(i, i);
end
end
display(U)
U_Transpose=U'
rhs=input('Enter the rhs of the equation [1 2 3]: \n');
B=rhs
Y=rhs/U';
X=Y/U
4. EXAMPLE PROBLEM
5. ERROR PROBLEM (WHEN MATRIX IN NOT SYMMETRIC)

6. ERROR PROBLEM (WHEN MATRIX IN NOT POSITIVE


DEFINITE)

You might also like