Talk:Root-finding algorithms

Jacoby's method

This method is now described at Jacoby's method. -- Jitse Niesen (talk) 13:04, 10 January 2006 (UTC)

This method is now described at Durand–Kerner method. -Stelio (talk) 09:48, 27 September 2017 (UTC)

I entered the section 'how to solve an algebraic equation'. For discussion see User talk:Bo Jacoby. The discussion items should perhaps be moved to this place? Note that the Wilkinson illconditioned equation is readily solved by 'my' method. Bo Jacoby 07:27, 13 September 2005 (UTC)

Copied from User talk:Bo Jacoby:

[...] I have some questions about your addition to root-finding algorithm. I don't remembering seeing this method before, but that's does not say much as I never really studied the numerical solution of polynomial equations. Do you have some reference for this method (this is required for verifiability)? Is there some analysis; for instance, does the iteration always converge, and is anything known about the speed of convergence? [...] Cheers, Jitse Niesen (talk) 22:20, 12 September 2005 (UTC)

Hello Jitse. Thank you very much for your comment on my article on root-finding algoritm. You request a reference for verifiability and some analysis, and you ask whether the method always converge and what is the speed? I agree that such theoretical stuff would be nice, but alas I have not got it. I have got a lot of practical experience with the method. It was taught in an engineering school in Copenhagen for more than 5 years, and the students implemented it on computer and solved thousands of examples. I have not got any nontrivial reports on nonconvergence. So much for verifiability. Does the method always converge ? The answer is no for topological reasons. This is why. Consider initial guess p,q,r,s converging towards roots P,Q,R,S. For reasons of symmetry the initial guess q,p,r,s will converge towards Q,P,R,S. Both solutions are satisfactory, but they are not the same point in four-dimensional complex space. Consider f(t)=(1-t)(p,q,r,s)+t(q,p,r,s), 0<t<1. This line joins the two initial guesses. Note that the iteration function, g, is continuous, no matter how many times we iterate. We don't iterate an infinite number of times. Let A and B be open disjoint sets such that A contains (P,Q,R,S) and B contains (Q,P,R,S) and such that g(f(0)) is in A and g(f(1)) is in B. But no continuous curve can jump from A to B. So for some value of t, 0<t<1, g(f(t)) is outside both A and B, and so the method does not converge everywhere.

I do not think that this immature argument belongs to a wikipedia article.

However, I believe that the method converges 'almost everywhere' in the sense of Lebesque, but I have no proof. Nevertheless, the question of convergence is not the right question to pose. As you only iterate a finite number of times, you will not necessary get close to a solution even if the method converges eventually. So, the method is good for no good theoretical reason! The solutions are attracting fixpoints for the iteration function. That's all.

Bo Jacoby 07:12, 13 September 2005 (UTC)

End of copy

I suggest we cut off the method then. There are no references, there is no guarantee that the method converges, if it converges it is slow (fixed point iteration), and the section ==How to solve an algebraic equation== is an odd addition to otherwise well-written first two sections, which summarize a great variety of methods, and I believe almost all (if not all) are more sophisticated and converge faster than that outlined in that section. Oleg Alexandrov (talk) 18:53, 6 January 2006 (UTC)

It is a good idea that the section be moved to an article of its own. It is not a good idea to cut off the method based on prejustices regarding speed and convergence. Many people have good experience by the method. Most people have no experience. Nobody have bad experience. Bo Jacoby 13:12, 9 January 2006 (UTC)

Yeah, I believe moving it out it is a good idea. Go for it. :)

But how are you going to call the new article? Again, you should worry about getting references. Either way, I plan to remove this method from this article, the method is not worth the attention it is given in the article for its value. Oleg Alexandrov (talk) 16:19, 9 January 2006 (UTC)

None of the other methods of the article constitute a general method for computing all the roots of any polynomial in a hurry. Newton and Laguerre find only one root which may not be the interesting one. Ruffini makes additional assumptions, and the Eigenvalue_algorithm#Power_iteration is slow. Try the different methods on a simple example like x³−2x = 0 and get some experience. Then you will agree that the method is worth your attention. What name for the method will you suggest? Bo Jacoby 07:49, 10 January 2006 (UTC)

It is not known when your method works and when it does not, so such praise is not applicable. Oleg Alexandrov (talk) 16:51, 10 January 2006 (UTC)

I moved the method to Jacoby's method. Bo mentioned one reference, albeit a very obscure one. I have to admit that I'm reluctant to delete it from Wikipedia mainly because I'm rather intrigued by the method. -- Jitse Niesen (talk) 13:04, 10 January 2006 (UTC)

Thanks a lot Jitse! You will find that the method is very fast! Bo Jacoby 13:53, 10 January 2006 (UTC)

Probably almost global convergence

I did not expect the method to converge for all initial guesses, though that would be great; in fact, the basic result I was wondering about is whether it converges for initial guesses sufficiently close to the exact solution, which apparently it does because the solutions are attractive fixed points of the iteration map. By the way, the first case is called global convergence, and the second case local convergence; I guess I should have been more precise in my question.

I agree, the really interesting question is not about convergence (after an infinite number of iterations), but things like: how often will the method yield a decent result, when applied to polynomials which typically occur in practice, and with starting guesses that are typically used? However, the convergence question is easier to pose and to answer.

