Please send all questions & assignments to:
prakash@cset.et.utoledo.edu

Solution of Nonlinear Equations

1. Bisection Method Tutorial

The method for finding roots that will be discussed here is the bisection method. We illustrate this method by considering the above-mentioned polynomial p(x) = x7 + 9x5 - 13x - 17 .

Note that p(0)=-17 and p(2)=373. Therefore, since p(x) is a continuous function (i.e., its graph has no ``breaks''), we know that there must be a root, say r, in the interval (0, 2).

To close in on r, we now evaluate p at the midpoint of (0, 2) which is 1. p(1)=-20. Now we see that r must actually lie in the interval (1, 2) since p switches signs from negative to positive as x ranges from 1 to 2. So we have reduced the interval under consideration from (0, 2) to (1, 2). We have cut the length of our interval in half, or bisected it.

We look next at the midpoint of (1, 2), namely 1.5. p(1.5)~48.929 . Thus, r must be in the interval (1, 1.5). We continue this procedure until a desired accuracy has been achieved. The following table summarizes the results of iterating this technique several times.

 

Left Endpoint Right Endpoint Midpoint p(Midpoint)
0 
1 
1 
1.25 
1.25 
1.25 
1.25 
1.25 
1.2578125 
1.2578125 		 2 
2 
1.5 
1.5 
1.375 
1.3125 
1.28125 
1.265625 
1.265625 
1.26171875 		 1 
1.5 
1.25 
1.375 
1.3125 
1.28125 
1.265625 
1.2578125 
1.26171875 
1.259765625 		 -20 
48.929 
-1.015 
18.651 
7.701 
3.086 
0.974 
-0.035 
0.465 
0.213 

Note that after these iterations are performed, we see that

 

1.2578125 < r < 1.259765625 .

 

Hence, we have been able to find r accurate to the hundredths place.

One question that should be raised is the following: Does this method always converge to a root? The answer is yes, provided the function under consideration is continuous and we begin with two values a and b such that p(a)<0 and p(b)>0. (The Intermediate Value Theorem guarantees that a root exists under these conditions.)

To close this section, I note that this algorithm is easily implemented via a computer program. One loop is all that is needed.

2. Newton's Method

We come now to a second method of approximating roots of functions known as Newton's method. We need to assume that f is a differentiable function in some interval [a, b], i.e., we can find f' in the interval [a, b] .

We first look at a "pictorial" view of how Newton's method works. Consider Figure 1.


 

[graph, Figure 3.1]

Figure 1


 

We see a portion of the graph of f along with the root r and an additional point x0 which will be referred to as a seed value. x0 is our initial approximation of r. We now draw a vertical line segment from the seed value x0 to the graph of f. See Figure 2.


 

[graph, Figure 3.2]

Figure 2


 

We then draw the tangent line to the curve of f through (x0 , f(x0 )) . This line crosses the x-axis at a new point, say x1 . See Figure 3


 

[graph, Figure 3.3]

Figure 3


 

Note that in Figure 3, x1 is a better approximation of r than x0 . We now iterate this process, yielding new pointsx2 , x3 , ... until we are "close enough" to r. Figure 4 shows one more iteration of this process, determining x2 .


 

[graph, Figure 3.4]

Figure 4


 

Now we consider this method algebraically. Referring back to Figure 3 we see that the slope of the line

through the points (x1 , 0) and (x0 , f(x0 )) is equal to

 

[0 - f(x_0)]/[x_1 - x_0]

Moreover, the slope also equals f'(x0 ) since this line is tangent to the curve of f. Hence,

f'(x_0) = -f(x_0)/[x_1 - x_0]

which yields

x_1 - x_0 = -f(x_0)/f'(x_0)

or

x_1 = x_0 - f(x_0)/f'(x_0) .

Iterating this yields the general term

x_{n+1} = x_n - f(x_n)/f'(x_n)

This iterative technique is the crux of Newton's method and can be easily applied via a computer program.

Example: Consider p(x) = x7 + 9x5 - 13x - 17 once again. We have seen from the bisection method that one

 root of p lies in the interval (1, 2). Using x0 = 1 as our seed value, we can generate the following table via Newton's method.

 n  xn p(xn ) p'(xn ) xn+1
0
1
2
3
4
5		 1
1.512820513
1.340672368
1.269368397
1.258332053
1.258092767		 -20
52.78287188
12.33751268
1.46911353
0.03053547
0.00001407		 39
306.6130739
173.0270062
133.1159618
127.6107243
127.4932403		 1.512820513
1.340672368
1.269368397
1.258332053
1.258092767
1.258092657

Note that after 6 iterations of Newton's method, the root r can be approximated as

r = 1.258092657 ,

accurate to 6 decimal places.

The secant method is similar to the Newton's Method, but is different in that the derivative f' is approximated

by using two consecutive iterative values of f. By using an approximation for the  derivative f'(xo) as

x_1 - x_0 = -f(x_0)/f'(x_0)

 

 

 

There have been visitors since 11/26/2003

Added to the Web: January 10, 2000.
Last updated: January 14, 2000.
Web page design by Dan Solarek.
http://cset.sp.utoledo.edu/eet2980/