Solving a linear system with Cholesky factorization

18.9k Views Asked by At

So, I've reached the following problem: Given $A \in R^{nxn} $ positive-definite and symmetrical, $B\in R^{nxn}$ and the vector $c\in R^n$ write an algorithm to solve to following situation:

$Ax=Bc$

After I break down A with Cholesky in $ L * L^t $ I don't know how should I proceed, should I get the inverse and find x or is there a easier method?

1

There are 1 best solutions below

0
On BEST ANSWER

The idea is the same of LU decomposition, i.e. use the triangular for of the matrix $L$.

For simplicity put, $Bc = b \, \in \mathbb{R}^n$, so the system is: $$ \begin{aligned} Ax &= b \\ L L^{T} x &= b \end{aligned} $$ now you call $L^{T} x = y $ and you solve the system: $$ \left \{ \begin{aligned} Ly &= b \\ L^{T} x &= y \end{aligned} \right. $$

The matrix $L$ is triangular so you solve it directly with forward and back substitution, first $Ly =b$ and after $L^{T} x = y$.

See also wiki page.