Difference between revisions of "Butcher series"
(Importing text file) |
m (ce) |
||
Line 7: | Line 7: | ||
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110705.png" /> is the set of rooted trees, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110706.png" /> is the coefficient for the series associated with the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110707.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110708.png" /> is the elementary differential associated with the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110709.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107010.png" /> is a stepsize or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107011.png" />-increment, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107012.png" />, often called the order of the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107013.png" />, is the number of nodes in the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107014.png" />. All terms will be defined below. For a more thorough discussion of Butcher series, see [[#References|[a1]]] or [[#References|[a2]]]. | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110705.png" /> is the set of rooted trees, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110706.png" /> is the coefficient for the series associated with the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110707.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110708.png" /> is the elementary differential associated with the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b1110709.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107010.png" /> is a stepsize or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107011.png" />-increment, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107012.png" />, often called the order of the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107013.png" />, is the number of nodes in the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107014.png" />. All terms will be defined below. For a more thorough discussion of Butcher series, see [[#References|[a1]]] or [[#References|[a2]]]. | ||
− | ==Definitions | + | ==Definitions== |
A tree is a connected acyclic graph (cf. also [[Graph|Graph]]). A rooted tree is a tree with a distinguished node, called the root (which is drawn at the bottom of the sample trees in the Table). Two rooted trees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107016.png" /> are isomorphic (i.e., equivalent) if and only if there is a [[Bijection|bijection]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107017.png" /> from the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107018.png" /> to the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107020.png" /> maps the root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107021.png" /> to the root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107022.png" /> and any two nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107024.png" /> are connected by an edge in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107025.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107027.png" /> are connected by an edge in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107028.png" />. | A tree is a connected acyclic graph (cf. also [[Graph|Graph]]). A rooted tree is a tree with a distinguished node, called the root (which is drawn at the bottom of the sample trees in the Table). Two rooted trees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107016.png" /> are isomorphic (i.e., equivalent) if and only if there is a [[Bijection|bijection]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107017.png" /> from the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107018.png" /> to the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107020.png" /> maps the root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107021.png" /> to the root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107022.png" /> and any two nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107024.png" /> are connected by an edge in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107025.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107027.png" /> are connected by an edge in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107028.png" />. | ||
− | The following bracket notation for rooted trees is very useful. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107030.png" /> be the trees with zero and one node, respectively. For rooted trees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107031.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107032.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107033.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107034.png" /> be the rooted tree formed by connecting a new root to the roots of each of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107035.png" />. Clearly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107036.png" /> and any rooted tree formed by permuting the subtrees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107037.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107038.png" /> is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107039.png" />. The rooted trees with at most four nodes are displayed in the table below. | + | The following bracket notation for rooted trees is very useful. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107030.png" /> be the trees with zero and one node, respectively. For rooted trees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107031.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107032.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107033.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107034.png" /> be the rooted tree formed by connecting a new root to the roots of each of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107035.png" />. Clearly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107036.png" /> and any rooted tree formed by permuting the subtrees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107037.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107038.png" /> is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107039.png" />. The rooted trees with at most four nodes are displayed in the table below. |
+ | |||
+ | <table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107040.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107041.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111070/b11107042.png" /></td> <td colname="2" style="background-color:white;" colspan="1"> | ||
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" /> | <img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" /> | ||
Line 109: | Line 111: | ||
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> J.C. Butcher, "The numerical analysis of ordinary differential equations" , Wiley (1987)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> E. Hairer, S.P. Nørsett, G. Wanner, "Solving ordinary differential equations I: nonstiff problems" , Springer (1987)</TD></TR></table> | + | <table> |
+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> J.C. Butcher, "The numerical analysis of ordinary differential equations" , Wiley (1987)</TD></TR> | ||
+ | <TR><TD valign="top">[a2]</TD> <TD valign="top"> E. Hairer, S.P. Nørsett, G. Wanner, "Solving ordinary differential equations I: nonstiff problems" , Springer (1987)</TD></TR> | ||
+ | </table> |
Revision as of 20:14, 12 December 2014
B-series
Let be an analytic function satisfying an ordinary differential equation
. A Butcher series for
is a series of the form
![]() |
where is the set of rooted trees,
is the coefficient for the series associated with the tree
,
is the elementary differential associated with the tree
,
is a stepsize or
-increment, and
, often called the order of the tree
, is the number of nodes in the tree
. All terms will be defined below. For a more thorough discussion of Butcher series, see [a1] or [a2].
Definitions
A tree is a connected acyclic graph (cf. also Graph). A rooted tree is a tree with a distinguished node, called the root (which is drawn at the bottom of the sample trees in the Table). Two rooted trees and
are isomorphic (i.e., equivalent) if and only if there is a bijection
from the nodes of
to the nodes of
such that
maps the root of
to the root of
and any two nodes
and
are connected by an edge in
if and only if
and
are connected by an edge in
.
The following bracket notation for rooted trees is very useful. Let and
be the trees with zero and one node, respectively. For rooted trees
with
for
, let
be the rooted tree formed by connecting a new root to the roots of each of
. Clearly,
and any rooted tree formed by permuting the subtrees
of
is isomorphic to
. The rooted trees with at most four nodes are displayed in the table below.
<tbody> </tbody>
|
Using this bracket notation for rooted trees, one can recursively define elementary differentials, as follows. Let
![]() |
and, for with
for
,
![]() |
![]() |
where , the
th derivative of
with respect to
, is a multi-linear mapping.
Since satisfies
, it is not hard to show that
![]() |
where is the
th derivative of
with respect to
,
, and
is the number of distinct ways of labeling the nodes of
with the integers
such that the labels increase as you follow any path from the root to a leaf of
. Consequently, one can write the Taylor series for
as a Butcher series:
![]() | (a1) |
![]() |
The importance of Butcher series stems from their use to derive and to analyze numerical methods for differential equations. For example, consider the -stage Runge–Kutta formula (cf. Runge–Kutta method)
![]() | (a2) |
![]() |
for the ordinary differential equation . Let
be the vector of weights and
the coefficient matrix for (a2). Then it can be shown that
can be written as the Butcher series
![]() | (a3) |
where the coefficients , defined below, depend only on the rooted tree
and the coefficients of the formula (a2).
To define , first let
![]() |
![]() |
and then, for with
for
, define
recursively by
![]() |
where the product of 's in the bracket is taken component-wise. Then
![]() |
![]() |
and, for with
for
,
![]() |
where, again, the product of 's in the bracket is taken componentwise.
Assuming that and that
for all trees
of order
, it follows immediately from (a1) and (a3) that
![]() |
The order of (a2) is the largest such .
References
[a1] | J.C. Butcher, "The numerical analysis of ordinary differential equations" , Wiley (1987) |
[a2] | E. Hairer, S.P. Nørsett, G. Wanner, "Solving ordinary differential equations I: nonstiff problems" , Springer (1987) |
Butcher series. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Butcher_series&oldid=16379