Talk:Rate of convergence

From Wikipedia, the free encyclopedia

I think that for linear convergence we need \mu = \lim \epsilon_{k+1} / \epsilon_k to be strictly smaller than one. Indeed, the sublinearly convergent seguence εk = logk has μ = 1. -- Jitse Niesen 18:00, 27 Dec 2004 (UTC)

--

In the book
Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0534382169
they just say μ > 0 for linear convergence.
I agree with you, intuitively εk = logk converges sublinearly. On the other hand, the sequence εk = 1 / k converges linearly, but with μ = 1. Same for εk = 1 / kp for p > 1. There are other strange sequences. For example, \epsilon_k=\frac{1}{2^{k^2}} does not converge with rate faster than linear (that is with q > 1), however if we say it converges linearly, one gets μ = 0.
So, the rate of convergence is not a perfect indicator of how fast a sequence converges. Probably ultimately it is a matter of convention. Do you have any references where μ < 1 for linear convergence? --Oleg Alexandrov 19:12, 27 Dec 2004 (UTC).

I am abroad, so I cannot check any references at the moment (I'll probably be back in the second week of January), but I probably got it either from the Gautschi book mentioned in the article, or from Süli and Mayers' An Introduction to Numerical Analysis.

According to the definition currently in the article, the sequence eps_k = 1/k does NOT converge linearly and eps_k = 1/2^(k^2) converges sublinearly, but not with order > 1. This is the correct definition in the framework of root-finding algorithms (unless I'm wildly wrong): the error of the bisection method is 1/2^k, which converges linearly, and the error of Newton's method is something like 1/2^(2^k), which converges quadratically.

I think you meant eps_k = 1/2^(k^2) converges superlinearly. You are right about the errors of the bisection method and Newton's method. We need to get the defintion of rate of convergence right, but ultimately, we discuss technicalities, the point of all numerical textbooks is that quadratic convergence is what we want, everything else is not important. Oleg Alexandrov 20:37, 27 Dec 2004 (UTC)

I now realize that there is another definition in numerical ordinary differential equations: a method has order q if the error is like 1/N^q where N = number of variables. A method with error 1/2^N (like the spectral method) would be called exponentially convergent in this context. This can be confusing, and so it should be explained better in the article.

I hope introducing an alternate defintion will not make things more confusing. Oleg Alexandrov 20:37, 27 Dec 2004 (UTC)

By the way, how do you like the book by Burden and Faires? I have never read it, but I saw it references in several Wikipedia articles, so perhaps I should give it a try. However, I still think we need μ < 1 because every convergent sequence satisfies the condition with μ = 1. -- Jitse Niesen 20:05, 27 Dec 2004 (UTC)

This is my wife's favorite numerical analysis book (that should matter a lot! :), it is also the standard textbook at UCLA, where I teach. Recently I was contacted to review a textbook in numerical analysis, and the editors wanted to know how their book compares to Burden and Faires. I would say it is a very nice book, with lots of problems, and good explanations. I think I put that book as references in the several places you saw it. Oleg Alexandrov 20:37, 27 Dec 2004 (UTC)
PS Burden and Faires is also very expensive ($140.95 list price in the US), it is also 7th edition. This probably says that the book is in demand.


Contents

[edit] Burden and Faires definition again

That book, unfortunately not only forgets that one must have μ<1, they actually have exercises where they ask to prove x_n=1/n converges linearly . So I think that book is overall confused on that topic. Oleg Alexandrov 20:36, 16 Jan 2005 (UTC)

Cheers, I didn't notice that, so it is a deliberate choice of Burden and Faires. All other books require μ < 1 though, so I'm keeping that definition. It's a pity, since the Burden and Faires book seems pretty nice overall, and apparently also used as a textbook at my university. -- Jitse Niesen 11:55, 17 Jan 2005 (UTC)
I think the point of Burden and Faires is that they are really after quadratic convergence. Therefore, anything slower than that they think is all and the same damn slow linear convergence. :) Oleg Alexandrov 16:11, 17 Jan 2005 (UTC)

[edit] Further tweaks to extended definition

In reference to my simultaneous edit to the article: The new formulation with "converges with at least order q" was taken from the Suli and Mayers book. The previous formulation ("the order of convergence is the largest q") has the disadvantage that it is not obvious that such a q exists. Feel free to revert as it is a bit nit-picking. (PS: Removing Burden and Faires from the references was the right solution) -- Jitse Niesen 12:21, 20 Jan 2005 (UTC)

I like your change. Cheers, Oleg Alexandrov | talk 05:41, 21 Jan 2005 (UTC)

[edit] Problem with the convergence examples

I'm fairly sure that sequence d doesn't converge at all... so can we use it as an example of sublinear convergence? -- EPAstor, 22:39 April 10, 2005 (UTC)

I don't understand. Are you refering to the sequence
1, \frac12, \frac13, \frac14, \frac15, \ldots?
This sequence certainly converges to zero (for every positive ε, one can find an N such that |dn| < ε for n ≥ N). Or perhaps you mean that the series
1 + \frac12 + \frac13 + \frac14 + \frac15 + \cdots
does not converge? That is true, but it is not what the article says. -- Jitse Niesen 12:25, 11 Apr 2005 (UTC)

[edit] Question regarding extended definition

In the basic definition, it seems that what one is really after is not the lim, but the lim sup. I think that this would actually be equivalent to the extended definition. Does that make any sense? --128.100.151.121 22:58, 11 February 2006 (UTC)

Yes, using "lim sup" instead of "lim" would make the basic definition equivalent to the extended definition. But I find it simpler that way, without lim sum. No? Oleg Alexandrov (talk) 00:25, 12 February 2006 (UTC)

[edit] Swapping Pages

Hello everyone, first of all, I don't understand why the order of converging page was directing everyone to the rate of convergence page. They are clearly two different things. They both measure how fast a sequence converges but they are two different way of measuring convergence. Order of convergence is how fast the terms of a sequence get smaller compared to its previous terms. Rate of convergence measures how fast a sequence/function converges compared to a known sequence/function. In addition, this page previously held information about order of convergence as opposed to rate of convergence. So I created the Order of convergence page and swapped both pages with each other because the info on the page titled rate of convergence was actually about the order of convergence. It took me a while to figure out the confusion as well. It is not easy. I have also added a few more examples. In case you are wondering, I used the Burden & Faires 8th edition. I understand from previous discussions on the rate of convergence page that some of you are already familiar with this book. The two definitions are entirely different with the rate of convergence being defined on page 35 and order of convergence being defined on page 75.
A Real Kaiser 06:38, 28 October 2007 (UTC)

I am familiar with the Burden & Faires book. I think it is rather non-standard in how it defines things. I undid your edits and I made order of convergence redirect here. Oleg Alexandrov (talk) 15:29, 4 April 2008 (UTC)