Civil Engineering Reference
In-Depth Information
Problems
n
3.9
1. In addition, let
A, B
and
C
be positive
definite
n
×
n
matrices. Suppose that the matrices
A
and
B
commute. Using as few
arithmetic operations as possible, compute
A
-orthogonal directions
d
0
,d
1
,...,d
k
,
which span the same space as
(a)
z, Az, A
2
z,...,A
k
z
,
(b)
z, CAz, (CA)
2
z,...,(CA)
k
z
,
(c)
z, Bz, B
2
z,...,B
k
z
.
How many matrix-vector multiplications, and how many scalar products are
needed? When can
A
2
-orthogonal directions be computed simply?
Suppose
z
∈ R
and
k
≥
3.10
Let
S
={
a
0
}∪
[
a, b
] with 0
<a
0
<a<b
and
κ
=
b/a
. Show that there
exists a polynomial
p
of degree
k
such that
√
κ
−
k
−
1
2
b
a
0
1
p(
0
)
=
1
and
|
p(x)
|≤
√
κ
+
for
x
∈
S.
1
3.11
How does the iteration in Problem 2.9 perform using conjugate directions?
Does the difficulty discussed in Problem 2.9 disappear if we use conjugate direc-
tions?
3.12
Let
κ(A)
=
1000. How many iteration steps are needed in the gradient and
the conjugate gradient methods in order to reduce the error by 0.01 in the worst
case?
3.13
The choice of
α
k
guarantees that
d
k
g
k
+
1
=
0, independent of the roundoff
errors in the previous steps. Thus,
d
k
+
1
A
is just the distance of the vector
g
k
+
1
from the one-dimensional linear space span[
d
k
]. Show that
1
κ(A)
1
/
2
g
k
+
1
A
.
d
k
+
1
A
≥
Hint: First compare the Euclidean norm of the vectors
d
k
+
1
and
g
k
+
1
.
Search WWH ::
Custom Search