In connection to the discussion about numerical or symbolic methods from a previous posting, Wolgang Tintemann showed my another interesting example: polynomials with integer coefficients. The zeros of such polynomials are called algebraic numbers, and many trigonometric values are algebraic. Here is an example.
If we expand
\((\cos \phi + i \, \sin \phi)^n\)
and take the real part, we get a polynomial in cosines and sines, which has zeros in well known values of phi. For a specific example, we compute (using Maxima in Euler Math Toolbox, of course)
\(\text{im} \, (x+iy)^5 = 5 x y^4 – 10 x^3 y^2 + x^5\)
If we divide this by x^5 and substitute y=xt, we get
\(p_5(t) = t^5 – 10t^3 + 5t\)
The 5 zeros of this polynomial correspond to places, where the imaginary part of z^5 is 0. In fact, because of
\(t = \dfrac{y}{x} = \dfrac{\sin \phi}{\cos \phi} = \tan \phi,\)
we easily see that the zeros are in
\(\tan \left( \dfrac{k\pi}{5} \right), \quad k=0,\ldots,4\)
Now let us try n=17. We get
\(t^{17}-136\,t^{15}+2380\,t^{13}-12376\,t^{11}+24310\,t^9-19448\,t^7+6188\,t^5-680\,t^3+17\,t\)
Suddenly, we have a problem if we want to check the „known“ zeros.
>n&:=17;
>function p(t) &= expand(subst(y=x*t,imagpart(expand((x+y*I)^n))/x^n))
17 15 13 11 9 7
t - 136 t + 2380 t - 12376 t + 24310 t - 19448 t
5 3
+ 6188 t - 680 t + 17 t
>p(tan((0:n-1)*pi/n))
[0, 0, 0, 0, 0, 0, 0, 8.8758e-006, -102.522, -712.053,
-8.43804e-006, 0, 0, 0, 0, 0, 0]
Some of the zeros are inaccurate. That’s the reason why the problem belongs to this series about numerical vs. algebraic methods. But why does this happen?
By construction, the polynomial (x+iy)^17 behaves well on the unit circle. But we divide by y^17, which is a very small number if y is not close to 1. Consequently, the polynomial p(t) grows rapidly, just like polynomials often do. It does not make sense to plot the polynomial. Let us compute three values only.
>x=tan(8*pi/17); eps=1e-14; >p(x) -102.522 >p(x-eps) -711.949 >p(x+eps) 490.905
So, a very small change has a very large effect. In fact, the derivative p'(x) exceeds 10^16 in this point. Thus, it is no surprise that the value at x cannot be computed with much accuracy.
The problem is known as cancellation of digits. The positive part and the negative part of the sum forming p(t) are both large compared to the total sum. Then only a few digits remain if both are subtracted from each other.
There is a fine point worth remembering: The inaccuracy is not due to an inaccurate evaluation of the polynomial. The inaccuracy starts with the value of pi, which the processor uses with 16 digits. Division by 17 and the tangent function is the next hurdle. So we evaluate the polynomial at a place which is only known to about 16 digits. And since the polynomial is so badly increasing at this point, the result must be off.
How can this be solved? The trivial solution is a computation with higher accuracy. Let us use the long floats in Maxima.
>&bfloat(p(tan(8*pi/17))) 1.332267629550187848508358001709b-14
Long floats are slow, since there is no processor support. So they are not used unless needed.
Finally, we have learned that solutions may be known exactly, but are not easy to compute numerically. On the other hand most problems have solutions, which can easily be computed numerically with sufficient accuracy, but do no have an exact solution at all. Since this is so in the majority of cases, education in numerical methods may be more fruitful than learning useless algebraic details. For a mathematician, both subjects are equally interesting.