Методы наивысшей алгебраической точности (Гаусса - Кристоффеля)
Материал из MachineLearning.
м |
(числовой пример) |
||
Строка 26: | Строка 26: | ||
Все нули этих многочленов действительны и расположены на интервале <tex>(a,b)</tex>. | Все нули этих многочленов действительны и расположены на интервале <tex>(a,b)</tex>. | ||
- | Составим по узлам интегрирования многочлен n-й степени <tex>$ \omega_n(x)=\prod_{k=1}^n(x-x_k) $</tex>. Функция <tex>$ f(x)=\omega_n(x)P_m(x) $</tex> при <tex>m \le n-1</tex> является многочленом степени не выше 2n-1. Следовательно, для неё формула Гаусса-Кристоффеля точна. Тогда получим: | + | Составим по узлам интегрирования многочлен n-й степени <tex>$ \omega_n(x)=\prod_{k=1}^n(x-x_k) $</tex>. Функция <tex>$ f(x)=\omega_n(x)P_m(x) $</tex> при <tex>m \le n-1</tex> является многочленом степени не выше <tex>2n-1</tex>. Следовательно, для неё формула Гаусса-Кристоффеля точна. Тогда получим: |
{{eqno|5}} | {{eqno|5}} | ||
<p align="center"> <tex>\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</tex> </p> | <p align="center"> <tex>\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</tex> </p> | ||
Строка 51: | Строка 51: | ||
== Числовой пример == | == Числовой пример == | ||
- | == | + | Формулы Гаусса-Кристоффеля рассчитаны на получение очень высокой точности уже при небольшом количестве узлов <tex>n \approx 4..10</tex>. Поэтому для них не строят обобщённых формул вида <tex>$ \int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{f(x_{i-1/2})h} $</tex>, как, например, для [[Методы прямоугольников и трапеций|метода прямоугольников]]. Приведём примеры конкретных узлов и весов формул Гаусса-Кристоффеля для наиболее употребительных весовых функций. Здесь же указаны пределы интегрирования <tex>[a,b]</tex> и выражения для ортогональных многочленов. |
- | == | + | # <tex>\rho(x)=1,\ a=-1,\ b=1</tex>: <p align="left">многочлены Лежандра: <tex>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).</tex></p><p align="left"><tex>n=1:\ \xi_1=0;\ \gamma_1=2.</tex></p><p align="left><tex>n=2:\ -\xi_1=\xi_2=\sqrt{1/3};\ \gamma_1=\gamma_2=1.</tex></p><p align="left"><tex>n=3:\ -\xi_1=\xi_3=\sqrt{3/5},\ \xi_2=0;\ \gamma_1=\gamma_3=5/9,\ \gamma_2=8/9.</tex></p><p align="left"><tex>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.</tex></p><p align="left"><tex>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.</tex></p> |
+ | # <tex>\rho(x)=\frac{1}{sqrt{1-x^2}},\ a=-1,\ b=1</tex>:<p align="left">многочлены Чебышева первого рода: <tex>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</tex></p><p align="left"><tex>\xi_i^{(n)}=cos{\left[ \frac{\pi(i-1/2)}{n} \right]},\ \gamma_i^{(n)}=\frac{\pi}{n},\ 1 \le i \le n</tex></p> | ||
+ | # <tex>\rho(x)=sqrt{1-x^2},\ a=-1,\ b=1</tex>:<p align="left">многочлены Чебышева второго рода: <tex>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</tex></p><p align="left"><tex>\xi_m^{n}=cos{\frac{\pi m}{n+1}},\ 1 \le m \le n;</tex></p><p align="left"><tex>n=1:\ \gamma_1=\pi/2</tex></p><p align="left"><tex>n=2:\ \gamma_1=\gamma_2=\pi/4</tex></p><p align="left"><tex>n=3:\ \gamma_1=\gamma_3=\pi/8,\ \gamma_2=\pi/4</tex></p><p align="left"><tex>n=4:\ \gamma_1=\gamma_4=\pi (5-sqrt5)/40,\ \gamma_2=\gamma_3=\pi(5+sqrt5)/40</tex></p><p align="left"><tex>n=5:\ \gamma_1=\gamma_5=\pi/24,\ \gamma_2=\gamma_4=\pi/8,\ \gamma_3=\pi/6.</tex></p> | ||
== Список литературы == | == Список литературы == | ||
* ''Н.Н.Калиткин.'' Численные методы М.: Наука, 1978. | * ''Н.Н.Калиткин.'' Численные методы М.: Наука, 1978. | ||
+ | * ''А.А.Самарский, А.В.Гулин.'' Численные методы М.: Наука, 1989. | ||
== См. также == | == См. также == | ||
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] | * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] | ||
+ | * [[Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)|Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)]] | ||
+ | * [[Применение сплайнов для численного интегрирования|Применение сплайнов для численного интегрирования]] | ||
{{stub}} | {{stub}} | ||
[[Категория:Численное интегрирование]] | [[Категория:Численное интегрирование]] | ||
[[Категория:Учебные задачи]] | [[Категория:Учебные задачи]] |
Текущая версия
Содержание |
Постановка задачи
Рассмотрим задачу поиска определённого интеграла вида
где функция непрерывна на отрезке
, а весовая функция
непрерывна на интервале
.
Выразить интеграл через элементарные функции в общем случае не удаётся, поэтому обычно
заменяют на некоторую аппроксимирующую функцию
. Она подбирается таким образом, чтобы интеграл от неё легко считался в элементарных функциях. Стандартный пример
- некоторый обобщённый интерполяционный многочлен. При этом
заменяется линейным выражением, со значениями в узлах в качестве коэффициентов:
где функция - остаточный член аппроксимации. Подстановкой (2) в (1) получаем формулу численного интегрирования (квадратурную формулу):
,
где называются узлами,
- весами, а
- погрешностью или остаточным членом. Интеграл приближённо заменяется суммой, причём узлы и коэффициенты этой суммы не зависят от
.
Таким образом, задача сводится к отысканию подходящих наборов узлов и весов, таких, чтобы обеспечить минимизацию погрешности
в приемлемое время.
Изложение метода
Параметрами формулы (3) являются узлы и веса. В известных формулах численного интегрирования, таких как формулы трапеций, Симпсона, принято фиксировать положение узлов и по ним находить веса. Таким образом в них не полностью используются возможности общей формулы. Логично предположить, что выбор оптимального положения узлов приведёт к улучшению работы метода.
Итак, формула (3) с n узлами содержит параметров, столько же коэффициентов у многочлена степени
. Значит, параметры можно подобрать так, чтобы квадратурная формула (3)
была точна для любого многочлена степени . Покажем, как находятся узлы и веса этих формул.
Будем считать, что вес положителен , непрерывен на
, может обращаться в нуль или бесконечность на концах отрезка так, чтобы существовал
. Известно[источник?], что при выполнении этих условий существует полная система алгебраических многочленов
, ортогональных на
с заданным весом:
Все нули этих многочленов действительны и расположены на интервале .
Составим по узлам интегрирования многочлен n-й степени . Функция
при
является многочленом степени не выше
. Следовательно, для неё формула Гаусса-Кристоффеля точна. Тогда получим:
так как . Значит многочлен
ортогонален всем многочленам
степени
.
Если разложить в ряд по рассматриваемым ортогональным многочленам и подставить этот ряд в условие ортогональности (5), то получим:
,
,
т.е. все коэффициенты разложения при
. Это значит, что
с точностью до численного множителя совпадает с
. Значит, узлами формулы Гаусса-Кристоффеля являются нули многочленов соответствующей степени
, ортогональных на
с весом
.
Веса интегрирования нетрудно определить, если узлы уже найдены. Функция
есть многочлен степени n-1, т.е. для неё формула Гаусса-Кристоффеля точна. Подставляя её в формулу (3) и учитывая, что эта формула равна нулю во всех узлах, кроме m-го, получим веса формулы Гаусса-Кристоффеля:
Формулы Гаусса-Кристоффеля называют также формулами наивысшей алгебраической точности, поскольку для произвольного многочлена степени выше формула (3) с
узлами уже не может быть точной.
Анализ метода и оценка ошибок
Рассмотрим некоторые частные случаи:
- Собственно формула Гаусса соответствует
. Линейным преобразованием аргумента можно перейти к отрезку
. На нём ортогональны с единичным весом многочлены Лежандра. Если обозначить их узлы и соответствующие веса через
, то обратным линейным преобразованием можно получить узлы и веса для произвольного отрезка
,
.
получаем формулу средних. Погрешность формулы Гаусса (приводится без вывода) пропорциональна той производной, которая соответствует низшей неучтённой формуле аргумента; верхняя граница погрешности равна
.
.
- Формула Эрмита позволяет интегрировать на отрезке
с весом
. При этих условиях ортогональны многочлены Чебышева первого рода
. Соответствующие узлы и веса интегрирования равны:
Отметим, что веса во всех узлах одинаковы. На произвольный отрезок эти узлы и веса преобразуются так же, как в формуле Гаусса. Погрешность формулы Эрмита не превышает
.
Числовой пример
Формулы Гаусса-Кристоффеля рассчитаны на получение очень высокой точности уже при небольшом количестве узлов . Поэтому для них не строят обобщённых формул вида
, как, например, для метода прямоугольников. Приведём примеры конкретных узлов и весов формул Гаусса-Кристоффеля для наиболее употребительных весовых функций. Здесь же указаны пределы интегрирования
и выражения для ортогональных многочленов.
-
:
многочлены Лежандра:
-
:
многочлены Чебышева первого рода:
-
:
многочлены Чебышева второго рода:
Список литературы
- Н.Н.Калиткин. Численные методы М.: Наука, 1978.
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.