math/doc/html/math_toolkit/bad_guess.html
2019-10-31 17:55:35 +00:00

778 lines
15 KiB
HTML

<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>