Civil Engineering Reference
In-Depth Information
2.2 Remark.
In practice the line search is done only approximately. There are two
possibilities:
(1) Find a point for which the directional derivative is small, say
|
d
k
∇
f(x
k
+
td
k
)
|
<
1
4
|
d
k
∇
f(x
k
)
|
.
(2) First choose a reasonable step size
t
, and continue halving it until the corre-
sponding improvement in the function value is at least one quarter of what we
would get by linearization, i.e., until
t
4
|
d
k
∇
f(x
k
)
|
.
f(x
k
+
td
k
)
≤
f(x
k
)
−
This version of the gradient method leads to global convergence:
either there
is some subsequence which converges to a point x
∈
M with
0
,orthe
sequence tends to the boundary of M.
The latter cannot happen if
f
is greater than
f(x
0
)
as we approach
∂M
(or as
x
→∞
∇
f(x)
=
, respectively).
Gradient Methods and Quadratic Functions
Rather than presenting a general proof of convergence, we instead focus on a
more detailed examination of the case of quadratic functions. In this case the rate
of convergence is determined by the size of
κ(A)
.
As a measure of distance, we use the
energy norm
=
√
x
Ax.
x
A
:
(
2
.
6
)
If
x
∗
is a solution of the equation
Ax
=
b
, then as in II.2.4
1
f(x)
=
f(x
∗
)
+
2
x
−
x
∗
2
A
.
(
2
.
7
)
Now (2.4) and (2.5) imply
f(x
k
+
1
)
=
f(x
k
+
α
k
d
k
)
1
2
(x
k
+
α
k
d
k
)
A(x
k
+
α
k
d
k
)
−
b
(x
k
+
α
k
d
k
)
=
f(x
k
)
+
α
k
d
k
(Ax
k
−
b)
+
=
1
2
α
k
d
k
Ad
k
(d
k
d
k
)
2
d
k
Ad
k
1
2
=
f(x
k
)
−
.
Combining this with (2.7), we have
(d
k
d
k
)
2
x
k
+
1
−
x
∗
2
A
=
x
k
−
x
∗
2
A
−
d
k
Ad
k
.
Search WWH ::
Custom Search