Notes on the Bisection MethodDr. HolmesNovember 6, 2009Here and in everything that follows, a < b are real numbers (so [a, b] is aclosed interval) and f is a continuous function on that closed interval.1 The Bisection Method in GeneralWe define a sequence of closed intervals {In}n∈N. Each Inis of the form[an, bn]. I1= [a, b], so a1= a, b1= b. We assume that for each n, In+1iseither [an,an+bn2] or [an+bn2, bn] (which one it is may be different for differentvalues of n): at each step we bisect the interval and choose one of the resultinghalf-intervals as the next interval.It is clearly true that In+1⊆ In, so the intersection of all the In’s isnonempty, and there is at least one number c which belongs to all the inter-vals. We claim further that there is exactly one number c which belongs toall the intervals In.Because of the bisection construction, we know that bn−an=12n−1(b−a).Suppose that c ≤ d are numbers each of which belongs to all of theintervals In. Clearly 0 ≤ d − c ≤ bn− anfor each n. Thus 0 ≤ d − c ≤12n−1(b − a) for every n. But this means that d − c = 0, so c = d.The bisection method is always to be understood as a way of closing downon a uniquely determined number in [a, b] with desired properties.2 Using the Bisection Method to Prove theIntermediate Value TheoremNow suppose that f is continuous on [a, b], f (a) < 0 and f (b) > 0. Our aimis to find c in (a, b) such that f (c) = 0.1All that we need to do is indicate how to choose the In’s.I1= [a, b] as usual. We want to choose the In’s so that f(an) ≤ 0 andf(bn) > 0 at each stage. (of course if we find f(an) = 0 we are done!)We can do this for n = 1 by our hypotheses.Suppose we have chosen Ikso that f(ak) ≤ 0 and f(bk) > 0. If f(ak+bk2) ≤0, we choose [ak+bk2, bk] as Ik+1: it satisfies the conditions we want. f (ak+bk2) >0, we choose [ak,ak+bk2] as Ik+1, and it satisfies the conditions we want.We have shown by mathematical induction that we can find intervals Iksatisfying the desired conditions for every n ∈ N.It then follows by the general results about the bisection method thatthere is a unique real number c which belongs to every In.There are three cases, c = a, c = b (these we will show to be impossible)and c ∈ (a, b). We consider the last of these cases first.Suppose f (c) > 0. Because f is continuous at c, there is a δ > 0 suchthat if |x − c| < δ, we will have |f (x) − f (c)| <|f(c)|2, from which it followsthat f (x) ≥|f(c)|2> 0. But we can find an n such that12n−1(b − a), the lengthof the interval In, is less than δ, so the whole interval Inlies in the interval(c − δ, c + δ). We have just seen that all values of f on this interval arepositive, but also Inis included in the interval, and f is nonpositive at anbythe basic properties of the In’s. This is a contradiction.Suppose f (c) < 0. Because f is continuous at c, there is a δ > 0 suchthat if |x − c| < δ, we will have |f (x) − f (c)| <|f(c)|2, from which it followsthat f(x) ≤ −|f(c)|2< 0. But we can find an n such that12n−1(b − a), thelength of the interval In, is less than δ, so the whole interval Inlies in theinterval (c − δ, c + δ). We have just seen that all values of f on this intervalare negative, but also Inis included in the interval, and f is positive at anby the basic properties of the In’s. This is a contradiction.So f (c) = 0 in the first case [where c ∈ (a, b)].Suppose c = a (we need to rule this out, so we assume it and argue to acontradiction). For some δ > 0, for all x ∈ [a, a + δ), |f(x) − f(a)| <|f(a)|2, sof(x) <f(a)2< 0. Now choose an Inwith total length < δ as above, so Inisincluded in [a, a + δ), and get a contradiction in the same way (f is negativeon [a, a + δ) but has a positive value at bn).Suppose c = b (we need to rule this out, so we assume it and argue to acontradiction). For some δ > 0, for all x ∈ (b − δ, b], |f(x) − f (a)| <|f(b)|2,so f (x) >f(b)2> 0. Now choose an Inwith total length < δ as above, so Inis2included in [a, a + δ), and get a contradiction in the same way. (f is positiveon (b − δ, b] but has a nonpositive value at an).This completes the proof: the only case that can occur is c ∈ (a, b) andwe have shown f (c) = 0 in this case.3 Using the Bisection Method to Prove thata Continuous Function on a Closed Intervalis Bounded AboveSuppose that f is continuous on [a, b] and the range of f is unbounded. Wededuce a contradiction using the bisection method.We define the sequence of intervals Inwith the intention that the set ofvalues of f on each Inhave no upper bound.By hypothesis, this is true for I1= [a, b].Suppose that we have constructed Iksuch that the set of values of f onIkhas no upper bound. Then either the set of values of f on [ak,ak+bk2] isunbounded, in which case we choose Ik+1= [ak,ak+bk2], or the set of values off on [ak,ak+bk2] has an upper bound N1. It follows in this case that the setof values of f on [ak+bk2, bk] is unbounded: if it had an upper bound N2, thenmax(N1, N2) would be an upper bound for values of f on Ik, which wouldcontradict our assumptions. So in the second case we can choose [ak+bk2, bk]as Ik+1, and in both cases the set of values of f on Ik+1is unbounded. Wehave shown by mathematical induction that we can select a suitable Inforevery n.Now we know that there is a unique c which belongs to all the In’s. Asabove, there are three cases, c = a, c = b, and c ∈ (a, b). We will show thateach one leads to contradiction.If c ∈ (a, b), we know that f is continuous at c, so we can choose a δ suchthat if |x − c| < δ then |f(x) − f (c)| < 1. It follows from this that the setof values of f on (c − δ, c + δ) is bounded above by f (c) + 1. Now choosen so that the length of Inis less than δ. The interval Inwill be completelyincluded in (c − δ, c + δ) so the values of f on Inwill be bounded as well.This is a contradiction.If c = a, we know that f is continuous at c, so we can choose a δ suchthat if a < x < a + δ then |f(x) − f(a)| < 1. It follows from this that theset of values of f on …