3
$\begingroup$

I have been trying to prove this theorem which I think is wrong. Theorem: Assume that $$f(h)=p(h)+O(h^n),g(h)=q(h)+O(h^m)$$and $$r=min\{m,n| m,n \in \mathbb{Z}_+\}$$ then $$f(h)+g(h)=p(h)+q(h)+O(h^r)$$ My views are,if we suppose that WLOG $$m\leq n$$ then $$h^m=O(h^n)$$ therefore $$O(h^m)+O(h^n)=O(h^n)$$ contrary to the proposition. So my question; am I right?if not where am I going wrong and how can I then prove the theorem above?

$\endgroup$
1
$\begingroup$

In principle you are right. But there is one detail missing: $$h→0 \qquad \text{or}\qquad h→∞?$$

Depending on that, your assumption is either true or false.

  • $h→0$: It holds $h^m=\mathcal{O}(h^n)$ for $m≥n$.
  • $h→∞$: It holds $h^m=\mathcal{O}(h^n)$ for $m≤n$.

And the proof of this is straight forward:

$$\frac{h^m}{h^n}=h^{m-n}→ … \tag{*}$$

The limit now depends on $m-n≥0$ or $m-n≤0$, and on $h→0/∞$.
If $(*)$ tends to a value $a<∞$, then it holds $h^m=\mathcal{O}(h^n)$.

Edit: The reason why I mention this is, that in numerics usually $h$ stands for a small value. Examples are the size of a grid cell in FEM/FDM, or the step-size in numerical methods for ODEs, or a small increment in a difference quotient.

$\endgroup$
  • $\begingroup$ I get it now in this case I was wrong as $h\rightarrow 0$ $\endgroup$ – Tom Carter Oct 16 '17 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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