I am thinking of putting 'your' method in a separate article and leave a short summary here, just like other methods like Newton's method. What do you think about this? Of course, we then need a name for the method ... any ideas? Perhaps I'll go to the library and see whether I can find anything similar. -- Jitse Niesen (talk) 15:02, 13 September 2005 (UTC)

1. The method has probably almost global convergence. Further study might reveil that it has almost global convergence, which is far better than local convergence, but it will certainly not have global convergence for the reason given above.
2. Your idea of a separate article is great.
3. Associate professor Agnethe Knudsen called the method "Bo Jacobys metode" in her lecture notes "Numeriske Metoder", Københavns Teknikum. I know of no better name. I do not believe that I was the first to discover that the iteration formula has local convergence, but I think that I was the first to conjecture the "almost global convergence", meaning that is a reliable practical method for the numerical solution of any algebraic equation.

Thank you for your interest. Bo Jacoby 09:53, 19 September 2005 (UTC)

Quadratic equations

Should we add the method of solving "quadratic" equations using "discriminants" to this article? i.e., ax^2 + bx + c = 0

x1 = (-b + sqrt(b^2 - 4ac)) / 2a

x2 = (-b - sqrt(b^2 - 4ac)) / 2a

You might want to include a reference to Quadratic equation in the section Root-finding_algorithm#Finding_roots_of_polynomials Bo Jacoby 09:27, 17 October 2005 (UTC)

The Quadratic Equations isn't an algorithm (it doesn't iterate or contain logical conditionals, so it shouldn't be included as a "root-finding algorithm." Thetwentyone (talk) 18:43, 24 October 2011 (UTC)

Bisection

There has been some editing on the condition that there exists a and b such that f(a)<0 and f(b)>0. It has been changed to that f(a) and f(b) have opposite signs. Nobody said that a<b, so the two formulations are logically equivalent. Bo Jacoby 13:19, 31 October 2005 (UTC)

When and where

