!!§!! Вспомогательная страница к разделу <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:polynomial ПОЛИНОМ ОДНОЙ ПЕРЕМЕННОЙ)).

----





























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

~~TOC~~

!!§!! Будем обозначать через $ \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-1}+z^{n-2}+\dots + z^2 +z+1=\sum_{j=0}^{n-1} z^{j} 
$$
являются возвратными. Последний полином --- частное от деления 
((:complex_num/circlediv полинома деления круга)) $ z^n-1$ на $ z-1 $.


Определение можно сделать более формальным, если ввести следующее преобразование.
Для произвольного полинома $ 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) $.

<note>
Имеется нестыковка в русскоязычном понятии //возвратный полином// (//возвратное уравнение//) и английским выражением //reciprocal polynomial//. Согласно ангоязычной Википедии  //((http://en.wikipedia.org/wiki/Reciprocal_polynomial reciprocal polynomial))// для произвольного полинома $ F(z) $ --- это полином, обозначенный выше $ F^{\ast}(z) $ (да еще с дополнительным сопряжением коэффициентов), а собственно возвратный --- в приведенном выше определении --- полином называется //palindromic polynomial//[[От слова ((http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D0%BB%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80.D1.8B_.D0.BF.D0.B0.D0.BB.D0.B8.D0.BD.D0.B4.D1.80.D0.BE.D0.BC.D0.BE.D0.B2 палиндром)), обозначающего слово или выражение, читающееся одинаково слева направо и справа налево ("А роза упала на лапу Азора" А.Фет.)]].
</note>

!!Т!! **Теорема 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 $.
Следовательно, по ((:polynomial#корни теореме Безу)), 
$ f(z)\equiv (z+1)f_1(z), \deg f_1=\deg f -1 $. Осталось показать, что 
и полином $ f_1(z) $ будет возвратным. С помощью ((:polynomial#схема_хорнера схемы Хорнера)) установим принцип формирования его коэффициентов на примере $ 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}
$$
Для общего случая рассуждения аналогичны. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>


Итак, возвратный полином нечетной степени обязательно имеет корень $ \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 $ по формуле ((:binomial#бином бинома Ньютона)):
$$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 $. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>


!!П!! **Пример.** 

$$
\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} \ . $$



!!?!!  Найти выражения для $ \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 $. Этот способ основан на вычислении ((:dets:resultant результанта)) двух полиномов.

!!Т!! **Теорема 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 $.

<note cert>
Здесь мы встретились с отдельной интересной проблемой: известно, что некоторый полином $ \Psi(z) $ является квадратом какого-то другого полинома $ \Phi(z) $; как найти $ \Phi(z) $, т.е. извлечь квадратный корень из $ \Psi(z) $ ? Имеются разные подходы к решению этой задачи. Наиболее просто реализуемый заключается в вычислении наибольшего общего делителя полинома $ \Psi(z) $ и его производной (см. теорию  <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html> ((:polynomial#производные_от_полинома ЗДЕСЬ)) ):
$$  \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 $), но эти вырождения мне лень сейчас описывать...
</note>

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

$$ f(z)=z^6-6\,z^5+14\,z^4-18\,z^3+14\,z^2-6\,z+1 $$
 из последнего примера представим результант в ((dets:resultant#результант_в_форме_сильвестра форме Сильвестра)):
$$
\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) $. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>



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

$$ 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 \quad \mbox{ при } \ b_n/b_0 = f(-1)/f(1) \, . $$

!!Т!! **Теорема 6.** //Полином// $ f(z) \in \mathbb C[z] $ //четной степени// $ 2n_{} $ //является возвратным тогда и только тогда, когда его можно представить в виде произведения[[Операция $ ^{\ast} $ определена выше.]]// 

$$ 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) $ ((:polynomial#основная_теорема_высшей_алгебры на линейные множители)) будет иметь вид
$$ 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)} \ . $$
Согласно свойству <html>
  <font face="Times">
        <font color="#0000ff" size="+1">3</font>
    </font>
</html>
 из пункта <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:polynomial#преобразования_корней ПРЕОБРАЗОВАНИЕ КОРНЕЙ)) имеет место тождество $ f_2(z) \equiv f_1^{\ast}(z) $. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>
















==Применения==

!!Т!! **Теорема.** //Если ((:algebra2:charpoly характеристический полином))// $ \det (P-\lambda E) $ //вещественной  ((:algebra2:ort_matrix ортогональной матрицы))// $ P $ //не имеет корнем// $ \lambda= +1 $ //или же ((:polynomial#основная_теорема_высшей_алгебры кратность)) этого корня --- четная, то этот полином является возвратным. Если же кратность корня// $ \lambda=+1 $ //нечетная, то частное//  

$$ \frac{\det (P-\lambda E)}{\lambda-1} $$
//является возвратным полиномом.//

**Доказательство** <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html> ((:algebra2:ort_matrix#характеристический_полином_собственные_числа ЗДЕСЬ)).



==Обобщения==

Рассмотрим полином $ 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) $ "симметричен с ((:complex_num#определение комплексным сопряжением))" относительно середины этого набора: 
$$ a_0=\overline{a_{n}},a_1=\overline{a_{n-1}},\dots, a_{j}=\overline{a_{n-j}} \dots  $$

<note>
В отечественной литературе я встречал для подобного полинома название //симметрический// только в ((#istochniki [2])). Не очень удобное название, поскольку возникает коллизия с ((:polynomialm#odnorodnyj_polinom другим объектом)), за которым это название прочно закрепилось.   В англоязычной литературе он называется //self-reciprocal// (см. замечание о терминологии в предыдущем ((#возвратный_полином пункте)) ). В настоящем ресурсе буду называть его **сопряженно-возвратным**.
</note>

!!П!! **Пример.** 

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


<note>
Сопряженно-возвратный полином используется в теории  <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:interpolation:dft#тригонометрический_полином тригонометрических полиномов)).
</note>

!!Т!! **Теорема [Кон]**. //Число корней сопряженно-возвратного полинома внутри единичного круга равно числу различных корней его производной вне этого круга//.

==Задачи==

((:polynomial/reciprocal:problems ЗДЕСЬ))












==Источники==

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

[2]. **Крейн М., Наймарк М.** //Метод симметрических и эрмитовых форм в теории отделения корней
алгебраических уравнений//.-Харьков, ГТТИ, 1936, 39 с.