Chapter 1.5 Positive Definite System Chelosky Decomposition

[Def] If A is square symmetry , real and satisfy x^TAx>0 for all x , then A is called positive definite matrix.

[Thm] If A is positive definite then A is nonsingular.

[Cor] A is positive definite then the system Ax=b has a unique solution.
<Proof of Thm>

If A is singular then $\exists$ x $\ne$ 0 $\rightarrow$ Ax=0 $\Rightarrow$ x^T(Ax)=x^T 0 = 0 $\to \gets$

$\Rightarrow$ A is not position definite.

[Thm] If M is real and nonsingular , then A=MM^T is position definite.

<Proof>

1.

real $\rightarrow$ OK !

2.

symmetric (A^T=A) because A^T=(MM^T)^T=(M^T)^TM^T=MM^T=A

3.

for all x $\ne$ 0 (x^TAx > 0) because x^TAx=x^T(MM_T)x=y^Ty ( Let y=M^Tx ) > 0

If y= (y₁, ... ,y_n)^T

y^Ty=y²₁+y²₂+ ... +y²_n $=\sum_{i=1}^n y^2_i > 0$

<PS>

1.

If A is positive definite then all its eigenvalues are positive and real.

2.

Positive definite matrix , not all entries are positive.

[Thm] Cholesky Decomposition If A is positive definite , then A can be factored into A=GG^T where G is a lower triangular matrix and has positive entries on its main diagonal element .

Example :

(1) M= $\left [ \matrix{ 1 & 0 & 0 \cr 1 & 1 & 0 \cr 1 & 1 & 1 \cr } \right ]$ M^T= $\left [ \matrix{ 1 & 1 & 1 \cr 0 & 1 & 1 \cr 0 & 0 & 1 \cr } \right ]$

then A=MM^T= $\left [ \matrix{ 1 & 1 & 1 \cr 1 & 2 & 2 \cr 1 & 2 & 3 \cr } \right ]$  is  a  positive  definite.

If A= $\left [ \matrix{ 1 & 1 & 1 \cr 1 & 2 & 2 \cr 1 & 2 & 3 \cr } \right ]$  is  a  positive  definite , then  if  A=GG^T G=M

A=LU= $\left [ \matrix{ 1 & 0 & 0 \cr l_{21} & 1 & 0 \cr l_{31} & l_{32} & 1 \cr }... ... u_{12} & u_{13} \cr 0 & u_{22} & u_{23} \cr 0 & 0 & u_{33} \cr } \right ]$

= $\left [ \matrix{ 1 & 0 & 0 \cr l_{21} & 1 & 0 \cr l_{31} & l_{32} & 1 \cr }... ...\over u_{11} \cr 0 & 1 & u_{23} \over u_{22} \cr 0 & 0 & 1 \cr } \right ]$

= $\left [ \matrix{ 1 & 0 & 0 \cr l_{21} & 1 & 0 \cr l_{31} & l_{32} & 1 \cr }... ... \over u_{11} \cr 0 & 1 & u_{23} \over u_{22} \cr 0 & 0 & 1 \cr } \right ]$

Example :

M= $\left [ \matrix{ 1 & 2 \cr 2 & 4 \cr } \right ]$ and A=MM^T= $\left [ \matrix{ 5 & 11 \cr 11 & 25 \cr } \right ]$

The LU Decomposition of

A= $\left [ \matrix{ 1 & 0 \cr 11 \over 5 & 1 \cr } \right ] \left [ \matrix{ 5 & 11 \cr 0 & 4 \over 5 \cr } \right ]$ = $\left [ \matrix{ 1 & 0 \cr 11 \over 5 & 1 \cr } \right ] \left [ \matrix... ...cr } \right ] \left [ \matrix{ 1 & 11 \over 5 \cr 0 & 1 \cr } \right ]$

= $\left [ \matrix{ 1 & 0 \cr 11 \over 5 & 1 \cr } \right ] \left [ \matrix... ...\cr } \right ] \left [ \matrix{ 1 & 11 \over 5 \cr 0 & 1 \cr } \right ]$

