An Upper Bound on the Error at Each Iteration When Finding a Root or Fixed Point
Generally, the exact value of the root
of a function
(or the exact value of a fixed point) is unknown, so it is impossible to evaluate the error of iterative methods,
but
we can find an upper bound on the error using the difference between two iterates.
Definition: A sequence
is called contractive if there exists a positive constant
such that
Theorem
Ifis contractive with constant
then,
i. is convergent with limit
ii.
is bounded above and
Hence, forgiven,
provides an upper bound on
the error at
iteration
Example:
The first five
are given below.
| 0.0000 | 1.0000 | 2.0000 | 3.0000 | 4.0000 | 5.0000 |
| 1.0000 | 1.5000 | 1.3710 | 1.4297 | 1.4077 | 1.4169 |
|
| 0.5000 | 0.1290 | 0.0587 | 0.0220 | 0.0092 |
|
|
| 0.2580 | 0.4550 | 0.3750 | 0.4180 |
| 0.4142 | 0.0858 | 0.0392 | 0.0155 | 0.0065 | 0.0027 |
K can be hard to find. It can be shown that we can take
from the above table so
