Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

The Effect of a Poor Initial Guess

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:

Initial Guess=

-500% (≈1.323)

-100% (≈3.97)

-50% (≈3.96)

-20% (≈6.35)

-10% (≈7.14)

-5% (≈7.54)

5% (≈8.33)

10% (≈8.73)

20% (≈9.52)

50% (≈11.91)

100% (≈15.87)

500 (≈47.6)

bracket_and_solve_root

12

8

8

10

11

11

11

11

11

11

7

13

newton_iterate

12

7

7

5

5

4

4

5

5

6

7

9

halley_iterate

7

4

4

3

3

3

3

3

3

4

4

6

schroder_iterate

11

6

6

4

3

3

3

3

4

5

5

8

As you can see bracket_and_solve_root 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.

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:

Initial Guess=

-500% (≈20.6)

-100% (≈61.81)

-50% (≈61.81)

-20% (≈98.9)

-10% (≈111.3)

-5% (≈117.4)

5% (≈129.8)

10% (≈136)

20% (≈148.3)

50% (≈185.4)

100% (≈247.2)

500 (≈741.7)

bracket_and_solve_root

11

5

5

8

8

7

7

8

9

8

6

10

newton_iterate

4

4

4

3

3

3

3

3

3

4

4

4

halley_iterate

4

3

3

3

3

2

2

3

3

3

3

3

schroder_iterate

4

3

3

3

3

2

2

3

3

3

3

3

Interestingly this function is much more resistant to a poor initial guess when using derivatives.


PrevUpHomeNext