Hey it's a me again @drifter1!
Today's article is another high-school refresher on Mathematics, and more specifically on Solving Polynomials. This is the third and final part. I highly suggest checking out part 1 and part 2 before this part!
So, without further ado, let's get straight into it!
After applying the Rational Root Test, and either by brute force substitution of the candidates or using some division algorithm, it may be possible to find out that some rational number r is a root. Based on the Factor Theorem this means that x - r is a factor of the polynomial.
If only brute-force was used then the polynomial will have to be divided by that factor in order to end up with a reduced polynomial that will give the remaining roots / factors. Of course, dividing by each candidate factor is more efficient, because the reduced polynomial is produced as a side-product directly!
Two main techniques can be used for dividing. The first one, known as polynomial long division, applies for any polynomial division with a divisor that has the same or lower degree than the dividend. The second one, known as synthetic division, can also be generalized for any division, but is more commonly used for divisions by linear monic polynomials of the form x - a.
Polynomial long division is a type of Euclidean division of polynomials. Starting off with two polynomials, A and B, and if B is not zero and is of same or lower degree than A, there will be a quotient Q and a remainder R, so that:
Of course R must be either 0 or of lower degree than B.
R = 0 basically means that B is a factor of A, and is exactly what is checked for when trying out the possible rational root candidates!
When applied on pen-and-paper, the Blomqvist's method, also known as short division, can be used instead, which requires less writing and is faster as remainders are determined mentally.
The steps are as follows:
Let's get into a simple example to understand the procedure better!
Dividing the first term of the dividend, x2, by the first term of the divisor, x, gives x, which is put below the bar. Multiplying this result by the second term of the divisor, -3, gives us -3x, which when subtracted from the second term of the dividend, -5x, results in -5x -(-3x) = -2x. So, now the first term can be striked out, and the second term replaced by the calculated remainder -2x.
Dividing the first term of the remainder, -2x, by the first term of the divisor, x, gives -2, which is put below the bar. Multiplying it by the second term of the divisor, -3, gives (-2)(-3) = 6, which when subtracted from the second term of the remainder, 6, gives 6 - 6 = 0. So, the new remainder is 0 and the division has been completed.
In other words, applying polynomial division it was proven that 3 is a root of the polynomial equation, or that x - 3 is a factor of the polynomial. Additionally, the quotient x - 2 gives us the second root, which is x = 2.
The polynomial can be factorized as follows:
Regular synthetic division, which is also known as Ruffini's rule, applies to division by polynomials of the form x - a. The main advantages of this approach are:
So, this technique is basically made for solving polynomials!
Let's first try to understand the concept and why it works.
Synthetic division is based on something known as nested multiplication. When substituting each root candidate quite a lot of multiplications and additions are required if the calculations are applied on the polynomial as they come up. But, if the polynomial gets written in nested multiplication format then the number of multiplications and additions becomes far less. This allows for faster calculations and the benefit adds up really fast for higher-degree polynomials.
For example, consider the following polynomial:
From the Rational Root Test, the root candidates are ±1, ±2, ±4, up to ±32.
Trying out x = 1 is simple, as there are no difficult multiplications (one term is 1n = 1), and in that case nested multiplication is not required:
So, let's say that we instead had to try out x = 4, because the previous candidates where not roots. In that case the multiplications and additions pile up by quite a margin, even if the exponentials of 4 are calculated before-hand:
Thus, let's write the polynomial in nested multiplication format:
and calculate x = 4 on that:
Only 4 additions and 3 multiplications are required for that calculation, and those calculations where also much simpler (no exponentials which yielded additions with bigger numbers) and faster!
Of course, we promised that no variables will be required! So, how does one write the nested multiplication in a better format?
Synthetic division is written as follows:
Let's take a look at the previous example again by using that approach in order to check if 4 is a root.
The calculation goes as follows:
Now the initial result 1 is multiplied by the candidate root 4 and added to the second coefficient, 1, giving 5.
Multiplying 5 by 4 gives 20 which is added to the third coefficient, -18, resulting in 2.
Repeating the same method for the remaining two coefficients, the final result is:
The right-most result is 0, which means that x = 4 is a root!
The result is equal to the coefficients of the reduced polynomial, which in that case is:
Applying the same technique on that polynomial once again, will reduce the degree once more, yieling a quadratic polynomial that can be solved directly!
There are some additional theorems that can be used together with the Rational Root Theorem and Synthetic Division to help narrow down the search even further, these are:
When no more rational roots can be found, then the irrational roots can be found approximately by applying numerical methods. In general these methods can be thought of as root-finding algorithms. It's part of a whole branch of mathematics known as Numerical Analysis.
There are various types of methods, such as:
These topics are of course far more advanced, and no longer high school math, which was the main target of this series! For example, I had a Numerical analysis course during my CS studies. A series on such topics is on my to-do list for sure...
Mathematical equations used in this article, have been generated using quicklatex.
Block diagrams and other visualizations were made using draw.io.
And this is actually it for today's post!
The next article(s) will be about:
Basically more High-School Math Refreshers!
See ya!
Keep on drifting!
