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

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

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

$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_{n}x+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\leq 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)\geq 0$. С другой стороны, многочлен $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}\geq ||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$. Далее по индукции.

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

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

${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_{n}W(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 \neq 0,\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\neq 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{aligned}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{aligned}}$

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

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

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

$\mu _{n}=\int _{a}^{b}{w(x)x^{n}dx}$

моменты весовой функции, тогда многочлен $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{aligned}\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{aligned}}$

Поскольку матрица имеет две совпадающие строки для $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 xp_{n},p_{n}\rangle }{\langle p_{n},p_{n}\rangle }},\qquad \gamma _{n}={\frac {\langle xp_{n},p_{n-1}\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 University Press, 2005. — ISBN 0-521-78201-5.
• Vilmos Totik. Orthogonal Polynomials (неопр.) // Surveys in Approximation Theory. — 2005. — Т. 1. — С. 70—125.
• Бейтмен Г., Эрдейи А. . Функции Бесселя, функции параболического цилиндра, ортогональные многочлены // Высшие трансцендентные функции. Т. 2. / Пер. с англ. Н. Я. Виленкина. — М.: Наука, 1966. — 296 с.