Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)
Материал из MachineLearning.
Строка 2: | Строка 2: | ||
=== Постановка математической задачи === | === Постановка математической задачи === | ||
- | + | Задача численного интегрирования состоит в нахождении приближенного значения интеграла | |
{{ eqno | 1 }} | {{ eqno | 1 }} | ||
Строка 13: | Строка 13: | ||
где <tex>f(x_i)</tex> - значения функции <tex>f(x)</tex> в узлах <tex>x=x_i</tex> , где <tex>c_i</tex> - ''весовые множители'', зависящие только от узлов, но не зависящие от выбора <tex>f(x)</tex>. Формула {{eqref|2}} называется ''квадратурной формулой''. | где <tex>f(x_i)</tex> - значения функции <tex>f(x)</tex> в узлах <tex>x=x_i</tex> , где <tex>c_i</tex> - ''весовые множители'', зависящие только от узлов, но не зависящие от выбора <tex>f(x)</tex>. Формула {{eqref|2}} называется ''квадратурной формулой''. | ||
- | + | Задача численного интегрирования при помощи квадратур состоит в отыскании таких узлов <tex>\{x_i\}</tex> и таких весов <tex>\{c_i\}</tex>, чтобы ''погрешность квадратурной формулы'' | |
::<tex>D[f]=\sum_{i=0}^N{c_i f(x_i)} - \int_a^b{f(x)dx} = J_N[f] - J[f]</tex> | ::<tex>D[f]=\sum_{i=0}^N{c_i f(x_i)} - \int_a^b{f(x)dx} = J_N[f] - J[f]</tex> | ||
Строка 32: | Строка 32: | ||
=== Построение квадратурных формул === | === Построение квадратурных формул === | ||
- | + | В силу вышеизложенного выше, вычисление приближенного значения интеграла производится при помощи квадратурной формулы | |
::<tex>\int_a^b{f(s)ds}\approx\sum_{k=0}^m{c_kf(s_k)}.</tex> | ::<tex>\int_a^b{f(s)ds}\approx\sum_{k=0}^m{c_kf(s_k)}.</tex> | ||
Строка 85: | Строка 85: | ||
Формулы такого типа называют квадратурными '''формулами Котеса'''. | Формулы такого типа называют квадратурными '''формулами Котеса'''. | ||
+ | |||
+ | == Изложение метода == | ||
+ | |||
+ | === Применение квадратурных формул === | ||
+ | |||
+ | Вернемся к рассмотрению интеграла {{eqref|1}}. Как было показано выше, данный интеграл заменой сводится к интегралу на единичном отрезке <tex>[0,1]</tex>, а следовательно легко обобщить формулы для приближенного вычисления интеграла на единичном отрезке на произвольный. Применим аппарат квадратурных формул. Пусть задано равномерное разбиение отрезка с шагом <tex>h:</tex> <tex>\omega_h=\{x_i=a+ih, i=0,1,\ldots,N;hN=b-a}</tex>, где обозначим <tex>f_i=f(a+ih)</tex>. Пусть также выбрана некоторая квадратурная формула Ньютона-Котеса (то есть выбрана степень полинома <tex>n</tex>, а следовательно каждый полином строится по <tex>n+1</tex> точке сетки). Мы также считаем, что данный набор из <tex>N+1</tex> точки можно разбить на поднаборы по <tex>m</tex> точек с совпадающими крайним, то есть | ||
+ | |||
+ | {{ eqno | 7 }} | ||
+ | ::<tex>N=n*k,</tex> где <tex>k \in \mathbb N.</tex> | ||
+ | |||
+ | Тогда, суммируя значения квадратур на каждом поднаборе, получим приближенное значение искомого интеграла. Если обозначить весовые множители <tex>c_i,i=0 \ldots n,</tex> то приближенное значение интеграла можно записать в виде двойной суммы | ||
+ | |||
+ | ::<tex>\int_a^b{f(x)dx \approx \sum_{j=0}^{k-1}{\sum_{i=0}^n{c_i f_{(i+j*n)}}}</tex> | ||
+ | |||
+ | Данный алгоритм естественным образом обобщается на случай, когда <tex>[a,b]=\bigcup_{i=0}^K{[a_i,b_i]}</tex>, где <tex>a_0=a, b_K=b, b_{i+1}=a_i;i=0\ldots K-1</tex>, а на каждом отрезке <tex>[a_i,b_i]</tex> задана равномерная сетка. Тогда искомый интеграл равен | ||
+ | |||
+ | ::<tex>\int_a^b{f(x)dx} = \sum_{i=0}^K{\int_{a_i}^{b_i}{f(x)dx}},</tex> | ||
+ | |||
+ | а на каждом из отрезков приближенное значение интеграла вычисляется при помощи квадратурных формул. | ||
=== Примеры квадратурных формул === | === Примеры квадратурных формул === | ||
- | + | Приведем примеры квадратурных формул Котеса на равномерной сетке с шагом <tex>h:</tex> <tex>\omega_h=\{x_i=a+ih, i=0,1,\ldots,N;hN=b-a}</tex>, где обозначим <tex>f_i=f(a+ih),</tex> <tex>\xi \in [a,b]</tex>: | |
*для 3 точек(метод Симпсона), <tex>m=2:</tex> | *для 3 точек(метод Симпсона), <tex>m=2:</tex> | ||
::<tex>J_2[f]=\frac{1}{3}h(f_0+4f_1+f_2),</tex> | ::<tex>J_2[f]=\frac{1}{3}h(f_0+4f_1+f_2),</tex> | ||
- | ::<tex> | + | ::<tex>D[f]=\frac{1}{90} h^5 f^{(4)}(\xi),</tex> |
*для 4 точек, <tex>m=3:</tex> | *для 4 точек, <tex>m=3:</tex> | ||
::<tex>J_3[f]=\frac{3}{8}h(f_0+3f_1+3f_2+f_3),</tex> | ::<tex>J_3[f]=\frac{3}{8}h(f_0+3f_1+3f_2+f_3),</tex> | ||
- | ::<tex> | + | ::<tex>D[f]=\frac{3}{80} h^5 f^{(4)}(\xi),</tex> |
*для 5 точек, <tex>m=4:</tex> | *для 5 точек, <tex>m=4:</tex> | ||
::<tex>J_4[f]=\frac{2}{45}h(7f_0+32f_1+12f_2+32f_3+7f_4),</tex> | ::<tex>J_4[f]=\frac{2}{45}h(7f_0+32f_1+12f_2+32f_3+7f_4),</tex> | ||
- | ::<tex> | + | ::<tex>D[f]=\frac{8}{945} h^7 f^{(6)}(\xi),</tex> |
*для 6 точек, <tex>m=5:</tex> | *для 6 точек, <tex>m=5:</tex> | ||
::<tex>J_5[f]=\frac{5}{288}h(19f_0+75f_1+50f_2+50f_3+75f_4+19f_5),</tex> | ::<tex>J_5[f]=\frac{5}{288}h(19f_0+75f_1+50f_2+50f_3+75f_4+19f_5),</tex> | ||
+ | ::<tex>D[f]=\frac{275}{12096} h^7 f^{(6)}(\xi),</tex> | ||
*для 7 точек, <tex>m=6:</tex> | *для 7 точек, <tex>m=6:</tex> | ||
::<tex>J_6[f]=\frac{1}{140}h(41f_0+216f_1+27f_2+272f_3+27f_4+216f_5+41f_6),</tex> | ::<tex>J_6[f]=\frac{1}{140}h(41f_0+216f_1+27f_2+272f_3+27f_4+216f_5+41f_6),</tex> | ||
+ | ::<tex>D[f]=\frac{9}{1400} h^9 f^{(8)}(\xi),</tex> | ||
*для 8 точек, <tex>m=7:</tex> | *для 8 точек, <tex>m=7:</tex> | ||
::<tex>J_7[f]=\frac{7}{17280}h(751f_0+3577f_1+1323f_2+2989f_3+2989f_4+1323f_5+3577f_6+751f_7),</tex> | ::<tex>J_7[f]=\frac{7}{17280}h(751f_0+3577f_1+1323f_2+2989f_3+2989f_4+1323f_5+3577f_6+751f_7),</tex> | ||
+ | ::<tex>D[f]=\frac{8183}{518400} h^9 f^{(8)}(\xi),</tex> | ||
*для 9 точек, <tex>m=8:</tex> | *для 9 точек, <tex>m=8:</tex> | ||
::<tex>J_8[f]=\frac{4}{14175}h(989f_0+5888f_1-928f_2+10496f_3-4540f_4+10496f_5-928f_6+5888f_7+989f_8),</tex> | ::<tex>J_8[f]=\frac{4}{14175}h(989f_0+5888f_1-928f_2+10496f_3-4540f_4+10496f_5-928f_6+5888f_7+989f_8),</tex> | ||
+ | ::<tex>D[f]=\frac{2368}{467775} h^{11} f^{(10)}(\xi),</tex> | ||
*для 10 точек, <tex>m=9:</tex> | *для 10 точек, <tex>m=9:</tex> | ||
::<tex>J_9[f]=\frac{9}{89600}h(2857f_0+15741f_1+1080f_2+19344f_3+5778f_4+5778f_5+19344f_6+1080f_7+15741f_8+2857f_9).</tex> | ::<tex>J_9[f]=\frac{9}{89600}h(2857f_0+15741f_1+1080f_2+19344f_3+5778f_4+5778f_5+19344f_6+1080f_7+15741f_8+2857f_9).</tex> | ||
- | + | ::<tex>D[f]=\frac{173}{14620} h^{11} f^{(10)}(\xi),</tex> | |
- | + | ||
== Анализ метода == | == Анализ метода == |
Версия 19:36, 16 октября 2008
Содержание |
Введение
Постановка математической задачи
Задача численного интегрирования состоит в нахождении приближенного значения интеграла
где - заданная и интегрируемая на отрезке функция. На отрезке вводится сетка и в качестве приближенного значения интеграла рассматривается число
где - значения функции в узлах , где - весовые множители, зависящие только от узлов, но не зависящие от выбора . Формула (2) называется квадратурной формулой. Задача численного интегрирования при помощи квадратур состоит в отыскании таких узлов и таких весов , чтобы погрешность квадратурной формулы
была минимальной по модулю для функции из заданного класса (величина зависит от гладкости ). Погрешность зависит как от расположения узлов, так и от выбора весовых коэффициентов. Введем на равномерную сетку с шагом , т.е. множество точек , и представим интеграл (1) в виде суммы интегралов по частичным отрезкам:
Для построения формулы численного интегрирования на всм отрезке достаточно построить квадратурную формулу для интеграла
на частичном отрезке и воспользоваться свойством (3).
Построение квадратурных формул
В силу вышеизложенного выше, вычисление приближенного значения интеграла производится при помощи квадратурной формулы
Данную формулу при помощи замены можно привести к стандартному виду
В общем случае узлы и веса неизвестны и подлежат определению.
Рассмотрим случай, когда узлы заданы и требуется найти веса квадратурной формулы . Будем пользоваться требованием: формула (5) должна быть точной для любого полинома степени . Для того чтобы полином степени удовлетворял данному требованию, достаточно потребовать, чтобы квадратурная формула была точной для любого одночлена степени . Учитывая, что , получаем уравнение
Эта система имеет единственное решение, так как ее определителем является определитель Вандермонда, отличный от нуля если нет совпадающих узлов, .
Так, полагая , имеем систему , решением которой являются веса формулы Симпсона: . Таким образом, формула Симпсона является точной для полинома второй степени. Однако, в силу симметрии, она является точной и для всех полиномов третьей степени:
так как она точна для :
Формулы треугольника и трапеции точны для линейной функции,т.е. для полинома первой степени, в чем легко убедиться непосредственно. В общем случае в качестве можно выбрать интерполяционный полином Лагранжа
где - интерполяционный коэффициент Лагранжа. Из равенства
видно, что формула (5) верна для полинома степени , если весовые коэффициенты определяются по формуле
Формулы такого типа называют квадратурными формулами Котеса.
Изложение метода
Применение квадратурных формул
Вернемся к рассмотрению интеграла (1). Как было показано выше, данный интеграл заменой сводится к интегралу на единичном отрезке , а следовательно легко обобщить формулы для приближенного вычисления интеграла на единичном отрезке на произвольный. Применим аппарат квадратурных формул. Пусть задано равномерное разбиение отрезка с шагом , где обозначим . Пусть также выбрана некоторая квадратурная формула Ньютона-Котеса (то есть выбрана степень полинома , а следовательно каждый полином строится по точке сетки). Мы также считаем, что данный набор из точки можно разбить на поднаборы по точек с совпадающими крайним, то есть
- где
Тогда, суммируя значения квадратур на каждом поднаборе, получим приближенное значение искомого интеграла. Если обозначить весовые множители то приближенное значение интеграла можно записать в виде двойной суммы
Данный алгоритм естественным образом обобщается на случай, когда , где , а на каждом отрезке задана равномерная сетка. Тогда искомый интеграл равен
а на каждом из отрезков приближенное значение интеграла вычисляется при помощи квадратурных формул.
Примеры квадратурных формул
Приведем примеры квадратурных формул Котеса на равномерной сетке с шагом , где обозначим :
- для 3 точек(метод Симпсона),
- для 4 точек,
- для 5 точек,
- для 6 точек,
- для 7 точек,
- для 8 точек,
- для 9 точек,
- для 10 точек,
Анализ метода
Числовой пример
Рекомендации программисту
Заключение
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- А.А.Самарский. Введение в численные методы М.: Наука, 1982.
- http://mathworld.wolfram.com/Newton-CotesFormulas.html