Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
General linear methods
open-in-new
<h2 id="some-definitions">Some definitions</h2> <p>Numerical methods for first-order ordinary differential equations approximate solutions to initial value problems of the form </p> y ′ = f ( t , y ) , y ( t 0 ) = y 0 . {\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.} <p>The result is approximations for the value of y ( t ) {\displaystyle y(t)} at discrete times t i {\displaystyle t_{i}} : </p> y i ≈ y ( t i ) where t i = t 0 + i h , {\displaystyle y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,} <p>where <i>h</i> is the time step (sometimes referred to as Δ t {\displaystyle \Delta t} ). </p> <h2 id="a-description-of-the-method">A description of the method</h2> <p>We follow Butcher (2006), pp. 189–190 for our description, although we note that this method can be found elsewhere. </p><p>General linear methods make use of two integers: r {\displaystyle r} – the number of time points in history, and s {\displaystyle s} – the number of collocation points. In the case of r = 1 {\displaystyle r=1} , these methods reduce to classical <a href="/facts/Runge%25E2%2580%2593Kutta_methods/YRjbyHpY">Runge–Kutta methods</a>, and in the case of s = 1 {\displaystyle s=1} , these methods reduce to <a href="/facts/Linear_multistep_method/Q1taSMtG">linear multistep methods</a>. </p><p>Stage values Y i {\displaystyle Y_{i}} and stage derivatives F i , i = 1 , 2 , … s {\displaystyle F_{i},\ i=1,2,\dots s} are computed from approximations y i [ n − 1 ] , i = 1 , … , r {\displaystyle y_{i}^{[n-1]},\ i=1,\dots ,r} at time step n {\displaystyle n} : </p> y [ n − 1 ] = [ y 1 [ n − 1 ] y 2 [ n − 1 ] ⋮ y r [ n − 1 ] ] , y [ n ] = [ y 1 [ n ] y 2 [ n ] ⋮ y r [ n ] ] , Y = [ Y 1 Y 2 ⋮ Y s ] , F = [ F 1 F 2 ⋮ F s ] = [ f ( Y 1 ) f ( Y 2 ) ⋮ f ( Y s ) ] . {\displaystyle y^{[n-1]}=\left[{\begin{matrix}y_{1}^{[n-1]}\\y_{2}^{[n-1]}\\\vdots \\y_{r}^{[n-1]}\\\end{matrix}}\right],\quad y^{[n]}=\left[{\begin{matrix}y_{1}^{[n]}\\y_{2}^{[n]}\\\vdots \\y_{r}^{[n]}\\\end{matrix}}\right],\quad Y=\left[{\begin{matrix}Y_{1}\\Y_{2}\\\vdots \\Y_{s}\end{matrix}}\right],\quad F=\left[{\begin{matrix}F_{1}\\F_{2}\\\vdots \\F_{s}\end{matrix}}\right]=\left[{\begin{matrix}f(Y_{1})\\f(Y_{2})\\\vdots \\f(Y_{s})\end{matrix}}\right].} <p>The stage values are defined by two matrices A = [ a i j ] {\displaystyle A=[a_{ij}]} and U = [ u i j ] {\displaystyle U=[u_{ij}]} : </p> Y i = ∑ j = 1 s a i j h F j + ∑ j = 1 r u i j y j [ n − 1 ] , i = 1 , 2 , … , s , {\displaystyle Y_{i}=\sum _{j=1}^{s}a_{ij}hF_{j}+\sum _{j=1}^{r}u_{ij}y_{j}^{[n-1]},\qquad i=1,2,\dots ,s,} <p>and the update to time t n {\displaystyle t^{n}} is defined by two matrices B = [ b i j ] {\displaystyle B=[b_{ij}]} and V = [ v i j ] {\displaystyle V=[v_{ij}]} : </p> y i [ n ] = ∑ j = 1 s b i j h F j + ∑ j = 1 r v i j y j [ n − 1 ] , i = 1 , 2 , … , r . {\displaystyle y_{i}^{[n]}=\sum _{j=1}^{s}b_{ij}hF_{j}+\sum _{j=1}^{r}v_{ij}y_{j}^{[n-1]},\qquad i=1,2,\dots ,r.} <p>Given the four matrices A , U , B {\displaystyle A,U,B} and V {\displaystyle V} , one can compactly write the analogue of a <a href="/facts/Butcher_tableau/YRjbyHpY">Butcher tableau</a> as </p> [ Y y [ n ] ] = [ A ⊗ I U ⊗ I B ⊗ I V ⊗ I ] [ h F y [ n − 1 ] ] , {\displaystyle \left[{\begin{matrix}Y\\y^{[n]}\end{matrix}}\right]=\left[{\begin{matrix}A\otimes I&U\otimes I\\B\otimes I&V\otimes I\end{matrix}}\right]\left[{\begin{matrix}hF\\y^{[n-1]}\end{matrix}}\right],} <p>where ⊗ {\displaystyle \otimes } stands for the <a href="/facts/Kronecker_product/gABGx6I6">Kronecker product</a>. </p> <h2 id="examples">Examples</h2> <p>We present an example described in (Butcher, 1996).<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> This method consists of a single "predicted" step and "corrected" step, which uses extra information about the time history, as well as a single intermediate stage value. </p><p>An intermediate stage value is defined as something that looks like it came from a <a href="/facts/Linear_multistep_method/Q1taSMtG">linear multistep method</a>: </p> y n − 1 / 2 ∗ = y n − 2 + h ( 9 8 f ( y n − 1 ) + 3 8 f ( y n − 2 ) ) . {\displaystyle y_{n-1/2}^{*}=y_{n-2}+h\left({\frac {9}{8}}f(y_{n-1})+{\frac {3}{8}}f(y_{n-2})\right).} <p>An initial "predictor" y n ∗ {\displaystyle y_{n}^{*}} uses the stage value y n − 1 / 2 ∗ {\displaystyle y_{n-1/2}^{*}} together with two pieces of time history: </p> y n ∗ = 28 5 y n − 1 − 23 5 y n − 2 + h ( 32 15 f ( y n − 1 / 2 ∗ ) − 4 f ( y n − 1 ) − 26 15 f ( y n − 2 ) ) , {\displaystyle y_{n}^{*}={\frac {28}{5}}y_{n-1}-{\frac {23}{5}}y_{n-2}+h\left({\frac {32}{15}}f(y_{n-1/2}^{*})-4f(y_{n-1})-{\frac {26}{15}}f(y_{n-2})\right),} <p>and the final update is given by </p> y n = 32 31 y n − 1 − 1 31 y n − 2 + h ( 5 31 f ( y n ∗ ) + 64 93 f ( y n − 1 / 2 ∗ ) + 4 31 f ( y n − 1 ) − 1 93 f ( y n − 2 ) ) . {\displaystyle y_{n}={\frac {32}{31}}y_{n-1}-{\frac {1}{31}}y_{n-2}+h\left({\frac {5}{31}}f(y_{n}^{*})+{\frac {64}{93}}f(y_{n-1/2}^{*})+{\frac {4}{31}}f(y_{n-1})-{\frac {1}{93}}f(y_{n-2})\right).} <p>The concise table representation for this method is given by </p> [ 0 0 0 0 1 9 8 3 8 32 15 0 0 28 5 − 23 5 − 4 − 26 15 64 93 5 31 0 32 31 − 1 31 4 31 − 1 93 64 93 5 31 0 32 31 − 1 31 4 31 − 1 93 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 ] . {\displaystyle \left[{\begin{array}{ccc|cccc}0&0&0&0&1&{\frac {9}{8}}&{\frac {3}{8}}\\{\frac {32}{15}}&0&0&{\frac {28}{5}}&-{\frac {23}{5}}&-4&-{\frac {26}{15}}\\{\frac {64}{93}}&{\frac {5}{31}}&0&{\frac {32}{31}}&-{\frac {1}{31}}&{\frac {4}{31}}&-{\frac {1}{93}}\\\hline {\frac {64}{93}}&{\frac {5}{31}}&0&{\frac {32}{31}}&-{\frac {1}{31}}&{\frac {4}{31}}&-{\frac {1}{93}}\\0&0&0&1&0&0&0\\0&0&1&0&0&0&0\\0&0&0&0&0&1&0\\\end{array}}\right].} <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Runge%25E2%2580%2593Kutta_methods/YRjbyHpY">Runge–Kutta methods</a></li> <li><a href="/facts/Linear_multistep_method/Q1taSMtG">Linear multistep methods</a></li> <li><a href="/facts/Numerical_methods_for_ordinary_differential_equations/rbrYBco3">Numerical methods for ordinary differential equations</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Butcher, John C. (January 1965). <a href="https://doi.org/10.1145%2F321250.321261">"A Modified Multistep Method for the Numerical Integration of Ordinary Differential Equations"</a>. <i>Journal of the ACM</i>. 12 (1): 124–135. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321250.321261">10.1145/321250.321261</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:36463504">36463504</a>.</li> <li>Gear, C. W. (1965). "Hybrid Methods for Initial Value Problems in Ordinary Differential Equations". <i>Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis</i>. 2 (1): 69–86. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1965SJNA....2...69G">1965SJNA....2...69G</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0702006">10.1137/0702006</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2027%2Fuiuo.ark%3A%2F13960%2Ft4rj60q8s">2027/uiuo.ark:/13960/t4rj60q8s</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122744897">122744897</a>.</li> <li>Gragg, William B.; Hans J. Stetter (April 1964). <a href="https://doi.org/10.1145%2F321217.321223">"Generalized Multistep Predictor-Corrector Methods"</a>. <i>Journal of the ACM</i>. 11 (2): 188–209. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321217.321223">10.1145/321217.321223</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17118462">17118462</a>.</li> <li>Hairer, Ernst; Wanner, Wanner (1973), "Multistep-multistage-multiderivative methods for ordinary differential equations", <i>Computing</i>, 11 (3): 287–303, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02252917">10.1007/BF02252917</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:25549771">25549771</a>.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.scholarpedia.org/article/General_linear_methods">General Linear Methods</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Butcher, John C. (February–March 1996). "General linear methods". Computers & Mathematics with Applications. 31 (4–5): 105–112. doi:10.1016/0898-1221(95)00222-7. <a href="https://doi.org/10.1016%2F0898-1221%2895%2900222-7" target="_blank">https://doi.org/10.1016%2F0898-1221%2895%2900222-7</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Butcher, John (May 2006). "General linear methods". Acta Numerica. 15: 157–256. Bibcode:2006AcNum..15..157B. doi:10.1017/S0962492906220014. S2CID 125962375. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Butcher, John (February 2009). "General linear methods for ordinary differential equations". Mathematics and Computers in Simulation. 79 (6): 1834–1845. doi:10.1016/j.matcom.2007.02.006. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Butcher, John (2005). "General Linear Methods". Numerical Methods for Ordinary Differential Equations. John Wiley & Sons, Ltd. pp. 357–413. doi:10.1002/0470868279.ch5. ISBN 9780470868270. S2CID 2334002. <a href="9780470868270" target="_blank">9780470868270</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Butcher, John (1987). The numerical analysis of ordinary differential equations: Runge–Kutta and general linear methods. Wiley-Interscience. ISBN 978-0-471-91046-6. <a href="978-0-471-91046-6" target="_blank">978-0-471-91046-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Jackiewicz, Zdzislaw (2009). General Linear Methods for Ordinary Differential Equations. Wiley. ISBN 978-0-470-40855-1. <a href="978-0-470-40855-1" target="_blank">978-0-470-40855-1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Butcher 1996, p. 107. - Butcher, John C. (February–March 1996). "General linear methods". Computers & Mathematics with Applications. 31 (4–5): 105–112. doi:10.1016/0898-1221(95)00222-7. <a href="https://doi.org/10.1016%2F0898-1221%2895%2900222-7" target="_blank">https://doi.org/10.1016%2F0898-1221%2895%2900222-7</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> </ol>