This is a method used to solve equations of the form f(x) = 0. If a function y = f(x) is known to be continuous, and f(a) and f(b) have opposite signs, there must be a solution to f(x) = 0, where x lies between a and b. Figure 5 below illustrates this where x = c is the solution to f(x) = 0, f(a) is negative and f(b) is positive, hence a < c < b.
An arbitrary guess is made, c(0), where a < c(0) < b. A better approximation, c(1), can then be found by drawing a tangent to the graph at x = c(0), and finding where it crosses the x-axis. The point at which it crosses the x-axis is the new approximation. This process is repeated, or iterated, and the values obtained usually converge to the solution.
An example of the method failing is when the tangent has gradient zero, and hence does not cross the x-axis, since c(n) <> 0.
Figure 5 - the Newton-Raphson method for solving f(x)=0; an initial guess of x=c(0) has been made, and a tangent drawn at this point. The new approximation, c(1), is given by the point at which the tangent crosses the axis.
The iteration can be expressed mathematically:
The vertical distance between (c(0),f(c(0))) and the axis is f(c(0)), the gradient of the tangent is f '(c(0)), hence the horizontal distance between c(0) and c(1) can be calculated:
In general the Newton-Raphson method says:
The equation x^p - 1 = 0, where p is an integer, always has an integer solution x = 1. However, when p = 2, there are two solutions, x = ±1, so are there three solutions when p = 3? The only solution there appears to be is x = +1, since (+1)³ = +1 but (-1)³ = -1. However, there are two further solutions, which are imaginary. So far, only real solutions have been considered.
The solutions to x³ - 1 = 0, are: +1, - 0.5 + 3i and - 0.5 - 3i. In general, for x^p - 1 = 0, there are p solutions. The Newton fractal illustrates these solutions by applying the Newton-Raphson method previously described to complex numbers.
The function used to produce the Newton fractal is
If c(n) is an approximation to the solution f(x) = 0
The equation to produce the Newton fractal is:
The fractal is produced in a similar way to the Mandelbrot and Julia sets. The pixel location determines the initial value of c (c(0)), and the iteration above is applied until the value of c approaches one of the solutions. There are two popular ways of producing the colour, or shading, for the Newton fractal, and both are illustrated.
The first (Figure 6), colours the pixels according to how many iterations are taken to approach a solution. There are dark circles around the solutions, indicating the areas where the solutions is approached quickly. In the fringes between two solutions, many iterations are required to converge to a solution, and a very small change in the starting position can cause the iteration to flip from one solution to another.
Figure 6 - a Newton fractal (degree 6) shaded according to how many iterations are require to converge to a solution (Higher-Resolution Image)
The second colouring scheme (Figure 7) colours the pixels according to which solution they converge to. Distinct solid colour regions are seen around each solution. However between two solutions a chaotic region is seen, which follows no distinct pattern. A zoomed version of one of these areas is shown.
Figure 7 - a Newton fractal (degree 6) shaded according to which solution the iteration converges to, and a zoomed version showing the chaotic region
Higher-Resolution Image (Fig 7a), Higher-Resolution Image (Fig 7b)
