Участник:Gukov/Песочница
Материал из MachineLearning.
(→Общие сведения) |
(→Изложение метода) |
||
Строка 126: | Строка 126: | ||
с шагами <tex>h_1</tex> и <tex>h_2 \ne h_1</tex>, мы повысили порядок точности на <tex>2</tex> (на <tex>(q - p)</tex>) для | с шагами <tex>h_1</tex> и <tex>h_2 \ne h_1</tex>, мы повысили порядок точности на <tex>2</tex> (на <tex>(q - p)</tex>) для | ||
<tex>{\tilde I} = \sigma I^{h_1} + (1 - \sigma)I^{h_2}</tex>. | <tex>{\tilde I} = \sigma I^{h_1} + (1 - \sigma)I^{h_2}</tex>. | ||
+ | |||
+ | === Процесс Эйткена === | ||
+ | |||
+ | Метод расчета на нескольких сетках применяется для повышения порядка точности даже в том случае, когда неизвестен порядок главного члена погрешности. Предположим, чт для погрешности имеет место представление | ||
+ | |||
+ | :<tex>D^{h}(f) = \alpha _p h^{p} + \alpha _q h^{q} + \ldots</tex>, <tex>q > p</tex>, | ||
+ | |||
+ | так что | ||
+ | |||
+ | :<tex>I^{h}[f] = I[f] + \alpha _p h^p + \alpha _q h^{q} + \ldots</tex> | ||
+ | |||
+ | Проведем вычисления на трех сетках: <tex>h_1 = h</tex>, <tex>h_2 = \rho h</tex>, <tex>h_3 = \rho^{2} h</tex> (<tex>0 < \rho < 1</tex>). Определим <tex>p</tex>. При этом пренебрегаем членом <tex>O(h^q)</tex>. Образуем отношение | ||
+ | |||
+ | :<tex>A = \frac{I^{h_1}[f] - I^{h_2}[f]}{I^{h_2}[f] - I^{h_3}[f]} \approx \frac{h^p_1 - h^p_2}{h^p_2 - h^p_3} = \frac{1 - \rho^p}{\rho^p(1-\rho^p)} = (\frac{1}{\rho})^p</tex> | ||
+ | |||
+ | и найдем | ||
+ | |||
+ | :<tex>p \approx \frac{\ln A}{\ln(\frac{1}{\rho})}</tex>. | ||
+ | |||
+ | Зная приближенное значение <tex>p</tex>, можно методом методом Рунге повысить порядок точности. Для этого образуем комбинацию | ||
+ | <tex>{\tilde I}^h = \sigma I^{h_1} + (1 - \sigma)I^{h_2}</tex> и выберем <tex>\sigma</tex> так, чтобы <tex> \sigma h_1^p+(1 - \sigma)h_2^p = (\sigma + (1 - \sigma)\rho^p)h^p = 0 </tex>, то есть <tex>\sigma = \frac{\rho^p}{\rho^p - 1} = \frac{1}{1 - A}</tex>. | ||
+ | Тогда для погрешности <tex>{\tilde D}^h = {\tilde I}^h - I</tex> получаем | ||
+ | |||
+ | :<tex> {\tilde D}^h(f) = O(h^q) </tex>. | ||
== Числовой пример == | == Числовой пример == |
Версия 15:18, 20 октября 2008
Содержание |
Введение
Постановка математической задачи
Задача численного интегрирования состоит в приближенном нахождении значения интеграла
где
- заданная и интегрируемая на
функция. В качестве приближенного значения рассматривается число
где - числовые коэффициенты и
- точки отрезка
,
.
Приближенное равенство
называется квадратурной формулой, а сумма вида (2) - квадартурной суммой. Точки называются узлами квадратурной формулы.
Разность
называется погрешностью квадратурной формулы. Погрешность зависит как от расположения узлов, так и от выбора коэффициентов.
Изложение метода
Экстраполяция Ричардсона
Предположим, что для вычисления интеграла (1) отрезок разбит на
равных отрезков длины
и на каждом частичном отрезке применяется одна и та жа квадратурная формула. Тогда исходный интеграл
заменяется некоторой квадратурной суммой
, причем возникающая погрешность зависит от шага сетки
.
Для некоторых квадратурных формул удается получить разложение погрешности
по степеням
. Предположим,
что для данной квадратурной суммы
существует разложение:
,
где и коэффициенты
не зависят от
.
При этом величины
предполагаются известными.
Теперь предположим:
Чтобы избавиться от степени , составляющей ошибку (ибо среди всех слагаемых, составляющих ошибку, слагамое при
является наибольшим) вычислим величину
. Имеем:
Отсюда
то есть имеем более точное приближение к интегралу .
Таким образом, рекуррентную формулу можно записать в виде:
Заметим, что - величина, на которую мы делим размер шага при каждом новом вычислении
. Разумно положить
, т.к. большие значения
могут вызвать резкое увеличение количества вычислений.
Для наглядности представим процесс экстраполирования следующей таблицей:
Метод Рунге
Пусть существует асимптотическое разложение вида:
,
где - достаточно гладкая функция, а
.
Проведем расчеты на двух равномерных сетках с шагами и
соответственно и найдем выражения
и
,
. Потребуем,
чтобы погрешность для их линейной комбинации:
была величиной более высокого порядка по сравнению с и
. Если для
имеет место формула вида
,
то для
получим
Выберем параметр \sigma из условия :
.
Имеем
,
,
причем . Так, если
, то
. Таким образом, проведя вычисления на двух сетках
с шагами
и
, мы повысили порядок точности на
(на
) для
.
Процесс Эйткена
Метод расчета на нескольких сетках применяется для повышения порядка точности даже в том случае, когда неизвестен порядок главного члена погрешности. Предположим, чт для погрешности имеет место представление
,
,
так что
Проведем вычисления на трех сетках: ,
,
(
). Определим
. При этом пренебрегаем членом
. Образуем отношение
и найдем
.
Зная приближенное значение , можно методом методом Рунге повысить порядок точности. Для этого образуем комбинацию
и выберем
так, чтобы
, то есть
.
Тогда для погрешности
получаем
.
Числовой пример
Найдем с помощью квадратурной формулы трапеций приближенное значение интеграла, применив экстраполяцию Ричардсона (данный метод называется методом Ромберга):
В нижеследующей таблице представлены результаты работы программы:
r | Исходная формула | Экстраполированная формула | Точное значение | Погрешность вычислений | Погрешность формулы |
---|---|---|---|---|---|
2 | 3.98277278 | 4.04665506 | 4.04718956 | 0.0005345 | 0.00275556 |
4 | 4.03068449 | 4.04714980 | 4.04718956 | 0.00003976 | 0.00017222 |
8 | 4.04303347 | 4.04718692 | 4.04718956 | 0.00000264 | 0.00001076 |
16 | 4.04614856 | 4.04718939 | 4.04718956 | 0.00000017 | 0.00000067 |
32 | 4.04692918 | 4.04718955 | 4.04718956 | 0.00000001 | 0.00000004 |
64 | 4.04712446 | 4.04718956 | 4.04718956 | 0 | 0 |
20384 | 4.04718956 |
Здесь - коэффициент измельчения шага
. Исходная величина шага
.
На иллюстрации черная сплошная линия - исходная формула, красная пунктирная - экстраполированная.
Как мы видим, разница между экстраполированными и неэкстраполированными результатами значительна. Уже при величине шага в мы можем найти значение интеграла с точностью
, тогда как в исходной формуле нам для достижения такой точности пришлось бы задать величину шага
.
Рекомендации программисту
Заключение
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- Fundamental Methods of Numerical Extrapolation With Applications, mit.edu