devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379
							<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Root Finding With Derivatives: Newton-Raphson, Halley &amp; Schr&#246;der</title>
<link rel="stylesheet" href="../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Math Toolkit 2.11.0">
<link rel="up" href="../root_finding.html" title="Chapter&#160;10.&#160;Root Finding &amp; Minimization Algorithms">
<link rel="prev" href="roots_noderiv/implementation.html" title="Implementation">
<link rel="next" href="root_finding_examples.html" title="Examples of Root-Finding (with and without derivatives)">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="roots_noderiv/implementation.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="root_finding_examples.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.roots_deriv"></a><a class="link" href="roots_deriv.html" title="Root Finding With Derivatives: Newton-Raphson, Halley &amp; Schr&#246;der">Root Finding With Derivatives:
    Newton-Raphson, Halley &amp; Schr&#246;der</a>
</h2></div></div></div>
<h5>
<a name="math_toolkit.roots_deriv.h0"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.synopsis"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.synopsis">Synopsis</a>
    </h5>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">roots</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span> <span class="special">{</span>
<span class="keyword">namespace</span> <span class="identifier">tools</span> <span class="special">{</span> <span class="comment">// Note namespace boost::math::tools.</span>
<span class="comment">// Newton-Raphson</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">newton_raphson_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">);</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">newton_raphson_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>

<span class="comment">// Halley</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">halley_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">);</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">halley_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>

<span class="comment">// Schr'''&amp;#xf6;'''der</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">schroder_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">);</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">schroder_iterate</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">guess</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">digits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Complex</span><span class="special">&gt;</span>
<span class="identifier">Complex</span> <span class="identifier">complex_newton</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> <span class="identifier">Complex</span> <span class="identifier">guess</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">max_iterations</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Complex</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">&gt;::</span><span class="identifier">digits</span><span class="special">);</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">auto</span> <span class="identifier">quadratic_roots</span><span class="special">(</span><span class="identifier">T</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">T</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">b</span><span class="special">,</span> <span class="identifier">T</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">c</span><span class="special">);</span>

<span class="special">}}}</span> <span class="comment">// namespaces boost::math::tools.</span>
</pre>
<h5>
<a name="math_toolkit.roots_deriv.h1"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.description"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.description">Description</a>
    </h5>
<p>
      These functions all perform iterative root-finding <span class="bold"><strong>using
      derivatives</strong></span>:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          <code class="computeroutput"><span class="identifier">newton_raphson_iterate</span></code>
          performs second-order <a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson
          iteration</a>.
        </li>
<li class="listitem">
          <code class="computeroutput"><span class="identifier">halley_iterate</span></code> and <code class="computeroutput"><span class="identifier">schroder_iterate</span></code> perform third-order
          <a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.halley">Halley</a> and <a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.schroder">Schr&#246;der</a> iteration.
        </li>
<li class="listitem">
          <code class="computeroutput"><span class="identifier">complex_newton</span></code> performs
          Newton's method on complex-analytic functions.
        </li>
<li class="listitem">
          <code class="computeroutput"><span class="identifier">solve_quadratic</span></code> solves
          quadratic equations using various tricks to keep catastrophic cancellation
          from occurring in computation of the discriminant.
        </li>
</ul></div>
<div class="variablelist">
<p class="title"><b>Parameters of the real-valued root finding functions</b></p>
<dl class="variablelist">
<dt><span class="term">F f</span></dt>
<dd>
<p>
            Type F must be a callable function object (or C++ lambda) that accepts
            one parameter and returns a <a class="link" href="internals/tuples.html" title="Tuples">std::pair,
            std::tuple, boost::tuple or boost::fusion::tuple</a>:
          </p>
<p>
            For second-order iterative method (<a href="http://en.wikipedia.org/wiki/Newton_Raphson" target="_top">Newton
            Raphson</a>) the <code class="computeroutput"><span class="identifier">tuple</span></code>
            should have <span class="bold"><strong>two</strong></span> elements containing
            the evaluation of the function and its first derivative.
          </p>
