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.

How an exact solution can sometimes be found, without using the general solution.

One of the facts which I’ve been writing about is, that the general solution to a polynomial of a degree higher than (4), that is expected to produce Algebraically exact results, cannot be used because none exists. At the same time, I make a distinction between an exact solution, and the general solution. This distinction can also be explained in greater detail…

We are sometimes given a polynomial, which has at least one “rational root”, meaning a root that can be stated either as a whole number, which is actually referred to as an “integer”, or as a fraction. The following is an example:

x^3 -3*x^2 -2*x + 6 = 0

In this case it can be observed, that the coefficient of (x^3), which is not stated, corresponds to a (1), and that the constant term, which is visible as (+6), is an integer. What can be done here, is that all the factors of (6) can be used positively and negatively – not only the prime factors – and plugged in to see whether they do in fact constitute one root. Again, they do if and only if the equation is satisfied as resulting in zero.

Thus, as potential candidates, ±1, ±2, ±3, ±6 can all be tried.

(Updated 3/2/2019, 16h30 … )

Continue reading How an exact solution can sometimes be found, without using the general solution.

Simplifying the approach, to finding roots of polynomials.

In some cases, the aim of my postings is to say, ‘I am able to solve a certain problem – more or less – and therefore, the problem is solvable.’ It follows from this position that my solutions are not assumed to be better by any means, than mainstream solutions. So recently, I suggested an approach to finding the roots of polynomials numerically, again just to prove that it can be done. And then one observation which my readers might have made would be, that my approach is only accurate to within (10-12), while mainstream solutions are accurate to within (10-16). And one possible explanation for this would be, that the mainstream solutions polish their roots, which I did not get into. (:1)

(Edit 2/8/2019, 6h40 : )

A detail which some of my readers might have missed is, that when I refer to a ‘numerical solution’, I’m generally referring to an approximation.

(End of Edit, 2/8/2019, 6h40 . )

But another observation which I made, was that Mainstream Code Examples are much tighter, than what I suggested, which poses the obvious question: ‘Why can mainstream programmers do so much, with much less code complexity?’ And I think I know one reason.

The mainstream example I just linked to, bypasses a concept which I had suggested, which was to combine conjugate complex roots into quadratic terms, which could be factorized out of the original polynomial as such. What the mainstream example does is to assume that the coefficients of the derived polynomials could be complex, even though the original one only has real coefficients. And then, if a complex root has been found, factorizing it out results in such a polynomial with complex coefficients, after which to factorize out the conjugate, causes the coefficients of the quotient to become real again.

(Edited 1/30/2019, 8h50… )

(Updated 2/9/2019, 23h50… )

I’ve just written some source-code of my own, to test my premises…

Continue reading Simplifying the approach, to finding roots of polynomials.

A Hypothetical Algorithm…

One of the ideas which I’ve written about often is, that when certain Computer Algebra Software needs to compute the root of an equation, such as of a polynomial, an exact Algebraic solution, which is also referred to as the analytical solution, or symbolic Math, may not be at hand, and that therefore, the software uses numerical approximation, in a way that never churned out the Algebraic solution in the first place. And while it might sound disappointing, often, the numerical solution is what Engineers really need.

But one subject which I haven’t analyzed in-depth before, was, how this art might work. This is a subject which some people may study in University, and I never studied that. I can see that in certain cases, an obvious pathway suggests itself. For example, if somebody knows an interval for (x), and if the polynomial function of (x), that being (y), happens to be positive at one end of the interval, and negative at the other end, then it becomes feasible to keep bisecting the interval, so that if (y) is positive at the point of bisection, its value of (x) replaces the ‘positive’ value of (x) for the interval, while if at that new point, (y) is negative, its value for (x) replaces the ‘negative’ value of (x) for the interval. This can be repeated until the interval has become smaller than some amount, by which the root is allowed to be inaccurate.

But there exist certain cases in which the path forward is not as obvious, such as what one should do, if one was given a polynomial of an even degree, that only has complex roots, yet, if these complex roots nevertheless needed to be found. Granted, in practical terms such a problem may never present itself in the lifetime of the reader. But if it does, I just had lots of idle time, and have contemplated an answer.

(Updated 1/30/2019, 13h00 … )

Continue reading A Hypothetical Algorithm…