<< . .

. 18
( : 26)



. . >>





Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




115
BROYDEN™S METHOD

The main result in this section, Theorem 7.1.1 and its corollary for linear
problems, are used to prove superlinear convergence for Broyden™s method in
this chapter and many other quasi-Newton methods. See [61], [28], [62], and
[64] for several more examples. Our formulation of the Dennis“Mor´ result is
e
a bit less general than that in [60] or [63].
Theorem 7.1.1. Let the standard assumptions hold, let {Bn } be a sequence
of nonsingular N — N matrices, let x0 ∈ RN be given and let {xn }∞ be given
n=1
— for any n. Then x ’ x— q-superlinearly if
by (7.5). Assume that xn = x n
— and the Dennis“Mor´ condition (7.6) holds.
and only if xn ’ x e
Proof. Since
’F (xn ) = Bn sn = F (x— )sn + En sn
we have

(7.7) En sn = ’F (x— )sn ’ F (xn ) = ’F (x— )en+1 + F (x— )en ’ F (xn ).

We use the fundamental theorem of calculus and the standard assumptions to
obtain
1

(F (x— ) ’ F (x— + ten ))en dt
F (x )en ’ F (xn ) =
0
and hence
F (x— )en ’ F (xn ) ¤ γ en 2 /2.
Therefore, by (7.7)

En sn ¤ F (x— )en+1 + γ en 2 /2.
(7.8)

Now, if xn ’ x— q-superlinearly, then for n su¬ciently large

(7.9) sn /2 ¤ en ¤ 2 sn .

The assumption that xn = x— for any n implies that the sequence

(7.10) νn = en+1 / en

is de¬ned and and νn ’ 0 by superlinear convergence of {xn }. By (7.9) we
have
en+1 = νn en ¤ 2νn sn ,
and hence (7.8) implies that

En sn ¤ (2 F (x— ) νn + γ en ) sn

which implies the Dennis-Mor´ condition (7.6).
e
Conversely, assume that xn ’ x— and that (7.6) holds. Let

En sn
µn = .
sn



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




116 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

We have, since
En sn = (Bn ’ F (x— ))sn = ’F (xn ) ’ F (x— )sn ,
(7.11)
F (x— )’1 ’1 ¤ F (x— )sn ¤ En sn + F (xn )
sn
(7.12)
= µn sn + F (xn ) .
Since µn ’ 0 by assumption,
µn ¤ F (x— )’1 ’1
(7.13) /2,
for n su¬ciently large. We assume now that n is large enough so that (7.13)
holds. Hence,
sn ¤ 2 F (x— )’1 F (xn ) .
(7.14)
Moreover, using the standard assumptions and (7.11) again,
¤ F (xn ) + F (x— )sn + (F (x— ) ’ F (xn ))sn
F (xn ) + F (xn )sn
(7.15)
¤ (µn + γ en ) sn .
Since xn ’ x— by assumption, ·n ’ 0 where
·n = 2 F (x— )’1 (µn + γ en ).
Combining (7.14) and (7.15) implies that
(7.16) F (xn ) + F (xn )sn ¤ ·n F (xn ) ,
which is the inexact Newton condition. Since ·n ’ 0, the proof is complete
by Theorem 6.1.2.

7.2. Convergence analysis
Our convergence analysis is based on an approach to in¬nite-dimensional
problems from [97]. That paper was the basis for [168], [104], and [115], and
we employ notation from all four of these references. We will use the l2 norm
throughout our discussion. We begin with a lemma from [104].
ˆ
Lemma 7.2.1. Let 0 < θ < 1 and let
ˆ ˆ
{θn }∞ ‚ (θ, 2 ’ θ).
n=0

Let { n }∞ ‚ RN be such that
n=0

< ∞,
n2
n

and let {·n }∞ be a set of vectors in RN such that ·n is either 1 or 0 for
2
n=0
all n. Let ψ0 ∈ RN be given. If {ψn }∞ is given by
n=1
T
(7.17) ψn+1 = ψn ’ θn (·n ψn )·n + n

then
T
(7.18) lim ·n ψn = 0.
n’∞




Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




117
BROYDEN™S METHOD

Proof. We ¬rst consider the case in which n = 0 for all n. In that case, we
can use the fact that
ˆ
θn (2 ’ θn ) > θ2 > 0
to show that the sequence {ψn } is bounded in l2 -norm by ψ0 and, in fact,
2

2 2 ’ θn (2 ’ θn )(·n ψn )2
T
ψn+1 ¤ ψn
2 2

ˆT
2 ’ θ2 (·n ψn )2
¤ ψn 2


¤ ψn 2 .
2

Therefore, for any M > 0,
M 2 2
ψ0 ’ ψM +1 ψ0 2
2 2
(·n ψn )2
T
¤ ¤ .
ˆ ˆ
θ2 θ2
n=0

We let M ’ ∞ to obtain

(·n ψn )2 < ∞.
T
(7.19)
n=0

Convergence of the series in (7.19) implies convergence to zero of the terms in
the series, which is (7.18).
To prove the result for n = 0 we use the inequality

b2
a2 b2
(7.20) ’ ¤a’ ,
2a
which is valid for a > 0 and |b| ¤ a. This inequality is used often in the analysis
of quasi-Newton methods [63]. From (7.20) we conclude that if ψn = 0 then

T 2 ’ θn (2 ’ θn )(·n ψn )2
T
ψn ’ θn (·n ψn )·n ¤ ψn
2 2