Information on the assumptions made for each method to work needs to improve, The Newton-Raphson method is made to look like it works for all F, wich is hardly the case(The simplest counter example would be a funktion where the curve increases as x approches the rootpoint. //Nobody.

If the 'curve increases as x approches the rootpoint', then the function does not have a derivative at the root, which was explicitely assumed. Bo Jacoby 14:53, 31 December 2005 (UTC)

Clarification of Jacoby's Method

The explanation, while easy to understand, leaves me wondering about one part that may need to be clarified: when performing the substitutions, which values of q,r,s,... should be used? For example, after completing the first substitution and moving on to the second, what p value should be used: the value that just finished being calculated, or the value from before any substitutions began?

Darthmarth37 03:53, 24 January 2006 (UTC)

Thanks for your interest and for asking. The text should not be ambiguous, so I will put in some semicolons after the substitution formulas to clarify that they are to be executed one by one. The short answer to your question is that it doesn't really matter, as both interpretations of the description solves the equation. However, an improved value of p should be used as soon as possible, so my intention was that the value of p just finished is input in the calculation of the next value of q etc. If you use an array programming language, then all the substitutions are done together, and the input values of p,q,r,s are not the same as when you use a scalar programming language. But again, it doesn't matter much improving on a solved problem. Bo Jacoby 08:36, 24 January 2006 (UTC)

Removing Ruffini's Method ?

Ruffini's method is not at all a root-finding algoritm as described in the introduction. I will remove the reference from the article. Any objections ? Bo Jacoby 08:58, 24 January 2006 (UTC)

Conditioning

I don't think it's quite correct to say that "the numerical evaluation of polynomials is subject to round-off error, and so finding roots can be ill-conditioned". Any computation is subject to round-off error, but that does not necessarily imply round-off error. Perhaps what was meant is "the numerical evaluation of polynomials can be ill-conditioned, and so finding roots can be ill-conditioned as well". However, I'm not convinced that this is true. Such a statement would at least need a reference. -- Jitse Niesen (talk) 14:33, 24 January 2006 (UTC)

The evaluation of any polynomial close to a root involves the subtraction of almost equal terms, giving loss of precision. Evaluating the polynomial f(x) = x−1.00009 for x = 1.00000 gives the result f(x) = −0.00009 having only one significant digit even if the coefficients and the argument have six significant digits. The computed value of a sum of several terms depend on the order of the computation: (a+b)+c ≠ a+(b+c). Try a = 100001, b = −100000, c = −1.12456, computing both ways with six significant digits. Bo Jacoby 15:12, 24 January 2006 (UTC)

"The evaluation of any polynomial close to a root involves the subtraction of almost equal terms" — not necessarily true; consider for instance f(x) = x. In any case, my problem is that the relation between the conditioning of "evaluating a polynomial" and "finding its root" is as straightforward as the word so in "the numerical evaluation of polynomials is subject to round-off error, and so finding roots can be ill-conditioned" implies. -- Jitse Niesen (talk) 15:52, 24 January 2006 (UTC)

The function f(x) = x is a singleterm expression, a monomial, and not really a a multiterm expression, a polynomial. It is trivial to find the roots of a monomial. Anyway you are right. The meaning of the word 'many' changed from 'three or more' in classic Greek mathematics to 'zero or more' in modern mathematics, to the confusion of many (in the classic sense of the word). The numerical evaluation of the polynomial is the Achilles' heel of root-finding. If you cannot tell the sign of f(x) due to round-off errors, then even bisection doesn't work. Bo Jacoby 08:18, 25 January 2006 (UTC)

I'm not at all convinced that "[t]he numerical evaluation of the polynomial is the Achilles' heel of root-finding". There may well be some truth in it, but I need to see some arguments. The root of f(x) = x−1.00009 can be determined with full precision. That (a+b)+c ≠ a+(b+c) in floating-point arithmetic is well known, but I don't see where exactly it is relevant here.

Be that as it may, I removed "the numerical evaluation of polynomials is subject to round-off error, and so finding roots can be ill-conditioned" because the word so implies a causal relation, and I cannot see this relation. What precisely do you mean with "finding roots can be ill-conditioned"? -- Jitse Niesen (talk) 14:00, 25 January 2006 (UTC)

Why don't we remove that section on round-off error and ill-condition all together. I makes the reader confused and unhappy and the exact meaning is unclear. Bo Jacoby 12:44, 26 January 2006 (UTC)

Apology

I have made a few minor cosmetic amendments, but in case anybody sees my name as an editor on this article I'd like to go on record as saying it needs serious help. I am not leaving it as it should be, but only as it is. Sorry; maybe another day. --KSmrq^T 14:25, 18 May 2006 (UTC)

Hi KSmrq. You wrote that Typical numerical root-finding methods use iteration. There is no numerical root-finding method that does not use iteration, because a finite rational algorithm does not produce irrational roots from rational coefficients and initial guesses. Do you mind removing the word typical ? Bo Jacoby 09:31, 23 May 2006 (UTC)

Yes, I mind, because your point has no validity in finite precision. All our floating point numbers are rational and bounded. Consider a standard algorithm for finding the real roots of a real quadratic equation; it contains no visible iteration in the usual sense. We may argue that the iteration is hidden within the implementation of the square root function, but that's not a fair argument. In terms of complexity theory, the square root is essentially no different from division, and we don't count division as an iteration unless we are explicitly considering arbitrary precision arithmetic. We can build square root into our hardware, or deploy an algorithm in software with no open-ended iteration yet a good-to-the-last-bit guarantee. The article on methods of computing square roots is a bit of a mess and not especially helpful on this point, but one can consult the professional literature. Also supporting the non-iterative view is the fact that many sophisticated numerical algorithms feel free to use a square root as a constant-time step. For example, the Householder transformation used in a QR decomposition must compute the magnitude of a vector, which means using a square root. Therefore, I claim that "all" is incorrect and "typical" should stand. Which is why I made the change in the first place. --KSmrq^T 14:11, 23 May 2006 (UTC)

Merger with the "Finding multiple roots" article

I converted the "Finding multiple roots" article into a redirect to this article. I merged the deleted text into this article with minor changes like changing sections into subsections. You can still reach the talk page of the old article via Talk:Finding multiple roots. To view the history of the old article, switch to this article itself and select "What links here", then click on "Finding multiple roots (redirect page)", then click the "history" tab. JRSpriggs 07:01, 20 May 2006 (UTC)

I now add direct links to the histories of "Finding multiple roots" and its talk page:

http://en.wikipedia.org/w/index.php?title=Finding_multiple_roots&action=history

http://en.wikipedia.org/w/index.php?title=Talk:Finding_multiple_roots&action=history

And I converted the talk page there into a redirect to this talk page. The contents follow in the next subsection. JRSpriggs 08:56, 23 May 2006 (UTC)

Merged talk from "Finding multiple roots" -- Response to Jitse Niesen

Q1. Why did you decide to start a new article, instead of adding an extra section to Root-finding algorithm? I prefer to have a few long articles with a couple of people working on them and correcting each other, rather than spreading out our works on many small articles (but this is partially a matter of taste).
A1. No particular reason. I just thought of this as just another method of finding roots like the other methods which have their own articles. If you want to merge it into the main article in this category, please feel free to do so.

support merger. -lethe ^{talk +} 13:49, 30 April 2006 (UTC)

Q2. Ideally, every article should be supported by a couple of references. Please add one or two. I'm especially interested in references, because it is not clear to me how to compute the gcd in the presence of rounding error. If the example you give in Finding multiple roots is computed with floating-point arithmetic, then the remainder might not be zero.
A2. I am sorry; but this article was based on my memories of a math class I took many decades ago. I do not know of any reference book for it. As for round off errors, I agree that that could be a problem. But I think that it is a problem in determining convergence generally -- you have to make a judgement whether this is close enough to zero that we should assume that it really is zero (or would have been zero, if computations were done with infinite precision). It may mean that the usefulness of this method is restricted -- not only restricted to functions which are presented as polynomials, but to those whose coefficients are given exactly, i.e. symbolically, like (3+sqrt(7))/4. JRSpriggs 12:25, 30 April 2006 (UTC)

If by root-finding we mean numerical root-finding using floating-point computations, then I would really like to see a reference to support this approach, because it only seems suitable for exact computations. Unless such a reference is produced, I would not like to see this merged, because it sounds like questionable advice. However, looking for a common root of a polynomial and its derivative is standard practice in exact computations for algebraic geometry, as one example. If this is the intent, perhaps it should be merged with a different article. It doesn't stand well on its own, whatever the merit of its content. --KSmrq^T 13:24, 18 May 2006 (UTC)

I merged this article into Root-finding algorithm. Any additional talk about "Finding multiple roots" should be conducted at Talk:Root-finding algorithm. JRSpriggs 08:39, 21 May 2006 (UTC)

End merged talk from "Finding multiple roots

"Finding multiple roots" is not a root-finding algorithm and so it does not belong here. Exact algebra on integers should be finished before the problem is forwarded to approximate root-finding using floating point numbers. Bo Jacoby 10:13, 28 July 2006 (UTC)

Request for comments on Splitting circle method

Hi, while reading the relevant papers of Schönhage and Pan in the last few days I tried to assemble things I understood or knew already into a short description of the method. An accessible formulation of the main result is still missing. If I find a short way to formulate it, I will add it later.--LutzL 17:20, 27 July 2006 (UTC)

Halley's method

Perhaps someone might mention Halley's method - a considerable improvement on Newton's. By comparison, the overhead is calculation of the second derivative of the function at the initial approximation point ... and higher order methods in a similar vein are possible too! If noöne else does it, I may add it. (Note: Halley, of comet fame.) Hair Commodore 20:09, 19 January 2007 (UTC)

If you have a reference, go ahead and create an article about it. Put it in this category Category:Root-finding algorithms when you first start on the article so that it does not get lost in the system. JRSpriggs 06:19, 20 January 2007 (UTC)

No - at this precise moment, I don't have a reference for it - but it can be found in the French "section" of Wikipedia! (Unfortunately, the article in question - and others associated with it, such as that for Householder's method(s) - does not have a "language translation box".) Hair Commodore 19:33, 21 January 2007 (UTC)

