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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Числовой пример)
(Формула трапеций)
Строка 135: Строка 135:
Погрешность этой формулы оценивается следующим образом:
Погрешность этой формулы оценивается следующим образом:
 +
{{ eqno | 13 }}
<p align="center"><tex>|\Psi|\le \frac{h^2(b-a)}{12}M_2,M_2=\underset{x\in [a,b]}{max}|f''(x)|</tex></p>
<p align="center"><tex>|\Psi|\le \frac{h^2(b-a)}{12}M_2,M_2=\underset{x\in [a,b]}{max}|f''(x)|</tex></p>

Версия 11:35, 6 октября 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).

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

Формула трапеций

На частичном отрезке эта формула имеет вид

( 10 )

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

и получается путем замены подынтегральной функции f(x) интерполяционным многочленом первой степени,постоенным по узлам x_{i-1},x_i, т.е. функцией

L_{1,i}(x)=\frac{1}{h}((x-x_{i-1})f(x_i)-(x-x_i)f(x_{i-1})).

Для оценки погрешности достаточно вспомнить,что

f(x)-L_{1,i}(x)=\frac{(x-x_{i-1})(x-x_i)}{2}f''(\xi_i(x)).

Отсюда получим

\psi_i=\int_{x_{i-1}}^{x_i}{f(x)dx}-\frac{f(x_{i-1})+f(x_i)}{2}h=\int_{x_{i-1}}^{x_i}{(f(x)-L_{1,i}(x))dx}=\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1})(x-x_i)}{2}f''(\xi_i(x))dx}

и,следовательно,

( 11 )

|\psi_i|\le \frac{M_{2,i}h^3}{12}

Оценка (11) неулучшаема, так как в ней достигается равенство, например, для f(x)=(x-x_i)^2.

Составная формула трапеций имеет вид

( 12 )

\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{\frac{f(x_{i-1})+f(x_i)}{2}h}=h(0.5f_0+f_1+...+f_{N-1}+0.5f_N),

где f_i=f(x_i),i=0,1,...,N,hN=b-a.

Погрешность этой формулы оценивается следующим образом:

( 13 )

|\Psi|\le \frac{h^2(b-a)}{12}M_2,M_2=\underset{x\in [a,b]}{max}|f''(x)|

Таким образом, формула трапеций имеет, так же как и формула прямоугольников, второй порядок точности,\Psi=O(h^2), но ее погрешность оценивается величиной в два раза большей.

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

Вычислим по формулам прямоугольников и трапеций при n=2 интеграл

( 12 )

I=\int_{0}^{\pi/2}{\sin(x)dx} = 1

В данном случае


P_2=\frac{\pi}{4}(\sin(\frac{\pi}{8})+\sin(\frac{3\pi}{8}))=1.026172

T_2=\frac{\pi}{4}(\frac{1}{2}\sin(0)+\sin(\frac{\pi}{4})+\frac{1}{2}\sin(\frac{\pi}{2}))=0.948059

Зная точный ответ (12), найдем погрешности

( 13 )

\alpha_2=-0.026172,\beta_2=0.051941

Вторая производная функции \sin(x) на отрезке [0,\pi/2] отрицательна, ее модуль не превышает единицы: M_2=1. Величина погрешностей (13) удовлетворяет неравенствам (43) и (44):

|\alpha_2|\le \frac{1}{96}(\frac{\pi}{2})^3<0.041,|\beta_2|\le \frac{1}{48}(\frac{\pi}{2})^3<0.081

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

Заключение

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

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