*I believe in the fundamental Truth of all the great religions of the world. I believe that they are all God given. I came to the conclusion long ago… that all religions were true and also that all had some error in them.*(Mahatma Gandhi)*The fairest thing we can experience is the mysterious. It is the fundamental emotion which stands at the cradle of true art and true science. He who know it not and can no longer wonder, no longer feel amazement, is as good as dead, a snuffed-out can.*(Einstein)*Most of the fundamental ideas of science are essentially simple, and may, as a rule, be expressed in a language comprehensible to everyone.*(Einstein)

# Time Stepping

The Fundamental Theorem concerns time-stepping of the basic IVP (initial value problem):

- ,

where the Lipschitz continuous function does not depend on the unknown , only on the (independent) time variable t, and is a given initial value.

We now extend to allow the function to depend also on . Assuming for simplicity no explicit dependence on t, we thus consider the IVP:

- ,

where is a given Lipschitz continuous function of with Lipschitz constant .

The basic question is if the solution can be computed to arbitrary precision by time-stepping ?

The basic case is and , that is the IVP:

- ,

with and solution denoted by referred to as the *exponential function* being computed by Forward Euler:

- ,
- ,
- ,

with time step .

We estimate the effect of dividing the time-step by a factor 2, using that (because ):

- .

We see that the difference is proportional to the time step . As in the proof of the Fundamental Theorem of Calculus, we conclude that determines with a precision proportional to the time step with a multiplicative factor .

# Time Stepping with General f(u)

The above proof extends to an arbitrary Lipschitz continuous function with the difference that the time-stepping error in computing , now is proportional to the time step with a multiplicative factor , where is the Lipschitz constant of . This extends to systems with with d>1.

It is natural to refer to this result as a *Generalized Fundamental Theorem*: The Fundamental Theorem concerns and the Generalized Fundamental Theorem concerns . Calculus in a nutshell!

# The Two Parts of the Proof

A proof of the Generalized Fundamental Theorem can be performed by combining the following two parts:

**Part 1: **Estimate the difference by taking one (Forward Euler) time step of length (here ) and two time steps of length , from the same initial value :

- .

Illustration of Part 1 in the proof of the Generalized Fundamental Theorem

**Part 2**: Estimate the difference after one time step from different initial conditions :

- .

Illustration of Part 2 of the proof of the Generalized Fundamental Theorem.

Combining (see hint below) Part 1 and Part 2, we obtain a final error proportional to the time step with a multiplicative factor , which we refer to as a *stability factor.*

To see the connection with the basic case , think of estimating a general function , assuming for simplicity, by , which suggests that the factor for should be replaced by for a general (because ).

Generalization to a vector valued function with is direct, and we have thus presented the essentials of a proof (with a hint to completion below) of the following main result of Calculus:

**Generalized Fundamental Theorem of Calculus**: The solution u(t) of the IVP for with u(0) given, where is Lipschitz continuous with Lipschitz constant , is uniquely computable by Forward Euler time stepping with a precision proportional to the time step times a stability factor of size exp(LT).

The proof is similar for the alternative methods (with $u^n=u(nk)$):

- Forward Euler
- Backward Euler
- Midpoint Euler
- Trapezoidal Method.

Note that if is linear in , then Midpoint Euler and the Trapezoidal Method coincide.

# A Posteriori Error Control

For a more precise error control, based on computed solutions, see

- MST Chap 82: Time Stepping Error Analysis,
- MST Chap 161: Time Stepping by FEM.

# The Illusion of an Exponential Bound

If and , which looks pretty harmeless, then = *googol*, an incredibly large number, much larger than the number of atoms in the Universe.

A matching time step of is beyond all rationale and thus computation of a solution of an IVP with moderate Lipschitz constant over a moderatley long time interval may be impossible. An example is the Lorenz system with

- ,

for which computation on an interval of length requires computation with about digits, see:

- MST Chap 256: The Lorenz System and the Essence of Chaos
- Long-Time Computability of the Lorenz System

# Stiff IVPs

There is a class of IVPs with large or very large Lipschitz constants, which are computable on long time intervals, because the function has a decay property (negative derivative) causing errors to decay rather than grow exponentially. Such problems are called *stiff problems* and may require implicit time stepping to avoid severe time step restrcitions in explicit methods. See \hyperref[sectionstiffproblems]{Stiff Problems}.

# Wave Equations

IVPs with wavelike solutions, like the system

with solutions being linear combinations of and , have formally Lipschitz constants of size 1, can be integrated with error growth , instead of by the above (crude) estimate, if a proper time-stepping method like Trapezoidal method is used. This is due to error cancellation in wave motion.

For more complex wave problems, or problems with more or less periodic solutions, the stability factorcan have a polynomial growth in time , e.g. quadratic for simple planetary systems.

# Summary: Time Stepping of IVP

The precision in time stepping the solution of an IVP for $0<t\le T$, with a first order method such as Forward/Backward Euler with time step , can be estimated by , where acts as *stability factor measuring error propagation and accumulation* of size

- (general), where is the Lipschitz constant of $f$,
- (stiff: diffusion problems)
- (wave problems), (planetary system).

# Preparing for a More Precise Analysis

As a preparation for the more precise error analysis in

- MST Chap 82: Time Stepping Error Analysis,
- MST Chap 161: Time Stepping by FEM,

we consider two solutions and computed with the same time step but different initial data and . Subtracting the update formulas we have formally for the difference :

showng that an initial error is propagated as a solution to a linearized IVP with coefficient depending on a computed solution . We shall see that by solving the linearized problem (or rather a closely related dual linearized problem), the stability factors measuring error growth can be computed and the precision on the computation of can be assessed.

The linearized problem (or its dual) thus gives the key to unlock time stepping precision.

Note that with , the linearized problem reads with solution , showing exponential error growth, as expected.

# Completion of the Proof

To complete the proof of the Generalized Fundmental Theorem we are to sum up the error contributions from each subinterval of length , which according to Part 1 and Part 2 amounts to

- ,

where and $M\ge\max_{u}\vert f(u)\vert$. Can you explain what is going on here? If not, take a look at:

# Hint to Completion of the Proof

We can think of comparing computations with and with corresponding solutions and in two ways depending on how we choose initial values on each time interval :

- Compute and independently with timestep and .
- Assume that at the beginning of time step and account for the effect at final time of the difference at the end of time step .

1. is the most direct from computational point of view and a corresponding proof is given in \hyperref[chaptergenivp]{General Case}.

Here we consider 2. because the proof is (maybe) simpler: The error from the first time step is bounded by assuming no error in initial data, and is propagated with a factor bounded by for each time step, thus with a factor after steps. Similarly, the error from the second time step is bounded by , again assuming no error in the corresponding initial value, and is propagated with a factor , et cet. Summing we obtain a bound of the total error after steps.

# Uniqueness of Solution

To prove that the solution of the with is unique, we assume is a possibly different solution also satisfying for and . Subtraction gives for the difference

and thus taking the scalar product with and using Cauchy’s inequality, we get

and thus for

- ,

which shows that (why?)

- .

But and thus and for and uniqueness follows. But to be scientifically honest, size of the exponential factor is crucial. If and , which does not look too frightening, then googol, which means that the argument the is small (zero) if is small (zero), is questionable, very questionable, right?

# How to Prove that exp(t+s)=exp(t)exp(s)?

To prove the basic law of the exponential , note that the function satisfies for and . But the function also satisfies for and and by uniqueness , that is .

Model of a virus as a large molecular dynamics system of differential equations .}

Next: The World as IVP Previous: Contraction Mapping Theorem