CTK Insights

Tweet

The Regula Falsi method - the method of the false position - for getting an approximation to a solution of an equation $f(x)=0$ consists in applying the formula

$t=\frac{x_{1}f(x_{2})-x_{2}f(x_{1})}{f(x_{2})-(f(x_{1})}$

with two initial guesses $x_{1}$ and $x_{2}$. The Secant method consist in iterating the formula in a way that depends on the sign distribution of successive values of $f(x)$.

But there are two other (more deterministic, in a sense) ways to engage the formula in an iterative manner. To distinguish between the two I shall use different letters. One keeps one endpoint fixed:

$a_{n+1}=\frac{a_{1}f(a_{n})-a_{n}f(a_{1})}{f(a_{n})-(f(a_{1})}$.

The other replaces the endpoints at every step:

$b_{n+1}=\frac{b_{n-1}f(b_{n})-b_{n}f(b_{n-1})}{f(b_{n})-(f(b_{n-1})}$.

What follows constitutes a very meaningful exercise for operations with fractions. It can be carried out manually and will entertain and surprise an observant student.

We shall look for an approximation to $\sqrt{2}$ by solving the quadratic equation $x^{2}-2=0$. One can check that with $f(x)=x^{2}-2$ the two iterations become

$a_{n+1}=\frac{a_{1}a_{n}+2}{a_{n}+a_{1}}$.

and, respectively,

$b_{n+1}=\frac{b_{n-1}b_{n}+2}{b_{n}+b_{n-1}}$.

I choose $a_{1}=b_{1}=1$ and $a_{2}=b_{2}=3/2$. Starting with these we get two sequences:

$a_{n}=\{1,3/2,7/5,17/12,41/29,99/70,239/169,577/408,\ldots\}$

and

$b_{n}=\{1,3/2,7/5,41/29,577/408,47321/33461\ldots\}$

Now is the time for observation. What one may be expected to notice is that $b_{n}$ appears to be a subsequence of $a_{n}$. And not just. Besides $b_{1}=a_{1}$ and $b_{2}=a_{2}$, we also have

$b_{3}=a_{3},b_{4}=a_{5},b_{5}=a_{8},\ldots$

As a matter of fact, the indices of the terms of the $a$-sequence which are the terms of the $b$-sequence are

$1, 2, 3, 5, 8,\ldots$

and appear to form the Fibonacci sequence. They do indeed form the Fibonacci sequence and this is worth proving.

Define $F(x,y)=\frac{xy+2}{x+y}$. So defined function $F$ has the properties of commutativity $F(x.y)=F(y,x)$ and associativity:

$F(x,F(y,z))=F(F(x,y),z)$.

The proof consists in verification that both sides are equal to

$\frac{xyz + 2(x+y+z)}{xy+yz+zx+2}$.

Proposition

Proof

The proof is by induction on $m$. By definition,

$a_{1+n}=F(a_{1},a_{n})=\frac{a_{1}a_{n}+2}{a_{1}+a_{n}}$,

for all $n\gt 0$. Now assume that $a_{m+n}=F(a_{m},a_{n})$ holds for a some $m=k\gt 0$ and all $n\gt 0$. Then, in particular, for all $n$

$a_{k+(n+1)}=F(a_{k},a_{n+1})=F(a_{k},F(a_{1},a_{n}))=F(F(a_{k},a_{1}),a_{n})=F(a_{k+1},a_{n})$,

implying

$a_{(k+1)+n}=a_{k+(n+1)}=F(a_{k+1},a_{n})$,

as required. Which completes the proof of Proposition.

Proposition explains the manner in which sequence $b_{n}$ is embedded into sequence $a_{n}$. Sequence $a_{n}$ converges to $\sqrt{2}$ and so does sequence $b_{n}$ but, since $b_{n}$ skips a growing number of indices, its convergence is faster. We'll look into that in another post.

References

1. D. Chakerian, The Rule of False Position, in Mathematical Adventures for Students and Amateurs, D. F. Hayes, T. Shubina, (editors), MAA, 2004, 157-169