CTK Insights

19 Apr

The Regula Falsi - Iterated

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

For all m, n\gt 0,

a_{m+n}=F(a_{m},a_{n})=\frac{a_{m}a_{n}+2}{a_{m}+a_{n}}.

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

Leave a Reply


4 − = zero

© 2014 CTK Insights | Entries (RSS) and Comments (RSS)

Powered by Wordpress, design by Web4 Sudoku, based on Pinkline by GPS Gazette