+- 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: Ostroswki-based enhacement for the False Position root-seeking Method (/thread-7538.html)
Ostroswki-based enhacement for the False Position root-seeking Method - Namir - 01-08-2017 03:09 PM
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 IfThe 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