Numerical Analysis/Order of RK methods/Derivation of a second order RK method

Let a single step numerical method for solving ODE of the type

$y'(t)=f(t,y(t)),y(t_{0})=y_{0},\,$

(1.1)

be given by the following [2,4] recurrence formula

$y_{n+1}=y_{n}+h(a_{1}k_{1}+a_{2}k_{2})\,$

(method)

with

$k_{1}=f(t_{n},y_{n})\,$

$k_{2}=f(t_{n}+ph,y_{n}+hqk_{1})\,$

Using Taylor series expansion about t_n, the following can be obtained

$y(t_{n}+h)=y(t_{n})+y'(t_{n})h+y''(t_{n})h^{2}/2+y'''(t_{n})h^{3}/3!+O(h^{4})\,$

(1.2)

Assuming that the previous point in (1.2) is exact (which we may because we are analyzing the local truncation error, i.e. the error generated at the last step), we will denote $y(t_{n})=y_{n},y(t_{n}+h)={\overline {y_{n+1}}}\,$. Therefore, both $y_{n}\,$ and ${\overline {y_{n+1}}}\,$ are considered exact values of $y(t)\,$ at $t=t_{n}\,$ and $t=t_{n}+h\,$, respectively.

Then,

${\overline {y_{n+1}}}=y_{n}+y'(t_{n})h+y''(t_{n})h^{2}/2+y'''(t_{n})h^{3}/3!+O(h^{4})\,$

(1.3)

Using the differential equation (1.1) and replacing the derivatives of y, (1.3) becomes

${\overline {y_{n+1}}}=y_{n}+f(t_{n},y_{n})h+f'(t_{n},y_{n})h^{2}/2+f''(t_{n},y_{n})h^{3}/3!+O(h^{4}),\,$

(1.4)

where

$f'(t_{n},y_{n})={\frac {\partial f}{\partial t}}(t_{n},y_{n})+{\frac {\partial f}{\partial y}}(t_{n},y_{n})f(t_{n},y_{n}),\,$

(1.5)

or in the compact form (1.5) is $f'(t_{n},y_{n})=\left(f_{t}+f_{y}f\right)_{t_{n},y_{n}},\,$

and

$f''(t_{n},y_{n})=\left({\frac {\partial ^{2}f}{\partial t^{2}}}+{\frac {\partial ^{2}f}{\partial y\partial t}}f+{\frac {\partial ^{2}f}{\partial y\partial t}}f+{\frac {\partial f}{\partial y}}{\frac {\partial f}{\partial t}}+{\frac {\partial ^{2}f}{\partial y^{2}}}f^{2}+{\frac {\partial f}{\partial y}}{\frac {\partial f}{\partial y}}f\right)_{t=t_{n},y=y_{n}}\,$

(1.6)

or in the compact form (1.6) is $f''(t_{n},y_{n})=\left(f_{tt}+2f_{ty}f+f_{t}f_{y}+f_{yy}f^{2}+f_{y}f_{y}f\right)_{t=t_{n},y=y_{n}}\,$

After substituting the expressions for f′ and f″ into the Taylor series expansion (1.4), the following is obtained

${\overline {y_{n+1}}}=y_{n}+hf(t_{n},y_{n})+{\frac {h^{2}}{2}}(f_{t}+f_{y}f)_{(t_{n},y_{n})}+{\frac {h^{3}}{6}}\left(f_{tt}+2f_{ty}f+f_{t}f_{y}+f_{yy}f^{2}+f_{y}f_{y}f\right)_{(t_{n},y_{n})}+O(h^{4})\,$

(1.7)

Now, our objective is to adjust the method's recurrence equation (1.2), such that it can be compared, term by term, with the equation obtained using the Taylor series expansion (1.7). This step requires the Taylor series expansion of the $f(t_{n}+ph,y_{n}+hqk_{1})\,$ term about the $(t_{n},y_{n})\,$ point, as follows.

${\begin{aligned}f(t_{n}+ph,y_{n}+hqk_{1})=&f(t_{n},y_{n})+{\frac {\partial f}{\partial t}}(t_{n},y_{n})(hp)+{\frac {\partial f}{\partial y}}(t_{n},y_{n})(qhf(t_{n},y_{n}))\\&+{\frac {h^{2}}{2}}\left({\frac {\partial ^{2}f}{\partial t^{2}}}p^{2}+2{\frac {\partial ^{2}f}{\partial y\partial t}}qpf+{\frac {\partial ^{2}f}{\partial y^{2}}}q^{2}f^{2}\right)_{t=t_{n},y=y_{n}}+O(h^{3})\,\end{aligned}}$

