Ортогональные многочлены

Пафнутий Львович Чебышёв

В математике последовательностью ортогональных многочленов называют бесконечную последовательность действительных многочленов

$~p_0(x),\ p_1(x),\ p_2(x),\ \ldots$,

где каждый многочлен $~p_n(x)$ имеет степень $~n$, а также любые два различных многочлена этой последовательности ортогональны друг другу в смысле некоторого скалярного произведения, заданного в пространстве $~L^2$.

Понятие ортогональных многочленов было введено в конце XIX в. в работах Чебышёва П. Л. по непрерывным дробям и позднее развито Марковым А. А. и Стилтьесом Т. И. и нашло различные применения во многих областях математики и физики.

Определение

Ортогональность с весом

Пусть $~(a,b)$ — промежуток на вещественной оси (конечный или бесконечный). Этот промежуток называется интервалом ортогональности. Пусть

$w : ~(a,b) \to \mathbb{R}$

заданная непрерывная, строго положительная внутри промежутка $~(a,b)$ функция. Такая функция называется весовой или просто весом. Функция $~w(x)$ связана с пространством функций $~L_{2}$, для которых сходится интеграл

$\int_{a}^{b} \left[f(x)\right]^2 w(x) \; dx < \infty$.

В полученном пространстве можно ввести скалярное произведение по формуле

$\langle f, g \rangle = \int_{a}^{b} f(x) g(x) w(x) \; dx$ для вещественных функций,

$\langle f, g \rangle = \int_{a}^{b} f(x) \overline{g(x)} w(x) \; dx$ для комплекснозначных функций.

Если скалярное произведение двух функций равно нулю $~\langle f, g \rangle = 0$, то такие функции называются ортогональными с весом $~w(x)$. Как правило, среди ортогональных полиномов рассматриваются только вещественных функции.

Классическая формулировка

Систему многочленов

$~p_0(x),p_1(x),\cdots,p_n(x),\cdots$

называют ортогональной, если

1. $~p_n(x)$ — многочлен степени $~n$,
2. $\langle p_m,p_n \rangle = \delta_{mn} h_{n}$, где $~\delta_{mn}$ — символ Кронекера, $~h_{n}$ — нормировочный множитель.

Ортогональный базис называется ортонормированным, если все его элементы имеют единичную норму $||p_n||=h_n=1$. Некоторые классические многочлены, представленные ниже, могут быть нормированы по какому-либо другому правилу. Для таких многочленов значения $~h_n$ отличаются от единицы и указаны в таблице внизу.

Общие свойства последовательностей ортогональных многочленов

Рекуррентные соотношения

Любые ортогональные полиномы удовлетворяют следующей рекуррентной формуле, связывающей три последовательных многочлена из системы:

${p_{n+1}(x)\ =\ (A_nx+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)},$

где

$A_n=\frac{k_{n+1}}{k_n},\quad B_n=A_n \left(r_{n+1}-r_n \right), \quad C_n= \frac {A_n h_n} {A_{n-1} h_{n-1}},$

