aron/sandbox

We have added some edits

An explicit linear multistep method \[ \begin{align} \label{lmm} u_n = \sum_{j=0}^{k-1} \alpha_j u_{n-k+j} + \Delta t \beta_j F(u_{n-k+j}) \end{align} \]

is said to have SSP coefficient \(r>0\) if \[ \begin{align} \label{sspc} \beta_j & \ge 0 & \alpha_j - r \beta_j & \ge 0 & \mbox{ for } 0\le j \le k-1. \end{align} \] The method is accurate to order \(p\) if

\[ \begin{align} \label{oc} \sum_{j=0}^{k-1} \left(j^m \alpha_j + mj^{m-1}\beta_j\right) & = k^m & \mbox{ for } 0\le m\le p. \end{align} \]

A fundamental open question is whether SSP methods exist with arbitrarily high order. That is, given any positive integer \(p\), do there exist \(r>0,k>0\) and coefficients \(\alpha,\beta\) such that and are satisfied?

This can be written as a standard linear programming feasibility problem by introducing \(\delta_j = \alpha_j-r\beta_j\). Then the order conditions read This system of equations can be written as where \(x=(\delta_0,\dots,\delta_{k-1},\beta_0,\dots,\beta_{k-1})^T\) and

The problem then amounts to proving that for some \(r>0\) and sufficiently large \(k\), the vector \(v_k\) can be written as a positive linear combination of the vectors \(v_j\) and \(w_j\) for \(0\le j \le k-1\).

Farkas’ lemma says that proving feasibility of the problem above is equivalent to proving infeasibility of its dual, which is obtained by considering the transpose of the matrix above: Writing these conditions out completely:

A different (but equivalent) linear system is obtained if one uses Taylor series about \(n\Delta t\) rather than \((n-k)\Delta t\) to derive the order conditions. They then read

The method is accurate to order \(p\) if Introducing again \(\delta_j = \alpha_j-r\beta_j\), the order conditions read