[Math] How to show that regula falsi has linear rate of convergence

numerical methodsrate-of-convergenceregula falsi

How can we prove that regula falsi method has linear rate of convergence?

I know how to do so for the secant method but I am unable to derive it for regula falsi.

Any help is much appreciated. Thank you.

Best Answer

Assume first that the function has a root in $x=0$ and looks locally around $x=0$ like $f(x)=cx(x+d)$ with $c,d>0$ and the bracketing interval $[a,b]$ satisfying $-d<a<0<b$.

Now show that the function value at the mid-point $$ m=\frac{af(b)-bf(a)}{f(b)-f(a)}=\frac{ab·c(b-a)}{c(b-a)(b+a+d)}=\frac{ab}{a+b+d}<0 $$ is always negative (or show $m=a\frac{b}{b+(a+d)}>a>-d$), $$ f(m)=c·\frac{ab}{a+b+d}·\frac{ab+da+db+d^2}{a+b+d}=c·\frac{ab(a+d)(b+d)}{((a+d)+b)^2}<0, $$ as $a+d>0$. This means that the midpoint $m$ is always used to replace the left point $a$. For sufficiently small $a$, $$a_+=m\approx\beta a$$ with $\beta=\frac{b}{b+d}$ which establishes the linear convergence.

As $d$ is determined by the curvature of the function $f$, the convergence speed depends only on $b$, the farther $b$ is from $0$, the closer $β$ is to $1$, thus the slower the convergence. This also tells that any measure, no matter how crude, that decreases $b$ will substantially increase the speed of convergence.


To translate this to the more general case, compare the quadratic approximation $$cx(x+d)=cdx+cx^2$$ with the quadratic Taylor polynomial $$f(x^*+x)=f(x^*)+f'(x^*)x+\frac12f''(x^2)x^2+o(x^2)$$ in the root $f(x^*)=0$.

We find $c=2f''(x^*)$ and $cd=f'(x^*)$, which of course only makes sense if both quantities are different from zero. Apply reflections on the $x$ and $y$ axes to get both derivatives and thus both of $c$ and $d$ to be positive.

Related Question