tuto9_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
5
Uploaded by MinisterGorilla8297
MATH3230 Numerical Analysis
Tutorial 9 with solution
1
Recall:
1.
Discrete and continuous least-squares approximations:
(a)
Discrete least-squares approximations:
Let
A
be a
m
×
n
matrix, with
m > n
and now we consider a general linear system
Ax
=
b.
(1)
The least-squares solution seeks for some vector
x
that minimizes the error
(
Ax
−
b
)
in the least-squares
sense, that is
min
x
∈
R
n
?
Ax
−
b
?
2
.
We assume that the columns of
A
are linearly independent. We define
f
(
x
) =
?
Ax
−
b
?
2
.
The minimizer of
f
(
x
)
satisfies the normal equation
A
T
Ax
=
A
T
b.
(b)
Continuous least-squares approximations:
This method is an approximation of a general function
f
on an interval
[
a, b
]
.
For any two functions
f, g
∈
C
[
a, b
]
, we define their inner product as
〈
f, g
〉
=
ˆ
b
a
f
(
x
)
g
(
x
)
dx,
and the norm as
?
f
?
2
=
〈
f, g
〉
1
/
2
=
?
ˆ
b
a
f
2
(
x
)
dx
?
1
/
2
.
Let
P
n
be the set of all polynomials of degree
n
on
[
a, b
]
. Then we can define the continuous least-squares
approximation of a general function
f
on an interval
[
a, b
]
as follows: Find
p
n
∈
P
n
such that
?
p
n
−
f
?
2
= min
p
∈
P
n
?
p
−
f
?
2
.
p
n
∈
P
n
is the least-squares approximation of
f
(
x
)
on
[
a, b
]
if and only if the error function
p
n
−
f
is
orthogonal to the space
P
n
.
2.
Sensitivity of linear systems:
Consider solving the linear system (1). Because of the rounding errors, or the observation data errors, the
actual problem we are solving by computer is the perturbed system:
˜
A
˜
x
=
b.
Let
A
be a nonsingular matrix, and
˜
A
=
A
+
E
. If
Ax
=
b,
˜
A
˜
x
=
b,
b
∕
= 0
,
1
then we have
?
˜
x
−
x
?
?
˜
x
?
≤ ?
A
−
1
E
?
=
?
A
−
1
˜
A
−
I
?
.
In addition, if
?
A
−
1
E
?
<
1
, we have
?
˜
x
−
x
?
?
x
?
≤
?
A
−
1
E
?
1
− ?
A
−
1
E
?
.
The real number
κ
(
A
)
given by
κ
(
A
) =
?
A
??
A
−
1
?
is called the
condition number
of the matrix
A
. Note that
κ
(
A
)
≥
1
. Then we have
?
˜
x
−
x
?
?
x
?
≤
c
(
E
)
κ
(
A
)
?
E
?
?
A
?
=
c
(
E
)
κ
(
A
)
?
˜
A
−
A
?
?
A
?
,
where
c
(
E
) =
1
1
−
κ
(
A
)
?
E
?
?
A
?
>
1
.
The condition number gives a bound on how inaccurate the solution
x
will be after approximation.
If the
condition number is large, even a small error in
b
will cause a large error in
x
. If the condition number is
small, then the solution
x
will be stable.
2
Exercises:
Please do the star problems (*) in the tutorial class and finish the rest after the class.
1. Let
A
be a
m
×
n
matrix and consider a general linear system
Ax
=
b.
(2)
(a) Write down the di
ff
erences between the two systems: the square system with
m
=
n
and the non-square
system with
m > n
. When do these systems have a solution?
(b) Assume that
A
with
m > n
is full rank, we can find the least square solution
x
∗
which minimizes
?
Ax
−
b
?
2
. Prove that solving for
x
∗
is equivalent to solving the equation
A
T
Ax
=
A
T
b
. And explain
briefly the relation between the error vector
Ax
∗
−
b
and the space spanned by the column vectors of
A
.
(c) * Solve the following linear system using the Cholesky factorization in the least-squares sense.
Ax
=
b,
where
A
=
?
?
?
?
1
−
1
1
−
1
1
1
0
1
−
1
0
1
−
1
?
?
?
?
and
b
=
?
?
?
?
2
1
1
−
2
?
?
?
?
.
Solution.
(a)-(b) See lecture notes.
(c) Note that
A
T
A
=
?
?
2
−
2
0
−
2
4
−
2
0
−
2
4
?
?
Then
A
T
A
=
?
?
√
2
−
√
2
0
0
√
2
−
√
2
0
0
√
2
?
?
T
?
?
√
2
−
√
2
0
0
√
2
−
√
2
0
0
√
2
?
?
=
R
T
R
First we solve
Ry
=
A
T
b
, we have
y
=
?
?
?
1
√
2
−
1
√
2
3
√
2
?
?
?
2
then we solve
Rx
=
y
, we have
x
=
?
?
3
2
1
3
2
?
?
2. * Apply the continuous least-squares approximation to the function
f
(
x
) =
e
x
for
x
∈
[0
,
1]
. The basis of
P
n
is
{
φ
k
(
x
) =
x
k
}
n
k
=0
and consider the case
n
= 1
. Find
p
1
∈
P
1
such that
?
p
1
−
f
?
2
= min
p
∈
P
1
?
p
−
f
?
2
.
Solution.
Let
p
1
=
c
0
+
c
1
x
. Then the error function is given by
E
(
c
0
, c
1
) :=
?
f
(
x
)
−
(
c
0
+
c
1
x
)
?
2
L
2
=
ˆ
b
a
(
f
(
x
)
−
c
0
−
c
1
x
)
2
d
x
=
ˆ
b
a
?
f
(
x
)
2
−
2
f
(
x
) (
c
0
+
c
1
x
) +
?
c
2
0
+ 2
c
0
c
1
x
+
c
2
1
x
2
??
d
x
=
ˆ
b
a
f
(
x
)
2
d
x
−
2
c
0
ˆ
b
a
f
(
x
)d
x
−
2
c
1
ˆ
b
a
xf
(
x
)d
x
+
c
2
0
(
b
−
a
) +
c
0
c
1
?
b
2
−
a
2
?
+
1
3
c
2
1
?
b
3
−
a
3
?
.
Then we optimize
E
over
c
0
and
c
1
, i.e., we find the values of
c
0
and
c
1
for which
∂
E
∂
c
0
=
∂
E
∂
c
1
= 0
.
We have
c
0
(
b
−
a
) +
1
2
c
1
?
b
2
−
a
2
?
=
ˆ
b
a
f
(
x
)d
x,
1
2
c
0
?
b
2
−
a
2
?
+
1
3
c
1
?
b
3
−
a
3
?
=
ˆ
b
a
xf
(
x
)d
x.
That is
?
(
b
−
a
)
1
2
?
b
2
−
a
2
?
1
2
?
b
2
−
a
2
?
1
3
?
b
3
−
a
3
?
? ?
c
0
c
1
?
=
?
´
b
a
f
(
x
)d
x
´
b
a
xf
(
x
)d
x
?
.
Hence
?
1
1
2
1
2
1
3
? ?
c
0
c
1
?
=
?
e
−
1
1
?
.
The desired solution is
c
0
= 4e
−
10
,
c
1
= 18
−
6e
.
3. Given an invertible
n
×
n
matrix
A
. Let
b, b
δ
, x, x
δ
∈
R
n
\{
0
}
be four non-zero vectors such that
Ax
=
b
and
Ax
δ
=
b
δ
.
(a) Show that there exists
κ
(
A
)
>
0
such that
1
κ
(
A
)
?
b
−
b
δ
?
?
b
δ
?
≤
?
x
−
x
δ
?
?
x
δ
?
≤
κ
(
A
)
?
b
−
b
δ
?
?
b
δ
?
,
where
?
·
?
is a given norm.
(b)
Let
A
=
?
20
25
15
20
?
.
Find
?
κ
(
A
)
?
in the following norm
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
i.
1
-norm.
ii. sup-norm.
(c) Based on the statement in
(
a
)
, explain the importance of the condition number
κ
(
A
)
for solving the
system
Ax
=
b
.
Solution.
(a) Let us first recall that
?
Ax
? ≤ ?
A
??
x
?
∀
x
∈
R
n
.
Using this inequality and the fact that
b
=
Ax
b
δ
=
Ax
δ
,
we have
i.
?
b
−
b
δ
? ≤ ?
A
???
x
−
x
δ
?
ii.
?
b
δ
? ≤ ?
A
??
x
δ
?
iii.
?
x
−
x
δ
? ≤ ?
A
−
1
??
b
−
b
δ
?
iv.
?
x
δ
? ≤ ?
A
−
1
??
b
δ
?
Using (i) and (iv), we have
?
b
−
b
δ
?
·
1
?
b
δ
?
1
?
A
??
A
−
1
?
≤ ?
x
−
x
δ
?
·
1
?
x
δ
?
.
which is the first inequality required. Then using (ii) and (iii), we have
?
x
−
x
δ
?
·
1
?
x
δ
?
≤ ?
A
−
1
??
b
−
b
δ
??
A
?
·
1
?
b
δ
?
,
which is the second inequality required.
(b)
i.
κ
(
A
) =
?
A
?
1
?
A
−
1
?
1
= 45
×
1
.
8 = 81
.
ii.
κ
(
A
) =
?
A
?
∞
?
A
−
1
?
∞
= 45
×
1
.
8 = 81
.
(c) See lecture notes.
4. Consider
Ax
=
b
. THe perturbation occurs on both
A
and
b
, which means
Ax
=
b
⇒
(
A
+
∆
A
) (
x
+
∆
x
) =
b
+
∆
b.
(a) If
?
A
?
<
1
,
?
I
?
= 1
, prove that
?
?
?
(
I
−
A
)
−
1
?
?
?
≤
1
1
− ?
A
?
.
(b) If
?
A
?
<
1
, prove that
?
I
+
A
?
is invertible.
(c) * Suppose
?
?
A
−
1
?
?
?
∆
A
?
<
1
.
Using the result of (a) and (b), prove that
?
∆
x
?
?
x
?
≤
κ
(
A
)
1
−
κ
(
A
)
?
∆
A
?
?
A
?
?
?
∆
A
?
?
A
?
+
?
∆
b
?
?
b
?
?
.
Solution.
(a) Since
?
A
?
<
1
and
?
A
n
? ≤ ?
A
?
n
, we have
?
A
n
? →
0
when
n
→ ∞
.
Let
s
N
=
N
?
k
=0
A
k
4
Then
s
N
(
I
−
A
)
=
I
−
A
N
+1
s
N
=
(
I
−
A
)
−
1
(
I
−
A
N
+1
)
when
N
→ ∞
,
A
N
+1
→
0
(Since
?
A
N
?
= 0
i
ff
A
N
≡
0
)
⇒
lim
N
→∞
s
N
= (
I
−
A
)
−
1
.
So
?
?
∞
k
=0
A
k
?
=
?
(
I
−
A
)
−
1
?
. Moreover, we have
?
∞
?
k
=0
A
k
?
≤
∞
?
k
=0
?
A
k
?
=
?
I
?
+
?
A
?
+
· · ·
=
1
1
− ?
A
?
(b)
∀
x
∕
= 0
,
?
(
I
+
A
)
x
?
=
?
x
+
Ax
? ≥ ?
x
? − ?
Ax
? ≥ ?
x
? − ?
A
??
x
?
=
?
x
?
(1
− ?
A
?
)
>
0
.
So
I
+
A
is
invertible.
(c) Since
(
A
+
∆
A
)(
x
+
∆
x
) =
b
+
∆
b
, we have
(
A
+
∆
A
)
∆
x
=
∆
b
−
∆
Ax
(3)
We have
?
(
I
+
A
−
1
∆
A
)
−
1
? ≤
1
1
− ?
A
−
1
??
∆
A
?
(4)
By (3),
∆
x
=
(
A
+
∆
A
)
−
1
(
∆
b
−
∆
Ax
)
=
(
I
+
A
−
1
∆
A
)
−
1
A
−
1
(
∆
b
−
∆
Ax
)
⇒ ?
∆
x
?
≤
?
(
I
+
A
−
1
∆
A
)
−
1
??
A
−
1
?
(
?
∆
b
?
+
?
∆
A
??
x
?
)
By (4),
?
∆
x
?
≤
?
A
−
1
?
1
− ?
A
−
1
??
∆
A
?
(
?
∆
b
?
+
?
∆
A
??
x
?
)
⇒
?
∆
x
?
?
x
?
≤
?
A
−
1
?
1
− ?
A
−
1
??
∆
A
?
(
?
∆
A
?
+
?
∆
b
?
?
x
?
)
≤
?
A
−
1
?
1
− ?
A
−
1
??
∆
A
?
(
?
∆
A
?
+
?
∆
b
??
A
?
?
b
?
)
≤
κ
(
A
)
1
−
κ
(
A
)
?
∆
A
?
?
A
?
(
?
∆
A
?
?
A
?
+
?
∆
b
?
?
b
?
)
5