1. Example `6x+15y+55z=76,15x+55y+225z=295,55x+225y+979z=1259`
1. Solve Equations 6x+15y+55z=76,15x+55y+225z=295,55x+225y+979z=1259 using Cholesky decomposition method
Solution:
Total Equations are `3`
`6x+15y+55z=76 -> (1)`
`15x+55y+225z=295 -> (2)`
`55x+225y+979z=1259 -> (3)`
Now converting given equations into matrix form
`[[6,15,55],[15,55,225],[55,225,979]] [[x],[y],[z]]=[[76],[295],[1259]]`
Now, A = `[[6,15,55],[15,55,225],[55,225,979]]`, X = `[[x],[y],[z]]` and B = `[[76],[295],[1259]]`
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` | = | | `6` | `15` | `55` | | | `15` | `55` | `225` | | | `55` | `225` | `979` | |
|
Test method 1: Existence of all Positive Pivots. First apply Gaussian Elimination method to find Pivots | `A` | = | | `6` | `15` | `55` | | | `15` | `55` | `225` | | | `55` | `225` | `979` | |
|
`R_2 larr R_2-5/2xx R_1` | = | | `6` | `15` | `55` | | | `0` `0=15-5/2xx6`
`R_2 larr R_2-5/2xx R_1` | `35/2` `35/2=55-5/2xx15`
`R_2 larr R_2-5/2xx R_1` | `175/2` `175/2=225-5/2xx55`
`R_2 larr R_2-5/2xx R_1` | | | `55` | `225` | `979` | |
|
`R_3 larr R_3-55/6xx R_1` | = | | `6` | `15` | `55` | | | `0` | `35/2` | `175/2` | | | `0` `0=55-55/6xx6`
`R_3 larr R_3-55/6xx R_1` | `175/2` `175/2=225-55/6xx15`
`R_3 larr R_3-55/6xx R_1` | `2849/6` `2849/6=979-55/6xx55`
`R_3 larr R_3-55/6xx R_1` | |
|
`R_3 larr R_3-5xx R_2` | = | | `6` | `15` | `55` | | | `0` | `35/2` | `175/2` | | | `0` `0=0-5xx0`
`R_3 larr R_3-5xx R_2` | `0` `0=175/2-5xx35/2`
`R_3 larr R_3-5xx R_2` | `112/3` `112/3=2849/6-5xx175/2`
`R_3 larr R_3-5xx R_2` | |
|
Pivots are the first non-zero element in each row of this eliminated matrix. `:.` Pivots are `6,35/2,112/3` Here all pivots are positive, so matrix is positive definate.
Test method 2: Determinants of all upper-left sub-matrices are positive. | `A` | = | | `6` | `15` | `55` | | | `15` | `55` | `225` | | | `55` | `225` | `979` | |
|
| `6` | `15` | `55` | | | `15` | `55` | `225` | | | `55` | `225` | `979` | |
| `=3920` |
Dets are `6,105,3920` 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(6)=2.4495`
`l_(21)=(a_(21))/l_(11)=(15)/(2.4495)=6.1237`
`l_(22)=sqrt(a_(22)-l_(21)^2)=sqrt(55-(6.1237)^2)=sqrt(55-37.5)=4.1833`
`l_(31)=(a_(31))/l_(11)=(55)/(2.4495)=22.4537`
`l_(32)=(a_(32)-l_(31) xx l_(21))/l_(22)=(225-(22.4537)xx(6.1237))/(4.1833)=(225-137.5)/(4.1833)=20.9165`
`l_(33)=sqrt(a_(33)-l_(31)^2-l_(32)^2)=sqrt(979-(22.4537)^2-(20.9165)^2)=sqrt(979-941.6667)=6.1101`
| So `L` | = | | `l_(11)` | `0` | `0` | | | `l_(21)` | `l_(22)` | `0` | | | `l_(31)` | `l_(32)` | `l_(33)` | |
| = | | 2.4495 | 0 | 0 | | | 6.1237 | 4.1833 | 0 | | | 22.4537 | 20.9165 | 6.1101 | |
|
| `L xx L^T` | = | | 2.4495 | 0 | 0 | | | 6.1237 | 4.1833 | 0 | | | 22.4537 | 20.9165 | 6.1101 | |
| `xx` | | 2.4495 | 6.1237 | 22.4537 | | | 0 | 4.1833 | 20.9165 | | | 0 | 0 | 6.1101 | |
| = | |
Now, `Ax=B`, and `A=LL^T => LL^Tx=B`
let `L^Tx=y`, then `Ly=B =>`
| `2.4495` | `0` | `0` | | | `6.1237` | `4.1833` | `0` | | | `22.4537` | `20.9165` | `6.1101` | |
| `xx` | | = | |
| | | `` | `2.4495y_1` | | | | | `=` | `76` | `` | | | | `` | `6.1237y_1` | `+` | `4.1833y_2` | | | `=` | `295` | `` | | | | `` | `22.4537y_1` | `+` | `20.9165y_2` | `+` | `6.1101y_3` | `=` | `1259` | `` |
Now use forward substitution method
From (1)
`2.4495y_1=76`
`=>2.4495y_1=76`
`=>y_1=76/2.4495=31.0269`
From (2)
`6.1237y_1+4.1833y_2=295`
`=>6.1237(31.0269)+4.1833y_2=295`
`=>190+4.1833y_2=295`
`=>4.1833y_2=295-190=105`
`=>y_2=105/4.1833=25.0998`
From (3)
`22.4537y_1+20.9165y_2+6.1101y_3=1259`
`=>22.4537(31.0269)+20.9165(25.0998)+6.1101y_3=1259`
`=>1221.6667+6.1101y_3=1259`
`=>6.1101y_3=1259-1221.6667=37.3333`
`=>y_3=37.3333/6.1101=6.1101`
Now, `L^Tx=y`
| `2.4495` | `6.1237` | `22.4537` | | | `0` | `4.1833` | `20.9165` | | | `0` | `0` | `6.1101` | |
| `xx` | | = | | `31.0269` | | | `25.0998` | | | `6.1101` | |
|
| | | `` | `2.4495x` | `+` | `6.1237y` | `+` | `22.4537z` | `=` | `31.0269` | `` | | | | | | `` | `4.1833y` | `+` | `20.9165z` | `=` | `25.0998` | `` | | | | | | | | `` | `6.1101z` | `=` | `6.1101` | `` |
Now use back substitution method
From (3)
`6.1101z=6.1101`
`=>z=6.1101/6.1101=1`
From (2)
`4.1833y+20.9165z=25.0998`
`=>4.1833y+20.9165(1)=25.0998`
`=>4.1833y+20.9165=25.0998`
`=>4.1833y=25.0998-20.9165=4.1833`
`=>y=4.1833/4.1833=1`
From (1)
`2.4495x+6.1237y+22.4537z=31.0269`
`=>2.4495x+6.1237(1)+22.4537(1)=31.0269`
`=>2.4495x+28.5774=31.0269`
`=>2.4495x=31.0269-28.5774=2.4495`
`=>x=2.4495/2.4495=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
|
