Page 179 - Matrices theory and applications

9. Iterative Methods for Linear Problems
162
2
1/2
wherewehave used the equality Aw, w
= A
w . Hence
2
2
2
1/2
≤ min{ I n + AQ(A) A
E(x k − ¯x)
e 0 | deg Q ≤ k − 1}
2
2
2
= E(e 0 )min{ρ(I n + AQ(A)) | deg Q ≤ k − 1},
since ρ(S)= S 2 holds for every real symmetric matrix.
From Lemma 9.5.1, we deduce an estimate of the error E(x k − ¯x)by
bounding the right-hand side by
2
min max |1+ tQ(t)| .
deg Q≤k−1 t∈[λ 1 ,λ n]
Classically, the minimum is reached for

2X − λ 1 − λ n
1+ XQ(X)= ω k T k ,
λ n − λ 1
where T k is a Chebyshev polynomial:

 cos k arccost if |t|≤ 1,
T k (t)= cosh k arcosht if t ≥ 1,
k

(−1) cosh k arcosh |t| if t ≤−1.
The number ω k is the number that furnishes the value 1 at X =0, namely
(−1) k
ω k =
.
T k λ n +λ 1
λ n −λ 1
Then
1
max |1+ tQ(t)| = |ω k | = .
[λ 1 ,λ n ] cosh k arcosh λ n +λ 1
λ n −λ 1
2
Hence E(x k − ¯x) ≤|ω k | E(e 0 ). However, if
λ n + λ 1
θ := arrcosh ,
λ n − λ 1
then |ω k | =(cosh kθ) −1 ≤ 2exp(−kθ), while exp(−θ) is the root, less than
one, of the quadratic polynomial
2
T − 2 λ n + λ 1 T +1.
λ n − λ 1
Setting K(A):= A 2 A −1 2 = λ n /λ 1 the condition number of A,we
obtain
& √ √
2
λ n − K(A) − 1
e −θ = λ n + λ 1 − λ n + λ 1 − 1= √ √ λ 1 = .
λ n − λ 1 λ n − λ 1 λ n + λ 1 K(A)+1
The final result is the following.