# Thread: Num. analysis #2

1. ## Num. analysis #2

Hello. I'm having problem with these:

a). Prove that the Bisection algorithm gives a sequence that has the bound of error which converges linearly to zero.

b). The sequence $\displaystyle F_n$ described as $\displaystyle F_0$, $\displaystyle F_1$, and $\displaystyle F_{n+2}=F_n+F_{n+1}, n\geq0$, is called Fibonacci sequence and $\displaystyle x_n=\frac{F_{n+1}}{F_n}, \lim_{n\to\infty}{x_n}=x$ exists, prove that that limit is $\displaystyle x=\frac{(1+\sqrt5)}{2}$. (This number is called golden ratio)

Thank you for your time.

2. Originally Posted by javax
Hello. I'm having problem with these:

a). Prove that the Bisection algorithm gives a sequence that has the bound of error which converges linearly to zero.
If the initial interval length is $\displaystyle L$, the interval length after $\displaystyle n$ itterations is

$\displaystyle L_n=\frac{L}{2^n}$

So:

$\displaystyle L_{n+1}=L_n/2$

and as $\displaystyle L_k$ is a bound on the error the convergence is linear.

CB

3. Originally Posted by javax
b). The sequence $\displaystyle F_n$ described as $\displaystyle F_0$, $\displaystyle F_1$, and $\displaystyle F_{n+2}=F_n+F_{n+1}, n\geq0$, is called Fibonacci sequence and $\displaystyle x_n=\frac{F_{n+1}}{F_n}, \lim_{n\to\infty}{x_n}=x$ exists, prove that that limit is $\displaystyle x=\frac{(1+\sqrt5)}{2}$. (This number is called golden ratio)

Thank you for your time.
$\displaystyle x_n=\frac{F_{n+1}}{F_n}=\frac{F_n+F_{n-1}}{F_n}=1+\frac{1}{x_{n-1}}$

Now we are told that the limit as x \to \infty exists, so the limit must satisfy the equation:

$\displaystyle x=1+\frac{1}{x}$

which may be simplified to:

$\displaystyle x^2-x-1=0$

which has roots:

$\displaystyle x=\frac{1\pm\sqrt{5}}{2}$

Of these roots we may discard the one with the negative sign as $\displaystyle x$ must be greater than $\displaystyle 0$ (in fact greater than $\displaystyle 1$), so the required root is:

$\displaystyle x=\frac{1+\sqrt{5}}{2}$

CB