Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.