Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to see how the error propagates on a mapping that I have. I have proven that $$|f(x+\varepsilon)-f(x)|=\varepsilon(1+\varepsilon),$$ let $\varepsilon_n$ be the error after $n$ applications of the mapping, it holds $\varepsilon_{n+1}=\varepsilon_n(1+\varepsilon_n)$. It is easy to show $\varepsilon_n$ obeys $$\frac{\varepsilon_n}{\varepsilon_0}=\sum_{k=0}^{2^n} p_k(n) \varepsilon_0^k$$ with $p_k(n)$ polynomials. I have convinced myself that $p_k(n)$ is of degree $k$ and the coefficient of the highest order term is 1, which by the way is exactly what I need. However I cannot find how to prove it. I even have difficulties setting up an induction.

So, first of all, is this by any chance a known map? Can I find any results anywhere? Also any idea on how to prove this is more than welcome.

EDIT: Motivation

The motivation comes from trying to approximate the separatrices of a map. So I have a map $f:\mathbb{C}^2\to\mathbb{C}^2$ and let $w(s)$ be a separatrix parametrised by $s\in\mathbb{C}$ for which it holds $f(w(s))=w(s+1)$.

The problem is that I know $w(s)$ as an approximation by a formal series $w_N(s)=\sum_{i=1}^N w_i s^{-i}$ I also know that the error is of the order of $s^{-N}$.

I try to prove that $$\lim_{n\to\infty}f^n(w_N(s-n))=w(s)$$ this is possible because the error is not constant with $n$, for big $n$ the error is of the order $n^{-N}$ and if the error propagates as expected, then it goes to zero as $n$ goes to infinity.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

Let $$\frac{\varepsilon_n}{\varepsilon_0}=\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k$$ where $f(k, n)$ is your $p_k(n)$.

Note that \begin{align} \sum_{k=0}^{\infty} f(k, n+1) \varepsilon_0^k=\frac{\varepsilon_{n+1}}{\varepsilon_0}& =\frac{\varepsilon_n(1+\varepsilon_n)}{\varepsilon_0} \\ &=\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)\left(1+\varepsilon_0\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right) \\ & =\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)+\varepsilon_0\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)^2 \\ &=\left(\sum_{k=0}^{\infty} f(k, n) \varepsilon_0^k\right)+\left(\sum_{k=0}^{\infty} \left(\sum_{j=0}^{k-1} f(j, n)f(k-1-j, n)\right)\varepsilon_0^k\right) \end{align}

Thus $$f(k, n+1)=f(k, n)+\left(\sum_{j=0}^{k-1} f(j, n)f(k-1-j, n)\right)$$

Note: This equation holds $\forall n,k \in \mathbb{Z}, n, k \geq 0$. In the following proof by strong induction, there is no restriction on $n$. Any equation with $n$ is assumed to hold for all non-negative integers $n$.

We now prove by strong induction on $k$ that $f(k, n)$ is a polynomial in $n$ of degree $k$ with leading coefficient $1$.

The above equation implies $f(0, n+1)=f(0, n)$ (the 2nd term with the sum is empty), so by induction $f(0, n)=1 \, \forall n \in \mathbb{Z}, n \geq 0$.

Suppose that the statement holds for $0 \leq k \leq l$. Then by the induction hypothesis, $f(i, n)f(l-i, n)$ is a polynomial in $n$ with degree $l$ and leading coefficient $1 \, \forall i$, so $f(l+1, n+1)-f(l+1, n)=\left(\sum\limits_{i=0}^{l} f(i, n)f(l-i, n)\right)$ is a polynomial in $n$ with degree $l$ and leading coefficient $(l+1)$. Thus there exists $a_0, a_1, \ldots , a_{l-1}$ such that $$f(l+1, n+1)-f(l+1, n)=(l+1)!\binom{n}{l}+\sum_{i=0}^{l-1}{a_i\binom{n}{i}}$$

