Register to reply

Choleski Split

by niko2000
Tags: choleski, split
Share this thread:
niko2000
#1
Aug20-04, 03:33 PM
P: 52
Hi,
Could anybody describe a procedure for splitting a matrix using a choleski method?
Could anyone show this on a simple example:
Let's say we have a matrix A:
[2 1 0 0]
[1 2 1 0]
[0 1 2 1]
[0 0 1 2]
and matrix b:
[1]
[0]
[0]
[1]
How to get x:
Ax = b
using abovementioned method?
Phys.Org News Partner Science news on Phys.org
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
Wong
#2
Aug21-04, 04:24 AM
P: 80
ha...I just learnt choleski factorisation last semester in the numerical analysis course!

To apply choleski factorisation, the matrix ought to be postive definite. This is true for the matrix you wrote. To explain the procedure one needs to know how to "partition" a matrix. I hope that you know it already.

Cholesky factorisation says that for a positive definite matrix P, it is possible to factorise it in the form,

[tex] P = LL^{T} [/tex]

where L is lower triangular and "[tex]...^{T}[/tex] denotes transpose. To develop a recursive procedure for the factorisation, we partition the matrix in the form,

[tex] P = \left(\begin{array}{cc}a & b^{T}\\b & C\end{array}\right) [/tex]
[tex] L = \left(\begin{array}{cc} d &0\\e & F\end{array}\right) [/tex]

where a, d are scalars, b, e are column vectors. Then,

[tex] P = \left(\begin{array}{cc}a & b^{T}\\b & C\end{array}\right) = LL^{T} = \left(\begin{array}{cc}d^{2} & de^{T}\\de & ee^{T}+FF^{T}\end{array}\right) [/tex]

So d=sqrt(a), e=b/d, and F*F^T = C*C^T - e*e^T. Remember that what we want is d, e and F. Now we get d and e. To get F, just notice that F*F^T is positive definite and so we may apply the previous step again until we get all entries of F.

To illustrate, use your example [tex] \left(\begin{array}{cccc}2&1&0&0\\1&2&1&0\\0&1&2&1\\0&0&1&2\end{array}\ right) [/tex]. Then a = 2, b^T=[1 0 0], [tex] C = \left(\begin{array}{ccc}2&1&0\\1&2&1\\0&1&2\end{array}\right) [/tex]. Thus d = sqrt(2), e^T = 1/sqrt(2)*[1 0 0] and similarly find F*F^T. Now treat F*F^T as the positive definite matrix and continue the previous steps until you get the factorisation.

To solve A*x=b, notice that once we get the factorisation A=L*L^T, the system becomes L*L^T*x=b, where L is lower triangular. We first solve L*y=b for y by "forward substitution" and then solve L^T*x=y by "backward substitution".

To illustrate, suppose we have the following system,

2x = 4
x + y = 6
x + y +z = 10

Then one may first solve the first equation to get x=2 and then substitute it into the second equation to get y=4. Finally put x=2, y=4 into the third equation to get z=4.

Hope that helps


Register to reply

Related Discussions
3+1 split General Physics 0