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:

 

Screenshot_20200904_062403

 

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… )

(As of 9/04/2020, 7h10: )

The following is an example, where an established Computer Algebra System constructed a polynomial of the 8th degree, with the roots in sequence from x ∈ [0.1 .. 0.8] – i.e., with exact roots integer multiples of (0.1) :

 

Screenshot_20200904_083613

 

This example might be an interesting test of my program, because it’s one of the few, in which to turn on Reverse Deflation causes the 3 smallest roots to be found with greater accuracy. However, even in such cases, the greater roots become less-accurate, when this setting is turned on. And only the results in text-form are meaningful here. The plot just seems to exhibit ‘a flat line’ from (x=0.1) to (x=0.8).

 


 

(Update 9/04/2020, 11h35: )

Perhaps I should mention, that the thoughts which I put into scaling the X- and Y-axes had as purpose, to make simpler polynomials ‘look correct’, including a linear equation which will extend diagonally across the plot window. Hence, if I give it the quadratic:

x2 – x + 0.25 = 0

That also has a single value as root, with a multiplicity of (2), but the plot is easier to understand:

Screenshot_20200904_112811


 

(Update 9/04/2020, 12h40: )

I have now added a few lines of code to my plotting functions, that test whether the spread between roots found is less than 0.05, and if it is, renormalize the plot window to extend by ±1.25 around the suspected, multiple root in both the X- and the Y-direction, since high powers seem to have their point of inflection around (±1.0). This will give ‘a normal look’ to most of the plots in this posting, though not, to the plot where the roots were integer multiples of (0.1). The patched source files and AppImage have been uploaded…

Screenshot_20200904_124555

 


 

(Update 9/04/2020, 15h40: )

It seemed to be a contributing factor to the second problem mentioned in this posting, that I had designed the plotting function to apply a minimum range of Y-values that the plot window must encompass. Therefore, when given the problem of the roots, integer multiples of (0.1), the maxima and minima between those roots were much smaller than that minimum range.

With some trepidation, I have now commented-out the line of code that applied this minimum. In theory, its removal could result in an eventual divide-by-zero. But it means that future plots will now stretch out, to cover ½ the Y-axis, no matter how close the roots are.

I felt that one reason I could get away with this now is, the fact that the code which sets a minimum X- span, if there is only one value as root, also sets a minimum Y- span. It was the eventual problem of polynomials that produce only one such value as root, that had caused me to set a minimum Y- span globally.

In theory, if a real polynomial has at least 2 distinct roots, its minima or maxima between those roots should also deviate from zero by some amount…

 

Screenshot_20200904_151544

 

Uploaded.

Enjoy,

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>