NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

1102-20-1110 August 19, 1952 1888

THE CONVERGENCE OF NUMERICAL ITERATION

by

H.A.Antosiewicz* and J.M. Hammer sley

##

Montana State College and

^American University, Washington, D.C.

University of Oxford and

American University, Washington,©. C.

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

The publication, reprinting, or reprod Approved for public release by the

ed unless permission Is obtained In writing from the Office of the Director, Natli Director of the National Institute of is not needed, however, by an agency for which a report has been specifically f that particular report for Its own use. Standards and Technology (NIST) on October 9, 2015
. \ f

i,

/, )
THE CONVERGENCE OF NUMERICAL INTERATION^

by H» A0 Antoslewic&^/snd J®Mo HanimerslejJ/

Iteration arises frequently In the numerical solution of

anolted problem®*, Textbook statements on its convergence are

often cursory® We hop© this note will put students on their

guard*

We shall deal with solving

(1) X s® t{x)

by means of the iteration

(2) x « f(x }

n n-i

starting with a trial value xQ

o For simplicity we shall suppose

throughout that f(x) Is a real function of a real variable xh that (1) possesses a unique solution , and that this solution Is

x Oo From the point of view of theory , there is no reel, loss

of generality involved In this last assumption* for if x » a 4 0

were the solution of x ® f(x) 8 then x » 0 would be the solution

of x = g(x) w f(x+a) - ao To avoid triviality^ we shall also

suppose throughout that the Initial valu© xQ Is not s ero©

We shall confine our attention to equations in a single

unknown xj the difficulties in the case of several unknowns are

more s sv©r®

l/fo.r> pirfomedT under contract with the National Bureau of

Standards*

;|/Montana State College | and the American University*, Washington

Bo Go

J^/Univ os Oxfordi and the American University, Washington^

D o 0 o

=2=

Under certain conditions upon the function f(x) the

sequence x , x., 8 Xg, 0 « » will converge to the desired-root x ® Oo

We naif invite the reader„ who cares to test his appreciation

of such conditions a to answer the following questions (with the

aid of a textbook if he so desires)

Question Is Is it sufficient for convergence that, for some

given k-<l# |f 8 {§)l< k for every f in a (sufficiently small)

neighborhood of the root x ® 0, and that x0 shall belong to -

this neighborhood? (In this question and subsequently., f * ( ac)

denotes the derivative of f(x)»)

Question 2% Is It sufficient for divergence that, for some given

Is >i9 |f 8 (§) |->k for every £ in a ( sufficiently small) neighbor*

& t

hood of the root x « Q 3 and that xn

shall belong to this

neighborhood?

Question 3s Consider two functions f-

? {x) and f 9 (x) which both

satisfy the conditions of Qus stion 1 in a c ommon ( sufficiently

small) neighborhood of the root x » 0; and suppose that k-j and kg

are respectively the smaller possible values of k for* which

these conditions hold [i 6 e 0 there exist no constants k® < k s

k^ < k.., such that | f

8 ^(^) | <k8 ^

5 |f 8 0 (Jp| 4k8 ^ for all € In this

neighborhood] «, If k^ < kc_ and if both Iterative processes converge,

will the convergence for f-^(x) be more rapid than that for fp(x)?

Question 4g la it necessary for convergence that ail conditions

stated in Question 1 shall hold (a) if we restrict ourselves to

the class of functions f(x) which are everywhere differentiable

or (b) if we make no such restriction?

Question 5? Gan a condition bearing on the derivative f

8 (0) or

on a Lipsehitg condition solely at the root x « 0 be sufficient

for convergence?

Question St Are there any functions f(x) s satisfying f(0) » 0

and being discontinuous both to the left and to the right of

x * 0 f) for which the iteration (2) converges whenever lies

within some (sufficiently small) neighborhood of x «* 0?

The answer to Question 1 is ?1 Y©So sl Thbs is a corollary

to our answer to Question 5 (see below},,

The answer to Question 2 is aa shown by the example

r2x |x| < 1

(3) f(x) -

'

tp 1*1 > i

for which the process (2) converges®

The answer to Question 3 is 3{ No 0

*s The example

X

^ ^s \

t V
-
isx . |x|< (l-k)A

(4) fix) =4|^/

Z

(lac+23!i-2)

2

(3toc+2lt-2)/(:l»fe)

2

Sl-k) A^W^Cl-fcS/k.

1^0 |x|Z2(l«3c)A

satisfies the conditions of Question If and yet just one step .

of the iteration will yield the desired root x « 0 if

l£ > l/d+J-jx^l )o

whereas an Infinite number .of . steps is needed if

k < 1/{ X“H|- | Xq 1 5 ®

The convergence is slowest in the case k *• l/(l+T§l x | ) o The

smallness of k* therefore* is not always a guarantee for rapid

convergence as stated in textbooks » In practice* however* it

will be a useful (though not wholly reliable) guide for the

rapidity of convergence®

The answer to Question 4(a) is ‘•No-o" The process (2)

converges (very rapidly! for the function

( 5 ) f(x)

!xp't/2 e~x

sinjfj* x/0

0* X as 0

whatever the Initial value x

Q

i although f 8 (x.) is unbounded In

©very neighborhood of the root x ® 0® A fortiori ,, the answer to

Question 4(b) is **NOo® In one of the standard textbooks the

conditions of Question 1 ar© falsely stated as both .necessary

and sufficient for convergence®

Th© answer to Question 5 is “Yes® 81 It is sufficient for

convergence that* solely at the root x « 0* f(x) shall satisfy

a Lipschits condition (of order unity) with an Implied constant

k less than unity? that is to say
>
(6) II® sup JJLLiyJ 4 fe < le

X --^0 B

j' Fors If (6) holdsj, there exists a number cf > 0 such that

II® sup

x<f0

whenever l*n-^ ! £ «/\ Therefore^ If x0 belongs to the neighborhood

fix) can satisfy (6) even though it may not be differentiable;

Ife however, fix) Is differentiable s we say replace' { 6) by the

condition

Condition (?) Is a weaker condition than the condition of Question

lo Th© reader will also notice that the foregoing proof of

convergence is very much shorter than the corresponding proofs of

weaker versions found In some textbooks® Finallys a condition

sufficient for convergence need hold only 'at a single pointy as

we have Just shown; but an analoguous condition sufficient for

divergence woulds It eeem^ have to hold for all points; see for

instance example (3) above®

Th© answer to Question 6 Is ^Yee®*5 A simple example Is

(?) I r » ( ©•) I < io

if x Is rational

Her© at most two steps yield the root x ® 0 8 although the function

is everywhere discontinuous® A more elaborate example shows