Advanced Numerical Methods for Finding Fixed Points Without Linear Equations

Among the various numerical methods, those designed to find fixed points of a function without relying on linear equations are particularly useful. Specifically, functions that have a fixed point a where f(a) a are of great interest. These methods are typically nonlinear and can be derived from an auxiliary function G(x) such that G(a) a.

One such method is the simple iteration, where one sets up an iterative process described by x_{k 1} G(x_k). While simple, this method often converges slowly and is not always the most effective approach, especially in more complex scenarios. However, it is sometimes the most practical option.

Understanding Iteration Order

The performance of an iterative method can be quantified using the concept of iteration order. An iteration procedure is said to be of order m if for some constant K, the following approximately holds as k rightarrow infty: x_{k 1} - a K (x_k - a)^m [x_k - a^{m-1}]

For a simple iteration, the accuracy of the k 1-th iterate is only a fixed multiple of the accuracy of the k-th iterate. In contrast, higher-order iterations can lead to dramatic improvements in accuracy. For example, an iteration of order two will approximately double the accuracy of each successive iterate, and an order three iteration will approximately triple it.

Classical Iteration Functions

Two well-known examples of higher-order iterations are the Newton-Raphson iteration and the Steffensen iteration. The Newton-Raphson iteration is given by:

G(x) frac{xf(x) - f(x)}{f(x) - 1}

and the Steffensen iteration by:

G(x) frac{xf(x) - f(x^2)}{f(x)f(x) - 2xf(x)}

Both of these methods are of second order, meaning they can significantly improve the accuracy of the iterates. Notably, the Steffensen iteration does not require the differentiation of f(x), which can be an advantage in cases where derivatives are difficult to obtain.

Higher-Order Derivative-Free Iterations

In his 1970 paper, J. Foncannon outlined a method for constructing higher-order derivative-free iteration processes, which are extensions of the Steffensen method. These higher-order methods, such as formulas 41 and 42 in his work, can be third-order generalizations of the Steffensen procedure. They are valuable for scenarios where derivatives are not easily obtainable.

For extending the Newton-Raphson process, Bairstow's method, detailed in reference [5], is a notable third-order generalization.

General Functional Equations and Iterative Processes

Iterative procedures are not limited to finding fixed points of a function. They can also be applied to more general functional equations, where P is an operation mapping an open set of a Banach space into itself. The derivative of P can then be defined, leading to an analog of Newton's method for finding the fixed points of P. For detailed information, one can refer to reference [1].

References

[1] L. V. Kantorovich and G. P. Akilov, Functional Analysis in Normed Spaces, ch. XVIII, Pergamon Press, 1964.

[2] Wikipedia: Newton’s Method.

[3] Wikipedia: Steffensen’s Method.

[4] J. Foncannon, Derivative-free Iteration Processes. SIAM J. Numer. Anal., 1970; 329-334.

[5] Wikipedia: Bairstow’s Method.