Order of a numerical iteration method

51 Views Asked by At

Suppose that we have the definition of order $p$ of a numerical method as in the first snippet below. Now I want to prove that for a one-point iterative method this order $p$ is a positive integer. To that end, Ralston in the theorem $8.1$ takes a Taylor expansion as in the next snippet below. But there I got stuck: in formula $(8.4-4)$ in the r.h.s. he says $$\lim_{i\to\infty} \dfrac{\left|x_{i+1}-\alpha\right|}{\left|x_i-\alpha\right|^{p}}=\frac{1}{p!}F^{(p)}(\alpha)\neq 0.$$ Now why this equality after $\lim$ holds with $F^{(p)}(\alpha)$ is evaluated at $\alpha$ while $(8.4-3)$ is evaulated at $\xi$ ?

Last but not least if $$F^{(j)}(\alpha)\neq 0$$ for some $j=1,\ldots,p-1$ then $F(x)$ cannot be of order $p$. Why this is so, what is intuition for this ?

enter image description here

enter image description here

1

There are 1 best solutions below

7
On BEST ANSWER

Ralston assumes that $F$ has "sufficiently many derivatives" and so is probably also assuming that $F^{(p)}$ is continuous. Since $\xi$ lies between $x_i$ and $\alpha$, and $x_i \to \alpha$, then that necessarily implies that $\xi \to \alpha$ and so $F^{(p)}(\xi)\to F^{(p)}(\alpha)$ as $i\to\infty$.

To answer your second question, suppose that $F^{(j)}(\alpha) \neq 0$ for some $j < p$. Then, assuming the rest of the derivatives of $F$ of order less than $j$ are zero, we find via a Taylor expansion up to order $j$ that $$F(x_i) = x_{i+1} = \alpha + \frac{1}{j!}F^{(j)}(\xi)(x-\alpha)^{j}$$ where $\xi$ lies in the interval between $x_i$ and $\alpha$. Therefore, we have $$\frac{|x_{i+1}-\alpha|}{|x_{i}-\alpha|^j} = \frac{1}{j!}F^{(j)}(\xi). $$ Taking the limit as $i\to \infty$ then yields $$\lim_{i\to\infty} \frac{|x_{i+1}-\alpha|}{|x_{i}-\alpha|^j} = \frac{1}{j!}F^{(j)}(\alpha)$$ indicating that the order of convergence is at most $j$. Since $j<p$, we cannot have $p^{\text{th}}$ order convergence.