(1.8)

or in the compact symbolic form (1.8) is:

$f(t_{n}+ph,y_{n}+hqk_{1})=\left(f+f_{t}hp+f_{y}fhq+{\frac {h^{2}}{2}}(f_{tt}p^{2}+2f_{ty}qpf+f_{yy}q^{2}f^{2})\right)_{t=t_{n},y=y_{n}}+O(h^{3})\,$

(1.9)

By substituting (1.9) into (method), the following is obtained

${\begin{aligned}y_{n+1}=&y_{n}+\left(hf(a_{1}+a_{2})+ha_{2}(hpf_{t}+hqf_{y}f)+{\frac {h^{3}a_{2}}{2}}(f_{tt}p^{2}+2f_{t}f_{y}qpf+f_{yy}q^{2}f^{2})\right)_{t=t_{n},y=y_{n}}\\&+\underbrace {ha_{2}O_{2}(h^{3})} _{O_{3}(h^{4})}\,\end{aligned}}$

(1.10)

Finally, the method's equation (1.10) and the exact one step solution (1.7) can be compared. By substracting (1.10) from (10.7), the following error expression is obtained.

${\overline {y_{n+1}}}-y_{n+1}=\left((1-a_{1}-a_{2})hf+(1/2-pa_{2})h^{2}f_{t}+(1/2-qa_{2})h^{2}f_{y}f+A(h)\right)_{t=t_{n},y=y_{n}}\,$

(1.11)

where

${\begin{aligned}A(h)=&\left(h^{3}(1/3(f_{tt}+2f_{ty}f+f_{t}f_{y}+f_{yy}f^{2}+f_{y}f_{y}f)-{\frac {a_{2}}{2}}(f_{tt}p^{2}+2f_{t}f_{y}qpf+f_{yy}q^{2}f^{2}))\right)_{t=t_{n},y=y_{n}}\\&+O_{1}(h^{4})-O_{3}(h^{4})\,\end{aligned}}$

(1.12)

It can be noticed that the multiplier expression of $h^{3}\,$ in (1.12) does not cancel out in (1.11) for any combination of the parameters, since there are terms that appear only once without any parameter. This means that the dominant term in the error expression cannot be of higher order than $O(h^{3})\,$. In order to achieve the local truncation error of the third order, all terms in the error expression containing $h^{0},h^{1},h^{2}\,$ must be eliminated, by adjusting the 4 parameters. By satisfying the equations (1.13-1.15), the local error is of $O(h^{3})\,$, and, consequently, the global error is of $O(h^{2})\,$ order. Therefore, the resulting method is a second order method.

The equation set that must satisfied is the following

$a_{1}+a_{2}=1,\,$

(1.13)

$pa_{2}=1/2,\,$

(1.14)

$qa_{2}=1/2.\,$

(1.15)

There are three equations (1.13,1.14,1.15) but with four unknown parameters. This means that one parameter must be chosen. Now, it is tempting to ask whether the extra parameter (additional degree of freedom) could be used to cancel next term in the error expression. However, we have already seen that it is not possible in this case, due to the additional term that are not associated (multiplied) with a parameter.

Since one parameter can be chosen, then there is non-unique form of a second order method.

• (case 1) Choose $a_{1}=a_{2}\,$, then $a_{1}=a_{2}=1/2,p=q=1\,$

The method equation (1.2) for these parameter becomes

$y_{n+1}=y_{n}+{\frac {h}{2}}(k_{1}+k_{2})\,$

with

$k_{1}=f(t_{n},y_{n})\,$

$k_{2}=f(t_{n}+h,y_{n}+hk_{1})\,$

or in a compact form

$y_{n+1}=y_{n}+{\frac {h}{2}}(f(t_{n},y_{n})+f(t_{n}+h,y_{n}+hf(t_{n},y_{n})))\,$

• (case 2) If $a_{1}=0\,$ is chosen (notice that $a_{2}=0\,$ cannot be selected, because of the last two equations), then

$y_{n+1}=y_{n}+hk_{2}\,$

$k_{1}=f(t_{n},y_{n})\,$

$k_{2}=f(t_{n}+1/2h,y_{n}+1/2hk_{1})\,$

or in a compact form

$y_{n+1}=y_{n}+hf(t_{n}+h,y_{n}+hf(t_{n},y_{n}))\,$