Методы наивысшей алгебраической точности (Гаусса - Кристоффеля)

Материал из MachineLearning.

Версия от 04:55, 21 октября 2008; Василий Ломакин (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Содержание

1 Постановка задачи
2 Изложение метода
3 Анализ метода и оценка ошибок
4 Числовой пример
5 Список литературы
6 См. также

Постановка задачи

Рассмотрим задачу поиска определённого интеграла вида

( 1 )

$I=\int_a^b{f(x)\rho(x)dx},\ \rho(x)>0,$

где функция $f(x)$ непрерывна на отрезке $[a,b]$ , а весовая функция $\rho(x)$ непрерывна на интервале $(a,b)$ . Выразить интеграл через элементарные функции в общем случае не удаётся, поэтому обычно $f(x)$ заменяют на некоторую аппроксимирующую функцию $\varphi(x)\approx f(x)$ . Она подбирается таким образом, чтобы интеграл от неё легко считался в элементарных функциях. Стандартный пример $\varphi(x)$ - некоторый обобщённый интерполяционный многочлен. При этом $f(x)$ заменяется линейным выражением, со значениями в узлах в качестве коэффициентов:

( 2 )

$f(x)=\sum_{i=0}^n {f(x_i)\varphi_i(x)} + r(x),$

где функция $r(x)$ - остаточный член аппроксимации. Подстановкой (2) в (1) получаем формулу численного интегрирования (квадратурную формулу):

( 3 )

$F=\sum_{i=0}^n {c_i f(x_i)} + R,$

$c_i = \int_a^b{\varphi(x)\rho(x)dx},\ \ R=\int_a^b{r(x)\rho(x)dx}$ ,

где $x_i$ называются узлами, $c_i$ - весами, а $R$ - погрешностью или остаточным членом. Интеграл приближённо заменяется суммой, причём узлы и коэффициенты этой суммы не зависят от $f(x)$ . Таким образом, задача сводится к отысканию подходящих наборов узлов и весов, таких, чтобы обеспечить минимизацию погрешности $R$ в приемлемое время.

Изложение метода

Параметрами формулы (3) являются узлы и веса. В известных формулах численного интегрирования, таких как формулы трапеций, Симпсона, принято фиксировать положение узлов и по ним находить веса. Таким образом в них не полностью используются возможности общей формулы. Логично предположить, что выбор оптимального положения узлов приведёт к улучшению работы метода.

Итак, формула (3) с n узлами содержит $2n$ параметров, столько же коэффициентов у многочлена степени $2n-1$ . Значит, параметры можно подобрать так, чтобы квадратурная формула (3)

$F=\int_a^b{f(x)\rho(x)dx}\approx \sum_{i=0}^n {c_i f(x_i)}$

была точна для любого многочлена степени $2n-1$ . Покажем, как находятся узлы и веса этих формул.

Будем считать, что вес положителен $\rho(x)>0$ , непрерывен на $(a,b)$ , может обращаться в нуль или бесконечность на концах отрезка так, чтобы существовал $\int_a^b\rho(x)dx$ . Известно^{[источник?]}, что при выполнении этих условий существует полная система алгебраических многочленов $P_m(x)$ , ортогональных на $[a,b]$ с заданным весом:

(4)

$\int_a^b P_k(x)P_m(x)\rho(x)dx=\delta_k_m ||P_k(x)||^2_L_2$

Все нули этих многочленов действительны и расположены на интервале $(a,b)$ .

Составим по узлам интегрирования многочлен n-й степени $\omega_n(x)=\prod_{k=1}^n(x-x_k)$ . Функция $f(x)=\omega_n(x)P_m(x)$ при $m \le n-1$ является многочленом степени не выше $2n-1$ . Следовательно, для неё формула Гаусса-Кристоффеля точна. Тогда получим:

(5)

$\int_a^b\omega_n(x)P_m(x)\rho(x)dx=\sum_{k=1}^n c_k \omega_n(x_k) P_m(x_k)=0$

так как $\omega_n(x)=0$ . Значит многочлен $\omega_n(x)$ ортогонален всем многочленам $P_m(x)$ степени $m \le n-1$ .

Если разложить $\omega_n(x)$ в ряд по рассматриваемым ортогональным многочленам и подставить этот ряд в условие ортогональности (5), то получим:

(6)

$\omega_n(x)=\sum_{k=0}^n b_k P_k(x)$ ,

$\0=\int_a^b \omega_n(x) P_m(x) \rho(x)dx = b_m||P_m||^2,\ m \le n-1$ ,

т.е. все коэффициенты разложения $b_m=0$ при $m \le n-1$ . Это значит, что $\omega_n(x)$ с точностью до численного множителя совпадает с $P_n(x)$ . Значит, узлами формулы Гаусса-Кристоффеля являются нули многочленов соответствующей степени $P_n(x)$ , ортогональных на $[a,b]$ с весом $\rho(x)$ .

Веса интегрирования нетрудно определить, если узлы уже найдены. Функция

$\psi_m(x)=\prod_{k=1,\ k \not= 1}^n (x-x_k)/(x_m-x_k)$

есть многочлен степени n-1, т.е. для неё формула Гаусса-Кристоффеля точна. Подставляя её в формулу (3) и учитывая, что эта формула равна нулю во всех узлах, кроме m-го, получим веса формулы Гаусса-Кристоффеля:

(7)

$c_m=\int_a^b \rho(x)\left{ \prod_{k=1,\ k \not= 1}^n (x-x_k)/(x_m-x_k) \right}dx$

Формулы Гаусса-Кристоффеля называют также формулами наивысшей алгебраической точности, поскольку для произвольного многочлена степени выше $2n-1$ формула (3) с $n$ узлами уже не может быть точной.

Анализ метода и оценка ошибок

Рассмотрим некоторые частные случаи:

Собственно формула Гаусса соответствует $\rho(x)=1$ . Линейным преобразованием аргумента можно перейти к отрезку $a=-1,\ b=1$ . На нём ортогональны с единичным весом многочлены Лежандра. Если обозначить их узлы и соответствующие веса через $\xi_k,\ \gamma_k$ , то обратным линейным преобразованием можно получить узлы и веса для произвольного отрезка
$x_k=\frac12 (a+b)+\frac12 (b-a)\xi_k$ ,

$c_k=\frac12 (b-a)\gamma_k,\ 1 \le k \le n$ .
В частности при $n=1$ получаем формулу средних. Погрешность формулы Гаусса (приводится без вывода) пропорциональна той производной, которая соответствует низшей неучтённой формуле аргумента; верхняя граница погрешности равна
$max|R|=\frac{(b-a)^{2n+1}(n!)^4}{(2n+1)((2n)!)^3}M_{2n} \approx \frac{b-a}{2.5\sqrt{n}} {\left( {\frac{b-a}{3n}} \right)}^{2n}M_{2n}$

$M_{2n}=\max_{[a,b]}|f^{(2n)}(x)|$ .
Формула Гаусса рассчитана на функции, имеющие достаточно высокие производные, причём не слишком большие по абсолютной величине. Для таких функций формула обеспечивает очень высокую точность при небольшом числе узлов, ибо численный коэффициент в остаточном члене быстро убывает с ростом $n$ .
Формула Эрмита позволяет интегрировать на отрезке $[-1,\ 1]$ с весом $\rho(x)=\frac{1}{\sqrt{1-x^2}}$ . При этих условиях ортогональны многочлены Чебышева первого рода $T_n(x)$ . Соответствующие узлы и веса интегрирования равны:
$\xi_k=cos {\left[ {\pi(k-\frac12)n} \right]} ,\ \gamma_k=\frac{\pi}{n},\ 1 \le k \le n$
Отметим, что веса во всех узлах одинаковы. На произвольный отрезок эти узлы и веса преобразуются так же, как в формуле Гаусса. Погрешность формулы Эрмита не превышает
$max|R|=\pi \frac{M_{2n}}{\left[ 2^{n-1}(2n)! \right]}$
.

Числовой пример

Формулы Гаусса-Кристоффеля рассчитаны на получение очень высокой точности уже при небольшом количестве узлов $n \approx 4..10$ . Поэтому для них не строят обобщённых формул вида $\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{f(x_{i-1/2})h}$ , как, например, для метода прямоугольников. Приведём примеры конкретных узлов и весов формул Гаусса-Кристоффеля для наиболее употребительных весовых функций. Здесь же указаны пределы интегрирования $[a,b]$ и выражения для ортогональных многочленов.

$\rho(x)=1,\ a=-1,\ b=1$ :
многочлены Лежандра: $L_0(x)=1,\ L_1(x)=x,\ L_2(x)=\frac12 (3x^2-1),\ L_3(x)=\frac12 (5x^3-3x),\ L_4(x)=\frac18 (35x^4-30x^2+3),\ L_5(x)=\frac18(63x^5-70x^3+15x).$
$n=1:\ \xi_1=0;\ \gamma_1=2.$
$n=2:\ -\xi_1=\xi_2=\sqrt{1/3};\ \gamma_1=\gamma_2=1.$
$n=3:\ -\xi_1=\xi_3=\sqrt{3/5},\ \xi_2=0;\ \gamma_1=\gamma_3=5/9,\ \gamma_2=8/9.$
$n=4:\ -\xi_1=\xi_4=\sqrt{(15+2 sqrt{30})/35},\ -\xi_2=\xi_3=\sqrt{(15-2 sqrt{30})/35};\ -\gamma_1=\gamma_4=(18-\sqrt{30})/36,\ \gamma_2=\gamma_3=(18+\sqrt{30})/36.$
$n=5:\ -\xi_1=\xi_5=\sqrt{(35+2 \sqrt{70})/63},\ -\xi_2=\xi_4=\sqrt{(35+2 \sqrt{70})/63},\ \xi_3=0;\ \gamma_1=\gamma_5=(322-13\sqrt{70})/900,\ \gamma_2=\gamma_4=(322-13\sqrt{70})/900,\ \gamma_3=128/225.$
$\rho(x)=\frac{1}{sqrt{1-x^2}},\ a=-1,\ b=1$ :
многочлены Чебышева первого рода: $T_0(x)=1,\ T_1(x)=x,\ T_2(x)=2x^2-1,\ T_3(x)=4x^3-3x,\ T_4(x)=8x^4-8x^2+1,\ T_5(x)=16x^5-20x^3+5x,\ T_6(x)=32x^6-48x^4+18x^2-1$
$\xi_i^{(n)}=cos{\left[ \frac{\pi(i-1/2)}{n} \right]},\ \gamma_i^{(n)}=\frac{\pi}{n},\ 1 \le i \le n$
$\rho(x)=sqrt{1-x^2},\ a=-1,\ b=1$ :
многочлены Чебышева второго рода: $U_0(x)=1,\ U_1(x)=2x,\ U_2(x)=4x^2-1,\ U_3(x)=8x^3-4x,\ U_4(x)=16x^4-12x^2+1,\ U_5(x)=32x^5-32x^3+6x$
$\xi_m^{n}=cos{\frac{\pi m}{n+1}},\ 1 \le m \le n;$
$n=1:\ \gamma_1=\pi/2$
$n=2:\ \gamma_1=\gamma_2=\pi/4$
$n=3:\ \gamma_1=\gamma_3=\pi/8,\ \gamma_2=\pi/4$
$n=4:\ \gamma_1=\gamma_4=\pi (5-sqrt5)/40,\ \gamma_2=\gamma_3=\pi(5+sqrt5)/40$
$n=5:\ \gamma_1=\gamma_5=\pi/24,\ \gamma_2=\gamma_4=\pi/8,\ \gamma_3=\pi/6.$