3.1. 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 following order conditions that govern the values of the coefficients \(a_{ij}\), \(b_i\) and \(c_i\).

Definition 3.1 (The \(B(k)\), \(C(k)\) and \(D(k)\) order conditions)

\[\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*}\]

For convenience 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(\lfloor \tfrac{1}{2}k \rfloor) \text{ and } D (\lfloor \tfrac{1}{2}k \rfloor) \implies G(2s)\]

So to determine the order of an IRK method we need find the highest value of \(k\) for which \(B(k)\) and \(C(\lfloor \frac{1}{2}k \rfloor)\) and \(D(\lfloor \frac{1}{2}k \rfloor)\) are satisfied. If no value of \(k>0\) satisfies these conditions then it isn’t a valid implicit Runge-Kutta method.

Example 3.1

Determine the order of the following IRK method

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

Solution (click to show)

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.