Majorizing sequences and error bounds for iterative methods

Abstract:

Given a sequence $\{ {x_n}\} _{n = 0}^\infty$ in a Banach space, it is well known that if there is a sequence $\{ {t_n}\} _{n = 0}^\infty$ such that $\left \| {{x_{n + 1}} - {x_n}} \right \| \leqslant {t_{n + 1}} - {t_n}$ and $\lim {t_n} = {t^\ast } < \infty$, then $\{ {x_n}\} _{n = 0}^\infty$ converges to some ${x^\ast }$ and the error bounds $\left \| {{x^\ast } - {x_n}} \right \| \leqslant {t^\ast } - {t_n}$ hold. It is shown that certain stronger hypotheses imply sharper error bounds, \[ \left \| {{x^\ast } - {x_n}} \right \| \leqslant \frac {{{t^\ast } - {t_n}}}{{{{({t_n} - {t_{n - 1}})}^\mu }}}{\left \| {{x_n} - {x_{n - 1}}} \right \|^\mu } \leqslant \frac {{{t^\ast } - {t_n}}}{{{{({t_1} - {t_0})}^\mu }}}{\left \| {{x_1} - {x_0}} \right \|^\mu },\quad \mu \geqslant 0.\] Representative applications to infinite series and to iterates of types ${x_n} = G{x_{n - 1}}$ and ${x_n} = H({x_n},{x_{n - 1}})$ are given for $\mu = 1$. Error estimates with $0 \leqslant \mu \leqslant 2$ are shown to be valid and optimal for Newton iterates under the hypotheses of the Kantorovich theorem. The unified convergence theory of Rheinboldt is used to derive error bounds with $0 \leqslant \mu \leqslant 1$ for a class of Newton-type methods, and these bounds are shown to be optimal for a subclass of methods. Practical limitations of the error bounds are described.