Методы прямоугольников и трапеций
Материал из MachineLearning.
(→Рекомендации программисту) |
|||
Строка 78: | Строка 78: | ||
т.е. формула имеет погрешность <tex>O(h^3)</tex> при <tex>h\rightarrow0</tex>. | т.е. формула имеет погрешность <tex>O(h^3)</tex> при <tex>h\rightarrow0</tex>. | ||
- | Заметим,что оценка | + | Заметим,что оценка {{eqref|7}} является неулучшаемой, т.е. существует функция <tex>f(x)</tex>, для которой {{eqref|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> | <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> | ||
- | Суммируя равенства | + | Суммируя равенства {{eqref|5}} по <tex>i</tex> от <tex>1</tex> до <tex>N</tex>, получим ''составную формулу прямоугольников'' |
{{ eqno | 8 }} | {{ eqno | 8 }} | ||
Строка 130: | Строка 130: | ||
<p align="center"><tex>|\psi_i|\le \frac{M_{2,i}h^3}{12}</tex></p> | <p align="center"><tex>|\psi_i|\le \frac{M_{2,i}h^3}{12}</tex></p> | ||
- | Оценка | + | Оценка {{eqref|11}} неулучшаема, так как в ней достигается равенство, например, для <tex>f(x)=(x-x_i)^2</tex>. |
''Составная формула трапеций'' имеет вид | ''Составная формула трапеций'' имеет вид | ||
Строка 159: | Строка 159: | ||
<p align="center"><tex>T_2=\frac{\pi}{4}(\frac{1}{2}\sin(0)+\sin(\frac{\pi}{4})+\frac{1}{2}\sin(\frac{\pi}{2}))=0.948059</tex></p> | <p align="center"><tex>T_2=\frac{\pi}{4}(\frac{1}{2}\sin(0)+\sin(\frac{\pi}{4})+\frac{1}{2}\sin(\frac{\pi}{2}))=0.948059</tex></p> | ||
- | Зная точный ответ | + | Зная точный ответ {{eqref|14}}, найдем погрешности |
{{ eqno | 15 }} | {{ eqno | 15 }} | ||
<p align="center"><tex>\alpha_2=-0.026172,\beta_2=0.051941</tex></p> | <p align="center"><tex>\alpha_2=-0.026172,\beta_2=0.051941</tex></p> | ||
- | Вторая производная функции <tex>\sin(x)</tex> на отрезке <tex>[0,\pi/2]</tex> отрицательна, ее модуль не превышает единицы: <tex>M_2=1</tex>. Величина погрешностей | + | Вторая производная функции <tex>\sin(x)</tex> на отрезке <tex>[0,\pi/2]</tex> отрицательна, ее модуль не превышает единицы: <tex>M_2=1</tex>. Величина погрешностей {{eqref|15}} удовлетворяет неравенствам {{eqref|9}} и {{eqref|13}}: |
<p align="center"><tex>|\alpha_2|\le \frac{1}{96}(\frac{\pi}{2})^3<0.041,|\beta_2|\le \frac{1}{48}(\frac{\pi}{2})^3<0.081</tex></p> | <p align="center"><tex>|\alpha_2|\le \frac{1}{96}(\frac{\pi}{2})^3<0.041,|\beta_2|\le \frac{1}{48}(\frac{\pi}{2})^3<0.081</tex></p> | ||
Строка 176: | Строка 176: | ||
=== Автоматический выбор шага интегрирования === | === Автоматический выбор шага интегрирования === | ||
- | Величина погрешности численного интегрирования зависит как от шага сетки <tex>h</tex>, так и от гладкости подынтегральной функции <tex>f(x)</tex>. Например, в оценку | + | Величина погрешности численного интегрирования зависит как от шага сетки <tex>h</tex>, так и от гладкости подынтегральной функции <tex>f(x)</tex>. Например, в оценку {{eqref|11}}, наряду с <tex>h</tex>, входит величина |
<p align="center"><tex>M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|,</tex></p> | <p align="center"><tex>M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|,</tex></p> | ||
Строка 194: | Строка 194: | ||
<p align="center"><tex>I_i-I_{h/2,i}\approx \frac{I_{h/2,i}-I_{h,i}}{2^m-1}</tex></p> | <p align="center"><tex>I_i-I_{h/2,i}\approx \frac{I_{h/2,i}-I_{h,i}}{2^m-1}</tex></p> | ||
- | Возможность апостериорно оценивать погрешность позволяет вычислять интеграл | + | Возможность апостериорно оценивать погрешность позволяет вычислять интеграл {{eqref|1}} с заданной точностью <tex>\epsilon >0</tex> путем автоматического выбора шага интегрирования <tex>h_i</tex>. Пусть используется составная квадратурная формула |
<p align="center"><tex>I\approx I_h=\sum_{i=1}^N{I_{h,i}}</tex></p> | <p align="center"><tex>I\approx I_h=\sum_{i=1}^N{I_{h,i}}</tex></p> | ||
- | где <tex>I_{h,i}</tex> - квадратурная сумма на частичном отрезке, причем на каждом частичном отрезке используется одна и та же квадратурная формула (например, формула трапеций). Проведем на каждом частичном отрезке <tex>[x_{i-1},x_i]</tex> все вычисления дважды, один раз - с шагом <tex>h_i</tex> и второй раз - с шагом <tex>0.5h_i</tex> и оценим погрешность по правилу Рунге | + | где <tex>I_{h,i}</tex> - квадратурная сумма на частичном отрезке, причем на каждом частичном отрезке используется одна и та же квадратурная формула (например, формула трапеций). Проведем на каждом частичном отрезке <tex>[x_{i-1},x_i]</tex> все вычисления дважды, один раз - с шагом <tex>h_i</tex> и второй раз - с шагом <tex>0.5h_i</tex> и оценим погрешность по правилу Рунге {{eqref|17}}. |
Если для заданного <tex>\epsilon >0</tex> будут выполняться неравенства | Если для заданного <tex>\epsilon >0</tex> будут выполняться неравенства | ||
Строка 211: | Строка 211: | ||
т.е. будет достигнута заданная точность <tex>\epsilon</tex>. | т.е. будет достигнута заданная точность <tex>\epsilon</tex>. | ||
- | Если же на каком-то из частичных отрезков оценка | + | Если же на каком-то из частичных отрезков оценка {{eqref|18}} не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида {{eqref|18}}. Заметим, что для некоторой функции <tex>f(x)</tex> такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений,а также вожможность увеличения <tex>\epsilon</tex>. |
Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции <tex>f(x)</tex> и с мелким шагом - на участках быстрого изменения <tex>f(x)</tex>. Это позволяет при заданной точности <tex>\epsilon</tex> уменьшить количество вычислений значений <tex>f(x)</tex> по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм <tex>I_{h/2,i}</tex> не надо пересчитывать значения <tex>f(x)</tex> во всех узлах, достаточно вычислять <tex>f(x)</tex> только в новых узлах. | Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции <tex>f(x)</tex> и с мелким шагом - на участках быстрого изменения <tex>f(x)</tex>. Это позволяет при заданной точности <tex>\epsilon</tex> уменьшить количество вычислений значений <tex>f(x)</tex> по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм <tex>I_{h/2,i}</tex> не надо пересчитывать значения <tex>f(x)</tex> во всех узлах, достаточно вычислять <tex>f(x)</tex> только в новых узлах. |
Версия 13:26, 19 октября 2008
Содержание |
Введение
Постановка математической задачи
Задача численного интегрирования состоит в нахождении приближенного значения интеграла
где - заданная и интегрируемая на отрезке функция. На отрезке вводится сетка и в качестве приближенного значения интеграла рассматривается число
где - значения функции в узлах , - весовые множители, зависящие только от узлов, но не зависящие от выбора . Формула (2) называется квадратурной формулой.
Задача численного интегрирования при помощи квадратур состоит в отыскании таких узлов и таких весов , чтобы погрешность квадратурной формулы
была минимальной по модулю для функции из заданного класса (величина зависит от гладкости ). Погрешность зависит как от расположения узлов, так и от выбора весовых коэффициентов.
Введем на равномерную сетку с шагом , т.е. множество точек , и представим интеграл (1) в виде суммы интегралов по частичным отрезкам:
Для построения формулы численного интегрирования на всем отрезке достаточно построить квадратурную формулу для интеграла
на частичном отрезке и воспользоваться свойством (3).
Изложение метода
Формула прямоугольников
Заменим интеграл (3) выражением , где
Тогда получим формулу
которая называется формулой прямоугольников на частичном отрезке
Погрешность метода (5) определяется величиной
которую легко оценить с помощью формулы Тейлора. Действительно, запишем в виде
и воспользуемся разложением
где . Тогда из (6) получим
Обозначая , оценим следующим образом:
Таким образом, для погрешности формулы прямоугольников на частичном отрезке справедлива оценка
т.е. формула имеет погрешность при .
Заметим,что оценка (7) является неулучшаемой, т.е. существует функция , для которой (7) выполняется со знаком равенства. Действительно, для имеем и
Суммируя равенства (5) по от до , получим составную формулу прямоугольников
Погрешность этой формулы
равна сумме погрешностей по всем частичным отрезкам,
Отсюда, обозначая , получим
т.е. погрешность формулы прямоугольников на всем отрезке есть велицина .
Видим, что квадратурная формула имеет второй порядок точности.
Формула трапеций
На частичном отрезке эта формула имеет вид
и получается путем замены подынтегральной функции интерполяционным многочленом первой степени,постоенным по узлам , т.е. функцией
Для оценки погрешности достаточно вспомнить,что
Отсюда получим
и,следовательно,
Оценка (11) неулучшаема, так как в ней достигается равенство, например, для .
Составная формула трапеций имеет вид
где .
Погрешность этой формулы оценивается следующим образом:
Таким образом, формула трапеций имеет, так же как и формула прямоугольников, второй порядок точности,, но ее погрешность оценивается величиной в два раза большей.
Числовой пример
Вычислим по формулам прямоугольников и трапеций при интеграл
В данном случае
Зная точный ответ (14), найдем погрешности
Вторая производная функции на отрезке отрицательна, ее модуль не превышает единицы: . Величина погрешностей (15) удовлетворяет неравенствам (9) и (13):
Рекомендации программисту
Пример программы на языке C++
Автоматический выбор шага интегрирования
Величина погрешности численного интегрирования зависит как от шага сетки , так и от гладкости подынтегральной функции . Например, в оценку (11), наряду с , входит величина
которая может сильно меняться от точки к точке и, вообще говоря, заранее неизвестна. Если величина погрешности велика, то ее можно уменьшить путем измельчения сетки на данном отрезке . Для этого прежде всего надо уметь апостериорно, т.е. после проведения расчета, оценивать погрешность.
Апостериорную оценку погрешности можно осуществить методом Рунге. Пусть какая-то квадратурная формула имеет на частичном отрезке порядок точности , т.е. . Тогда
откуда получим
Возможность апостериорно оценивать погрешность позволяет вычислять интеграл (1) с заданной точностью путем автоматического выбора шага интегрирования . Пусть используется составная квадратурная формула
где - квадратурная сумма на частичном отрезке, причем на каждом частичном отрезке используется одна и та же квадратурная формула (например, формула трапеций). Проведем на каждом частичном отрезке все вычисления дважды, один раз - с шагом и второй раз - с шагом и оценим погрешность по правилу Рунге (17).
Если для заданного будут выполняться неравенства
то получим
т.е. будет достигнута заданная точность .
Если же на каком-то из частичных отрезков оценка (18) не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида (18). Заметим, что для некоторой функции такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений,а также вожможность увеличения .
Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции и с мелким шагом - на участках быстрого изменения . Это позволяет при заданной точности уменьшить количество вычислений значений по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм не надо пересчитывать значения во всех узлах, достаточно вычислять только в новых узлах.
Заключение
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- А.А.Самарский. Введение в численные методы М.: Наука, 1982.