7
$\begingroup$

I'm a bit confused about the concepts of convergence rate and convergence order. Let me first give you the definitions we use: [sorry for the English, it's all self translated]

Let $x^{*}$ be our solution.

Definition 1: The sequence $x^{(k)}$ is called linearly converging towards $x^{*}$, if $$\exists L<1 \text{ so that } \|x^{(k+1)}-x^{*}\|\leq L\| x^{(k)}-x^{*}\|,\quad \forall k\geq k_0.$$

We call the constant $L$ rate of convergence.

Definition 2: The order of convergence of a numerical method is $p$, if: $$\exists C > 0 \text{ so that }\|x^{(k+1)}-x^{*}\|\leq C\| x^{(k)}-x^{*}\|^p,\quad \forall k\in \mathbb N \quad\text{with $C<1$ for $p=1$}.$$

Note: We assumed, that chose the starting value so that we get an converging sequence.

Questions:

Question 1: Can someone explain me the difference between $C$ and $L$ here?

Question 2: Can someone explain me the concept/idea behind the rate/order of convergence? [Just so I heard it from another perspective]

Question 3: Also, I often see that we use linglog and loglog plots, but I don't really get why we do that. E.g., if we have linear convergence, we can see a linear function if we lin-log plot our errors. (Why do we need the lin-log plot here)

$\endgroup$
8
$\begingroup$

$\|x^{(k)}-x^*\|$ is the error in the $k$th term, call it $E_k$. For a "good" numerical method, we want the approximation to get closer and closer to the desired result so $E_k$ has to decrease to zero. If the error is guaranteed to reduce to at least a certain fraction $L$ of the previous step, you have linear convergence: $$E_{k+1} \le L E_k.$$ This essentially guarantees that the error drops at least as fast as a geometric series. An example would be the sequence $0.9, 0.99, 0.999 \ldots$ which converges to 1. The error at the $k$th step is $10^{-k}$ so that $L=0.1$.

But the error could fall faster than linear. Consider the sequence $$0.9, 0.99, 0.9999, 0.99999999\ldots$$ This converges to 1 too, but at each step the error reduces as the square of the previous step so that $p=2$. When you have a faster than linear convergence order ($p>1$), you are not really worried about $C$: it could even be greater than 1. But when $p=1$, $C$ becomes the same as $L$ and you want it to be less than 1.

Now why the log-linear plot? Assuming linear convergence with geometrically reducing error, we would have $$E_k = L^{-k} E_0$$ replacing $\le$ with equality. Taking the log of this, $$\log(E_k) = \log(E_0) - k \log(L)$$ which is a linear curve.

$\endgroup$
  • $\begingroup$ By mentoining the geometrical series, you just made it clear to me, that we are basically using the ratio test known from calculus, thus the $L< 1$. I think I never really saw that. But anyway, the important part of your answer is the end. It's clear, that it can converge faster than linearily. So, basically, if $p=1$ we are intretested in $L$ but if $p\neq 1$ we are interested in $L$. Also, if we have two methods with the same $p$ we can further compare it using $C$, right? The smaller $C$ the better, right? $\endgroup$ – xotix Jan 31 '17 at 18:17
  • $\begingroup$ But isn't there a case where $p>1$ and $C>>L$, so that a method with $p=1$ still converges better? The important thing for me to get is: The $C$ in Definition 2 is still the rate of convergence, right? It's just not very informative for $p>1$, right? $\endgroup$ – xotix Jan 31 '17 at 18:17
  • $\begingroup$ No, p>1 always wins out eventually. Yes, C is some kind of rate of convergence for p>1 too but not very useful. $\endgroup$ – Raziman T V Jan 31 '17 at 18:20
  • $\begingroup$ okay, good. Thanks, I think that makes it clear. $\endgroup$ – xotix Jan 31 '17 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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