Generalized Fundamental Theorem
- 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
,
where the Lipschitz continuous function does not depend on the unknown
, only on the (independent) time variable
.
We now extend to allow to depend also on
. Assuming for simplicity no explicit dependenceon
, we thus consider the IVP:
,
where is a given Lipschitz continuous function 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
.
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
and two time steps on 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 of the IVP
for
with
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
.
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
Leave a Reply