Talk:Root-finding algorithm

Jacoby's method

This method is now described at Jacoby's method. -- Jitse Niesen (talk) 13:04, 10 January 2006 (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)

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)