Newton-Raphson Method for Solving Nonlinear Equations

Suppose we wanted to find the values of x for which $\tan x = x$.The Maple solve command gives us just one solution:

> solve(x=tan(x));
                                       0

To see where the other roots lie, we can plot the two functions and see where they intersect.

> plot({x,tan(x)},x=0..3*Pi,y=-1..10);

Notice that we specify the vertical range because of the singularities in the tan(x) function. From the plot we can see solutions around x = 4.5 and x = 7.5 as well as x = 0.

To find the other zeros without the aid of Maple, we can try the Newton-Raphson method. The general method finds the zeros of f(x). In our case we will be using $f(x) = \tan x - x$.

The method works from a Taylor series and makes an iterative approximation to the true zero. The iterative approximation starts from a guess at the solution and generates a new guess that is supposed to be closer to the true solution. Suppose x₀ is where the zero occurs. Suppose x is our guess. Then we may make a Taylor series expansion of f(x) around x and evaluate it at x₀:

$$f(x_0) = f(x) + (x_0-x)f^\prime(x) + O(x_0-x)^2$$

We may substitute f(x₀) = 0. Then, keeping only the first two terms, we solve for x₀:

$$x_0 = x - f(x)/f^\prime(x)$$

Because we kept only the first two terms in the Taylor series, the value of x₀ is only approximate, but it gets better as we approach the true solution. The algorithm is then simply to plug our guess into the right side of the equation and get the new guess. Then repeat until our answer has converged.

Here is a Maple procedure that does the job, finding the zero near 4.5. We also introduce some new Maple techniques.

> diff(tan(x)-x,x);
                                          2
                                    tan(x)

_______________________________________________
> z0 := 4.5;
                                   z0 := 4.5
_______________________________________________
> newton := z0;
                                  newton := 4.5
_______________________________________________
> for j from 0 to 4 do z.(j+1) := evalf(z.j - (tan(z.j)-z.j)/(tan(z.j))^2);  
>     newton := newton, z.(j+1);  
>       od: 
_______________________________________________
>  newton; 
      4.5, 4.493613903, 4.493409655, 4.493409458, 4.493409458, 4.493409458
_______________________________________________
> z5; 
                                  4.493409458

_______________________________________________
> tan(z5);
                                  4.493409460

What this procedure does is to generate a list of successive approximations using the Newton-Raphson technique, and to name the list newton. The list of approximations is a new Maple object, called an ``expression sequence''. An expression sequence is merely a list of expressions, separated by commas. The expressions in this case are just single numbers. The first member of this sequence is our first guess, which is called z0. The second member is called z1 and represents the result of carrying out the Newton-Raphson technique once with z0 as input, and so on. The command newton; dumps the entire list.

The sequence is generated using a Maple for loop. The syntax is a bit different from other programming languages, but the ingredients are all there. The counter is j; the loop assigns the values 0,1,2,3,4. The statements in the for block are sandwiched between do and od. Each statement ends with a semicolon.

Two more details of note: The period . in z.j and z.(j+1) is one convenient way to create and refer to an indexed name. The period isn't really part of the name. The actual names are just z0, z1, etc. The purpose of the period is to cause the two parts of the name to be joined, or ``concatenated''.

Finally, notice that the od: statement ends with a colon, rather than a semicolon. With a semicolon, we would get a full report of the evaluation of the loop. Try it and see! A colon at the end of a Maple command tells Maple to do its work silently.

Now for the details of the program. The first command gets the derivative, which is to be used in the algorithm. The next two commands initialize the expression sequence newton and the first approximation. The next statements define the loop, in which the next term in the sequence z.(j+1) is calculated in terms of z.j according to the Newton-Raphson algorithm. We must use evalf to get a number. The loop also includes a statement that appends the result to the list newton.