Computer programs and graphing calculators have built-in equation solving algorithms which provide very accurate decimal values for solutions. Two of the best known root finding algorithms are the bisection method and Newton's method, named after the eminent 18^th century mathematician and scientist Isaac Newton. Newton's method uses calculus in the computation of slopes of tangent lines. While is more efficient, it can fail when the original estimate is too far from the root. The bisection method does not use any calculus and usually takes longer to converge.

Open Roots.xls. The first graph in Figure D_1 shows a global view of this cubic and the second graph in Figure D_2 focuses on the root between 3 and 4.

BISECTION METHOD

To find a root of using bisection, we must first supply the left and right endpoints of an interval that we know contains the desired root. To guarantee that a root is indeed contained in an interval [left, right], the value of f(left) and f(right) must be opposite in sign. In other words one must be negative and the other positive.

In the sheet Bisection Method the initial left-hand endpoint, L1, is specified as 3 in the cell for "lower x". Since the initial width is set to 1 the initial right hand endpoint, R1, will be equal to L1 plus one which is 4.

If we let M1 be the midpoint of the current interval [L1, R1] then M1 = L1 + (( R1-L1)/ 2) = (L1+R1)/2. One of the following situations must be true:

(1) f(M1) = 0 in which case M1 is the root r and there is no need to continue.

(2) f(M1) has the same sign as f(L1) in which case the root we are looking for is in the interval (M1, R1). Our new left hand endpoint becomes M1. The right hand endpoint, R2, is equal to R1.

(3) f(M1) has the same sign as f(R1) in which case the root we are looking for is in the interval (L1, M1). Our new right hand endpoint becomes M1. The left hand endpoint, L2, is equal to L1.

Repeat this iterative process on the interval [L2, R2] to form the interval [L3, R3], then the interval [L4, R4], [L5, R5], and so on. Successive intervals will contain the root and the interval width will be one-half the width of the preceding interval.

This procedure can be stopped after a certain number of iterations ( we chose 20 iterations) or after the desired degree of accuracy has been achieved. If the original interval has unit width (width = 1) then ten iterations will guarantee accuracy to the nearest thousandth. Can you justify this claim?

NEWTON'S METHOD

To find a root of f(x) = 0 using Newton's method we start with an initial guess x0 and replace it with a series of new estimates, x1, x2, x3, and so on, until we have reached a desired level of accuracy. For this same cubic f(x) = 0.5x3-4x-3, we let x0 = 2 be our initial guess.
	Figure D_3

To find the next estimate we construct the tangent line to the curve at (x₀, f(x₀) and extend it until it crosses the x axis at x₁. The figure for the cubic shows that x₁ is between 5 and 6. We find another tangent line using x₁ instead of x₀. This second tangent line crosses the x-axis at x₂ which is near 4. Repeating again we see that the tangent line to the cubic at (x₂, (f(x₂)) crosses the

x-axis closer to the root. The recursive relationship that relates each approximation to the previous one is given by

- provided

The table below shows that six place accuracy has been reached by the sixth iteration of Newton's method compared with over twice as many iterations using the bisection method even though we started Newton's method further away from the root . If we had chosen x₀ = -1 then Newton's method would have converged on the root between -1 and 0. In most practical situations Newton's method is successful and efficient at finding a root of f(x) = 0. Occasionally the sequence x₀, x₁, x₂, … fails to converge even though the function does have at least one real root and the initial estimate is close to a root. Failures can occur if the tangent line at (x_n, f(x_n)) is nearly horizontal for some x_n or if an inflection point occurs between successive iterations.

Return to Table of Contents

Copyright © Joseph F. Aieta, Babson College 1997