Observe that the successive interval widths form the pattern b1-a1 b1 It is left as an exercise for the reader to use mathematical induction and show that bo (1.27) Combining(1. 26) and(1.27) results in Ir-cnI bo-ao Now an argument similar to the one given in Theorem 1.3 can be used to show that (1. 28) implies that the sequence nino converges to r and the proof of the theorem is complete. Example 1.7. The function h(a)=r sin( )occurs in the study oscillations. Find the value of r that lies in the interval [0, 2 where the function on the value h(a)=l(the function sin(a)is evaluated in radians) We use the bisection method to find a zero of the function f(a)= r sin()-1 Starting with ao=0 and bo= 2, we compute ∫(0)=-1.000000andf(2)=0.818595, so a root of f(a)=0 lies in the interval 0, 2. At the midpoint co= 1, we find that f(1)=0.158529. Hence the function changes sign on co, bol=[1, 2 To continue, we squeeze from the left and set a1=co and b1= bo. The midpoint C1=1.5andf(cn)=0.496242.Now,f(1)=-0.158529andf(1.5)=0.496242impl that the root lies in the interval [a1, c1=[1.0, 1.5. The next decision is to squeeze from the right and set a2 = a1 and b2=C1. In this manner we obtain a sequence IckI that converges to r N 1. 114157141. A sample calculation is given in Table 1.1 16
Observe that the successive interval widths form the pattern b1 − a1 = b0 − a0 2 1 b2 − a2 = b1 − a1 2 = b0 − a0 2 . It is left as an exercise for the reader to use mathematical induction and show that bn − an = b0 − a0 2 n . (1.27) Combining (1.26) and (1.27) results in |r − cn| ≤ b0 − a0 2 n+1 for all n. (1.28) Now an argument similar to the one given in Theorem 1.3 can be used to show that (1.28) implies that the sequence {cn} ∞ n=0 converges to r and the proof of the theorem is complete. Example 1.7. The function h(x) = x sin(x) occurs in the study of undamped forced oscillations. Find the value of x that lies in the interval [0, 2], where the function takes on the value h(x) = 1 (the function sin(x) is evaluated in radians). We use the bisection method to find a zero of the function f(x) = x sin(x) − 1. Starting with a0 = 0 and b0 = 2, we compute f(0) = −1.000000 and f(2) = 0.818595, so a root of f(x) = 0 lies in the interval [0, 2]. At the midpoint c0 = 1, we find that f(1) = 0.158529. Hence the function changes sign on [c0, b0] = [1, 2]. To continue, we squeeze from the left and set a1 = c0 and b1 = b0. The midpoint is c1 = 1.5 and f(c1) = 0.496242. Now, f(1) = −0.158529 and f(1.5) = 0.496242 imply that the root lies in the interval [a1, c1] = [1.0, 1.5]. The next decision is to squeeze from the right and set a2 = a1 and b2 = c1. In this manner we obtain a sequence {ck} that converges to r ≈ 1.114157141. A sample calculation is given in Table 1.1. 16
Table 1.1 Bisection Method Solution of sin(a)-1=0 Function value k end point, ak Midpoint, Ck end point, bp f( 00 0.158529 11.0 1.5 2.0 0.496242 21.00 1.25 0.186231 31.000 1.125 1250 0.015051 41.0000 1.0615 1.1250 0.071827 51.06250 1.09375 1.12500 0.028362 61.093750 1.125000 0.006643 111718751.1250000 0.004208 81.109375001.1328125 718750 0.001216 A virtue of the bisection method is that formula(1.24)provides a predetermined estimate for the accuracy of the computed solution. In Example 1. 7 the width of the starting interval was bo -a0= 2. Suppose that Table 1. 1 were continued to the thirty-first iterate; then, by(1. 24), the error bound would be E31 <(2-0)/232N 4.656613x 10-10. Hence C31 would be an approximation to r with nine decimal places of accuracy. The number N of repeated bisections needed to guarantee that the Nth idpoint cN is an approximation to a zero and has an error less than the preassigned ue d N= int In(b-a)-In(0) ln(2) (1.29) The proof of this formula is left as an exercise Another popular algorithm is the method of false position or the regula falsi method. It was developed because the bisection method converges at a fairly slow speed. As before, we as that f(a) and f(b) have opposite sings. The bisection method used the midpoint of the interval [a, b] as the next iterate. A better approxi- mation is obtained if we find the point(c, 0) where the secant line L joining the points (a, f(a))and(b, f(b) crosses the z-axis(see Figure 1.8). To find the value c, we write down two versions of the slope m of the line L: (1.30) where the points(a, f(a)) and(b, f(b)are used, and 0-f(b
Table 1.1 Bisection Method Solution of x sin(x) − 1 = 0 Left Right Function value, k end point, ak Midpoint, ck end point, bk f(ck) 0 0 1 2 −0.158529 1 1.0 1.5 2.0 0.496242 2 1.00 1.25 1.50 0.186231 3 1.000 1.125 1.250 0.015051 4 1.0000 1.0615 1.1250 −0.071827 5 1.06250 1.09375 1.12500 −0.028362 6 1.093750 1.109375 1.125000 −0.006643 7 1.1093750 1.1171875 1.1250000 0.004208 8 1.10937500 1.11328125 1.11718750 −0.001216 . . . . . . . . . . . . . . . A virtue of the bisection method is that formula (1.24) provides a predetermined estimate for the accuracy of the computed solution. In Example 1.7 the width of the starting interval was b0 − a0 = 2. Suppose that Table 1.1 were continued to the thirty-first iterate; then, by (1.24), the error bound would be |E31| ≤ (2 − 0)/2 32 ≈ 4.656613 × 10−10. Hence c31 would be an approximation to r with nine decimal places of accuracy. The number N of repeated bisections needed to guarantee that the N th midpoint cN is an approximation to a zero and has an error less than the preassigned value δ is N = int à ln(b − a) − ln(δ) ln(2) ! (1.29) The proof of this formula is left as an exercise. Another popular algorithm is the method of false position or the regula falsi method. It was developed because the bisection method converges at a fairly slow speed. As before, we assume that f(a) and f(b) have opposite sings. The bisection method used the midpoint of the interval [a, b] as the next iterate. A better approximation is obtained if we find the point (c, 0) where the secant line L joining the points (a, f(a)) and (b, f(b)) crosses the x -axis (see Figure 1.8). To find the value c, we write down two versions of the slope m of the line L: m = f(b) − f(a) b − a , (1.30) where the points (a, f(a)) and (b, f(b)) are used, and m = 0 − f(b) c − b , (1.31) 17