Among others, it is described on Xavier Gourdons Newton page, section "Cubic iteration". Use the Postscript-version linked to at the top for a correct display of formulas.--LutzL 06:45, 22 January 2007 (UTC)

Could it be another name for Laguerre's method? If you can give me a link to the French article and it is not too wordy, I might be able to translate it to English. JRSpriggs 07:07, 22 January 2007 (UTC)

No, Laguerre is "taylored to polynomials". Halley and generally Householder methods are for general real functions. The webpage I gave, although from a french mathematician, is in english. Dates and references are provided. Further reading fr:Itération de Halley and from there [1].--LutzL 10:20, 22 January 2007 (UTC)

OK. I copied over the French version and translated it (more or less). There were some errors which I had to fix. Also it needs more detail, especially an explanation of why its convergence is cubic. It is at Halley's method. JRSpriggs 13:10, 22 January 2007 (UTC)

Root finding is equation solving?

Conversely, any equation can take the canonical form f(x) = 0, so equation solving is the same thing as computing (or finding) a root of a function.

(from the article, 3rd paragraph)

This is only true of equations which have the form f(x) = g(x). Implicit equations don't always have a canonical f(x) = 0 form. —Preceding unsigned comment added by Mgsloan (talk • contribs) 21:51, 9 November 2007 (UTC)

Please provide an example. Bo Jacoby 00:02, 11 November 2007 (UTC).

This image shows the graph of cos(y arccos sin|x| + x arcsin cos|y|).

.

Lets say we made this into an equation by setting it equal to 0.3. This would be equivalent to tracing out a particular slice of this image. There's no way to write this as f(x) = 0 without leaving out huge swaths of the range. Perhaps the article should specify that they are equations of one variable? Mgsloan 20:59, 12 November 2007 (UTC)

What is the problem in writing f(x,y)=0. Noone said either that the x in the introduction could not be a vector of variables. The function f could be vector valued as well. So yes, there are root sets that are positive dimensional. If one tried hard enough, one could surely come up with a function with a fractal root set as well. Yours is not fractal, since your function is locally Lipschitz. Although it is a nice picture--LutzL 07:53, 13 November 2007 (UTC)

Solver = root-finder?

I don't have any references at hand, but in my experience solver (computer science) normally means root-finder. I would re-direct solver to this article, because solver (computer science) is basically listing an arbitrary selection of numerical problems. 205.228.104.143 (talk) 04:09, 17 September 2009 (UTC)

I strongly oppose to the merger. If you've only found that particular class of solvers, it doesn't mean there aren't many other classes included under the same general definition. What we need is expanding the article about the general concept of a solver program, not redirecting it to an article covering only a subset of it. In particular, logic solvers have nothing to do with numerical methods for finding a root of a function - at least if you don't want to invoke the formal equivalence between logic and mathematics. Diego (talk) 11:53, 17 September 2009 (UTC)

OK, so basically you are saying that any algorithm is a solver? Could be, but either way we need references. 221.47.185.5 (talk) 13:19, 19 September 2009 (UTC) Incidentally, I never heard the phrase "logic solver", do you mean "automatic theorem prover"? 221.47.185.5 (talk) 13:26, 19 September 2009 (UTC)

I'm saying that any software designed around a search algorithm for its main purpose is a solver. There are algorithms that don't follow that structure, but anything exploring a solution space constructing a solution at each step would qualify.

An automatic theorem prover is one kind of logic solver, which is one kind of solver, which is one kind of algorithm. Clearer? And any reference in the AI literature will disqualify this proposed merger that tries to present solvers exclusively as numerical methods for function roots. Diego (talk) 23:17, 19 September 2009 (UTC)

Thanks, I have a few questions.

1. Is a root finder a search algorithm? I can't see any link from one article to the other.
2. "There are algorithms that don't follow that structure" - This is probably getting a bit epistemological, but could you please offer an example? All iterative algorithms perform a search in a solution space given an input that encodes a problem. So is it correct to say iterative algorithm = search algorithm? Is therefore solver = implementationOf(iterative algorithm) = implementationOf(search algorithm)?
3. "An automatic theorem prover is one kind of logic solver" - what other kinds are there? It would be nice to start a logic solver stub - and reference it.

