Schröder's method refers to two families of equations used to find roots of nonlinear functions of a single variable. These methods are not very often explored, but it does deserve it's own page.

History

In 1870, Ernst Schröder (1841 - 1902) published this paper: On Infinitely Many Algorithms for Solving Equations (original German title: Ueber unendlich viele hlgorithmen zur hufliisnng der Gleichungen). This paper was originally published in German, but an English translation was published by G. W. Stewart on November 1992 (revised January 1993). Schröder's goal was to find the roots of the equation f(z) = 0, where f is analytic about the roots in question. He begun by distinguishing two kinds of methods. The first is typified by Newton's method and consists of the successive substitution of iterates in a fixed formula. Schröder calls such methods algorithms, a usage more restricted than ours today. The essence of the second kind of method consists in constructing a sequence of functions. Bernoulli's method can be regarded as a method of the second kind. It is in this paper that he created Schröder's equation.

One of these algorithms creates the following equations, using a factor omega: for omega = 1, z' = z - (z*f)/(z*f1 - lambda*f), z' = z - (z*f*f1)/(z*(f1^2 - f*f2) - lambda*f*f1), which is the most general quadratically converging algorithm that can come from this source. For the simplest case, lambda = 0, we get Newton's algorithm z' = z - f/f1 on the one hand and on the other an equally worthy algorithm z' = z - (f*f1)/(f1^2 - f*f2) (where f is the function, f1 is the first derivative and f2, the second derivative), which, to Schröder's knowledge, has not previously been considered. Besides being almost as simple, this latter algorithm has the advantage that it converges quadratically even for multiple roots. The second formula appears to be a modification of Halley's method formula, in which it removes the two integers of two in both the numerator and the denominator.

For omega = 2, we get the general cubic convergent algorithms, such as: z' = z - z*f * (z*f1 - lambda*f)/(z^2*(f1^2 - 0.5*f*f2) - lambda*z*f*f1 + ((lambda*(lambda-1))/2) * f^2).

For the simplest case lambda = 0, we have: z' = z - (f*f1)/(f1^2 - 0.5*f*f2), and z' = z - f*(f1^2 - f*f2)/(f1^3 - 1.5*f*f1*f2 + 0.5*f^2*f3). In this case, f3 is the third derivative.

Examples

Quadratic Schröder's method for f(z) = z^3 - 1

As we can see, it shows structures seen in the Newton fractal.

Cubic Schröder's method for f(z) = z^3 - 1

With cubic convergence, the patterns resemble that of Halley's method.

Notes

• 2nd order has quadratic convergence, 3rd order is cubic
• Can diverge or divide by zero
• Quasi Nova variant has miniature Mandelbrot sets (when z is set to c while equal to pixel instead of initializing z to a certain start value)
• Requires extra derivative with increasing lambda and/or omega
• Can double back or oscillate, as well as enter an infinite loop
• Handles root multiplicity really well, sometimes solving the function in one iteration