Многочлены Кравчука

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Многочлены Кравчука
Общая информация
Формула

\mathcal{K}^{(p)}_n(x)=(-1)^n \binom{N}{n} p^n {}_2 F_1(-n,-x;-N;1/p)

Скалярное произведение

(f, g) = \sum\limits^N_{x=0}f(x) g(x) \sigma(x).

Область определения

 x \in {1, 2, ... N}

Дополнительные характеристики
Названы в честь

Кравчук, Михаил Филиппович

Многочлены Кравчука ( М. Ф. Кравчук, 1929) относятся к классическим ортогональным полиномам дискретной переменной на равномерной сетке, для которых соотношение ортогональности представляет собой не интеграл, а ряд или конечную сумму: \sum\limits^N_{x=0}k^{(p)}_n(x)k^{(p)}_m(x) \sigma(x)= d_n^2,\delta_{m,n}.

Здесь \sigma(x)=\binom{N}{x} p^x q^{N-x} — весовая функция, d_n=\sqrt{\binom{N}{n}(pq)^n} — квадратичная норма, 0<p<1, \quad 0<q<1, \quad p+q=1. Для p=q=1\left/2\right. весовая функция с точностью до постоянного множителя 1\left/ 2^N\right. сводится к биномиальному коэффициенту.

Рекуррентное соотношение для этих многочленов имеет вид (n+1)k^{(p)}_{n+1}(x)+pq\left(N-n+1\right)k^{(p)}_{n-1}(x)= \bigl[ x+n(p-q)-pN
\bigr]k^{(p)}_n (x).

Путем несложных преобразований его можно привести к форме

f_{n+1}\frac{k^{(p)}_{n+1}(x)}{d_{n+1}}+f_{n}\frac{k^{(p)}_{n-1}(x)}{d_{n-1}}= \left( rx+\varepsilon n+\Delta \right)\frac{k^{(p)}_n (x)}{d_n},

где

f_n=\sqrt{\frac{n(N+1-n)}{N}},\quad
 r=\frac{1}{\sqrt{pqN}},\quad \varepsilon=r(p-q),\quad  \Delta=-rpN.

Многочлены Кравчука могут быть выражены через гипергеометрическую функцию Гаусса:

k^{(p)}_n(x)=(-1)^n \binom{N}{n} p^n {}_2 F_1(-n,-x;-N;1/p)

В пределе при N\to\infty многочлены Кравчука переходят в многочлены Эрмита:

\lim\limits_{N\to\infty} \left(2/Npq\right)^{n/2}n! ;k_n^{(p)} \left( Np +
\sqrt{2Npq},x \right) = H_n(x)

Первые четыре полинома для простейшего случая p=q=1/2:

  • \mathcal{K}_0(x, N) = 1
  • \mathcal{K}_1(x, N) = -2x + N
  • \mathcal{K}_2(x, N) = 2x^2 - 2Nx + {N\choose 2}
  • \mathcal{K}_3(x, N) = -\frac{4}{3}x^3 + 2Nx^2 - \left(N^2 - N + \frac{2}{3}\right)x + {N \choose 3}

Литература[править | править вики-текст]

  • Sur une généralisation des polynomes d’Hermite. M. Krawtchouk. C.R.Acad. Sci. 1929. T.189, No.17. P.620 — 622 — статья, в которой впервые введены многочлены Кравчука; по ссылке доступны французский оригинал и переводы на английский и русский языки.
  • А. Ф. Никифоров, С. К. Суслов, В. Б. Уваров. Классические ортогональные полиномы дискретной переменной. Москва, «Наука», 1985.
  • Krawtchouk Polynomials Home Page — сайт, посвященный многочленам Кравчука, содержит, в частности, обширную библиографию.

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