Русская Википедия:Многочлены Шапиро
Многочлены Шапиро — последовательность многочленов, впервые изученная Гарольдом Шапиро в 1951 году при рассмотрении величин некоторых специальных тригонометрических сумм[1]. С точки зрения обработки сигналов, полиномы Шапиро обладают хорошими автокорреляционными свойствами[2], и их значения в единичном круге малы. Первые члены последовательности:
- <math>
\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} </math>,
где вторая последовательность, Q, называется дополнительной к первой последовательности, P.
Построение
Полиномы Шапиро <math>P_n(z)</math> могут быть получены из последовательности Рудина-Шапиро <math>a_n</math> (<math>a_n = 1</math>, если число подстрок 11 в двоичной записи числа n четно, и <math>a_n = -1</math> иначе (OEIS Шаблон:OEIS2C)). Так, <math>a_0 = 1, a_1 = 1, a_2 = 1, a_3 = -1</math> и т. д.
<math>P_n</math> есть частичная сумма порядка <math>2^n - 1</math> степенного ряда <math>f(z) = a_0 + a_1 z + a_2 z^2 + ...</math>
Последовательность Рудина-Шапиро <math>a_n</math> имеет структуру, схожую с фрактальной — например, <math>a_n = a_{2n}</math>, то есть подпоследовательность <math>a_0, a_2, a_4, ...</math> совпадает с исходной <math>\{a_n\}</math>. Это свойство приводит к примечательным функциональным уравнениям, которым удовлетворяет <math>f(z)</math>.
Дополнительные полиномы Шапиро, <math>Q_n(z)</math>, могут быть определены через эту же последовательность, через отношение <math>Q_n(z) = (-1)^n z^{2n} P_n(\frac{-1}{z})</math>, или же через рекуррентные формулы:
- <math>P_0(z)=1; ~~ Q_0(z) = 1 ; </math>
- <math>P_{n+1}(z) = P_n(z) + z^{2^n} Q_n(z) ; </math>
- <math>Q_{n+1}(z) = P_n(z) - z^{2^n} Q_n(z) . </math>
Свойства
Дополнительная последовательность, <math>Q_n</math>, соответствующая <math>P_n</math>, однозначно определяется следующими свойствами:
- Степень <math>Q_n</math> равна <math>2^n - 1</math>.
- Коэффициенты <math>Q_n</math> равны <math>\pm 1</math>, коэффициент при нулевой степени равен 1.
- Равенство <math>|P_n(z)|^2 + |Q_n(z)|^2 = 2^{n+1}</math> выполнено на всей единичной окружности <math>z \in \Complex, |z| = 1</math>.
Наиболее интересным свойством последовательности <math>P_n</math> является то, что модуль значения <math>P_n(z)</math> на единичной окружности ограничен <math>\sqrt{2^{n+1}}</math>, что по порядку равно <math>L_2</math>-норме <math>P_n</math>. Многочлены с коэффициентами <math>\pm 1</math>, максимум модуля которых на единичной окружности близок к среднему значению модуля, полезны в различных приложениях теории коммуникаций (например, форма антенны и сжатие данных). Свойство (3) показывает, что (P, Q) образуют пару Голея.
Другие свойства этих многочленов[3]:
- <math> P_{n+1}(z) = P_n(z^2) + z P_n(-z^2) ;</math>
- <math> Q_{n+1}(z) = Q_n(z^2) + z Q_n(-z^2) ;</math>
- <math>P_n(z) P_n(1/z) + Q_n(z) Q_n(1/z) = 2^{n+1} ;</math>
- <math>P_{n+k+1}(z) = P_k(z)P_n(z^{2k+1}) + z^{2k}Q_k(z)P_n(-z^{2k+1}) ;</math>
- <math>P_n(1) = 2^{\lfloor (n+1)/2 \rfloor}; {~}{~} P_n(-1) = (1+(-1)^n)2^{\lfloor n/2 \rfloor - 1} .</math>
См. также
Примечания
Список литературы
- Шаблон:Книга Chapter 4.
