Method of False Position (Regular Falsi) - Pros/Cons

Could anyone provide and explain some drawbacks and benefits of the method of false position against say newtons method.

I know one of benefits is that it doesn't require the derivative and one of the cons is that one of the interval definitions can get stuck (Incomes the Illinois method to save the day). However I wondered if there were any more?

Thanks!

Solution 1:

False position:

For functions which are not convex at the root, such as $\sqrt[3]x$ or $\arctan(x)$, false position will give tight bounds without either bound getting stuck. For simple roots, the behavior becomes equivalent to the secant method, giving fast convergence.

For functions which are convex at the root, such as $e^x-1$ or $\ln(x)$, one bound will remain fixed. The convergence becomes linear for simple roots and worse otherwise. This means that at best for convex functions, it converges at a rate which is a constant multiple of bisection, better or worse depending on the size of the initial interval and the curvature of the function over the initial interval.

This drawback alone is a major alarm, because it means most situations will cause false position to perform about as good as bisection. There is also less guarantee on the behavior of false position. Even if it converges linearly, it may converge very slowly (e.g. $x^{10}-1$ on the initial interval $[0,10]$). For roots which are not simple, the convergence is usually sublinear.

Conclusion:

Overall, the benefit of sometimes converging as fast as the secant method is usually outweighed by how slow and unreliable false position can be.

Modifications:

As you point out, there are modifications of this which attempt to remedy this issue, most famously the Illinois method. The Illinois method has the advantage of superlinear convergence for simple roots with an order of convergence of $\sqrt[3]3\approx1.44$ for convex functions and $\varphi\approx1.61$ for non-convex functions.

This is actually comparable to Newton's method, giving higher order of convergence$^{[1]}$ for simple roots. Another advantage is that it usually gives tight bounds on the root and is guaranteed to converge. The drawback is the the function has to change signs on the initial endpoints.

Similar to Newton's method and false position, convergence, especially initial convergence, may be slow if the initial points are chosen poorly and the function exhibits bad behaviors such as large curvature (e.g. $x^{10}-1$ on the initial interval $[0,10]$). In such cases, especially for low accuracy estimations, it is better to use hybrid modifications involving bisection.

Conclusion:

The Illinois method is comparable to both the secant and Newton methods in terms of speed and is also guaranteed to converge but requires a change in the function's sign. For more extreme cases, it is better to use hybrid methods using bisection which guarantee a minimum speed of convergence.

$[1]:$ This is per function evaluation, which is where avoiding the derivative comes into making Newton slower than its theoretical order of convergence.

Solution 2:

Too long for a comment:

Regula falsi might be interpreted as computing a convex combination of the interval endpoints at each iteration. The pure method uses the inverse function values as weights, $$ c=\frac{|f(a)|^{-1}\,a+|f(b)|^{-1}\,b}{|f(a)|^{-1}+|f(b)|^{-1}} $$ so that the endpoint with the smaller function value gets more weight. Because of $f(a)f(b)<0$, this can be rewritten in the usual way.

The Illinois and other variants modify these weights according to the iteration history $$ c=\frac{u\,|f(a)|^{-1}\,a+v\,|f(b)|^{-1}\,b}{u\,|f(a)|^{-1}+v\,|f(b)|^{-1}} $$ so that the weight of the unmodified side is increased in each step, drawing the midpoint in its direction and thus eventually over the root that is (too) slowly approximated by the changing side of the interval.

Brents method, in contrast and among other things, performs explicit detection of stalling and inserts a bisection step to move also the other interval end.

Solution 3:

There is a good introduction in Bill Kahan's notes, which you can find here.

His conclusion is that the secant method is often better. It's theoretical rate of convergence is slower than Newton's, but not by much (1.618 vs 2), and it has other benefits that out-weigh (theoretical) speed of convergence. For example, the secant method converges from a wider range of starting points. One of the referenced documents (this one) gives much more detail.

Solution 4:

Advantage of Regula-Falsi with respect to Newton's method:

Regula Falsi always converges, and often rapidly, when Newton's method doesn't converge.

Disadvangage of Regula-Falsi with respect to Newton's method:

Newton's method converges faster, under conditions favorable to it.

When ordinary Regula-Falsi has slow convergence, try Anderson-Bjork Regula-Falsi.

When it, too, converges slowly, use Bisection.

Bisection is the only method that always converges at a useful (but not spectacular) rate.