= $\left [ \matrix{ \sqrt 5 & 0 \cr {11 \sqrt 5} \over 5 & {2 \sqrt 5} \over 5 ... ...x{ \sqrt 5 & {11 \sqrt 5} \over 5 \cr 0 & {2 \sqrt 5} \over 5 \cr } \right ]$ = GG^T
Cholesky Decomposition

A is position Definite

$\Leftrightarrow$ A can be decomposed in exact one way A=GG^Twhere G is lower triangular with positive diagonal.

[ $\Leftarrow$ MM^T=A Then A is positive Definite

In particular M=G. ]

A=GG^T

A=(a_ij)= $\left [ \matrix{ a_{11} & a_{12} & \cdots & a_{1n} \cr a_{21} & a_{22} & \cd... ...dots & \cdots & \vdots \cr a_{n1} & a_{n2} & \cdots & a_{nn} \cr } \right ]$ = $\left [ \matrix{ g_{11} & 0 & 0 & 0 \cr g_{21} & g_{22} & 0 & 0 \cr \vdots &... ...& g_{2n} \cr 0 & 0 & \ddots & \vdots \cr 0 & 0 & 0 & g_{nn} \cr } \right ]$

First , find the first colume of G .

STEP 1.

a₁₁=g₁₁ g₁₁ $\Rightarrow$ g₁₁= $+ \sqrt a_{11}$ (a_i1=g_i1 g₁₁)

STEP 2.

$\left \{\matrix{ a_{21}=g_{21} g_{11} \Rightarrow g_{21}={a_{21} \over g_{1... ... a_{n1}=g_{n1} g_{11} \Rightarrow g_{n1}={a_{n1} \over g_{11}} \cr }\right$

Second , slove the second colume .

a₂₂=g₂₁ g₂₁ + g₂₂ g₂₂ $\rightarrow$ g₂₂= $+\sqrt {a_{22}-g^2_{21}}$

In general , For j=1 ...n ,

g_ii= $+ \sqrt {a_ja_j- \sum_{k=1}^{j-1} g^2_{jk}}$

g_ij= ${(a_{ij}- \sum_{k=1}^{j-1} g_{ik}g_{jk}) \over g_{jj}}$ , $i=j+1 \dots n$

(  Find  g_ii  ,  then  find  g_ij )

Example : A= $\left [ \matrix{ 4 & -2 & 4 & 2 \cr -2 & 10 & -2 & -7 \cr 4 & -2 & 8 & 4 \cr 2 & -7 & 4 & 7 \cr } \right ]$ = $\left [ \matrix{ g_{11} & 0 & 0 & 0 \cr g_{21} & g_{22} & 0 & 0 \cr g_{31} &... ...& g_{24} \cr 0 & 0 & g_{33} & g_{34} \cr 0 & 0 & 0 & g_{44} \cr } \right ]$

Phase 1. first colume

4=g²₁₁ $\rightarrow$ g₁₁= $+ \sqrt 4$ = 2

g₂₁= ${-2 \over 2}$ = -1 g₃₁= ${4 \over 2}$ =2

g₄₁= ${2 \over 2}$ =1

Phase 2. second colume

g₂₂= $\sqrt {a_{22}-g^2_{21}}$ = 3

g₃₂= ${(a_{32}-g_{31}g_{21}) \over g_{22}}$ = 0

g₄₂= -2

Note : 1. A positive definite $\Rightarrow$ a_ii > 0 for all i
2. a_ij not necessary $\geq$ 0

Algorithm ( Cholesky Decomposition )

for j=1 ...n

for n=1 ...j-1

a_jj $\leftarrow$ a_jj-a²_jk

a_jj $\leftarrow \sqrt(a_{jj})$

for i=j+1 ...n

for k=1 ...j-1

a_ij $\leftarrow$ a_ij-a_ik a_jk

a_ij $\leftarrow$ ${a_{ij} \over a_{jj}}$