Next: The MidPoint Method
Up: Pushing Particles
Previous: Solving the HamiltonJacobi Equation
Since Newton equations can be reduced either directly
or through the Lagrangian or Hamiltonian routes to systems
of first order ordinary differential equations, once we
know how to solve the latter numerically, we'll have a handle
on Newton equations themselves.
So let us consider then the following simple ODE:

(4.66) 
The Euler method of solving this equation is very simple.
Replace
d x(t)/d t with a finite difference:

(4.67) 
This is, actually, one possible choice,
that will lead to an explicit integration
scheme. The other choice is:

(4.68) 
This choice leads to an implicit integration scheme.
Let us focus on the explicit scheme first. Equation
(4.71) suggests the following integration scheme:

(4.69) 
or, in other words, once we have assumed a certain initial
condition for x, say,
x_{0} = x(t_{0}) then:
Observe that this scheme is intrinsically sequential. It cannot
be parallelised, unless you are solving a very large system of
coupled ODEs, in which case, the whole system of equations can
be solved in parallel. This is generally true of any ODE problem,
and any ODE numerical method. They cannot be parallelised by themselves.
Parallelism is possible for large systems of ODEs only.
The Euler scheme may become unstable. To see that consider
two possible solutions x_{n} and x'_{n} at t_{n} that are very close, so
that
,
where
is a very small
number. In order to assess the stability of the method we need
to consider the evolution of
with time.
Plugging
into the Euler scheme yields:

(4.70) 
Since x_{n+1} and x_{n} are already linked by the Euler
relationship, we get

(4.71) 
Now, let us assume that
,
where
g is a growth factor. Plugging this into
equation (4.75) yields:

(4.72) 
For the scheme to be numerically stable we must have
that
,
hence the condition:

(4.73) 
This means that if, for example,
is positive then
Euler method is bound to be unstable, whatever the choice of
.
If however
is negative,
then by choosing
an appropriately small
we can stabilise the
computation.
The simplest example of a negative
is when it is
a negative constant, e.g.,

(4.74) 
where k > 0,
or, in other words,

(4.75) 
Assume that C=0, then the exact solution is
x(t) = x_{0} e^{kt}

(4.76) 
The stability criterion implies that
.
Euler method is not only unstable in great many circumstances.
It is not very accurate
either. This can be ascertained easily by comparing
the exact solution of
for which a stable numerical Euler scheme is possible,
with a numerical approximation. Starting from x_{0} numerically
we are going to get:
The exact solution is:
Hence the error is:
or of order
.
Such methods are said to be firstorder accurate.
The reason for this lack of accuracy is that
as the formula advances the solution through the
interval
the derivative
information that pertains to the interval is sampled
only at the beginning of the interval.
Next: The MidPoint Method
Up: Pushing Particles
Previous: Solving the HamiltonJacobi Equation
Zdzislaw Meglicki
20010226