Transcription
Runge–Kutta methods forordinary differential equationsJohn ButcherThe University of AucklandNew ZealandCOE Workshop on Numerical AnalysisKyushu UniversityMay 2005Runge–Kutta methods for ordinary differential equations – p. 1/48
ContentsIntroduction to Runge–Kutta methodsRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsOrder barriersRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsOrder barriersAlgebraic interpretationRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsOrder barriersAlgebraic interpretationEffective orderRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsOrder barriersAlgebraic interpretationEffective orderImplicit Runge–Kutta methodsRunge–Kutta methods for ordinary differential equations – p. 2/48
ContentsIntroduction to Runge–Kutta methodsFormulation of methodTaylor expansion of exact solutionTaylor expansion for numerical approximationOrder conditionsConstruction of low order explicit methodsOrder barriersAlgebraic interpretationEffective orderImplicit Runge–Kutta methodsSingly-implicit methodsRunge–Kutta methods for ordinary differential equations – p. 2/48
Introduction to Runge–Kutta methodsIt will be convenient to consider only autonomous initialvalue problemsy 0 (x) f (y(x)),y(x0 ) y0 ,f : R N RN .Runge–Kutta methods for ordinary differential equations – p. 3/48
Introduction to Runge–Kutta methodsIt will be convenient to consider only autonomous initialvalue problemsy 0 (x) f (y(x)),y(x0 ) y0 ,f : R N RN .The simple Euler method:yn yn 1 hf (yn 1 ),h xn xn 1can be made more accurate by usingthe mid-pointquadrature formula: 1yn yn 1 hf yn 1 2 hf (yn 1 ) .Runge–Kutta methods for ordinary differential equations – p. 3/48
Introduction to Runge–Kutta methodsIt will be convenient to consider only autonomous initialvalue problemsy 0 (x) f (y(x)),y(x0 ) y0 ,f : R N RN .The simple Euler method:yn yn 1 hf (yn 1 ),h xn xn 1can be made more accurate by using either the mid-pointor the trapezoidal rule quadrature formula: 1yn yn 1 hf yn 1 2 hf (yn 1 ) . 11yn yn 1 2 hf (yn 1 ) 2 hf yn 1 hf (yn 1 ) .Runge–Kutta methods for ordinary differential equations – p. 3/48
These methods from Runge’s 1895 paper are “secondorder” because the error in a single step behaves likeO(h3 ).Runge–Kutta methods for ordinary differential equations – p. 4/48
These methods from Runge’s 1895 paper are “secondorder” because the error in a single step behaves likeO(h3 ).A few years later, Heun gave a full explanation of order 3methods and Kutta gave a detailed analysis of order 4methods.Runge–Kutta methods for ordinary differential equations – p. 4/48
These methods from Runge’s 1895 paper are “secondorder” because the error in a single step behaves likeO(h3 ).A few years later, Heun gave a full explanation of order 3methods and Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aimseemed to be to find explicit methods of higher andhigher order.Runge–Kutta methods for ordinary differential equations – p. 4/48
These methods from Runge’s 1895 paper are “secondorder” because the error in a single step behaves likeO(h3 ).A few years later, Heun gave a full explanation of order 3methods and Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aimseemed to be to find explicit methods of higher andhigher order.Later the aim shifted to finding methods that seemed tobe optimal in terms of local truncation error and tofinding built-in error estimators.Runge–Kutta methods for ordinary differential equations – p. 4/48
With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Runge–Kutta methods for ordinary differential equations – p. 5/48
With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Methods have been found based on Gaussian quadrature.Runge–Kutta methods for ordinary differential equations – p. 5/48
With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Methods have been found based on Gaussian quadrature.Later this extended to methods related to Radau andLobatto quadrature.Runge–Kutta methods for ordinary differential equations – p. 5/48
With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Methods have been found based on Gaussian quadrature.Later this extended to methods related to Radau andLobatto quadrature.A-stable methods exist in these classes.Runge–Kutta methods for ordinary differential equations – p. 5/48
With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Methods have been found based on Gaussian quadrature.Later this extended to methods related to Radau andLobatto quadrature.A-stable methods exist in these classes.Because of the high cost of these methods, attentionmoved to diagonally and singly implicit methods.Runge–Kutta methods for ordinary differential equations – p. 5/48
Formulation of methodIn carrying out a step we evaluate s stage valuesY1 ,Y2 ,.,Ysand s stage derivativesF1 , F 2 ,.,Fs ,using the formula Fi f (Yi ).Runge–Kutta methods for ordinary differential equations – p. 6/48
Formulation of methodIn carrying out a step we evaluate s stage valuesY1 ,Y2 ,.,Ysand s stage derivativesF1 , F 2 ,.,Fs ,using the formula Fi f (Yi ).Each Yi is found as a linear combination of the Fj addedon to y0 :sXaij FjYi y 0 hj 1Runge–Kutta methods for ordinary differential equations – p. 6/48
Formulation of methodIn carrying out a step we evaluate s stage valuesY1 ,Y2 ,.,Ysand s stage derivativesF1 , F 2 ,.,Fs ,using the formula Fi f (Yi ).Each Yi is found as a linear combination of the Fj addedon to y0 :sXaij FjYi y 0 hj 1and the approximation at x1 x0 h is found fromsXb i Fiy1 y0 hi 1Runge–Kutta methods for ordinary differential equations – p. 6/48
We represent the method by a tableau:c1 a11c2 a21. . .cs as1b1a12a22.as2b2· · · a1s· · · a2s.· · · ass· · · bsRunge–Kutta methods for ordinary differential equations – p. 7/48
We represent the method by a tableau:c1 a11c2 a21. . .cs as1b1a12a22.as2b2· · · a1s· · · a2s.· · · ass· · · bsor, if the method is explicit, by the simplified tableau0c2 a21. . . . . .cs as1 as2 · · · as,s 1b1 b2 · · · bs 1 bsRunge–Kutta methods for ordinary differential equations – p. 7/48
Examples: 1y1 y0 0hf (y0 ) 1hf y0 2 hf (y0 )012120 1Runge–Kutta methods for ordinary differential equations – p. 8/48
Examples: 1y1 y0 0hf (y0 ) 1hf y0 2 hf (y0 )Y101212Y20 1Runge–Kutta methods for ordinary differential equations – p. 8/48
Examples: 1y1 y0 0hf (y0 ) 1hf y0 2 hf (y0 )0Y112Y2120 1y1 y0 1hf (y0 )2 1hf2y0 1hf (y0 )01 112 12Runge–Kutta methods for ordinary differential equations – p. 8/48
Examples: 1y1 y0 0hf (y0 ) 1hf y0 2 hf (y0 )0Y112Y2120 1y1 y0 Y11hf (y0 )2 1hf2y0 1hf (y0 )01 112 Y212Runge–Kutta methods for ordinary differential equations – p. 8/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))y 00 (x) f 0 (y(x))y 0 (x) f 0 (y(x))f (y(x)))Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))y 00 (x) f 0 (y(x))y 0 (x) f 0 (y(x))f (y(x)))y 000 (x) f 00 (y(x))(f (y(x)), y 0 (x)) f 0 (y(x))f 0 (y(x))y 0 (x) f 00 (y(x))(f (y(x)), f (y(x))) f 0 (y(x))f 0 (y(x))f (y(x))Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))y 00 (x) f 0 (y(x))y 0 (x) f 0 (y(x))f (y(x)))y 000 (x) f 00 (y(x))(f (y(x)), y 0 (x)) f 0 (y(x))f 0 (y(x))y 0 (x) f 00 (y(x))(f (y(x)), f (y(x))) f 0 (y(x))f 0 (y(x))f (y(x))This will become increasingly complicated as weevaluate higher derivatives.Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))y 00 (x) f 0 (y(x))y 0 (x) f 0 (y(x))f (y(x)))y 000 (x) f 00 (y(x))(f (y(x)), y 0 (x)) f 0 (y(x))f 0 (y(x))y 0 (x) f 00 (y(x))(f (y(x)), f (y(x))) f 0 (y(x))f 0 (y(x))f (y(x))This will become increasingly complicated as weevaluate higher derivatives.Hence we look for a systematic pattern.Runge–Kutta methods for ordinary differential equations – p. 9/48
Taylor expansion of exact solutionWe need formulae for the second, third, . . . , derivatives.y 0 (x) f (y(x))y 00 (x) f 0 (y(x))y 0 (x) f 0 (y(x))f (y(x)))y 000 (x) f 00 (y(x))(f (y(x)), y 0 (x)) f 0 (y(x))f 0 (y(x))y 0 (x) f 00 (y(x))(f (y(x)), f (y(x))) f 0 (y(x))f 0 (y(x))f (y(x))This will become increasingly complicated as weevaluate higher derivatives.Hence we look for a systematic pattern.Write f f (y(x)), f0 f 0 (y(x)), f00 f 00 (y(x)), . . . .Runge–Kutta methods for ordinary differential equations – p. 9/48
y 0 (x) ff000ff000000y (x) f fy (x) f (f, f) f0 f0 ffff00ff0f0Runge–Kutta methods for ordinary differential equations – p. 10/48
y 0 (x) ff000ff000000y (x) f fy (x) f (f, f) f0 f0 ffff00ff0f0The various terms have a structure related to rooted-trees.Runge–Kutta methods for ordinary differential equations – p. 10/48
y 0 (x) ff000ff000000y (x) f fy (x) f (f, f) f0 f0 ffff00ff0f0The various terms have a structure related to rooted-trees.Hence, we introduce the set of all rooted trees and somefunctions on this set.Runge–Kutta methods for ordinary differential equations – p. 10/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .Runge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treeRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupγ(t)density of tRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupγ(t)density of tα(t)number of ways of labelling with an ordered setRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupγ(t)density of tα(t)number of ways of labelling with an ordered setβ(t)number of ways of labelling with an unordered setRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupγ(t)density of tα(t)number of ways of labelling with an ordered setβ(t)number of ways of labelling with an unordered setF (t)(y0 ) elementary differentialRunge–Kutta methods for ordinary differential equations – p. 11/48
Let T denote the set of rooted trees:nT ,,,,,,,,.oWe identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesσ(t)symmetry of t order of automorphism groupγ(t)density of tα(t)number of ways of labelling with an ordered setβ(t)number of ways of labelling with an unordered setF (t)(y0 ) elementary differentialWe will give examples of these functions based on t Runge–Kutta methods for ordinary differential equations – p. 11/48
t Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 4r(t) 7567Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 4r(t) 7567σ(t) 8Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 4r(t) 7567σ(t) 81 11 1γ(t) 63337Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 45r(t) 767σ(t) 81 11 13γ(t) 63α(t) r(t)!σ(t)γ(t)37 10Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 45r(t) 767σ(t) 81 11 13γ(t) 6337α(t) r(t)!σ(t)γ(t) 10β(t) r(t)!σ(t) 630Runge–Kutta methods for ordinary differential equations – p. 12/48
t 1 23 45r(t) 767σ(t) 81 11 13γ(t) 637α(t) r(t)!σ(t)γ(t) 10β(t) r(t)!σ(t) 6300030000F (t) f f (f, f), f (f, f) f f f ff00f00f00Runge–Kutta methods for ordinary differential equations – p. 12/48
These functions are easy to compute up to order 4 trees:tr(t) 1 2334444σ(t) 1 1216121γ(t) 1 236481224α(t) 1 1111311β(t) 1 2364241224F (t) f f0 f f00 (f, f) f0 f0 f f(3) (f, f, f) f00 (f, f0 f) f0 f00 (f, f) f0 f0 f0 fRunge–Kutta methods for ordinary differential equations – p. 13/48
The formal Taylor expansion of the solution at x0 h isy(x0 h) y0 X α(t)hr(t)t Tr(t)!F (t)(y0 )Runge–Kutta methods for ordinary differential equations – p. 14/48
The formal Taylor expansion of the solution at x0 h isy(x0 h) y0 X α(t)hr(t)t Tr(t)!F (t)(y0 )Using the known formula for α(t), we can write this asy(x0 h) y0 Xt Thr(t)F (t)(y0 )σ(t)γ(t)Runge–Kutta methods for ordinary differential equations – p. 14/48
The formal Taylor expansion of the solution at x0 h isy(x0 h) y0 X α(t)hr(t)t Tr(t)!F (t)(y0 )Using the known formula for α(t), we can write this asy(x0 h) y0 Xt Thr(t)F (t)(y0 )σ(t)γ(t)Our aim will now be to find a corresponding formula forthe result computed by one step of a Runge-Kuttamethod.Runge–Kutta methods for ordinary differential equations – p. 14/48
The formal Taylor expansion of the solution at x0 h isy(x0 h) y0 X α(t)hr(t)t Tr(t)!F (t)(y0 )Using the known formula for α(t), we can write this asy(x0 h) y0 Xt Thr(t)F (t)(y0 )σ(t)γ(t)Our aim will now be to find a corresponding formula forthe result computed by one step of a Runge-Kuttamethod.By comparing these formulae term by term, we willobtain conditions for a specific order of accuracy.Runge–Kutta methods for ordinary differential equations – p. 14/48
Taylor expansion for numerical approximationWe need to evaluate various expressions which dependon the tableau for a particular method.Runge–Kutta methods for ordinary differential equations – p. 15/48
Taylor expansion for numerical approximationWe need to evaluate various expressions which dependon the tableau for a particular method.These are known as “elementary weights”.Runge–Kutta methods for ordinary differential equations – p. 15/48
Taylor expansion for numerical approximationWe need to evaluate various expressions which dependon the tableau for a particular method.These are known as “elementary weights”.We use the example tree we have already considered toillustrate the construction of the elementary weight Φ(t).lt m njokiRunge–Kutta methods for ordinary differential equations – p. 15/48
Taylor expansion for numerical approximationWe need to evaluate various expressions which dependon the tableau for a particular method.These are known as “elementary weights”.We use the example tree we have already considered toillustrate the construction of the elementary weight Φ(t).lt Φ(t) sXm njokibi aij aik ajl ajmaknakoi,j,k,l,m,n,o 1Runge–Kutta methods for ordinary differential equations – p. 15/48
Taylor expansion for numerical approximationWe need to evaluate various expressions which dependon the tableau for a particular method.These are known as “elementary weights”.We use the example tree we have already considered toillustrate the construction of the elementary weight Φ(t).lt Φ(t) m njsXokibi aij aik ajl ajmaknakoi,j,k,l,m,n,o 1Simplify by summing over l, m, n, o:Φ(t) sX22biaij cj aik cki,j,k 1Runge–Kutta methods for ordinary differential equations – p. 15/48
Now add Φ(t) to the table of functions:tr(t)α(t)β(t)Φ(t)111Pbi212Pbi ci313P 2bi ci316Pbi aij cjtr(t)4444α(t)13114241224β(t)P 3 PPP2Φ(t)bi cibi ci aij cjbi aij cjbi aij ajk ckRunge–Kutta methods for ordinary differential equations – p. 16/48
The formal Taylor expansion of the solution at x0 h isy1 y0 X β(t)hr(t)t Tr(t)!Φ(t)F (t)(y0 )Runge–Kutta methods for ordinary differential equations – p. 17/48
The formal Taylor expansion of the solution at x0 h isy1 y0 X β(t)hr(t)t Tr(t)!Φ(t)F (t)(y0 )Using the known formula for β(t), we can write this asy1 y 0 X hr(t)t Tσ(t)Φ(t)F (t)(y0 )Runge–Kutta methods for ordinary differential equations – p. 17/48
Order conditionsTo match the Taylor seriesX hr(t)F (t)(y0 )y(x0 h) y0 σ(t)γ(t)t Ty1 y0 X hr(t)t Tσ(t)Φ(t)F (t)(y0 )up to hp terms we need to ensure that1,Φ(t) γ(t)Runge–Kutta methods for ordinary differential equations – p. 18/48
Order conditionsTo match the Taylor seriesX hr(t)F (t)(y0 )y(x0 h) y0 σ(t)γ(t)t Ty1 y0 X hr(t)t Tσ(t)Φ(t)F (t)(y0 )up to hp terms we need to ensure thatfor all trees such that1,Φ(t) γ(t)r(t) p.Runge–Kutta methods for ordinary differential equations – p. 18/48
Order conditionsTo match the Taylor seriesX hr(t)F (t)(y0 )y(x0 h) y0 σ(t)γ(t)t Ty1 y0 X hr(t)t Tσ(t)Φ(t)F (t)(y0 )up to hp terms we need to ensure thatfor all trees such that1,Φ(t) γ(t)r(t) p.These are the “order conditions”.Runge–Kutta methods for ordinary differential equations – p. 18/48
Construction of low order explicit methodsWe will attempt to construct methods of order p s withs stages for s 1, 2, . . . .Runge–Kutta methods for ordinary differential equations – p. 19/48
Construction of low order explicit methodsWe will attempt to construct methods of order p s withs stages for s 1, 2, . . . .We will find that this is possible up to order 4 but not forp 5.Runge–Kutta methods for ordinary differential equations – p. 19/48
Construction of low order explicit methodsWe will attempt to construct methods of order p s withs stages for s 1, 2, . . . .We will find that this is possible up to order 4 but not forp 5.The usual approach will be to first choose c2 , c3 , . . . , csand then solve for b1 , b2 , . . . , bs .Runge–Kutta methods for ordinary differential equations – p. 19/48
Construction of low order explicit methodsWe will attempt to construct methods of order p s withs stages for s 1, 2, . . . .We will find that this is possible up to order 4 but not forp 5.The usual approach will be to first choose c2 , c3 , . . . , csand then solve for b1 , b2 , . . . , bs .After this solve for those of the aij which can be found assolutions to linear equations.Runge–Kutta methods for ordinary differential equations – p. 19/48
Construction of low order explicit methodsWe will attempt to construct methods of order p s withs stages for s 1, 2, . . . .We will find that this is possible up to order 4 but not forp 5.The usual approach will be to first choose c2 , c3 , . . . , csand then solve for b1 , b2 , . . . , bs .After this solve for those of the aij which can be found assolutions to linear equations.b1 b 2 1Order 2:b2 c2 120c20c21 2c1212c212120 101 11212Runge–Kutta methods for ordinary differential equations – p. 19/48
Order 3:b1 b 2 b 3b2 c2 b 3 c3b2 c22 b3 c23b3 a32 c2 1 12 13 16Runge–Kutta methods for ordinary differential equations – p. 20/48
b1 b 2 b 3b2 c2 b 3 c3b2 c22 b3 c23b3 a32 c2Order 3:012 1 12 13 160121 1 2162316232302301423382338230 1 10 3414Runge–Kutta methods for ordinary differential equations – p. 20/48
b1 b 2 b 3 b 4b2 c2 b 3 c3 b 4 c4b2 c22 b3 c23 b4 c24b3 a32 c2 b4 a42 c2 b4 a43 c3b2 c32 b3 c33 b4 c34b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3222b3 a32 c2 b4 a42 c2 b4 a43 c3b4 a43 a32 c2Order 4: 1 12 13 16 14 181 121 24(1)(2)(3)(4)(5)(6)(7)(8)Runge–Kutta methods for ordinary differential equations – p. 21/48
b1 b 2 b 3 b 4 1(1)(2)b2 c2 b3 c3 b4 c4 12(3)b2 c22 b3 c23 b4 c24 13b3 a32 c2 b4 a42 c2 b4 a43 c3 16(4)b2 c32 b3 c33 b4 c34 14(5)b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3 18(6)2221b3 a32 c2 b4 a42 c2 b4 a43 c3 12(7)1b4 a43 a32 c2 24(8)To solve these equations, treat c2 , c3 , c4 as parameters,and solve for b1 , b2 , b3 , b4 from (1), (2), (3), (5).Order 4:Runge–Kutta methods for ordinary differential equations – p. 21/48
b1 b 2 b 3 b 4 1(1)(2)b2 c2 b3 c3 b4 c4 12(3)b2 c22 b3 c23 b4 c24 13b3 a32 c2 b4 a42 c2 b4 a43 c3 16(4)b2 c32 b3 c33 b4 c34 14(5)b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3 18(6)2221b3 a32 c2 b4 a42 c2 b4 a43 c3 12(7)1b4 a43 a32 c2 24(8)To solve these equations, treat c2 , c3 , c4 as parameters,and solve for b1 , b2 , b3 , b4 from (1), (2), (3), (5).Now solve for a32 , a42 , a43 from (4). (6), (7).Order 4:Runge–Kutta methods for ordinary differential equations – p. 21/48
b1 b 2 b 3 b 4 1(1)(2)b2 c2 b3 c3 b4 c4 12(3)b2 c22 b3 c23 b4 c24 13b3 a32 c2 b4 a42 c2 b4 a43 c3 16(4)b2 c32 b3 c33 b4 c34 14(5)b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3 18(6)2221b3 a32 c2 b4 a42 c2 b4 a43 c3 12(7)1b4 a43 a32 c2 24(8)To solve these equations, treat c2 , c3 , c4 as parameters,and solve for b1 , b2 , b3 , b4 from (1), (2), (3), (5).Now solve for a32 , a42 , a43 from (4). (6), (7).Use (8) to obtain consistency condition on c2 , c3 , c4 .Order 4:Runge–Kutta methods for ordinary differential equations – p. 21/48
b1 b 2 b 3 b 4 1(1)(2)b2 c2 b3 c3 b4 c4 12(3)b2 c22 b3 c23 b4 c24 13b3 a32 c2 b4 a42 c2 b4 a43 c3 16(4)b2 c32 b3 c33 b4 c34 14(5)b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3 18(6)2221b3 a32 c2 b4 a42 c2 b4 a43 c3 12(7)1b4 a43 a32 c2 24(8)To solve these equations, treat c2 , c3 , c4 as parameters,and solve for b1 , b2 , b3 , b4 from (1), (2), (3), (5).Now solve for a32 , a42 , a43 from (4). (6), (7).Use (8) to obtain consistency condition on c2 , c3 , c4 .Result: c4 1.Order 4:Runge–Kutta methods for ordinary differential equations – p. 21/48
We will prove a stronger result in another way.Runge–Kutta methods for ordinary differential equations – p. 22/48
We will prove a stronger result in another way.Lemma 1 Let U and V be 3 3 matrices such that w11 w12 0w11 w12 U V w21 w22 0 whereis non-singularw21 w2200 0then either the last row of U is zero or the last column ofV is zero.Runge–Kutta methods for ordinary differential equations – p. 22/48
We will prove a stronger result in another way.Lemma 1 Let U and V be 3 3 matrices such that w11 w12 0w11 w12 U V w21 w22 0 whereis non-singularw21 w2200 0then either the last row of U is zero or the last column ofV is zero.Proof Let W U V . Either U or V is singular. If U is singular, letx be a non-zero vector such that xT U 0. Therefore xT W 0.Therefore the first two components of x are zero. Hence, the last rowof U is zero. The second case follows similarly if V is singular.Runge–Kutta methods for ordinary differential equations – p. 22/48
We will prove a stronger result in another way.Lemma 1 Let U and V be 3 3 matrices such that w11 w12 0w11 w12 U V w21 w22 0 whereis non-singularw21 w2200 0then either the last row of U is zero or the last column ofV is zero.Proof Let W U V . Either U or V is singular. If U is singular, letx be a non-zero vector such that xT U 0. Therefore xT W 0.Therefore the first two components of x are zero. Hence, the last rowof U is zero. The second case follows similarly if V is singular.We will apply this result with a specific choice of U andV.Runge–Kutta methods for ordinary differential equations – p. 22/48
Let b2 b2 c2 PU i bi ai2 b2 (1 c2 )b3bcP 3 3i bi ai3 b3 (1 c3 ) b4 b4 c4 P bai i i4 b4 (1 c4 )Runge–Kutta methods for ordinary differential equations – p. 23/48
Let b2b3b4 bcbcbc2 23 34 4 PPPU bababai i i2i i i3i i i4 b2 (1 c2 ) b3 (1 c3 ) b4 (1 c4 )P 1 2 2c2 c2a2j cj 2 c2jP1 2 2ac c3V c3 c33j jj2P1 22c4 c4ac j 4j j2 c4Runge–Kutta methods for ordinary differential equations – p. 23/48
Let b2b3b4 bcbcbc2 23 34 4 PPPU bababai i i2i i i3i i i4 b2 (1 c2 ) b3 (1 c3 ) b4 (1 c4 )P 1 2 2c2 c2a2j cj 2 c2jP1 2 2ac c3V c3 c33j jj2P1 22c4 c4ac j 4j j2 c4then 1 12 3 0U V 13 41 0 0 0 0Runge–Kutta methods for ordinary differential equations – p. 23/48
It follows that b4 0, c2 0 or c4 1.Runge–Kutta methods for ordinary differential equations – p. 24/48
It follows that b4 0, c2 0 or c4 1.The first two options are impossible because1b4 a43 a32 c2 24.Runge–Kutta methods for ordinary differential equations – p. 24/48
It follows that b4 0, c2 0 or c4 1.The first two options are impossible because1b4 a43 a32 c2 24.Hence, c4 1 and the last row of U is zero.Runge–Kutta methods for ordinary differential equations – p. 24/48
It follows that b4 0, c2 0 or c4 1.The first two options are impossible because1b4 a43 a32 c2 24.Hence, c4 1 and the last row of U is zero.The construction of fourth order Runge–Kutta methodsnow becomes straightforward.Runge–Kutta methods for ordinary differential equations – p. 24/48
It follows that b4 0, c2 0 or c4 1.The first two options are impossible because1b4 a43 a32 c2 24.Hence, c4 1 and the last row of U is zero.The construction of fourth order Runge–Kutta methodsnow becomes straightforward.Kutta classified all solutions to the fourth orderconditions.Runge–Kutta methods for ordinary differential equations – p. 24/48
It follows that b4 0, c2 0 or c4 1.The first two options are impossible because1b4 a43 a32 c2 24.Hence, c4 1 and the last row of U is zero.The construction of fourth order Runge–Kutta methodsnow becomes straightforward.Kutta classified all solutions to the fourth orderconditions.In particular we have his famous method:01212120 121 0 0 116131316Runge–Kutta methods for ordinary differential equations – p. 24/48
Order barriersWe will review what is achievable up to order 8.Runge–Kutta methods for ordinary differential equations – p. 25/48
Order barriersWe will review what is achievable up to order 8.In the table below, Np is the number of order conditionsto achieve this order.Runge–Kutta methods for ordinary differential equations – p. 25/48
Order barriersWe will review what is achievable up to order 8.In the table below, Np is the number of order conditionsto achieve this order.Ms s(s 1)/2 is the number of free parameters tosatisfy the order conditions for the required s stages.Runge–Kutta methods for or
Contents Introduction to Runge-Kutta methods Formulation of method Taylor expansion of exact solution Taylor expansion for numerical approximation
