2. Example `25x+15y-5z=35,15x+18y+0z=33,-5x+0y+11z=6`
Solve Equations 25x+15y-5z=35,15x+18y+0z=33,-5x+0y+11z=6 using Cholesky decomposition method
Solution:
Total Equations are `3`
`25x+15y-5z=35 -> (1)`
`15x+18y+0z=33 -> (2)`
`-5x+0y+11z=6 -> (3)`
Now converting given equations into matrix form
`[[25,15,-5],[15,18,0],[-5,0,11]] [[x],[y],[z]]=[[35],[33],[6]]`
Now, A = `[[25,15,-5],[15,18,0],[-5,0,11]]`, X = `[[x],[y],[z]]` and B = `[[35],[33],[6]]`
Cholesky decomposition : `A=L*L^T`, Every symmetric positive definite matrix A can be decomposed into a product of a unique lower triangular matrix L and its transpose.
Here matrix is symmetric positive definate, so Cholesky decomposition is possible.A matrix is positive definite if it's symmetric and all its pivots are positive. | `A` | = | | `25` | `15` | `-5` | | | `15` | `18` | `0` | | | `-5` | `0` | `11` | |
|
Test method 1: Existence of all Positive Pivots. First apply Gaussian Elimination method to find Pivots | `A` | = | | `25` | `15` | `-5` | | | `15` | `18` | `0` | | | `-5` | `0` | `11` | |
|
`R_2 larr R_2-3/5xx R_1` | = | | `25` | `15` | `-5` | | | `0` `0=15-3/5xx25`
`R_2 larr R_2-3/5xx R_1` | `9` `9=18-3/5xx15`
`R_2 larr R_2-3/5xx R_1` | `3` `3=0-3/5xx-5`
`R_2 larr R_2-3/5xx R_1` | | | `-5` | `0` | `11` | |
|
`R_3 larr R_3+1/5xx R_1` | = | | `25` | `15` | `-5` | | | `0` | `9` | `3` | | | `0` `0=-5+1/5xx25`
`R_3 larr R_3+1/5xx R_1` | `3` `3=0+1/5xx15`
`R_3 larr R_3+1/5xx R_1` | `10` `10=11+1/5xx-5`
`R_3 larr R_3+1/5xx R_1` | |
|
`R_3 larr R_3-1/3xx R_2` | = | | `25` | `15` | `-5` | | | `0` | `9` | `3` | | | `0` `0=0-1/3xx0`
`R_3 larr R_3-1/3xx R_2` | `0` `0=3-1/3xx9`
`R_3 larr R_3-1/3xx R_2` | `9` `9=10-1/3xx3`
`R_3 larr R_3-1/3xx R_2` | |
|
Pivots are the first non-zero element in each row of this eliminated matrix. `:.` Pivots are `25,9,9` Here all pivots are positive, so matrix is positive definate.
Test method 2: Determinants of all upper-left sub-matrices are positive. | `A` | = | | `25` | `15` | `-5` | | | `15` | `18` | `0` | | | `-5` | `0` | `11` | |
|
| `25` | `15` | `-5` | | | `15` | `18` | `0` | | | `-5` | `0` | `11` | |
| `=2025` |
Dets are `25,225,2025` Here all determinants are positive, so matrix is positive definate.
Formula
`l_(ki)=(a_(ki) - sum_{j=1}^{i-1} l_(ij) * l_(kj))/(l_(ii))`
`l_(kk)=sqrt(a_(kk)-sum_{j=1}^{k-1} l_(kj)^2)`
`l_(11)=sqrt(a_(11))=sqrt(25)=5`
`l_(21)=(a_(21))/l_(11)=(15)/(5)=3`
`l_(22)=sqrt(a_(22)-l_(21)^2)=sqrt(18-(3)^2)=sqrt(18-9)=3`
`l_(31)=(a_(31))/l_(11)=(-5)/(5)=-1`
`l_(32)=(a_(32)-l_(31) xx l_(21))/l_(22)=(0-(-1)xx(3))/(3)=(0-(-3))/(3)=1`
`l_(33)=sqrt(a_(33)-l_(31)^2-l_(32)^2)=sqrt(11-(-1)^2-(1)^2)=sqrt(11-2)=3`
| So `L` | = | | `l_(11)` | `0` | `0` | | | `l_(21)` | `l_(22)` | `0` | | | `l_(31)` | `l_(32)` | `l_(33)` | |
| = | |
Now, `Ax=B`, and `A=LL^T => LL^Tx=B`
let `L^Tx=y`, then `Ly=B =>`
| `5` | `0` | `0` | | | `3` | `3` | `0` | | | `-1` | `1` | `3` | |
| `xx` | | = | |
| | | `` | `5y_1` | | | | | `=` | `35` | `` | | | | `` | `3y_1` | `+` | `3y_2` | | | `=` | `33` | `` | | | | `-` | `y_1` | `+` | `y_2` | `+` | `3y_3` | `=` | `6` | `` |
Now use forward substitution method
From (1)
`5y_1=35`
`=>5y_1=35`
`=>y_1=(35)/(5)=7`
From (2)
`3y_1+3y_2=33`
`=>3(7)+3y_2=33`
`=>21+3y_2=33`
`=>3y_2=33-21=12`
`=>y_2=(12)/(3)=4`
From (3)
`-y_1+y_2+3y_3=6`
`=>-(7)+(4)+3y_3=6`
`=>-3+3y_3=6`
`=>3y_3=6+3=9`
`=>y_3=(9)/(3)=3`
Now, `L^Tx=y`
| `5` | `3` | `-1` | | | `0` | `3` | `1` | | | `0` | `0` | `3` | |
| `xx` | | = | |
| | | `` | `5x` | `+` | `3y` | `-` | `z` | `=` | `7` | `` | | | | | | `` | `3y` | `+` | `z` | `=` | `4` | `` | | | | | | | | `` | `3z` | `=` | `3` | `` |
Now use back substitution method
From (3)
`3z=3`
`=>z=(3)/(3)=1`
From (2)
`3y+z=4`
`=>3y+(1)=4`
`=>3y+1=4`
`=>3y=4-1=3`
`=>y=(3)/(3)=1`
From (1)
`5x+3y-z=7`
`=>5x+3(1)-(1)=7`
`=>5x+2=7`
`=>5x=7-2=5`
`=>x=(5)/(5)=1`
Solution by Cholesky Decomposition method is
`x=1,y=1,z=1`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
