|
Home | Libraries | People | FAQ | More |
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.