Root finding using the Bisection Method - exact solutions

As a final blog on this program, I want to cover the situation where an exact solution of f(x)=0 is found by the bisection method, i.e. where the program finds α where f(α)=0 and not just an approximation to α.

Consider the quadratic equation 160x²-428x-645=0. This equation has a root around x=-1 because f(-1.1)=19.4 and f(-0.9)=-130.2 (where f(x)=160x²-428x-645), so f changes sign between -1.1 and -0.9. If we now edit the program to have 160C²-428C-645 instead of C-COS(C) in the "subroutine" then on running the program with A being -1.1, B being -0.9 and D set to 1x10^-5 we obtain the root -1.075 in 3 bisections. This is the exact value for the root because the quadractic equation can be factorised to (x-3.75)(x+1.075)=0, so the roots are x=-1.075 and x=3.75.

This shows that the program can cope with the situation where it finds the root exactly. Of course, this doesn't always happen even if an exact value could be found. For example, rerunning the program with A set to -1.5, B set to -0.5 and D as before, we obtain C as -1.075004578 in 17 iterations.

Root finding using the Bisection Method - execution of the program

In a previous post I provided a program for finding the root of a function f(x) using the bisection method. To show how this works, consider the problem of calculating where the lines y=x and y=cos x intersect on a graph of y against x (see the above plot from Wolfram Alpha). There is a single point of intersection somewhere between x=0 and x=π/2 and to find it we need to obtain the solution of x=cos x, i.e. x-cos x=0. This trigonometric equation has no obvious solutions and so we can use the bisection method to find a numerical solution (where f(x)=x-cos x).

The program given is already set up for this. On running the program the display shows A? This is the lower limit of the interval that is being bisected. Enter [0] and press [EXE]. The display then shows B? This is the upper limit of the interval. Enter [SHIFT] [π] [/] [2] and press [EXE]. The display then shows D? This the error tolerance. Enter [1] [EXP] [-] [5] and press [EXE].

After a moment or two the display shows that the calculated root C is 0.739085126 and pressing [EXE] once more, the number of iterations X used in the calculations was 18. The maximum error in the root is  ±0.0000060, smaller than the tolerance of ±0.00001 requested, as expected (the maximum error can be calculated from C-A). So we can probably quote the root as being 0.7391 to four decimal places and be confident that this is correct (other maths software shows that the root is 0.739085133 to 9 decimal places).

Repeating the bisection with different intervals but the same level of tolerance in the error gives the following results:-

A=0.5, B=1, C=0.739082336, X=16
A=0.25, B=1.5, C=0.739091873, X=17
A=0.7, B=0.8, C=0.73908081, X=14

and this confirms that quoting the root as 0.7391 to 4 d.p. is correct.

Root finding using the Bisection Method - the program

I discussed the logic for this program in a previous blog. Here is the logic converted into a program for the fx-50F:-

?→A:A→C:0→X:Goto 1:Lbl 2:Y→M:?→B:?→D:Lbl 4:X+1→X:.5(A+B)→C:.5(B-A)<D=>Goto 0:Goto 1:Lbl 3:Y=0=>Goto 0:If MY>0:Then C→A:Y→M:Else C→B:IfEnd:Goto 4:Lbl 0:C▲X▲Lbl 1:C-COS(C)→Y:X=0=>Goto 2:X≠0=>Goto 3:

This is pretty much how the program looks when keyed into the calculator in edit mode. Special Program Commands (? → => : Lbl = < > ≠ If Then Else IfEnd ▲ Goto) are input using the [SHIFT] [P-CMD] keys. The cursor key (marked Replay) is used to switch between various screens of commands. Memory variables A, B, C, D, X, Y, and M are input using [ALPHA] [A], [B] etc keys. The ":" Separator Code command is used frequently and can be alternatively input using the [EXE] key.

This program is 132 steps in length.