devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777
							<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>The Effect of a Poor Initial Guess</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="root_finding_examples/elliptic_eg.html" title="A More complex example - Inverting the Elliptic Integrals">
<link rel="next" href="bad_roots.html" title="Examples Where Root Finding Goes Wrong">
</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="root_finding_examples/elliptic_eg.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="bad_roots.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.bad_guess"></a><a class="link" href="bad_guess.html" title="The Effect of a Poor Initial Guess">The Effect of a Poor Initial Guess</a>
</h2></div></div></div>
<p>
      It's instructive to take our "toy" example algorithms, and use deliberately
      bad initial guesses to see how the various root finding algorithms fair. We'll
      start with the cubed root, and using the cube root of 500 as the test case:
    </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
              <p>
                Initial Guess=
              </p>
            </th>
<th>
              <p>
                -500% (&#8776;1.323)
              </p>
            </th>
<th>
              <p>
                -100% (&#8776;3.97)
              </p>
            </th>
<th>
              <p>
                -50% (&#8776;3.96)
              </p>
            </th>
<th>
              <p>
                -20% (&#8776;6.35)
              </p>
            </th>
<th>
              <p>
                -10% (&#8776;7.14)
              </p>
            </th>
<th>
              <p>
                -5% (&#8776;7.54)
              </p>
            </th>
<th>
              <p>
                5% (&#8776;8.33)
              </p>
            </th>
<th>
              <p>
                10% (&#8776;8.73)
              </p>
            </th>
<th>
              <p>
                20% (&#8776;9.52)
              </p>
            </th>
<th>
              <p>
                50% (&#8776;11.91)
              </p>
            </th>
<th>
              <p>
                100% (&#8776;15.87)
              </p>
            </th>
<th>
              <p>
                500 (&#8776;47.6)
              </p>
            </th>
</tr></thead>
<tbody>
<tr>
<td>
              <p>
                bracket_and_solve_root
              </p>
            </td>
<td>
              <p>
                12
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                10
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                13
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                newton_iterate
              </p>
            </td>
<td>
              <p>
                12
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                9
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                halley_iterate
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                schroder_iterate
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
</tr>
</tbody>
</table></div>
<p>
      As you can see <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code>
      is relatively insensitive to starting location - as long as you don't start
      many orders of magnitude away from the root it will take roughly the same number
      of steps to bracket the root and solve it. On the other hand the derivative-based
      methods are slow to start, but once they have some digits correct they increase
      precision exceptionally fast: they are therefore quite sensitive to the initial
      starting location.
    </p>
<p>
      The next table shows the number of iterations required to find the second radius
      of an ellipse with first radius 50 and arc-length 500:
    </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
              <p>
                Initial Guess=
              </p>
            </th>
<th>
              <p>
                -500% (&#8776;20.6)
              </p>
            </th>
<th>
              <p>
                -100% (&#8776;61.81)
              </p>
            </th>
<th>
              <p>
                -50% (&#8776;61.81)
              </p>
            </th>
<th>
              <p>
                -20% (&#8776;98.9)
              </p>
            </th>
<th>
              <p>
                -10% (&#8776;111.3)
              </p>
            </th>
<th>
              <p>
                -5% (&#8776;117.4)
              </p>
            </th>
<th>
              <p>
                5% (&#8776;129.8)
              </p>
            </th>
<th>
              <p>
                10% (&#8776;136)
              </p>
            </th>
<th>
              <p>
                20% (&#8776;148.3)
              </p>
            </th>
<th>
              <p>
                50% (&#8776;185.4)
              </p>
            </th>
<th>
              <p>
                100% (&#8776;247.2)
              </p>
            </th>
<th>
              <p>
                500 (&#8776;741.7)
              </p>
            </th>
</tr></thead>
<tbody>
<tr>
<td>
              <p>
                bracket_and_solve_root
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                9
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                10
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                newton_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                halley_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                schroder_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
</tr>
</tbody>
</table></div>
<p>
      Interestingly this function is much more resistant to a poor initial guess
      when using derivatives.
    </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="root_finding_examples/elliptic_eg.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="bad_roots.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>