$r_n=\frac{k'_n}{k_n}, \quad h_n= \langle p_n(x),p_n(x) \rangle$,

$~k_n$ и $~k'_n$ — коэффициенты при членах $~x^n$ и $~x^{n-1}$ в полиноме $~p_n(x).$

Эта формула остаётся справедливой и для $~n=0$, если положить $~p_{-1}(x)=0$.

Доказательство  

Докажем, что для любого n существуют такие коэффициенты a, b и c, что выполняется последнее рекуррентное соотношение.

• Выберем a так, чтобы коэффициент при $x^{n+1}$ в многочлене $p_{n+1}(x)$ занулялся

$a\ x\ p_n(x)\ -\ p_{n+1}(x)$ - многочлен n-ой степени.

• Выберем b так, чтобы коэффициент при $x^n$ в многочлене $p_{n+1}(x)$ занулялся

$(ax+b)\ p_n(x)\ -\ p_{n+1}(x)$ - многочлен (n-1)-ой степени.

• Разложим многочлен в ряд (это возможно, так как система ортогональных многочленов полна)

$(ax+b)\ p_n(x)\ -\ p_{n+1}(x)\ =\ \sum_{i=0}^{n-1} {\lambda}_i p_i(x)$

• Полученное выражение умножим скалярно на $p_j(x)$ степени $j\le n-1$

$a\ \langle x\ p_n, p_j \rangle - b\ \langle p_n, p_j\rangle\ =\ \sum_{i=0}^{n-1} {\lambda}_i \langle p_i, p_j \rangle$

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

$a\ \langle p_n,\ xp_j \rangle\ =\ {\lambda}_j \langle p_j,\ p_j \rangle$

• Если $j < n-1$, то многочлен $xp_j(x)$ все ещё имеет степень меньше n и ортогонален к $p_n(x)$. Следовательно, $\lambda_j = 0$ для $j < n-1$.

Таким образом, ненулевой коэффициент только для $j = n-1$ и, положив $c = \lambda_{n-1}$, получаем искомое соотношение

$p_{n+1}(x)\ =\ (ax+b)\ p_n(x)\ -\ c\ p_{n-1}(x)$.

Формула Кристоффеля-Дарбу

$\sum_{k=0}^{n}\frac{p_k(x)p_k(y)}{h_k}=\frac{k_n}{k_{n+1}h_n}\frac{p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)}{x-y}$,

или при $y \to x$

$\sum_{k=0}^{n}h_k^{-1}\left[p_k(x)\right]^2=\frac{k_n}{k_{n+1}h_n}\left[p'_{n+1}(x)p_n(x)-p_{n+1}(x)p'_n(x)\right]$

Корни многочленов

Все корни многочлена $~p_n(x)$ являются простыми, вещественными и все расположены внутри интервала ортогональности $~\left[a;b\right]$.

Доказательство  

Предположим, что $~p_n(x)$ внутри интервала ортогональности меняет знак лишь в $~m<n$ точках. Тогда существует многочлен $~s_m(x)$ степени $~m$ такой, что $~p_n(x)s_m(x)\ge0$. С другой стороны, многочлен $~s_m(x)$ можно представить в виде линейной комбинации многочленов $~p_0(x), p_1(x), \cdots, p_m(x)$, а значит $~s_m(x)$ ортогонален $~p_n(x)$, то есть $~\langle p_n(x),s_m(x)\rangle=0$. Полученное противоречие и доказывает наше утверждение.

Между двумя последовательными корнями многочлена $~p_n(x)$ расположен в точности один корень многочлена $~p_{n+1}(x)$ и по крайней мере один корень многочлена $~p_m(x)$, при $~m>n$.

Минимальность нормы

Каждый многочлен $p_n(x)$ в ортогональной последовательности имеет минимальную норму среди всех многочленов $P_n(x)$ такой же степени и с таким же первым коэффициентом.

Доказательство  

Для данного n любой многочлен p(x) степени n с таким же первым коэффициентом может быть представлен как

$p(x) = p_n(x) + \sum_{i=0}^{n-1} {\alpha}_i\ p_i(x).$

Используя ортогональность, квадратная норма p(x) удовлетворяет

$||p(x)||^2 = \langle p(x),p(x)\rangle = ||p_n(x)||^2 + \sum_{i=0}^{n-1} {\alpha}_i^2||p_i(x)||^2 \ge ||p_n(x)||^2.$

Так как нормы являются положительными, необходимо взять квадратные корни обеих сторон и получится результат.

Полнота системы

Система ортогональных многочленов $p_i(x)$ является полной. Это значит, что любой многочлен $S(x)$ степени n может быть представлен в виде ряда

$S(x)=\sum_{i=0}^n {\alpha}_i\ p_i(x)$,

где $\alpha$ коэффициенты разложения.

Доказательство  

Доказывается с помощью математической индукции. Выберем $\ {\alpha}_n$ так, чтобы $\ S(x)-{\alpha}_n P_n(x)$ был многочленом степени n-1. Далее по индукции.

