MHB How Does the Order of Convergence Relate to Numerical Schemes for ODEs?

[MarkFL]

A while back, I dug out a topic I worked on many years ago after taking a course in ordinary differential equations and I was left with an unanswered question, which I thought I would post here. While my question arose from studying numeric methods for approximating the solutions to ODEs, I feel it is probably more of a question in numeric analysis.

I was analyzing the correlation between the approximation methods for definite integrals and for first order initial value problems via the anti-derivative form of the Fundamental Theorem of Calculus. In an attempt to determine the rate of convergence for the various methods, I have observed what I believe to be a pattern, but had difficulty in proving a hypothesis.

I began by using the IVP:

$\displaystyle \frac{dy}{dx}=y$ where $y(0)=1$

and used the explicit numerical schemes to approximate y(1) which led to approximations for $e$.

Analysis of Euler's method (Riemann sum of regular partitions) gave rise to

$\displaystyle e=\lim_{n\to\infty}\left(1+\frac{1}{n} \right)^n$

Use of a limit comparison test shows this scheme to be of order 1.

Analysis of the improved Euler's method (trapezoidal scheme) and the 2nd order Runge-Kutta method (mid-point scheme) which both use Euler's method as a predictor-corrector, show that both give rise to:

$\displaystyle e=\lim_{n\to\infty}\left(1+\frac{1}{n}+\frac{1}{2n^2} \right)^n$

Use of a limit comparison test shows this scheme to be of order 2.

Analysis of the 4th order Runge-Kutta method (Simpson's or prismoidal scheme) gave rise to:

$\displaystyle e=\lim_{n\to\infty}\left(1+\frac{1}{n}+\frac{1}{2n^2}+\frac{1}{6n^3}+\frac{1}{24n^4} \right)^n$

Use of a limit comparison test shows this scheme to be of order 4.

My hypothesis is that an explicit numerical scheme that yields

(1) $\displaystyle e=\lim_{n\to\infty}\left(\sum_{i=0}^{p}\left(\frac{1}{i!n^{i}} \right) \right)^n$

will be of order $p$.

Interestingly, two of the implicit methods yield the formula

$\displaystyle e=\lim_{n\to\infty}\left(\frac{2n+1}{2n-1} \right)^n$

but I did not explore its rate of convergence or what type of formula an implicit method of order $p$ will yield.

While it was a simple enough matter to show that (1) is valid and that as p increases the rate of convergence improves, demonstrating that this rate of convergence increases linearly as $p$ is another matter entirely. I applied L'Hôpital's rule and Maclaurin expansions for logarithmic functions, but to no avail. I also looked into the use of a Taylor formula of order $p$ because of its relationship to the limit comparison test and its use in the derivation of the Runge-Kutta methods and the Maclaurin power series.

If anyone could shed some light on this or post links to relevant material, I would greatly appreciate it!

 

[I like Serena]

Just to verify, I created an Excel sheet with these sequences.
A log-log-plot of n versus the error in the approximation from e, shows the rate of convergence.
And indeed for each approximation sequence we get a line with a slope that corresponds to the order of convergence.
It turns out that a sequence with powers up to 6, has a 6th order of convergence.

The quotient form $(\dfrac {2n+1}{2n-1})^2$ turns out to have convergence order 2.
It is also the only one that approaches e from above instead of from below.

 

[MarkFL]

I appreciate you taking the time to verify the rate of convergence up to $p=6$. (Yes)

 

[I like Serena]

Here's an observation.
Suppose we let p go to infinity, then we get for n=1:

$\qquad (\displaystyle\sum_{p=0}^\infty \dfrac{1}{p! n^p})^n = (1 + \frac 1 {2!} + \frac 1 {3!} + ...)^1 = e$

Hey! We know this sequence!
It is the Taylor expansion of $e^x$ for $x=1$.

And for higher values of n, we simply get $(e^{1/n})^n = e$.
So in the ultimate case we get a constant sequence of just e.