This discussion revolves around terminology so we really need some references, otherwise it's a bit pointless. 221.47.185.5 (talk) 04:11, 20 September 2009 (UTC)

Finding papers that directly address the definition of Solvers is difficult, all seem devoted to describe one particular strategy or other. So far I've found this paper Computer science as empirical inquiry: Symbols and search by A Newell, HA Simon - 1976, and I'm skimming through it. Diego (talk) 08:35, 21 September 2009 (UTC)

Thanks. I agree it's a hard thing to reference. I'm going to give it a try myself in 2 days' time.

By the way, I noticed that Iterative method seems to cover only root-finding (ironically without referencing this article until I added the link). 221.47.185.5 (talk) 10:24, 21 September 2009 (UTC)

OK, I can't find any reference to back what I thought was understood to be a solver in numerical analysis. I removed the merge proposals, but I think this discussion was fruitful, in that it identified some links and some (open) questions - see above. Thanks. 122.26.120.146 (talk) 01:49, 23 September 2009 (UTC)

Bernoulli method

The Bernoulli referred to is Daniel for clarity. His method is described in the book Mathematics and Computers by Stibitz and Larrivee (1957),pp 77-79.--Billymac00 (talk) 03:34, 13 April 2010 (UTC)

Fixed Point Iteration

Why isn't fixed point iteration mentioned in this article ? — Preceding unsigned comment added by 168.96.204.43 (talk) 17:45, 29 June 2011 (UTC)

What do you have in mind? Bo Jacoby (talk) 06:40, 30 June 2011 (UTC).

@Bo Jacoby: Probably the user meant iteration $x_{k+1}:=g(x_{k})$ to solve the equation $x=g(x)$, as described e.g. in [2]. I second the request for it to be included in the article. I think this method is important to know to see a broader picture: for example, the gradient descent can be interpreted as the simple fixed point iteration method applied to find a zero of the first derivative, in which the step size $s$ should be chosen small enough to guarantee the convergence condition $|sg'(x)|<1$. AVM2019 (talk) 21:56, 14 September 2020 (UTC)

Vincent-Uspenski-Collins-Akritas-Zimmerman

I'm all for giving the Mrs. Budan, Fourier and Vincent, and also Mr. Akrita's work at reconstructing this result, all their due respect. However, the paragraph discussing this history is much too long and detailed for an overview that gives the other methods only one or two sentences. I'm for shortening it to mention that the recent Collins-Akritas method conforms to the original idea of Mr. Vincent in using continued fractions, while the Zimmerman method uses the idea of Möbius transforms for a bisection-exclusion scheme. By the way, what about the bisection-exclusion scheme of Yakoubsohn/Dedieu?--LutzL (talk) 19:14, 19 December 2013 (UTC)

The paragraph is dense, but it's OK. I'm not opposed to giving other methods more detail. Glrx (talk) 23:50, 20 December 2013 (UTC)

It is not the detail of the methods that I oppose, but that the controversy about the origin and content of Vincents method is described in that much detail. This belongs in the history section of the method articles, not in the overview.--LutzL (talk) 12:55, 21 December 2013 (UTC)

@LutzL: I fully agree with you. Moreover the present version hides the main facts: a/ The methods based on Descartes rule of signs are, in practice, much faster than Sturm's. b/ They (at least Rouillier-Zimmermann, as implemented in Maple) allow to solve routinely polynomial of degree up to 1000 with coefficients up to 1000 decimal digits. c/ This make them competitive with purely numerical methods. The history of this paragraph is as follows: Finding in the article the wrong assertion that these methods are to slow to be used in practice, I have rewritten this paragraph in order to emphasize these facts, talking only on Rouillier-Zimmerman variant of "Uspenski algorithm". Then Akritas himself edited the article to emphasize his own terminology and introduce his variants of the method. Lacking of time for reading the original articles in view of a neutral presentation and knowing the usual aggressive behavior of Akritas, I gave up. I'll support you if you edit the paragraph as you suggest. D.Lazard (talk) 13:54, 21 December 2013 (UTC)

OK, just a quick look again, and the debate on the name in the first sentence is pointless. First sentence:

The algorithm for isolating the roots, using Descartes' rule of signs and Vincent's theorem, had been originally called modified Uspensky's algorithm by its inventors Collins and Akritas. After going through names like "Collins-Akritas method" and "Descartes' method" (too confusing if ones considers Fourier's article), it was finally François Boulier, of Lille University, who gave it the name Vincent-Collins-Akritas (VCA) method, p. 24, based on the fact that "Uspensky's method" does not exist and neither does "Descartes' method".

Change to

The algorithm for isolating the roots using Descartes' rule of signs and Vincent's theorem, called the Vincent-Collins-Akritas (VCA) method, was developed by Collins and Akritas.

It keeps the basis, the guy who named it, and the inventors. It dumps the details of the name debate. OK? Glrx (talk) 17:11, 21 December 2013 (UTC)

It's a mess. The most important information -- for the present article -- of the lengthy paragraph is buried somewhere in the middle. It's that there is a continued fraction method (VAS) dating back to Vincent and a bisection-exclusion method (VCA) apparently (not) invented by Uspensky, taken up by Collins/Akritas before they rediscovered the original wisdom of the cont.fract. approach and then efficiently implemented by Rouillier/Zimmermann.

