Newton-Raphson method  

Robert P. Munafo, 2010 Sep 12.



The Newton-Raphson method, also called Newton's method, is a simple iterative process often useful for solving equations with one free variable. If the variable is x, the equation to be solved is

f(x) = 0

where f(x) is some differentiable function of x. If f'(x) is the derivative of f(x) with respect to x, then the Newton-Raphson iteration involves calculating

xn+1 = xn - f(xn) / f'(xn)

which allows us to calculate a new approximation xn+1 from an existing approximation xn.

Using complex math, Newton's method can be used to find the nucleus of a mu-atom of known period. In this case the equation being solved is LP(C)=0 where P is the period of the mu-atom and LP is the Pth Lemniscate function (that is, the function Z'=Z2+C iterated P times with an initial value Z0=0). For example, if the period is 3, the lemniscate function is

L3(C) = ((02+C)2+C)2+C = C4 + 2 C3 + C2 + C

and its derivative is

(L3)'(C) = 4 C3 + 6 C2 + 2 C + 1

(NOTE: In general, it is not necessary to know the polynomial expansions of LP(C) and LP'(C) as shown here, because the values can be calculated iteratively. See below for details.)

Starting with an initial guess C0 we calculate LP(C0) and the derivative (LP)'(C0). Then our new guess is

C1 = C0 - L3(C0) / (L3)'(C0)

As a concrete example, we can use the initial guess -0.12+0.76i and find the nucleus of R2.1/3a:

step C L3(C) (L3)'(C) next C
1 -0.12+0.76i 0.01314-0.02923i -1.79437-1.19898i -0.12246 + 0.74535i
2 -0.12246+0.74535i 0.000389-0.000937i -1.67919-1.12683i -0.12256 + 0.74486i
3 -0.12256+0.74486i 3.66×10-7-1.07×10-7i -1.67529-1.12456i -0.12256 + 0.74486i

After just two steps of the iteration the approximation is accurate to 5 digits. The result after three steps, -0.12256116687638... + 0.74486176662039...i, agrees with the exact answer given in the R2.1/3a article (-0.12256116628477... + 0.74486176791682...i) in the first 8 digits of both components.

Iterative Evaluation of LN and its Derivative

In the example above, the lemnicate L3(C) and its derivative L3'(C) are shown as fully expanded polynomials. As the period increases, these polynomials rapidly become too big to manage (see Z5 and Z6 at the end of the lemniscates article). Fortunately, there is no need to know these polynomials when finding a mu-atom nucleus by the Newton-Raphson method, because LN(C) and LN'(C) can both be computed by iteration. This table shows how:

iteration polynomial iteration polynomial
L0(C) = 0 = 0 L0'(C) = 0 = 0
L1(C) = L0(C)2 + C = 02 + C = C L1'(C) = 2 L0(C) L0'(C) + 1 = 2×0×0 + 1 = 1
L2(C) = L1(C)2 + C = C2 + C L2'(C) = 2 L1(C) L1'(C) + 1 = 2 C + 1
L3(C) = L2(C)2 + C = (C2+C)2+C = C4 + 2 C3 + C2 + C L3'(C) = 2 L2(C) L2'(C) + 1 = 2 (C2 + C) (2C + 1) + 1 = 4 C3 + 6 C2 + 2 C + 1
L4(C) = L3(C)2 + C L4'(C) = 2 L3(C) L3'(C) + 1
L5(C) = L4(C)2 + C L5'(C) = 2 L4(C) L4'(C) + 1
etc. etc.

As you can see from the 1st and 3rd columns, each value of L(C) and L'(C) can be computed from the previous values with the formulas:

LN+1(C) = (LN(C))2 + C

LN+1'(C) = 2 LN(C) LN'(C) + 1


The following shows the calculation of the nucleus of the period-3 mu-atom R2.1/3a. This was done with maxima:

(%i1) l3(c):=c^4+2*c^3+c^2+c; 4 3 2 (%o1) l3(c) := c + 2 c + c + c (%i2) diff(l3(c),c); 3 2 (%o2) 4 c + 6 c + 2 c + 1 (%i3) d3(c):=4*c^3+6*c^2+2*c+1; 3 2 (%o3) d3(c) := 4 c + 6 c + 2 c + 1 (%i4) c0:-0.12+0.76*%i; (%o4) 0.76 %i - 0.12 (%i5) rectform(l3(c0)); (%o5) 0.0131404799999999 - .02923264000000014 %i (%i6) rectform(d3(c0)); (%o6) - 1.198976 %i - 1.794368 (%i7) c1:rectform(c0-l3(c0)/d3(c0)); (%o7) .7453543395553945 %i - .1224628812914806 (%i8) c2:rectform(c1-l3(c1)/d3(c1)); (%o8) .7448623089253219 %i - .1225610213028558 (%i9) c3:rectform(c2-l3(c2)/d3(c2)); (%o9) .7448617666203934 %i - .1225611668763843





From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2014.     Mu-ency index


Robert Munafo's home pages on HostMDS   © 1996-2014 Robert P. Munafo.   about   contact    mrob    mrob27    @mrob_27
This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. Details here.

This page was last updated on 2014 Nov 21. s.11