Участник:Gukov/Песочница

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

Перейти к: навигация, поиск

Содержание

[убрать]

Введение

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

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

( 1)
I = \int\limits_a^b f(x)\,dx,

где f(x) - заданная и интегрируемая на [a, b] функция. В качестве приближенного значения рассматривается число

( 2)
I_n=\sum_{i=0}^n c_k f(x_k),

где c_k - числовые коэффициенты и x_k - точки отрезка [a,b], k = 0, 1, \ldots, n . Приближенное равенство

\int\limits_a^b f(x)\,dx=\sum_{k=0}^n c_k f(x_k)

называется квадратурной формулой, а сумма вида (2) - квадартурной суммой. Точки x_i называются узлами квадратурной формулы. Разность

\Psi _n = \int\limits_a^b f(x)\,dx-\sum_{k=0}^n c_k f(x_k)

называется погрешностью квадратурной формулы. Погрешность зависит как от расположения узлов, так и от выбора коэффициентов.

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

Экстраполяция Ричардсона

Предположим, что для вычисления интеграла (1) отрезок [a, b] разбит на N равных отрезков длины h = \frac{b-a}N и на каждом частичном отрезке применяется одна и та жа квадратурная формула. Тогда исходный интеграл I заменяется некоторой квадратурной суммой I_h, причем возникающая погрешность зависит от шага сетки h. Для некоторых квадратурных формул удается получить разложение погрешности I_h - I по степеням h. Предположим, что для данной квадратурной суммы I_h существует разложение:

( 3)
I_h = I_0 + a_1 h^{\alpha _1} + a_2 h^{\alpha _2} + \ldots + a_m h^{\alpha _m} + O(h^{\alpha _{m+1}}),

где 0 < \alpha _1 < \alpha _2 < \ldots < \alpha _m < \alpha _{m+1} и коэффициенты \{ a_i \} \subset \mathbb{R} не зависят от h. При этом величины \{ \alpha _i \} \subset \mathbb{R} предполагаются известными. Теперь предположим:

I(\frac{h}{r}) = I_0 + a_1\,\frac{h^{\alpha _1}}{r^{\alpha 1}} + a_2\,\frac{h^{\alpha _2}}{r^{\alpha 2}} + \ldots

Чтобы избавиться от степени h^{\alpha _1}, составляющей ошибку (ибо среди всех слагаемых, составляющих ошибку, слагамое при h^{\alpha _1} является наибольшим) вычислим величину r^{\alpha _1}\,I(\frac{h}r) - I(h). Имеем:

r^{\alpha _1}\,I(\frac{h}{r}) - I(h) = r^{\alpha _1}\,I_0 - I_0 + \fbox{a_1 h^{\alpha _1} - a_1 h^{\alpha _1}} + a_2\,\frac{h^{\alpha _2}}{r^{\alpha _2 - \alpha _1}} - a_2 h^{\alpha _2} + \ldots

Отсюда

