2

I've been studying numerical analysis and I ran into false position method and I can't figure out its diffrence between secant method , because I also heard that the convergence is guaranteed in false position method but not in secant method. And also what is regula-falsi method ? There was a table which said the rate of convergence for secant,bisection and regula-fasi method is respectively 1.618 , 0.5 and 1 . But I even don't know how it's calculated ! Aren't they linear ?

Elias
  • 197

1 Answers1

3

False-position method is another name for regula falsi.

The difference to the secant method is the bracketing interval. Meaning that the new secant root is not computed from the last two secant roots, but from the last two where the function values have opposing signs.

Yes, bracketing interval methods ensure convergence, as they shrink the interval that is known---via intermediate-value theorem---to contain a root. Thus the sequences of interval end-points are monotonous, both converging, at least one of them converging to a root.

The secant method, if it converges to a simple root, has the golden ratio $\frac{\sqrt5+1}2=1.6180..$ as superlinear order of convergence.

Bisection, in only considering the length of the bracketing interval, has convergence order 1, that is, linear convergence, and convergence rate $0.5$ from the halving of the interval in every step.

Regula falsi in most cases does not converge in the sense of shrinking the interval towards zero length. In such a situation, one side of the interval will converge to the root linearly, with order 1. And most likely a very unfortunate convergence rate close to $1$.

That is why anti-stalling versions of the method exist. For instance the Illinois modification shrinks the interval systematically towards zero length and reduces the error by the third power every 3 steps in a quite periodic pattern, so has a superlinear order of convergence of $\sqrt[3]3= 1.4422..$. One might claim that this is still faster than the $\sqrt2=1.4142..$ per function evaluation of the Newton method.

See Accuracy of approximation using linear interpolation

Lutz Lehmann
  • 126,666
  • Great thanks , but first of all how to find the convergence rate and convergence order ? And what are bracketing interval methods exactly? I know bolzano's theorem but haven't heard about this one . – Elias Mar 26 '21 at 12:17
  • 1
    You do a Taylor expansion at the root and trace the evolution for some steps until a pattern emerges. Then decide what defines the "beat" of the algorithm, full method steps or function evaluations. In many practical cases, function evaluation is more expensive than everything else in the method step. So in Newton, the derivative evaluation is at least one additional function evaluation, if not more expensive. – Lutz Lehmann Mar 26 '21 at 12:22
  • Do you know any article with more example and further explanation about calculating convergence rate and convergence order ? – Elias Mar 26 '21 at 12:31
  • 1
    Not from the top of my head. You could check the Wikipedia pages of the methods, also the other main languages, German, French, Spanish, if you can read it, Russian, for the literature cited there. In many cases, good overview sources are cited. – Lutz Lehmann Mar 26 '21 at 13:28