# Numerical Differential Equation Analysis Package

The Numerical Differential Equation Analysis package combines functionality for analyzing differential equations using Butcher trees, Gaussian quadrature, and Newton-Cotes quadrature.

### Butcher

Runge-Kutta methods are useful for numerically solving certain types of ordinary differential equations. Deriving high-order Runge-Kutta methods is no easy task, however. There are several reasons for this. The first difficulty is in finding the so-called order conditions. These are nonlinear equations in the coefficients for the method that must be satisfied to make the error in the method of order O (hn) for some integer n where h is the step size. The second difficulty is in solving these equations. Besides being nonlinear, there is generally no unique solution, and many heuristics and simplifying assumptions are usually made. Finally, there is the problem of combinatorial explosion. For a twelfth-order method there are 7813 order conditions!

Don’t waste time! Our writers will create an original "Numerical Differential Equation Analysis Package" essay for you

This package performs the first task: finding the order conditions that must be satisfied. The result is expressed in terms of unknown coefficients aij, bj, and ci. The s-stage Runge-Kutta method to advance from x to x+h is then

where

Sums of the elements in the rows of the matrix [aij] occur repeatedly in the conditions imposed on aij and bj. In recognition of this and as a notational convenience it is usual to introduce the coefficients ci and the definition

This definition is referred to as the row-sum condition and is the first in a sequence of row-simplifying conditions.

If aij=0 for all i≤j the method is explicit; that is, each of the Yi (x+h) is defined in terms of previously computed values. If the matrix [aij] is not strictly lower triangular, the method is implicit and requires the solution of a (generally nonlinear) system of equations for each timestep. A diagonally implicit method has aij=0 for all i<j.

There are several ways to express the order conditions. If the number of stages s is specified as a positive integer, the order conditions are expressed in terms of sums of explicit terms. If the number of stages is specified as a symbol, the order conditions will involve symbolic sums. If the number of stages is not specified at all, the order conditions will be expressed in stage-independent tensor notation. In addition to the matrix a and the vectors b and c, this notation involves the vector e, which is composed of all ones. This notation has two distinct advantages: it is independent of the number of stages s and it is independent of the particular Runge-Kutta method.

For further details of the theory see the references.

 ai,j the coefficient of f(Yj(x)) in the formula for Yi(x) of the method bj the coefficient of f(Yj(x)) in the formula for Y(x) of the method ci a notational convenience for aij e a notational convenience for the vector (1, 1, 1, …)

Notation used by functions for Butcher.

 RungeKuttaOrderConditions[p,s] give a list of the order conditions that any s-stage Runge-Kutta method of order p must satisfy ButcherPrincipalError[p,s] give a list of the order p+1 terms appearing in the Taylor series expansion of the error for an order-p, s-stage Runge-Kutta method RungeKuttaOrderConditions[p], ButcherPrincipalError[p] give the result in stage-independent tensor notation

Functions associated with the order conditions of Runge-Kutta methods.

 ButcherRowSum specify whether the row-sum conditions for the ci should be explicitly included in the list of order conditions ButcherSimplify specify whether to apply Butcher’s row and column simplifying assumptions

Some options for RungeKuttaOrderConditions.

This gives the number of order conditions for each order up through order 10. Notice the combinatorial explosion.

 In:=
 Out=

This gives the order conditions that must be satisfied by any first-order, 3-stage Runge-Kutta method, explicitly including the row-sum conditions.

 In:=
 Out=

These are the order conditions that must be satisfied by any second-order, 3-stage Runge-Kutta method. Here the row-sum conditions are not included.

 In:=
 Out=

It should be noted that the sums involved on the left-hand sides of the order conditions will be left in symbolic form and not expanded if the number of stages is left as a symbolic argument. This will greatly simplify the results for high-order, many-stage methods. An even more compact form results if you do not specify the number of stages at all and the answer is given in tensor form.

These are the order conditions that must be satisfied by any second-order, s-stage method.

 In:=
 Out=

Replacing s by 3 gives the same result asRungeKuttaOrderConditions.

 In:=
 Out=

These are the order conditions that must be satisfied by any second-order method. This uses tensor notation. The vector e is a vector of ones whose length is the number of stages.

 In:=
 Out=

The tensor notation can likewise be expanded to give the conditions in full.

 In:=
 Out=

These are the principal error coefficients for any third-order method.

 In:=
 Out=

This is a bound on the local error of any third-order method in the limit as h approaches 0, normalized to eliminate the effects of the ODE.

 In:=
 Out=

Here are the order conditions that must be satisfied by any fourth-order, 1-stage Runge-Kutta method. Note that there is no possible way for these order conditions to be satisfied; there need to be more stages (the second argument must be larger) for there to be sufficiently many unknowns to satisfy all of the conditions.

 In:=
 Out=
 RungeKuttaMethod specify the type of Runge-Kutta method for which order conditions are being sought Explicit a setting for the option RungeKuttaMethod specifying that the order conditions are to be for an explicit Runge-Kutta method DiagonallyImplicit a setting for the option RungeKuttaMethod specifying that the order conditions are to be for a diagonally implicit Runge-Kutta method Implicit a setting for the option RungeKuttaMethod specifying that the order conditions are to be for an implicit Runge-Kutta method \$RungeKuttaMethod a global variable whose value can be set to Explicit, DiagonallyImplicit, or Implicit

Controlling the type of Runge-Kutta method in RungeKuttaOrderConditions and related functions.

RungeKuttaOrderConditions and certain related functions have the option RungeKuttaMethod with default setting \$RungeKuttaMethod. Normally you will want to determine the Runge-Kutta method being considered by setting \$RungeKuttaMethod to one of Implicit, DiagonallyImplicit, and Explicit, but you can specify an option setting or even change the default for an individual function.

These are the order conditions that must be satisfied by any second-order, 3-stage diagonally implicit Runge-Kutta method.

 In:=
 Out=

An alternative (but less efficient) way to get a diagonally implicit method is to force a to be lower triangular by replacing upper-triangular elements with 0.

 In:=
 Out=

These are the order conditions that must be satisfied by any third-order, 2-stage explicit Runge-Kutta method. The contradiction in the order conditions indicates that no such method is possible, a result which holds for any explicit Runge-Kutta method when the number of stages is less than the order.

 In:=
 Out=
 ButcherColumnConditions[p,s] give the column simplifying conditions up to and including order p for s stages ButcherRowConditions[p,s] give the row simplifying conditions up to and including order p for s stages ButcherQuadratureConditions[p,s] give the quadrature conditions up to and including order p for s stages ButcherColumnConditions[p], ButcherRowConditions[p], etc. give the result in stage-independent tensor notation

More functions associated with the order conditions of Runge-Kutta methods.

Butcher showed that the number and complexity of the order conditions can be reduced considerably at high orders by the adoption of so-called simplifying assumptions. For example, this reduction can be accomplished by adopting sufficient row and column simplifying assumptions and quadrature-type order conditions. The option ButcherSimplify in RungeKuttaOrderConditions can be used to determine these automatically.

These are the column simplifying conditions up to order 4.

 In:=
 Out=

These are the row simplifying conditions up to order 4.

 In:=
 Out=

These are the quadrature conditions up to order 4.

 In:=
 Out=

Trees are fundamental objects in Butcher’s formalism. They yield both the derivative in a power series expansion of a Runge-Kutta method and the related order constraint on the coefficients. This package provides a number of functions related to Butcher trees.

 f the elementary symbol used in the representation of Butcher trees ButcherTrees[p] give a list, partitioned by order, of the trees for any Runge-Kutta method of order p ButcherTreeSimplify[p, , ] give the set of trees through order p that are not reduced by Butcher’s simplifying assumptions, assuming that the quadrature conditions through order p, the row simplifying conditions through order , and the column simplifying conditions through order all hold. The result is grouped by order, starting with the first nonvanishing trees ButcherTreeCount[p] give a list of the number of trees through order p ButcherTreeQ[tree] give True if the tree or list of trees tree is valid functional syntax, and False otherwise

Constructing and enumerating Butcher trees.

This gives the trees that are needed for any third-order method. The trees are represented in a functional form in terms of the elementary symbol f.

 In:=
 Out=

This tests the validity of the syntax of two trees. Butcher trees must be constructed using multiplication, exponentiation or application of the function f.

 In:=
 Out=

This evaluates the number of trees at each order through order 10. The result is equivalent to Out but the calculation is much more efficient since it does not actually involve constructing order conditions or trees.

 In:=
 Out=

The previous result can be used to calculate the total number of trees required at each order through order10.

 In:=
 Out=

The number of constraints for a method using row and column simplifying assumptions depends upon the number of stages. ButcherTreeSimplify gives the Butcher trees that are not reduced assuming that these assumptions hold.

This gives the additional trees that are necessary for a fourth-order method assuming that the quadrature conditions through order 4 and the row and column simplifying assumptions of order 1 hold. The result is a single tree of order 4 (which corresponds to a single fourth-order condition).

 In:=
 Out=

It is often useful to be able to visualize a tree or forest of trees graphically. For example, depicting trees yields insight, which can in turn be used to aid in the construction of Runge-Kutta methods.

 ButcherPlot[tree] give a plot of the tree tree ButcherPlot[{tree1,tree2,…}] give an array of plots of the trees in the forest {tree1, tree2,…}

Drawing Butcher trees.

 ButcherPlotColumns specify the number of columns in the GraphicsGrid plot of a list of trees ButcherPlotLabel specify a list of plot labels to be used to label the nodes of the plot ButcherPlotNodeSize specify a scaling factor for the nodes of the trees in the plot ButcherPlotRootSize specify a scaling factor for the highlighting of the root of each tree in the plot; a zero value does not highlight roots

Options to ButcherPlot.

This plots and labels the trees through order 4.

 In:=
 Out=

In addition to generating and drawing Butcher trees, many functions are provided for measuring and manipulating them. For a complete description of the importance of these functions, see Butcher.

 ButcherHeight[tree] give the height of the tree tree ButcherWidth[tree] give the width of the tree tree ButcherOrder[tree] give the order, or number of vertices, of the tree tree ButcherAlpha[tree] give the number of ways of labeling the vertices of the tree tree with a totally ordered set of labels such that if (m, n) is an edge, then m

Other functions associated with Butcher trees.

This gives the order of the tree f[f[f[f] f^2]].

 In:=
 Out=

This gives the density of the tree f[f[f[f] f^2]].

 In:=
 Out=

This gives the elementary weight function imposed by f[f[f[f] f^2]] for an s-stage method.

 In:=
 Out=

The subscript notation is a formatting device and the subscripts are really just the indexed variable NumericalDifferentialEquationAnalysis`Private`\$i.

 In:=
 Out//FullForm=

It is also possible to obtain solutions to the order conditions using Solve and related functions. Many issues related to the construction Runge-Kutta methods using this package can be found in Sofroniou. The article also contains details concerning algorithms used in Butcher.m and discusses applications.

As one of its methods, the Mathematica function NIntegrate uses a fairly sophisticated Gauss-Kronrod-based algorithm. The Gaussian quadrature functionality provided in Numerical Differential Equation Analysis allows you to easily study some of the theory behind ordinary Gaussian quadrature which is a little less sophisticated.

The basic idea behind Gaussian quadrature is to approximate the value if an integral as a linear combination of values of the integrand evaluated at specific points:

Since there are 2n free parameters to be chosen (both the abscissas xi and the weights wi) and since both integration and the sum are linear operations, you can expect to be able to make the formula correct for all polynomials of degree less than about 2n. In addition to knowing what the optimal abscissas and weights are, it is often desirable to know how large the error in the approximation will be. This package allows you to answer both of these questions.

 GaussianQuadratureWeights[n,a,b] give a list of the pairs (xi, wi) to machine precision for quadrature on the interval a to b GaussianQuadratureError[n,f,a,b] give the error to machine precision GaussianQuadratureWeights[n,a,b,prec] give a list of the pairs (xi, wi) to precision prec GaussianQuadratureError[n,f,a,b,prec] give the error to precision prec

This gives the abscissas and weights for the five-point Gaussian quadrature formula on the interval (-3, 7).

 In:=
 Out=

Here is the error in that formula. Unfortunately it involves the tenth derivative of f at an unknown point so you don’t really know what the error itself is.

 In:=
 Out=

You can see that the error decreases rapidly with the length of the interval.

 In:=
 Out=

Newton-Cotes

As one of its methods, the Mathematica function NIntegrate uses a fairly sophisticated Gauss-Kronrod based algorithm. Other types of quadrature formulas exist, each with their own advantages. For example, Gaussian quadrature uses values of the integrand at oddly spaced abscissas. If you want to integrate a function presented in tabular form at equally spaced abscissas, it won’t work very well. An alternative is to use Newton-Cotes quadrature.

The basic idea behind Newton-Cotes quadrature is to approximate the value of an integral as a linear combination of values of the integrand evaluated at equally spaced points:

In addition, there is the question of whether or not to include the end points in the sum. If they are included, the quadrature formula is referred to as a closed formula. If not, it is an open formula. If the formula is open there is some ambiguity as to where the first abscissa is to be placed. The open formulas given in this package have the first abscissa one half step from the lower end point.

Since there are n free parameters to be chosen (the weights) and since both integration and the sum are linear operations, you can expect to be able to make the formula correct for all polynomials of degree less than about n. In addition to knowing what the weights are, it is often desirable to know how large the error in the approximation will be. This package allows you to answer both of these questions.

 NewtonCotesWeights[n,a,b] give a list of the n pairs (xi, wi) for quadrature on the interval a to b NewtonCotesError[n,f,a,b] give the error in the formula

 option name default value QuadratureType Closed the type of quadrature, Open or Closed

Option for NewtonCotesWeights and NewtonCotesError.

Here are the abscissas and weights for the five-point closed Newton-Cotes quadrature formula on the interval (-3, 7).

 In:=
 Out=

Here is the error in that formula. Unfortunately it involves the sixth derivative of f at an unknown point so you don’t really know what the error itself is.

 In:=
 Out=

You can see that the error decreases rapidly with the length of the interval.

 In:=
 Out=

This gives the abscissas and weights for the five-point open Newton-Cotes quadrature formula on the interval (-3, 7).

 In:=
 Out=

Here is the error in that formula.

 In:=
 Out=

### Runge-Kutta Methods

In numerical analysis, the Runge-Kutta methods (German pronunciation:[ˌʀʊŋəˈkʊta]) are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations. These techniques were developed around 1900 by the German mathematicians C. Runge and M.W. Kutta.

See the article on numerical ordinary differential equations for more background and other methods. See also List of Runge-Kutta methods.

### Contents

1 The common fourth-order Runge-Kutta method

2 Explicit Runge-Kutta methods

o 2.1 Examples

3 Usage

5 Implicit Runge-Kutta methods

6 References

### The Common Fourth-Order Runge-Kutta Method

One member of the family of Runge-Kutta methods is so commonly used that it is often referred to as “RK4”, “classical Runge-Kutta method” or simply as “the Runge-Kutta method”.

Let an initial value problem be specified as follows.

Then, the RK4 method for this problem is given by the following equations:

where yn + 1 is the RK4 approximation of y(tn + 1), and

Thus, the next value (yn + 1) is determined by the present value (yn) plus the product of the size of the interval (h) and an estimated slope. The slope is a weighted average of slopes:

k1 is the slope at the beginning of the interval;

k2 is the slope at the midpoint of the interval, using slope k1 to determine the value of y at the point tn + h / 2 using Euler’s method;

k3 is again the slope at the midpoint, but now using the slope k2 to determine the y-value;

k4 is the slope at the end of the interval, with its y-value determined using k3.

In averaging the four slopes, greater weight is given to the slopes at the midpoint:

The RK4 method is a fourth-order method[needs reference], meaning that the error per step is on the order of h5, while the total accumulated error has order h4.

Note that the above formulae are valid for both scalar- and vector-valued functions (i.e., y can be a vector and f an operator). For example one can integrate Schrödinger’s equation using the Hamiltonian operator as function f.

### Explicit Runge-Kutta Methods

The family of explicit Runge-Kutta methods is a generalization of the RK4 method mentioned above. It is given by

where

(Note: the above equations have different but equivalent definitions in different texts).

To specify a particular method, one needs to provide the integer s (the number of stages), and the coefficients aij (for 1 ≤ j < i ≤ s), bi (for i = 1, 2, …, s) and ci (for i = 2, 3, …, s). These data are usually arranged in a mnemonic device, known as a Butcher tableau (after John C. Butcher):

 0 c2 a21 c3 a31 a32 cs as1 as2 as,s − 1 b1 b2 bs − 1 bs

The Runge-Kutta method is consistent if

There are also accompanying requirements if we require the method to have a certain order p, meaning that the truncation error is O(hp+1). These can be derived from the definition of the truncation error itself. For example, a 2-stage method has order 2 if b1 + b2 = 1, b2c2 = 1/2, and b2a21 = 1/2.

### Examples

The RK4 method falls in this framework. Its tableau is:

 0 1/2 1/2 1/2 0 1/2 1 0 0 1 1/6 1/3 1/3 1/6

However, the simplest Runge-Kutta method is the (forward) Euler method, given by the formula yn + 1 = yn + hf(tn,yn). This is the only consistent explicit Runge-Kutta method with one stage. The corresponding tableau is:

 0 1

An example of a second-order method with two stages is provided by the midpoint method

The corresponding tableau is:

 0 1/2 1/2 0 1

Note that this ‘midpoint’ method is not the optimal RK2 method. An alternative is provided by Heun’s method, where the 1/2’s in the tableau above are replaced by 1’s and the b’s row is [1/2, 1/2]. If one wants to minimize the truncation error, the method below should be used (Atkinson p.423). Other important methods are Fehlberg, Cash-Karp and Dormand-Prince. Also, read the article on Adaptive Stepsize.