Both methods parametrize an interval $[{\tfrac {a}{b}},{\tfrac {c}{d}})$ using some variation of ${\tfrac {a+bx}{c+dx}}$ with $x\in [0,\infty )$ and examine the polynomial in question using $(c+dx)^{\deg p}\,p({\tfrac {a+bx}{c+dx}})$ either with the Descartes test for 0, 1 or possibly many real roots or the Budan test to localize sub-intervals possibly containing roots, limiting the number of necessary Möbius transformations. While the bisection method throws away the transformed polynomial, the cont.fract. method uses it as base for further refinements.

What Akritas added to the original cont.fract. method of Vincent, besides its rediscovery (from vol. 1 of Compte rendu, no less) and popularization, was an efficient integer implementation for the Cauchy lower bound for positive real roots and the proof of the competitive complexity (and finiteness) of the thus modified algorithm. All of this is more or less lengthily covered in the articles dedicated to the special topics. Here it is rather excessive to follow all these twists.--LutzL (talk) 23:12, 21 December 2013 (UTC)

Spelling, etc.

Please. Notice this edit. In particular:

• Don't capitalize the initial letter of a word just because it's in a section heading.
• Things like "Cohn–Schur" require an en-dash, not a hyphen.
• Similarly, ranges of pages, as in "pp. 31–43" require an en-dash, not a hyphen.
• Do not indiscriminately italicize everything in non-TeX mathematical notation. Italicize variables, but NOT digits, parentheses and other punctuation, or things like sin, cos, det, log, max, sup, etc. Also, capital Greek letters should not be italicized. The point is of course to be consistent with TeX style. I found lots of stuff like f(x)³ instead of f(x)³.

All of this is codified in WP:MOS and WP:MOSMATH. Michael Hardy (talk) 20:27, 3 January 2014 (UTC)

Couldn't find an algorithm

Isn't there an algorithm that starts with a similar equation with a known solution and approximates the equation, finding a new solution each step, using the previous one as a guess? I read about that but couldn't find it again.— Preceding unsigned comment added by 187.35.227.178 (talk) 00:32, 21 November 2014‎

Please sign your posts in talk pages with four tildes (~~~~).

Apparently, you refer to the homotopy continuation method. This method is limited to polynomial equations, because of the need of a proper notion of "similar equation". As far as I know, although it could work, it is not useful and not used for single univariate equations. D.Lazard (talk) 08:55, 21 November 2014 (UTC)

Homotopy continuation methods, such as Newton homotopy methods, are a bit more general than that. While they require some differentiability conditions, methods such as the hybrid method in [3] can handle nonpolynomial equations. --Mark viking (talk) 12:36, 21 November 2014 (UTC)

Roots vs fixed points

(...) a limit (the so-called "fixed point") which is a root

This phrase is misleading as the roots of e.g. $f(x)=x^{2}+1$ are not fixed points of the same function (i.e. they are not zero). Helder 23:06, 9 July 2015 (UTC)

Good point. I have fixed this. D.Lazard (talk) 07:19, 10 July 2015 (UTC)

Newton's method (and similar derivative-based methods)

re: this revert with explanation "(Reverted 2 edits by 199.34.4.20 (talk): Primary source, too recent for the existence of secondary sources. No reason for giving a spcial emphasis to one paper among tausends. (TW))"

I do not understand why the McDougall Wotherspoon modification of Newton's method is not worth mentioning under this section, and moreover why any of the other "thousands" of variants on Newton's method should also not be mentioned. Especially if, as is in the case of the McDougall variant, they are published in a scholarly pier reviewed journal. When looking for a root-finding algorithm to use in practice I for one would appreciate knowing about a method which: has a better convergence rate, the same calculation cost, is more likely to converge, and remains as relatively simple to implement as Newton's method.

Text cut out of the section:

Another method by McDougall and Wotherspoon is a simple modification on Newton's method to achieve  1 + √2 convergence while still only using one function and derivative evaluation per step. 

References

199.34.4.20 (talk) 20:49, 19 November 2015 (UTC)

• I agree with the removal. It is a primary source; a secondary source is not telling us the modification is important. The method may be significant, but WP editors cannot make that assessment. The abstract also has some comments about having good first estimates. Glrx (talk) 17:49, 21 November 2015 (UTC)

Golden Section Search

Would it be worth adding the golden section search below the bisection search? — Preceding unsigned comment added by Jeremyminton (talk • contribs) 12:22, 18 December 2015 (UTC)

Golden section search is a search for an optimum rather than a root. Glrx (talk) 19:59, 23 March 2016 (UTC)

Table of algorithms?

There are a lot of algorithms. Would it make sense to make a table of them clarifying their differences, such as how many roots they find at once, whether they are guaranteed to converge, convergence speed, etc.? — Preceding unsigned comment added by 71.167.63.118 (talk) 02:02, 21 March 2016 (UTC)

Requested move 22 June 2016

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review. No further edits should be made to this section.

The result of the move request was: no consensus. Both sides have said their pieces but it doesn't look like there is general agreement either way. (non-admin closure) Eventhorizon51 ^(talk) 02:14, 10 July 2016 (UTC)

---

