Relation between two different definitions of quadratic convergence

169 Views Asked by At

I'm trying to prove quadratic convergence of the multivariate Newton-Raphson method, and I've proved that for some constant $C>0$, we have $\lVert x_{k+1}-a \rVert \leq C \cdot \lVert x_k - a \rVert^2$ for all $k \in \mathbb{N}$.

Some authors write that this is exactly quadratic convergence of $x_k$ towards $a$. However, reading the English Wikipedia, quadratic convergence is defined to be convergence of the sequence $\frac{\lVert x_{k+1}-a\rVert}{\lVert x_k -a\rVert^2}$ towards some number $\mu > 0$. See https://en.wikipedia.org/wiki/Rate_of_convergence#Basic_definition

Of course, my statement ensures that the sequence $\frac{\lVert x_{k+1}-a\rVert}{\lVert x_k -a\rVert^2}$ is bounded, but I fail to prove quadratic convergence as defined on Wikipedia.

My question is, are these two definitions of quadratic convergence the same? And if they are, how does the first imply the latter?

Thanks in advance for any help.

1

There are 1 best solutions below

0
On BEST ANSWER

Thanks to the comments on the question, here is an answer on my question.

The two definitions are not equivalent.

As a counter example, consider the recursively defined sequence: $x_0 = 1/2$, and for $k > 0$, $$ x_{k+1} = \begin{cases} 2x_k^2 & k \equiv 0 \pmod{2} \\ x_k^2 & k \equiv 1 \pmod{2} \\ \end{cases} $$

Then $x_1= 1/2$, $x_2 = 1/4$, $x_3=1/8$, $x_4 = 1/64$, etc., thus it is clear that $x_k \rightarrow 0$ as $k \rightarrow \infty$.

Thus $\lvert x_{k+1} \rvert \leq 2 \lvert x_k \rvert^2$. Also, $$ \frac{\lvert x_{k+1} \rvert}{\lvert x_k \rvert^2} = \begin{cases} 2 & k \equiv 0 \pmod{2} \\ 1 & k \equiv 1 \pmod{2} \\ \end{cases} $$

So $\frac{\lvert x_{k+1} \rvert}{\lvert x_k \rvert^2}$ is bounded but not convergent.

As pointed out, $\limsup\limits_{k \rightarrow \infty}\frac{\lvert x_{k+1} \rvert}{\lvert x_k \rvert^2}$ exists, (and is $2$).