- •1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод хорд
- •9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод Ньютона
- •10. Численное решение уравнения модифицированным методом Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Модифицированный метод Ньютона
- •Модифицированный метод Ньютона (метод секущих)
- •Метод ньютона-рафсона
- •11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Условие сходимости
- •12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод простых итераций
- •13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод прямоугольников
- •Пример реализации
- •14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод трапеций
- •15. Численное интегрирование методом парабол. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Формула
- •Представление в виде метода Рунге-Кутта
- •Составная формула (формула Котеса)
- •16. Численное интегрирование методом Гаусса-Лежандра. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •17. Численное интегрирование методом Монте-Карло. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Интегрирование методом Монте-Карло
- •Обычный алгоритм Монте-Карло интегрирования
- •Геометрический алгоритм Монте-Карло интегрирования
- •Использование выборки по значимости
- •Оптимизация Применение в физике
- •18. Построение кривой по точкам. Интерполяционный полином Лагранжа. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Определение
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •Погрешность интерполирования
- •Выбор узлов интерполяции
- •20. Построение кривой по точкам. Интерполяция кубическими сплайнами. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Интерполяция кубическими сплайнами
- •Введение
- •Постановка математической задачи
- •Изложение метода
- •Метод прогонки
- •Пример: интерполирование неизвестной функции
- •Ошибка интерполяции
- •Пример: интерполяция синуса
- •Дискретное преобразование Фурье
- •Пример использования
- •Погрешность вычислений
- •Программная реализация
15. Численное интегрирование методом парабол. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Метод Симпсона
В методе Симпсона в каждой части деления подынтегральная функция аппроксимируется квадратичной параболой a0x2+a1x+a2. В результате вся кривая подынтегральной функции на участке [a,b] заменяется кусочно-непрерывной линией, состоящей из отрезков квадратичных парабол. Приближенное значение интеграла I равно сумме площадей под квадратичными параболами.
Т.к. для построения квадратичной параболы необходимо иметь три точки, то каждая часть деления в методе Симпсона включает два шага, т.е.
Lk=2h.
В результате количество частей деления N2=n/2. Тогда n в методе Симпсона всегда четное число.
Определим площадь S1 на участке [x0, x2] (рис.12.2).
Исходя из геометрического смысла определенного интеграла, площадь S1 равна определенному интегралу от квадратичной параболы на участке [x0, x2]:
Неизвестные коэффициенты квадратичной параболы а0 , а1, а2 определяем из условия прохождения параболой через три узловых точки с координатами (x0y0), (x1y1), (x2y2).
На основании этого условия строим систему линейных уравнений:
Решая эту систему, найдем коэффициенты параболы.
В результате имеем: ..
Для участка [x2, x4]: ..
:::::::::::::::::::
Для участка [xi-1, xi+1]: .,
где .
Суммируя все площади S1 под квадратичными параболами, получим квадратурную формулу по методу Симпсона:
где
N2 - количество частей деления.
Точность метода Симпсона имеет порядок (h3/h4).
Схема алгоритма метода Симпсона представлена на рис.12.7.
Рис. 12.7. Схема алгоритма Симпсона (с автоматическим выбором шага)
Формула Симпсона (также Ньютона-Симпсона[1]) относится к приёмам численного интегрирования. Получила название в честь британского математика Томаса Симпсона (1710—1761).
Суть приёма заключается в приближении подынтегральной функции на отрезке интерполяционным многочленом второй степени , то есть приближение графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности 4 и алгебраический порядок точности4.
Формула
Формулой Симпсона называется интеграл от интерполяционного многочлена второй степени на отрезке :
где , и — значения функции в соответствующих точках (на концах отрезка и в его середине)
Погрешность
При условии, что у функции на отрезке существует четвёртая производная, погрешность , согласно найденной Джузеппе Пеано формуле равна:
В связи с тем, что значение зачастую неизвестно, для оценки погрешности используется следующее неравенство:
Представление в виде метода Рунге-Кутта
Формулу Симпсона можно представить в виде таблицы метода Рунге-Кутты следующим образом:
Составная формула (формула Котеса)
Для более точного вычисления интеграла, интервал разбивают на отрезков одинаковой длины и применяют формулу Симпсона на каждом из них. Значение исходного интеграла является суммой результатов интегрирования на всех отрезках.
где — величина шага, а — узлы интегрирования, границы элементарных отрезков, на которых применяется формула Симпсона. Обычно для равномерной сетки данную формулу записывают в других обозначениях (отрезок разбит на узлов) в виде
Также формулу можно записать используя только известные значения функции, т.е. значения в узлах:
где означает что индекс меняется от единицы с шагом, равным двум. Следует обратить внимание на удвоение коэффициента перед суммой. Это связано с тем, что в данном случае роль промежуточных узлов играют исходные узлы интегрирования.
Общая погрешность при интегрировании по отрезку с шагом (при этом, в частности, , ) определяется по формуле[2]:
.
При невозможности оценить погрешность с помощью максимума четвёртой производной (например, на заданном отрезке она не существует, либо стремится к бесконечности), можно использовать более грубую оценку:
.