Finding the order of the rate of convergence

[relinquished™]

Hello,

Our class was tasked to develop programs for the Fixed Point Method, Newton-Rhapson Method, and the Secant Method, then create a subroutine that could compute the order of the rate of convergence for all the iterative methods. I DO know the orders of rate of convergence of each method, it's just that I can't demonstrate it in Scilab, the program we use in our class (although I also tried to demonstrate it in Matlab)

The Order can be derived from the formula

$e_{n+1} = C |e_{n}|^q$

hence,

$q= {{\ln(e_{n+1}) - \ln(C) }\over \ln(e_n)}$

What I've done so far is create 2 vectors containing iterates. One vector X contains the 1st, 2nd, ... nth iterate, while the other Y contains the 2nd, 3rd, ..., (n+1)th iterate. I then create a new vector E=Y-X which contains the errors in-between successive iterates. This is the part where I'm stuck - I have no clue as to how to compute for the asymptotic error constant (which is the only unknown I need to find q). I'm not even sure if the mathematical framework is correct... is there anything wrong with it?

All help is appreciated

reli~

 

[0rthodontist]

So, basically, you have a recurrence and you want to compute the exponent q from the recurrence.

C should matter less and less as n grows, so you could just set it to be 1 and ignore it. Alternatively, in addition to
$$e_{n+1} = C |e_{n}|^q$$
you know
$$e_{n} = C |e_{n-1}|^q$$
So dividing the first by the second, you know
$$\frac {e_{n+1}}{e_n} = |\frac{e_n}{e_{n-1}}|^q$$

$$q = \frac{ln (\frac {e_{n+1}}{e_n})}{ln |\frac{e_n}{e_{n-1}}|}$$

 

[relinquished™]

Thanx so much Orthodonist, your suggestion has helped me very well. However, there's a problem about the rate of convergence that comes out when I test the Secant Method. The Secant Method should give an approximate order of 1.618, but it gives me 1! But anyway, thanks for the help. I will see where I went wrong on my own.

Thanx again

reli~

 

[HallsofIvy]

Are you expected to use a formula? Since you are talking about programs to do this, it seems to me that a straight forward way to do this would be to take a problem with a known answer, approximate the solution by each method using a specific number of steps, and then divide the error (|known answer- approximate solution) by the number of steps.

 

[relinquished™]

HallsofIvy:

That's the kind of program I've done so far. I'm finding the roots of

$$x^2 - 5x - 6$$

Of course I know the roots (x=-1, x=6) I've already developed the codes for Newton, Secant and Fixed Point Method. I do know that the order of the rate of convergence, q, for each method is q=2, q= the golden ratio (1.618 blah blah) , and q=1, respectively. As of now, the suggestion made by Orthodonist produces the correct values of q for the Newton and Fixed point, but not for the Secant Method.Sorry for being so clueless, but what does dividing the error by the number of steps produce? Does it result in the asymptotic error constant? I know that the asymptotic error constant is given by

$$\lim_{n \rightarrow \infty} \frac{ e_{n+1}}{e^{q}_{n} } = C$$
All help is appreciated

reli~

 

[HallsofIvy]

HallsofIvy:

That's the kind of program I've done so far. I'm finding the roots of

$$x^2 - 5x - 6$$

Of course I know the roots (x=-1, x=6) I've already developed the codes for Newton, Secant and Fixed Point Method. I do know that the order of the rate of convergence, q, for each method is q=2, q= the golden ratio (1.618 blah blah) , and q=1, respectively. As of now, the suggestion made by Orthodonist produces the correct values of q for the Newton and Fixed point, but not for the Secant Method.


Sorry for being so clueless, but what does dividing the error by the number of steps produce? Does it result in the asymptotic error constant?

No, it results in the rate of convergence which is what you wanted. How fast does the sequence converge to the correct answer? How many steps does it take to get close to the correct answer?

I know that the asymptotic error constant is given by

$$\lim_{n \rightarrow \infty} \frac{ e_{n+1}}{e^{q}_{n} } = C$$



All help is appreciated

reli~

 

[relinquished™]

No, it results in the rate of convergence which is what you wanted. How fast does the sequence converge to the correct answer? How many steps does it take to get close to the correct answer?

I see... that clears things up a bit... so what can you say about Orthodonist's suggestion on getting the order of the rate of convergence (which I know is q in the formula you quoted)? I mean, in the alternative he gave me, he told me to ignore the value of C, but I know that q could be solved by using

$q= {{\ln(e_{n+1}) - \ln(C) }\over \ln(e_n)}$

I'm sorry if I sound to persistent, it's just that the algorithm I made still gives me an incorrect order q for the Secant method...

Thanks a billion times,

reli~