- •Глава1. Проблема аппроксимации
- •§1. Полиномиальная апппроксимация
- •§2. Интерполяционный полином в форме Лагранжа
- •§3. Интерполяционный полином в форме Ньютона
- •§4. Аппроксимация сплайнами
- •§5. Метод наименьших квадратов
- •§6. Полиномиальная интерполяция с кратными узлами
- •§7. Свойства разделенных разностей
- •§8. Задача Чебышева. Разрешимость системы
- •§9. Теорема Чебышева
- •§10. Многочлены Чебышева
- •Глава2. Численное дифференцирование
- •Глава3. Численное интегрирование
- •§1. Интерполяционные квадратурные формулы
- •1.Интерполяционные квадратурные формулы
- •2.Интерполяционные квадратурные формулы наилучшей алгебраической точности
- •3.Ортогональные многочлены и их свойства
- •§2. Применение квадратурных формул
- •§3. Метод Монте-Карло (метод статистических испытаний)
- •§4. Правило Рунге практической оценки погрешности
- •Глава4. Алгебраическая проблема собсвенных значений
- •§1. Ортогональные матрицы
- •1.Ортогональные матрицы
- •2.Матрица элементарного поворота
- •§2. Вариационное свойство собственных значений
- •§3. Приведение симметричной матрицы к диагональному виду
- •§4. Сингулярное разложение матрицы
- •§5. Сопряженная матрица
- •§6. Частная спектральная задача
- •1.Вариационный метод
- •2.Степенной метод
- •§7. Метод максимизации столбцов
- •1.Максимизация первого столбца
- •2.Алгоритм сингулярного разложения
- •3.Главное собственное число
- •§8. Метод вращения
§3. Метод Монте-Карло (метод статистических испытаний)
Всякий интеграл можетбыть сведен линейной заменой масштабов к интегралу вида , где 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% ошибка не превосходит ( - дисперсия от среднеарифметического). При реальных испытаниях ошибка обычно не превосходит . С увеличением числа испытаний погрешность ответа будет убывать римерно как .
§4. Правило Рунге практической оценки погрешности
Величины погрешности численного интегрирования зависит как от шага h, так и от гладкости подинтегральной функции. Если величина погрешности велика, то ее можно уменьшить путем измельчения сетки на данном отрезке [xk-1;xk]. Для этого необходимо уметь апостериорно (т.е. после проведения расчета) оценивать погрешность. Правило Рунге позволяет произвести такую оценку.
Представим интеграл в виде приближенной формулы:
Заметим, что S и R зависят от шага h, т.е. от числа точек разбиения n. Тогда S=Sn, R=Rn.
Будем считать, что дана априорная погрешность (предполагаемая):
Если С известно, то можно заранее для нужной точности указать число точек разбиения и т.п.
Если же С неизвестно, то используют правило Рунге:
1. Производят 2 вычисления приближенного значения интеграла при n=n1 и n=n2 (обычно n2=2n1).
2. Таким образом, будет получено:
I=Sn1+Rn1; I=Sn2+Rn2
Вычитая из первого равенства второе, получим:
Отсюда, .
Подставим C в Rn1 и Rn2:
При этом выражение .
Таким образом, , т.к. невелико (обычно , а=2).
Это и есть правило Рунге:
В выбранной квадратурной формуле берется некоторое число точек разбиения n1 и вычисляетя соответствующее ему значение интеграла.
Затем вычисляется приближенное значение, соответствующее числу точек разбиения n2>n1. Если модуль разности между ними не превышает требуемой точности, то вычисления останавливаются. В противном случае, процедуру необходимо повторить.
В качестве ответа обычно берут Sn2 или линейную комбинацию Sn1, Sn2.