Contents

• 1  Regula-Falsi method
• 2  Exercise
  • 2.1  Approximate, using the Regula-Falsi method, $r=\sqrt{3}.$ Use as initial interval $[1,2].$ Perform three iterations.
  • 2.2  Calcular el residual.
  • 2.3  Give an error bound for the approximation. Is it a good error bound? Why?

Regula-Falsi method

The Regula-Falsi method can be considered a hybrid of the Bisection method with the Secant method.

• We start with a function $f$, and two initial points $a$ and $b$ that satisfy the conditions of Bolzano's theorem, as in Bisection.
• In each iteration we calculate a new point $c$ with the same formula as the Secant, using the two previous points.
• We discard one of the two points from the previous iteration using the same criteria as for Bisection, that is, we are left with the two points for which the function meets Bolzano's theorem conditions..

The formula for computing the next iteration with the secant method is

$$x_k=x_{k-1}-f(x_{k-1})\dfrac{x_{k-1}-x_{k-2}}{f(x_{k-1})-f(x_{k-2})}$$

In regula-falsi method, the next point is

$$c = b - f(b)\frac{b-a}{f(b)-f(a)}=\frac{b f(b)-b f(a)-b f(b)+a f(b)}{f(b)-f(a)}=\frac{a\,f(b)-b\,f(a)}{f(b)-f(a)}$$

Algorithm

• Given $a_1=a$, $b_1=b$.
• For $k=1,2,\ldots,\mathrm{MaxNumIter}$

  • Compute the point $x_k=\dfrac{a_k\,f(b_k)-b_k\,f(a_k)}{f(b_k)-f(a_k)}$.
  • If the point $x_k$ meets stopping conditions, stop.
  • Else,

    • if $f(a_k)f(x_k)<0$ then:

      $ a_{k+1}=a_{k},$ $ b_{k+1}=x_k,$

    • else, if $f(x_k)f(b_k)<0$ then:

      $ a_{k+1}=x_{k},$ $ b_{k+1}=b_k.$

    • else:

      stop.

Once Loop Reflect

Drawbacks

• It converges more slowly than the Secant method, as the order of convergence is 1.
• The interval containing the zero does not always decrease in length significantly with iterations, as in Bisection. Therefore, its length is not a good error bound, as in Bisection.

Advantages

• Unlike the secant method, starting with the Bolzano conditions, the convergence is guaranteed.
• As the secant method, it does not need the derivative.

Exercise

Approximate, using the Regula-Falsi method, $r=\sqrt{3}.$ Use as initial interval $[1,2].$ Perform three iterations. Compute the residual. Give an error bound for the approximation. Is it a good error bound? Why?

Approximate, using the Regula-Falsi method, $r=\sqrt{3}.$ Use as initial interval $[1,2].$ Perform three iterations.

The equation is

$$x=\sqrt{3} \quad \Rightarrow \quad x^2=3 \quad \Rightarrow \quad x^2-3=0$$

And the function $f(x)=x^2-3$

The sequence generated by Regula-Falsi uses the formula

$$x_k=\dfrac{a_k\,f(b_k)-b_k\,f(a_k)}{f(b_k)-f(a_k)}$$

Iterations

Iteration 1

The interval is $[1,2]$ and the next point is

$$c = \frac{a\,f(b)-b\,f(a)}{f(b)-f(a)}= \frac{1(2^2-3)-2\,(1^2-3)}{(2^2-3)-(1^2-3)}=\frac{1+4}{1+2}= \frac{5}{3}=1.666667$$

As the signs of $f(1.666667)=-0.22$ and $f(2)=1$ are different, the next interval is $[1.666667,2]$.

Iteración 2

The interval is $[1.666667,2]$ and the next point is

$$c = \frac{1.666667(2^2-3)-2\,(1.666667^2-3)}{(2^2-3)-(1.666667^2-3)}=1.727273$$

As the signs of $f(1.727273)=-0.02$ and $f(2)=1$ are different, the next interval is $[1.727273,2]$.

Iteración 3

The interval is $[1.727273,2]$ and the next point is

$$c = \frac{1.727273(2^2-3)-2\,(1.727273^2-3)}{(2^2-3)-(1.727273^2-3)}=1.731707$$

\begin{array}{|r|rrr|rrr|r|} \hline \mathrm{iteration} & a & c & b & f(a) & f(c) & f(b) & \mathrm{Error}\; \mathrm{bound}\\ \hline 1 & 1.000000 &{\color{red}{1.666667}} &{\color{blue}{2.0}} & -2.00 &{\color{red}{-0.222}} & {\color{blue}{1.0}} & 0.333333\\ 2 & 1.666667 &{\color{red}{1.727273}} &{\color{blue}{2.0}} & -0.22& {\color{red}{-0.017}} & {\color{blue}{1.0}} & 0.272727\\ 3 & 1.727273 &{\color{red}{1.731707}} &{\color{blue}{2.0}} & -0.02 &{\color{red}{-0.001}} & {\color{blue}{1.0}} & 0.268293\\ \hline \end{array}

Once Loop Reflect

Calcular el residual.

The value of the function at the root is zero. The value of the function in the approximation is called residual and, if it is a good approximation, it is a small

$$r =|f(x_3)|=|1.731707^2-3|=0.001$$

Also, the residual in step $k$ is known, while the error is unknown (we need the exact solution, which is what we are looking for).

Como $\alpha= 1.732051$ el error absoluto es

$$e_a = |x_3-\alpha|=|1.731707-1.732051|=0.0003$$

Give an error bound for the approximation. Is it a good error bound? Why?

In the table, we have calculated an error boundary. This, as in the Bisection method, is given by the length of the last interval. But in the case of Regula-Falsi, it is not very useful because, in many cases (like this one) the length of the interval does not decrease significantly as we approach the zero because the method creates a sequence that, from a certain point, approaches the zero always from the left or always from the right.

Thus, the final boundary is approximately 0.28, which is very different from the 0.0003 error and, therefore, does not provide relevant information.

---

Taking into account that the zero we are looking for is $\alpha= 1.732051,$ let's compare the three methods that we have used to solve this problem

\begin{array}{|cccc|} \hline k & \mathrm{Newton} & \mathrm{Secant} & \mathrm{Regula-Falsi}\\ \hline 1 & 2.000000 & 1.666667 & 1.666667\\ 2 & 1.750000 & 1.727273 & 1.727273\\ 3 & 1.732143 & 1.732143 & 1.731707\\ \hline \end{array}

In this case, we have obtained the same results with Newton's and Secant methods. Regula-Falsi is only slightly worse.