Examination Questions#
The following are examination questions from previous examinations for this module. Students are advised to work through these in preparation for the examination.
Explicit Runge-Kutta Methods#
(a) An explicit Runge-Kutta method is expressed using the Butcher tableau below.
\[\begin{split} \begin{align*} \begin{array}{c|cccc} 0 & 0 \\ \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 1 & 1 & -2 & 2 \\ \hline & \frac{1}{6} & 0 & \frac{2}{3} & \frac{1}{6} \end{array} \end{align*} \end{split}\]Use this Runge-Kutta method with a step length of \(h = 0.2\) to solve the following IVP
\[ \begin{align*} y' &= t - 2 y, & t &\in [0, 1], & y(0) &= 2. \end{align*} \][10 marks](b) The exact solution to the IVP from part (a) is \(y(t) = \frac{1}{9}(3t + 19 e^{-3t} - 1)\). Calculate the global truncation error for the numerical solution to the IVP for \(y(1)\) using the Runge-Kutta method from part (a) with \(h = 0.2\) and \(h = 0.1\). Use your global truncation errors to estimate the order accuracy of this Runge-Kutta method.
[10 marks](c) Explain in words how step size control is implemented within a Runge-Kutta method.
[5 marks]
Solution
(a)
import numpy as np
def f(t, y):
return t - 2 * y
h = 0.2
nsteps = 5
t = np.arange(0, 1 + h, h)
y = np.zeros(t.shape)
for n in range(nsteps):
k1 = f(t[n], y[n])
k2 = f(t[n] + 1/4 * h, y[n] + 1/4 * h * k1)
k3 = f(t[n] + 1/2 * h, y[n] + 1/2 * h * k2)
k4 = f(t[n] + h, y[n] + h * (k1 - 2 * k2 + 2 * k3))
y[n+1] = y[n] + h / 6 * (k1 + 4 * k3 + k4)
print(t)
print(y)
f = @(t, y) t - 2 * y;
nsteps = 5;
h = 0.2;
t = 0 : h : 1;
y = zeros(size(t));
y(1) = 2;
for n = 1 : nsteps
k1 = f(t(n), y(n));
k2 = f(t(n) + 1/4 * h, y(n) + 1/4 * h * k1);
k3 = f(t(n) + 1/2 * h, y(n) + 1/2 * h * k2);
k4 = f(t(n) + h, y(n) + h * (k1 - 2 * k2 + 2 * k3));
y(n+1) = y(n) + h / 6 * (k1 + 4 * k3 + k4);
end
t
y
Note: solutions may also be calculated using a pen and calculator or using Excel.
(b) The exact solution is \(y(1) = 0.554504\) and numerical solutions are \(y(1, h= 0.2) = 0.554686\) and \(y(1,h = 0.1) = 0.554514\) so the GTE are
therefore
Implicit Runge-Kutta Methods#
(a) The \(B(k)\) and \(C(k)\) order conditions for a Runge-Kutta method are
\[\begin{split} \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, \end{align*} \end{split}\]and the \(n\)-order Legendre polynomial is
\[ \begin{align*} P_n(x) = \sum_{i=0}^n {n \choose i} {n + i \choose i} (x - 1)^i, \end{align*} \]where \({n \choose i}\) is the Binomial coefficient.
An \(s\)-stage Radau IIA method has order \(2s - 1\), the \(c_i\) values are the roots of \(P_s(x) - P_{s-1}(x)\) and the \(a_{ij}\) and \(b_i\) coefficients are chosen to satisfy the \(B(2s)\) and \(C(s)\) order conditions respectively.
Derive a third-order Radau IIA method expressing your solution as a Butcher tableau.
[10 marks](b) A 2-stage SDIRK method is given below
\[\begin{split} \begin{align*} \begin{array}{c|cc} \frac{1}{8} & \frac{1}{8} & 0 \\ \frac{7}{8} & \frac{3}{4} & \frac{1}{8} \\ \hline & \frac{1}{2} & \frac{1}{2} \end{array} \end{align*} \end{split}\]Write the stability function of this method and determine whether it is A-stable or not. You may find the following formulae useful:
\[\begin{split} \begin{align*} R(z) &= \frac{\det(I - zA + z\mathbf{eb}^\mathsf{T})}{\det(I - zA)}, \\ E(y) &= |Q(iy)|^2 - |P(iy)|^2. \end{align*} \end{split}\][10 marks](c) Explain what is meant by a stiff system of equations. What methods would be most suitable for solving stiff and non-stiff problems?
[5 marks]
Solution
A third-order Radua IIA method has \(s = 2\) stages. The values of \(c_1\) and \(c_2\) are the roots of \(P_2(x) - P_1(x) = 0\)
so \(c_1 = \frac{1}{3}\) and \(c_2 = 1\). The \(b_1\) and \(b_2\) values satsisfy the \(B(2)\) order conditions
so \(b_1 = \frac{3}{4}\) and \(b_2 = \frac{1}{4}\). The \(A\) values satisfy the \(C(1)\) order conditions
Substracting the third equation from the first gives \(a_{11} = \frac{5}{12}\) so \(a_{12} = -\frac{1}{12}\). Subtracting the fourth equation from the second gives \(a_{21} = \frac{3}{4}\) and \(a_{22} = \frac{1}{4}\). So the Butcher tableau for the third-order Radau IIA method is
(b) The stability function for this DIRK method is
The roots of the denominator are
which is positive so the first condition for A-stability is satisfied.
Matrix Decomposition Methods#
(a) Use LUP decomposition to solve the following system of equations
\[\begin{split} \begin{align*} 2x_1 + 2x_2 + x_3 &= 11, \\ 4x_1 + x_2 + 3x_3 &= 46, \\ -3x_1 - 5x_2 + 4x_3 &= 14. \end{align*} \end{split}\][10 marks](b) The Gram-Schmidt method for computing the QR decomplsition of the matrix \(A\) is:
for \(j = 1 \ldots n\)
\(r_{ij} = \mathbf{q}_i \cdot \mathbf{a}_j, \qquad i = 1, \ldots, j - 1\)
\(\mathbf{u}_j = \mathbf{a}_i - \displaystyle\sum_{i=1}^{j - 1} r_{ij} \mathbf{q}_i\)
\(r_{jj} = \| \mathbf{u}_j \|\)
\(\mathbf{q}_j = \dfrac{\mathbf{u}_i}{r_{jj}}\)
Calculate the QR decomposition of the following matrix using the Gram-Schmidt process and verify that your decomposition is an orthogonal matrix.
\[\begin{split} \begin{align*} A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 3 & 4 \end{pmatrix} \end{align*} \end{split}\][10 marks](c) Explain how LU decomposition used in the calculation of the stage values of an implicit Runge-Kutta method. What advantages does it have for this application over other methods for solving systems of linear equations?
[5 marks]
Solution
(a) Performing partial pivoting on the coefficient matrix
Performing the same row swaps on \(I_3\)
Computing the LU decomposition of \(PA\)
therefore
Solving \(L\mathbf{y} = P \mathbf{b}\)
Solving \(U \mathbf{x} = \mathbf{y}\)
(b)
therefore