Методы прямоугольников и трапеций

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Введение)
(→Введение)
Строка 32: Строка 32:
=== Формула прямоугольников ===
=== Формула прямоугольников ===
-
Заменим интеграл {{eqref|3}} выражением <tex>f(x_{i-\frac{1}{2}})h</tex>, где <tex>x_{i-\frac{1}{2}}=x_{i}-0.5h.</tex>
+
Заменим интеграл {{eqref|3}} выражением <tex>f(x_{i-1/2})h</tex>, где <tex>x_{i-1/2}=x_{i}-0.5h.</tex>
Геометрически такая замена означает, что площадь криволинейной трапеции <tex>ABCD</tex> заменяется площадью прямоугольника <tex>ABC'D'</tex> (см. рис. 1). Тогда получим формулу
Геометрически такая замена означает, что площадь криволинейной трапеции <tex>ABCD</tex> заменяется площадью прямоугольника <tex>ABC'D'</tex> (см. рис. 1). Тогда получим формулу
{{ eqno | 5 }}
{{ eqno | 5 }}
-
<p align="center"><tex>\int_{x_{i-1}}^{x_i}{f(x)dx}\approx f(x_{i-\frac{1}{2}})h,</tex></p>
+
<p align="center"><tex>\int_{x_{i-1}}^{x_i}{f(x)dx}\approx f(x_{i-1/2})h,</tex></p>
которая называется ''формулой прямоугольников на частичном отрезке'' <tex>[x_{i-1},x_i].</tex>
которая называется ''формулой прямоугольников на частичном отрезке'' <tex>[x_{i-1},x_i].</tex>
Строка 43: Строка 43:
Погрешность метода {{eqref|5}} определяется величиной
Погрешность метода {{eqref|5}} определяется величиной
-
<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-\frac{1}{2}})h</tex></p>
+
<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h</tex></p>
которую легко оценить с помощью формулы Тейлора. Действительно, запишем <tex>\psi_{i}</tex> в виде
которую легко оценить с помощью формулы Тейлора. Действительно, запишем <tex>\psi_{i}</tex> в виде
{{ eqno | 6 }}
{{ eqno | 6 }}
-
<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{(f(x)-f(x_{i-\frac{1}{2}}))dx}</tex></p>
+
<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{(f(x)-f(x_{i-1/2}))dx}</tex></p>
и воспользуемся разложением
и воспользуемся разложением
-
<p align="center"><tex>f(x)=f(x_{i-\frac{1}{2}})+(x-x_{i-\frac{1}{2}})f'(x_{i-\frac{1}{2}})+\frac{(x-x_{i-\frac{1}{2}})^2}{2}f''(\psi),</tex></p>
+
<p align="center"><tex>f(x)=f(x_{i-1/2})+(x-x_{i-1/2})f'(x_{i-1/2})+\frac{(x-x_{i-1/2})^2}{2}f''(\xi),</tex></p>
 +
 
 +
где <tex>\xi_i=\xi_i(x)\in [x_{i-1},x_i]</tex>. Тогда из {{eqref|6}} получим
 +
 
 +
<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}</tex></p>
 +
 
 +
Обозначая <tex>M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|</tex>, оценим <tex>\xi_i</tex> следующим образом:
 +
 
 +
<p align="center"><tex>|\xi_i|\le M_{2,i} \int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}dx}=\frac{h^3}{24}M_{2,i}</tex></p>
 +
 
 +
Таким образом, для погрешности формулы прямоугольников на частичном отрезке справедлива оценка
 +
 
 +
{{ eqno | 7 }}
 +
<p align="center"><tex>|\xi_i|\le \frac{h^3}{24}M_{2,i}</tex></p>
 +
 
 +
т.е. формула имеет погрешность <tex>O(h^3)</tex> при <tex>h\rightarrow0</tex>.
 +
 
 +
Заметим,что оценка (7) является неулучшаемой, т.е. существует функция <tex>f(x)</tex>, для которой (7) выполняется со знаком равенства. Действительно, для <tex>f(x)=(x-x_{i-1/2})^2</tex> имеем <tex>M_{2,i}=2, f(x_{i-1/2})=0</tex> и
 +
 
 +
<p align="center"><tex>\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h=\frac{h^3}{24}M_{2,i}</tex></p>
 +
 
 +
Суммируя равенства (5) по <tex>i</tex> от <tex>1</tex> до <tex>N</tex>, получим ''составную формулу прямоугольников''
 +
 
 +
{{ eqno | 8 }}
 +
