Page 174 - Compact Numerical Methods For Computers

One-dimensional problems 163
Algorithm 18. Root-finding by bisection and False Position (cont.)

if fup*flow>0 then noroot := true else noroot := false; {STEP 1}
while (not noroot) and ((ubound-lbound)>tol) do
begin {main body of procedure to find root. Note that the test on
noroot only occurs once.}
{STEP 9b -- now placed here in Pascal version}
if (nbis*((ifn - 2) div nbis) = (ifn - 2)) then
begin {STEP 10 -- order changed}
write(‘Bisect‘);
b := lbound + 0.5*(ubound-lbound) {bisection of interval}
end
else
begin {STEP 2}
write(‘FalseP‘);
b := (lbound*fup-ubound*flow)/(fupflow);{to compute false position b}
end;
{STEP 3 -- begin convergence tests}
if b<=lbound then
begin
b := lbound; {to bring argument within interval again}
ubound := lbound; {to force convergence, since the function
argument b cannot be outside the interval [lbound, ubound]
in exact arithmetic by either false position or bisection}
end;
if b>=ubound then {STEP 4}
begin
b := ubound; lbound := ubound {as in STEP 3}
end;
ifn := ifn+1; {to count function evaluations} {STEP 5}
fb := fn1d(b, notcomp);
if notcomp then halt; {safety check}
write(ifn,’evalns: f(‘,b:16,‘)=‘,fb:10);
writeln(‘width interval= ‘,(ubound-lbound): 10);
if (ubound-lbound)>tol then
begin (update of interval)
if fb*flow<0.0 then {STEP 6}
begin {STEP 7}
fup := fb; ubound := b; {since root is in [lbound, b]}
end
else {we could check the equal to zero case -- root found,
but it will be picked up at STEPs 2, 3, or 4}
begin
flow := fb; lbound := b; {since root is in [b, ubound] }
end; {else}
end; {update of interval}
end; {while loop}
writeln(‘Converged to f(‘,b,‘)=‘,fb);
writeln(‘Final interval width =‘,ubound-lbound);
end; {alg18.pas = root1d}

The algorithm above is able to halt if a point is encountered where the function is not computable.
In later minimisation codes we will be able to continue the search for a minimum by presuming
such points are not local minima. However, in the present context of one-dimensional root-