Determining the order of an implicit Runge-Kutta method

3.2. Determining the order of an implicit Runge-Kutta method#

One of the differences between implicit and explicit methods is that an implicit method can achieve the same accuracy as an explicit method but using fewer stages. To determine the order of an implicit method we need to consider the order conditions that govern the values of the coefficients \(a_{ij}\), \(b_i\) and \(c_i\)

\[\begin{align*} B(k): && \sum_{i=1}^s b_i c_i^{j-1} = & \frac{1}{j}, & j&=1\ldots k, \\ C(k): && \sum_{j=1}^s a_{ij} c_j^{\ell-1} = & \frac{1}{\ell}c_i^{\ell} , & i&=1 \ldots s, & \ell &=1 \ldots k,\\ D(k): && \sum_{i=1}^s b_i c_i^{\ell-1} a_{ij} = & \frac{1}{\ell}b_j (1-c_j^{\ell}), & j&=1 \ldots s, & \ell &=1 \ldots k. \end{align*}\]

Let \(G(k)\) represent the fact that a given implicit method has order \(k\) then it can be shown that

\[B(k) \text{ and } C(\left\lfloor \tfrac{1}{2}k \right\rfloor) \text{ and } D (\left\lfloor \tfrac{1}{2}k \right\rfloor) \implies G(2s)\]

In other words, to determine the order of an IRK method we need find the highest value of \(k\) for which \(B(k)\) and \(C(\left\lfloor \frac{1}{2}k \right\rfloor)\) and \(D(\left\lfloor \frac{1}{2}k \right\rfloor)\) are satisfied. If no value of \(k\) satisfies these conditions then it is not a valid implicit Runge-Kutta method.

Example 3.3

Determine the order of the following IRK method

\[\begin{align*} \begin{array}{c|cc} 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & 0 \\ 1 & 0 & 1 & 0 \\ \hline 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \end{array} \end{align*}\]

Solution

First check the highest value of \(k\) that satisfies \(B(k)\)

\[\begin{split} \begin{align*} k &= 1: & B(1) &= b_1 + b_2 + b_3 = \frac{1}{6} + \frac{2}{3} + \frac{1}{6} = 0, \\ k &= 2: & B(2) &= b_1c_1 + b_2c_2 + b_3c_3 = \frac{1}{6}(0) + \frac{2}{3}\left( \frac{1}{2} \right) + \frac{1}{6} (1) = \frac{1}{2}, \\ k &= 3: & B(3) &= b_1c_1^2 + b_2c_2^2 + b_3c_3^2 = \frac{1}{6}(0)^2 + \frac{2}{3} \left(\frac{1}{2}\right)^2 + \frac{1}{6}(1)^2 = \frac{1}{3}, \\ k &= 4: & B(4) &= b_1c_1^3 + b_2c_2^3 + b_3c_3^3 = \frac{1}{6}(0)^3 + \frac{2}{3} \left(\frac{1}{2}\right)^3 + \frac{1}{6}(1)^3 = \frac{1}{4}, \\ k &= 5: & B(5) &= b_1c_1^4 + b_2c_2^4 + b_3c_3^4 = \frac{1}{6}(0)^4 + \frac{2}{3} \left(\frac{1}{2}\right)^4 + \frac{1}{6}(1)^4 = \frac{5}{24}. \end{align*} \end{split}\]

So the highest value of \(k\) for which \(B(k)\) is satisfied is \(k=4\). We now need to check whether \(C(2)\) and \(D(2)\) are satisfied.

