Décomposition de CHOLESKY. Comment résoudre un système linéaire par la décomposition de CHOLESKY ?

Introduction

This tutorial will guide you through the Cholesky decomposition method, a technique used to solve linear systems. It's particularly useful for solving systems with positive definite matrices. Understanding this method can greatly enhance your skills in linear algebra and its applications in various fields, such as computer science, engineering, and statistics.

Step 1: Understand Cholesky Decomposition

Cholesky decomposition involves breaking down a positive definite matrix into the product of a lower triangular matrix and its transpose. Here’s how it works:

• If A is a symmetric positive definite matrix, you can write:

  [ A = L \cdot L^T ]

  where L is a lower triangular matrix.

Practical Tip

• Ensure your matrix is symmetric and positive definite before applying this method, as Cholesky decomposition only applies to these types of matrices.

Step 2: Set Up the Matrix Equation

To solve a system of linear equations Ax = b using Cholesky decomposition, follow these steps:

• Identify your matrix A and your vector b.
• Verify that A is symmetric and positive definite.

Example

Given a matrix:

[ A = \begin{bmatrix} 4 & 2 \ 2 & 3 \end{bmatrix} ]

and a vector:

[ b = \begin{bmatrix} 8 \ 7 \end{bmatrix} ]

Step 3: Perform Cholesky Decomposition

To find matrix L, apply the following formulas for each element:

1. For diagonal elements: [ L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2} ]

2. For off-diagonal elements: [ L_{ij} = \frac{1}{L_{jj}}(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}) ]

Example Calculation

For the matrix A above:

• Calculate L step by step for each element.

Step 4: Solve the Lower Triangular System

Once you have the lower triangular matrix L, solve the intermediate system:

1. Solve Ly = b for y using forward substitution.

Forward Substitution Steps

• Start from the first equation and work your way down.

Example

For our earlier example, you would set up the equations based on L and solve for y.

Step 5: Solve the Upper Triangular System

Now, solve for x using the matrix equation L^T x = y with backward substitution.

Backward Substitution Steps

• Start from the last equation and work your way up.

Example

Again, set up the equations based on L^T and solve for x.

Conclusion

Cholesky decomposition is a powerful technique for solving linear systems, particularly when dealing with symmetric positive definite matrices. By following these steps, you can efficiently decompose a matrix and find solutions to linear equations. Practice with different matrices to solidify your understanding, and explore applications in computational mathematics for further learning.