xmds2-doc 2.2.3+dfsg-5 / usr / share / doc / xmds2 / bulirschStoer.html

This file is indexed.

/usr/share/doc/xmds2/bulirschStoer.html is in xmds2-doc 2.2.3+dfsg-5.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>Modified Midpoint Method &mdash; XMDS2 2.2.3 documentation</title>
    
    <link rel="stylesheet" href="_static/classic.css" type="text/css" />
    <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    './',
        VERSION:     '2.2.3',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="_static/jquery.js"></script>
    <script type="text/javascript" src="_static/underscore.js"></script>
    <script type="text/javascript" src="_static/doctools.js"></script>
    <script type="text/javascript" src="file:///usr/share/javascript/mathjax/MathJax.js?config=TeX-AMS_HTML,file:///usr/share/doc/xmds2/_static/mathjax-use-tex-fonts.js"></script>
    <link rel="shortcut icon" href="_static/xmds_favicon.ico"/>
    <link rel="top" title="XMDS2 2.2.3 documentation" href="index.html" />
    <link rel="up" title="Reference section" href="reference_index.html" />
    <link rel="next" title="Advanced Topics" href="advanced_topics.html" />
    <link rel="prev" title="XMDS2 script elements" href="reference_elements.html" /> 
  </head>
  <body role="document">
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="advanced_topics.html" title="Advanced Topics"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="reference_elements.html" title="XMDS2 script elements"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="index.html">XMDS2 2.2.3 documentation</a> &raquo;</li>
          <li class="nav-item nav-item-1"><a href="reference_index.html" accesskey="U">Reference section</a> &raquo;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <div class="section" id="modified-midpoint-method">
