HP Forums
A New Variant of the Bisection Method - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: A New Variant of the Bisection Method (/thread-7486.html)

A New Variant of the Bisection Method - Namir - 12-29-2016 04:56 PM

Encircling-Variant of Bisection

This algorithm is inspired by the Bisection method. It requires, in general, fewer iterations than the Bisection. The basic idea is to start with x=A, such that A<Xroot, and march towards the root. As the value of A passes over the root, we change the sign of the marching step and also reduce it. This change makes the value of A move around the root and closes in on it.

Given a function f(x)=0 and x=A, such that A<Xroot, and the root bracketing interval [A,Z], and the tolerance Toler. The value of Z is needed only to calculate the initial search step. You can eliminate Z if you provide the value for the initial search step.

Removing the nested IF statement causes the algorithm to slow down and require significantly more iterations than the Bisection method.

Delta = (Z-A)/2
Fa = f(A)
  B = A
  Fb = Fa
  A = A + Delta
  Fa = f(A)
  If Fa*Fb<0 then
    Delta = -Delta/4
    C = (A + B) / 2
    Fc = f(C)
    If Fa * Fc > 0 Then
      A = C
      Fa = Fc
    End If
  End If
Loop Until Abs(Delta)<=Toler
Return A as the refined root