A Basic Weakness, in my Polynomial Roots Finder (Resolved).

One of the subjects which I’ve written about often is that, in the past, I wrote a program which approximates the roots of polynomials, and more recently, that I wrote a version of the same program, that has a (Qt5-based) GUI – a Graphical User Interface. AFAICT, both versions of the program seem to work fine. The GUI version additionally displays a plot of the polynomial.

Note: Polynomials of a degree greater than 4 generally don’t have exact, algebraic solutions – with some exceptions – so that their roots are usually best found by numerical approximation.

Because I’ve published all the recent versions of this program on my blog, I also retest it thoroughly, with polynomials that I know will give it some difficulty each time. And what I have found was that presently, the simplified plotting window has a behaviour that is not false, but that may be difficult for the user to understand. This is less than ideal, because the purpose of that plotting window is, to make the polynomial which the user entered easier to understand, and not harder.

The problem manifests, if the user enters a polynomial that has exactly one root, or that has the same root with some multiplicity. In that situation, my plotting window will assume that the interval on the X-axis to be displayed, deviates from that root by ±0.25, which is also the smallest interval its internal logic allows it to display. While what it displays is not wrong, the very narrow range can make it hard to read:

Here, I’ve used an established Computer Algebra System, to construct a polynomial that has a root of (0.5), with a multiplicity of 8. It’s a polynomial of the 8th degree. Its behaviour near (x=0.5) is the same as what the behaviour would be, of x8, near (x=0.0). In other words, the Y-values never get big, because, to raise some small fraction (x <= 0.25) to the power of 8, will always produce some even-smaller fraction.

But what the plot does non-ideally, is, to centre at (x=0.5) in this case, and only to cover the interval from (x=-0.25) to (x=0.75), as described above. The user must then read from the bottom of the plotting window, that the X-Tick-Interval is only (0.05), and must recognize that the plot is indeed centred at (x=0.5), 4 ticks after the labelled tick at (x=0.3). In this example, it’s easier to read the text-form of the solution.

The reason why my program does this, is the fact that its auto-determined interval spans the range of roots, adds some small fraction to that positively and negatively, but that in this case the spread between the roots is zero, because there is only one. And, I refuse to make the minimum span ±1.0, because some polynomials may in fact have roots closer together than that, which might also need to be plotted…

This program can be found at the following repository on my site:

https://dirkmittler.homeip.net/binaries/

The source code can be found in the files:

• Dirk_Roots_GUI_1.tar.gz
• Dirk_Roots_GUI_1.zip

And an AppImage can be found in the file:

• Dirk_Roots_GUI_1-x86_64.AppImage

(Updated 9/04/2020, 15h40… )

I have now created a GUI version of my polynomial roots approximation program.

One of the facts which I had blogged about some time ago, was that I had developed a program that approximates the roots of polynomials, the intention being that it be used on polynomials of a very high degree, by entirely numerical means. And I did this with the knowledge that polynomials with a degree greater than 4 have no exact, analytical solutions, except for certain special cases.

I think that maybe, one reason why some readers were disinterested in that program, could have been the fact that it was entirely command-line driven. So, what I have now done was,

• To convert the core program into a truly object-oriented format, so that it could act as a module within some other program, and no longer have its own ‘main()’ function, And
• Applied what I’ve taught myself about the Qt5 GUI Library, to design a minimalistic GUI for it…
• One of the things the GUI now does, in addition to just listing the roots as text, is also to provide a rudimentary plot of the polynomial each time.
• One thing which the GUI version can no longer do, is to accept complex coefficients from the user. The command-line version was able to do that. But the GUI version can still find all the complex roots, given some luck.

The AppImage can be found at this repository on my site:

https://dirkmittler.homeip.net/binaries/

The relevant file is named ‘Dirk_Roots_GUI_1-x86_64.AppImage‘. It will only run under Linux, unfortunately.

Dirk

In certain situations, Maxima can actually solve a sextic equation.

For readers who don’t know, a sextic equation is a polynomial of the 6th degree. As the subject line suggests, recent versions of Maxima can find symbolic solutions to those, if used correctly, and, if the sextic actually has ‘an exact, analytical solution’, which is also referred to sometimes as ‘a symbolic solution’.

Whether these analytical solutions are actually more useful than numeric approximations, remains an unanswered question.

What has happened to me is, that I’ve tried to use the method shown below, to cause Maxima to display the solution, and that due to what amounted to a typo, I had given it a polynomial which was visually similar to the one shown, but which was also different in some small way, so that the only solution which Maxima displayed, was the original polynomial, thus implying that Maxima was not able to solve an altered one. The reason this happened is easy to explain…

Not all polynomials of the 6th degree actually have an analytical solution. If given an example that does not, Maxima will fail to display one. All polynomials of the 4th degree actually have an analytical solution, but it may easily be too complex for consumer-grade Computer Algebra Systems (CAS) to output. But, by the time the user is asking a CAS to solve a cubic, he should be able to expect this form of a solution to be output.

The sextic below is actually the product of two cubics, which also explains why Maxima was able to solve it. The reader will need to enable JavaScript:

• From my site, And
• From MathJax.org,

To be able to view the worksheet:

(Updated 7/04/2020, 13h30… )

Revisiting the subject of approximating roots of polynomials.

In an earlier posting, I had written about an approach, for how to find approximations of the roots of polynomials, of an arbitrary degree, but in such away, also to find all the complex roots. (:1)

But with such strategies, there are issues. One concept was, that a home-grown search algorithm would get close to the actual root. Next, polishing would make the result more accurate. And then, an augmented division would be computed, which is also referred to as “Deflation”, resulting in a deflated polynomial, as many times as the original polynomial’s degree, minus one.

Pondering this issue today, I realized that there was still a conceptual weakness in that approach, that being, the fact that some small amount of error is tolerated in the first root found, so that each successive deflated polynomial contains progressively greater degrees of error. What effectively happens next is, that accurate roots are found, of increasingly inaccurate polynomials, and, that there appeared to be few ways to detect and correct the resulting errors, in roots found afterwards. Theoretically, this problem could progress to the point, where doubt is evoked, in whether or not roots found later, were even roots of the original polynomial, since by that time, the object which the roots are being found of, is no longer that original polynomial.

(Update 6/08/2020, 18h35… )