Root-finding algorithm → Root-finding method – (over redirect) Root-finding is usually numerical method rather than an algorithm. Most named root-finders have "method" rather than "algorithm" in their name. For example, the usual names are Newton's method or Brent's method rather than Newton's algorithm or Brent's algorithm. The typical result of these methods is an approximation rather than an exact result; the methods are terminated when the results are close enough; some root-finders may fail on particular inputs and therefore do not compute a result. This requested move is to acknowledge a subtle distinction between "algorithm" and "method". Compare to graphy theory algorithms such as Dikjstra's algorithm that computes an exact result after a specified time. Glrx (talk) 15:17, 22 June 2016 (UTC) Relisted. Jenks24 (talk) 04:26, 1 July 2016 (UTC)

• Support. Good point. Good argument. I am in favour of this suggestion. Bo Jacoby (talk) 23:03, 22 June 2016 (UTC).
• Neutral. I'd be happy with either name, but I don't agree with the argument. Does "Dikjstra's algorithm" become only a "method" when it is used with floating-point edge lengths? (Answer: no.) I have never heard of a distinction being made between "algorithm" and "method" on the basis of precision. There is no doubt that Gaussian elimination is an algorithm, for example, even though 99.99% of applications are numerical. The only point I see, one not made, is that "algorithm" usually implies eventual stopping, which Newton's method programmed carelessly does not, though bisection does. As for "reliable sources", at Google Scholar, "root-finding algorithm" wins over "root-finding method". McKay (talk) 05:41, 23 June 2016 (UTC)

@McKay: The issue is not about precision. An algorithm should give an exact answer in a finite time. Gaussian elimination is an algorithm when done with an honest field (e.g., R): it would give an exact answer after O(n³) steps. It's normally referred to as just GE -- without a "method" or "algorithm". Compare to names for typical root-finders: Newton's method, Brent's method, secant method, Bairstow's method, and bisection method. (BTW, Wolfram calls GE a method). I'm not going to argue that we should not call GE an algorithm, but when it is done with floating point arithmetic on an ill-conditioned matrix, its result does not satisfy the desired Ax=b: it takes finite time but does not give an exact answer. Arguably, graph algorithms that use floating point could fail to find the shortest path due to truncation error. So throw out the notion of precision and assume perfect arithmetic. The root finders won't find an exact answer in finite time and some won't converge for difficult inputs. Glrx (talk) 19:16, 27 June 2016 (UTC)

I agree with some of the comments of Glrx, but not those related to the bisection method: when used with exact rational arithmetic (and sometimes with interval arithmetic) it can give (in a finite number of steps) an exact answer consisting of one interval by root and the assertion that each interval contains exactly one root. However, the bisection method is never called an algorithm, as the different ways to implement it are different algorithms (mainly implementation with Descartes' rule of signs, often called Uspenski algorithm, or Sturm's theorem). So, I am neutral with this move. D.Lazard (talk) 19:54, 27 June 2016 (UTC)

• Oppose – I don't find the argument convincing. These methods are algorithms. Dicklyon (talk) 06:28, 23 June 2016 (UTC)

