Finding error of secant method empirically

[jjr]

Homework Statement

I need to find the roots of a given equation using the secant method and matlab. I have already found all the roots, but I am also asked to find the rate of convergence for the method empirically, meaning that they want me to find the order of convergence through the set of errors generated in by the program.

Homework Equations

The Attempt at a Solution

I know very well that the order of convergence of the secant method is α ≈ 1.618, but I am not sure how I should go about showing this empirically. In my case the roots are found within the desired error tolerance (1e-10) in about 6-8 iterations. I've tried taking the logarithms of the errors and plotting them versus the iteration number n, to draw out the exponential behaviour, but I can't get anyone clear answer... Any suggestions for putting me on the right track? Let me know if I need to clarify anything.

J

 

[BvU]

Check out these notes which Anatolii Grinshpan put on the net.

 

[jjr]

Thank you! I'm still not sure how I would go about finding the exponent given a set of errors, but I think it will be sufficent to show that \frac{|x_{n+1}-α|}{|x_n-α|^p} ≈ C , making p ≈ 1.618 a starting assumption.

 

[BvU]

I think so. What I wanted to point out is that the analysis is based on ignoring higher order terms, and even then you need $f''$ and $f'$ in $\alpha$. Depending on your test functions (and on whether you have an exact solution for $\alpha$ or only the last iteration) you end up in the noise very quickly. So with only a few iterations and any deviation popping up twice (in point n and also in point n+1), you can't expect a perfectly smooth log-log plot.

so there's no need to be so precise about the 1.61803398874989...

Conceptually I always remembered this as: Newton is quadratic, secant approaches Newton if the secant approaches the derivative. But it's a numerical derivative, so before it's really good enough you are in the noise anyway. So somewhere between 1 and 2.