Дифференциальные уравнения, приводящие к ортогональным многочленам

Очень важный класс ортогональных многочленов возникает при решении дифференциального уравнения следующего вида:

${Q(x)}\,f'' + {L(x)}\,f' + {\lambda}f = 0,\,$

где $Q(x)$ и $L(x)$ заданные многочлены второго и первого порядка, соответственно, а $f(x)$ и $\lambda$ неизвестные функция и коэффициент. Это уравнение называется задачей Штурма — Лиувилля и может быть переписано в его более стандартной форме

$(R(x)y')' + W(x)\,\lambda\,y = 0,\,\,$

где $\,R(x) = e^{\int\frac{L(x)}{Q(x)}\,dx},\, W(x) =\frac{R(x)}{Q(x)}.\,$ Решение этого уравнения приводит к множеству собственных чисел ${\lambda}_0, {\lambda}_1, {\lambda}_2, \dots$ и множеству собственных функций $P_0, P_1, P_2, \dots\,$, обладающих следующими свойствами:

• $P_n(x)$ - полином степени n, зависящий от ${\lambda}_n$

• последовательность $P_0, P_1, P_2, \dots\,$ ортогональна с весовой функцией $W(x)$

• Промежуток ортогональности зависит от корней многочлена Q, причём корень L находится внутри промежутка ортогональности

• Числа $\lambda_n$ и полиномы $P_n(x)$ могут быть получены из формул

${\lambda}_n = - n \left( \frac{n-1}{2} Q'' + L' \right)$

$P_n(x) = \frac{1}{e_n\,W(x)} \ \frac{d^n}{dx^n}\left(W(x)[Q(x)]^n\right)\,$ формула Родрига.

Дифференциальное уравнение имеет нетривиальные решения только при выполнения одного из следующих условий. Во всех этих случаях при изменении масштаба или/и сдвига области определения и выбора способа нормировки многочлены решения сводятся к ограниченному набору классов, которые называются классическими ортогональными полиномами

1. Якобиподобные многочлены

Q — многочлен второго порядка, L — первого. Корни Q различны и действительны, корень L лежит строго между корнями Q. Первые коэффициенты Q и L имеют один знак. При помощи линейного преобразования уравнение сводится к $Q(x)=1-x^2$ с интервалом ортогональности $[-1,1]$. Решениями являются многочлены Якоби $P_n^{(\alpha, \beta)}(x)$ или их частные случаи многочлены Гегенбауэра $C_n^{(\alpha)}(x)$, Лежандра $P_n(x)$ или Чебышёва обоих типов $T_n(x)$, $U_n(x)$.

2. Лягерроподобные многочлены

Q — многочлен первого порядка, L — первого. Корни Q и L различны. Первые коэффициенты Q и L имеют один знак, если корень L меньше корня Q и наоборот. Сводится к $Q(x)=x$ и интервалу ортогональности $[0,\infty)$. Решениями являются обобщённые многочлены Лягерра $L_n^{(\alpha)}(x)$ или их частному случаю многочленам Лягерра $L_n(x)$.

3. Эрмитоподобные многочлены

Q — не нулевая константа, L — первого. Первые коэффициенты Q и L имеют противоположный знак. Сводится к $Q(x)=1$ и интервалу ортогональности $(-\infty,\infty)$. Решениями являются многочлены Эрмита $H_n(x)$.

Производные ортогональных полиномов

Обозначим $P_n^{m}(x)$ как m-ую производную полинома $P_n(x)$. Производная $P_n^{m}(x)$ является полиномом степени $n-m$ и обладает следующими свойствами:

• ортогональность

Для заданного m последовательность полиномов $P_m^{m}, P_{m+1}^{m}, P_{m+2}^{m}, \dots$ ортогональна с весовой функцией $W(x)[Q(x)]^m$

• формула Родрига

$P_n^{m} = \frac{1}{e_nW(x)[Q(x)]^m} \ \frac{d^{n-m}}{dx^{n-m}}\left(W(x)[Q(x)]^m\right)$

• дифференциальное уравнение

${Q(x)}\,y'' + (m\,Q'(x)+L(x))\,y' + [{\lambda}_n-{\lambda}_m]\ y = 0$, где $y(x)=P_n^{m}(x)$

• дифференциальное уравнение второго вида

$(R(x)[Q(x)]^m\ y')' + [\lambda_n-\lambda_m]W(x)[Q(x)]^{m}\ y = 0$, где $y(x)=P_n^{m}(x)$

• рекуррентные соотношения (для удобства у коэффициентов a, b и c опущены индексы n и m)

$P_n^{m}(x) = aP_{n+1}^{m+1}(x) + bP_n^{m+1}(x) + cP_{n-1}^{m+1}(x),\,$

$P_n^{m}(x) = (ax+b)P_n^{m+1}(x) + cP_{n-1}^{m+1}(x),\,$

$Q(x)P_n^{m+1}(x) = (ax+b)P_n^{m}(x) + cP_{n-1}^{m}(x).\,$

Классические ортогональные многочлены

Классические ортогональные полиномы, которые происходят из дифференциального уравнения описанного выше, имеют много важных приложений в таких областях как: математическая физика, численные методы, и многие другие. Ниже приводятся их определения и основные свойства.

Многочлены Якоби

Многочлены Якоби обозначаются $P_n^{(\alpha, \beta)}(x)$, где параметры $\alpha$ и $\beta$ вещественные числа больше −1. Если $\alpha$ и $\beta$ не равны, полиномы перестают быть симметричными относительно точки $x=0$.

• Весовая функция $W(x)=(1-x)^\alpha(1+x)^\beta$ на промежутке ортогональности $[-1,1]$

• Дифференциальные уравнения

$(1-x^2)\,y'' + (\beta-\alpha-[\alpha+\beta+2]\,x)\,y' + {\lambda}\,y = 0$

• Собственные числа

$\lambda_n = n(n+1+\alpha+\beta)$

• Рекуррентная формула

$P_{n+1}(x) = (A_n\,x+B_n)\,P_n(x) - C_n\,P_{n-1}(x),\,$

где

$A_n=\frac{(2n+1+\alpha+\beta)(2n+2+\alpha+\beta)}{2(n+1)(n+1+\alpha+\beta)},\,$

$B_n=\frac{({\alpha}^2-{\beta}^2)(2n+1+\alpha+\beta)}{2(n+1)(2n+\alpha+\beta)(n+1+\alpha+\beta)},\,$

$C_n=\frac{(n+\alpha)(n+\beta)(2n+2+\alpha+\beta)}{(n+1)(n+1+\alpha+\beta)(2n+\alpha+\beta)}\,$

• Нормировка

$P_n^{(\alpha, \beta)}(1)=\frac{\Gamma(n+1+\alpha)}{n!\,\Gamma(1+\alpha)}, \qquad h_n=\frac{2^{\alpha+\beta+1}\,\Gamma(n\!+\!\alpha\!+\!1)\,\Gamma(n\!+\!\beta\!+\!1)} {n!(2n\!+\!\alpha\!+\!\beta\!+\!1)\Gamma(n\!+\!\alpha\!+\!\beta\!+\!1)}, \qquad k_n=\frac{\Gamma(2n+1+\alpha+\beta)}{n!\,2^n\,\Gamma(n+1+\alpha+\beta)}, \qquad e_n=(-2)^n\,n!$

Многочлены Гегенбауэра

Многочлены Гегенбауэра обозначаются $C_n^{(\alpha)}(x)$, где параметр $\alpha$ вещественное число больше −1/2. Он выводится из многочленов Якоби для равных параметров $\alpha$ и $\beta$

$C_n^{(\alpha)}(x) = \frac{\Gamma(2\alpha\!+\!n)\,\Gamma(\alpha\!+\!1/2)} {\Gamma(2\alpha)\,\Gamma(\alpha\!+\!n\!+\!1/2)}\! \ P_n^{(\alpha-1/2, \alpha-1/2)}.$

Остальные Якобиподобные многочлены являются частным случаем полиномов Гегенбауэра с выбранным параметром $\alpha$ и соответствующей нормализацией.

• Весовая функция $W(x)=(1-x^2)^{\alpha-1/2}$ на промежутке ортогональности $[-1,1]$

• Дифференциальные уравнения

$(1-x^2)\,y'' + (2\alpha+1)\,x\,\,y' + {\lambda}\,y = 0$

• Собственные числа

$\lambda_n = n(n+2\alpha)$

• Рекуррентная формула

$(n+1)\,C_{n+1}^{(\alpha)}(x) = 2(n+\alpha)x\,C_n^{(\alpha)}(x) - (n+2\alpha-1)\,C_{n-1}^{(\alpha)}(x)\,$

• Нормировка

$C_n^{(\alpha)}(1)=\frac{\Gamma(n+2\alpha)}{n!\,\Gamma(2\alpha)}\,$ если $\alpha\ne0,\qquad$ $h_n=\frac{\pi\,2^{1-2\alpha}\Gamma(n+2\alpha)}{n!(n+\alpha)(\Gamma(\alpha))^2}, \qquad k_n=\frac{\Gamma(2n+2\alpha)\Gamma(\frac{1}{2}+\alpha)}{n!\,2^n\,\Gamma(2\alpha)\Gamma(n+\frac{1}{2}+\alpha)}, \qquad e_n = \frac{(-2)^n\,n!\,\Gamma(2\alpha)\,\Gamma(n+\frac{1}{2}+\alpha)} {\Gamma(n+2\alpha)\Gamma(\alpha+\frac{1}{2})}$

• Прочие свойства

$C_n^{(\alpha+1)}(x) = \frac{1}{2\alpha}\! \ \frac{d}{dx}C_{n+1}^{(\alpha)}(x)$

Многочлены Лежандра

Многочлены Лежандра обозначаются $P_n(x)$ и являются частным случаем многочленов Гегенбауэра с параметром $\alpha=1/2$

$P_n(x) = C_n^{(1/2)}(x).\,$

• Весовая функция $W(x)=1$ на промежутке ортогональности $[-1,1]$

• Дифференциальные уравнения

$(1-x^2)\,y'' - 2x\,y' + {\lambda}\,y = 0, \qquad ([1-x^2]\,y')' + \lambda\,y = 0$

• Собственные числа

$\lambda_n = n(n+1)$

• Рекуррентная формула

$(n+1)\,P_{n+1}(x) = (2n+1)x\,P_n(x) - n\,P_{n-1}(x)\,$

• Нормировка

$P_n(1)=1, \qquad h_n=\frac{2}{2n+1}, \qquad k_n=\frac{(2n)!}{2^n\,(n!)^2}, \qquad e_n=(-2)^n\,n!$

• Первые несколько многочленов

$P_0(x)=1;\,$

$P_1(x)=x;\,$

$P_2(x)=(3x^2-1) / 2;$

$P_3(x)=(5x^3-3x) / 2;$

$P_4(x)=(35x^4-30x^2+3) / 8;$

Многочлены Чебышёва

Многочлен Чебышева $T_n(x)$ часто используется для аппроксимации функций как многочлен степени $n$, который меньше всего отклоняется от нуля на интервале $[-1,1]$

$T_n(x) = \cos(n\,Arccos(x)).\,$

Является частным случаем нормированного многочлена Гегенбауэра для параметра $\alpha \to 0$

$T_n(x) = \lim_{\alpha \to 0}n\,\Gamma(\alpha)\,C_n^{(\alpha)}.\,$

• Весовая функция $W(x)=(1-x^2)^{-1/2}$ на промежутке ортогональности $[-1,1]$

• Дифференциальное уравнение

$(1-x^2)\,y'' - x\,y' + {\lambda}\,y = 0$

• Собственные числа

$\lambda_n = n^2$

• Рекуррентная формула

$T_{n+1}(x) = 2x\,T_n(x) - T_{n-1}(x)\,$

• Нормировка

$T_n(1)=1, \qquad h_n=\left\{ \begin{matrix} \pi &:~n=0 \\ \pi/2 &:~n\ne 0 \end{matrix}\right. ,\qquad k_n = 2^{n-1}, \qquad e_n=(-2)^n\,\frac{\Gamma(n+1/2)}{\sqrt{\pi}}$

Многочлен Чебышева второго рода $U_n(x)$ характеризуются как многочлен, интеграл от абсолютной величины которого на интервале $[-1, +1]$ меньше всего отклоняется от нуля

$U_n = \frac{1}{n+1}\,T_{n+1}'\,$

• Весовая функция $W(x)=(1-x^2)^{1/2}$ на промежутке ортогональности $[-1,1]$
• Дифференциальное уравнение

$(1-x^2)\,y'' - 3x\,y' + {\lambda}\,y = 0$

• Нормировка

$U_n(1)=n+1, \qquad h_n=\pi / 2, \qquad k_n = 2^n, \qquad e_n=2(-2)^n\,\frac{\Gamma(n+3/2)}{(n+1)\,\sqrt{\pi}}$

Многочлены Лягерра

Ассоциированные или обобщённые многочлены Лягерра обозначаются $L_n^{(\alpha)}(x)$, где параметр $\alpha$ вещественное число больше -1. Для $\alpha = 0$ обобщённые многочлены сводятся к обычным многочленам Лягерра

$L_n(x) = L_n^{(0)}(x).\,$

• Весовая функция $W(x)=x^{\alpha}e^{-x}$ на промежутке ортогональности $[0,\infty)$

• Дифференциальные уравнения

$x\,y'' + (\alpha + 1-x)\,y' + {\lambda}\,y = 0\, \qquad (x^{\alpha+1}\,e^{-x}\, y')' + {\lambda}\,x^{\alpha}\,e^{-x}\,y = 0\,$

• Собственные числа

$\lambda_n = n$

• Рекуррентная формула

$(n+1)\,L_{n+1}^{(\alpha)}(x) = (2n+1+\alpha-x)\,L_n^{(\alpha)}(x) - (n+\alpha)\,L_{n-1}^{(\alpha)}(x)\,$

• Нормировка

$k_n=\frac{(-1)^n}{n!}, \qquad h_n=\frac{\Gamma(n+\alpha+1)}{n!}, \qquad e_n=n!$

• Прочие свойства

$L_n^{(\alpha+1)}(x) = - \frac{d}{dx}L_{n+1}^{(\alpha)}(x)$

Многочлены Эрмита

• Весовая функция $W(x)=e^{-x^2}$ на промежутке ортогональности $[-\infty,\infty]$

• Дифференциальные уравнения

$y'' - 2xy' + {\lambda}\,y = 0\, \qquad (e^{-x^2}\,y')' + e^{-x^2}\,\lambda\,y = 0\,$

• Собственные числа

$\lambda_n = 2n$

• Рекуррентная формула

$H_{n+1}(x) = 2x\,H_n(x) - 2n\,H_{n-1}(x)\,$

• Нормировка

$k_n = 2^n, \qquad h_n=2^n\,n!\,\sqrt{\pi}, \qquad e_n=(-1)^n$

• Первые несколько многочленов

$H_0(x) = 1\,$

$H_1(x) = 2x\,$

$H_2(x) = 4x^2-2\,$

$H_3(x) = 8x^3-12x\,$

$H_4(x) = 16x^4-48x^2+12\,$

Построение ортогональных многочленов

Процесс ортогонализации Грама-Шмидта

Система ортогональных многочленов $f_1, f_2, \ldots, f_k$ может быть построена путём применения процесса Грама-Шмидта к системе многочленов $g_k(x)=x^k$ следующим образом. Определим проектор как

$\mathrm{proj}_{f}\,(g) = {\langle f, g\rangle\over\langle f, f\rangle}f = { \int_{x_1}^{x_2} f(x) g(x) W(x) \; dx \over \int_{x_1}^{x_2} (f(x))^2 W(x) \; dx} f(x)$,

тогда ортогональные полиномы последовательно вычисляются по схеме

$\begin{align} f_1 & = g_1, \\ f_2 & = g_2-\mathrm{proj}_{f_1}\,(g_2), \\ f_3 & = g_3-\mathrm{proj}_{f_1}\,(g_3)-\mathrm{proj}_{f_2}\,(g_3), \\ & {}\ \ \vdots \\ f_k & = g_k-\sum_{j=1}^{k-1}\mathrm{proj}_{f_j}\,(g_k). \end{align}$

Данный алгоритм относится к численно неустойчивым алгоритмам. При вычислении коэффициентов разложения ошибки округления и погрешности численного интегрирования накапливаются с увеличением номера полинома.

По моментам весовой функции

Весовая функция $~w(x)$, заданная на промежутке $~\left[a;b\right]$, однозначно определяет систему ортогональных многочленов $\{p_n(x)\}_{n=0}^{\infty}$ с точностью до постоянного множителя. Обозначим через числа

$\mu_n=\int_a^b{w(x)x^ndx}$

моменты весовой функции, тогда многочлен $p_n(x)$ может быть представлен в виде:

$p_n(x) = \det\left[ \begin{matrix} \mu_0 & \mu_1 & \mu_2 & \cdots & \mu_n \\ \mu_1 & \mu_2 & \mu_3 & \cdots & \mu_{n+1} \\ \mu_2 & \mu_3 & \mu_4 & \cdots & \mu_{n+2} \\ \vdots & \vdots & \vdots & & \vdots \\ \mu_{n-1} & \mu_n & \mu_{n+1} & \cdots & \mu_{2n-1} \\ 1 & x & x^2 & \cdots & x^n \end{matrix} \right]$.

Сложность вычисления ортогональных полиномов определяется сложностью вычисления определителя матрицы. Существующие алгоритмические реализации вычисления требуют минимум $O(n^3)$ операций.

Доказательство  

Докажем, что заданный таким образом многочлен $p_n(x)$ ортогонален всем многочленам степени меньше n. Рассмотрим скалярное произведение $p_n(x)$ на $x^k$ для $k < n$.

$\begin{align} \int_\mathbb{R} x^k p_n(x)\,d\mu & {} = \int_\mathbb{R} x^k \det\left[ \begin{matrix} \mu_0 & \mu_1 & \mu_2 & \cdots & \mu_n \\ \mu_1 & \mu_2 & \mu_3 & \cdots & \mu_{n+1} \\ \mu_2 & \mu_3 & \mu_4 & \cdots & \mu_{n+2} \\ \vdots & \vdots & \vdots & & \vdots \\ \mu_{n-1} & \mu_n & \mu_{n+1} & \cdots & \mu_{2n-1} \\ 1 & x & x^2 & \cdots & x^n \end{matrix} \right] \,d\mu \\ \\ & {} = \int_\mathbb{R} \det\left[ \begin{matrix} \mu_0 & \mu_1 & \mu_2 & \cdots & \mu_n \\ \mu_1 & \mu_2 & \mu_3 & \cdots & \mu_{n+1} \\ \mu_2 & \mu_3 & \mu_4 & \cdots & \mu_{n+2} \\ \vdots & \vdots & \vdots & & \vdots \\ \mu_{n-1} & \mu_n & \mu_{n+1} & \cdots & \mu_{2n-1} \\ x^k & x^{k+1} & x^{k+2} & \cdots & x^{k+n} \end{matrix} \right] \,d\mu \\ \\ & {} = \det\left[ \begin{matrix} \mu_0 & \mu_1 & \mu_2 & \cdots & \mu_n \\ \mu_1 & \mu_2 & \mu_3 & \cdots & \mu_{n+1} \\ \mu_2 & \mu_3 & \mu_4 & \cdots & \mu_{n+2} \\ \vdots & \vdots & \vdots & & \vdots \\ \mu_{n-1} & \mu_n & \mu_{n+1} & \cdots & \mu_{2n-1} \\ \displaystyle \int_\mathbb{R} x^k \, d\mu & \displaystyle \int_\mathbb{R} x^{k+1} \, d\mu & \displaystyle \int_\mathbb{R} x^{k+2} \, d\mu & \cdots & \displaystyle \int_\mathbb{R} x^{k+n} \, d\mu \end{matrix} \right] \\ \\ & {} = \det \left[ \begin{matrix} \mu_0 & \mu_1 & \mu_2 & \cdots & \mu_n \\ \mu_1 & \mu_2 & \mu_3 & \cdots & \mu_{n+1} \\ \mu_2 & \mu_3 & \mu_4 & \cdots & \mu_{n+2} \\ \vdots & \vdots & \vdots & & \vdots \\ \mu_{n-1} & \mu_n & \mu_{n+1} & \cdots & \mu_{2n-1} \\ \mu_k & \mu_{k+1} & \mu_{k+2} & \cdots & \mu_{k+n} \end{matrix} \right] \\ \\ & {} = 0. \end{align}$

Поскольку матрица имеет две совпадающие строки для $k < n$.

По рекуррентным формулам

Если выбрать нормировку многочлена $p_n(x)$ таким образом, что коэффициент $k_n$ при главное члене равен единицы, рекуррентное соотношение может быть переписано в следующем виде:

${p_{n+1}(x)\ =\ (x-\alpha_n)\ p_n(x)\ -\ \gamma_n\ p_{n-1}(x)},$

где

$\alpha_n = \frac{\langle x p_n, p_n\rangle}{\langle p_n, p_n\rangle}, \qquad \gamma_n = \frac{\langle p_n, p_n\rangle}{\langle p_{n-1}, p_{n-1}\rangle}$.

Применение ортогональных многочленов

Ортогональные полиномы применяются для построения точных квадратурных формул

$\int\limits_{\Omega} f(x) w(x) dx \approx \sum\limits_{i=1}^{n} w_i f(x_i),$

где $x_i$ и $w_i$ являются узлами и весами квадратурной формулы. Квадратурная формула является точной для всех полиномов $f(x)$ до степени $2n-1$ включительно. При этом узлы $x_i$ есть корни n-го полинома из последовательности полиномов $p_0(x),p_1(x), ...$, ортогональных с весовой функцией $w(x)$. Веса $w_i$ вычисляются из формулы Кристоффеля-Дарбу.

Так же многочлены Чебышева первого $T_n(x)$ и второго $U_n(x)$ типа часто используется для аппроксимации функций.

Примечания

Ссылки

• Gabor Szego Orthogonal Polynomials. — Colloquium Publications - American Mathematical Society, 1939. — ISBN 0-8218-1023-5
• Dunham Jackson Fourier Series and Orthogonal Polynomials. — New York: Dover, 1941, 2004. — ISBN 0-486-43808-2
• Refaat El Attar Special Functions and Orthogonal Polynomials. — Lulu Press, Morrisville NC 27560, 2006. — ISBN 1-4116-6690-9
• Theodore Seio Chihara An Introduction to Orthogonal Polynomials. — Gordon and Breach, New York, 1978. — ISBN 0-677-04150-0

Для дальнейшего чтения

• Ismail, Mourad E. H. Classical and Quantum Orthogonal Polynomials in One Variable. — Cambridge: Cambridge Univ. Press, 2005. — ISBN 0-521-78201-5
• Vilmos Totik (2005). «Orthogonal Polynomials». Surveys in Approximation Theory 1: 70–125.

Для улучшения этой статьи желательно?: Перевести текст с иностранного языка на русский. Проверить достоверность указанной в статье информации. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.