# Numerical Integration Schemes Based on Composition of Adjoint Multistep Methods
## 3 Composition of Multistep Methods
### Adjoint for Multistep Method  
Adjoint for multistep method (3) can be derived in a similar way as for single step:  
\[-h\] \[\sum_{i=0}^{k}a_{i}y_{n+i}=-h\sum_{i=0}^{k}b_{i}f_{n+i}\] \[\text{shift:} \sum_{i=0}^{k}a_{k-i}y_{n-i}=-h\sum_{i=0}^{k}b_{k-i}f_{n-i}, \tag{7}\] \[\text{expand:} \sum_{i=0}^{k}a_{i}y_{n-i}=h\sum_{i=0}^{k}b_{i}f_{n-i}\]  
where \(\hat{a}_{i}=-a_{k-i}\), \(\hat{b}_{i}=b_{k-i}\). Further, we will highlight one of the key problems in the successful construction of composition schemes. Let us consider the following implicit linear multistep method with non-zero coefficients \(a_{0},a_{1},a_{2}\), \(a_{3},b_{0},b_{1},b_{2}\):  
\[a_{0}y_{n}+a_{1}y_{n-1}+a_{2}y_{n-2}+a_{3}y_{n-3}=h(b_{0}f_{n}+b_{1}f_{n-1}+b_ {2}f_{n-2}). \tag{8}\]  
The process of finding the adjoint equivalent to (7) is described in Figure 1. The resulting adjoint is the explicit linear multistep method:  
\[-a_{3}y_{n}+a_{2}y_{n-1}+a_{1}y_{n-2}+a_{0}y_{n-3}=h(b_{2}f_{n-1}+b_{1}f_{n-2} +b_{2}f_{n-3}).\]  
Another case of the linear multistep method is:  
\[a_{0}y_{n}+a_{1}y_{n-1}=h(b_{0}f_{n}+b_{1}f_{n-1}). \tag{9}\]  
Steps of obtaining the next adjoint method are depicted in Figure 2:  
\[a_{1}y_{n}+a_{0}y_{n-1}=h(b_{1}f_{n+1}+b_{0}f_{n}). \tag{10}\]One can see that adjoint (10) is not a linear multistep method because it possesses single implicit dependence from \(f_{n}\), similarly to conventional implicit methods, and one additional implicitness from \(f_{n+1}\). Some researchers call such dependencies \"super-future points\" [21]. Methods of this type were firstly obtained by [PERSON] to increase the stability region of backward differentiation formulas and are usually applied as predictor-corrector schemes with several predictors [22]. Of course, adjoints can be easily applied to ODE in a form \(\dot{y}=f(x)\) and in that case can be indistinguishable from their counterpart due to their symmetric nature. The following theorems generalize our results in applying of adjoint methods. Theorem 1: _The adjoint for the linear multistep method is a linear multistep method if and only if \(\exists l:a_{l}\
eq 0\,\forall j:b_{i}\
eq 0\,l\geq j\)._  
Proof: Take the oldest non-zero \(a_{l}\). If there is non-zero \(b_{i}\) with an index greater than \(l\), then the adjoint has the term with \(f_{n+(i-l)}\) and does not meet to (3). The adjoints which are not linear multistep methods have the same order of consistency [20]. Therefore for convergence of adjoint only stability is required. This leads us to the following theorems. Theorem 2: _The adjoint of the stable linear multistep methods is stable if and only if all roots of \(\rho(\zeta)\) are modulus one._  
Proof: If the generating polynomial \(\rho(\zeta)\) of the linear multistep method have a root with modulus \(\|\zeta_{i}\|\) then the generating polynomial \(\rho^{*}(\zeta)\) of its adjoint have a root with modulus \(\frac{1}{\|\zeta_{i}\|}\). For stability of linear multistep method and its adjoint both \(\|\zeta_{i}\|\) and \(\frac{1}{\|\zeta_{i}\|}\) should be not larger than one. Theorem 3: _If \(\exists i\geq 2:a_{i}\
eq 0\) then both linear multistep method and its adjoint can only be weakly stable in the best case. Otherwise at least one is unstable._  
\[\sum_{i=0}^{k}a_{i}y_{n+i}=-h\sum_{i=0}^{k}b_{i}f_{n+i}\]0 Example of adjoint finding for (8). \[\sum_{i=0}^{k}a_{i}y_{n+i}=-h\sum_{i=0}^{k}b_{i}f_{n+i}\]1 Example of adjoint finding for (9). Proof. : If there is a non-zero coefficient \(a_{i}\) with \(i\geq 2\) then generating polynomial \(\rho(\zeta)\) have at least two roots. If some roots are out or in the unit circle then a linear multistep method or its adjoint is unstable. Otherwise, they both are weakly stable. The existence of stable composition schemes consisting of a stable multistep method and its unstable adjoint or unstable multistep method and its unstable adjoint is not proven yet. In addition, the presence of a strong stable composition scheme based on a weakly stable multistep method is an open question as well.