# Deducing that the rate of convergence of the Secant method is 1.6.18 (Golden Ratio?

I have a function $$f(x) = e^x - (2-x)^3$$

And I am using the Secant method to find a root between $0$ and $5$.

I know that the value of this root is $t = 0.7261444\ldots$

Here's my output from matlab for 14 iterations where I show

$k$, $x_k$,$|t-x_k|$,$|t-x_k|^{1.68}$,$|t-x_k|^2$

 k | x(k)            | |t-x(k)|   | |t-x(k)|^1.68 | |t-x(k)|^2
1 | 0.00000000e+000 | 7.261e-001 |               |
2 | 5.00000000e+000 | 4.274e+000 |               |
3 | 1.91872122e-001 | 5.343e-001 | 3.489e-001    | 2.854e-001
4 | 3.17334769e-001 | 4.088e-001 | 2.225e-001    | 1.671e-001
5 | 6.42309464e-001 | 8.384e-002 | 1.554e-002    | 7.028e-003
6 | 7.12431582e-001 | 1.371e-002 | 7.420e-004    | 1.880e-004
7 | 7.25679662e-001 | 4.648e-004 | 2.518e-006    | 2.160e-007
8 | 7.26141901e-001 | 2.565e-006 | 4.049e-010    | 6.580e-012
9 | 7.26144465e-001 | 4.793e-010 | 2.205e-016    | 2.297e-019
10 | 7.26144466e-001 | 5.551e-016 | 2.347e-026    | 3.081e-031
11 | 7.26144466e-001 | 0.000e+000 | 0.000e+000    | 0.000e+000
12 | 7.26144466e-001 | 1.110e-016 | 1.571e-027    | 1.233e-032
13 | 7.26144466e-001 | 1.110e-016 | 1.571e-027    | 1.233e-032
14 | NaN | NaN | NaN | NaN


Now I am told in a question that the 'rate of convergence of a sequence $\{\epsilon_0,\epsilon_1,\epsilon_2,\ldots\}$ is $q$ if

$$\lim_{k \rightarrow \infty} \frac{\epsilon_{k+1}}{\epsilon_k^q} = u$$

for some constant $u$.

And I am told to make the program output $|t-x_k|$,$|t-x_k|^{1.68}$,$|t-x_k|^2$ and hence deduce that the rate of converge is greater than $1$, less than $2$ and roughly $(1 + \sqrt 5)/2 = 1.618$, the golden mean.

I can't see how I supposed to deduce this...I tried getting a few values for $$\frac{|t-x_{k+1}|}{|t-x_k|^{1.68}}$$ ... and this seems to go to $0$ and then the precision becomes too small for the computer to handle. I don't really know what I am doing here trying to deduce that the convergence is 1.6.18. Can anyone explain how I am supposed to be making this deduction?

EDIT: If I check $\phi=(1 + \sqrt 5)/2\approx1.618$, $|t-x_{k+1}|/|t-x_k|^\phi$ up to iteration 9 I get

 3 | 5.094e-002
4 | 1.127e+000
5 | 3.564e-001
6 | 7.569e-001
7 | 4.802e-001
8 | 6.331e-001
9 | 5.330e-001


Can this be taken that the sequence is converging to a fixed number $u$?

-

The exponent $1.68$ is due to a typo. As you almost correctly stated, the order (not rate) of convergence $q$ is determined by

$$\lim_{k \rightarrow \infty} \frac{\epsilon_{k+1}}{\epsilon_k^q} = u$$

for some non-zero $u$. (If $u$ could be zero, the condition would be fulfilled for all $q$ less than or equal to the order of convergence.)

So by definition the order of convergence is $\phi=(1 + \sqrt 5)/2\approx1.618$ if $|t-x_{k+1}|/|t-x_k|^\phi$, not $|t-x_{k+1}|/|t-x_k|^{1.68}$, converges to a non-zero constant, which indeed it appears to do.

Note that errors near $10^{-16}$ mainly reflect rounding errors of double-precision numbers, so you should stop at step $9$ and compare steps $8$ and $9$.

-
Ok cheers. I have edited in the values for the proper ratio into my original post. Would you say that sequence is converging given those values? –  Jim_CS Sep 30 '12 at 20:13
@Jim_CS: Formally, you can't tell from any finite number of terms whether a sequence converges, so the term "deduced" in the question is slightly misplaced. Heuristically, I'd say it looks pretty good, especially considering how much worse it looks for the nearby guess $1.68$. –  joriki Sep 30 '12 at 21:18

You can actually comment on the convergence. One key thing you missed here is regarding the constant u. abs(u) [the absolute value of u] should always be less than 1 to conclude convergence . This ensures that the magnitude of e(n+1) is always less than e(n) for all values of 'n' > c, where 'c' is a fixed number depending on the function.

If you tried with q=1; you would have observed that the magnitude of the error ratio is always less than 1. Implies q=1 could be the rate of convergence as it qualifies the condition on 'u'[Check this out]. Trying with q = 1.68, I see iteration 4 throwing a value of 1.27, which means 1.68 is not the rate of convergence. It also concludes that the rate would lie between [1 to 1.68].

Error ratio :|t−x'k+1|/|t−x'k|^q

-