tuto8_sol_3230
pdf
keyboard_arrow_up
School
The Chinese University of Hong Kong *
*We aren’t endorsed by this school
Course
3230
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
7
Uploaded by MinisterGorilla8297
MATH3230 Numerical Analysis
Tutorial 8 with solution
1
Recall:
1.
LU
factorization with partial pivoting:
Idea:
Permute the rows so that the largest entry in magnitude in the column becomes the pivot.
Strategy:
At the
k
th stage of the
LU
factorization, suppose the matrix
A
becomes
A
k
= (
a
(
k
)
ij
)
.
Then
determine an index
p
k
for which
|
a
(
k
)
p
k
,k
|
is the largest among all
|
a
(
k
)
j,k
|
for
k
≤
j
≤
n
. Then interchange rows
k
and
p
k
before proceeding the next step of the factorization.
2
Exercises:
Please do the star problems (*) in the tutorial class and finish the rest after the class.
1.
(a) *Find the
LU
factorization of the given matrix.
A
=
?
?
?
?
?
?
1
2
2
3
5
2
6
6
10
12
2
6
9
22
21
3
10
22
69
63
5
12
21
63
75
?
?
?
?
?
?
(b) *Convert the
LU
factorization of the symmetric positive definite matrix
A
to the
LDU
factorization and
U
T
U
factorization.
Solution.
(a) Let
L
1
=
?
?
?
?
?
?
1
0
0
0
0
−
2
1
0
0
0
−
2
0
1
0
0
−
3
0
0
1
0
−
5
0
0
0
1
?
?
?
?
?
?
,
then
L
1
A
=
?
?
?
?
?
?
1
2
2
3
5
0
2
2
4
2
0
2
5
16
11
0
4
16
60
48
0
2
11
48
50
?
?
?
?
?
?
L
2
=
?
?
?
?
?
?
1
0
0
0
0
0
1
0
0
0
0
−
1
1
0
0
0
−
2
0
1
0
0
−
1
0
0
1
?
?
?
?
?
?
,
then
L
2
L
1
A
=
?
?
?
?
?
?
1
2
2
3
5
0
2
2
4
2
0
0
3
12
9
0
0
12
52
44
0
0
9
44
48
?
?
?
?
?
?
L
3
=
?
?
?
?
?
?
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
−
4
1
0
0
0
−
3
0
1
?
?
?
?
?
?
,
then
L
3
L
2
L
1
A
=
?
?
?
?
?
?
1
2
2
3
5
0
2
2
4
2
0
0
3
12
9
0
0
0
4
8
0
0
0
8
21
?
?
?
?
?
?
L
4
=
?
?
?
?
?
?
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
−
2
1
?
?
?
?
?
?
,
then
L
4
L
3
L
2
L
1
A
=
?
?
?
?
?
?
1
2
2
3
5
0
2
2
4
2
0
0
3
12
9
0
0
0
4
8
0
0
0
0
5
?
?
?
?
?
?
=
U
1
Let
L
= (
L
4
L
3
L
2
L
1
)
−
1
=
?
?
?
?
?
?
1
0
0
0
0
2
1
0
0
0
2
1
1
0
0
3
2
4
1
0
5
1
3
2
1
?
?
?
?
?
?
Then
A
=
LU
=
?
?
?
?
?
?
1
0
0
0
0
2
1
0
0
0
2
1
1
0
0
3
2
4
1
0
5
1
3
2
1
?
?
?
?
?
?
?
?
?
?
?
?
1
2
2
3
5
0
2
2
4
2
0
0
3
12
9
0
0
0
4
8
0
0
0
0
5
?
?
?
?
?
?
(b) By (a), we have in
LDU
:
D
=
?
?
?
?
?
?
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
4
0
0
0
0
0
5
?
?
?
?
?
?
and
U
=
?
?
?
?
?
?
1
2
2
3
5
0
1
1
2
1
0
0
1
4
3
0
0
0
1
2
0
0
0
0
1
?
?
?
?
?
?
And in
U
T
U
:
U
=
?
?
?
?
?
?
1
2
2
3
5
0
√
2
√
2
2
√
2
√
2
0
0
√
3
4
√
3
3
√
3
0
0
0
2
4
0
0
0
0
√
5
?
?
?
?
?
?
2. Let
A
be nonsingular and the
LU
factorization with pivoting takes the form:
U
=
L
n
−
1
P
n
−
1
· · ·
L
2
P
2
L
1
P
1
A,
where
L
i
are elementary matrices,
U
is an upper triangular matrix and
P
i
are permutation matrices for
pivoting.
(a) *Explain when it is necessary to do the
LU
factorization with partial pivoting.
(b) Write down the idea of the
LU
factorization with partial pivoting. Do this factorization for the following
matrix
A
and find each of the matrix
U
,
L
i
,
P
i
for
i
= 1
,
2
,
· · ·
, n
−
1
, where
n
is the row number of
A
.
A
=
?
?
?
?
?
?
3
6
2
5
1
5
5
2
4
4
6
6
8
2
2
4
7
9
3
8
5
3
5
7
2
?
?
?
?
?
?
.
(c) Denote
P
=
P
n
−
1
· · ·
P
1
.
Prove that
PA
=
LU
, where
L
is a lower triangular matrix with
1
as its
diagonal entries and all entries of
L
satisfy that
|
l
ij
|
≤
1
.
(d) Find
P
,
L
,
U
in (c) according to question (b) such that
PA
=
LU
, where
A
is the matrix in (b).
(e) Use the decomposition in (d) to solve the system
Ax
=
b
, where
A
is the one in (b) and
b
= (46
,
57
,
60
,
97
,
64)
T
.
Solution.
2
(a) When the absolute value of diagonal entry is too small at certain stage of the
LU
factorization, it may
force algorithm to stop or cause bu
ff
er overflow.
(b)
R
3
↔
R
1
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
?
?
?
?
?
?
3
6
2
5
1
5
5
2
4
4
6
6
8
2
2
4
7
9
3
8
5
3
5
7
2
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
5
5
2
4
4
3
6
2
5
1
4
7
9
3
8
5
3
5
7
2
?
?
?
?
?
?
LU
?
?
?
?
?
?
1
−
5
6
1
−
1
2
1
−
2
3
1
−
5
6
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
5
5
2
4
4
3
6
2
5
1
4
7
9
3
8
5
3
5
7
2
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
0
−
14
3
7
3
7
3
3
−
2
4
0
3
11
3
5
3
20
3
−
2
−
5
3
16
3
1
3
?
?
?
?
?
?
R
3
↔
R
2
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
0
−
14
3
7
3
7
3
3
−
2
4
0
3
11
3
5
3
20
3
−
2
−
5
3
16
3
1
3
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
0
−
14
3
7
3
7
3
3
11
3
5
3
20
3
−
2
−
5
3
16
3
1
3
?
?
?
?
?
?
LU
?
?
?
?
?
?
1
1
0
1
−
1
1
2
3
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
0
−
14
3
7
3
7
3
3
11
3
5
3
20
3
−
2
−
5
3
16
3
1
3
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
−
14
3
7
3
7
3
17
3
−
7
3
20
3
−
3
8
1
3
?
?
?
?
?
?
R
4
↔
R
3
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
−
14
3
7
3
7
3
17
3
−
7
3
20
3
−
3
8
1
3
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
−
14
3
7
3
7
3
−
3
8
1
3
?
?
?
?
?
?
LU
?
?
?
?
?
?
1
1
1
14
17
1
9
17
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
−
14
3
7
3
7
3
−
3
8
1
3
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
3
17
133
17
115
17
197
51
?
?
?
?
?
?
R
5
↔
R
4
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
3
17
133
17
115
17
197
51
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
115
17
197
51
3
17
133
17
?
?
?
?
?
?
LU
?
?
?
?
?
?
1
1
1
1
−
7
115
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
115
17
197
51
3
17
133
17
?
?
?
?
?
?
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
115
17
197
51
2618
345
?
?
?
?
?
?
3
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
(c) From pivoting form:
U
=
L
n
−
1
P
n
−
1
...L
2
P
2
L
1
P
1
A
Now we claim that there exists some
L
(
k
)
such that
L
n
−
1
P
n
−
1
...L
2
P
2
L
1
P
1
=
L
(
n
−
1)
L
(
n
−
2)
. . . L
(1)
P
n
−
1
P
n
−
2
. . . P
1
such that the structure of
L
(
k
)
is equal to
L
k
but with the subdiagonal entries permuted.
We prove the claim as follows: Define
L
(
n
−
1)
=
L
n
−
1
,
L
(
n
−
2)
=
P
n
−
1
L
n
−
2
P
−
1
n
−
1
,
L
(
n
−
3)
=
P
n
−
1
P
n
−
2
L
n
−
3
P
−
1
n
−
2
P
−
1
n
−
1
, . . .
we have
L
(
n
−
1)
L
(
n
−
2)
. . . L
(1)
P
n
−
1
P
n
−
2
. . . P
1
=
L
n
−
1
(
P
n
−
1
L
n
−
2
P
−
1
n
−
1
)(
P
n
−
1
P
n
−
2
L
n
−
3
P
−
1
n
−
2
P
−
1
n
−
1
)
. . . P
n
−
1
P
n
−
2
. . . P
1
=
L
n
−
1
P
n
−
1
L
n
−
2
P
n
−
2
. . . L
1
P
1
(1)
Therefore we have
U
= (
L
(
n
−
1)
L
(
n
−
2)
. . . L
(1)
)(
P
n
−
1
P
n
−
2
. . . P
1
)
A
As
L
(
k
)
has the same structure as
L
k
for all
k
, we can combine them to form a lower triangular matrix
with 1’s as diagonal entries. Therefore we have proved the result.
(d)
L
=
?
?
?
?
?
?
1
1
2
1
2
3
1
1
5
6
−
2
3
−
9
17
1
5
6
0
−
14
17
7
115
1
?
?
?
?
?
?
,
U
=
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
115
17
197
51
2618
345
?
?
?
?
?
?
,
P
=
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
(e) We use
Ax
=
b
to denote the system in (a). Applying
PA
=
LU
and now we solve
LUx
=
Pb.
Righthand-side is
Pb
=
?
?
?
?
?
?
1
1
1
1
1
?
?
?
?
?
?
?
?
?
?
?
?
46
57
60
97
64
?
?
?
?
?
?
=
?
?
?
?
?
?
60
46
97
64
57
?
?
?
?
?
?
and lefthand-side
LU
=
?
?
?
?
?
?
1
1
2
1
2
3
1
1
5
6
−
2
3
−
9
17
1
5
6
0
−
14
17
7
115
1
?
?
?
?
?
?
?
?
?
?
?
?
6
6
8
2
2
3
−
2
4
0
17
3
−
7
3
20
3
115
17
197
51
2618
345
?
?
?
?
?
?
Then we solve
x
=
U
−
1
L
−
1
Pb
=
U
−
1
?
?
?
?
?
?
1
−
1
2
1
−
2
3
−
1
1
−
5
6
2
3
9
17
1
−
5
6
0
14
17
−
7
115
1
?
?
?
?
?
?
?
?
?
?
?
?
60
46
97
64
57
?
?
?
?
?
?
=
U
−
1
?
?
?
?
?
?
60
16
41
2365
/
51
2618
/
69
?
?
?
?
?
?
=
?
?
?
?
?
?
1
2
3
4
5
?
?
?
?
?
?
4
3. Let
A
∈
R
n
×
n
be strictly column diagonally dominant, i.e., there holds
|
a
kk
|
>
?
j
∕
=
k
|
a
jk
|
,
∀
k
= 1
,
· · ·
, n.
(a) *Prove that a strictly diagonally dominant matrix is nonsingular.
(b) Prove that if the strictly diagonally dominant matrix is symmetric and with positive diagonal entries,
then it is positive definite.
(c) Show that if
LU
factorization with partial pivoting is applied to
A
, no row interchanges take place.
Solution.
(a) We can prove by contradiction. Suppose
A
is singular, then
A
T
is also singular. There exists
x
∕
= 0
such
that
A
T
x
= 0
.
Let
k
∈
{
1
,
2
, ..., n
}
be such that
|
x
k
|
= max
1
≤
j
≤
n
{|
x
j
|}
>
0
Since
A
T
x
= 0
, we have
n
?
j
=1
a
jk
x
j
=
0
a
kk
x
k
=
−
?
j
∕
=
k
a
jk
x
j
Take absolute value on both sides, we have
|
a
kk
x
k
|
=
?
?
?
?
?
?
?
j
∕
=
k
a
jk
x
j
?
?
?
?
?
?
⇒
|
a
kk
| |
x
k
|
≤
?
j
∕
=
k
|
a
jk
| |
x
j
|
⇒
|
a
kk
| |
x
k
|
≤
?
j
∕
=
k
|
a
jk
| |
x
k
|
|
a
kk
|
<
|
a
kk
|
Contradiction occurs. So
A
is non-singular.
(b) We can prove it by contradiction. Suppose
A
has a negative eigenvalue
λ
and let
u
be the corresponding
eigenvector. Note that
λ
and
u
are nonzero. Let
k
∈
{
1
,
2
, ..., n
}
be such that
|
u
k
|
= max
1
≤
j
≤
n
|
u
j
|
>
0
Then we have
Au
=
λ
u
⇒
(
a
kk
−
λ
)
u
k
=
−
?
j
∕
=
k
a
kj
u
j
Take absolute value on both sides, we have
|
a
kk
−
λ
| |
u
k
|
≤
?
j
∕
=
k
|
a
kj
| |
u
j
|
⇒
|
a
kk
−
λ
| |
u
k
|
≤
?
j
∕
=
k
|
a
kj
| |
u
k
|
⇒
|
a
kk
−
λ
|
≤
?
j
∕
=
k
|
a
kj
|
⇒
|
a
kk
−
λ
|
<
|
a
kk
|
5
Contradiction occurs.
(c) Since
|
a
11
|
>
?
j
∕
=1
|
a
j
1
|
, there is no need to interchange row for the first step. Then we do the Gaussian
elimination.
We denote the
A
(1)
be the matrix
A
after the first step Gaussian elimination.
Then we
obtain for
j >
1
,
a
(1)
ij
=
a
ij
−
a
i
1
a
11
a
1
j
. Hence,
∀
k >
1
,
|
a
(1)
kk
|
=
|
a
kk
−
a
k
1
a
11
a
1
k
|
≥
|
a
kk
|
−
|
a
k
1
a
11
||
a
1
k
|
>
?
i
∕
=
k
|
a
ik
|
−
|
a
k
1
a
11
||
a
1
k
|
=
?
i>
1
,i
∕
=
k
a
(1)
ik
(2)
Therefore
A
(1)
is also strictly diagonally dominant matrix.
The argument repeats and the result is
proved.
4. In this question, we want to prove that:
If
A
is nonsingular, then there exist permutation matrices
P
1
and
P
2
, a unit lower triangular matrix
L
, and a
nonsingular upper triangular matrix
U
such that
P
1
AP
2
=
LU.
Note that if
A
is nonsingular, then it has a nonzero entry.
So we can choose permutation matrices
P
′
1
and
P
′
2
such that the (1,1)-th position of
P
′
1
AP
′
2
is nonzero.
(a) Let
P
′
1
AP
′
2
=
?
a
11
A
12
A
21
A
22
?
=
?
1
0
L
21
I
?
·
?
u
11
U
12
0
?
A
22
?
. Show that
?
A
22
is nonsingular.
(b) Suppose there exists
?
P
1
and
?
P
2
such that
?
P
1
?
A
22
?
P
2
=
?
L
?
U,
where
?
L
is a unit lower triangular matrix and
?
U
is a nonsingular upper triangular matrix. Show that
there exits permutation matrices
P
1
and
P
2
, such that
P
1
AP
2
=
?
1
0
?
P
1
L
21
?
L
?
?
u
11
U
12
?
P
2
0
?
U
?
.
(c) Using (a) and (b) with inductive argument, prove the theorem stated above.
Solution.
(a) Since
det(
P
′
1
AP
′
2
) =
±
det(
A
)
∕
= 0
and also
det(
P
′
1
AP
′
2
)
=
det
?
1
0
L
21
I
?
·
det
?
u
11
U
12
0
?
A
22
?
=
u
11
·
det(
?
A
22
)
Moreover
P
′
1
AP
′
2
=
?
a
11
A
12
A
21
A
22
?
=
?
1
0
L
21
I
?
·
?
u
11
U
12
0
?
A
22
?
=
?
u
11
U
12
L
21
u
11
L
21
U
12
+
?
A
22
?
Therefore we have
a
11
=
u
11
∕
= 0
. So
?
A
22
is invertible.
6
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
(b) Note
P
′
1
AP
′
2
=
?
1
0
L
21
I
? ?
u
11
U
12
0
?
P
T
1
?
L
?
U
?
P
T
2
?
=
?
1
0
L
21
I
? ?
1
0
0
?
P
T
1
?
L
? ?
u
11
U
12
0
?
U
?
P
T
2
?
=
?
1
0
L
21
?
P
T
1
?
L
?
?
u
11
U
12
?
P
2
0
?
U
?
?
1
0
0
?
P
T
2
?
=
?
1
0
0
?
P
T
1
? ?
1
0
?
P
1
L
21
?
L
?
?
u
11
U
12
?
P
2
0
?
U
?
?
1
0
0
?
P
T
2
?
so we get a desired factorization of
A
:
P
1
AP
2
=
??
1
0
0
?
P
1
?
P
′
1
?
A
?
P
′
2
?
1
0
0
?
P
2
??
=
?
1
0
?
P
1
L
21
?
L
?
?
u
11
U
12
?
P
2
0
?
U
?
(c) Using (a) and (b) and repeat the argument on the submatrix. The statement is proved.
7