|
 |
So, I was following a branching path of internet tangenting, and came across
this little blurb.
https://en.wikipedia.org/wiki/Real-root_isolation
The first complete real-root isolation algorithm results from Sturm's theorem
(1829). However, when real-root-isolation algorithms began to be implemented on
computers it appeared that algorithms derived from Sturm's theorem are less
efficient than those derived from Descartes' rule of signs (1637).
Perhaps that's not the whole story - or there's some licensing issue with the
Descarte-based algorithm, or ....?
I found the discussion here to very interesting as well.
https://en.wikipedia.org/wiki/Wilkinson%27s_polynomial
Definitely seems to be a challenging topic with a whole host of rules and
theorems and methods .
Post a reply to this message
|
|
|
|
On 8/11/19 3:59 PM, Bald Eagle wrote:
>
> So, I was following a branching path of internet tangenting, and came across
> this little blurb.
>
> https://en.wikipedia.org/wiki/Real-root_isolation
> The first complete real-root isolation algorithm results from Sturm's theorem
> (1829). However, when real-root-isolation algorithms began to be implemented on
> computers it appeared that algorithms derived from Sturm's theorem are less
> efficient than those derived from Descartes' rule of signs (1637).
>
>
> Perhaps that's not the whole story - or there's some licensing issue with the
> Descarte-based algorithm, or ....?
>
>
It's not the whole, complicated story.
The statement is not necessarily true for low orders and positive roots
only realm where we play. We also have frequent effective root
multiplicities and want to run on float hardware - both complications
most solver methods avoid up front.
That said, I posted in June to p.programming some details of a method I
have coded up in tcl one might call a:
Descartes' rule of signs
Budan-Fourier theorem
Vincent's theorem
Uspensky
Collins and Akritas 1976 (and many following papers(1))
Sturm-chain for root counts, but not isolation.
Newton-Raphson
Ruffini-Horner / Taylor-Shift
composite.
(1) - Mostly because I learned about Budan / Vincent from these not
because I'm using the continued fraction stuff.
To that composite method we add the idea of using ray-equation
generation in place of the traditional Mobius transforms - for much
better accuracy while isolating roots. The tcl implementation looks good
to me thus far. Unsure about performance in the end as still playing
with details like how to most efficiently evaluate the sign changes
while always maintaining the original coefficient sign information.
Anyway, I'm hopeful for something better - mostly for accuracy not
performance concerns. If the current promise holds, it will be using
sign changes in addition to Sturm's theorem(2,3).
Aside: Sturm's method depends on sign changes too.
>
Bill P.
(2) - Our Sturm implementation is really a Sturm bisection /
Regula-Falsi method with a kind of chain fuzzing (in master on by
default except in my updated solver branch where it's on only where
needed). The fuzzing or dumbing down can help with some root
multiplicities at the cost of isolation accuracy/ability.
(3) - Almost all Sturm implementations derive the Sturm chain in a
traditional eqn/derivative -remainder etc...way. Sturm's theorom is more
general having only certain requirements for the chain and it's
evaluation results. I don't have it in front of me, but I found in an
old book by L. E. Dickson a direct method for calculating the depressed
quartic sturm chain (a depressed cubic/quartic equation is the basis for
cubic and quartic solvers). Not tried an implementation, but seeing such
a thing got me thinking about perhaps implementing at least the bottom
parts of the sturm chain as a state machine or similar instead of
repeated blind evaluations of those equations. Feels like it should be
doable & probably at better accuracy. I don't know though, maybe too
obscure to be worth the bother practically. Plus I've got lots of work
to finish just what I already have going...
Post a reply to this message
|
|
