How to resolve the algorithm Cholesky decomposition step by step in the ALGOL 68 programming language
How to resolve the algorithm Cholesky decomposition step by step in the ALGOL 68 programming language
Table of Contents
Problem Statement
Every symmetric, positive definite matrix A can be decomposed into a product of a unique lower triangular matrix L and its transpose:
L
{\displaystyle L}
is called the Cholesky factor of
A
{\displaystyle A}
, and can be interpreted as a generalized square root of
A
{\displaystyle A}
, as described in Cholesky decomposition. In a 3x3 example, we have to solve the following system of equations: We can see that for the diagonal elements (
l
k k
{\displaystyle l_{kk}}
) of
L
{\displaystyle L}
there is a calculation pattern: or in general: For the elements below the diagonal (
l
i k
{\displaystyle l_{ik}}
, where
i
k
{\displaystyle i>k}
) there is also a calculation pattern: which can also be expressed in a general formula: Task description The task is to implement a routine which will return a lower Cholesky factor
L
{\displaystyle L}
for every given symmetric, positive definite nxn matrix
A
{\displaystyle A}
. You should then test it on the following two examples and include your output. Example 1: Example 2:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Cholesky decomposition step by step in the ALGOL 68 programming language
Source code in the algol programming language
#!/usr/local/bin/a68g --script #
MODE FIELD=LONG REAL;
PROC (FIELD)FIELD field sqrt = long sqrt;
INT field prec = 5;
FORMAT field fmt = $g(-(2+1+field prec),field prec)$;
MODE MAT = [0,0]FIELD;
PROC cholesky = (MAT a) MAT:(
[UPB a, 2 UPB a]FIELD l;
FOR i FROM LWB a TO UPB a DO
FOR j FROM 2 LWB a TO i DO
FIELD s := 0;
FOR k FROM 2 LWB a TO j-1 DO
s +:= l[i,k] * l[j,k]
OD;
l[i,j] := IF i = j
THEN field sqrt(a[i,i] - s)
ELSE 1.0 / l[j,j] * (a[i,j] - s) FI
OD;
FOR j FROM i+1 TO 2 UPB a DO
l[i,j]:=0 # Not required if matrix is declared as triangular #
OD
OD;
l
);
PROC print matrix v1 =(MAT a)VOID:(
FOR i FROM LWB a TO UPB a DO
FOR j FROM 2 LWB a TO 2 UPB a DO
printf(($g(-(2+1+field prec),field prec)$, a[i,j]))
OD;
printf($l$)
OD
);
PROC print matrix =(MAT a)VOID:(
FORMAT vector fmt = $"("f(field fmt)n(2 UPB a-2 LWB a)(", " f(field fmt))")"$;
FORMAT matrix fmt = $"("f(vector fmt)n( UPB a- LWB a)(","lxf(vector fmt))")"$;
printf((matrix fmt, a))
);
main: (
MAT m1 = ((25, 15, -5),
(15, 18, 0),
(-5, 0, 11));
MAT c1 = cholesky(m1);
print matrix(c1);
printf($l$);
MAT m2 = ((18, 22, 54, 42),
(22, 70, 86, 62),
(54, 86, 174, 134),
(42, 62, 134, 106));
MAT c2 = cholesky(m2);
print matrix(c2)
)
You may also check:How to resolve the algorithm GUI enabling/disabling of controls step by step in the R programming language
You may also check:How to resolve the algorithm Perfect numbers step by step in the Slate programming language
You may also check:How to resolve the algorithm Horner's rule for polynomial evaluation step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Generator/Exponential step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Send email step by step in the Python programming language