Civil Engineering Reference
In-Depth Information
Since
d
k
=−
A(x
k
−
x
∗
)
,wehave
x
k
−
x
∗
2
A
=
(A
−
1
d
k
)
A(A
−
1
d
k
)
=
d
k
A
−
1
d
k
and
1
.
(d
k
d
k
)
2
d
k
Ad
k
d
k
A
−
1
d
k
x
k
+
1
−
x
∗
2
A
=
x
k
−
x
∗
2
A
−
(
2
.
8
)
We now estimate the quantity in the square brackets. If we compute the
condition number of a matrix with respect to the Euclidean vector norm, then for
positive definite matrices, it coincides with the
spectral condition number
λ
max
(A)
λ
min
(A)
.
κ(A)
=
2.3 The Kantorovich Inequality.
Let A be a symmetric, positive definite matrix
with spectral condition number κ. Then
2
√
κ
−
1
)
2
(x
Ax)(x
A
−
1
x)
(x
x)
2
2
√
κ
+
≤
(
1
1
(
2
.
9
)
for every vector x
=
0
; cf. Kantorovich [1948].
[
λ
max
(A) λ
min
(A)
]
1
/
2
, and let
λ
i
be an eigenvalue of
A
. It follows
Proof.
Set
µ
:
=
that
κ
−
1
/
2
≤
λ
i
/µ
≤
κ
1
/
2
. Since the function
z
→
z
+
z
−
1
is monotone on the
interval
(
0
,
1
)
and for
z>
1, we know that
λ
i
/µ
+
µ/λ
i
≤
κ
1
/
2
+
κ
−
1
/
2
.
1
µ
A
+
µA
−
1
, and the
The eigenvectors of
A
are also eigenvectors of the matrix
eigenvalues of the latter are bounded by
κ
1
/
2
+
κ
−
1
/
2
. Hence, it follows from
Courant's maximum principle that
1
µ
(x
Ax)
+
µ(x
A
−
1
x)
≤
(κ
1
/
2
+
κ
−
1
/
2
)(x
x)
1
n
. The variant of Young's inequality
ab
≤
4
(
|
a
|+|
b
|
)
2
holds for all
x
∈ R
now
yields
4
1
µ
(x
Ax)
+
µ(x
A
−
1
x)
2
1
1
(x
Ax)(x
A
−
1
x)
≤
4
(κ
1
/
2
+
κ
−
1
/
2
)
2
(x
x)
2
,
≤
and the proof is complete.
The left-hand side of (2.9) attains its maximum when the vector
x
contains
only components from the eigenvectors that are associated to the largest and the
smallest eigenvalue and if the two contributions have the same size. Furthermore,
Example 2.5 below shows that the bound is sharp.
Now combining (2.8), (2.9), and the identity 1
4
/(
√
κ
+
√
κ
−
1
)
2
−
=
(κ
−
1
)
2
/(κ
+
1
)
2
,weget
Search WWH ::
Custom Search