On Convergence Rates of RootSeeking Methods

01302017, 08:05 PM
Post: #1




On Convergence Rates of RootSeeking Methods
Hi All,
I posted my study on convergence rates for rootseeking methods. Click here to download the ZIP file that contains the report, as a PDF file, and the macroenabled 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 

01302017, 10:06 PM
Post: #2




RE: On Convergence Rates of RootSeeking Methods
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. César  Information must flow. 

01312017, 06:20 AM
Post: #3




RE: On Convergence Rates of RootSeeking Methods
(01302017 10:06 PM)emece67 Wrote: Thanks a lot, Namir, for your work. 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 

01312017, 01:26 PM
Post: #4




RE: On Convergence Rates of RootSeeking Methods
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, 

01312017, 03:33 PM
Post: #5




RE: On Convergence Rates of RootSeeking Methods
(01312017 01:26 PM)RMollov Wrote: Hi Namir, From the Forums home page, where there is a short description for each subforum: "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. 

01312017, 03:54 PM
Post: #6




RE: On Convergence Rates of RootSeeking Methods
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. César  Information must flow. 

01312017, 04:57 PM
(This post was last modified: 01312017 04:58 PM by Pekis.)
Post: #7




RE: On Convergence Rates of RootSeeking Methods
Very interesting and not out of topic. Thanks Namir


01312017, 07:56 PM
Post: #8




RE: On Convergence Rates of RootSeeking Methods
(01312017 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 

01312017, 08:12 PM
Post: #9




RE: On Convergence Rates of RootSeeking Methods
(01302017 10:06 PM)emece67 Wrote: Thanks a lot, Namir, for your work. Convergene rate dependents on the numbers of Digits used? Mmmh ... 

01312017, 08:41 PM
(This post was last modified: 01312017 08:55 PM by brickviking.)
Post: #10




RE: On Convergence Rates of RootSeeking Methods
(01312017 01:26 PM)RMollov Wrote: Hi Namir, Of course! It includes mathematics, experimentation and just plain old science. (01312017 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. (01312017 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 HP34C could calculate the Gamma function. I'd never seen another calculator do that. At the time I called it noninteger 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 nutsandbolts (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) 

01312017, 09:01 PM
(This post was last modified: 01312017 09:06 PM by emece67.)
Post: #11




RE: On Convergence Rates of RootSeeking Methods
(01312017 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. César  Information must flow. 

01312017, 10:05 PM
Post: #12




RE: On Convergence Rates of RootSeeking Methods
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 rootseeking 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 

01312017, 10:22 PM
Post: #13




RE: On Convergence Rates of RootSeeking Methods
(01312017 09:01 PM)emece67 Wrote:(01312017 08:12 PM)JurgenRo Wrote: Convergene rate dependents on the numbers of Digits used? Mmmh ... That might be acceptable ... Juergen 

02012017, 03:38 AM
Post: #14




RE: On Convergence Rates of RootSeeking Methods  
02092017, 08:33 AM
(This post was last modified: 02092017 08:35 AM by RMollov.)
Post: #15




RE: On Convergence Rates of RootSeeking Methods
Ok I stand corrected
Apparently I was wrong Won't happen anymore 

02092017, 02:32 PM
Post: #16




RE: On Convergence Rates of RootSeeking Methods
(02092017 08:33 AM)RMollov Wrote: Ok I stand corrected No need to apologize. We are all tempted to regard the collection of legacy rootseeking methods (Bisection, FalsePoisson, 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 rootseeking algorithms. This progress seem to validate Voltaire's famous quote "The better is the enemy of the good". Namir 

03022018, 10:38 AM
Post: #17




RE: On Convergence Rates of RootSeeking Methods
Very interesting topic.
Is there any possible way to program the root seeking on the HP12C ....? Gamo 

03052018, 03:52 AM
(This post was last modified: 03052018 03:54 AM by Paul Dale.)
Post: #18




RE: On Convergence Rates of RootSeeking Methods
(03022018 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 

03052018, 02:13 PM
Post: #19




RE: On Convergence Rates of RootSeeking Methods
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 GaussSeidel relaxation for linear equations or (with even number of elements) a RedBlack relaxation. The RedBlack has the same asymptotic convergence rate as the GaussSeidel but a better average rate. Thus is converges more quickly at the beginning. For those unfamiliar with RedBlack: 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. 

03052018, 10:46 PM
(This post was last modified: 03052018 11:53 PM by Valentin Albillo.)
Post: #20




RE: On Convergence Rates of RootSeeking Methods
(03022018 01:00 PM)Mike (Stgt) Wrote: Hi, Namir 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. . 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)