Ostroswki-based enhacement for the False Position root-seeking Method

[Namir]

The False Position method is a root-bracketing method. It has faster convergence than the Bisection method. The False Position has a major weakness is that the root-bracketing range does not always shrink tightly around the root. An enhancement, called the Illinois Algorithm fixes that weakness by reducing the function value of either A or B that is not changed by the core False Position method. Here is the pseudo-code for the Illinois Algorithm

Code:

Given function Fx(x)=0, initial root-bracketing range [A, B], root tolerance Toler, and function value tolerance FxToler:
  
  Fa = Fx(A)
  Fb = Fx(B)
  Side = 0
  R = 2
  Do
    C = (Fb * A - Fa * B) / (Fb - Fa)
    Fc = Fx(C)
    If Fc * Fa > 0 Then
      A = C
      Fa = Fc
      If Side = -1 Then Fb = Fb / 2
      Side = -1
    Else
      B = C
      Fb = Fc
      If Side = 1 Then Fa = Fa / 2
      Side = 1
    End If
  Loop Until Abs(A - B) <= Toler Or Abs(Fc) < FxToler
  
  Return C as the refined guess for the root.

The Russian mathematician Ostrowski had proposed an enhancement to Newton's method by calculating two refinements for the root per iteration. I present an enhancement to the Illinois Algorithm based on Ostroski's approach:

Code:


Given function Fx(x)=0, initial root-bracketing range [A, B], root tolerance Toler, and function value tolerance FxToler:

  Side = 0
  Fa = Fx(A)
  Fb = Fx(B)
  Do
    Slope = (Fb - Fa) / (B - A)
    Z = B - Fb / Slope
    Fz = Fx(Z)
    C = Z - Fz * (B - Z) / (Fb - 2 * Fz)
    Fc = Fx(C)
    If Abs(Fz) < Abs(Fc) Then
      Fc = Fz
      C = Z
    End If
    If Fc * Fa > 0 Then
      A = C
      Fa = Fc
      If Side = -1 Then Fb = Fb / 2
      Side = -1
    Else
      B = C
      Fb = Fc
      If Side = 1 Then Fa = Fa / 2
      Side = 1
    End If
  Loop Until Abs(A - B) <= Toler Or Abs(Fc) < EPS
  
  Return C as the refined guess for the root.

In the above code you can replace the following statements:

Code:

  Z = B - Fb / Slope
  Fz = Fx(Z)
  C = Z - Fz * (B - Z) / (Fb - 2 * Fz)

With the following If statement to make the calculations of Z more robust, if needed.

Code:

  If Abs(Fb) < Abs(Fa) Then
    Z = B - Fb / Slope
    Fz = Fx(Z)
    C = Z - Fz * (B - Z) / (Fb - 2 * Fz)
   Else
    Z = A - Fa / Slope
    Fz = Fx(Z)
    C = Z - Fz * (A - Z) / (Fa - 2 * Fz)
  End If

The Ostrowski variation of the Illinois Algorithm converges faster than the Illinois Algorithm.

Of course if you use Ostrowski's enhancement to Newton's method, you get a rate of convergence matching that of Hailey's method which has a third order of convergence rate.

Enjoy!

Namir