• Oppose The word "algorithm" means mathematical method. There are methods which are not mathematical. For example, using a pig to search a forest for truffles attached to tree roots is a root-finding method which is not an algorithm. The word "algorithm" tips off the reader that we are talking about mathematics. JRSpriggs (talk) 08:49, 1 July 2016 (UTC)
• Oppose Even in mathematics, there are methods that are not related to computation, such as proof methods. Computational methods may far to be algorithmic as are heuristics and many methods of artificial intelligence. In this article, not all methods are algorithms in the strict meaning of the word, but all may be refined into algorithms. For example, if Newton's method fails to converge, the implementation may detect this and return "failed", which is a perfectly admissible output for an algorithm. Also, for a numerical algorithm, an approximate value and a error bound (or equivalently, an interval containing the bound) is an exact answer from the algorithmic point of view. Thus, the current title is technically correct, and the proposed title may be misleading, as being too vague. D.Lazard (talk) 09:39, 1 July 2016 (UTC)
• Oppose The move request seems to assume that algorithms must produce exact outputs. This is just not true. It is perfectly fine for an algorithm to produce an approximation. In fact, it is theoretically important that algorithms be allowed to do so, because there are problems for which finding the exact result is much more expensive than finding an approximate result (unless P = NP). See polynomial-time approximation scheme and APX. Ozob (talk) 12:32, 1 July 2016 (UTC)
• Mild support. (1) The list of names of such methods, using the name "method", makes it seem somewhat more consistent to call it a "method" (Newton's method, Brent's method, secant method, Bairstow's method, bisection method). (2) As to the definition of "algorithm", I wonder about a couple of things. It's easy to write a program to find an even number greater than 2 that is not a sum of two primes, if such a number exists. And if such a number exists, the program will run for a finite amount of time and give an exact answer. Therefore it would be an algorithm. By that definition, the question of whether it's an algorithm or not cannot be settled unless you can say whether Goldbach's conjecture is true! As for numerical precision of the result, how about this: Someone proposes an "algorithm" for finding the square root of an input number. It gives the right answer rounded to three significant digits. That's numerically exact if the intended purpose is to find the root rounded to three significant digits, and not if the intended purpose is a bit different. Does the definition of "algorithm" depend on what the intended purpose is? Maybe it could; I've never heard that before, but I'm not a computer scientist. To D.Lazard I would say that most methods used in mathematics are not algorithms. Mathematical induction is not an algorithm; proof by contradiction is not an algorithm; squeezing is not an algorithm, etc. (3) Thus my point (1) above supports the change and gives a reason; my point (2) says some of the other proposed reasons aren't very good. Michael Hardy (talk) 19:30, 1 July 2016 (UTC)

Some comments: (1) In modern computer science, an algorithm requires an explicit input/output specification, a description of the algorithm itself through a program, and a proof that the program satisfies the specifications. The input/output specification is analogous to the statement of a theorem (there exists an algorithm with this specification), and the program, with its proof of correction is analogous to the proof of the theorem. In fact, it is more than an analogy, it is a true equivalence, called Curry–Howard correspondence in the logical system (intuitionistic type theory) on which are based the most powerful proof assistants. In such a context, the use of method in this article is the analogous of a proof method, i.e. a starting idea for building a proof or an algorithm. It is what I meant by saying (in a preceding post) that methods may be refined into algorithms. (2) The "Goldbach program" described by Michael Hardy is a semialgorithm and a conjectural algorithm. As the existence of an algorithm depends on a proof, it is not a surprise that some algorithms depend on conjectures. One of them is the deterministic version of Miller–Rabin primality test, which depends on the generalized Riemann hypothesis. (3) Does the definition of "algorithm" depend on what the intended purpose is? My answer is "no", if talking about the definition of what is an algorithm, but "yes" if talking of a specific algorithm, as the input/output specification is exactly the intended purpose of the algorithm. D.Lazard (talk) 08:46, 2 July 2016 (UTC)

That's a precise usage of method, but is it how "method" is actually used?. Any algorithm with parameters is actually a family of algorithms, and one might refer to the family as a "method". For example, binary search fits into a family of search algorithms, each of which takes a sorted array of length n, compares the element f(n) with the target value, and either outputs a match and halts, recurses to the interval [0, f(n) − 1], recurses to the interval [f(n) + 1, n], or outputs that no match exist and halts. Any f(n) = floor(Cn) with C in (0, 1) produces an O(log n) algorithm, and if C = 0.5 the algorithm is binary search. One might refer to this family of algorithms as a "method", since the algorithms are identical except for a choice of parameter. It's what I think of when I think of "method"; but I'm not a computer scientist, so I might just be ignorant of standard terminology. Ozob (talk) 21:31, 2 July 2016 (UTC)

• Comment. Many of the above comments do not distinguish between "method", "algorithm", and "program". The current article seemingly treats "method" and "algorithm" as the same: "A root-finding algorithm is a numerical method, or algorithm, ...." But the article uses "algorithm" 28 times and "method" over 100 times. None of the 9 references use the term "algorithm"; four of them use "method". Some classic general texts for numerical programing are Richard Hamming's Numerical Methods for Scientists and Engineers and Forman S. Acton's Numerical Methods that Usually Work. The individual root-finding names use "method": "The simplest root-finding algorithm is the bisection method." The names in {{Root-finding algorithms}} use "method" in their name (yes, I know Jenkin-Traub is a pipe). If I search Google Books for "root-finding algorithm", I'll get hits for Berlekamp's algorithm which is an honest-to-god algorithm (it terminates in finite time with an exact answer) that is used for factoring polynomials over a finite fields; it is not the subject of this article. A method is a way to attack a problem. There's no guarantee that it will terminate or give an exact answer. The field of Numerical analysis looks at methods and tries to describe their requirements (alternating sign; continuous; no nearby poles) and effectiveness (e.g., convergence rate). Newton's method may quadratically converge to the exact answer, but it never gets there. The article Algorithm wants a finite time; it equates algorith with Effective method which requires termination after a finite number of steps and always producing the correct answer. By those terms, many of the root-finders describe here are just methods because without additional stopping criteria, they do not terminate. The bisection method just divides the interval; it only terminates when some stopping criteria are added. Some methods may run amok with some inputs, so they will not terminate with a correct answer; they are not effective for producing the root we want, so they are not effective methods and therefore not algorithms; they are just methods. Glrx (talk) 03:10, 8 July 2016 (UTC)

---

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.

Root finding of polynomials

I have rewritten a large part of the section now called "Roots of polynomials" ([4]) and particularly the section on real roots ([5]). The previous version for real roots suffered of WP:COI and non-neutral point of view, and this mess was extended to Vincent's theorem and Budan's theorem. So, I have rewritten Budan's theorem, created a new article Real-root isolation, and redirected Vincent's theorem to this new article.

The section here is now a summary of the new article with template {{main article}}. Real-root isolation is certainly full of typos and grammar errors. So, please fix those that you encounter.

Also, a reviewer as tagged Real-root isolation as too technical. I cannot see how making this subject less technical. In particular because all sources that I know are much more technical. So, please remove the tag, if you agree that this technicality is inherent to the subject. It is clear that I cannot do it myself.

I hope that you will agree that these edits improve the covering of the subject. D.Lazard (talk) 19:12, 30 December 2018 (UTC)

The sentence: "Also, even with a good approximation, when one evaluates a polynomial at an approximate root, one may get a result that is far to be close to zero." seems to be missing a phrase, but I am not sure how to fix it. Did you intend, "too large in magnitude"?

Missing phrase: "Also, even with a good approximation, when one evaluates a polynomial at an approximate root, one may get a result that is far *****MISSING PHRASE***** to be close to zero."

SlotAndSplit (talk) 17:55, 12 October 2022 (UTC)