Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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
@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

share|cite|improve this answer

Your Answer


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.