1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>The Effect of a Poor Initial Guess</title> 5<link rel="stylesheet" href="../math.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../index.html" title="Math Toolkit 2.12.0"> 8<link rel="up" href="../root_finding.html" title="Chapter 10. Root Finding & Minimization Algorithms"> 9<link rel="prev" href="root_finding_examples/elliptic_eg.html" title="A More complex example - Inverting the Elliptic Integrals"> 10<link rel="next" href="bad_roots.html" title="Examples Where Root Finding Goes Wrong"> 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="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> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<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> 28</h2></div></div></div> 29<p> 30 It's instructive to take our "toy" example algorithms, and use deliberately 31 bad initial guesses to see how the various root finding algorithms fair. We'll 32 start with the cubed root, and using the cube root of 500 as the test case: 33 </p> 34<div class="informaltable"><table class="table"> 35<colgroup> 36<col> 37<col> 38<col> 39<col> 40<col> 41<col> 42<col> 43<col> 44<col> 45<col> 46<col> 47<col> 48<col> 49</colgroup> 50<thead><tr> 51<th> 52 <p> 53 Initial Guess= 54 </p> 55 </th> 56<th> 57 <p> 58 -500% (≈1.323) 59 </p> 60 </th> 61<th> 62 <p> 63 -100% (≈3.97) 64 </p> 65 </th> 66<th> 67 <p> 68 -50% (≈3.96) 69 </p> 70 </th> 71<th> 72 <p> 73 -20% (≈6.35) 74 </p> 75 </th> 76<th> 77 <p> 78 -10% (≈7.14) 79 </p> 80 </th> 81<th> 82 <p> 83 -5% (≈7.54) 84 </p> 85 </th> 86<th> 87 <p> 88 5% (≈8.33) 89 </p> 90 </th> 91<th> 92 <p> 93 10% (≈8.73) 94 </p> 95 </th> 96<th> 97 <p> 98 20% (≈9.52) 99 </p> 100 </th> 101<th> 102 <p> 103 50% (≈11.91) 104 </p> 105 </th> 106<th> 107 <p> 108 100% (≈15.87) 109 </p> 110 </th> 111<th> 112 <p> 113 500 (≈47.6) 114 </p> 115 </th> 116</tr></thead> 117<tbody> 118<tr> 119<td> 120 <p> 121 bracket_and_solve_root 122 </p> 123 </td> 124<td> 125 <p> 126 12 127 </p> 128 </td> 129<td> 130 <p> 131 8 132 </p> 133 </td> 134<td> 135 <p> 136 8 137 </p> 138 </td> 139<td> 140 <p> 141 10 142 </p> 143 </td> 144<td> 145 <p> 146 11 147 </p> 148 </td> 149<td> 150 <p> 151 11 152 </p> 153 </td> 154<td> 155 <p> 156 11 157 </p> 158 </td> 159<td> 160 <p> 161 11 162 </p> 163 </td> 164<td> 165 <p> 166 11 167 </p> 168 </td> 169<td> 170 <p> 171 11 172 </p> 173 </td> 174<td> 175 <p> 176 7 177 </p> 178 </td> 179<td> 180 <p> 181 13 182 </p> 183 </td> 184</tr> 185<tr> 186<td> 187 <p> 188 newton_iterate 189 </p> 190 </td> 191<td> 192 <p> 193 12 194 </p> 195 </td> 196<td> 197 <p> 198 7 199 </p> 200 </td> 201<td> 202 <p> 203 7 204 </p> 205 </td> 206<td> 207 <p> 208 5 209 </p> 210 </td> 211<td> 212 <p> 213 5 214 </p> 215 </td> 216<td> 217 <p> 218 4 219 </p> 220 </td> 221<td> 222 <p> 223 4 224 </p> 225 </td> 226<td> 227 <p> 228 5 229 </p> 230 </td> 231<td> 232 <p> 233 5 234 </p> 235 </td> 236<td> 237 <p> 238 6 239 </p> 240 </td> 241<td> 242 <p> 243 7 244 </p> 245 </td> 246<td> 247 <p> 248 9 249 </p> 250 </td> 251</tr> 252<tr> 253<td> 254 <p> 255 halley_iterate 256 </p> 257 </td> 258<td> 259 <p> 260 7 261 </p> 262 </td> 263<td> 264 <p> 265 4 266 </p> 267 </td> 268<td> 269 <p> 270 4 271 </p> 272 </td> 273<td> 274 <p> 275 3 276 </p> 277 </td> 278<td> 279 <p> 280 3 281 </p> 282 </td> 283<td> 284 <p> 285 3 286 </p> 287 </td> 288<td> 289 <p> 290 3 291 </p> 292 </td> 293<td> 294 <p> 295 3 296 </p> 297 </td> 298<td> 299 <p> 300 3 301 </p> 302 </td> 303<td> 304 <p> 305 4 306 </p> 307 </td> 308<td> 309 <p> 310 4 311 </p> 312 </td> 313<td> 314 <p> 315 6 316 </p> 317 </td> 318</tr> 319<tr> 320<td> 321 <p> 322 schroder_iterate 323 </p> 324 </td> 325<td> 326 <p> 327 11 328 </p> 329 </td> 330<td> 331 <p> 332 6 333 </p> 334 </td> 335<td> 336 <p> 337 6 338 </p> 339 </td> 340<td> 341 <p> 342 4 343 </p> 344 </td> 345<td> 346 <p> 347 3 348 </p> 349 </td> 350<td> 351 <p> 352 3 353 </p> 354 </td> 355<td> 356 <p> 357 3 358 </p> 359 </td> 360<td> 361 <p> 362 3 363 </p> 364 </td> 365<td> 366 <p> 367 4 368 </p> 369 </td> 370<td> 371 <p> 372 5 373 </p> 374 </td> 375<td> 376 <p> 377 5 378 </p> 379 </td> 380<td> 381 <p> 382 8 383 </p> 384 </td> 385</tr> 386</tbody> 387</table></div> 388<p> 389 As you can see <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code> 390 is relatively insensitive to starting location - as long as you don't start 391 many orders of magnitude away from the root it will take roughly the same number 392 of steps to bracket the root and solve it. On the other hand the derivative-based 393 methods are slow to start, but once they have some digits correct they increase 394 precision exceptionally fast: they are therefore quite sensitive to the initial 395 starting location. 396 </p> 397<p> 398 The next table shows the number of iterations required to find the second radius 399 of an ellipse with first radius 50 and arc-length 500: 400 </p> 401<div class="informaltable"><table class="table"> 402<colgroup> 403<col> 404<col> 405<col> 406<col> 407<col> 408<col> 409<col> 410<col> 411<col> 412<col> 413<col> 414<col> 415<col> 416</colgroup> 417<thead><tr> 418<th> 419 <p> 420 Initial Guess= 421 </p> 422 </th> 423<th> 424 <p> 425 -500% (≈20.6) 426 </p> 427 </th> 428<th> 429 <p> 430 -100% (≈61.81) 431 </p> 432 </th> 433<th> 434 <p> 435 -50% (≈61.81) 436 </p> 437 </th> 438<th> 439 <p> 440 -20% (≈98.9) 441 </p> 442 </th> 443<th> 444 <p> 445 -10% (≈111.3) 446 </p> 447 </th> 448<th> 449 <p> 450 -5% (≈117.4) 451 </p> 452 </th> 453<th> 454 <p> 455 5% (≈129.8) 456 </p> 457 </th> 458<th> 459 <p> 460 10% (≈136) 461 </p> 462 </th> 463<th> 464 <p> 465 20% (≈148.3) 466 </p> 467 </th> 468<th> 469 <p> 470 50% (≈185.4) 471 </p> 472 </th> 473<th> 474 <p> 475 100% (≈247.2) 476 </p> 477 </th> 478<th> 479 <p> 480 500 (≈741.7) 481 </p> 482 </th> 483</tr></thead> 484<tbody> 485<tr> 486<td> 487 <p> 488 bracket_and_solve_root 489 </p> 490 </td> 491<td> 492 <p> 493 11 494 </p> 495 </td> 496<td> 497 <p> 498 5 499 </p> 500 </td> 501<td> 502 <p> 503 5 504 </p> 505 </td> 506<td> 507 <p> 508 8 509 </p> 510 </td> 511<td> 512 <p> 513 8 514 </p> 515 </td> 516<td> 517 <p> 518 7 519 </p> 520 </td> 521<td> 522 <p> 523 7 524 </p> 525 </td> 526<td> 527 <p> 528 8 529 </p> 530 </td> 531<td> 532 <p> 533 9 534 </p> 535 </td> 536<td> 537 <p> 538 8 539 </p> 540 </td> 541<td> 542 <p> 543 6 544 </p> 545 </td> 546<td> 547 <p> 548 10 549 </p> 550 </td> 551</tr> 552<tr> 553<td> 554 <p> 555 newton_iterate 556 </p> 557 </td> 558<td> 559 <p> 560 4 561 </p> 562 </td> 563<td> 564 <p> 565 4 566 </p> 567 </td> 568<td> 569 <p> 570 4 571 </p> 572 </td> 573<td> 574 <p> 575 3 576 </p> 577 </td> 578<td> 579 <p> 580 3 581 </p> 582 </td> 583<td> 584 <p> 585 3 586 </p> 587 </td> 588<td> 589 <p> 590 3 591 </p> 592 </td> 593<td> 594 <p> 595 3 596 </p> 597 </td> 598<td> 599 <p> 600 3 601 </p> 602 </td> 603<td> 604 <p> 605 4 606 </p> 607 </td> 608<td> 609 <p> 610 4 611 </p> 612 </td> 613<td> 614 <p> 615 4 616 </p> 617 </td> 618</tr> 619<tr> 620<td> 621 <p> 622 halley_iterate 623 </p> 624 </td> 625<td> 626 <p> 627 4 628 </p> 629 </td> 630<td> 631 <p> 632 3 633 </p> 634 </td> 635<td> 636 <p> 637 3 638 </p> 639 </td> 640<td> 641 <p> 642 3 643 </p> 644 </td> 645<td> 646 <p> 647 3 648 </p> 649 </td> 650<td> 651 <p> 652 2 653 </p> 654 </td> 655<td> 656 <p> 657 2 658 </p> 659 </td> 660<td> 661 <p> 662 3 663 </p> 664 </td> 665<td> 666 <p> 667 3 668 </p> 669 </td> 670<td> 671 <p> 672 3 673 </p> 674 </td> 675<td> 676 <p> 677 3 678 </p> 679 </td> 680<td> 681 <p> 682 3 683 </p> 684 </td> 685</tr> 686<tr> 687<td> 688 <p> 689 schroder_iterate 690 </p> 691 </td> 692<td> 693 <p> 694 4 695 </p> 696 </td> 697<td> 698 <p> 699 3 700 </p> 701 </td> 702<td> 703 <p> 704 3 705 </p> 706 </td> 707<td> 708 <p> 709 3 710 </p> 711 </td> 712<td> 713 <p> 714 3 715 </p> 716 </td> 717<td> 718 <p> 719 2 720 </p> 721 </td> 722<td> 723 <p> 724 2 725 </p> 726 </td> 727<td> 728 <p> 729 3 730 </p> 731 </td> 732<td> 733 <p> 734 3 735 </p> 736 </td> 737<td> 738 <p> 739 3 740 </p> 741 </td> 742<td> 743 <p> 744 3 745 </p> 746 </td> 747<td> 748 <p> 749 3 750 </p> 751 </td> 752</tr> 753</tbody> 754</table></div> 755<p> 756 Interestingly this function is much more resistant to a poor initial guess 757 when using derivatives. 758 </p> 759</div> 760<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 761<td align="left"></td> 762<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 763 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 764 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 765 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 766 Daryle Walker and Xiaogang Zhang<p> 767 Distributed under the Boost Software License, Version 1.0. (See accompanying 768 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>) 769 </p> 770</div></td> 771</tr></table> 772<hr> 773<div class="spirit-nav"> 774<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> 775</div> 776</body> 777</html> 778
