Convergence of numeric schemes

[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.

 

[blue_raver22]

I find your observations and hypothesis about the convergence of numerical schemes for approximating ODE solutions to be very interesting. It seems like you have put a lot of thought and effort into analyzing these methods and trying to understand their convergence rates.

One suggestion I have is to look into the concept of "order of convergence" in numerical analysis. This refers to the rate at which the error in a numerical method decreases as the step size (or number of subintervals) decreases. It is usually denoted by the letter "p" and can be determined by analyzing the error term in the method's formula.

In your case, it seems like you have already observed a pattern where the order of convergence increases as the number of terms in the formula increases. This is consistent with the idea that more terms in the formula can lead to a more accurate approximation. However, it is important to note that the order of convergence may also depend on other factors such as the smoothness of the function being approximated.

I would suggest looking into the error analysis of the methods you have studied and comparing them to see if they align with your observations. This may also help you to understand why the implicit methods yield a different formula for $e$ and what their order of convergence is.

Overall, your question and observations are a great example of the intersection between numerical analysis and differential equations. I hope you continue to explore this topic and make new discoveries. Good luck!