\[\begin{split} \begin{align*} \ell &= 1, & i &= 1: & LHS &= a_{11} + a_{12} + a_{13} = 0 + 0 + 0 = 0, \\ &&&& RHS &= \frac{1}{1}c_1^1 = 0, \\ \ell &= 1, & i &= 2: & LHS &= a_{21} + a_{22} + a_{23} = \frac{1}{4} + \frac{1}{4} + 0 = \frac{1}{2}, \\ &&&& RHS &= \frac{1}{1}c_2^1 = \frac{1}{2}, \\ \ell &= 1, & i &= 3: & LHS &= a_{31} + a_{32} + a_{33} = 0 + 1 + 0 = 1, \\ &&&& RHS &= \frac{1}{1}c_3^1 = 1, \\ \ell &= 2, & i &= 1: & LHS &= a_{11}c_1 + a_{12}c_2 + a_{13}c_3 = 0(0) + 0\left(\frac{1}{2}\right) + 0(1) = 0, \\ &&&& RHS &= \frac{1}{2}c_1^2 = 0, \\ \ell &= 2, & i &= 2: & LHS &= a_{21}c_1 + a_{22}c_2 + a_{23}c_3 = \frac{1}{4}(0) + \frac{1}{4}\left(\frac{1}{2}\right) + 0(1) = \frac{1}{8}, \\ &&&& RHS &= \frac{1}{2}c_2^2 = \frac{1}{2}\left(\frac{1}{2}\right)^2 = \frac{1}{8}, \\ \ell &= 2, & i &= 3: & LHS &= a_{31}c_1 + a_{32}c_2 + a_{33}c_3 = 0(0) + 1\left(\frac{1}{2}\right) + 0(1) = \frac{1}{2}, \\ &&&& RHS &= \frac{1}{2}c_3^3 = \frac{1}{2}(1)^3 = \frac{1}{2}. \end{align*} \end{split}\]

So the \(C(2)\) condition is satisfied. Checking the \(D(2)\) condition

\[\begin{split} \begin{align*} \ell &= 1, & j &= 1: & LHS &= b_1a_{11} + b_2a_{21} + b_3a_{31} = \frac{1}{6}(0) + \frac{2}{3}\left(\frac{1}{4}\right) + \frac{1}{6}(0) = \frac{1}{6}, \\ &&&& RHS &= \frac{1}{1}b_1(1 - c_1^1) = \frac{1}{6}(1 - 0) = \frac{1}{6}, \\ \ell &= 1, & j &= 2: & LHS &= b_1a_{12} + b_2a_{22} + b_3a_{32} = \frac{1}{6}(0) + \frac{2}{3}\left( \frac{1}{4} \right) + \frac{1}{6}(1) = \frac{1}{3}, \\ &&&& RHS &= \frac{1}{1}b_2(1 - c_2^1) = \frac{2}{3}\left(1 - \frac{1}{2}\right) = \frac{1}{3}, \\ \ell &= 1, & j &= 3: & LHS &= b_1a_{13} + b_2a_{23} + b_3a_{33} = \frac{1}{6}(0) + \frac{2}{3}\left(\frac{1}{4}\right) + \frac{1}{6}(0) = \frac{1}{6}, \\ &&&& RHS &= \frac{1}{1}b_3(1 - c_3^1) = \frac{1}{6}(1 - 0) = \frac{1}{6}, \\ \ell &= 2, & j &= 1: & LHS &= b_1c_1a_{11} + b_2c_2a_{21} + b_3c_3a_{31} = \frac{1}{6}(0)(0) + \frac{2}{3}\left(\frac{1}{2}\right)\left(\frac{1}{4}\right) + \frac{1}{6}(1)(0) = \frac{1}{12}, \\ &&&& RHS &= \frac{1}{2}b_1(1 - c_1^2) = \frac{1}{2}\left(\frac{1}{6}\right)(1 - 0) = \frac{1}{12}, \\ \ell &= 2, & j &= 2: & LHS &= b_1c_1a_{12} + b_2c_2a_{22} + b_3c_3a_{23} = \frac{1}{6}(0)(0) + \frac{2}{3}\left(\frac{1}{2}\right)\left(\frac{1}{4}\right) + \frac{1}{6}(1)(1) = \frac{1}{4}, \\ &&&& RHS &= \frac{1}{2}b_2(1 - c_2^2) = \frac{1}{2} \left(\frac{2}{3}\right) \left(1 - \left(\frac{1}{2}\right)^2\right) = \frac{1}{4}, \\ \ell &= 2, & j &= 3: & LHS &= b_1c_1a_{13} + b_2c_2a_{23} + b_3c_2a_{33} = \frac{1}{6}(0)(0) + \frac{2}{3}\left(\frac{1}{2}\right)(0) + \frac{1}{6}(1)(0) = 0, \\ &&&& RHS &= \frac{1}{2}b_3(1 - c_3^3) = \frac{1}{2}\left(\frac{1}{6}\right)(1 - 1^2) = 0. \end{align*} \end{split}\]

So the \(D(2)\) condition is also satisfied, therefore this method is a fourth-order method.