m + category |
ChildofMidnight (talk | contribs) tagging for cleanup. long run-on sentences. poor wording and grammar. needs work. |
||
Line 1: | Line 1: | ||
{{cleanup}} |
|||
In [[mathematics]], the '''Butcher group''', named after the New Zealand mathematician [[John C. Butcher]], is an algebraic formalism involving [[rooted tree]]s that provides [[formal power series]] solutions of the non-linear [[ordinary differential equation]]s modeling the flow of a [[vector field]]. It was [[Arthur Cayley]], prompted by the work of [[James Joseph Sylvester]] on change of variable in [[differential calculus]], who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. In [[numerical analysis]], Butcher's formalism provides a method for analysing solutions of ordinary differential equations by the [[Runge-Kutta method]]. It was later realised that his group and the associated [[Hopf algebra]] of rooted trees underlie the Hopf algebra introduced by [[Dirk Kreimer]] and [[Alain Connes]] in their work on [[renormalization]] in [[quantum field theory]]. |
In [[mathematics]], the '''Butcher group''', named after the New Zealand mathematician [[John C. Butcher]], is an algebraic formalism involving [[rooted tree]]s that provides [[formal power series]] solutions of the non-linear [[ordinary differential equation]]s modeling the flow of a [[vector field]]. It was [[Arthur Cayley]], prompted by the work of [[James Joseph Sylvester]] on change of variable in [[differential calculus]], who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. In [[numerical analysis]], Butcher's formalism provides a method for analysing solutions of ordinary differential equations by the [[Runge-Kutta method]]. It was later realised that his group and the associated [[Hopf algebra]] of rooted trees underlie the Hopf algebra introduced by [[Dirk Kreimer]] and [[Alain Connes]] in their work on [[renormalization]] in [[quantum field theory]]. |
||
Revision as of 15:53, 24 June 2009
You must add a |reason=
parameter to this Cleanup template – replace it with {{Cleanup|reason=<Fill reason here>}}
, or remove the Cleanup template.
In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher, is an algebraic formalism involving rooted trees that provides formal power series solutions of the non-linear ordinary differential equations modeling the flow of a vector field. It was Arthur Cayley, prompted by the work of James Joseph Sylvester on change of variable in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics. In numerical analysis, Butcher's formalism provides a method for analysing solutions of ordinary differential equations by the Runge-Kutta method. It was later realised that his group and the associated Hopf algebra of rooted trees underlie the Hopf algebra introduced by Dirk Kreimer and Alain Connes in their work on renormalization in quantum field theory.
Differentials and rooted trees
A rooted tree is a graph with a distinguished node, called the root, in which every other node is connected to the root by a unique path. If the root of a tree t is removed and the nodes connected to the original node by a single bond are taken as new roots, the tree t breaks up into rooted trees t1, t2, ... Reversing this process a new tree t = [t1, t2, ...] can be constructed by joining the roots of the trees to a new common root. The number of nodes in a tree is denoted by |t|. A heap-ordering of of a rooted tree t is an allocation of the numbers 1 through |t| to the nodes so that the numbers increase on any path going away from the root. The number of heap-orderings on a particular tree is denoted by α(t) and can be computed using the Butcher's formula:
where St denotes the symmetry group of t and the tree factorial is defined recursively by
with the tree factorial of an isolated root defined to be 1
The ordinary differential equation for the flow of a vector field on an open subset U of RN can be written
where x(s) takes values in U, f is a smooth function from U to RN and x0 is the starting point of the flow at time s = 0.
Cayley (1857) gave a method to compute the higher order derivatives xm(s) in terms of rooted trees. His formula can be conveniently expressed using the elementary differentials introduced by Butcher. These are defined inductively by
With this notation
giving the power series expansion
As an example when N = 1, so that x and f are real-valued functions of a single real variable, the formula yields
where the four terms correspond to the four rooted trees from left to right in Figure 3 above.
Hopf algebra of rooted trees
References
- Cayley, Arthur (1857), "On the theory of analytic forms called trees", Philosophical Magazine, XIII: 172–176 (also in Volume 3 of the Collected Works of Cayley, pages 242-246)
- Butcher, J.C (2009), "Trees and numerical methods for ordinary differential equations", Numerical Algorithms, Springer online
- Hairer, E.; Wanner, G. (1974), "On the Butcher group and general multi-value methods", Computing, 13: 1–15
- Grossman, R.; Larson, R. (1989), "Hopf algebraic structures of families of trees" (PDF), Journal Algebra, 26: 184–210
- Connes, Alain; Kreimer, Dirk (1998), "Hopf Algebras, Renormalization and Noncommutative Geometry", Communications in Mathematical Physics, 199: 203–242
- Brouder, Christian (2000), "Runge-Kutta methods and renormalization", Eur.Phys.J., C12: 521–534
- Gracia Bondía, José; Várilly, Joseph C.; Figueroa, Héctor (2000), Elements of noncommutative geometry, Birkhäuser, ISBN 0817641246, Chapter 14.