- •Математическое моделирование и вычислительный эксперимент.
- •Виды погрешностей.
- •2. Приближенное решение нелинейных уравнений
- •3.Численное решение систем нелинейных уравнений.
- •4.Численные методы решения систем линейных алгебраических уравнений (слау).
- •5. Численное интегрирование. Квадратурные формулы Ньютона–Котеса. Формула трапеций, формула Симпсона. Погрешность квадратурных формул. Интегрирование с помощью степенных рядов. Метод Монте-Карло.
- •6. Численное дифференцирование.
- •7. Интерполирование функций.
- •8. Численное решение задачи Коши для дифференциальных уравнений.
- •9. Краевые задачи для обыкновенных дифференциальных уравнений.
- •13. Комбинаторные объекты и комбинаторные числа
- •14. Рекуррентные соотношения
- •15. Булевы функции. Представление булевых функций полиномами Жегалкина.
- •17. Множества.
- •Операции над множествами
- •Свойства отношений
- •Примеры отношений эквивалентности
- •18. Графы.
- •Эйлеровы графы.
- •5 Красок
- •19. Алгоритмы на графах. Алгоритмы на графах.
- •Задача о кратчайших путях
- •Различные алгоритмы на графах
- •Перебор с возвратами
- •Методы сокращения перебора: эвристики, метод ветвей и границ, динамическое программирование.
- •20. Деревья.
- •21. Проблема разрешимости в алгебре высказываний.
- •24. Понятие о компьютерном математическом моделировании. Этапы и цели. Классификация математических моделей. Моделирование физических процессов.
- •25. Имитационное моделирование.
- •26. Моделирование фрактальных объектов. Моделирование фрактальных объектов.
- •Самоподобные множества с необычными свойствами в математике
- •Рекурсивная процедура получения фрактальных кривых
- •Фракталы как неподвижные точки сжимающих отображений
- •Фракталы в комплексной динамике
- •Стохастические фракталы
- •Применение фракталов
- •Конструктивные, алгебраические и стохастические фракталы.
- •Понятие о фрактальной размерности.
- •Рекурсивный алгоритм построения конструктивных фракталов.
- •Построение
- •Свойства
5. Численное интегрирование. Квадратурные формулы Ньютона–Котеса. Формула трапеций, формула Симпсона. Погрешность квадратурных формул. Интегрирование с помощью степенных рядов. Метод Монте-Карло.
Квадратурные формулы Ньютона - Котеса
В тех случаях, когда для вычисления определённого интеграла по каким-либо причинам не представляется возможным использовать формулу Ньютона - Лейбница, применяют численные методы вычисления интеграла. Многие из них основаны на том, что на отрезке [a, b] функцию f(x) заменяют интерполирующей функцией.
Разобьём отрезок интерполирования [a, b] на п частей. Получим точку, где . Заменим функцию f(x) на отрезке [a; b] интерполяционным многочленом Лагранжа для равноотстоящих узлов. Обозначим значения функции в узлах интерполяции: .
,
где .
Положим:
Сделаем замену: ,.
При имеем t = 0, а при имеем t = n. Получаем:
(6.1)
где (6.2)
Формула (6.1) называется квадратурной формулой Ньютона - Котеса, а (6.2) называются коэффициентами Котеса.
Формула трапеций
При из формулы (6.1), (6.2) получаем:
(6.3)
Формула (6.3) даёт один из простейших способов вычисления определённого интеграла и называется формулой трапеций. Распространяя формулу (6.3) на все отрезки разбиения, получим общую формулу трапеций на отрезке [a; b]:
(6.4)
Оценка погрешности метода трапеции:
, где (6.5)
Формула Симпсона
При из формул (6.1), (6.2) имеем:.
Получаем на отрезке :
(6.6)
Если , то применяя формулу (6.6) к каждой паре частичных отрезков(i = 1, 2, …m) получим:
Формула (6.7) называется формулой Симпсона.
Оценка погрешности формулы Симпсона:
, где .
Иногда удобно использовать следующую оценку: , где – значения интеграла, вычисленные по формуле Симпсона соответственно при п и 2п отрезках разбиения.
Вычисление интегралов методом Монте - Карло
В практических приложениях часто приходится вычислять значения кратных интегралов. Кратный интеграл вычисляется для функции многих переменных по замкнутой ограниченной многомерной области. Вычислительная схема имеет вид: интервал, соответствующий изменению каждой переменной внутри области интегрирования, разбивается на фиксированное число отрезков. Таким образом, задается разбиение области интегрирования на определенное число элементарных многомерных объемов. Вычисляются значения подынтегральной функции для точек, взятых по одной внутри каждого элементарного объема, и полученные значения суммируются. При увеличении кратности интеграла число слагаемых очень быстро возрастает. Пусть, например, мы разбиваем интервал изменения каждой переменной на десять частей. Для вычисления 10-кратного интеграла потребуется сумма, количество слагаемых в которой определяется числом 1010. Вычисление такой суммы затруднительно даже на самых быстродействующих современных ЭВМ. В таких ситуациях предпочтительнее использовать для получения значения интеграла метод Монте - Карло. В основе оценки искомого значения интеграла I лежит известное соотношение: где –
значение подынтегральной функции в некоторой «средней» точке области интегрирования, а – (многомерный) объем области интегрирования. При этом предполагается, что подынтегральная функция
(обозначим ее ) непрерывна в области интегрирования. Выберем в этой области n случайных точек Mi. При достаточно большом n приближенно можно считать:
(6.8)
Точность оценки значения интеграла методом Монте-Карло пропорциональна корню квадратному из числа случайных испытаний и не зависит от кратности интеграла. Именно поэтому применение метода целесообразно для вычисления интегралов высокой кратности. Рассмотрим применение метода для простейшего случая интеграла: .
В этой ситуации и равенство (6.8) принимает вид:, где– случайные точки, лежащие в интервале [a;b]. Для получения таких точек на основе последовательности случайных точек , равномерно распределенных в интервале [0; 1], достаточно выполнить преобразование: .