8.5 The Fourth-Order Runge -Kutta Algorithm The last algorithm we'll examine in this chapter is from a set of algorithms called Runge-Kutta. [4] The most popular one is the fourth-order Runge-Kutta algorithm. Like the predictor -corrector algorithm, it uses an average of slopes, but Runge-Kutta also uses slopes taken within the interval, not just at the sides. [4] These algorithms are named after Carl Runge (1856C1927) and Martin Wilhelm Kutta (1867C1944), two German mathematicians who developed them. At each interval, Runge-Kutta starts out by computing in sequence four values, where y ' = f ( x, y ): The algorithm makes several "probes" into the interval and at the other side of the interval to get slope values: -
First, k 1 is the slope at the point ( x i , y i ) at the beginning of the interval. -
Using k 1 , we find a point halfway into the interval and compute k 2 , the slope at that point. -
Then we go back to the beginning point and use k 2 to find another point halfway into the interval and compute k 3 , the slope at that point. -
Once again, we return to the beginning point and use k 3 to find a point at the other side of the interval and compute k 4 , the slope at that point. -
Finally, from the beginning point ( x i , y i ), we use a weighted average of the four slopes to compute the next point at the other side of the interval: and x i + 1 = x i + h. Listing 8-1e shows class RungeKuttaDiffEqSolver in package numbercruncher.mathutils , a subclass of DiffEqSolver . Its nextPoint() method implements the fourth-order Runge-Kutta algorithm. Listing 8-1e Class RungeKuttaDiffEqSolver , the differential equation solver that implements the fourth-order Runge-Kutta algorithm. package numbercruncher.mathutils; /** * Differential equation solver that implements * a fourth-order Runge-Kutta algorithm. */ public class RungeKuttaDiffEqSolver extends DiffEqSolver { /** * Constructor. * @param equation the differential equation to solve */ public RungeKuttaDiffEqSolver(DifferentialEquation equation) { super(equation); } /** * Return the next data point in the * approximation of the solution. * @param h the width of the interval */ public DataPoint nextPoint(float h) { float k1 = equation.at(x, y); float k2 = equation.at(x + h/2, y + k1*h/2); float k3 = equation.at(x + h/2, y + k2*h/2); float k4 = equation.at(x + h, y + k3*h); y += (k1 + 2*(k2 + k3) + k4)*h/6; x += h; return new DataPoint(x, y); } } By changing the command-line argument to the noninteractive version of Program 8C1 (review Listing 8-1b) to "runge," we get output from instantiating a RungeKuttaDiffEqSolver object. See Listing 8-1f. Listing 8-1f Output from Program 8C1 with the command-line argument "runge" for the fourth-order Runge-Kutta algorithm. ALGORITHM: Runge-Kutta Differential equation: f(x,y) = 6x^2 - 20x + 11 Initial condition: y(0.0) = -5.0 Analytical solution: y = 2x^3 - 10x^2 + 11x - 5 True value: y(6.0) = 133.0 n h y(6.0) Error ----------------------------------------------------- 2 3.0 133.0 0.0 4 1.5 133.0 0.0 Differential equation: f(x,y) = 2xe^2x + y Initial condition: y(0.0) = 1.0 Analytical solution: y = 3e^x - 2e^2x + 2xe^2x True value: y(1.0) = 8.154845 n h y(1.0) Error ----------------------------------------------------- 2 0.5 8.148893 -0.0059518814 4 0.25 8.154289 -5.559921E-4 8 0.125 8.154804 -4.1007996E-5 16 0.0625 8.154843 -1.9073486E-6 32 0.03125 8.154845 0.0 64 0.015625 8.154845 0.0 Differential equation: f(x,y) = xe^-2x - 2y Initial condition: y(0.0) = -0.5 Analytical solution: y = (x^2e^-2x - e^-2x)/2 True value: y(1.0) = 0.0 n h y(1.0) Error ----------------------------------------------------- 2 0.5 -0.0027439892 -0.0027439892 4 0.25 -1.2015179E-4 -1.2015179E-4 8 0.125 -6.262213E-6 -6.262213E-6 16 0.0625 -3.6507845E-7 -3.6507845E-7 32 0.03125 -3.4924597E-8 -3.4924597E-8 64 0.015625 1.7695129E-8 1.7695129E-8 128 0.0078125 1.2805685E-9 1.2805685E-9 256 0.00390625 6.9849193E-9 6.9849193E-9 Of the three algorithms we've examined, the fourth-order Runge-Kutta algorithm has the fastest convergence and generates the most accurate solutions. But, of course, it requires the most computation per interval. Screen 8-1c shows the first three iterations of the interactive version of Program 8C1 using this algorithm to solve the same initial value problem as in Screens 8-1a and 8-1b. Screen 8-1c. The first three iterations of Program 8C1 using the fourth-order Runge-Kutta algorithm to solve the initial value problem y' = xe -2 x - 2 y and y (0) = -0.5. The analytical solution is the smooth curve, and the numerical solution consists of the line segments. The dot represents the initial condition. |