Processing math: 100%
Skip to main content

Section 9.1 Newton's method

The idea of Newton's method is geometrically natural. We want to solve f(x)=0 but since f may be complicated, we replace it by its linear approximation (tangent line at a certain point). The resulting linear equation is easy to solve. Of course, its solution is probably not a solution of the original equation, but perhaps it is close to it. The process repeats, using the previously found solution as a new point at which to draw a tangent line. A static image of this process is below. Interactive visualization is also available.

Figure 9.1.1. Two steps of Newton's method

Formally, the linear approximation to f at a point x is f(x+h)β‰ˆf(x)+fβ€²(x)h. Equating the right hand side to 0 we find h=βˆ’f(x)/fβ€²(x) which means that the point where the tangent line at x meets the line y=0 is x+h=xβˆ’f(x)/fβ€²(x). Therefore, we can express Newton's method as iteration of the function

g(x)=xβˆ’f(x)fβ€²(x)=xfβ€²(x)βˆ’f(x)fβ€²(x)

Note that any point where f(x)=0 and fβ€²(x)β‰ 0 is a fixed point of g. In fact, it is a super-attracting point of g because

gβ€²(x)=1βˆ’fβ€²(x)fβ€²(x)βˆ’f(x)fβ€³(x)(fβ€²(x))2=f(x)fβ€³(x)(fβ€²(x))2

which is zero when f(x)=0.

Given \(f(x) = x^3 - x\text{,}\) find and simplify the function \(g(x) = x - f(x)/f'(x)\text{.}\)

Solution

Bringing \(g\) to common denominator often helps:

\begin{equation*} g(x) = \frac{xf'(x) -f(x)}{f'(x)} = \frac{x(3x^2-1) - (x^3-x)}{3x^2-1} = \frac{2x^3}{3x^2-1} \end{equation*}

Once we have the function g, the rest of the process is the same as in Chapter 8, in particular in Example 8.2.1. Changing the first two lines of that program to

g = @(x) 2*x^3/(3*x^2-1); 
x0 = 0.6;

we get β€œFound x = 1 after 11 steps”. If the starting point is different, the process may converge to a different root of the equation x3βˆ’x=0. For example with x0 = 0.57 we get β€œFound x = -1 after 14 steps”. A small change of initial condition produced a rather different solution; we went from finding x = 1 to finding x = -1. The pattern of what starting points produce which solution can be very complicated: see the illustrations on Wikipedia page Newton fractal.