Timeline for Smallest real root of a polynomial in a range
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2016 at 21:32 | vote | accept | 1I1III1 | ||
| Apr 30, 2016 at 21:04 | answer | added | Evil | timeline score: 1 | |
| Apr 29, 2016 at 18:55 | comment | added | 1I1III1 | @EvilJS That's rather genius; you could use a binary search method with the Strum algorithm until the slope works out so newton's method converges to the smallest root in the range. If you want to post that as an answer I'd be more than happy to accept it. Thank you! | |
| Apr 29, 2016 at 14:46 | comment | added | Evil | Have you tried mix like Strum algorithm (to split range into ranges to know how many roots are there) and the run Newton method, which converges very fast with good initial guess? Of course for Strum - only up to first root range found. Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all). | |
| S Apr 29, 2016 at 14:35 | history | suggested | Anton Trunov |
add the 'numerical-algorithms' tag
|
|
| Apr 29, 2016 at 12:44 | review | Suggested edits | |||
| S Apr 29, 2016 at 14:35 | |||||
| Apr 29, 2016 at 11:57 | history | tweeted | twitter.com/StackCompSci/status/726017644072177664 | ||
| Apr 29, 2016 at 8:28 | comment | added | 1I1III1 | In case it helps anyone, my idea was to use householder's method with the same order the same as degree of the polynomial in hopes that it would always yield the root closest to the starting point. Then you could put it in the middle and do a binary search kind of thing to find the smallest root in the range. Unfortunately it can fall into an infinite loop trying to find an imaginary root, for example $2x^3-x^2-x+1$ with a starting point of 0 | |
| Apr 29, 2016 at 8:20 | comment | added | 1I1III1 | @D.W. after further testing it seems my idea doesn't always work. I'll keep working on it. Thank you for all your help. | |
| Apr 29, 2016 at 8:19 | comment | added | 1I1III1 | @adrianN I'm not quite sure which package you're referring to within CGAL, but the general idea is to avoid having to find all of the roots, seeing as only a specific one is needed | |
| Apr 29, 2016 at 7:59 | comment | added | adrianN | Have you tried using a library like CGAL for finding roots? Maybe it does want to you want. | |
| Apr 29, 2016 at 7:23 | comment | added | D.W.♦ | Great! Post an answer - you're welcome to answer your own question! You might wait a day or two before accepting, to give a chance for a better answer. (You can certainly accept one answer and then change which one you accept later, but it's often better to wait a few days before accepting an answer, if you think there's a chance a better answer might be possible. Accepting an answer might be viewed as a signal that "I am satisfied with this answer".) | |
| Apr 29, 2016 at 7:14 | comment | added | 1I1III1 | @D.W. degree. Fixed. Sorry about the confusion. I think I might have come up with an acceptable solution, but I'm not convinced it always works, or is the fastest option. Do I post an answer and accept it, then accept another if a better one comes along, or post it as part of the question because I'm not sure, or as a comment? If I do accept a solution will the question still be seen by people that might have a better solution? | |
| Apr 29, 2016 at 7:07 | history | edited | 1I1III1 | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Apr 29, 2016 at 6:47 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 52 characters in body
|
| Apr 29, 2016 at 3:20 | comment | added | 1I1III1 | @D.W. Corrected the question. Speed is the key; it'll be happening a lot. | |
| Apr 29, 2016 at 3:16 | history | edited | 1I1III1 | CC BY-SA 3.0 |
Clarified what I am looking for
|
| Apr 29, 2016 at 2:43 | comment | added | D.W.♦ | What properties do you want your algorithm to have? Do you just any algorithm for the task? If so, there are algorithms: e.g., find all the roots, then sort. (There are multiple ways to find all roots: factor the polynomial; find one root $r$ and divide $p(x)$ by $x-r$; use binary search.) Another algorithm is to use the bisection method appropriately. So, it seems like there are many possible answers, and I'm not sure exactly what you're looking for. Can you edit the question to clarify how you will evaluate answers? | |
| Apr 28, 2016 at 20:04 | review | First posts | |||
| Apr 28, 2016 at 20:59 | |||||
| Apr 28, 2016 at 20:01 | history | asked | 1I1III1 | CC BY-SA 3.0 |