2

What does the Butcher tableau of a Runge-Kutta method tell me about the method, besides the coefficients in its formulation? In particular, what requirements about it guarantee consistency and therefore convergence? I have been told something necessary is the row-sum condition, i.e.: $$c_i=\sum\limits_{j=1}^na_{ij}.$$ What does this guarantee or what is this necessary for? And could you give me proofs of any results you mention in your answers? Or links to them anyway. Thanks.

Rodrigo de Azevedo
  • 1
MickG
  • 8,645
  • PS I have seen this question, but it only deals with explicit methods, apparently. – MickG Sep 26 '14 at 17:07
  • The requirements are the same between explicit and implicit methods. The last row is a weighted average of the steps and thus their sum has to be equal to 1 in order not to change the results. – John Alexiou May 30 '18 at 18:11
  • Possible duplicate of Requirement(s) for consistency of Runga Kutta methods? – John Alexiou May 30 '18 at 18:14
  • 1
    @ja72 I don't believe the row-sum is in general a necessary condition, rather just a simplification made for derivations. Specifically, it is the C(1) condition as introduced by John Butcher. Decent review here (see Section 2.2 for C(n) conditions): https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20160005923.pdf. This paper, in particular, doesn't satisfy the row-sum conditions: https://epubs.siam.org/doi/pdf/10.1137/0902026 – Ben Southworth Nov 29 '18 at 23:14
  • 1
    @MickG, I realize this is a bit late, but see my answer here: https://math.stackexchange.com/questions/2890426/row-sum-condition-for-runge-kutta-methods/3019409#3019409 – Ben Southworth Nov 29 '18 at 23:49

1 Answers1

0

The Butcher Tableau determines the stability function $R(z)$ of the corresponding method. In particular, for the Linear Test equation due to Dahlquist $$u'(t) = \lambda u(t) \Rightarrow u(t) = u_0 e^{\lambda (t - t_0)}$$

the stability function determines how the approximation $u_{n+1}$ follows from the previous iterate $u_n$:

$$ u_{n+1} = R(z) u_n, \quad z = \lambda \Delta t_{n+1}$$

This stability function can actually be computed as (see for instance [1] or [2])

$$ R(z) = \frac{\text{det}\left(I-zA + z \boldsymbol 1 \boldsymbol b \right) }{\text{det}\left(I-zA\right)}$$ which simplifies for explicit methods with strictly lower triangular matrix $A$ to $$ R(z) =\text{det}\left(I-zA + z \boldsymbol 1 \boldsymbol b \right). $$

This stability function determines (as the name suggests) the region of absolute stability:

$$ z \in \mathbb C, \text{Re}(z): \vert R(z) \vert \leq 1. $$

Reason I mention this is that convergence is not guaranteed for convergent methods - the method has also to be a stable for the employed finite timesteps $\Delta t$.

For explicit methods, $R(z)$ is actually a polynomial

$$ R(z) = \sum_{j=0}^S \alpha_j z^j$$ and one can directly check the order of consistency by checking to what power the coefficients $\alpha_j$ agree with the terms of the exponential, i.e., $$ \alpha_j = \frac{1}{j!}, j = 0, \dots , p.$$

For implicit methods, however, the order of consistency cannot be that easily read-off from $R(z)$.

Dan Doe
  • 2,229