<p>
            For the third-order methods (<a href="http://en.wikipedia.org/wiki/Halley%27s_method" target="_top">Halley</a>
            and Schr&#246;der) the <code class="computeroutput"><span class="identifier">tuple</span></code>
            should have <span class="bold"><strong>three</strong></span> elements containing
            the evaluation of the function and its first and second derivatives.
          </p>
</dd>
<dt><span class="term">T guess</span></dt>
<dd><p>
            The initial starting value. A good guess is crucial to quick convergence!
          </p></dd>
<dt><span class="term">T min</span></dt>
<dd><p>
            The minimum possible value for the result, this is used as an initial
            lower bracket.
          </p></dd>
<dt><span class="term">T max</span></dt>
<dd><p>
            The maximum possible value for the result, this is used as an initial
            upper bracket.
          </p></dd>
<dt><span class="term">int digits</span></dt>
<dd><p>
            The desired number of binary digits precision.
          </p></dd>
<dt><span class="term">uintmax_t&amp; max_iter</span></dt>
<dd><p>
            An optional maximum number of iterations to perform. On exit, this is
            updated to the actual number of iterations performed.
          </p></dd>
</dl>
</div>
<p>
      When using these functions you should note that:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          Default <code class="computeroutput"><span class="identifier">max_iter</span> <span class="special">=</span>
          <span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&gt;::</span><span class="identifier">max</span><span class="special">)()</span></code> is effectively 'iterate for ever'.
        </li>
<li class="listitem">
          They may be very sensitive to the initial guess, typically they converge
          very rapidly if the initial guess has two or three decimal digits correct.
          However convergence can be no better than <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisect</a>,
          or in some rare cases, even worse than <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisect</a>
          if the initial guess is a long way from the correct value and the derivatives
          are close to zero.
        </li>
<li class="listitem">
          These functions include special cases to handle zero first (and second
          where appropriate) derivatives, and fall back to <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisect</a>
          in this case. However, it is helpful if functor F is defined to return
          an arbitrarily small value <span class="emphasis"><em>of the correct sign</em></span> rather
          than zero.
        </li>
<li class="listitem">
          The functions will raise an <a class="link" href="error_handling.html#math_toolkit.error_handling.evaluation_error">evaluation_error</a>
          if arguments <code class="computeroutput"><span class="identifier">min</span></code> and <code class="computeroutput"><span class="identifier">max</span></code> are the wrong way around or if they
          converge to a local minima.
        </li>
<li class="listitem">
          If the derivative at the current best guess for the result is infinite
          (or very close to being infinite) then these functions may terminate prematurely.
          A large first derivative leads to a very small next step, triggering the
          termination condition. Derivative based iteration may not be appropriate
          in such cases.
        </li>
<li class="listitem">
          If the function is 'Really Well Behaved' (is monotonic and has only one
          root) the bracket bounds <span class="emphasis"><em>min</em></span> and <span class="emphasis"><em>max</em></span>
          may as well be set to the widest limits like zero and <code class="computeroutput"><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">max</span><span class="special">()</span></code>.
        </li>
<li class="listitem">
          But if the function more complex and may have more than one root or a pole,
          the choice of bounds is protection against jumping out to seek the 'wrong'
          root.
        </li>
<li class="listitem">
          These functions fall back to <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisect</a>
          if the next computed step would take the next value out of bounds. The
          bounds are updated after each step to ensure this leads to convergence.
          However, a good initial guess backed up by asymptotically-tight bounds
          will improve performance no end - rather than relying on <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisection</a>.
        </li>
<li class="listitem">
          The value of <span class="emphasis"><em>digits</em></span> is crucial to good performance
          of these functions, if it is set too high then at best you will get one
          extra (unnecessary) iteration, and at worst the last few steps will proceed
          by <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisection</a>.
          Remember that the returned value can never be more accurate than <span class="emphasis"><em>f(x)</em></span>
          can be evaluated, and that if <span class="emphasis"><em>f(x)</em></span> suffers from cancellation
          errors as it tends to zero then the computed steps will be effectively
          random. The value of <span class="emphasis"><em>digits</em></span> should be set so that
          iteration terminates before this point: remember that for second and third
          order methods the number of correct digits in the result is increasing
          quite substantially with each iteration, <span class="emphasis"><em>digits</em></span> should
          be set by experiment so that the final iteration just takes the next value
          into the zone where <span class="emphasis"><em>f(x)</em></span> becomes inaccurate. A good
          starting point for <span class="emphasis"><em>digits</em></span> would be 0.6*D for Newton
          and 0.4*D for Halley or Shr&#246;der iteration, where D is <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">digits</span></code>.
        </li>
