Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Построение квадратурных формул)
(Построение квадратурных формул)
Строка 85: Строка 85:
<center><tex>L[(s-\frac{1}{2})^3]=\int_0^1{(s-\frac{1}{2})^3ds}=0.</tex></center>
<center><tex>L[(s-\frac{1}{2})^3]=\int_0^1{(s-\frac{1}{2})^3ds}=0.</tex></center>
-
Формулы треугольника и трапеции точны для линейной функции,т.е. для полинома первой степени, в чем легко убедиться непосредственно. В общем случае в качестве <tex>P_m(s)</tex> можно выбрать интерполяционный полином Лагранжа
+
Формулы [[Методы прямоугольников и трапеций|треугольника и трапеции]] точны для линейной функции,т.е. для полинома первой степени, в чем легко убедиться непосредственно. В общем случае в качестве <tex>P_m(s)</tex> можно выбрать интерполяционный полином Лагранжа
<center><tex>P_m(s)=\sum_{k=0}^m{l_k^{(m)}(s)f(s_k)},</tex></center>
<center><tex>P_m(s)=\sum_{k=0}^m{l_k^{(m)}(s)f(s_k)},</tex></center>

Версия 16:29, 26 сентября 2008

автор: Гордеев Дмитрий

Содержание

Введение

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

Задача численного интегрирования состоит в нахождении приближенного значения интеграла
J[f]=\int_a^b{f(x)dx},
(1)

где f(x) - заданная и интегрируемая на отрезке [a,b] функция. На отрезке вводится сетка \omega=\{x_i:x_0=a<x_1<\ldots<x_i<\ldots<x_N=b\} и в качестве приближенного значения интеграла рассматривается число

J_N[f]=\sum_{i=0}^N {c_i f(x_i)},
(2)

где f(x_i) - значения функции f(x) в узлах x=x_i , где c_i - весовые множители, зависящие только от узлов, но не зависящие от выбора f(x). Формула (2) называется квадратурной формулой.

Задача численного интегрирования при помощи квадратур состоит в отыскании таких узлов \{x_i\} и таких весов \{c_i\}, чтобы погрешность квадратурной формулы
D[f]=\sum_{i=0}^N{c_i f(x_i)} - \int_a^b{f(x)dx} = J_N[f] - J[f]


была минимальной по модулю для функции из заданного класса (величина D[f] зависит от гладкости f(x)). Погрешность зависит как от расположения узлов, так и от выбора весовых коэффициентов. Введем на [a,b] равномерную сетку с шагом h, т.е. множество точек \omega_h=\{x_i=a+ih, i=0,1,\ldots,N,hN=b-a}, и представим интеграл (1) в виде суммы интегралов по частичным отрезкам:

\int_a^b{f(x)dx}=\sum_{i=1}^N{\int_{x_{i-1}}^{x_i}{f(x)dx}}.
(3)

Для построения формулы численного интегрирования на всм отрезке [a,b] достаточно построить квадратурную формулу для интеграла

\int_{x_{i-1}}^{x_i}{f(x)dx}
(4)

на частичном отрезке [x_{i-1},x_i] и воспользоваться свойством (3).

Построение квадратурных формул

В силу вышеизложенного выше, вычисление приближенного значения интеграла производится при помощи квадратурной формулы
\int_a^b{f(s)ds}\approx\sum_{k=0}^m{c_kf(s_k)}.

Данную формулу при помощи замены x=a+(b-a)s, f(x)=f(a+(b-a)s) можно привести к стандартному виду

\int_0^1{f(s)ds}\approx\sum_{k=0}^m{c_kf(s_k)}.
(5)

В общем случае узлы и веса неизвестны и подлежат определению.

Рассмотрим случай, когда узлы заданы и требуется найти веса квадратурной формулы \{c_k\}. Будем пользоваться требованием: формула (5) должна быть точной для любого полинома P_r(s) степени r\le m. Для того чтобы полином степени r удовлетворял данному требованию, достаточно потребовать, чтобы квадратурная формула была точной для любого одночлена s^\sigma степени \sigma (\sigma=0,1,\ldots,r). Учитывая, что J[s^\sigma]=\frac{1}{\sigma+1}, получаем m+1 уравнение

c_0+c_1+\ldots+c_m=1,
c_0 s_0+c_1 s_1+\ldots+c_m s_m=\frac{1}{2},


.........................................


c_0 s_0^\sigma + c_1 s_1^\sigma + \ldots + c_m s_m^\sigma=\frac{1}{\sigma+1},


.........................................


c_0 s_0^m + c_1 s_1^m + \ldots + c_m s_m^m=\frac{1}{m+1}.

Эта система имеет единственное решение, так как ее определителем является определитель Вандермонда, отличный от нуля если нет совпадающих узлов, s_0<s_q<\ldots<s_m.

Так, полагая m=2,s_0=0,s_1=\frac{1}{2},s_2=1, имеем систему c_0+c_1+c_2=1, \frac{c_1}{2}+c_2=\frac{1}{2}, \frac{c_1}{4}+c_2=\frac{1}{3}, решением которой являются веса формулы Симпсона: c_0=c_2=\frac{1}{6},c_1=\frac{4}{6}. Таким образом, формула Симпсона является точной для полинома второй степени. Однако, в силу симметрии, она является точной и для всех полиномов третьей степени:

P_3(s)=1+\alpha_1 (s-\frac{1}{2})+\alpha_2 (s-\frac{1}{2})^2 +\alpha_3 (s-\frac{1}{2})^3,

так как она точна для f(s)=(s-\frac{1}{2})^3:

J_3[(s-\frac{1}{2})^3]=\frac{1}{6}((-\frac{1}{2})^3+4\cdot 0+(\frac{1}{2})^3)=0,
L[(s-\frac{1}{2})^3]=\int_0^1{(s-\frac{1}{2})^3ds}=0.

Формулы треугольника и трапеции точны для линейной функции,т.е. для полинома первой степени, в чем легко убедиться непосредственно. В общем случае в качестве P_m(s) можно выбрать интерполяционный полином Лагранжа

P_m(s)=\sum_{k=0}^m{l_k^{(m)}(s)f(s_k)},

где l_k^{(m)}(s) - интерполяционный коэффициент Лагранжа. Из равенства

L[P_m]=\int_0^1{P_m(s)ds}=\sum_{k=0}^m{f(s_k)\int_0^1{l_k^{(m)}(s)ds}}=\sum_{k=0}^m{c_k f(s_k)}

видно, что формула (5) верна для полинома степени m, если весовые коэффициенты c_k определяются по формуле

c_k=\int_0^1{l_k^{(m)}(s)ds}.
(6)

Формулы такого типа называют квадратурными формулами Котеса.

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

Анализ метода

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

Рекомендации программисту

Заключение

Список литературы

  • А.А.Самарский, А.В.Гулин.  Численные методы М.: Наука, 1989.
  • А.А.Самарский.  Введение в численные методы М.: Наука, 1982.
Личные инструменты