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

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

<math>p_0(x),\ p_1(x),\ p_2(x),\ \ldots</math>,

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

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

Определение

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

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

<math>w : ~(a,b) \to \mathbb{R}</math>

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

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

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

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

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

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

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

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

<math>p_0(x),p_1(x),\cdots,p_n(x),\cdots</math>

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

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

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

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

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

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

<math>{p_{n+1}(x)\ =\ (A_nx+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)},</math>

где

<math>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}}, </math>

<math>r_n=\frac{k'_n}{k_n}, \quad h_n= \langle p_n(x),p_n(x) \rangle</math>,

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

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

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

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

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

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

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

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

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

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

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

<math>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</math>

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

<math>a\ \langle p_n,\ xp_j \rangle\ =\ {\lambda}_j \langle p_j,\ p_j \rangle</math>

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

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

<math>p_{n+1}(x)\ =\ (ax+b)\ p_n(x)\ -\ c\ p_{n-1}(x)</math>.

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

<math>\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}</math>,

или при <math>y \to x</math>

<math>\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]</math>

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

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

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

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

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

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

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

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

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

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

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

<math>

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

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

<math>S(x)=\sum_{i=0}^n {\alpha}_i\ p_i(x)</math>,

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

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

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

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

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

<math>{Q(x)}\,f + {L(x)}\,f' + {\lambda}f = 0,</math>

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

<math>(R(x)y')' + W(x)\,\lambda\,y = 0,</math>

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

• <math>P_n(x)</math> — полином степени n, зависящий от <math>{\lambda}_n</math>

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

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

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

<math>{\lambda}_n = - n \left( \frac{n-1}{2} Q + L' \right)</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

<math>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)</math>

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

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

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

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

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

<math>P_n^{m}(x) = aP_{n+1}^{m+1}(x) + bP_n^{m+1}(x) + cP_{n-1}^{m+1}(x),</math>

<math>P_n^{m}(x) = (ax+b)P_n^{m+1}(x) + cP_{n-1}^{m+1}(x),</math>

<math>Q(x)P_n^{m+1}(x) = (ax+b)P_n^{m}(x) + cP_{n-1}^{m}(x).</math>

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

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

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

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

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

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

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

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

<math>\lambda_n = n(n+1+\alpha+\beta)</math>

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

<math>P_{n+1}(x) = (A_n\,x+B_n)\,P_n(x) - C_n\,P_{n-1}(x),</math>

где

<math>A_n=\frac{(2n+1+\alpha+\beta)(2n+2+\alpha+\beta)}{2(n+1)(n+1+\alpha+\beta)},</math>

<math>B_n=\frac{({\alpha}^2-{\beta}^2)(2n+1+\alpha+\beta)}{2(n+1)(2n+\alpha+\beta)(n+1+\alpha+\beta)},</math>

<math>C_n=\frac{(n+\alpha)(n+\beta)(2n+2+\alpha+\beta)}{(n+1)(n+1+\alpha+\beta)(2n+\alpha+\beta)}</math>

• Нормировка

<math>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!</math>

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

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

<math>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)}.</math>

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

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

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

<math>(1-x^2)\,y - (2\alpha+1)\,x\,\,y' + {\lambda}\,y = 0</math>

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

<math>\lambda_n = n(n+2\alpha)</math>

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

<math>(n+1)\,C_{n+1}^{(\alpha)}(x) = 2(n+\alpha)x\,C_n^{(\alpha)}(x) - (n+2\alpha-1)\,C_{n-1}^{(\alpha)}(x)</math>

• Нормировка

<math>C_n^{(\alpha)}(1)=\frac{\Gamma(n+2\alpha)}{n!\,\Gamma(2\alpha)}</math> если <math>\alpha\ne0,\qquad</math> <math> 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})}</math>

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

<math>C_n^{(\alpha+1)}(x) = \frac{1}{2\alpha}\! \ \frac{d}{dx}C_{n+1}^{(\alpha)}(x)</math>

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

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