I_1(h) = \frac{r^{\alpha _1}I(\frac{h}r) - I(h)}{r^{\alpha _1} - 1} = I_0 + \underbrace{a_2\,\frac{r^{\alpha _1 - \alpha _2} - 1}{r^{\alpha _1} - 1}}_{a_2 '}\,h^{\alpha _2} + \ldots

то есть имеем более точное приближение к интегралу I.

Таким образом, рекуррентную формулу можно записать в виде:

( 4)
I_{i+1}(h) = I_i(\frac{h}r) + \frac{I_i(\frac{h}r) - I_i(h)}{r^{\alpha _1} - 1}

Заметим, что r - величина, на которую мы делим размер шага при каждом новом вычислении I. Разумно положить s = 2, т.к. большие значения s могут вызвать резкое увеличение количества вычислений.

Для наглядности представим процесс экстраполирования следующей таблицей:


\line(1, 0){200}

I_0^{0}(h)
I_0^{1}(\frac{h}r) I_1^{0}(h)
I_0^{2}(\frac{h}{r^2}) I_1^{1}(\frac{h}r) I_2^{0}(h)
\vdots \vdots \vdots \ddots

\line(1,0){200}

Метод Рунге

Пусть существует асимптотическое разложение вида:

D_N(f) = I_N(f) - I_0 = \alpha _2 h^2 + \alpha _4 h^4 + \alpha _6 h^6 + \ldots,

где f(x) - достаточно гладкая функция, а hN = b - a.

Проведем расчеты на двух равномерных сетках с шагами h_1 и h_2 соответственно и найдем выражения I^{h_1}[f] = I_{N_1}[f] и I^{h_2}[f] = I_{N_2}[f], h_1 N_1 = h_2 N_2 = b - a. Потребуем, чтобы погрешность для их линейной комбинации:

{\tilde D}^{h}(f) = \sigma D^{h_1}(f) + (1 - \sigma)D^{h_2}(f)

была величиной более высокого порядка по сравнению с D^{h_1} и D^{h_2}. Если для D^h = D_N имеет место формула вида

D^{h} = I^{h}[f] - I[f] = \alpha _p h^p + \alpha _q h^q + \ldots,     q > p,

то для

{\tilde D}^{h} = (\sigma I^{h_1}[f] + (1 - \sigma)I^{h_2}[f]) - I[f]

получим

{\tilde D}^{h}(f) = \alpha _p(\sigma h_1^{p} + (1 - \sigma)h_2^{p}) + \alpha _q (\sigma h_1^{q} + (1 - \sigma)h_2^{q}) + \ldots

Выберем параметр \sigma из условия \sigma h_1^{p} + (1 - \sigma)h_2^{p}:

\sigma = \frac{h_2^p}{h_2^p - h_1^p}.

Имеем

{\tilde D}^h(f) = \alpha _q(\sigma h_1^q + (1 - \sigma)h_2^q) + \ldots = O(h^q),       h = max(h_1, h_2),

причем \sigma h_1^q + (1 - \sigma)h^q_2 < 0. Так, если p = 2, q = 4, то {\tilde D}^{h}(f) = - \alpha _4 h_1^2 h_2^2 + \ldots = O(h^4). Таким образом, проведя вычисления на двух сетках с шагами h_1 и h_2 \ne h_1, мы повысили порядок точности на 2 (на (q - p)) для {\tilde I} = \sigma I^{h_1} + (1 - \sigma)I^{h_2}.

Процесс Эйткена

Метод расчета на нескольких сетках применяется для повышения порядка точности даже в том случае, когда неизвестен порядок главного члена погрешности. Предположим, чт для погрешности имеет место представление

D^{h}(f) = \alpha _p h^{p} + \alpha _q h^{q} + \ldots,     q > p,

так что

I^{h}[f] = I[f] + \alpha _p h^p + \alpha _q h^{q} + \ldots

Проведем вычисления на трех сетках: h_1 = h, h_2 = \rho h, h_3 = \rho^{2} h (0 < \rho < 1). Определим p. При этом пренебрегаем членом O(h^q). Образуем отношение

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

и найдем

p \approx \frac{\ln A}{\ln(\frac{1}{\rho})}.

Зная приближенное значение p, можно методом методом Рунге повысить порядок точности. Для этого образуем комбинацию {\tilde I}^h = \sigma I^{h_1} + (1 - \sigma)I^{h_2} и выберем \sigma так, чтобы \sigma h_1^p+(1 - \sigma)h_2^p = (\sigma + (1 - \sigma)\rho^p)h^p = 0 , то есть \sigma = \frac{\rho^p}{\rho^p - 1} = \frac{1}{1 - A}. Тогда для погрешности {\tilde D}^h = {\tilde I}^h - I получаем

{\tilde D}^h(f) = O(h^q) .

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

Найдем с помощью квадратурной формулы трапеций приближенное значение интеграла, применив экстраполяцию Ричардсона (данный метод называется методом Ромберга):

\int^{5}_{1} \ln x\, dx = x \ln x - x |_1^{5} = 5\ln 5 - 4

В нижеследующей таблице представлены результаты работы программы:

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

Здесь r - коэффициент измельчения шага h. Исходная величина шага h = 2.

На иллюстрации черная сплошная линия - исходная формула, красная пунктирная - экстраполированная.

Как мы видим, разница между экстраполированными и неэкстраполированными результатами значительна. Уже при величине шага в h = \frac{1}{64} мы можем найти значение интеграла с точностью 10^{-8}, тогда как в исходной формуле нам для достижения такой точности пришлось бы задать величину шага h = \frac{1}{10192}.

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

Программируя экстраполяцию Ричардсона следует предпочесть итерацию рекурсии. Также реализуя многократное экстраполирование итеративно, нам не нужно хранить всю таблицу значений - достаточно иметь в распоряжении два последних столбца.

Заключение

Мы получили более точные результаты при меньшем количестве вычислений функции, чем в исходном методе. Избавившись от степени, составляющей ошибку, мы пришли к результату, который в противном случае был бы недостижим без значительного уменьшения размера шага. Таким образом, мы преобразовали весьма посредственный алгоритм вычисления интегралов в довольно эффективный.

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

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gukov/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты