Team:St Andrews/project/modelling/models/RK4

From 2010.igem.org

(Difference between revisions)
 
(15 intermediate revisions not shown)
Line 2: Line 2:
<html>
<html>
-
<h1> Foruth Order Runge-Kutta Method </h1>
+
<h1> Differential Solver (RK4) </h1>
</html>
</html>
Line 10: Line 10:
=Mathematical basis=
=Mathematical basis=
-
While the strict mathematical derivation of the Runge-Kutta method is available( see [http://www.ss.ncu.edu.tw/~lyu/lecture_files_en/lyu_NSSP_Notes/Lyu_NSSP_AppendixC.pdf here for details] ), we omit it here and instead give a brief explanation of the principles behind the technique.
+
While the strict mathematical derivation of the Runge-Kutta method is available (see [http://www.ss.ncu.edu.tw/~lyu/lecture_files_en/lyu_NSSP_Notes/Lyu_NSSP_AppendixC.pdf here for details] ), we omit it here and instead give a brief explanation of the principles behind the technique.
-
There are several key formulae in the 4th Order Runge-Kutta algorithm, which are:
+
There are several key formulae in the Fourth Order Runge-Kutta algorithm, which are:
[[Image:Runge kutta eqns.jpg]]
[[Image:Runge kutta eqns.jpg]]
 +
 +
'''Figure 1: Runge-Kutta equations'''
Line 26: Line 28:
-
Then consider k<sub>2</sub>. It should be noted that the x-value at which the function is being evaluated is halfway across the prediction interval and the y-value consists of the current y-value plus half of the Euler predicted Δy. So then the function is evaluated at a point lying halfway between the current point and the Euler-predicted next point. When we evaluate the function at this point what is produced is an estimate of the slope of the solution curve at this halfway point on curve. Multiplying this result by h gives a prediction of the y-jump made by the solution across the entire interval. However, this prediction is made not on the slope of the solution at the left end of the interval but on the estimated slope halfway to the next Euler-predicted point.
+
Then consider k<sub>2</sub>. It should be noted that the x-value at which the function is being evaluated is halfway across the prediction interval and the y-value consists of the current y-value plus half of the Euler predicted Δy. So then the function is evaluated at a point lying halfway between the current point and the Euler-predicted next point. When we evaluate the function at this point what is produced is an estimate of the slope of the solution curve at this halfway point on the curve. Multiplying this result by h gives a prediction of the y-jump made by the solution across the entire interval. However, this prediction is made not on the slope of the solution at the left end of the interval but on the estimated slope halfway to the next Euler-predicted point.
Line 32: Line 34:
-
Finally, k<sub>4</sub> evaluates the function at the right-hand side of the prediction interval. The y-value at which the function is evaluated, y<sub>n</sub>+k<sub>3</sub> is an estimate of the y-value at the right-hand side based on the estimate of the y-jump made by k<sub>3</sub>. In its entirey, k<sub>4</sub> gives a final estimate of the y-jump made by the solution across the entire width of the prediction interval.
+
Finally, k<sub>4</sub> evaluates the function at the right-hand side of the prediction interval. The y-value at which the function is evaluated, y<sub>n</sub>+k<sub>3</sub> is an estimate of the y-value at the right-hand side based on the estimate of the y-jump made by k<sub>3</sub>. In its entirety, k<sub>4</sub> gives a final estimate of the y-jump made by the solution across the entire width of the prediction interval.
So to provide a summary: each k<sub>i</sub> yields an estimate of the y-jump made by the solution across the entire width of the prediction interval h, with each using the previous k<sub>i</sub> to make its estimate. The Runge-Kutta formula can be viewed as the y-value of the current point plus a weighted average of four different predictions for the slope.
So to provide a summary: each k<sub>i</sub> yields an estimate of the y-jump made by the solution across the entire width of the prediction interval h, with each using the previous k<sub>i</sub> to make its estimate. The Runge-Kutta formula can be viewed as the y-value of the current point plus a weighted average of four different predictions for the slope.
 +
 +
 +
[[Image:Picture 4.png|600px]]
 +
 +
'''Figure 2: Runge-Kutta technique'''
 +
=Implementation=
 +
The code which performs the operations in the Runge-Kutta algorithm is shown below.
 +
 +
The operation of the algorithm is thus; k<sub>1</sub> is calculated from the value stored from the solved differential equation which is stored in the array "ode", multiplied by our step size h which can be chosen by the user. This process is looped round for each variable to produce an array with an element for variable in the system. Values for y<sub>2</sub> are then calculated using the value for k<sub>1</sub> and the y value from the previous iteration, which is initially zero. Again this process is looped round for each variable. Similar processes are followed for the other values, and finally the y value if found by averaging the calculated k-values. The Runge-Kutta function is called for every increment the model is run.
 +
 +
void RungeKutta(double y[], double dy[]){
 +
            double k1[var], k2[var], k3[var], k4[var], y2[var], y3[var], y4[var], *pode;
 +
            double h = 0.025;
 +
            pode = ode(y,dy);
 +
           
 +
            //Calculates k1 (for all variables) -> The slope at the start of the interval (h)
 +
            for (int i = 0; i < var; ++i) {
 +
                        k1[i] = *(pode + i) * h;
 +
            }
 +
 +
            //  Calculates k2 (for all variables) -> The slope at the midpoint of the interval (h),
 +
            for (int i = 0; i < var; ++i) {
 +
                        y2[i] =y[i] + k1[i] * 0.5 ;
 +
            }
 +
            pode = ode(y2,dy);
 +
            for (int i = 0; i < var; ++i) {
 +
                        k2[i] = *(pode + i) * h;
 +
            }
 +
 +
            // Calculates k3 (for all variables) -> The slope at the midpoint of... using the y value (y2) determined from k2.
 +
            for (int i = 0; i < var; i++) {
 +
                        y3[i]=y[i] + k2[i] * 0.5;
 +
            }
 +
            pode = ode(y3,dy);
 +
            for (int i = 0; i < var; i++) {
 +
                        k3[i] = *(pode + i) * h;
 +
            }
 +
 +
            // Calculates k4 (for all variables) -> The slope at the end of the interval (h).
 +
            for (int i = 0; i < var; i++) {
 +
                        y4[i]= y[i] + k3[i];
 +
            }
 +
            pode=ode(y4,dy);
 +
            for (int i = 0; i < var; i++) {
 +
                        k4[i] = *(pode + i) * h;
 +
            }
 +
 +
            // Calculates the new y values (for all variables).
 +
            for (int i = 0; i < var; i++){
 +
                        y[i] +=((k1[i] + 2*k2[i] + 2*k3[i] + k4[i])/6);
 +
            }
 +
}
 +
 +
=References=
 +
[1] Barker.C.A, "Numerical Methods for Solving Differential Equations,The Runge-Kutta Method, Theoretical Introduction", San Joaquin Delta College, 2009 http://calculuslab.deltacollege.edu/ODE/7-C-3/7-C-3-h.html, [Accessed 13 September 2010]
 +
 +
[2] "Numerical Recipes in Fortran 77: The Art of Scientific Computing", Cambridge University Press, 1992, pp 704-707

Latest revision as of 02:02, 28 October 2010


St Andrews from East Sands

University of St Andrews iGEM 2010

Welcome!

The Saints

University of St Andrews iGEM 2010

Our first year at iGEM!

Differential Solver (RK4)

Contents

Introduction

Our method of solving differential equations is based on Fourth Order Runge-Kutta Method. This technique is the most widely used way of numerically solving differential equations and various methods of implementation were looked at. Most of our coding has been based on the work of Aberdeen 2009 iGEM team who used the same method in their modelling. We would like to thank the team for their work and making it available to others like us for future use.

Mathematical basis

While the strict mathematical derivation of the Runge-Kutta method is available (see here for details ), we omit it here and instead give a brief explanation of the principles behind the technique.

There are several key formulae in the Fourth Order Runge-Kutta algorithm, which are:


Runge kutta eqns.jpg

Figure 1: Runge-Kutta equations


The iteration of the x-values is done very simply adding a fixed step-size (h) at each iteration, thus resulting in a constant increase in the x-value according to the value of h chosen for a particular purpose.

The y-value iteration contains a much more elegant set of relationships. It should be clear to you that the y-iteration formula is in fact a weighted average of the four value k values, k1, k2, k3 and k4. Even at a first glance it should also be apparent that a 'weight' of 2/6 is given to k2 and k3 while a smaller weighting of 1/6 is attributed to k1 and k2. What then do these k-value correspond to geometrically?


Look first at k1. It is equal to the function f(xn,yn) multiplied by the step-size h, which is just the Euler prediction for Δy. It is the vertical distance from the previous point to the next Euler-predicted point.


Then consider k2. It should be noted that the x-value at which the function is being evaluated is halfway across the prediction interval and the y-value consists of the current y-value plus half of the Euler predicted Δy. So then the function is evaluated at a point lying halfway between the current point and the Euler-predicted next point. When we evaluate the function at this point what is produced is an estimate of the slope of the solution curve at this halfway point on the curve. Multiplying this result by h gives a prediction of the y-jump made by the solution across the entire interval. However, this prediction is made not on the slope of the solution at the left end of the interval but on the estimated slope halfway to the next Euler-predicted point.


A comparison can be made between k3 and k2, with the only difference in their formulation being the replacement of k1 by k2. Here the function evaluated at this point gives an estimate of the solution slope at the midpoint of the prediction interval but one which is based in the y-jump predicted by k2 rather than the Euler-predicted one. When multiplied by h we get a further estimate of the y-jump made by the solution across the whole interval.


Finally, k4 evaluates the function at the right-hand side of the prediction interval. The y-value at which the function is evaluated, yn+k3 is an estimate of the y-value at the right-hand side based on the estimate of the y-jump made by k3. In its entirety, k4 gives a final estimate of the y-jump made by the solution across the entire width of the prediction interval.


So to provide a summary: each ki yields an estimate of the y-jump made by the solution across the entire width of the prediction interval h, with each using the previous ki to make its estimate. The Runge-Kutta formula can be viewed as the y-value of the current point plus a weighted average of four different predictions for the slope.


Picture 4.png

Figure 2: Runge-Kutta technique

Implementation

The code which performs the operations in the Runge-Kutta algorithm is shown below.

The operation of the algorithm is thus; k1 is calculated from the value stored from the solved differential equation which is stored in the array "ode", multiplied by our step size h which can be chosen by the user. This process is looped round for each variable to produce an array with an element for variable in the system. Values for y2 are then calculated using the value for k1 and the y value from the previous iteration, which is initially zero. Again this process is looped round for each variable. Similar processes are followed for the other values, and finally the y value if found by averaging the calculated k-values. The Runge-Kutta function is called for every increment the model is run.

void RungeKutta(double y[], double dy[]){
           double k1[var], k2[var], k3[var], k4[var], y2[var], y3[var], y4[var], *pode;
           double h = 0.025;
           pode = ode(y,dy);
           
           //Calculates k1 (for all variables) -> The slope at the start of the interval (h)
           for (int i = 0; i < var; ++i) {
                       k1[i] = *(pode + i) * h;
           }
           //  Calculates k2 (for all variables) -> The slope at the midpoint of the interval (h),
           for (int i = 0; i < var; ++i) {
                       y2[i] =y[i] + k1[i] * 0.5 ;
           }
           pode = ode(y2,dy);
           for (int i = 0; i < var; ++i) {
                       k2[i] = *(pode + i) * h;
           }
           // Calculates k3 (for all variables) -> The slope at the midpoint of... using the y value (y2) determined from k2.
           for (int i = 0; i < var; i++) {
                       y3[i]=y[i] + k2[i] * 0.5;
           }
           pode = ode(y3,dy);
           for (int i = 0; i < var; i++) {
                       k3[i] = *(pode + i) * h;
           }
           // Calculates k4 (for all variables) -> The slope at the end of the interval (h).
           for (int i = 0; i < var; i++) {
                       y4[i]= y[i] + k3[i];
           }
           pode=ode(y4,dy);
           for (int i = 0; i < var; i++) {
                       k4[i] = *(pode + i) * h;
           }
           // Calculates the new y values (for all variables).
           for (int i = 0; i < var; i++){
                       y[i] +=((k1[i] + 2*k2[i] + 2*k3[i] + k4[i])/6);
           }
}

References

[1] Barker.C.A, "Numerical Methods for Solving Differential Equations,The Runge-Kutta Method, Theoretical Introduction", San Joaquin Delta College, 2009 http://calculuslab.deltacollege.edu/ODE/7-C-3/7-C-3-h.html, [Accessed 13 September 2010]

[2] "Numerical Recipes in Fortran 77: The Art of Scientific Computing", Cambridge University Press, 1992, pp 704-707