Transcript LU decomposition - National Cheng Kung University

Numerical Analysis
EE, NCKU
Tien-Hao Chang (Darby Chang)
1
In the previous slide

Accelerating convergence
– linearly convergent
– Newton’s method on a root of
multiplicity >1
– (exercises)

Proceed to systems of equations
– linear algebra review
– pivoting strategies
2
In this slide

Error estimation in system of equations
– vector/matrix norms

LU decomposition
– split a matrix into the product of a lower and a
upper triangular matrices
– efficient in dealing with a lots of right-hand-side
vectors

Direct factorization
– as an systems of n2+n equations
– Crout decomposition
– Dollittle decomposition
3
3.3
Vector and Matrix Norms
4
Vector and matrix norms


Pivoting strategies are designed to
reduce the impact roundoff error
The size of a vector/matrix is
necessary to measure the error
5
Vector norm
6
The two most commonly used norms in practice
7
8
9
Vector norm
Equivalent

One of the other uses of norms is to
establish the convergence
lim x
k 

(k )
x 0
Two trivial questions:
– converge or diverge in different norms?
– converge to different limit values in different
norms?

The answer to both is no
– all vector norms are equivalent
10
11
The Euclidean norm and the maximum norm are equivalent
12
Matrix norms

Similarly, there are various matrix
norms, here we focus on those norms
related to vector norms
– natural matrix norms
13
Matrix norms
Natural matrix norms
14
15
Natural matrix norms
Computing maximum norm
16
17
18
Natural matrix norms
Computing Euclidean norm


Is, unfortunately, not as
straightforward as computing
maximum matrix norms
Requires knowledge of the
eigenvalues of the matrix
19
Eigenvalue review
later
20
21
Eigenvalue review
22
23
http://thomashawk.com/hello/209/1017/1024/Jackson%20Running.jpg
In action
24
25
26
Any Questions?
3.3 Vector and Matrix Norms
27
3.4
Error Estimates and Condition Number
28
Error estimation



A linear system Ax=b, and x’ is an
approximate solution
The error, e=x’-x, cannot be directly
computed (x is never known)
The residue vector, r=Ax’-b, can be
easily computed
– r=0  x’=x  e=0
29
Any Questions?
30
Is ||r|| a good estimation of ||e||?



Construct the relationship between r
hint#1
and e
hint#2
From the
definition
hint#3 hint#4
answer
r=Ax’-b=Ax’-Ax=A(x’-x)=Ae
31
32
33
34
35
Condition number
36
37
Perturbations (skipped)
.
.
.
38
Any Questions?
3.4 Error Estimates and Condition
Number
39
3.5
LU Decomposition
40
LU decomposition
Motivation

Gaussian elimination solve a linear system,
Ax=b, with n unknowns
– (2/3)n3 + (3/2)n2 – (7/6)n
– with back substitution
– the minimum number of operations

If there are a lots of right-hand-side vectors
– how many operations for a new RHS?
– with Gaussian elimination, all operations are
also carried out on the RHS
41
LU decomposition


Given a matrix A, a lower triangular
matrix L and an upper triangular matrix
U for which LU=A are said to form an LU
decomposition of A
Here we replace mathematical
descriptions with an example to show
how use Gaussian elimination to obtain
an LU decomposition
42
43
44
45
46
Any Questions?
47

Is there any other LU decompositions
in addition to using modified
Gaussian elimination?
– degree of freedoms (number of
unknowns) hint
– An2, LUn2+n

Direct factorization (3.6)
answer
– as an systems of n2+n equations
48
Solving a linear system


A  LU
When a new RHS comes
– Ax=b  PAx=Pb  LUx=Pb
– with z=Ux, actually to solve Lz=Pb and
Ux=z
• both steps are easy
• notice that Pb does not require real matrixvector multiplication
49
50
Solving a linear system
In summary

Anyway, the two-step algorithm (LU
decomposition) is superior to
Gaussian elimination with back
substitution
51
Any Questions?
3.5 LU Decomposition
52
3.6
Direct Factorization
53

Is there any other LU decompositions
in addition to using modified
Gaussian elimination?
– degree of freedoms (number of
unknowns)
– An2, LUn2+n

Direct factorization (3.6)
– as an systems of n2+n equations
Recall that
http://www.dianadepasquale.com/ThinkingMonkey.jpg
54
Direct factorization

Just add more n equations
– ex: diagonal must be 1

Crout decomposition
– lii=1 for each i=1, 2, …, n

Dollittle decomposition
– uii=1 for each i=1, 2, …, n
55
56
57
58
59
Any Questions?
3.6 Direct Factorization
60