david/Stability optimization of linear multistep methods

An explicit linear multistep method

\[\begin{align*} \sum_{j=0}^{k} \alpha_j u_{n+j} + h \beta_j F(u_{n+j})\end{align*}\]

applied to the linear scalar test problem \[u'(t) = \lambda u\] results in the iteration (taking, WLOG, \(\alpha_k = -1\)) \[u_{n+k} = \sum_{j=0}^{k-1}\left(\alpha_j + z \beta_j\right) u_{n+j}\] where \(z=h\lambda\).

This can be rewritten as a multivalued one-step method, using the companion matrix: \[\begin{pmatrix} u_{n+1} \\ u_{n+2} \\ \vdots \\ u_{n+k-1} \\ u_{n+k} \end{pmatrix} = \begin{pmatrix} & 1 & \\ & & 1 & \\ & & & \ddots & \\ & & & & 1 \\ \alpha_0 + z\beta_0 & \alpha_1 + z\beta_1 & \cdots & \cdots & \alpha_{k-1} + z\beta_{k-1} \end{pmatrix} = \begin{pmatrix} u_{n} \\ u_{n+1} \\ \vdots \\ u_{n+k-2} \\ u_{n+k-1} \end{pmatrix}\] The method is absolutely stable for a given \(z\) if the eigenvalues \(\mu_i\) of the matrix above satisfy the root condition: \[|\mu_i| \le 1 \mbox{ and if } |\mu_i|=1, \mu_i \mbox{ is a simple eigenvalue.}\]

We’d like to solve the following problem:

Given a spectrum \(\{\lambda_i\}\), a number of steps \(k\), and an order of accuracy \(p\), choose \(\alpha, \beta\) to maximize \(h\) subject to

• The eigenvalues of the companion matrix, \(\mu_i(h\lambda_i)\), satisfy the root condition for each \(\lambda_i\).

• Order conditions are satisfied (a set of linear equality constraints involving \(\alpha,\beta\)).

Thus we have a set of matrices (corresponding to points in the complex plane) and as a first approach we can think of trying to minimize the magnitude of the largest eigenvalue.