# Understanding proof : Runge-Kutta and B-series

I'm working with a theorem on representing the numerical approximation of an ODE with a B-series, where I can't follow some of the steps in the proof so hoping there is someone on here who will help clear it up for me.

$$\mathbf{Theorem}$$ The numerical approximation $$y_{1}$$ as well as the stage values $$Y_{0, i}$$ can be written in terms of $$B$$ -series $$Y_{0, i}=B\left(\Phi_{i}, y_{0} ; h\right), \quad y_{1}=B\left(\beta, y_{0} ; h\right)$$ with \begin{align} \Phi(\emptyset) & \equiv \mathbb{1}_{s}, \quad \Phi(\bullet)(h)=h \mathcal{A} \mathbb{1}_{s} \tag{5.12a} \\ \Phi(\tau)(h) &=h \mathcal{A}\left(\odot_{j=1}^{\kappa} \Phi\left(\tau_{j}\right)(h)\right) \text { if } \tau=\left[\tau_{1}, \ldots, \tau_{\kappa}\right] \tag{5.12b} \end{align} and \begin{align} \beta(\emptyset) & \equiv 1, \quad \beta(\bullet)(h)=h b^{\top} \mathbb{1}_{s} \tag{5.13a}\\ \beta\left(\left[\tau_{1}, \ldots, \tau_{\kappa}\right]\right)(h) &=h b^{\top}\left(\odot_{j=1}^{\kappa} \Phi\left(\tau_{j}\right)(h)\right)\tag{5.13b} \end{align}

$$\mathbf{Proof:}$$ Write $$Y_{0, i}$$ as a B-series, that is \begin{align} Y_{0, i} &=\sum_{\tau \in T} \alpha(\tau) \Phi_{i}(\tau)(h) F(\tau)\left(y_{0}\right) \tag{1a}\\ &= \color{gray}{ \alpha(\emptyset) \Phi_{i}(\emptyset)(h) F(\emptyset)\left(y_{0}\right)+\sum_{\tau \in T \backslash \emptyset} \alpha(\tau) \Phi_{i}(\tau)(h) F(\tau)\left(y_{0}\right)}\tag{1b} \end{align} Use Definition [ 5.1] of the Runge-Kutta method together with Lemma [ 5.2] to obtain \begin{align} Y_{0, i} &=y_{0}+h \sum_{j=1}^{s} a_{i j} f\left(Y_{0, j}\right) \tag{2a}\\ &=y_{0}+h \sum_{j=1}^{s} a_{i j} f\left(\sum_{\tau \in T} \alpha(\tau) \Phi_{j}(\tau)(h) F(\tau)\left(y_{0}\right)\right) \tag{2b}\\ &=y_{0}+h \sum_{j=1}^{s} a_{i j} \sum_{\tau \in T} \alpha(\tau) \Phi_{j}^{\prime}(\tau)(h) F(\tau)\left(y_{0}\right) \tag{2c}\\ &=y_{0}+\sum_{\tau \in T} \alpha(\tau)\left(h \mathcal{A} \Phi^{\prime}(\tau)(h)\right)_{i} F(\tau)\left(y_{0}\right) \tag{2d}\\ &=\color{gray}{y_{0}+\alpha(\theta)\left(h \mathcal{A} \Phi^{\prime}(\emptyset)(h)\right)_{i} F(\tau)\left(y_{0}\right)+}\\ & \qquad\color{gray}{\sum_{\tau \in T \backslash \emptyset} \alpha(\tau)\left(h \mathcal{A} \Phi^{\prime}(\tau)(h)\right)_{i} F(\tau)\left(y_{0}\right) }\tag{2e}\\ & \end{align}

Comparing the two series in gray print (here 1b and 2e) term-by-term and taking Lemma [ 5.2] into account gives $$\Phi_{i}(\tau)=h\left(\mathcal{A} \Phi^{\prime}(\tau)\right)_{i}+\left\{\begin{array}{ll}{1} & {: \tau=\emptyset} \\ {0} & {: \tau \neq \emptyset}\end{array}, \text { which proves }(5.12)\right.$$ Analogously, \begin{aligned} y_{1} &=y_{0}+h \sum_{i=1}^{s} b_{i} f\left(Y_{0, i}\right) \\ &=y_{0}+\sum_{\tau \in T} \alpha(\tau) h b^{\top} \Phi^{\prime}(\tau)(h) F(\tau)\left(y_{0}\right) \end{aligned} which, by similar considerations, leads to ( 5.13).

$$\mathbf{Questions}\\$$

So what understand is that (1a) and (1b) is to set up what we want to arrive at.

Then (2a) is from the definition reffered to (def 5.1).

(2b) $$Y_{0,j}$$ is written as a B-series, but how can this be justified? My thought is that since we are here to prove that $$Y_{0,i}$$ can be written as b-series then is must also be true for $$Y_{0,j}$$

(2c) lemma 5.2: function of a b-series gives a modified functoin $$\phi'$$

(2d) Here I see that $$h\sum a_{ij}$$ is moved 'into' the b-series, but now we have the matrix $$\mathcal{A}$$ instead of the sum of its entries, how do they get to this point? I also dont understand the subscript of i here

Lastly I also have trouble understanding the term by term comparison of (1b) and (2e). Of course I see that the main difference is in the term with $$\phi (\tau)$$ but I dont see how they arrive at that specific $$\phi (\tau)$$

(2a) Yes. (2b) You are right that in the cited form the proof of the theorem seems to assume that an expansion of the step as B-series exists, and only computes the concrete form of its coefficients. As I do not know what preceded this theorem, this may be a defect or just some unfortunate formulation.

The steps to cover this gap are not that large

1. For a generic smooth or analytic $$f$$ the stage equations as implicit system of equations have a Taylor expansion in powers of $$h$$.

2. Modulo $$O(h)$$ it is trivial to see that $$Y_{0,i}=y_0+O(h)$$.

3. Modulo $$O(h^2)$$ one then sees $$Y_{0,i}=y_0+hc_if(y_0)+O(h^2)$$, $$c=A1\!\!1_s$$. This can be interpreted as the beginning of a B-series.

4. Now conclude by induction that if $$Y_{0,i}$$ is a B-series $$\sum_{|\tau| modulo $$O(h^k)$$, then by inserting into the stage equations it follows that also the degree $$k$$ terms, $$|\tau|=k$$ are terms of the B-series, as the expansion of $$f(\sum_{|\tau| consists of only B-series terms (as that's the design principle of the B-series). (2c) Disregarding the specific composition, this gives some other set of B-series coefficients, provisionally call them $$\Phi'_i$$.

5. Looking closer at the terms and comparing coefficients, one then also finds the coefficient relations of the theorem.

(2d) $$\Phi'$$ is to be understood as the column vector of $$\Phi'_1,...,\Phi'_s$$. The final subscript $$i$$ then indicates that the row-$$i$$ term is extracted. This is just matrix-vector-multiplication notation, $$\sum_j A_{ij}x_j=[Ax]_i$$.

The formula is somewhat over-complicated, it would have been simpler to write $$\Phi_i(\tau)(h)=\begin{cases}1,&\tau=\emptyset\\h\left(\mathcal{A} \Phi^{\prime}(\tau)\right)_{i},&\text{else}\end{cases}$$ There are no terms without $$f$$ in the expansion of $$f(Y_{0,j})$$, so $$\Phi'(\emptyset)=0$$, I'm not sure why this was explicitly added in (2e).