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).


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)$


1 Answer 1


(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|<k}\alpha(\tau)\Phi_i(\tau)(h)F(\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|<k}\alpha(\tau)\Phi_i(\tau)(h)F(\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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.