Многочлены Шапиро

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Многочлены Шапиро — последовательность многочленов, впервые изученная Гарольдом Шапиро в 1951 году при рассмотрении величин некоторых специальных тригонометрических сумм.[1] С точки зрения обработке сигналов, полиномы Шапиро обладают хорошими автокорреляционными свойствами[2], и их значения в единичном круге малы. Первые члены последовательности:


\begin{align}
P_1(x) & {} =1 + x \\
P_2(x) & {} =1 + x + x^2 - x^3 \\
P_3(x) & {} =1 + x + x^2 - x^3 + x^4 + x^5 - x^6 + x^7 \\
... \\
Q_1(x) & {} =1 - x \\
Q_2(x) & {} =1 + x - x^2 + x^3 \\
Q_3(x) & {} =1 + x + x^2 - x^3 - x^4 - x^5 + x^6 - x^7 \\
... \\
\end{align}
,

где вторая последовательность, Q, называется дополнительной к первой последовательности, P.

Построение[править | править вики-текст]

Полиномы Шапиро P_n(z) могут быть получены из последовательности Рудина-Шапиро a_n (a_n = 1, если число подстрок 11 в двоичной записи числа n четно, и a_n = -1 иначе (OEIS A020985)). Так, a_0 = 1, a_1 = 1, a_2 = 1, a_3 = -1 и т. д.

P_n есть частичная сумма порядка 2^n - 1 степенного ряда f(z) = a_0 + a_1 z + a_2 z^2 + ...

Последовательность Рудина-Шапиро a_n имеет структуру, схожую с фрактальной — например, a_n = a_{2n}, то есть подпоследовательность a_0, a_2, a_4, ... совпадает с исходной \{a_n\}. Это свойство приводит к примечательным функциональным уравнениям, которым удовлетворяет f(z).

Дополнительные полиномы Шапиро, Q_n(z), могут быть определены через эту же последовательность, через отношение Q_n(z) = (-1)^n z^{2n} P_n(\frac{-1}{z}), или же через рекуррентные формулы

P_0(z)=1; ~~ Q_0(z) = 1 ;
P_{n+1}(z) = P_n(z) + z^{2^n} Q_n(z) ;
Q_{n+1}(z) = P_n(z) - z^{2^n} Q_n(z) .

Свойства[править | править вики-текст]

Дополнительная последовательность, Q_n, соответствующая P_n, однозначно определяется следующими свойствами:

  1. Степень Q_n равна 2^n - 1.
  2. Коэффициенты Q_n равны \pm 1, коэффициент при нулевой степени равен 1.
  3. Равенство |P_n(z)|^2 + |Q_n(z)|^2 = 2^{n+1} выполнено на всей единичной окружности z \in \C, |z| = 1.

Наиболее интересным свойством последовательности P_n является то, что модуль значения P_n(z) на еденичной окружности ограничен \sqrt{2^{n+1}}, что по порядку равно L_2 норме P_n. Многочлены с коэффициентами \pm 1, чей максимум модуля на единичной окружности близок к среднему значению модуля, полезны в различных приложениях теории коммуникаций (например, форма антенны и сжатие данных). Свойство (3) показывает, что (P, Q) образуют пару Голея.

Другие свойства этих многочленов[3]:

 P_{n+1}(z) = P_n(z^2) + z P_n(-z^2) ; \,
 Q_{n+1}(z) = Q_n(z^2) + z Q_n(-z^2) ; \,
P_n(z) P_n(1/z) + Q_n(z) Q_n(1/z) = 2^{n+1} ; \,
P_{n+k+1}(z) = P_k(z)P_n(z^{2k+1}) + z^{2k}Q_k(z)P_n(-z^{2k+1}) ; \,
P_n(1) = 2^{\lfloor (n+1)/2 \rfloor}; {~}{~} P_n(-1) = (1+(-1)^n)2^{\lfloor n/2 \rfloor - 1} . \,

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. John Brillhart and L. Carlitz (May, 1970). «Note on the Shapiro polynomials». Proceedings of the American Mathematical Society (Proceedings of the American Mathematical Society, Vol. 25, No. 1) 25 (1): 114–118. DOI:10.2307/2036537.
  2. Somaini, U. (June 26 1975). «Binary sequences with good correlation properties». Electronics Letters 11 (13): 278–279. DOI:10.1049/el:19750211.
  3. J. Brillhart; J.S. Lomont, P. Morton (1976). «Cyclotomic properties of the Rudin–Shapiro polynomials». J. Reine Angew. Math. 288: 37–65.

Список литературы[править | править вики-текст]