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

Всякий интеграл можетбыть сведен линейной заменой масштабов к интегралу вида , где 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.

 

 

Глава4. Алгебраическая проблема собсвенных значений

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

Пусть A=(a_ik) – вещественная матрица порядка n×n пространства Rⁿ. Элементы пространства Rⁿ имеют вид: x=(x₁..x_n)^T.

Скалярное произведение векторов в Rⁿ: .

Норма вектора в пространстве Rⁿ: .

 

Число λ – собственное число матрицы А, если существует нетривиальный вектор x¹≠0: Ax=λx. При этом x¹ – собственный вектор А. (1)

Множество всех собственных чисел матрицы – её спектр.

 

Спектральная задача – задача нахождения всех или нескольких собственных чисел матрицы и, возможно, соответствующих им собственных векторов.

 

Пусть λ₁ – собственное число матрицы А. Перепишем уравнение (1) в виде:

.

 

Многочлен вида: - характеристический многочлен матрицы А.

Т.о. если λ – собственное число матрицы А, то λ – корень характеристического многочлена матрицы А. Верно и обратное.

 

Утверждение Любая матрица А порядка n×n имеет хотя бы один собственный вектор и имеет n собственных чисел (могут быть как различными, так и кратными).

 

Из сказанного: задача нахождения собственных чисел матрицы А сводится к задаче нахождения корней её характеристического многочлена, т.е. решения уравнения P_n(λ) = 0.