Transcription
IntroductionFormulationTaylor series: exact solutionApproximationJohn Butcher’s tutorialsIntroduction to Runge–Kutta methodsΦ(t) 1γ(t)Introduction to Runge–Kutta methodsOrder conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsIntroductionIt will be convenient to consider only autonomous initial valueproblemsy ′ (x) f (y(x)),f :RNy(x0 ) y0 ,N R .The Euler method is the simplest way of obtaining numericalapproximations atx1 x0 h,x2 x1 h, . . .using the formulayn yn 1 hf (yn 1 ), h xn xn 1 , n 1, 2, . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsIntroductionIt will be convenient to consider only autonomous initial valueproblemsy ′ (x) f (y(x)),f :RNy(x0 ) y0 ,N R .The Euler method is the simplest way of obtaining numericalapproximations atx1 x0 h,x2 x1 h, . . .using the formulayn yn 1 hf (yn 1 ), h xn xn 1 , n 1, 2, . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsIntroductionIt will be convenient to consider only autonomous initial valueproblemsy ′ (x) f (y(x)),f :RNy(x0 ) y0 ,N R .The Euler method is the simplest way of obtaining numericalapproximations atx1 x0 h,x2 x1 h, . . .using the formulayn yn 1 hf (yn 1 ), h xn xn 1 , n 1, 2, . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThis method can be made more accurate by using either themid-point quadrature formula yn yn 1 hf yn 1 12 hf (yn 1 ) .or the trapezoidal rule quadrature formula: yn yn 1 12 hf (yn 1 ) 12 hf yn 1 hf (yn 1 ) .These methods from Runge’s 1895 paper are “second order”because the error in a single step behaves like O(h3 ).This is in contrast to the first order Euler method where theorder behaviour is O(h2 ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThis method can be made more accurate by using either themid-point quadrature formula yn yn 1 hf yn 1 12 hf (yn 1 ) .or the trapezoidal rule quadrature formula: yn yn 1 12 hf (yn 1 ) 12 hf yn 1 hf (yn 1 ) .These methods from Runge’s 1895 paper are “second order”because the error in a single step behaves like O(h3 ).This is in contrast to the first order Euler method where theorder behaviour is O(h2 ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThis method can be made more accurate by using either themid-point quadrature formula yn yn 1 hf yn 1 12 hf (yn 1 ) .or the trapezoidal rule quadrature formula: yn yn 1 12 hf (yn 1 ) 12 hf yn 1 hf (yn 1 ) .These methods from Runge’s 1895 paper are “second order”because the error in a single step behaves like O(h3 ).This is in contrast to the first order Euler method where theorder behaviour is O(h2 ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThis method can be made more accurate by using either themid-point quadrature formula yn yn 1 hf yn 1 12 hf (yn 1 ) .or the trapezoidal rule quadrature formula: yn yn 1 12 hf (yn 1 ) 12 hf yn 1 hf (yn 1 ) .These methods from Runge’s 1895 paper are “second order”because the error in a single step behaves like O(h3 ).This is in contrast to the first order Euler method where theorder behaviour is O(h2 ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsA few years later, Heun gave a full explanation of order 3methods.Shortly afterwards Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aim seemed tobe to find explicit methods of higher and higher order.Later the aim shifted to finding methods that seemed to beoptimal in terms of local truncation error and to finding built-inerror estimators.With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsA few years later, Heun gave a full explanation of order 3methods.Shortly afterwards Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aim seemed tobe to find explicit methods of higher and higher order.Later the aim shifted to finding methods that seemed to beoptimal in terms of local truncation error and to finding built-inerror estimators.With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsA few years later, Heun gave a full explanation of order 3methods.Shortly afterwards Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aim seemed tobe to find explicit methods of higher and higher order.Later the aim shifted to finding methods that seemed to beoptimal in terms of local truncation error and to finding built-inerror estimators.With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsA few years later, Heun gave a full explanation of order 3methods.Shortly afterwards Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aim seemed tobe to find explicit methods of higher and higher order.Later the aim shifted to finding methods that seemed to beoptimal in terms of local truncation error and to finding built-inerror estimators.With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsA few years later, Heun gave a full explanation of order 3methods.Shortly afterwards Kutta gave a detailed analysis of order 4methods.In the early days of Runge–Kutta methods the aim seemed tobe to find explicit methods of higher and higher order.Later the aim shifted to finding methods that seemed to beoptimal in terms of local truncation error and to finding built-inerror estimators.With the emergence of stiff problems as an importantapplication area, attention moved to implicit methods.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsFormulation of Runge–Kutta methodsIn carrying out a step we evaluate s stage valuesY1 ,and s stage derivativesY2 ,.,YsF1 ,F2 ,. ,Fs ,using the formula Fi f (Yi ).Each Yi is defined as a linear combination of the Fj added on toy0 :sXaij Fj , i 1, 2, . . . , s,Yi y 0 hj 1and the approximation at x1 x0 h is found fromsXbi Fi .y1 y0 hi 1Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsFormulation of Runge–Kutta methodsIn carrying out a step we evaluate s stage valuesY1 ,and s stage derivativesY2 ,.,YsF1 ,F2 ,. ,Fs ,using the formula Fi f (Yi ).Each Yi is defined as a linear combination of the Fj added on toy0 :sXaij Fj , i 1, 2, . . . , s,Yi y 0 hj 1and the approximation at x1 x0 h is found fromsXbi Fi .y1 y0 hi 1Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsWe represent the method by a tableau:c1 a11 a12c2 a21 a22.cs as1 as2b1 b2······a1sa2s.······assbsor, if the method is explicit, by the simplified tableau0c2 a21.cs as1 as2 · · ·b1 b2 · · ·as,s 1bs 1 bsPIn each case, ci (i 1, 2, . . . ) is defined as sj 1 aij . The valueof ci indicates the point Xi x0 hci for which Yi is a goodapproximation to y(Xi ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsWe represent the method by a tableau:c1 a11 a12c2 a21 a22.cs as1 as2b1 b2······a1sa2s.······assbsor, if the method is explicit, by the simplified tableau0c2 a21.cs as1 as2 · · ·b1 b2 · · ·as,s 1bs 1 bsPIn each case, ci (i 1, 2, . . . ) is defined as sj 1 aij . The valueof ci indicates the point Xi x0 hci for which Yi is a goodapproximation to y(Xi ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsWe represent the method by a tableau:c1 a11 a12c2 a21 a22.cs as1 as2b1 b2······a1sa2s.······assbsor, if the method is explicit, by the simplified tableau0c2 a21.cs as1 as2 · · ·b1 b2 · · ·as,s 1bs 1 bsPIn each case, ci (i 1, 2, . . . ) is defined as sj 1 aij . The valueof ci indicates the point Xi x0 hci for which Yi is a goodapproximation to y(Xi ).Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionExamples: y1 y0 0hf (y0 ) 1hf y0 12 hf (y0 )012120 1Introduction to Runge–Kutta methodsApproximationOrder conditions
IntroductionFormulationTaylor series: exact solutionExamples: y1 y0 0hf (y0 ) 1hf y0 12 hf (y0 )0Y112120 1Introduction to Runge–Kutta methodsY2ApproximationOrder conditions
IntroductionFormulationTaylor series: exact solutionExamples: y1 y0 0hf (y0 ) 1hf y0 12 hf (y0 )0Y11212Y20 1 y1 y0 12 hf (y0 ) 12 hf y0 1hf (y0 )01 112Introduction to Runge–Kutta methods12ApproximationOrder conditions
IntroductionFormulationTaylor series: exact solutionExamples: y1 y0 0hf (y0 ) 1hf y0 12 hf (y0 )0Y11212Y20 1 y1 y0 12 hf (y0 ) 12 hf y0 1hf (y0 )Y1Introduction to Runge–Kutta methods01 11212Y2ApproximationOrder conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of exact solutionWe need formulae for the second, third, . . . , derivatives.y ′ (x) f (y(x))y ′′ (x) f ′ (y(x))y ′ (x) f ′ (y(x))f (y(x))y ′′′ (x) f ′′(y(x))(f (y(x)), y ′ (x)) f ′(y(x))f ′(y(x))y ′ (x) f ′′ (y(x))(f (y(x)), f (y(x))) f ′ (y(x))f ′ (y(x))f (y(x))This will become increasingly complicated as we evaluate higherderivatives.Hence we look for a systematic pattern.Write f f (y(x)), f′ f ′ (y(x)), f′′ f ′′ (y(x)), . . . .Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationy ′ (x) ffy ′′ (x) f′ fff′y ′′′ (x) f′′ (f, f) f′ f′ ffOrder conditionsf′′fff′f′The various terms have a structure related to rooted-trees.Hence, we introduce the set of all rooted trees and somefunctions on this set.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationy ′ (x) ffy ′′ (x) f′ fff′y ′′′ (x) f′′ (f, f) f′ f′ ffOrder conditionsf′′fff′f′The various terms have a structure related to rooted-trees.Hence, we introduce the set of all rooted trees and somefunctions on this set.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationy ′ (x) ffy ′′ (x) f′ fff′y ′′′ (x) f′′ (f, f) f′ f′ ffOrder conditionsf′′fff′f′The various terms have a structure related to rooted-trees.Hence, we introduce the set of all rooted trees and somefunctions on this set.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,We identify the following functions on T .Introduction to Runge–Kutta methodsApproximation,, .oOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,We identify the following functions on T .In this table, t will denote a typical treeIntroduction to Runge–Kutta methodsApproximation,, .oOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,We identify the following functions on T .In this table, t will denote a typical treer(t)order of t number of verticesIntroduction to Runge–Kutta methodsApproximation,, .oOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .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 groupIntroduction to Runge–Kutta methodsOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .oWe identify the following functions on T .In thisr(t)σ(t)γ(t)table, t will denote a typical treeorder of t number of verticessymmetry of t order of automorphism groupdensity of tIntroduction to Runge–Kutta methodsOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .oWe identify the following functions on T .In thisr(t)σ(t)γ(t)α(t)table, t will denote a typical treeorder of t number of verticessymmetry of t order of automorphism groupdensity of tnumber of ways of labelling with an ordered setIntroduction to Runge–Kutta methodsOrder conditions
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .Order conditionsoWe identify the following functions on T .In thisr(t)σ(t)γ(t)α(t)β(t)table, t will denote a typical treeorder of t number of verticessymmetry of t order of automorphism groupdensity of tnumber of ways of labelling with an ordered setnumber of ways of labelling with an unordered setIntroduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .Order conditionsoWe identify the following functions on T .In thisr(t)σ(t)γ(t)α(t)β(t)F (t)(y0 )table, t will denote a typical treeorder of t number of verticessymmetry of t order of automorphism groupdensity of tnumber of ways of labelling with an ordered setnumber of ways of labelling with an unordered setelementary differentialIntroduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionLet T denote the set of rooted trees:nT ,,,,,,Approximation,, .Order conditionsoWe identify the following functions on T .In thisr(t)σ(t)γ(t)α(t)β(t)F (t)(y0 )table, t will denote a typical treeorder of t number of verticessymmetry of t order of automorphism groupdensity of tnumber of ways of labelling with an ordered setnumber of ways of labelling with an unordered setelementary differentialWe will give examples of these functions based on t Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutiont Introduction to Runge–Kutta methodsApproximationOrder conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 4r(t) 7Introduction to Runge–Kutta methods567
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 4r(t) 7σ(t) 8Introduction to Runge–Kutta methods567
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 4r(t) 7567σ(t) 81 1 1 1γ(t) 63Introduction to Runge–Kutta methods337
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 45r(t) 767σ(t) 81 1 1 13γ(t) 63α(t) r(t)!σ(t)γ(t)Introduction to Runge–Kutta methods37 10
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 45r(t) 767σ(t) 81 1 1 13γ(t) 63α(t) r(t)!σ(t)γ(t) 10β(t) r(t)!σ(t) 630Introduction to Runge–Kutta methods37
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionst 1 2 3 45r(t) 767σ(t) 81 1 1 13γ(t) 63α(t) r(t)!σ(t)γ(t) 10β(t) r(t)!σ(t) 630f F (t) f′′ f′′ (f, f), f′′ (f, f)Introduction to Runge–Kutta methods37′′ff fff′′f′′
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThese 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 f′ f f′′(f, f) f′ f′ f f(3)(f, f, f) f′′(f, f′ f) f′ f′′(f, f) f′ f′ f′ fIntroduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe 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 for theresult computed by one step of a Runge–Kutta method.By comparing these formulae term by term, we will be able toobtain conditions for a specific order of accuracy.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe 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 for theresult computed by one step of a Runge–Kutta method.By comparing these formulae term by term, we will be able toobtain conditions for a specific order of accuracy.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe 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 for theresult computed by one step of a Runge–Kutta method.By comparing these formulae term by term, we will be able toobtain conditions for a specific order of accuracy.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe 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 for theresult computed by one step of a Runge–Kutta method.By comparing these formulae term by term, we will be able toobtain conditions for a specific order of accuracy.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of approximationWe need to evaluate various expressions which depend on thetableau for a particular method.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of approximationWe need to evaluate various expressions which depend on thetableau for a particular method.These are known as “elementary weights”.Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of approximationWe need to evaluate various expressions which depend on thetableau 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 njkiIntroduction to Runge–Kutta methodso
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of approximationWe need to evaluate various expressions which depend on thetableau 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 njokiΦ(t) sXi,j,k,l,m,n,o 1Introduction to Runge–Kutta methodsbi aij aik ajl ajm akn ako
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTaylor series of approximationWe need to evaluate various expressions which depend on thetableau 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 njokiΦ(t) sXbi aij aik ajl ajm akn akoi,j,k,l,m,n,o 1Simplify by summing over l, m, n, o:sXbi aij c2j aik c2kΦ(t) i,j,k 1Introduction to Runge–Kutta methods
IntroductionFormulationTaylor series: exact solutionApproximationNow add Φ(t) to the table of functions:tr(t)α(t)β(t)Φ(t)111Pbi212Pbi ci313P 2bi ci316Pbi aij cjtr(t)4444α(t)1311β(t)4241224PPP 3 P2Φ(t)bi aij ajk ckbi ci aij cjbi aij cjbi ciIntroduction to Runge–Kutta methodsOrder conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe formal Taylor expansion of the numerical approximation tothe 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 y0 X hr(t)t TIntroduction to Runge–Kutta methodsσ(t)Φ(t)F (t)(y0 )
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe formal Taylor expansion of the numerical approximation tothe 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 y0 X hr(t)t TIntroduction to Runge–Kutta methodsσ(t)Φ(t)F (t)(y0 )
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTo match the Taylor seriesy(x0 h) y0 Xt Ty1 y0 hr(t)F (t)(y0 )σ(t)γ(t)X hr(t)t Tσ(t)up to hp terms we need to ensure thatΦ(t) 1,γ(t)for all trees such thatr(t) p.These are the “order conditions”.Introduction to Runge–Kutta methodsΦ(t)F (t)(y0 )Order conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsTo match the Taylor seriesy(x0 h) y0 Xt Ty1 y0 hr(t)F (t)(y0 )σ(t)γ(t)X hr(t)t Tσ(t)up to hp terms we need to ensure thatΦ(t) 1,γ(t)for all trees such thatr(t) p.These are the “order conditions”.Introduction to Runge–Kutta methodsΦ(t)F (t)(y0 )Order conditions
IntroductionFormulationTaylor series: exact solutionApproximationOrder conditionsThe order conditions will be illustrated in the case of explicit 4stage methods with order 4.Φ(t) t1γ(t)b1 b2 b3 b4 1b2 c2 b3 c3 b4 c4 12b2 c22 b3 c23 b4 c24 13b3 a32 c2 b4 a42 c2 b4 a43 c3 16b2 c32 b3 c33 b4 c34 14b3 c3 a32 c2 b4 c4 a42 c2 b4 c4 a43 c3 18b3 a32 c22 b4 a42 c22 b4 a43 c23 112b4 a43 a32 c2 124Introduction to Runge–Kutta methods
In carrying out a step we evaluate s stage values Y1, Y2, ., Ys and s stage derivatives F1, F2, . , Fs, using the formula Fi f(Yi). Each Yi is defined as a linear combination of the Fj added on to y0: Yi y0 h Xs j 1 aijFj, i 1,2,.,s, and the approximation at x1 x0 h is fou
