- •1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод хорд
- •9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод Ньютона
- •10. Численное решение уравнения модифицированным методом Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Модифицированный метод Ньютона
- •Модифицированный метод Ньютона (метод секущих)
- •Метод ньютона-рафсона
- •11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Условие сходимости
- •12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод простых итераций
- •13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод прямоугольников
- •Пример реализации
- •14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод трапеций
- •15. Численное интегрирование методом парабол. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Формула
- •Представление в виде метода Рунге-Кутта
- •Составная формула (формула Котеса)
- •16. Численное интегрирование методом Гаусса-Лежандра. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •17. Численное интегрирование методом Монте-Карло. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Интегрирование методом Монте-Карло
- •Обычный алгоритм Монте-Карло интегрирования
- •Геометрический алгоритм Монте-Карло интегрирования
- •Использование выборки по значимости
- •Оптимизация Применение в физике
- •18. Построение кривой по точкам. Интерполяционный полином Лагранжа. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Определение
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •Погрешность интерполирования
- •Выбор узлов интерполяции
- •20. Построение кривой по точкам. Интерполяция кубическими сплайнами. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Интерполяция кубическими сплайнами
- •Введение
- •Постановка математической задачи
- •Изложение метода
- •Метод прогонки
- •Пример: интерполирование неизвестной функции
- •Ошибка интерполяции
- •Пример: интерполяция синуса
- •Дискретное преобразование Фурье
- •Пример использования
- •Погрешность вычислений
- •Программная реализация
Метод хорд
Метод основан на замене функции f(x) на каждом шаге поиска хордой, пересечение которой с осью Х дает приближение корня.
При этом в процессе поиска семейство хорд может строиться:
а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х0=b (рис. 4.10а);
б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х0=a (рис. 4.10б);
Рис. 4.10.
В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:
для случая а)
|
(4.11) |
для случая б)
|
(4.12) |
Процесс поиска продолжается до тех пор, пока не выполнится условие
|
(4.13) |
Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце интервала [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.
Схема алгоритма уточнения корня методом хорд
Пример программы:
double f(double x)
{
return sqrt(fabs(cos(x))) - x; // Заменить ф-ей, корни которой мы ищем
}
// a, b - пределы хорды, epsilon - необходимая погрешность
double findRoot(double a, double b, double epsilon)
{
while(fabs(b - a) > epsilon)
{
a = b - (b - a) * f(b)/(f(b) - f(a));
b = a - (a - b) * f(a)/(f(a) - f(b));
}
// a - i-1, b - i-тый члены
return b;
}
9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Метод Ньютона (метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.
Суть:
Задан отрезок [а,b], содержащий корень уравнения F(x)=0. Уточнение значения корня производится путем использования уравнения касательной. В качестве начального приближения задается тот из концов отрезка [а,b], где значение функции и ее второй производной имеют одинаковые знаки (т.е. выполняется условиеF(x0)*F"(x0) > 0).
В точке F(x0) строится касательная к кривой у = F(x) и ищется ее пересечение с осью х. Точка пересечения принимается за новую итерацию. Метод Ньютона самый быстрый способ нахождения корней уравнений
Итерационная формула имеет вид:
Итерационный процесс проходит до того времени, пока не будет выполнено условие /F(X)/< e , где e - заданная точность.
Рис. 1. Иллюстрация метода Ньютона
Рис. 1. иллюстрирует работу метода Ньютона. В данном случае вторая производная функции положительна, поэтому в качестве начального приближения выбрана точка хо = b. Как видно из рисунка, метод имеет очень быструю сходимость среди всех методов решения нелинейных уравнений: обычно заданная точность достигается за 2-3 итерации.
Достоинство метода Ньютона: очень быстрая сходимость по сравнению с методом половинного деления и методом простой итерации к заданной точности. Недостаток: громоздкий алгоритм: на каждой итерации необходимо вычислять значение функции и ее первой производной.