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

2µ

M T 2

n=0 (·n ψn ) ¤ ( ψn ’ ψn+1 + n 2)

2 2

ˆ

θ2 n=0

M

2µ

= ψ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