Hi,
On 18 June 2013 09:35, Heiner Kirchhoffer <[email protected]>wrote:
> Hi smichr and all,
>
> Thank you for your quick response.
> Does that mean that the method 'refine_root()' of class 'Poly' is not
> capable of finding isolation intervals for all real roots of an arbitrary
> polynomial?
> If so, this would, unfortunately, render the method 'refine_root()'
> useless for my application.
>
> Maybe I should say a few more words about what I need.
> Given a set of polynomials, I need a list of all real roots of all
> polynomials in the set ordered by value.
> I don't need a good rational or floating point approximation of the roots,
> but I need the ordering of the roots to be 100% correct for any thinkable
> set of polynomials (of a predefined maximum degree and for integer
> coefficients).
>
> I think, an implementation that gives me an ordering of the roots which is
> guaranteed to be correct with the lowest computational complexity would
> solve my problem best.
>
> 'refine_root()' seemed to me to be perfectly suited for this purpose
> because I only refine a root until there is no overlap of the isolation
> interval with any of the other roots isolation intervals anymore.
>
> Any (alternative) way of solving my problem using sympy is highly
> appreciated!
>
> Would it be possible (and make sense) to extend the 'refine_root()' method
> of class Poly in order to guarantee that it always produces a refined
> interval for an arbitrary real root of an arbitrary polynomial?
>
> If yes, would it require a big effort to implement it?
>
> Unfortunately, I am not familiar with the concepts used in the
> implementation of 'refine_root()'. But I would be happy if someone could
> point me to some literature to these concepts so I can maybe contribute in
> improving 'refine_root()'.
>
If you want to get isolation intervals of all roots of a polynomial, then
use intervals(), e.g.:
In [1]: f = x**4 - 6*x**3 + 11*x**2 - 6*x + 1
In [2]: intervals(f)
Out[2]: [((0, 1), 2), ((2, 3), 2)]
In [3]: intervals(f, eps=1e-20)
Out[3]:
⎡⎛⎛ 4807526976 7778742049⎞ ⎞ ⎛⎛53316291173 32951280099⎞ ⎞⎤
⎢⎜⎜───────────, ───────────⎟, 2⎟, ⎜⎜───────────, ───────────⎟, 2⎟⎥
⎣⎝⎝12586269025 20365011074⎠ ⎠ ⎝⎝20365011074 12586269025⎠ ⎠⎦
In [4]: epath("/*/[0]/*", _, lambda e: e.evalf(n=21))
Out[4]: [((0.381966011250105151793, 0.381966011250105151796), 2),
((2.6180339887498948482, 2.61803398874989484821), 2)]
By default, intervals() returns isolation intervals only of real roots.
Pass all=True to get two lists with real and complex roots separately.
refine_root() doesn't work with non-squarefree polynomials. Unfortunately
it's not written in the documentation. Remove root multiplicities with
sqf() and then proceed with your original approach, e.g.:
In [8]: sqf_list(f)
Out[8]:
⎛ ⎡⎛ 2 ⎞⎤⎞
⎝1, ⎣⎝x - 3⋅x + 1, 2⎠⎦⎠
In [9]: _[1][0][0]
Out[9]:
2
x - 3⋅x + 1
In [10]: refine_root(_9, 0, 1)
Out[10]: (0, 1/2)
In [11]: refine_root(_9, 0, 1, eps=1e-20)
Out[11]:
⎛ 4807526976 7778742049⎞
⎜───────────, ───────────⎟
⎝12586269025 20365011074⎠
You can pass check_sqf flag to refine_root() to make it check if there are
no multiple roots in the input polynomial, e.g.:
In [14]: refine_root(f, 0, 1, check_sqf=True)
(...)
PolynomialError: only square-free polynomials supported
In future this limitation will be removed.
Thank you for your help!
>
> Best regards,
> Heiner
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at http://groups.google.com/group/sympy.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
Mateusz
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy.
For more options, visit https://groups.google.com/groups/opt_out.
