3
$\begingroup$

I've made this question here. But I got no answer then I'll make a question with it:

I remember of studying:

  • Sum of two polynomials;
  • Difference of two polynomials;
  • Product of a constant and a polynomial;
  • Product of two polynomials;

And they kinda make sense for me, but I have a doubt on composition of two polynomials, what is composition of two polynomials useful for?

EDIT: This image made me understande it more easily, I've found it on wikipedia.

enter image description here

  • 0
    @BillDubuque I'm reading [Barbeau's polynomials](http://www.amazon.com/Polynomials-Problem-Books-Mathematics-Barbeau/dp/0387969195). In the page I'm in, he said only about composition of two polynomials.2012-07-24

4 Answers 4

3

One of the uses of polynomial composition arises when we wish to factor, or find the roots of, a fixed polynomial $p$. If we can write $p=q\circ r$ for two other polynomials $q$ and $r$, we have simplified our problem. For if we can factor $q$ as $q=q_1\cdot q_2$, then we get that $p=(q_1\circ r)\cdot (q_2\circ r)$ thus factoring $p$ into smaller degree polynomials where we may potentially recursively apply this approach by either factoring $q_1\circ r$ directly or factoring $q_1$ further if we can.

Even seemingly useless compositions, such as when $r$ is a linear polynomial, can be useful. Using this approach was how Ferrari and Cardano simplified the cubic polynomial into a cubic without an $x^2$ term.

For more complicated compositions, you would of course need that $p$ has a degree which is composite. James Rickards actually gave a fairly algorithmic way to determine whether a polynomial can be written as a composition of lower degree polynomials using the polynomial's coefficients in his paper "When Is a Polynomial a Composition of Other Polynomials?" published in the Mathematical Association of America.

One may think that these type of problems are artificially contrived, but these type of problems do show up naturally for functions that satisfy some sort of recursive polynomial relationship. For example, there is a famous sequence of polynomials $T_n$, the Chebyshev polynomials, such that $\cos(nx)=T_n(\cos x)\,.$ Applying these kinds of reductions to $T_5$ would allow one to explicitly calculate $\cos \pi/5$ by factoring polynomials.

6

It might be very useful if you need to make a substitution in an integral. Say you need to substitute $y=x^2+1$ to make part of the integral simpler, and then you need to do the same in another part of the integrand, which happens to be another polynomial.

  • 0
    @Bruno What you mean?2012-07-25
4

Composition of polynomials is usually used when we have two polynomial functions, say $f(x)$ and $g(x)$, and we wish to perform something like:

$f(g(x))=(f\circ g)(x),$

If we needed to know the result of this for some value of $x$, we could of course simply compute $g(x)$ and then use this as our argument $x$ in $f(x)$.

However, say we are writing a computer program, and we need to calculate $f(g(x))$ several thousand times over the course of the program. Computing $g(x)$ for each value of $x$ first, and then computing $f(g(x))$ based on the output of $g(x)$ can be expensive. A much more efficient approach would be to sit down and actually perform the composition of the two polynomials (which will result in a polynomial of degree $\deg{f} + \deg{g}$), $(f\circ g)(x)$.

Of course, the difference in efficiency here would be fairly negligible, but it is just a simple example of where you could encounter polynomial composition.

EDIT: Incorrect. The output degree is $\deg{f} \times \deg{g}$. In general, the composition written out contains much more terms than the two separate, so it is not useful to expand them. In fact, there are algorithms that explicitly rely on iteration or composition because it is an efficient and numerically stable way to construct polynomials of very high degree.

  • 1
    The degree of the composition is the product of the degrees.2018-04-25
4

Iteration is a special case of composition (namely, composition with itself). Studying $f(x), f(f(x)), f(f(f(x)))...$ is an entire field, see for example Mandelbrot sets and Julia sets. Now, a special case of the latter is Newtons method on solving polynomial equations numerically: every time you ask your calculator to numerically solve a polynomial equation, it will most likely use repeated polynomial composition somewhere in the algorithm. (This is a bit rough, what really is done is a bit more involved).