Solving systems of linear equations using Cholesky decomposition method Example 6x+15y+55z=76,15x+55y+225z=295,55x+225y+979z=1259

We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more

AtoZmath.com

College Algebra

Matrix & Vector

Numerical Methods

Statistical Methods

Operation Research

Home > Matrix & Vector calculators > Solving systems of linear equations using Cholesky decomposition method example

11. Cholesky decomposition method example ( Enter your problem )

( Enter your problem )

Example `6x+15y+55z=76,15x+55y+225z=295,55x+225y+979z=1259`
Example `25x+15y-5z=35,15x+18y+0z=33,-5x+0y+11z=6`

Other related methods

10. LU decomposition using Crout's method
(Previous method)

2. Example `25x+15y-5z=35,15x+18y+0z=33,-5x+0y+11z=6`
(Next example)

1. Example `6x+15y+55z=76,15x+55y+225z=295,55x+225y+979z=1259`

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`

`=6`

	`6`	`15`
	`15`	`55`

`=105`

	`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)`

Here `A`

=

	6	15	55
	15	55	225
	55	225	979

`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

=

	6	15	55
	15	55	225
	55	225	979

and `A`

=

	6	15	55
	15	55	225
	55	225	979

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`

	`y_1`
	`y_2`
	`y_3`

=

	`76`
	`295`
	`1259`

			``	`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`

	`x`
	`y`
	`z`

=

	`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 Submit Here

10. LU decomposition using Crout's method
(Previous method)

2. Example `25x+15y-5z=35,15x+18y+0z=33,-5x+0y+11z=6`
(Next example)

Share this solution or page with your friends.

College Algebra

Copyright © 2023. All rights reserved. Terms, Privacy