Note: To see why this is true, note that both $f(l+1, n+1)-f(l+1, n)$ and $(l+1)!\binom{n}{l}$ are polynomials in $n$ with degree $l$ and leading coefficient $l+1$, so their difference is a polynomial in $n$ with degree $\leq (l-1)$. Any polynomial $P(n)$ can be written as a linear combination of binomial coefficients $\binom{n}{i}$, where $0 \leq i \leq deg(P(n))$, so in particular the above equation holds for some $a_i$.

Thus \begin{align} f(l+1, n)& =f(l+1, 0)+\sum_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))} \\ &=\sum_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))} \\ & =\sum_{j=0}^{n-1}{\left((l+1)!\binom{j}{l}+\sum_{i=0}^{l-1}{a_i\binom{j}{i}}\right)} \\ & =(l+1)!\binom{n}{l+1}+\sum_{i=0}^{l-1}{a_i\binom{n}{i+1}} \end{align}

Note:$f(l+1, 0)=0$ since $l+1 \geq 1$ and $1=\frac{\varepsilon_0}{\varepsilon_0}=\sum_{k=0}^{\infty} f(k, 0) \varepsilon_0^k$.

This is indeed a polynomial in $n$ of degree $l+1$ and leading coefficient $1$.

We are thus done by strong induction.

share|improve this answer
    
I am a bit lost at the line $$f(l+1, n+1)-f(l+1, n)=(l+1)!\binom{n}{l}+\sum_{i=0}^{l-1}{a_i\binom{n}{i}}$$ how did $(l+1)!\binom{n}{l}$ appear? And maybe a silly question but how do we know that such $a_i$'s exist? –  tst Feb 13 '13 at 17:50
    
Both $f(l+1, n+1)-f(l+1, n)$ and $(l+1)!\binom{n}{l}$ are polynomials with degree $l$ and leading coefficient $l+1$. Thus their difference is a polynomial with degree $\leq (l-1)$. Now every polynomial of degree $d$ can be written as a linear combination of binomial coefficients $\binom{n}{i}$, where $0 \leq i \leq d$ e.g. $n^3=6\binom{n}{3}+6\binom{n}{2}+\binom{n}{1}$. Thus we can write $f(l+1, n+1)-f(l+1, n)-(l+1)!\binom{n}{l}$ as $\sum\limits_{i=0}^{l-1}{a_i\binom{n}{i}}$ for some $a_i$. –  Ivan Loh Feb 14 '13 at 0:13
    
Oh! ok, I can see that is a polynomial of degree $l$ and leading coefficient $l+1$ so we have $(l+1)(l!\binom{n}{l})=(l+1)!\binom{n}{l}$. My other problem is that I cannot see how the following equation appears $$f(l+1, n)=\sum_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))}$$ Also does your proof hold when $n>l$ or is it more general? –  tst Feb 14 '13 at 2:23
    
I think I skipped a step there. Note: $f(l+1, n)=f(l+1, 0)+(f(l+1, 1)-f(l+1, 0))+(f(l+1, 2)-f(l+1, 1))+ \ldots + f(l+1, n)-f(l+1, n-1))=f(l+1, 0)+\sum\limits_{j=0}^{n-1}{(f(l+1, j+1)-f(l+1, j))}$ Now $f(l+1, 0)=0$ so you get that equation. –  Ivan Loh Feb 14 '13 at 2:47
    
There is no restriction on $n$. The equation $$f(k, n+1)=f(k, n)+\left(\sum_{j=0}^{k-1} f(j, n)f(k-1-j, n)\right)$$ holds for all $n, k$. I will edit my answer to make it clearer. –  Ivan Loh Feb 14 '13 at 2:54
show 2 more comments

Sorry, but $\epsilon_{n + 1} = \epsilon_n (1 + \epsilon_n)$ diverges (if $\epsilon_n > 0$ then $1 + \epsilon_n > 1$, and $\epsilon_{n + 1} > \epsilon_n$).

share|improve this answer
    
Well yes, but I don't see how this is relevant to the question. –  tst Feb 13 '13 at 22:26
    
It makes the question moot? If the error tends to $\infty$, there is no point in the approximation scheme. –  vonbrand Feb 13 '13 at 22:43
    
No, check the question, I updated it. –  tst Feb 13 '13 at 22:57
add comment

Your Answer

 
discard

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.