<li class="listitem">
          If you need some diagnostic output to see what is going on, you can <code class="computeroutput"><span class="preprocessor">#define</span> <span class="identifier">BOOST_MATH_INSTRUMENT</span></code>
          before the <code class="computeroutput"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">roots</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span></code>, and also ensure that display of all
          the significant digits with <code class="computeroutput"> <span class="identifier">cout</span><span class="special">.</span><span class="identifier">precision</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;::</span><span class="identifier">digits10</span><span class="special">)</span></code>: or even possibly significant digits with
          <code class="computeroutput"> <span class="identifier">cout</span><span class="special">.</span><span class="identifier">precision</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;::</span><span class="identifier">max_digits10</span><span class="special">)</span></code>:
          but be warned, this may produce copious output!
        </li>
<li class="listitem">
          Finally: you may well be able to do better than these functions by hand-coding
          the heuristics used so that they are tailored to a specific function. You
          may also be able to compute the ratio of derivatives used by these methods
          more efficiently than computing the derivatives themselves. As ever, algebraic
          simplification can be a big win.
        </li>
</ul></div>
<h5>
<a name="math_toolkit.roots_deriv.h2"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.newton"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.newton">Newton
      Raphson Method</a>
    </h5>
<p>
      Given an initial guess <span class="emphasis"><em>x0</em></span> the subsequent values are computed
      using:
    </p>
<div class="blockquote"><blockquote class="blockquote"><p>
        <span class="inlinemediaobject"><img src="../../equations/roots1.svg"></span>

      </p></blockquote></div>
<p>
      Out-of-bounds steps revert to <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisection</a>
      of the current bounds.
    </p>
<p>
      Under ideal conditions, the number of correct digits doubles with each iteration.
    </p>
<h5>
<a name="math_toolkit.roots_deriv.h3"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.halley"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.halley">Halley's
      Method</a>
    </h5>
<p>
      Given an initial guess <span class="emphasis"><em>x0</em></span> the subsequent values are computed
      using:
    </p>
<div class="blockquote"><blockquote class="blockquote"><p>
        <span class="inlinemediaobject"><img src="../../equations/roots2.svg"></span>

      </p></blockquote></div>
<p>
      Over-compensation by the second derivative (one which would proceed in the
      wrong direction) causes the method to revert to a Newton-Raphson step.
    </p>
<p>
      Out of bounds steps revert to bisection of the current bounds.
    </p>
<p>
      Under ideal conditions, the number of correct digits trebles with each iteration.
    </p>
<h5>
<a name="math_toolkit.roots_deriv.h4"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.schroder"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.schroder">Schr&#246;der's
      Method</a>
    </h5>
<p>
      Given an initial guess x0 the subsequent values are computed using:
    </p>
<div class="blockquote"><blockquote class="blockquote"><p>
        <span class="inlinemediaobject"><img src="../../equations/roots3.svg"></span>

      </p></blockquote></div>
<p>
      Over-compensation by the second derivative (one which would proceed in the
      wrong direction) causes the method to revert to a Newton-Raphson step. Likewise
      a Newton step is used whenever that Newton step would change the next value
      by more than 10%.
    </p>
<p>
      Out of bounds steps revert to <a href="https://en.wikipedia.org/wiki/Bisection" target="_top">bisection</a>
      of the current bounds.
    </p>
<p>
      Under ideal conditions, the number of correct digits trebles with each iteration.
    </p>
<p>
      This is Schr&#246;der's general result (equation 18 from <a href="http://drum.lib.umd.edu/handle/1903/577" target="_top">Stewart,
      G. W. "On Infinitely Many Algorithms for Solving Equations." English
      translation of Schr&#246;der's original paper. College Park, MD: University of Maryland,
      Institute for Advanced Computer Studies, Department of Computer Science, 1993</a>.)
    </p>
<p>
      This method guarantees at least quadratic convergence (the same as Newton's
      method), and is known to work well in the presence of multiple roots: something
      that neither Newton nor Halley can do.
    </p>
