1
$\begingroup$

The definition of convergence for root finding algorithms is given in a few sources as: A sequence ${x^k}$ generated by a numerical method is said to converge to the root $\alpha$ with order $p\geq 1$ if:

$\exists C > 0 : \frac{|x^{(k+1)} - \alpha |}{|x^{k} - \alpha|^p}\leq C \qquad \forall k \geq k_0$

Where the order is $\exists C$ s.t. $\forall k$ instead of $\forall C$, $\exists k$ as you would have for a regular sequence. Why the change and how does it even make sense? Surely all you're determining is that the method is bounded?

A method that was just oscillating within bounds such as $x_k = (-1)^k$ would be considered convergent by the above definition despite clearly not being so what gives?

I don't know if I've misunderstood something or it's just taken as read that an algorithm would be created sensibly so as to not exhibit behaviour like this but I just don't understand why the statement is like this when the normal sequence definition would surely work perfectly well here too.

Hope that makes sense, thanks in advance for any help.

$\endgroup$
5
  • $\begingroup$ Is there a condition such as $C < 1$? If so, with $p=1$ to simplify, $\forall k \geq 0, |x^k - \alpha| \leq C^k |x^0 - \alpha|$ for a sequence converging by that definition (up to the initial $k_0$). This sequence converges by the usual definition. More generally, $\forall k, |x^k - \alpha| \leq C^{p^{k-1}} |x^0 - \alpha|^{p^k}$. This also converges if $C<1$ with asymptotic slope $\log(p)$ in $\log\log$. $\endgroup$
    – Sardine
    May 18, 2023 at 16:13
  • $\begingroup$ Surely in that case I could just set $x_k = m(-1)^k$ where $m<1$ and the condition would still be satisfied without convergence though? $\endgroup$ May 18, 2023 at 16:44
  • 1
    $\begingroup$ You could, but that sequence would not converge in the sense of the definition you gave ! Surely you agree that, if $C < 1$, then $C^k |x^0 - \alpha|$ converges to $0$? $\endgroup$
    – Sardine
    May 18, 2023 at 23:29
  • $\begingroup$ If $p>1$, then $C>1$ is totally fine. $\endgroup$ May 19, 2023 at 0:00
  • $\begingroup$ Actually, I made a mistake in deriving the general case, what we have is: $|x^k-\alpha| \leq C^{\sum_{j=0}^{k-1}p^j} |x^0-\alpha|^{p^k} = C^{\frac{1-p^k}{1-p}} |x^0-\alpha|^{p ^k}$. Whether it converges or not depends on $C|x^0 - \alpha|^{p-1}$, as the bound can then be rewritten as $C|x^k - \alpha|^{p-1} \leq \left(C|x^0-\alpha|^{p-1} \right)^{p^k}$ Thus the general condition is $C|x^0 - \alpha|^{p-1} < 1$. Optimization is not my field, but I suspect this is linked to the famous "provided $x^0$ sufficiently close to $\alpha$" of Newton's & co. $\endgroup$
    – Sardine
    May 19, 2023 at 13:40

2 Answers 2

5
$\begingroup$

This is not the definition of convergence. It is the definition of the convergence rate -- that is, how fast the sequence converges to a limit.

In other words, the definition you quote can only be meaningfully applied to sequences that are already known to converge.

$\endgroup$
0
3
$\begingroup$

I can't give a very informed answer on this topic, but I can help sort out whether such a sequence converges.

Let's denote $\epsilon_k = |x^k - \alpha|$ the error for simplicity. If $p=1$, we have

$\epsilon_k \leq C \epsilon_{k-1} \leq C^2 \epsilon_{k-2} ... \leq C^{k} \epsilon_0$

This is a sequence that converges if $C < 1$. Now for the more general case, assume $p > 1$:

$\epsilon_k \leq C \epsilon_{k-1}^p \leq C C^p \epsilon_{k-2}^{p^2} ... \leq C^{\sum_{j=0}^{k-1} p^j} \epsilon_0^{p^k}$

We can rework that expression a bit. First, $\sum_{j=0}^{k-1} p^j = \frac{1-p^k}{1-p}$. Then, as $p-1 > 0$, we can compose by $\cdot^{p-1}$ without affecting the order,

$\epsilon_k^{p-1} \leq C^{p^k-1} (\epsilon_0^{p-1})^{p^k}$

I intentionally left the last term this way, as it is now readily apparent that

$C\epsilon_k^{p-1} \leq (C\epsilon_0^{p-1})^{p^k}$

Thus this sequence converges if $C\epsilon_0^{p-1} < 1$.

This condition means that, for any constant $C$, there exists $x^0$ sufficiently close from $\alpha$ such that the sequence is going to converge. This is generally summarized in e.g. Newton's method by the statement "converges provided $x^0$ close enough to a root". Newton's quadratic convergence is a particular case of this general definition, with $p=2$.

When the constant is greater than one, you may observe oscillations as you proposed, or even divergence. This is possible behaviour of Newton's method (and other root finding algorithms) when the initial guess is far from a solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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