Regula-Falsi Method (False-Position Method)

It seems that the simplest methods often converge the slowest. This certainly seems the case here.

The bisection method does not use values of $f(x)$. Only their sign. However, the values could be exploited. One way to use values of $f(x)$ is to bias the search according to value of $f(x)$: use a weighted average

Choose $c$ as the intercept of the secant line through $(a,f(a))$ and $(b,f(b))$.

$$\frac{y-f(b)}{x-b}=\frac{f(a)-f(b)}{a-b} \mbox{This gives the formula for the secant line}$$

pick $y=0$, the intercept then

$\quad x_1=\displaystyle \frac{af(b)-bf(a)}{f(b)-f(a)}\mbox{the next approximation}$

The algorithm is depicted in Figure 15.

Figure 15: Regula-Falsi Algorithm.

$x_1$ is first approximation to $x^*$

As in bisection, if $f(x_1)\ne 0\Rightarrow f(a)f(x_1)<0$ or $f(x_1)f(b)<0$

$\Rightarrow$ there must be a root $x^{\star}\in [x_1, b].$ Suppose $f(x_1)f(b)<0$, then

$$x_2=\frac{x_1f(b)-bf(x_1)}{f(b)-f(x_1)},\,\mbox {etc.}$$

This is the pseudo code for the Regula Falsi method:

User inputs: a,b, max, epsilon
Initialize: iteration = 0
              xold = b       //to start out

Inside a  loop with condition that iteration <=max:

  while(iteration <=max)
	compute f(a)
	compute f(b)

	x = a - ((f(a)*(b-a)) / (f(b)-f(a))
            increment iteration

	Test:
	if |x-xold| < epsilon*|x| then
	   output x
	   goto stop
	else
	   output (iteration, a, b, x)
	   xold = x
	   compute f(x)
	
	    if f(a)*f(x) > 0    // here we are testing
                                // for a positive sign,
                                // not necessarily the value
	              a = x
                else
                      b = x
                end
             end
      end

stop

Problem: Stopping criteria (Recall that in bisection we had intervals getting smaller)

Could use

(1)

$$\vert x_n-x_{n-1}\vert<\varepsilon$$

and

(2)

$$\begin{eqnarray*} \vert f(x_n)\vert<\delta \end{eqnarray*}$$

however these can lead to problems:

Suppose $\vert x_n-x_{n-1}\vert=\displaystyle \frac{1}{n}$ this is satisfied by (1) with $n\ge \displaystyle \frac{1}{\varepsilon }$

however $\{x_n\}$ actually diverges! MORE LATER.

Suppose $f(x)=(2-x)^7,\quad x^{*}=2\mbox { and }\quad x_n=2-\frac{1}{n}\Rightarrow \vert f(x_n)\vert<10^{-2}\,\forall n>1$

whereas $\vert x^{*}-x_{n}\vert <10^{-2}\mbox{only for} n>100$

So the test will signal convergence prematurely!

Thus, use

and use a relative error as well for $f(x_n)$. $\Box$