Splitting a Matrix with Choleski Method: A Simple Example

In summary, the Choleski factorisation method can be used to factorise a positive definite matrix into a lower triangular matrix multiplied by its transpose. This can be done recursively by partitioning the matrix and solving for the entries of the lower triangular matrix. This method can then be applied to solve a system of equations, by first solving for y using "forward substitution" and then solving for x using "backward substitution".
  • #1
niko2000
51
0
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?
 
Physics news on Phys.org
  • #2
ha...I just learned 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
 
  • #3


Sure, I would be happy to explain the procedure for splitting a matrix using the Choleski method and provide a simple example. The Choleski method is a numerical algorithm used to decompose a symmetric, positive definite matrix into a lower triangular matrix and its transpose. This decomposition is useful for solving systems of linear equations, such as the one shown in your example, where we have a matrix A and vector b and we want to find the vector x that satisfies the equation Ax = b.

To begin, we first need to check that our matrix A is symmetric and positive definite. In your example, A is symmetric, so we just need to check if it is positive definite. This means that all of the eigenvalues of A must be positive. In your case, we can easily see that the eigenvalues are 3, 3, 3, and 3, so A is indeed positive definite.

Once we have verified that A is positive definite, we can start the Choleski decomposition. The first step is to find the lower triangular matrix L such that A = LL^T. This can be done by using the following formula:

L = [√a11 0 0 0]
[ a21/√a11 √(a22 - a21^2/a11) 0 0]
[ a31/√a11 (a32 - a31a21/a11)/√(a22 - a21^2/a11) √(a33 - a31^2/a11) 0]
[ a41/√a11 (a42 - a41a21/a11)/√(a22 - a21^2/a11) (a43 - a41a31/a11 - a42a32/a22)/√(a33 - a31^2/a11) √(a44 - a41^2/a11 - a42^2/a22 - a43^2/a33)]

In this formula, aij represents the element in the ith row and jth column of A. Using this formula, we can calculate L for our example matrix A:

L = [√2 0 0 0]
[ 1/√2 √(3/2) 0 0]
[ 0 1/√3 √(2/3) 0]
[ 0
 

1. What is the Choleski Method?

The Choleski Method is a numerical algorithm used to decompose a symmetric positive definite matrix into a lower triangular matrix and its transpose. This method is commonly used in scientific computing and data analysis.

2. Why is the Choleski Method useful for splitting a matrix?

The Choleski Method is useful for splitting a matrix because it reduces the computational complexity of solving a linear system of equations. By decomposing the matrix into a lower triangular matrix, the system can be solved more efficiently, making it a popular choice for large datasets.

3. How does the Choleski Method work?

The Choleski Method works by finding the square roots of the elements of the original matrix. It starts by decomposing the first element of the matrix, then uses the result to decompose the next element, and so on until the entire matrix is decomposed into a lower triangular matrix.

4. What are the advantages of using the Choleski Method over other matrix splitting methods?

The Choleski Method has several advantages over other matrix splitting methods. It is more efficient in terms of computational complexity, especially for large datasets. It also guarantees the positive definiteness of the resulting matrices, which is essential for many scientific applications.

5. Can the Choleski Method be used for any type of matrix?

No, the Choleski Method can only be used for symmetric positive definite matrices. This means that the matrix must have all positive eigenvalues and be symmetric, which is not always the case for all types of matrices.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
765
  • Linear and Abstract Algebra
Replies
8
Views
663
  • Linear and Abstract Algebra
Replies
8
Views
995
  • Linear and Abstract Algebra
Replies
34
Views
1K
Replies
24
Views
1K
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
1K
Replies
7
Views
782
  • Linear and Abstract Algebra
2
Replies
52
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
488
Back
Top