<math>P_n(x) = C_n^{(1/2)}(x).</math>

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

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

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

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

<math>\lambda_n = n(n+1)</math>

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

<math>(n+1)\,P_{n+1}(x) = (2n+1)x\,P_n(x) - n\,P_{n-1}(x)</math>

• Нормировка

<math>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!</math>

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

<math>P_0(x)=1;</math>

<math>P_1(x)=x;</math>

<math>P_2(x)=(3x^2-1) / 2;</math>

<math>P_3(x)=(5x^3-3x) / 2;</math>

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

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

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

<math>T_n(x) = \cos(n\,arccos(x)).</math>

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

<math>T_n(x) = \lim_{\alpha \to 0}n\,\Gamma(\alpha)\,C_n^{(\alpha)}.</math>

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

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

<math>(1-x^2)\,y - x\,y' + {\lambda}\,y = 0</math>

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

<math>\lambda_n = n^2</math>

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

<math>T_{n+1}(x) = 2x\,T_n(x) - T_{n-1}(x)</math>

• Нормировка

<math>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}} </math>

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

<math>U_n = \frac{1}{n+1}\,T_{n+1}'</math>

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

<math>(1-x^2)\,y - 3x\,y' + {\lambda}\,y = 0</math>

• Нормировка

<math>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}}</math>

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

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

<math>L_n(x) = L_n^{(0)}(x).</math>

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

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

<math>x\,y + (\alpha + 1-x)\,y' + {\lambda}\,y = 0\, \qquad (x^{\alpha+1}\,e^{-x}\, y')' + {\lambda}\,x^{\alpha}\,e^{-x}\,y = 0</math>

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

<math>\lambda_n = n</math>

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

<math>(n+1)\,L_{n+1}^{(\alpha)}(x) = (2n+1+\alpha-x)\,L_n^{(\alpha)}(x) - (n+\alpha)\,L_{n-1}^{(\alpha)}(x)</math>

• Нормировка

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

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

<math>L_n^{(\alpha+1)}(x) = - \frac{d}{dx}L_{n+1}^{(\alpha)}(x)</math>

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

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

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

<math>y - 2xy' + {\lambda}\,y = 0\, \qquad (e^{-x^2}\,y')' + e^{-x^2}\,\lambda\,y = 0</math>

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

<math>\lambda_n = 2n</math>

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

<math>H_{n+1}(x) = 2x\,H_n(x) - 2n\,H_{n-1}(x)</math>

• Нормировка

<math>k_n = 2^n, \qquad h_n=2^n\,n!\,\sqrt{\pi}, \qquad e_n=(-1)^n</math>

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

<math>H_0(x) = 1</math>

<math>H_1(x) = 2x</math>

<math>H_2(x) = 4x^2-2</math>

<math>H_3(x) = 8x^3-12x</math>

<math>H_4(x) = 16x^4-48x^2+12</math>

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

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

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

<math>\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)</math>,

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

<math>

\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} </math>

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

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

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

<math>\mu_n=\int_a^b{w(x)x^ndx}</math>

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

<math> 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] </math>.

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

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

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

<math>

\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} </math> Поскольку матрица имеет две совпадающие строки для <math>k < n</math>.

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

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

<math>{p_{n+1}(x)\ =\ (x-\alpha_n)\ p_n(x)\ -\ \gamma_n\ p_{n-1}(x)},</math>

где

<math>\alpha_n = \frac{\langle x p_n, p_n\rangle}{\langle p_n, p_n\rangle}, \qquad \gamma_n = \frac{\langle x p_n, p_{n-1}\rangle}{\langle p_{n-1}, p_{n-1}\rangle}</math>.

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

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

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

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

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

Ссылки

• 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. [www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521782012 Classical and Quantum Orthogonal Polynomials in One Variable]. — Cambridge: Cambridge Univ. Press, 2005. — ISBN 0-521-78201-5.
• Vilmos Totik (2005). «[arxiv.org/abs/math.CA/0512424 Orthogonal Polynomials]». Surveys in Approximation Theory 1: 70–125.