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

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

(Различия между версиями)

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

Версия 13:53, 20 октября 2008

Содержание

1 Введение
- 1.1 Постановка математической задачи
2 Изложение метода
- 2.1 Общие сведения
- 2.2 Метод Рунге
3 Числовой пример
4 Рекомендации программисту
5 Заключение
6 Список литературы

Введение

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

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

( 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}$ .

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

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

$\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}$ .

Заключение

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

А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
Fundamental Methods of Numerical Extrapolation With Applications, mit.edu

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://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»

Категория: Незавершённые статьи

@@ Строка 87: / Строка 87: @@
 </table>
 <tex>\line(1,0){200}</tex>
-=== О сходимости ===
+=== Метод Рунге ===
+Пусть существует асимптотическое разложение вида:
+<tex>D_N(f) = I_N(f) - I_0 = \alpha _2 h^2 + \alpha _4 h^4 + \alpha _6 h^6 + \ldots</tex>,
+где <tex>f(x)</tex> - достаточно гладкая функция, а <tex>hN = b - a</tex>.
+Проведем расчеты на двух равномерных сетках с шагами <tex>h_1</tex> и <tex>h_2</tex> соответственно и найдем выражения
+<tex>I^{h_1}[f] = I_{N_1}[f]</tex> и <tex>I^{h_2}[f] = I_{N_2}[f]</tex>, <tex>h_1 N_1 = h_2 N_2 = b - a</tex>. Потребуем,
+чтобы погрешность для их линейной комбинации:
+:<tex>{\tilde D}^{h}(f) = \sigma D^{h_1}(f) + (1 - \sigma)D^{h_2}(f)</tex>
+была величиной более высокого порядка по сравнению с <tex>D^{h_1}</tex> и <tex>D^{h_2}</tex>. Если для <tex>D^h = D_N</tex> имеет место формула вида
+:<tex> D^{h} = I^{h}[f] - I[f] = \alpha _p h^p + \alpha _q h^q + \ldots,</tex>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>q > p</tex>,
+то для
+:<tex>{\tilde D}^{h} = (\sigma I^{h_1}[f] + (1 - \sigma)I^{h_2}[f]) - I[f]</tex>
+получим
+:<tex>{\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</tex>
+Выберем параметр \sigma из условия <tex>\sigma h_1^{p} + (1 - \sigma)h_2^{p}</tex>:
+:<tex>\sigma = \frac{h_2^p}{h_2^p - h_1^p}</tex>.
+Имеем
+:<tex>{\tilde D}^h(f) = \alpha _q(\sigma h_1^q + (1 - \sigma)h_2^q) + \ldots = O(h^q)</tex>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tex>h = max(h_1, h_2)</tex>,
+причем <tex>\sigma h_1^q + (1 - \sigma)h^q_2 < 0</tex>. Так, если <tex>p = 2, q = 4</tex>, то
+<tex>{\tilde D}^{h}(f) = - \alpha _4 h_1^2 h_2^2 + \ldots = O(h^4)</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>.
 == Числовой пример ==

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

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

Версия 13:53, 20 октября 2008

Содержание

Введение

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

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

Общие сведения

Метод Рунге

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

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

Заключение

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

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты