Ostroswki-based enhacement for the False Position root-seeking Method
01-08-2017, 03:09 PM (This post was last modified: 01-08-2017 06:49 PM by Namir.)
Post: #1 Namir Senior Member Posts: 810 Joined: Dec 2013
Ostroswki-based enhacement for the False Position root-seeking Method
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)