Nonlinear Algebraic Equations - Elements of Scientific Computing - page 118

Our aim is to analyze when and under what conditions the values f v k g generated
by ( 4.83 ) converge toward a solution v of ( 4.82 ). To answer this question we intro-
duce the concept of a contractive mapping . Here, we will refer to h D h. v / as a
contractive mapping on a closed interval I if

(a) j h. v / h. w / j ı j v w j for any v ; w 2 I ,where0<ı<1,and
(b) v 2 I ) h. v / 2 I for all v 2 I .

For functions, as we consider in this chapter, we could refer to h as a contractive
function. But it turns out that similar properties are useful for much more general
mappings and we therefore use the standard term contractive mapping.
But what kind of functions are contractive mappings? To answer this, it is useful
to recall the mean value theorem of calculus. It states that if f is a differentiable
function defined on an interval Œa; b, then there exists a c 2 Œa; b such that

f.b/ f.a/ D f 0 .c/.b a/: (4.84)

It follows from ( 4.84 )thath in ( 4.75 ) is a contractive mapping defined on an interval
I if

ˇ ˇ h 0 ./ ˇ ˇ <ı<1

for all 2 I;

(4.85)

and h. v / 2 I for all v 2 I .
We observed above that the equation (see ( 4.77 ))

x D sin.x=10/ (4.86)

could easily be solved by using the fixed-point iteration

x kC1 D sin.x k =10/; (4.87)

and we note that

h.x/ D sin.x=10/ (4.88)

is indeed contractive on I D Π1; 1 because
ˇ ˇ h 0 .x/ ˇ ˇ D ˇ ˇ ˇ ˇ

10 cos.x=10/ ˇ ˇ ˇ ˇ

1 1

10

(4.89)

and also

x 2 Π1; 1 ) sin.x=10/ 2 Π1; 1: (4.90)