<span id="mmdetail"></span><span id="index-0"></span><h1>Modified Midpoint Method<a class="headerlink" href="#modified-midpoint-method" title="Permalink to this headline">¶</a></h1>
<p>Although the modified midpoint can be used standalone as an ordinary differential equation integrator, it is regarded as much more powerful when used as a stepper to complement the Bulirsch-Stoer technique.</p>
<p>The modified midpoint method advances a vector of dependent variables <span class="math">\(y(x)\)</span> from a point <span class="math">\(x\)</span>, to a point <span class="math">\(x + H\)</span> by a sequence of <span class="math">\(n\)</span> substeps, each of size <span class="math">\(h=H/n\)</span>.</p>
<p>The number of right-hand side evaluations required by the modified midpoint method is <span class="math">\(n+1\)</span>.  The formulas for the method are</p>
<div class="math">
\[\begin{split}z_0 &amp;= y(x) \\
z_1 &amp;= z_0 + h f(x, z_0) \\
z_{m+1} &amp;= z_{m-1} + 2 h f(x + m h, z_m)\; \text{ for } m = 1, 2, \dots, n-1 \\
y(x+H) \approx y_n &amp;= \frac{1}{2} \left[ z_n + z_{n-1} + h f(x + H, z_n) \right]\end{split}\]</div>
<p>The error of this, expressed as a power series in <span class="math">\(h\)</span>, the stepsize, contains only even powers of <span class="math">\(h\)</span>:</p>
<div class="math">
\[\begin{split}y_n - y(x + H) &amp;= \sum_{i=1}^{\infty} \alpha_i h^{2i}\end{split}\]</div>
<p>where <span class="math">\(H\)</span> is held constant, but <span class="math">\(h\)</span> changes <span class="math">\(y\)</span> by varing the <span class="math">\(n\)</span> in <span class="math">\(h = H/n\)</span>.</p>
<p>The importance of this even power series is that using Richardson Extrapolation to combine steps and knock out higher-order error terms gains us two orders at a time.</p>
<p>The modified midpoint method is a second-order method, but holds an advantage over second order Runge-Kutta, as it only requires one derivative evaluation per step, instead of the two evaluations that Runge-Kutta necessitates.</p>
</div>
<div class="section" id="bulirsch-stoer-algorithm">
<span id="bsdetail"></span><span id="index-1"></span><h1>Bulirsch-Stoer Algorithm<a class="headerlink" href="#bulirsch-stoer-algorithm" title="Permalink to this headline">¶</a></h1>
<p>The Bulirsch-Stoer algorithm utilizes three core concepts in its design.</p>
<p>First, the usage of Richardson Extrapolation.</p>
<img alt="_images/richardsonExtrapolation.png" class="align-center" src="_images/richardsonExtrapolation.png" />
<p>Richardson Extrapolation considers the final answer of a numerical calculation as being an analytic function of an adjustable parameter such as the stepsize <span class="math">\(h\)</span>. That analytic function can be probed by performing the calculation with various values of <span class="math">\(h\)</span>, none of them being necessarily small enough to yield the accuracy that we desire. When we know enough about the function, we fit it to some analytic form and then evaluate it at the point where <span class="math">\(h = 0\)</span>.</p>
<p>Secondly, the usage of rational function extrapolation in Richardson-type applications. Rational function fits can remain good approximations to analytic functions even after the various terms in powers of <span class="math">\(h\)</span>, all have comparable magnitudes. In other words, <span class="math">\(h\)</span> can be so large as to make the whole notion of the “order” of the method meaningless — and the method can still work superbly.</p>
<p>The third idea is to use an integration method whose error function is strictly even, allowing the rational function or polynomial approximation to be in terms of the variable <span class="math">\(h^2\)</span> instead of just <span class="math">\(h\)</span>.</p>
<p>These three ideas give us the Bulirsch-Stoer method, where a single step takes us from <span class="math">\(x\)</span> to <span class="math">\(x + H\)</span>, where <span class="math">\(H\)</span> is supposed to be a significantly large distance. That single step consists of many substeps of the modified midpoint method, which is then extrapolated to zero stepsize.</p>
<p>(Excerpts derived from <strong>Numerical Recipes: The Art of Scientific Computing</strong>, Third Edition (2007), p1256; Cambridge University Press; ISBN-10: 0521880688, <a class="reference external" href="http://www.nr.com/">http://www.nr.com/</a>)</p>
</div>
<div class="section" id="error-scaling-behaviour">
<span id="errorscaling"></span><span id="index-2"></span><h1>Error Scaling Behaviour<a class="headerlink" href="#error-scaling-behaviour" title="Permalink to this headline">¶</a></h1>
<a class="reference internal image-reference" href="_images/error_scaling.png"><img alt="_images/error_scaling.png" class="align-center" src="_images/error_scaling.png" style="width: 800px; height: 600px;" /></a>
<p>The graph above shows the error scaling behaviour for the Bulirsch-Stoer method. This was generated using data from XMDS2 for a simple problem whose analytical solution was known. For more information and to generate this plot yourself see the testsuite/integrators/richardson_extrapolation/error_scaling directory. There you will find the .xmds files for generating the data and a python script to generate the plot above (requires gnuplot).</p>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="index.html">
              <img class="logo" src="_static/xmds_logo.png" alt="Logo"/>
            </a></p>
  <h3><a href="index.html">Table Of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#">Modified Midpoint Method</a></li>
<li><a class="reference internal" href="#bulirsch-stoer-algorithm">Bulirsch-Stoer Algorithm</a></li>
<li><a class="reference internal" href="#error-scaling-behaviour">Error Scaling Behaviour</a></li>
</ul>

<div id="searchbox" style="display: none" role="search">
  <h3>Quick search</h3>
    <form class="search" action="search.html" method="get">
      <input type="text" name="q" />
      <input type="submit" value="Go" />
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
    <p class="searchtip" style="font-size: 90%">
    Enter search terms or a module, class or function name.
    </p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="advanced_topics.html" title="Advanced Topics"
             >next</a> |</li>
        <li class="right" >
          <a href="reference_elements.html" title="XMDS2 script elements"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="index.html">XMDS2 2.2.3 documentation</a> &raquo;</li>
          <li class="nav-item nav-item-1"><a href="reference_index.html" >Reference section</a> &raquo;</li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &copy; Copyright 2008-2014, Graham Dennis, Joe Hope and Mattias Johnsson. Licensed under the GNU FDL.
      Last updated on Jan 21, 2017.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.3.6.
    </div>
  </body>
</html>

APT Browse - Built by Thomas Orozco.