ceph/src/boost/libs/math/doc/html/math_toolkit/roots/bad_roots.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Examples Where Root Finding Goes Wrong</title>
   5 <link rel="stylesheet" href="../../math.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.5.1">
   8 <link rel="up" href="../roots.html" title="Root finding">
   9 <link rel="prev" href="bad_guess.html" title="The Effect of a Poor Initial Guess">
  10 <link rel="next" href="brent_minima.html" title="Locating Function Minima using Brent's algorithm">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="bad_guess.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../roots.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="brent_minima.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="math_toolkit.roots.bad_roots"></a><a class="link" href="bad_roots.html" title="Examples Where Root Finding Goes Wrong">Examples Where Root Finding
  28       Goes Wrong</a>
  29 </h3></div></div></div>
  30 <p>
  31         There are many reasons why root root finding can fail, here are just a few
  32         of the more common examples:
  33       </p>
  34 <h4>
  35 <a name="math_toolkit.roots.bad_roots.h0"></a>
  36         <span class="phrase"><a name="math_toolkit.roots.bad_roots.local_minima"></a></span><a class="link" href="bad_roots.html#math_toolkit.roots.bad_roots.local_minima">Local
  37         Minima</a>
  38       </h4>
  39 <p>
  40         If you start in the wrong place, such as z<sub>0</sub> here:
  41       </p>
  42 <p>
  43         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../roots/bad_root_1.svg" width="372.047244094489" height="262.204724409449"></object></span>
  44       </p>
  45 <p>
  46         Then almost any root-finding algorithm will descend into a local minima rather
  47         than find the root.
  48       </p>
  49 <h4>
  50 <a name="math_toolkit.roots.bad_roots.h1"></a>
  51         <span class="phrase"><a name="math_toolkit.roots.bad_roots.flatlining"></a></span><a class="link" href="bad_roots.html#math_toolkit.roots.bad_roots.flatlining">Flatlining</a>
  52       </h4>
  53 <p>
  54         In this example, we're starting from a location (z<sub>0</sub>) where the first derivative
  55         is essentially zero:
  56       </p>
  57 <p>
  58         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../roots/bad_root_2.svg" width="372.047244094489" height="262.204724409449"></object></span>
  59       </p>
  60 <p>
  61         In this situation the next iteration will shoot off to infinity (assuming
  62         we're using derivatives that is). Our code guards against this by insisting
  63         that the root is always bracketed, and then never stepping outside those
  64         bounds. In a case like this, no root finding algorithm can do better than
  65         bisecting until the root is found.
  66       </p>
  67 <p>
  68         Note that there is no scale on the graph, we have seen examples of this situation
  69         occur in practice <span class="emphasis"><em>even when several decimal places of the initial
  70         guess z<sub>0</sub> are correct.</em></span>
  71       </p>
  72 <p>
  73         This is really a special case of a more common situation where root finding
  74         with derivatives is <span class="emphasis"><em>divergent</em></span>. Consider starting at
  75         z<sub>0</sub> in this case:
  76       </p>
  77 <p>
  78         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../roots/bad_root_4.svg" width="372.047244094489" height="262.204724409449"></object></span>
  79       </p>
  80 <p>
  81         An initial Newton step would take you further from the root than you started,
  82         as will all subsequent steps.
  83       </p>
  84 <h4>
  85 <a name="math_toolkit.roots.bad_roots.h2"></a>
  86         <span class="phrase"><a name="math_toolkit.roots.bad_roots.micro_stepping_non_convergence"></a></span><a class="link" href="bad_roots.html#math_toolkit.roots.bad_roots.micro_stepping_non_convergence">Micro-stepping
  87         / Non-convergence</a>
  88       </h4>
  89 <p>
  90         Consider starting at z<sub>0</sub> in this situation:
  91       </p>
  92 <p>
  93         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../roots/bad_root_3.svg" width="372.047244094489" height="262.204724409449"></object></span>
  94       </p>
  95 <p>
  96         The first derivative is essentially infinite, and the second close to zero
  97         (and so offers no correction if we use it), as a result we take a very small
  98         first step. In the worst case situation, the first step is so small - perhaps
  99         even so small that subtracting from z<sub>0</sub> has no effect at the current working
 100         precision - that our algorithm will assume we are at the root already and
 101         terminate. Otherwise we will take lot's of very small steps which never converge
 102         on the root: our algorithms will protect against that by reverting to bisection.
 103       </p>
 104 <p>
 105         An example of this situation would be trying to find the root of e<sup>-1/z<sup>2</sup></sup> -
 106         this function has a single root at <span class="emphasis"><em>z = 0</em></span>, but for <span class="emphasis"><em>z<sub>0</sub> &lt;
 107         0</em></span> neither Newton nor Halley steps will ever converge on the root,
 108         and for <span class="emphasis"><em>z<sub>0</sub> &gt; 0</em></span> the steps are actually divergent.
 109       </p>
 110 </div>
 111 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 112 <td align="left"></td>
 113 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2010, 2012-2014 Nikhar Agrawal,
 114       Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
 115       Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R&#229;de, Gautam Sewani,
 116       Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
 117         Distributed under the Boost Software License, Version 1.0. (See accompanying
 118         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 119       </p>
 120 </div></td>
 121 </tr></table>
 122 <hr>
 123 <div class="spirit-nav">
 124 <a accesskey="p" href="bad_guess.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../roots.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="brent_minima.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 125 </div>
 126 </body>
 127 </html>