We study the dependence of the time step dt in time-stepping dx = f(t)*dt by Forward Euler to compute the integral or primitive function x(t) of a given function f(t):
- x(t+dt) = x(t) + f(t)*dt.
We compare taking one step with time step dt to compute x(t+dt), with two steps of time step dt/2 to compute x2(t+dt) from the same given value at t:
- x(t+dt) – x2(t+dt) = f(t)*dt – (f(t)+f(t+dt/2)*dt/2
- = (f(t)-f(t+dt/2))*dt/2,
Assuming that f(t) is Lipschitz continuous with Lipschitz constant L, we then find that
- | x(t+dt) – x2(t+dt) | ≤ L*dt*dt/4.
as illustrated in the following picture with t = n*dt after taking n time steps:
Summing the contributions from N time steps up to a final time T=N*dt starting from 0, we get
- | x(T)-x2(T) | ≤ N*L*dt*dt/4 = L*T*dt/4,
where thus x(T) is computed with time step dt and x2(T) with time step dt/2.
Repeating the argument with successively refined times step dt/4, dt/8,…, we get
- | x(T)-x2(T) | ≤ L*T*dt/2
for the difference between x(T) computed with time step dt and x2(T) now computed with vanishingly small time step, since
- 1/4 +1/8 +1/16 … < 1/2.
We have now proved the Fundamental Theorem of Calculus:
Theorem Forward Euler time-stepping of dx = f(t)*dt computes the integral or primitive function x(t) of a given function f(t) with Lipschitz constant L over a time interval of length T with time step dt, with accuracy bounded by L*T*dt/2.
This result captures the essence of the Calculus of Leibniz (and Newton). You see that the proof is short and not difficult to understand. If you put this into your mathematics tool box you have come a long way. So do it!
Residual: Connection to FEM
As a serious student, you now probably ask: In precisely what sense is the differential equation Dx(t) = f(t) with D = d/dt is satisfied by an Euler Forward solution x(t) with time step dt? It certainly is so constructed, but can we get a direct verification? One way to do this is to associate a continuous piecewise linear function determined by the values x(n*k) at the discrete time levels n*k, again denoted by x(t). We then have on each interval (n*k,(n+1)*k), by the definition of x(t):
from which we conclude that
We can thus say that x(t) satisfies the differential equation Du(t)=f(t)$ for all t with a precision of . In other words, the residual is smaller than .
We shall see below that extending a function defined on a discrete set of points to a continuous piecewise linear function, is a central aspect of approximation in general and of the Finite Element Method FEM in particular.
- Estimate the accuracy of Backward Euler and Midpoint Euler.
- The quadrature of all figures follow from the inverse method of tangents, and thus the whole science of sums and quadratures can be reduced to analysis, a thing nobody even had any hopes of before. (Leibniz)
- Knowing thus the Algorithm of this calculus, which I call Differential Calculus, all differential equations can be solved by a common method. (Leibniz)
In other words, understanding the integral of a function , means to understand that:
- is determined by Riemann sums with vanishingly small step size, as the solution to the IVP , ,
- the difference between two Riemann sums with mesh size and , is bounded by (or more precisely by ).