<p>
      The complex Newton method works slightly differently than the rest of the methods:
      Since there is no way to bracket roots in the complex plane, the <code class="computeroutput"><span class="identifier">min</span></code> and <code class="computeroutput"><span class="identifier">max</span></code>
      arguments are not accepted. Failure to reach a root is communicated by returning
      <code class="computeroutput"><span class="identifier">nan</span></code>s. Remember that if a function
      has many roots, then which root the complex Newton's method converges to is
      essentially impossible to predict a priori; see the Newton's fractal for more
      information.
    </p>
<p>
      Finally, the derivative of <span class="emphasis"><em>f</em></span> must be continuous at the
      root or else non-roots can be found; see <a href="https://math.stackexchange.com/questions/3017766/constructing-newton-iteration-converging-to-non-root" target="_top">here</a>
      for an example.
    </p>
<p>
      An example usage of <code class="computeroutput"><span class="identifier">complex_newton</span></code>
      is given in <code class="computeroutput"><span class="identifier">examples</span><span class="special">/</span><span class="identifier">daubechies_coefficients</span><span class="special">.</span><span class="identifier">cpp</span></code>.
    </p>
<h5>
<a name="math_toolkit.roots_deriv.h5"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.quadratics"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.quadratics">Quadratics</a>
    </h5>
<p>
      To solve a quadratic <span class="emphasis"><em>ax</em></span><sup>2</sup> + <span class="emphasis"><em>bx</em></span> + <span class="emphasis"><em>c</em></span>
      = 0, we may use
    </p>
<pre class="programlisting"><span class="keyword">auto</span> <span class="special">[</span><span class="identifier">x0</span><span class="special">,</span> <span class="identifier">x1</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">tools</span><span class="special">::</span><span class="identifier">quadratic_roots</span><span class="special">(</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">,</span> <span class="identifier">c</span><span class="special">);</span>
</pre>
<p>
      If the roots are real, they are arranged so that <code class="computeroutput"><span class="identifier">x0</span></code>
      &#8804; <code class="computeroutput"><span class="identifier">x1</span></code>. If the roots are
      complex and the inputs are real, <code class="computeroutput"><span class="identifier">x0</span></code>
      and <code class="computeroutput"><span class="identifier">x1</span></code> are both <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">Real</span><span class="special">&gt;::</span><span class="identifier">quiet_NaN</span><span class="special">()</span></code>. In this case we must cast <code class="computeroutput"><span class="identifier">a</span></code>, <code class="computeroutput"><span class="identifier">b</span></code>
      and <code class="computeroutput"><span class="identifier">c</span></code> to a complex type to
      extract the complex roots. If <code class="computeroutput"><span class="identifier">a</span></code>,
      <code class="computeroutput"><span class="identifier">b</span></code> and <code class="computeroutput"><span class="identifier">c</span></code>
      are integral, then the roots are of type double. The routine is much faster
      if the fused-multiply-add instruction is available on your architecture. If
      the fma is not available, the function resorts to slow emulation. Finally,
      speed is improved if you compile for your particular architecture. For instance,
      if you compile without any architecture flags, then the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">fma</span></code> call
      compiles down to <code class="computeroutput"><span class="identifier">call</span> <span class="identifier">_fma</span></code>,
      which dynamically chooses to emulate or execute the <code class="computeroutput"><span class="identifier">vfmadd132sd</span></code>
      instruction based on the capabilities of the architecture. If instead, you
      compile with (say) <code class="computeroutput"><span class="special">-</span><span class="identifier">march</span><span class="special">=</span><span class="identifier">native</span></code> then
      no dynamic choice is made: The <code class="computeroutput"><span class="identifier">vfmadd132sd</span></code>
      instruction is always executed if available and emulation is used if not.
    </p>
<h5>
<a name="math_toolkit.roots_deriv.h6"></a>
      <span class="phrase"><a name="math_toolkit.roots_deriv.examples"></a></span><a class="link" href="roots_deriv.html#math_toolkit.roots_deriv.examples">Examples</a>
    </h5>
<p>
      See <a class="link" href="root_finding_examples.html" title="Examples of Root-Finding (with and without derivatives)">root-finding examples</a>.
    </p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2006-2019 Nikhar
      Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
      Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan
      R&#229;de, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg,
      Daryle Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        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>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="roots_noderiv/implementation.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="root_finding_examples.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>