θn (2 ’ θn )(·n ψn )2
T
¤ ψn 2’ .
2 ψn 2
Hence if ψn = 0

θn (2 ’ θn )(·n ψn )2
T
(7.21) ψn+1 ¤ ψn 2’ + n 2.
2
2 ψn 2
Hence
2 ψn 2
(·n ψn )2 ¤
T
(7.22) ( ψn ’ ψn+1 + n 2 ),
2 2
θn (2 ’ θn )
which holds even if ψn = 0.
From (7.21) we conclude that

ψn+1 ¤ µ,
2




Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




118 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

where ∞
µ= + ψ0 2 .
i2
i=0
Hence
M

M T 2
n=0 (·n ψn ) ¤ ( ψn ’ ψn+1 + n 2)
2 2
ˆ
θ2 n=0

M

= ψ0 ’ ψM +1 +
2 2 n2
ˆ
θ2 n=0

2µ2
¤ .
ˆ
θ2
Hence (7.19) holds and the proof is complete.

7.2.1. Linear problems. We may use Lemma 7.2.1 to prove a result from
[130] on the convergence of Broyden™s method for linear problems. The role of
ˆ
the parameter θ and the sequence {θn } in Lemma 7.2.1 is nicely illustrated by
this application of the lemma.
In this section F (x) = Ax’b and Bn = A+En . The standard assumptions
in this case reduce to nonsingularity of A. Our ¬rst task is to show that
the errors in the Broyden approximations to A do not grow. This property,
called bounded deterioration [28], is an important part of the convergence
analysis. The reader should compare the statement of the result with that
in the nonlinear case.
In the linear case, the Broyden update has a very simple form. We will
consider a modi¬ed update

(y ’ Bc s)sT (Ax+ ’ b)sT
(7.23) B+ = Bc + θc = Bc + θc .
sT s sT s
If xc and Bc are the current approximations to x— = A’1 b and A and
s = x+ ’ xc then

y ’ Bc s = (Ax+ ’ Axc ) ’ Bc (x+ ’ xc ) = ’Ec s

and therefore
(y ’ Bc s)sT (Ec s)sT
(7.24) B+ = Bc + θc = Bc ’ θc .
s2 s2
2 2

Lemma 7.2.2. Let A be nonsingular, θc ∈ [0, 2], and xc ∈ RN be given. Let
Bc be nonsingular and let B+ be formed by the Broyden update (7.23). Then

(7.25) E+ ¤ Ec 2 .
2




Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




119
BROYDEN™S METHOD

Proof. By subtracting A from both sides of (7.24) we have

(Ec s)sT
E+ = Ec ’ θ c
s2
(7.26) 2

= Ec (I ’ θc Ps ),

where Ps is the orthogonal projector

ssT
(7.27) Ps = .
s22

This completes the proof as

E+ ¤ Ec I ’ θ c Ps
2 2 2

and I ’ θc Ps 2 ¤ 1 by orthogonality of Ps and the fact that 0 ¤ θc ¤ 2.
Now, θc can always be selected to make B+ nonsingular. In [130] one
suggestion was ±
 1, |γc | ≥ σ,
1 ’ sign(γc )σ
θc =
, otherwise,

1 ’ γc
where
(Bc y)T s
’1 (Bc As)T s
’1
γc = =
s2 s2
2 2
and σ ∈ (0, 1) is ¬xed. However the results in [130] assume only that the
ˆ
sequence {θn } satis¬es the hypotheses of Lemma 7.2.1 for some θ ∈ (0, 1) and
that θc is always chosen so that B+ is nonsingular.
For linear problems one can show that the Dennis“Mor´ condition implies
e
convergence and hence the assumption that convergence takes place is not
needed. Speci¬cally
Proposition 7.2.1. Let A be nonsingular. Assume that {θn } satis¬es
ˆ
the hypotheses of Lemma 7.2.1 for some θ ∈ (0, 1). If {θn } is such that
the matrices Bn obtained by (7.23) are nonsingular and {xn } is given by the
modi¬ed Broyden iteration
’1
(7.28) xn+1 = xn ’ Bn (Axn ’ b)

then the Dennis“Mor´ condition implies convergence of {xn } to x— = A’1 b.
e
We leave the proof as Exercise 7.5.1.
The superlinear convergence result is remarkable in that the initial iterate
need not be near the root.
Theorem 7.2.1. Let A be nonsingular. Assume that {θn } satis¬es the
ˆ
hypotheses of Lemma 7.2.1 for some θ ∈ (0, 1). If {θn } is such the matrices Bn
obtained by (7.23) are nonsingular then the modi¬ed Broyden iteration (7.28)
converges q-superlinearly to x— = A’1 b for every initial iterate x0 .



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




120 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

Proof. Our approach is to show that for every φ ∈ RN that
En sn
lim φT
(7.29) = 0.
sn 2
n’∞

Assuming that (7.29) holds, setting φ = ej , the unit vector in the jth
En sn
coordinate direction, shows that the j component of has limit zero.
sn 2
As j was arbitrary, we have
En sn
lim =0
sn 2
n’∞

which is the Dennis“Mor´ condition. This will imply q-superlinear convergence
e
by Theorem 7.1.1 and Proposition 7.2.1.
Let φ ∈ RN be given. Let
sn sT
n
Pn = .
sn 22

Since for all v ∈ RN and all n

<< . .

. 18
( : 26)



. . >>