On Convergence Rates of Root-Seeking Methods

[Namir]

Hi All,

I posted my study on convergence rates for root-seeking methods. Click here to download the ZIP file that contains the report, as a PDF file, and the macro-enabled Excel files that I used in the study.

My study looks at the effective convergence rate that manifests itself in the entire iteration process (from the initial guess to the refined root guess that meets the tolerance requirements) AND also the convergence rate calculated for each iteration. It seems that the theoretical convergence rate manifests itself ONLY FOR A FEW ITERATIONS .. which is very disappointing to me. I always thought that after the first few iterations, the root refinement process reaches a steady state which adheres to the theoretical convergence rate. This is NOT the case, unless the initial root guess is very very close to the root. I also discovered that using divided difference approximations for the derivatives slows down the convergence rate a bit.

Namir

[emece67]

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.

[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

[RMollov]

Hi Namir,
I really appreciate your input in this forum, but is this really a home for such topics?
IMHO solvers in hp calculators do whatever they are supposed to and I don't see room for improvement here given the fact those calculators are no longer made and hardly used. I for one have used them to get something done and never cared about how it's done internally at low level. Even if I did I don't think I could change anything.
Don't get me wrong, I only think topics like this one should reside elsewhere.

Best regards,

[BartDB]

(01-31-2017 01:26 PM)RMollov Wrote:  Hi Namir,
I really appreciate your input in this forum, but is this really a home for such topics?
IMHO solvers in hp calculators do whatever they are supposed to and I don't see room for improvement here given the fact those calculators are no longer made and hardly used. I for one have used them to get something done and never cared about how it's done internally at low level. Even if I did I don't think I could change anything.
Don't get me wrong, I only think topics like this one should reside elsewhere.

Best regards,

From the Forums home page, where there is a short description for each sub-forum:
"General Forum
Including all HP calculators except the HP Prime. Also HP news, general math and science etc."

As Namir's discussion falls under "general maths", it is quite at home here.

Regards.

[emece67]

Namir's findings can be applied to new solvers to be used on many programmable hp (or not) calculators. The venerable 41 benefits greatly with new modules developed by people at this forum that use algorithms and methods not used previously in any hp model. I do also think that there's a place here for threads like this one.

Regards.

[Pekis]

Very interesting and not out of topic. Thanks Namir

[JurgenRo]

(01-31-2017 04:57 PM)Pekis Wrote:  Very interesting and not out of topic. Thanks Namir

Agreed! But still, that is what I meant, Namir. You cannot modify a mathematical scheme by your will and conclude that the modified scheme will have the same properties just because the original had. Mathematics is not that simple.
Anyways an interesting thread. Thanks a lot!
Juergen

[JurgenRo]

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

Convergene rate dependents on the numbers of Digits used? Mmmh ...

[brickviking]

(01-31-2017 01:26 PM)RMollov Wrote:  Hi Namir,
I really appreciate your input in this forum, but is this really a home for such topics?

Of course! It includes mathematics, experimentation and just plain old science.

(01-31-2017 01:26 PM)RMollov Wrote:  IMHO solvers in hp calculators do whatever they are supposed to and I don't see room for improvement here given the fact those calculators are no longer made and hardly used.

While I agree for original calculators with no real expandability, for the later generations (HP41–50G) you could create modules/libraries/programs with better functions to supplement the existing ones. I've already seen this in play with my HP50G, and even seen a Gamma function implemented for the Casio 9750G+, and I'm sure you've seen the HP41CL project. As a previous poster has already asserted, nothing's stopping future developments in HP calculator space.

(01-31-2017 01:26 PM)RMollov Wrote:  I for one have used them to get something done and never cared about how it's done internally at low level. Even if I did I don't think I could change anything.

Understanding the limits of what a venerable HP28C can do will make you aware how far you can push some calculations before you eventually have to give up and step up to "big iron". I've been intrigued about internal calculator functions and their limits since I first discovered that the HP-34C could calculate the Gamma function. I'd never seen another calculator do that. At the time I called it non-integer primes, but since discovered its proper name. I was fascinated that I could put in 3.1415 into n! and actually get a result.

I also investigate accuracy for the calculators that I have; it's fun to know some of the limits of what a calculator can do. I grant that yes, they're there to pick up and use without worrying about the nuts-and-bolts (or we'd all be writing our own WP43Q on a Raspberry Pi with a LCD display with an embedded Smalltalk), but it's interesting to realise that earlier calculators were only a couple of magnitudes better than a really good sliderule operator. Programmability and "modern" methods of manufacture changed the game in this, I reckon.

(Post 53, after a long hiatus of post counters)
--
Cheers, BrickViking (a.k.a. DrSmokey)

[emece67]

(01-31-2017 08:12 PM)JurgenRo Wrote:  Convergene rate dependents on the numbers of Digits used? Mmmh ...

Computational order of convergence. The "bare" order of convergence is what it is, but the COC, I think, depends on the computation.

Regards.

[Namir]

My opening message in this trhead provides a link to my website where all the files that I created for the study reside.

I appreciate the support of many and I agree that we can and should talk about numerical algorithms in this forum.

Until abut the year 2000, I did not question much various algorithms. I simply used them. Since 2000, I began to ask questions about the assumptions and mechanisms of various root-seeking algorithms (from Bisection and up). I discovered it was very fun to come up with improvments. Looking at convergence rates is a real eye opener for me. I learned much and replaced simplistic impressions from the past with new pieces of knowledge.

I think it's fun to push the limits of things and dare look at established concepts from a new angle.

Namir

[JurgenRo]

(01-31-2017 09:01 PM)emece67 Wrote:  

(01-31-2017 08:12 PM)JurgenRo Wrote:  Convergene rate dependents on the numbers of Digits used? Mmmh ...

Computational order of convergence. The "bare" order of convergence is what it is, but the COC, I think, depends on the computation.

Regards.

That might be acceptable ...
Juergen

[Claudio L.]

(01-31-2017 10:05 PM)Namir Wrote:  I think it's fun to push the limits of things and dare look at established concepts from a new angle.

Namir

It's fun, educational and very much on topic. I read your posts with interest.

[RMollov]

Ok I stand corrected
Apparently I was wrong
Won't happen anymore

[Namir]

(02-09-2017 08:33 AM)RMollov Wrote:  Ok I stand corrected
Apparently I was wrong
Won't happen anymore

No need to apologize. We are all tempted to regard the collection of legacy root-seeking methods (Bisection, False-Poisson, Secant, Newton, and Halley) to offer a good choice. But human desire to improve and invent has generated, especially in the last few decades, many new root-seeking algorithms. This progress seem to validate Voltaire's famous quote "The better is the enemy of the good".

Namir

[Gamo]

Very interesting topic.
Is there any possible way to program the root seeking on the HP-12C ....?

Gamo

[Paul Dale]

(03-02-2018 01:00 PM)Mike (Stgt) Wrote:  to compute sqare roots up to 100'000 digits and more?

Newton's method is quite widely used. A good initial estimate is required. The usual double precision hardware sqrt function is a start and it might even be good enough.

It might be worth looking into Halley's method, which has cubic convergence, but needs the second derivative which is a constant here. However, I doubt the extra computation would be worthwhile. I think higher order Householder methods will fail because all of the higher order derivatives are zero.

You could look for Karatsuba and FFT square roots. I remember them being Newton's method with improvements to the basic arithmetic operations.

Quote:And what for 3rd and 4th roots?

For cube root and above, I'd use Newton's because the arithmetic stays simple. Higher order methods might produce a benefit but again I doubt the extra computation is worthwhile.

Quote:For the later, would a sqrt(sqrt()) be faster than a special 4th root process?

I doubt it. Iterating a = \( \frac{1}{4} \left( a + \frac{z}{a^3} \right) \) once versus iterating \( \frac{1}{2} \left( a + \frac{z}{a} \right) \) twice. Crudely, it is trading two multiplies for a divide and an addition. The latter is likely to be the more difficult. I'm assuming the divide by 2 or 4 is free, if not it is worse for the double square root.

I think that sqrt(sqrt()) would be faster than using a y^x operation.

Quote:Would be a CORDIC algorithm for so many digits outreach simple Newton (iterating a = .5 * (a + z / a))?

Not a chance. CORDIC is linear in the number of digits, Newton quadratic. CORDIC might be usable to provide a sufficiently accurate starting point for Newton's method however.


Pauli

[ttw]

Very often, the converge rate is asymptotic. It holds either for very large N or for a guess close enough. Newton's method often converges linearly until the result is much closer to one root than the other; then it becomes quadratic.

A few "better" estimates are available. For example, one can use a Gauss-Seidel relaxation for linear equations or (with even number of elements) a Red-Black relaxation. The Red-Black has the same asymptotic convergence rate as the Gauss-Seidel but a better average rate. Thus is converges more quickly at the beginning.

For those unfamiliar with Red-Black: If the matrix represents a diffusion process, one can treat an even number of points as being colored like a checkerboard. The red sites depend only on themselves and the black sites and vice versa. By alternately solving for the red sites in terms of the black and vice versa, one gets quicker convergence.

[Valentin Albillo]

(03-02-2018 01:00 PM)Mike (Stgt) Wrote:  Hi, Namir

what would you as root finding expert recommend to compute sqare roots up to 100'000 digits and more?

Sorry to intrude. You may want to have a look at this PDF document:

AMS Journals - Computing the square root of 2 to 1,000,000 digits

where they discuss the methods used in the past to compute square roots to many thousand places and the particular one they used to compute the square root of 2 to in excess of one million digits.

Also, to check your very own implementation simply google "square root of 2 to 1 million digits" and you'll immediately find a link to the full result.

Regards.
V.
.