УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ПОЛИНОМ ОДНОЙ ПЕРЕМЕННОЙ.


Возвратный полином

§

Будем обозначать через \mathbb A_{} какое-либо из множеств \mathbb Q, \mathbb R_{} или \mathbb C_{}.

Возвратным или взаимным полиномом называется такой полином a_0z^n+a_1z^{n-1}+\dots+a_{n-1}z+a_n, \ a_0\ne 0, у которого набор коэффициентов (a_0,a_1,\dots, a_{n-1},a_n) симметричен относительно середины:

a_0=a_{n},a_1=a_{n-1},\dots, a_{j}=a_{n-j} \dots
П

Пример. Полиномы

z^2-3\,z+1,\quad -\sqrt{2}z^5+2\,z^4+\mathbf i z^3+2\,z-\sqrt{2},\quad z^n+1 , \quad z^n+z^{n-1}+z^{n-2}+\dots + z^2 +z+1=\sum_{j=1}^n z^{j}

будут возвратными.

Определение можно сделать более формальным, если ввести следующее преобразование. Для произвольного полинома F(z)=A_0z^n+A_1z^{n-1}+\dots+A_{n-1}z+A_n обозначим

F^{\ast}(z)= A_0+A_1z+\dots+A_{n-1}z^{n-1}+A_nz^n =\sum_{j=0}^n a_jz^{j} \ ,

т.е. полином F^{\ast}(z) — это записанный «в обратном порядке» степеней мономов полином F(z): старший коэффициент стал свободным членом, коэффициент при z^{n-1} перешел в коэффициент при z_{} и т.д. Формально полином F^{\ast}(z) связан с полиномом F(z) функциональным соотношением:

F^{\ast}(z)\equiv z^n F(1/z) \ .
§

В литературе по теории кодирования полином F^{\ast}(z) называется полиномом, двойственным к F_{}(z).

§

Имеется нестыковка в русскоязычном понятии возвратный полином (возвратное уравнение) и английским выражением reciprocal polynomial. Согласно ангоязычной Википедии reciprocal polynomial для произвольного полинома F(z) — это полином, обозначенный выше F^{\ast}(z) (да еще с дополнительным сопряжением коэффициентов), а собственно возвратный — в приведенном выше определении — полином называется palindromic polynomial1).

Т

Теорема 1. Полином f_{}(z) будет возвратным тогда и только тогда, когда f(z)\equiv f^{\ast}(z).

=>

Если \lambda_{} обозначает какой-то корень возвратного полинома, то корнем этого полинома будет и 1/\lambda.

Последнее следствие равносильно тому, что множество всех корней возвратного полинома можно разбить на пары корней \{\lambda,1/\lambda \}. Геометрически: изобразив на комплексной плоскости z=x+\mathbf i y корни возвратного полинома, находящиеся внутри единичного круга |z|<1, отображением w=1/z мы получим его корни, лежащие вне этого круга. Отдельно следует исследовать значения z_{}=\pm 1, т.к. они «остаются на своих местах» при таком отображении.

?

Доказать, что произведение двух возвратных полиномов является возвратным полиномом.

Т

Теорема 2. Возвратный полином f(z)\in \mathbb A[z] нечетной степени можно представить в виде произведения f(z)\equiv (z+1)f_1(z), где f_1(z)\in \mathbb A[z] является возвратным полиномом четной степени.

Доказательство производится формальной подстановкой z=-1 в функциональное равенство:

f(z)\equiv z^nf(1/z)\quad \Rightarrow \quad f(-1)=(-1)^n f(-1) \ ;

при n_{} нечетном это возможно только при f(-1)=0. Следовательно, по теореме Безу, f(z)\equiv (z+1)f_1(z), \deg f_1=\deg f -1. Осталось показать, что и полином f_1(z) будет возвратным. С помощью схемы Хорнера установим принцип формирования его коэффициентов на примере n_{}=7:

