Introduction to Numerical Methods/Ordinary Differential Equations

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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| edit source]

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| edit source]

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| edit source]

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| edit source]

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| edit source]

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| edit source]

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| edit source]

source

solution in a iPython notebook