<p align="center"><tex>\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{f(x_{i-1/2})h}</tex></p>
 +
 
 +
Погрешность этой формулы
 +
 
 +
<p align="center"><tex>\Psi=\int_{a}^{b}{f(x)dx}-\sum_{i=1}^N{f(x_{i-1/2})h}</tex></p>
 +
 
 +
равна сумме погрешностей по всем частичным отрезкам,
 +
 
 +
<p align="center"><tex>\Psi=\sum_{i=1}^N{\psi_i}=\sum_{i=1}^N{\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}}</tex></p>
 +
 
 +
Отсюда, обозначая <tex>M_2=\underset{x\in [a,b]}{max}|f''(x)|</tex>, получим
 +
 
 +
{{ eqno | 9 }}
 +
<p align="center"><tex>|\Psi|\le\frac{M_2Nh^3}{24}=\frac{h^2(b-a)}{24}M_2</tex></p>
 +
 
 +
т.е. погрешность формулы прямоугольников на всем отрезке есть велицина <tex>O(h^2)</tex>.
 +
 
 +
В этом случае говорят, что квадратурная формула имеет ''второй порядок точнотси''.
== Изложение метода ==
== Изложение метода ==

Версия 16:55, 5 октября 2008

Содержание

Введение

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

Задача численного интегрирования состоит в нахождении приближенного значения интеграла

( 1 )

J[f]=\int_a^b{f(x)dx},

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

( 2 )

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

где 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) в виде суммы интегралов по частичным отрезкам:

( 3 )

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

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

( 4 )

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

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

Формула прямоугольников

Заменим интеграл (3) выражением f(x_{i-1/2})h, где x_{i-1/2}=x_{i}-0.5h.

Геометрически такая замена означает, что площадь криволинейной трапеции ABCD заменяется площадью прямоугольника ABC'D' (см. рис. 1). Тогда получим формулу

( 5 )

\int_{x_{i-1}}^{x_i}{f(x)dx}\approx f(x_{i-1/2})h,

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

Погрешность метода (5) определяется величиной

\psi_{i}=\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h

которую легко оценить с помощью формулы Тейлора. Действительно, запишем \psi_{i} в виде

( 6 )

\psi_{i}=\int_{x_{i-1}}^{x_i}{(f(x)-f(x_{i-1/2}))dx}

и воспользуемся разложением

f(x)=f(x_{i-1/2})+(x-x_{i-1/2})f'(x_{i-1/2})+\frac{(x-x_{i-1/2})^2}{2}f''(\xi),

где \xi_i=\xi_i(x)\in [x_{i-1},x_i]. Тогда из (6) получим

\psi_{i}=\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}

Обозначая M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|, оценим \xi_i следующим образом:

|\xi_i|\le M_{2,i} \int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}dx}=\frac{h^3}{24}M_{2,i}

Таким образом, для погрешности формулы прямоугольников на частичном отрезке справедлива оценка

( 7 )

|\xi_i|\le \frac{h^3}{24}M_{2,i}

т.е. формула имеет погрешность O(h^3) при h\rightarrow0.

Заметим,что оценка (7) является неулучшаемой, т.е. существует функция f(x), для которой (7) выполняется со знаком равенства. Действительно, для f(x)=(x-x_{i-1/2})^2 имеем M_{2,i}=2, f(x_{i-1/2})=0 и

\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h=\frac{h^3}{24}M_{2,i}

Суммируя равенства (5) по i от 1 до N, получим составную формулу прямоугольников

( 8 )

\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{f(x_{i-1/2})h}

Погрешность этой формулы

\Psi=\int_{a}^{b}{f(x)dx}-\sum_{i=1}^N{f(x_{i-1/2})h}

равна сумме погрешностей по всем частичным отрезкам,

\Psi=\sum_{i=1}^N{\psi_i}=\sum_{i=1}^N{\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}}

Отсюда, обозначая M_2=\underset{x\in [a,b]}{max}|f''(x)|, получим

( 9 )

|\Psi|\le\frac{M_2Nh^3}{24}=\frac{h^2(b-a)}{24}M_2

т.е. погрешность формулы прямоугольников на всем отрезке есть велицина O(h^2).

В этом случае говорят, что квадратурная формула имеет второй порядок точнотси.

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

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

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

Заключение

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BF%D1%80%D1%8F%D0%BC%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_%D0%B8_%D1%82%D1%80%D0%B0%D0%BF%D0%B5%D1%86%D0%B8%D0%B9»
Личные инструменты