Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a theorem to prove for numerical mathematics regarding a fixed-point iteration (henceforth FPI).

Problem statement:
Given $p\geq 2$ and $\Phi \in C^{p} [a,b]$ for some $a,b\in\mathbb{R}$ is a FPI-Function ($x^{(\nu+1)}=\Phi(x^{(\nu)})$). Let $\tilde{x}\in(a,b)$ be a fixed point for the FPI s.t. $\Phi^{(j)}(\tilde{x})=0\quad j=1,...,p-1$ but $\Phi^{(p)}(\tilde{x})\neq 0$. We have to show that the order of convergence of the FPI is not greater than $p$.
Relevant definition (order of convergence):
A FPI is said to converge in Order $\alpha$ if $\exists C\in\mathbb{R} >0$ s.t. for all $k\in\mathbb{N}$ holds: $|x^{(k+1)}-\tilde{x}| \leq C |x^{(k)}-\tilde{x}|^\alpha$
Own solution:
The proof of convergence of order at least $p$ is done by taylor expansion of $\Phi$ around $\tilde{x}$ with lagrange remainder $\frac{\Phi^{(p)}(\xi(x, \tilde{x}))}{p!}(x-\tilde{x})^p$ then setting $x=x^{(k)}$ and then taking either the supremum/maximum of $\Phi^{(p)}$ over $[x_k,\tilde{x}]$ or taking limit $k\rightarrow\infty$.
Now to prove that the order is not higher than $p$ I assume it is (proof by contradiction), that is $\exists C>0$ s.t. the definition holds with $\alpha=p+1$.
Then I use the Taylor expansion from the first part of the proof to get: $|\frac{\Phi^{(p)}(\xi(x^{(k)}, \tilde{x}))}{p!}||x^{(k)}-\tilde{x}|^p \leq C |x^{(k)}-\tilde{x}|^{p+1}$ (where inequality holds by assumption)
Seeing as the differences are positive and nonzero I can get rid of $|x^{(k)}-\tilde{x}|^p$ on both sides.

Now taking the limit $\lim_{k\rightarrow\infty}$ on both sides of the inequality I obtain: $0\neq |\Phi^{(p)}(\tilde{x})/p!| = \lim_{k\rightarrow\infty} |\Phi^{(p)}(\xi(x^{(k)},\tilde{x}))/p!| \leq C \lim_{k\rightarrow\infty} | x^{(k)} -\tilde{x}| = 0$
which is a contradiction - as desired. Therefore QED.

My problem is that I am not sure whether this last part is sound.

Intuitively I'd say yes, because $\xi \in [x^{(k)},\tilde{x}]$ and therefore tends to $\tilde{x}$ if k tends to infinity (contraction of interval to a point). But experience has shown that what is intuitively clear to me mostly needs to be proven.

Therefore the question: Is the proof above valid or am I missing something fundamental (any other misses or things to be more precise about are welcome, too).

Thanks in advance

share|cite|improve this question
up vote 0 down vote accepted

Yes, as $x^{(k)} \to x$ then $\xi^{(k)} := \xi(x^{(k)}, \tilde{x}) \to \tilde{x}$ by your argument. Then, since $\Phi^{(p)}$ is continuous (by assumption), it follows that $\Phi^{(p)}(\xi^{(k)}) \to \Phi^{(p)}(\tilde{x})$, as $k \to \infty$.

The next inequality feels better if you write $\ldots \leq C \liminf_{k \to \infty} |x^{(k)} - \tilde{x}|$, because when you estimate from above inside the limit, it may be by something that does not converge; but in your case it does, of course.

I hope I have understood and answered your question well.

share|cite|improve this answer
Thanks for the feedback! I like math, but am not confident at proofs therefore the question. Let's see if this holds up in the exercises. – Nox Jan 14 '14 at 0:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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