On Convergence Rates of Root-Seeking Methods

[Namir]

(01-30-2017 10:06 PM)emece67 Wrote:  Thanks a lot, Namir, for your work.

I was also a bit shocked when the convergence orders I computed were usually lower than the expected ones. After some trials I assumed that I was working with too many digits. If, for example, one is working with 10 digits & with a 4th order method that, supposedly, multiplies the number of correct digits by 4 on each iteration (provided the method is actually converging to a root), you will only see such order if your guess has 2 or 3 correct figures. If the guess has less correct figures the method is not yet converging and does not show the expected convergence rate, if your guess has more that those correct figures, then the method cannot show such order because it "exhausts" all available digits (I think this is the reason for you not seeing the expected order in the last iterations).

I was, at last, able to see the theoretical convergence orders when I switched to 1024 digits.

Regards.

Excellent comments and very good explanation. I learned a few interesting things of the study I did. First, the approximations that I used for the derivative, slowed the convergence to some extent. Second, I often use initial guesses that do not share any digits with the actual roots. You explain very well how that affects convergence. Third lesson learned is that the function, its roots, proximity of the roots from each other, changes in the slope (first derivative) values, and changes in the curvature (second derivative) values are all factors that greatly influence convergence rates. Add to all that the proverbial monkey wrench of fundamental problems with reaching the root (extended range of x near the root where the first derivative is near zero, or parallel function asymptotes around the root, that cause refined guess values to cycle).

Finding test functions used to calculate convergence rates and yield good results is not a trivial process.

Namir