Introduction to Numerical Methods/Ordinary Differential Equations

Resources:

A differential equation is a equation that relates some function with its derivatives. Such relationship is commonly found in dynamic system modeling where the rate of change of a quantity is affect by another quantity, which can be a function of other quantities. Therefore differential equations are often used to mathematically represent such relations in many disciplines including engineering, physics, economics, and biology. We will focus on ordinary differential equations, which involves no partial derivative.

The solution to a differential equation is the function or a set of functions that satisfies the equation. Some simple differential equations with explicit formulas are solvable analytically, but we can always use numerical methods to estimate the answer using computers to a certain degree of accuracy.

http://martinfowler.com/bliki/TwoHardThings.html "Two hard things in computer science: cache invalidation, naming things, and off-by-one errors."

Initial Value Problem edit

The general form of first order differential equation:   or  . The solution contains an arbitrary constant (the constant of integration) because   satisfies all differential equations   satisfies. With an auxiliary condition, e.g. y(a)=b, we can solve y'=F(x, y). This is known as the initial value problem.

An indefinite integral of a function   is a class of functions   so that  . The indefinite integral is also known as the antiderivative. The definite integral of a function over a fixed interval is a number.

Connection with Integration edit

To calculate the integral   is to find a   that satisfies the condition  ,  . In other words, integration can be used to solve differential equations with a initial condition.

Euler's Method edit

 
Illustration of the Euler method. The unknown curve is in blue, and its polygonal approximation is in red.

Euler's method uses a step-wise approach to solve ordinary differential equations with an initial condition.

Given   and   (  is an independent variable and   is a dependent variable) Euler's methods solves for   for  .

Euler's method can be derived in a number of ways. Lets look at a geographical description.

Given that   at a particular point   we can approximate   with  . The derivative represents the instantaneous (happening continuously) change in   at  :

 

The average change in   over   is

 ,

which represents a discrete version of the change (changes over "steps" of time). If the change in   is small enough, either of the two can be used to approximate the other.

Assume that we know the derivative function of an unknown curve and wants to find the shape of the curve (a function that satisfies a differential equation). We can start from a known point, use the differential equation as as a formula to get the slope of the tangent line to the curve at any point on the curve, and take a small step along that tangent line up to the next point. If the step is small enough, we can expect the next point to be close to the curve. If we pretend that point is still on the curve, the same process can be used to find the next point and so on. Graphically we are using a polynomial to approximate the unknown curve. The gap between the two curves represents the error of the approximation, which can be reduced by shortening the step sizes.

We just derived the formula for Euler's method:

 

Example edit

Given  , and  , solve it for   at 1, i.e. y(1).

The Euler's method formula is a recursively defined function, which can be calculated iteratively.   is called the step size. If we pick a step size of 1 the solution is as follows:

 
Illustration of numerical integration for the equation   Blue is the Euler method; green, the midpoint method; red, the exact solution,   The step size is h = 1.0.
       
0 0 1 1
1 1 2 2
2 2 4 4
3 3 8 8

Another way to derive Euler's method is to use taylor expansion around  :

 

If we ignore higher order derivative terms we get the Euler's method formula:

 

Runge-Kutta 2nd Order Method edit

One of the Runge-Kutta 2nd order method is the midpoint method, which is a modified Euler's method (one-step method) for numerically solving ordinary differential equations:

 .

The midpoint method is given by the formula

 .

Note that   is the approximation of   using this method.

 
Illustration of the midpoint method assuming that   equals the exact value   The midpoint method computes   so that the red chord is approximately parallel to the tangent line at the midpoint (the green line).

Runga-Kutta 4th Order Method edit

The Runga-Kutta 4th order method is often called "RK4", "classical Runge–Kutta method" or simply as "the Runge–Kutta method".

 

for i = 0, 1, 2, 3, . . . , using

 

This method calculate   by adding to  ) a weighted average of four increments, each of which is the step size   multiplied by an estimated slope:

  •   is the increment based on the estimated slope at the beginning of the interval (Euler's method) ;
  •   is the increment based on the slope at the midpoint of the interval;
  •   is again the increment based on the slope at the midpoint, but now using  ;
  •   is the increment based on the slope at the end of the interval, using  .

In averaging the four increments, greater weight is given to the increments at the midpoint. The weights are chosen such that if   is independent of  , so that the differential equation is equivalent to a simple integral.

Case Study edit

source

solution in a iPython notebook