§2. Absolutely convergent series
137
Theorem 12. Let I be a closed interval, f a map from I to I, and assume
that there exists a positive number q < 1 such that
(16.11)
If(x) - f(y)1 ~ qlx - yl
for all x, y E I. Then the equation f(x) = x has one and only one solution
in I and the sequence (10) converges to it for any Xo.
Indeed, put M = IXI - xol and apply (11) repeatedly, replacing x and y
by xp and Xp-l; we obtain
IXn - xn-ll ~ qlXn-1 - x n-21 ~ ... ~ qn-2lx2 - xII ~ Mqn-l.
Since q < 1, the sequence (xn ) converges to a limit x, by Theorem 11. Since
If(x) - f(xnl ~ qlx - xnl, the sequence with general term f(xn ) converges
to f(x). But f(x n ) = Xn+l converges to x. Therefore f(x) = x.
If y also satisfies f(y) = y, one has
Ix - yl = If(x) - f(y)1 ~ qlx - yl
and thus x = y since q < 1, qed.
In practice, the theorem is applied to functions possessing a derivative
J'(x) everywhere, and such that 1f'(x)1 ~ q for any x; the mean value theorem
(Chap. III, n° 16) shows that for all x and y, there exists a z between x and
y such that
f(x) - f(y) = (x - y)f'(z),
whence (11). There are many other methods of approximating roots of a
equation; the first truly effective one was discovered by Newton around 1665
and is in widespread use.
The idea of the method of iteration seems first to have appeared among
the Arabs in the IX th century42 d propos the equation
u - e. sin u = wt
(O
The method consists of choosing the function
f(u) =e.sinu+wt
and I = lR; since one has always I sin x - sin yl ~ Ix - yl - this is obvious
from the graph of the function sine - even without the mean value theorem,
the relation 0 < e < 1 allows one to apply this method.
42 Unless some day it is discovered, for example, that the Indians knew it before
the Arabs. The questions of priority being sometimes difficult to unravel even
when it concerns the XX th century, it is strongly advisable to show prudence in
what concerns times for which we have only very fragmentary information, for
lack of which a militant in a cause courts the risk of one day finding himself the
biter bit.
137
Theorem 12. Let I be a closed interval, f a map from I to I, and assume
that there exists a positive number q < 1 such that
(16.11)
If(x) - f(y)1 ~ qlx - yl
for all x, y E I. Then the equation f(x) = x has one and only one solution
in I and the sequence (10) converges to it for any Xo.
Indeed, put M = IXI - xol and apply (11) repeatedly, replacing x and y
by xp and Xp-l; we obtain
IXn - xn-ll ~ qlXn-1 - x n-21 ~ ... ~ qn-2lx2 - xII ~ Mqn-l.
Since q < 1, the sequence (xn ) converges to a limit x, by Theorem 11. Since
If(x) - f(xnl ~ qlx - xnl, the sequence with general term f(xn ) converges
to f(x). But f(x n ) = Xn+l converges to x. Therefore f(x) = x.
If y also satisfies f(y) = y, one has
Ix - yl = If(x) - f(y)1 ~ qlx - yl
and thus x = y since q < 1, qed.
In practice, the theorem is applied to functions possessing a derivative
J'(x) everywhere, and such that 1f'(x)1 ~ q for any x; the mean value theorem
(Chap. III, n° 16) shows that for all x and y, there exists a z between x and
y such that
f(x) - f(y) = (x - y)f'(z),
whence (11). There are many other methods of approximating roots of a
equation; the first truly effective one was discovered by Newton around 1665
and is in widespread use.
The idea of the method of iteration seems first to have appeared among
the Arabs in the IX th century42 d propos the equation
u - e. sin u = wt
(O
The method consists of choosing the function
f(u) =e.sinu+wt
and I = lR; since one has always I sin x - sin yl ~ Ix - yl - this is obvious
from the graph of the function sine - even without the mean value theorem,
the relation 0 < e < 1 allows one to apply this method.
42 Unless some day it is discovered, for example, that the Indians knew it before
the Arabs. The questions of priority being sometimes difficult to unravel even
when it concerns the XX th century, it is strongly advisable to show prudence in
what concerns times for which we have only very fragmentary information, for
lack of which a militant in a cause courts the risk of one day finding himself the
biter bit.