Application Center - Maplesoft

App Preview:

Calculus I: Lesson 22: Solving Equations Numerically with Bisection and Newton's Method

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application


 

L22-newtonsMethod.mws

Calculus I

Lesson 22: Solving Equations Numerically with Bisection and Newton's Method

In this worksheet, we will investigate methods for finding approximate solutions to equations of the form f(x) = 0 . We will look at two important methods: repeated bisection, which is based on the Intermediate Value Theorem, and a method based on linear approximation known as Newton's method.

Repeated Bisection

The idea behind the repeated bisection method is very simple: if a continuous function f is negative somewhere and positive somewhere else, it must have a zero in between. The traditional first example of the method is to approximate sqrt(2) by solving the equation x^2-2 = 0 .

> restart;

> f := x -> x^2 - 2;

f := proc (x) options operator, arrow; x^2-2 end pr...

> plot(f, 0..4);

[Maple Plot]

It seems clear from the picture that f has a zero somewhere in the interval (1,2). We can quickly confirm this by evaluating f at these two points:

> f(1); f(2);

-1

2

The function changes sign on the interval [1,2]; since it is a polynomial, and therefore continuous, it must have a zero in the open interval (1,2). We can obviously locate this zero more accurately by testing values of f at the endpoints of shorter intervals, but the trick is to do this in the most efficient manner possible. It turns out that it is not possible, in general, to do any better than halving the length of the interval at each stage, so we bisect the interval in which we have found the zero, and evaluate f at the midpoint. Since there was a sign-change over the whole interval, there must be one over one of the half-intervals, and we have the zero located in a shorter interval than before. We can repeat this process as often as necesary to obtain the required accuracy.

> m1 := (1 +2)/2; f(m1);

m1 := 3/2

1/4

The sign change is between 1 and 3/2, so we know that 1 < sqrt(2) < 1.5 . We now repeat the procedure, starting withe the interval [1, 3/2].

> m2 := (1 + m1)/2; f(m2);

m2 := 5/4

-7/16

> m3 := (m2 + m1)/2; f(m3);

m3 := 11/8

-7/64

> m4 := (m3 + m1)/2; f(m4);

m4 := 23/16

17/256

> evalf([m3,m4]);

[1.375000000, 1.437500000]

> m5 := (m3 + m4)/2; f(m5);

m5 := 45/32

-23/1024

> m6 := (m5 + m4)/2; f(m6);

m6 := 91/64

89/4096

> evalf([m5,m6]);

[1.406250000, 1.421875000]

Since f changes sign on the interval [m5, m6], and is continuous, we now know that sqrt(2) = 1.4 to 2 significant figures.

(Guaranteed!) It may seem as though we have done a lot of work for a small result, but you might remember the following points:

1) We are illustrating a very general method, which can be used to solve much more complicated equations.

2) In principle, the method can be used to get any desired accuracy.

3) Most importantly, the accuracy is guaranteed: we not only get an approximation to the zero, but we get upper and lower bounds. That is, the zero is guaranteed to lie within a certain interval.

You should also observe that the method is highly repetitious, and is therefore a good candidate for programming. Here is a crude implementation, which takes a function and an initial interval, checks to see whether the function changes sign on the interval, and then iterates 10 times.

> bisect10 := proc(f,a,b) local a1,b1,m,j:

> if (evalf(f(a)*f(b)) >= 0) then

> RETURN(`No sign change detected on ` (a,b)):

> else

> a1 := a: b1 := b:

> for j from 1 to 10 do

> m := (a1 + b1)/2:

> if (f(a1)*f(m) < 0) then b1 := m:

> else a1 := m:

> fi:

> od:

> fi:

> print(`There is a zero in ` (evalf(a1), evalf(b1)) ):

> end:

> bisect10(f,2,3);

`No sign change detected on `(2,3)

> bisect10(f,1,2);

`There is a zero in `(1.414062500,1.415039062)

Can you explain the next result?

> bisect10(sin,-1,4);

`No sign change detected on `(-1,4)

>

>

Newton's Method

> restart;

Despite the advantages of repeated bisection listed towards the end of the last section, it can be slow if you need a highly accurate approximation, especially if you are doing the computations by hand. If we assume that our function f is not only continuous, but differentiable, we can use the idea of linear approximation: as you can see from the picture below, if we have somehow managed to find an approximation to a zero of f , the intersection of the tangent line at that point with the x -axis might be expected to be a better approximation. (In the picture, the original approximation is x = 1 .)

> f := x -> x^2 - 2;

f := proc (x) options operator, arrow; x^2-2 end pr...

> x0 := 1;

x0 := 1

> t1 := x -> f(x0) + D(f)(x0)*(x-x0);

t1 := proc (x) options operator, arrow; f(x0)+D(f)(...

> plot({f,t1}, 0..3);

[Maple Plot]

Now, of course, we repeat: we find where the tangent line crosses the x -axis. This is our new approximation to the zero, so we find the tangent line at this new point and see where it crosses the axis. Hopefully, by repeating the procedure as often as necessary, we can obtain any accuracy we desire.

> x1 := solve(t1(x) = 0, x);

x1 := 3/2

> t2 := x -> f(x1) + D(f)(x1)*(x-x1);

t2 := proc (x) options operator, arrow; f(x1)+D(f)(...

> plot({f,t2}, 0..3);

[Maple Plot]

Note that even after one iteration, we will need to zoom in to see the difference between the true zero of f and the intersection of the tangent line with the x -axis.

> x2 := solve(t2(x) = 0, x); evalf(%);

x2 := 17/12

1.416666667

Repeat if necessary:

> t3 := x -> f(x2) + D(f)(x2)*(x - x2);

t3 := proc (x) options operator, arrow; f(x2)+D(f)(...

> x3 := solve(t3(x) = 0, x); evalf(%);

x3 := 577/408

1.414215686

As a comparison, here is Maple's evaluation of sqrt(2) (to 10 digits):

> evalf(sqrt(2));

1.414213562

It is clear that Newton's method is extermely fast---at least in this example. Can you think of any disadvantages it may have?

>

>