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

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

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.

Screenshot_20200830_133324

Screenshot_20200830_133453


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.


 

Screenshot_20200831_233802


 

 

Dirk

 

One weakness of my algorithm, regarding polynomials.

Several months ago, I wrote a C++ program (with C coding-style) that computes numerical approximations, of the roots of an arbitrary polynomial. Even though I changed the code slightly since March, mainly to improve the chances that it will compile on other people’s computers, the basic algorithm hasn’t changed. Yet, because I wrote the algorithm, I know that it has certain weaknesses, and I’m about to divulge one of those…

The main search algorithm isn’t able to determine whether (x) is sufficiently close to a root. It’s really only able to determine whether (y) is sufficiently close to zero. And so an idea that an implementer could have about this would be, to name the maximum allowable error in (x) ‘epsilon’, to compute the derivative of the polynomial for the given value of (x), and then to multiply ‘epsilon’ by this derivative, perhaps naming the derived, allowable error in (y) ‘epsilond’. But I consciously chose not to go that route because:

  • Computing the real derivative of the polynomial each time, though certainly doable, would have made my code complex beyond what I was willing to tolerate,
  • Even had I done so, certain polynomials will have a uselessly low derivative near one of their roots. This can happen because of a doubled root, or simply because of two roots that are too close together. ‘epsilon’ is as small as what would be practical, given the number of bits the variables have to work with, that were, a 52-bit significand.

So my program, instead, computes a ‘notional derivative’ of the polynomial, near (x), that is really just the derivative of the highest exponent by itself. This little detail could actually make it difficult for some observers to understand my code. At the same time, my program limits the lower extent of this derivative, to an arbitrary, modest fraction, just so that (x) won’t need to be impossibly precise, just to satisfy the computation of how precise (y) would need to be.

But then, a predictable problem becomes, that the real derivative of a given polynomial might be much smaller than just, the derivative of this highest exponent. And if it is, then satisfying … for (y) will no longer satisfy … for (x).

The following output illustrates an example of this behaviour:

 


"Maxima" Preparation:

(%i1) expand((x-100)*(x-101)*(x-102));
(%o1) x^3-303*x^2+30602*x-1030200

(%i2) expand((x-100)*(x-110)*(x-120));
(%o2) x^3-330*x^2+36200*x-1320000

(%i3) expand((x-100)*(x-101));
(%o3) x^2-201*x+10100


Approximations from Program:

dirk@Phosphene:~$ poly_solve 1 -303 30602 -1030200

101.00000000013  +  0I
99.999999999938  +  0I
101.99999999993  +  0I


dirk@Phosphene:~$ poly_solve 1 -330 36200 -1320000

100  +  0I
110  +  0I
120  +  0I


dirk@Phosphene:~$ poly_solve 1 -201 10100

100  +  0I
101  +  0I


dirk@Phosphene:~$ 


 

 


 

(Updated 9/22/2019, 5h40 … )

Continue reading One weakness of my algorithm, regarding polynomials.

Some Observations about Roots with Multiplicities.

One of the subjects which I had visited in my past, was to write a C++ program that approximates the roots of polynomials, but that needed to deal with ‘Doubled Roots’ in a special way, just because the search algorithm within that program, which searches for the roots, cannot deal with doubled roots. And what I found was, roots cannot only be doubled, but can have multiplicities higher than (2). After not having pondered that programming project from the past, for some time, I now come back to rethink it, and find that it can be given a lecture of sorts, all to itself.

So, this is a link to a work-sheet, in which I try to explain Roots with Multiplicities, maybe to people with limited knowledge in Calculus:

Link to Letter-Sized PDF

Link to EPUB File, for viewing on Mobile Devices

And as those two documents mention, the following is a link to the earlier blog posting, from which readers can download the C++ program, as well as to find instructions on how to compile it, on Linux computers:

Link to Earlier Blog Posting

Hence, the C++ program linked to in the earlier blog posting, needed to make use of the subject, that the two PDF Files describe.

N.B.:

(Updated 5/06/2019, 13h15 … )

Continue reading Some Observations about Roots with Multiplicities.