Newton's Method for Finding Roots
Objective: This module shows how to implement Newton’s Method using a
in order to find a real root of an equation f(x) = 0. This iteration method
to a do loop that can terminate when we are close to the root. This loop is
placed inside the
procedure. The Maple commands in this module are
plot, abs, proc
The geometric idea behind Newton’s method is that the x-intercept of a tangent
the function f(x) is close to the root of the equation f(x) = 0.
The method begins with
a guess, x0, that is based on knowing where f is positive and negative. For
f(x) = x3 + 2x2 − 3, then the Intermediate Value Theorem tells us that a root is
0 and 2, since f(0) = −3 < 0 and f(2) = 13 > 0. Suppose x0 = 0.5. Then we
the tangent line at x0 and find its x-intercept, x1, as the next guess at the
root. The method
continues until the guesses converge (that is, show no change) to the root.
Recall that the tangent line at x0 has slope f'(x0). The tangent line is then y
= f'(x0) +
D(f)(x0)(x − x0) where we make use of the D(f) command. We plot the function
with the tangent line to show that the intercept of the line comes close to the
root of f(x):
We can compute the intercept of the tangent line by solving for x:
f(x0) + D(f)(x0)(x − x0) = 0 implies that x − x0 = −f(x0)/D(f)(x0), or
x = x0 − f(x0)/D(f)(x0)
We can call this x value tanzero(x). From the formula above, we see that
can be written as a function:
> tanzero:= x->evalf(x-f(x)/D(f)(x));
Note that the Newton’s method approximation is put inside a evalf(). The purpose
evalf() is to force Maple to evaluate the answer in the decimal form, instead of
expression. Moreover, if we let x:=tanzero(x), we can see that the tangent
at x1 has an intercept that is a better approximation to the root than that at
x0. To see this,
execute the following Maple commands:
4.1 Execute the commands x:=tanzero(x); x:=tanzero(x); repeatedly
until the output converges to 1. For each execution of the command, what is the
number of decimal places that are correct in each approximation?
4.2 Implement the sequence of commands in Exercise 4.1 using a for loop. Before
begins, define the initial guess using the label x:=0.3;.
4.3 Terminate the loop in Exercise 4.2 if two successive approximations are very
close; that is,
if abs(x[i-1]-x[i])<0.001. Use the initial guess x:=0.2; Your loop should
have enough iterations that the if .. then .. statement was for sure invoked.
The proc()...end; Command
Another programming feature, similar to the for...do...od; and the if...then...fi;
command structures, is the Maple procedure. A procedure is a group of commands
a particular task. The proc command typically has input variables (in order to
a task) and returns one or more answers (depending on the task). For example,
the following is
a procedure that computes x2 + 3x, given an input value x:
Notice that the proc ... end command begins with stating the function name (f),
define f as a procedure. Inside the procedure, we calculate the output value
using the variable
output, and then RETURN the output value. To execute this procedure, say, we
would like to
evaluate f(2), simply type
Within the procedure, you need to define any labels you use as local. In the
example, the variable output is a local variable inside the procedure only.
Notice that we can also define f(x) by f:=x->x∧2+3*x. In fact, Maple turns this
to a procedure, as shown by the output (if you turn the output into Maple
Procedures are, however, a lot more powerful in performing complex tasks. For
following is a procedure that computes the first and second derivatives of a
function f. Notice
that f has to be defined as an expression:
To execute this procedure, say, we want to find the first and second derivative
of x3 + 2x − 5,
the user simply enters
4.4 Implement the above procedure Derivs in your worksheet. Explain what the
Derivs did in each line.
Here’s another example that determines if a quadratic function f(x) = ax2+bx+c
has two real
roots, one real root, or two complex roots. The procedure uses the extension of
the if ...
then ... else statement to if ... then ... elif ... else. Look up
the structure in the Maple help section.
if discrim > 0 then RETURN("two real roots")
elif discrim < 0 then RETURN("two complex roots")
else RETURN("one real root")
4.5 Enter the above procedure into your worksheet. Execute the command
What does this command do? Which polynomial is it checking?
4.6 Write a procedure called ispositive where the procedure returns “true” if
value is positive, otherwise, it returns “false”. Test the accuracy of your
evaluating ispositive(1), ispositive(-2), ispositive(0). (Hint: start with
4.7 Incorporate Newton’s method that we developed in 4.2 into a procedure newton(f, s,
n) where f is the input function in terms of x; s represents the initial guess
x; and n is the
number of iterations that you want to carry out in the loop. Test your procedure
newton(x->x∧3+2*x∧2-3, 0.2, 3), newton(x->x∧3+2*x∧2-3, 5, 10).