\begin{array}{c|c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & a_3 & a_2 & a_1 & a_0 \\ \hline -1 & a_0 & -a_0+a_1 & a_0-a_1+a_2 &-a_0+a_1-a_2+a_3 & a_0-a_1+a_2 & -a_0+a_1 & a_0 \end{array}

Для общего случая рассуждения аналогичны.

Итак, возвратный полином нечетной степени обязательно имеет корень \lambda=-1. А для поиска остальных его корней мы получили возвратное уравнение четной степени. Покажем, что решение последнего может быть сведено к решению подходящего уравнения в два раза меньшей степени. Пусть \deg f=2\, m,\, m \in \mathbb N. Разделим уравнение f(z)=0 на z^m:

a_0z^m+a_1z^{m-1}+\dots +a_{m-1}z+ a_{m}+a_{m-1}\frac{1}{z}+ \dots + a_1\frac{1}{z^{m-1}}+a_0\frac{1}{z^{m}}=0 \ .

Сгруппируем члены с одинаковыми коэффициентами:

a_0\left(z^m + \frac{1}{z^{m}} \right)+a_1\left(z^{m-1} + \frac{1}{z^{m-1}} \right) +\dots + a_{m-1}\left(z + \frac{1}{z} \right)+a_m=0 \ .

Введем новую переменную

w= z + \frac{1}{z} \ .
Т

Теорема 3. Выражение z^k+1/z^k может быть представлено в виде полинома степени k_{} от переменной w_{} с целыми коэффициентами:

z^k+\frac{1}{z^k} \equiv P_k(w) \in \mathbb Z[w] \ .

Доказательство проводится индукцией по k_{}. Для k_{}=1 утверждение очевидно. Предположим, что оно доказано для всех показателей, меньших k_{}. Разложим w^k= (z+1/z)^k по формуле бинома Ньютона:

w^k=\left(z + \frac{1}{z} \right)^k=\left(z^k + \frac{1}{z^k} \right) +C_k^1\left(z^{k-2} + \frac{1}{z^{k-2}} \right) +C_k^2\left(z^{k-4} + \frac{1}{z^{k-4}} \right)+\dots

Поскольку, по индукционному предположению, выражения из второй, третьей и т.д. скобок правой части формулы могут быть выражены в виде полиномов от w_{}, то из этого равенства можно найти и выражение для z^k+1/z^k.

П

Пример.

\begin{array}{lcl} w^2=z^2 + 2 + 1/z^2 &\Rightarrow & z^2 + 1/z^2=w^2-2 \ , \\ w^3=z^3 + 3\,z +3/z+ 1/z^3 &\Rightarrow & z^3 + 1/z^3=w^3-3\,w \ , \\ w^4=z^4 + 4\,z^2 +6+ 4/z^2+ 1/z^4 &\Rightarrow & z^4 + 1/z^4=w^4-4\,(w^2-2) - 6= w^4-4\,w^2 + 2 \\ \dots \end{array}

Последняя теорема позволяет свести решение возвратного уравнения f(z)=0 четной степени 2\, m к решению уравнения

\Phi(w)\equiv a_0P_m(w)+a_1P_{m-1}(w)+\dots+ a_{m-1}w+a_m=0

степени m_{}. Если \mu_{} — произвольный корень последнего, то уравнение z+1/z=\mu даст значения двух корней возвратного уравнения.

П

Пример. Решить уравнение

z^6-6\,z^5+14\,z^4-18\,z^3+14\,z^2-6\,z+1 =0 \ .

Решение. Разделив уравнение на z^3, формируем уравнение

\left(z^3+\frac{1}{z^3} \right)-6\,\left( z^2+\frac{1}{z^2} \right)+14\left(z+\frac{1}{z} \right)-18=0 \ .

Затем, с помощью формул предыдущего примера, выписываем уравнение относительно w_{}:

(w^3-3\,w)-6\, (w^2-2)+14\,w -18 =0 \ \Rightarrow \ w^3-6\, w^2+11\, w -6 =0 \ .

Легко проверить, что корнями последнего уравнения являются \mu_1=1,\, \mu_2=2,\, \mu_3=3. Остается решить три квадратных уравнения

z+1/z=1,\ z+1/z=2,\ z+1/z=3 \ .

Ответ.

1 (кратности 2),\ \frac{1}{2} \pm \mathbf i \frac{\sqrt{3}}{2},\ \frac{3}{2}\pm \frac{\sqrt{5}}{2} \ .

Частным случаем возвратного уравнения является уравнение

\sum_{j=0}^{n-1} z^{n-1-j}= z^{n-1}+z^{n-2}+\dots + z + 1=0 \ ,

которое получается из уравнения деления круга z^n-1=0, задающего значения корней n-й степени из 1.

?

Найти выражения для \sin {2\pi}/5 и \cos {2\pi}/5, решив уравнение z^4+z^3+z^2+z+1=0.

Имеется способ непосредственного построения полинома \Phi(w), являющегося результатом подстановки w=z+1/z в выражение для f(z)/z^m. Этот способ основан на вычислении результанта двух полиномов.

Т

Теорема 4. Для возвратного полинома f(z) четной степени имеет место тождество

\mathcal R_z (f(z),z^2-wz+1) \equiv \Phi^2(w) \ ;

здесь результант рассматривается для полиномов относительно переменной z_{}.

=>

\Phi^2(0)=f(\mathbf i)f(-\mathbf i).

Это следует из представления результанта полиномов через корни одного из них — в данном случае, через корни полинома z^2+1.

§

Здесь мы встретились с отдельной интересной проблемой: известно, что некоторый полином \Psi(z) является квадратом какого-то другого полинома \Phi(z); как найти \Phi(z), т.е. извлечь квадратный корень из \Psi(z) ? Имеются разные подходы к решению этой задачи. Наиболее просто реализуемый заключается в вычислении наибольшего общего делителя полинома \Psi(z) и его производной (см. теорию ЗДЕСЬ ):

\operatorname{HOD} (\Psi(z),\Psi'(z)) \ ;

поскольку \operatorname{HOD} вычисляется с точностью до домножения на константу, следует зафиксировать один из коэффициентов — например, потребовать чтобы свободный член \operatorname{HOD} (\Psi(z),\Psi'(z)) был равен \sqrt{\Psi(0)}. Тогда, как правило, этот \operatorname{HOD} и будет искомым полиномом:

\Phi(z) \equiv \operatorname{HOD} (\Psi(z),\Psi'(z)) \ .

Имеются, однако, исключительные случаи (например, предлагаемый алгоритм засбоит на полиноме z^8+4\,z^6+6\,z^4+4\,z^2+1), но эти вырождения мне лень сейчас описывать…

П

Пример. Для полинома f(z)=z^6-6\,z^5+14\,z^4-18\,z^3+14\,z^2-6\,z+1 из последнего примера представим результант в форме Сильвестра:

\mathcal R_z (f(z),z^2-wz+1)=- \left|\begin{array}{rrrrrrrr} 1 & -6 & 14 &-18 & 14 & -6 & 1 & 0 \\ 0 & 1 & -6 & 14 &-18 & 14 & -6 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & -w & 1 \\ 0 & 0 & 0 & 0 & 1 & -w & 1 & 0 \\ 0 & 0 & 0 & 1 & -w & 1 & 0 & 0 \\ 0 & 0 & 1 & -w & 1 & 0 & 0 & 0 \\ 0 & 1 & -w & 1 & 0 & 0 & 0 & 0\\ 1 & -w & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right| =(-w^3+6\,w^2-11\,w+ 6)^2 \ .

Т

Теорема 5. Полином f(z) \in \mathbb C[z] четной степени 2n_{} является возвратным тогда и только тогда, когда его можно представить в виде произведения2)

f(z) \equiv f_1(z) f_1^{\ast}(z) \quad npu \quad f_1(z) \in \mathbb C[z], \deg f_1=n \ .

Полином f(z) \in \mathbb C[z] нечетной степени 2n_{}+1 является возвратным тогда и только тогда, когда его можно представить в виде произведения

f(z) \equiv (z+1)f_1(z) f_1^{\ast}(z) \quad npu \quad f_1(z) \in \mathbb C[z], \deg f_1=n \ .

Доказательство достаточности очевидно ввиду теоремы 1. Необходимость следует из следствия к той же теореме: корни возвратного полинома четной степени 2\,n можно разбить на пары \{ \lambda, 1/\lambda \}. В результате разложение f_{}(z) на линейные множители будет иметь вид

f(z)\equiv a_0\underbrace{(z-\lambda_1)(z-\lambda_2)\times \dots \times (z-\lambda_n)}_{\equiv f_{_1}(z)} \times \underbrace{(z-1/\lambda_1)(z-1/\lambda_2)\times \dots \times (z-1/\lambda_n)}_{\equiv f_{_2}(z)} \ .

Согласно свойству 3 из пункта ПРЕОБРАЗОВАНИЕ КОРНЕЙ имеет место тождество f_2(z) \equiv f_1^{\ast}(z).

Обобщения

Рассмотрим полином a_0z^n+a_1z^{n-1}+\dots+a_{n-1}z+a_n, \ a_0\ne 0, у которого набор коэффициентов (a_0,a_1,\dots, a_{n-1},a_n) «симметричен с комплексным сопряжением» относительно середины этого набора:

a_0=\overline{a_{n}},a_1=\overline{a_{n-1}},\dots, a_{j}=\overline{a_{n-j}} \dots
§

В отечественной литературе я не встречал специального названия для подобного полинома. В англоязычной он называется self-reciprocal (см. замечание о терминологии в предыдущем пункте ). Пока не обнаружу подходящего, буду называть его сопряженно-возвратным.

П

Пример. f(z)=(1+\mathbf i)z^5+ 3\,z^4+(-\sqrt{3}-2\mathbf i)z^3 +(-\sqrt{3}+2\mathbf i)x^2+3\,z+ (1-\mathbf i).

В случае, когда все коэффициенты полинома f_{}(z) вещественны, то сопряженно-возвратный полином совпадает с возвратным. По аналогии со случаем возвратного полинома, выводится функциональное тождество, определяющее сопряженно-возвратный полином:

f(z)\equiv z^n\overline{f(1/z)} \ ;

здесь знак \overline{ \cdot \ } над полиномом означает, что все его коэффициенты меняются на комплексно-сопряженные:

\overline{ (3-\mathbf i)z^2+2\mathbf i \, z - 178} \equiv (3+\mathbf i)z^2-2\mathbf i \, z - 178 \ .
=>

Если \lambda_{} — корень сопряженно-возвратного полинома f_{}(z), то и 1/ \overline{\lambda} также является корнем этого полинома.

§

Сопряженно-возвратный полином используется в теории тригонометрических полиномов.

Применения

Т

Теорема. Если характеристический полином \det (P-\lambda E) вещественной ортогональной матрицы P не имеет корнем \lambda= +1 или же кратность этого корня — четная, то этот полином является возвратным. Если же кратность корня \lambda=+1 нечетная, то частное

\frac{\det (P-\lambda E)}{\lambda-1}

является возвратным полиномом.

Доказательство ЗДЕСЬ.

1) От слова палиндром, обозначающего слово или выражение, читающееся одинаково слева направо и справа налево («А роза упала на лапу Азора» А.Фет.)
2) Операция ^{\ast} определена выше.

2016/10/11 18:55 редактировал au