Page 191 - Applied Numerical Methods Using MATLAB

180 NONLINEAR EQUATIONS
Proof. The Mean Value Theorem (MVT) (Appendix A) says that for any two
o
points x 0 and x , there exists a point x between the two points such that

o
o
o

g(x 0 ) − g(x ) = g (x)(x 0 − x ); x 1 − x o (4.1.3),(4.1.1) g (x)(x 0 − x ) (1)
=
Taking the absolute value of both sides of (1) and using the precondition
(4.1.2) yields
o o o
|x 1 − x |≤ α|x 0 − x | < |x 0 − x | (2)
o
which implies that x 1 is closer to x than x 0 and thus still stays inside the interval
I. Applying this successively, we can get
o o 2 o k o
|x k − x |≤ α|x k−1 − x |≤ α |x k−2 − x |≤ · · ·≤ α |x 0 − x |→ 0as k →∞ (3)

o
which implies that the iterative sequence {x k } generated by (4.1.3) converges to x .

(Q) Is there any possibility that the fixed point is not unique—that is, more than one
point satisfy Eq. (4.1.1) and so the iterative scheme may get confused among the
several fixed points?
(A) It can never happen, because the points x o1 and x o2 satisfying Eq. (4.1.1) must
be the same:

o2
o1
o2
o2
o2
|x o1 − x |=|g(x ) − g(x )|≤ α|x o1 − x | (α < 1); |x o1 − x |= 0; x o1 ≡ x o2
In order to solve a nonlinear equation f(x) = 0 using the iterative method based on
this fixed-point theorem, we must somehow arrange the equation into the form
x = g(x) (4.1.4)

and start the iteration (4.1.3) with an initial value x 0 , then continue until some stop-
ping criterion is satisfied; for example, the difference |x k+1 − x k | between the successive
iteration values becomes smaller than some predefined number (TolX) or the iteration
number exceeds some predetermined number (MaxIter). This scheme is cast into the
MATLAB routine “fixpt()”. Note that the second output argument (err) is never the
real error—that is, the distance to the true solution—but just the last value of |x k+1 − x k |
as an error estimate. See the following remark and examples.

Remark 4.1. Fixed-Point Iteration. Noting that Eq. (4.1.4) is not unique for a

given f(x) = 0, it would be good to have g(x) such that |g (x)| < 1inside
o
the interval I containing its fixed point x which is the solution we are look-
ing for. It may not be so easy, however, to determine whether |g (x)| < 1is