Convergence of Newton's Method for Approximating Square Roots
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.
Requires a Wolfram Notebook System
Edit on desktop, mobile and cloud with any Wolfram Language product.
This Demonstration shows the convergence properties of a family of Newton-like methods for computing square roots of positive reals as constructed by Hernández and Romero. In this Demonstration the roots of 35 are used. For each integer , the iterative formula (displayed in the top left‐hand corner) is defined. It generates a sequence (displayed below the formula) converging to one of the roots of 35 for almost all chosen starting values in the complex plane, outside the imaginary axis. The initial point is shown in purple, the two roots (limit points) are colored yellow, and some of the intermediate points are colored in shades of yellow, with darker colors corresponding to later positions in the sequence.[more]
Use the controls to vary the position of the starting point in the complex plane. Coloring each point in the plane according to whether the sequence with that initial point converges to the positive (pink) or negative (green) root yields an intricate fractal structure. A part of this structure can be seen by checking the fractal background checkbox. However, do not attempt to manipulate the controls with this option checked unless you are using a very fast computer.
The blue points belong to the so-called Julia set of the fractal. Close to these points convergence of the sequence becomes unpredictable.[less]
The well-known classical iterative method for computing the square root of a positive real number is globally convergent in the entire complex plane with the imaginary axis removed: initial points in the half‐plane produce sequences convergent to the positive square root, while those in the half-plane converge to the negative square root. Hernández and Romero constructed for each 2 an iterative method that exhibits a much more complicated behavior. For each 2 these sequences have convergence order (so for "generic initial" points larger should produce a shorter sequence). For even these methods have the property of "global convergence" on the real line, that is, they converge to one of the roots starting with any nonzero value on the real line. For odd the methods have the property of "general convergence" (a concept introduced by Smale)—that is, they converge for almost every starting point. In the complex plane the behavior of convergence with respect to different starting points is highly complex and displays an intricate fractal structure. Some points of the Julia set of this structure are displayed in blue. In particular, for odd there are always points in the Julia set lying on the real line (these are the fixed points of the iteration).
Checking the checkbox "fractal background" will show initial points that give rise to sequences converging to the positive square root (red) and those that give rise to sequences converging to the negative square root (green). (Unfortunately, to see the fractal nature of the convergence phenomenon we need a much larger number of points, which would excessively slow down the Demonstration).
Reference: M. A. Hernández and N. Romero, "Methods with Prefixed Order for Approximating Square Roots with Global and General Convergence," Applied Mathematics and Computation, 194(2), 2007 pp. 346–353.