### Usage

The following is an example usage of a two-stage explicit Runge-Kutta method:

 0 2/3 2/3 1/4 3/4

to solve the initial-value problem

with step size h=0.025.

The tableau above yields the equivalent corresponding equations below defining the method:

k1 = yn

 t0 = 1 y0 = 1 t1 = 1.025 k1 = y0 = 1 f(t0,k1) = 2.557407725 k2 = y0 + 2 / 3hf(t0,k1) = 1.042623462 y1 = y0 + h(1 / 4 f(t0,k1) + 3 / 4 f(t0 + 2 / 3h,k2)) = 1.066869388 t2 = 1.05 k1 = y1 = 1.066869388 f(t1,k1) = 2.813524695 k2 = y1 + 2 / 3hf(t1,k1) = 1.113761467 y2 = y1 + h(1 / 4 f(t1,k1) + 3 / 4 f(t1 + 2 / 3h,k2)) = 1.141332181 t3 = 1.075 k1 = y2 = 1.141332181 f(t2,k1) = 3.183536647 k2 = y2 + 2 / 3hf(t2,k1) = 1.194391125 y3 = y2 + h(1 / 4 f(t2,k1) + 3 / 4 f(t2 + 2 / 3h,k2)) = 1.227417567 t4 = 1.1 k1 = y3 = 1.227417567 f(t3,k1) = 3.796866512 k2 = y3 + 2 / 3hf(t3,k1) = 1.290698676 y4 = y3 + h(1 / 4 f(t3,k1) + 3 / 4 f(t3 + 2 / 3h,k2)) = 1.335079087

The numerical solutions correspond to the underlined values. Note that f(ti,k1) has been calculated to avoid recalculation in the yis.

The adaptive methods are designed to produce an estimate of the local truncation error of a single Runge-Kutta step. This is done by having two methods in the tableau, one with order p and one with order p − 1.

The lower-order step is given by

where the ki are the same as for the higher order method. Then the error is

which is O(hp). The Butcher Tableau for this kind of method is extended to give the values of :

 0 c2 a21 c3 a31 a32 cs as1 as2 as,s − 1 b1 b2 bs − 1 bs

The Runge-Kutta-Fehlberg method has two methods of orders 5 and 4. Its extended Butcher Tableau is:

 0 1/4 1/4 3/8 3/32 9/32 12/13 1932/2197 −7200/2197 7296/2197 1 439/216 −8 3680/513 -845/4104 1/2 −8/27 2 −3544/2565 1859/4104 −11/40 16/135 0 6656/12825 28561/56430 −9/50 2/55 25/216 0 1408/2565 2197/4104 −1/5 0

However, the simplest adaptive Runge-Kutta method involves combining the Heun method, which is order 2, with the Euler method, which is order 1. Its extended Butcher Tableau is:

 0 1 1 1/2 1/2 1 0

The error estimate is used to control the stepsize.

Other adaptive Runge-Kutta methods are the Bogacki-Shampine method (orders 3 and 2), the Cash-Karp method and the Dormand-Prince method (both with orders 5 and 4).

### Implicit Runge-Kutta Methods

The implicit methods are more general than the explicit ones. The distinction shows up in the Butcher Tableau: for an implicit method, the coefficient matrix aij is not necessarily lower triangular:

The approximate solution to the initial value problem reflects the greater number of coefficients:

Due to the fullness of the matrix aij, the evaluation of each ki is now considerably involved and dependent on the specific function f(t,y). Despite the difficulties, implicit methods are of great importance due to their high (possibly unconditional) stability, which is especially important in the solution of partial differential equations. The simplest example of an implicit Runge-Kutta method is the backward Euler method:

The Butcher Tableau for this is simply:

It can be difficult to make sense of even this simple implicit method, as seen from the expression for k1:

In this case, the awkward expression above can be simplified by noting that

so that

from which

follows. Though simpler then the “raw” representation before manipulation, this is an implicit relation so that the actual solution is problem dependent. Multistep implicit methods have been used with success by some researchers. The combination of stability, higher order accuracy with fewer steps, and stepping that depends only on the previous value makes them attractive; however the complicated problem-specific implementation and the fact that ki must often be approximated iteratively means that they are not common.

Our editors will help you fix any mistakes and get an A+!

##### Thank you!

We will send an essay sample to you in 2 Hours. If you need help faster you can always use our custom writing service.

##### Sorry, but copying text is forbidden on this website. You can leave an email and we will send it to you.
Didn't find the paper that you were looking for?
We can create an original paper just for you!