Правило Рунге практической оценки погрешности

Метод Монте-Карло (метод статистических испытаний)

Всякий интеграл можетбыть сведен линейной заменой масштабов к интегралу вида , где 0≤f(x)≤1.

Из теории вероятностей:

1)случайная величина ξ равномерно распределена на [0;1], если . В частности .

2)двумерная случайная величина (ξ ,η) равномерно распределена на [0;1]×[0;1], если . При этом если ξ ,η равномерно распределены на [0;1], то (ξ ,η) равномерно распределена на [0;1]×[0;1].

Таким образом, для вычисления интеграла (т.е. для вычисления заштрихованной области) достаточно определить вероятность того, что точка (x,y) попадет в эту площадь (область, где (x,y) – равномерно распределенная случайная величина).

В ЭВМ существует датчик псевдослучайных чисел, значениями которого являются случайные числа, равномерно распределенные на [0;1].

Алгоритм:

1)генерируются равномерно распределенные на [0;1] случайные числа ξ_k , η_k

2)вычисляется f(ξ_k)

3)сравнивается f(ξ_k) и η_k и подсчитывается число N неравенств f(ξ_k) > η_k, k=1..M.

При достаточно большом числе испытаний M>>1 .

Ответ, полученный с помощью данного метода носит вероятностный характер и может сколь угодно сильно отличаться от точного значения интеграла. Однако с вероятностью 99,7% ошибка не превосходит (- дисперсия от среднеарифметического). При реальных испытаниях ошибка обычно не превосходит. С увеличением числа испытаний погрешность ответа будет убывать римерно как .

Величины погрешности численного интегрирования зависит как от шага h, так и от гладкости подинтегральной функции. Если величина погрешности велика, то ее можно уменьшить путем измельчения сетки на данном отрезке [x_k-1;x_k]. Для этого необходимо уметь апостериорно (т.е. после проведения расчета) оценивать погрешность. Правило Рунге позволяет произвести такую оценку.

Представим интеграл в виде приближенной формулы:

Заметим, что S и R зависят от шага h, т.е. от числа точек разбиения n. Тогда S=S_n, R=R_n.

Будем считать, что дана априорная погрешность (предполагаемая):

Если С известно, то можно заранее для нужной точности указать число точек разбиения и т.п.

Если же С неизвестно, то используют правило Рунге:

1.Производят 2 вычисления приближенного значения интеграла при n=n₁ и n=n₂ (обычно n₂=2n₁).

2.Таким образом, будет получено:

I=S_n1+R_n1; I=S_n2+R_n2

Вычитая из первого равенства второе, получим:

Отсюда, .

Подставим C в R_n1 и R_n2:

При этом выражение .

Таким образом, , т.к. невелико (обычно , а=2).

Это и есть правило Рунге:

В выбранной квадратурной формуле берется некоторое число точек разбиения n₁ и вычисляетя соответствующее ему значение интеграла.

Затем вычисляется приближенное значение, соответствующее числу точек разбиения n₂>n₁. Если модуль разности между ними не превышает требуемой точности, то вычисления останавливаются. В противном случае, процедуру необходимо повторить.

В качестве ответа обычно берут S_n2 или линейную комбинацию S_n1, S_n2.