[go: up one dir, main page]
Scribd
Upload
48 views14 pages

7-Numerical Methods-LU Decomposition

The document discusses LU Decomposition as a method to implement Gauss elimination for solving systems of linear algebraic equations. It explains how LU decomposition separates the matrix elimination from right-hand-side manipulations, allowing for efficient evaluations of multiple right-hand-side vectors. The document outlines the procedure for LU decomposition, including the two-step strategy of decomposing the matrix and using substitution to find the solution.

Uploaded by

sraiden49
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
48 views14 pages

7-Numerical Methods-LU Decomposition

The document discusses LU Decomposition as a method to implement Gauss elimination for solving systems of linear algebraic equations. It explains how LU decomposition separates the matrix elimination from right-hand-side manipulations, allowing for efficient evaluations of multiple right-hand-side vectors. The document outlines the procedure for LU decomposition, including the two-step strategy of decomposing the matrix and using substitution to find the solution.

Uploaded by

sraiden49
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

THE UNIVERSITY OF JORDAN

School of Engineering
Department of Civil Engineering
(0951301): Numerical Methods
Dr. Ramia Al-Ajarmeh

LU Decomposition
LU Decomposition
Refer to the Textbook, Chapter 10

• Show how Gauss elimination method can be implemented as an


LU Decomposition.

• Gauss elimination is designed to solve systems of linear algebraic


equations:
[A]{x}={B}

• It becomes insufficient when solving equations with the same


coefficients [A], but with different right-hand-side constants (the
b's).
LU Decomposition

• LU decomposition methods separate the time-consuming the


eliminations of the matrix [A] from the manipulations of the right-
side {B}.

• Once [A] has been "decomposed", multiple right-hand-side


vectors can be evaluated in an efficient manner.

• Gauss-elimination can be expressed as LU-decomposition.


LU Decomposition Procedure

[A]{X}={B} re-arrange to [A]{X}-{B}=0

• It can be expressed as upper triangular system (such as the first


step of Gauss elimination:
𝑢11 𝑢12 𝑢13 𝑥1 𝑑1
0 𝑢22 𝑢23 𝑥2 = 𝑑2
0 0 𝑢33 𝑥3 𝑑3

• Eliminations is used to reduce the system to upper triangular form:


[U]{X}-{D}=0

• Assume that there is a lower diagonal matrix with 1’s on the


diagonal:
1 0 0
𝐿 = 𝑙21 1 0
𝑙31 𝑙32 1
LU Decomposition Procedure

𝐿 𝑈 𝑋 − 𝐷 = [A]{X} − {B}
𝐿 𝑈 = 𝐴
&
𝐿 {𝐷} = 𝐵
LU Decomposition Procedure

Two-step strategy:

1. LU decomposition step: [A] is factored or "decomposed" into lower


[L] and upper [U] triangular matrices.

2. Substitution step: [L] & [U] are used to determine a solution {X} for
right-hand-side {B}:
• generate an intermediate vector{D} by forward substitution
• result is substitution into [U]{X}-{D}=0
LU Decomposition Procedure

LU decomposition with Gauss Elimination:

𝑎11 𝑎12 𝑎13 𝑥1 𝑏1


𝑎21 𝑎22 𝑎23 𝑥2 = 𝑏2
𝑎31 𝑎32 𝑎33 𝑥3 𝑏3

𝑎11 𝑎12 𝑎13


𝑈 = 0 𝑎22 ′ 𝑎23 ′
0 0 𝑎33 ′′
LU Decomposition Procedure

1st step:
𝒂
➢ to multiply row 1 by the factor 𝒇𝟐𝟏 = 𝟐𝟏 & subtract the result
𝒂𝟏𝟏
from row 2 to eliminate 𝑎21
𝒂𝟑𝟏
➢ Similarly, row 1 is multiplied by 𝒇𝟑𝟏 = & subtract the result
𝒂𝟏𝟏
from row 3 to eliminate 𝑎31

𝒂𝟑𝟐 ′
➢ The final step is to multiply the modified second row by 𝒇𝟑𝟐 =
𝒂𝟐𝟐 ′
& subtract the result from row 3 to eliminate 𝑎32 ′
LU Decomposition Procedure

𝑎11 𝑎12 𝑎13


[A] can be written as: 𝑓21 𝑎22 ′ 𝑎23 ′
𝑓31 𝑓32 𝑎33 ′′

𝐴 → 𝐿 𝑈
where:

𝑎11 𝑎12 𝑎13


𝑈 = 0 𝑎22 ′ 𝑎23 ′
0 0 𝑎33 ′′

&

1 0 0
𝐿 = 𝑓21 1 0
𝑓31 𝑓32 1
LU Decomposition

Example:
Solve the following system using LU decomposition method:

3𝑥1 − 0.1𝑥2 − 0.2𝑥3 = 7.85 ⋯1


0.1𝑥1 + 7𝑥2 − 0.3𝑥3 = −19.3 ⋯2
0.3𝑥1 − 0.2𝑥2 + 10𝑥3 = 71.4 ⋯3
LU Decomposition
Example Solution:

1- LU Decomposition with Gauss Elimination:


LU Decomposition
Example Solution (continued):
LU Decomposition
Example Solution (continued):

2- The Substitution Step:

[L] {D} = {B}

Solve for d’s:


LU Decomposition
Example Solution (continued):

2- The Substitution Step:

[U] {X} = {D}

You might also like