Инструменты сайта


§

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


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

§

Будем обозначать через $ \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 \mbox{ (кратности 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. Замена переменной $$ w=\left(\frac{z+1}{z-1} \right)^2 $$ в возвратном уравнении $ f(z)=0 $ четной степени $ 2n_{} $ приводит к алгебраическому уравнению $ \Xi(w)=0 $ степени $ \le n $.

Доказательство. Отображение комплексной плоскости $ \mathbb C $, задаваемое формулой $$ u=\frac{z+1}{z-1} $$ отображает пару точек $ \{ z, 1/z \} $ в пару точек $ \{ u,-u\} $. Полином $$ \mathfrak F(u)\equiv (u-1)^{2n} f((u+1)/(u-1)) $$ будет четным по $ u $. Действительно, $$ \mathfrak F(-u)\equiv (-u-1)^{2n} f((-u+1)/(-u-1))\equiv (u+1)^{2n} f((u-1)/(u+1))\equiv (u+1)^{2n} f(1/z)\equiv $$ $$ \equiv (u+1)^{2n} f(1/z)z^{2n} \frac{1}{z^{2n}}\equiv (u-1)^{2n} f(z)\equiv (u-1)^{2n} f((u+1)/(u-1))\equiv \mathfrak F(u) \, . $$ Замена $ u^2=w $ в $ \mathfrak F(u) $ приводит к полиному $ \Xi(w) $.

П

Пример. Для полинома

$$ f(z)=z^6-8\,z^5+16\,z^4-32\,z^3+16\,z^2-8\,z+1 $$ замена переменной $$ z= \frac{\sqrt{w}+1}{\sqrt{w}-1} $$ приводит к дроби $$ -2\frac{-41+9\,w-7\,w^2+7\,w^3}{(\sqrt{w}-1)^6} \quad \Rightarrow \quad \Xi(w)=7\,w^3-7\,w^2+9\,w-41 \, . $$

=>

$ \deg \Xi(w) < n $ тогда и только тогда, когда $ f(1)=0 $. Если $ f(1) \ne 0 $ то $ \Xi(w) = b_0x^n+\dots+b_n $ при $ b_n/b_0 = f(-1)/f(1) $.

Т

Теорема 6. Полином $ 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) $.

Применения

Т

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

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

Обобщения

Рассмотрим полином $ 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} $ также является корнем этого полинома.

§

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

Источники

[1]. Журавский А.М. Сборник задач по высшей алгебре. М.-Л.ГТТИ. 1933

1)
От слова палиндром, обозначающего слово или выражение, читающееся одинаково слева направо и справа налево («А роза упала на лапу Азора» А.Фет.)
2)
Операция $ ^{\ast} $ определена выше.
polynomial/reciprocal.txt · Последние изменения: 2020/07/14 22:11 — au