- •Раздел 6.
- •Раздел 6. Модели и алгоритмы решения задач численными методами с использованием математических пакетов Рекомендации по использованию учебного пособия
- •Тема 6.1. Элементы теории погрешностей
- •6.1.1. Точные и приближенные числа
- •6.1.2. Абсолютная и относительная погрешность
- •Тема 6.2. Методы решения нелинейных уравнений
- •6.2.1. Постановка задачи
- •Отделение корней (локализация корней);
- •Итерационное уточнение корней.
- •6.2.2. Отделение корней
- •6.2.2.1. Графическое отделение корней
- •6.2.2.2. Аналитическое отделение корней
- •6.2.3. Уточнение корней
- •6.2.3.1. Метод половинного деления
- •6.2.3.2. Метод итерации
- •6.2.3.3. Метод Ньютона (метод касательных)
- •6.2.3.4. Метод хорд
- •6.2.3.5. Сравнение методов решения нелинейных уравнений
- •6.2.4. Технология решения нелинейных уравнений средствами MathCad
- •Тема 6.3. Интерполяция функций
- •6.3.1. Постановка задачи
- •6.3.2. Интерполяционная формула Лагранжа
- •6.3.3. Интерполяционные формулы Ньютона
- •6.3.3.1. Конечные разности
- •6.3.3.2. Первая интерполяционная формула Ньютона
- •6.3.3.3. Вторая интерполяционная формула Ньютона
- •6.3.4. Сплайн – интерполяция
- •6.3.5. Сравнение интерполяционных многочленов по применению
- •6.3.6. Технология интерполяции функций в среде математических пакетов
- •Тема 6.4. Численное интегрирование
- •6.4.1. Постановка задачи
- •6.4.2. Метод прямоугольников
- •6.4.3. Формула трапеций
- •6.4.4. Формула Симпсона
- •6.4.5. Оценка погрешности численного интегрирования
- •6.4.6. Технология вычисления интегралов в среде математических пакетов
- •Тема 6.5. Методы решения обыкновенных дифференциальных уравнений
- •6.5.1. Постановка задачи
- •6.5.2. Метод Эйлера
- •6.5.3. Методы Рунге-Кутты
- •6.5.4. Решение оду n-го порядка
- •6.5.5. Сравнение методов решения оду
- •6.5.6. Технология решения обыкновенных дифференциальных уравнений средствами математических пакетов
- •6.6.2. Метод дихотомии
- •6.6.3. Метод золотого сечения
- •6.6.4. Сравнение методов
- •6.6.5. Технология решения задач одномерной оптимизации средствами математических пакетов
- •Тема 6.7. Аппроксимация функций
- •6.7.1. Постановка задачи аппроксимации
- •6.7.2. Метод наименьших квадратов
- •6.7.3. Технология решения задач аппроксимации функций средствами математических пакетов
- •Тема 6.8. Многомерная оптимизация
- •6.8.1. Постановка задачи и основные определения
- •6.8.2. Методы спуска
- •6.8.3. Метод градиентного спуска с дроблением шага
- •6.8.4. Метод наискорейшего спуска
- •6.8.5. Проблема оврагов. Метод покоординатного спуска
- •6.8.6. Технология решения задач многомерной оптимизации средствами математических пакетов
- •Список литературы
- •Тема 6.4. Численное интегрирование................................................71
- •Тема 6.5. Методы решения обыкновенных дифференциальных Уравнений............................................................................. 92
- •Тема 6.6. Одномерная оптимизация................................................ 115
- •Тема 6.7. Аппроксимация функций....................................................132
- •Тема 6.8. Методы многомерной оптимизации............................... 149
- •Список литературы.................................................................... 204
6.6.2. Метод дихотомии
Пусть дана функция f(x), унимодальная на отрезке [a;b]. Обозначим a0 = a и b0 = b. Поиск минимума начинают с выбора на отрезке неопределенности [a0;b0] двух симметричных относительно середины точек:
где d - параметр метода.
Сравнивая вычисленные в точках a1 и b1 значения функций f(a1) и f(b1), в силу унимодальности функции можно провести сокращение отрезка неопределенности следующим образом:
1) если f(a1) £ f(b1), то x*Î[a0;b1] (Рис. 6.6.1-3.а);
2) если f(a1) > f(b1), то x*Î[a1;b0] (Рис. 6.6.1-3.b).
а) b)
Рис. 6.6.1-3
Если описанную процедуру принять за одну итерацию, то алгоритм поиска минимума можно описать следующим образом. Опишем k+1 итерацию, исходя из того, что k-й отрезок неопределенности найден [ak;bk]:
Вычисляются
Находят значения f(ak+1) и f(bk+1).
Находят k+1-й отрезок неопределенности по правилу:
если f(ak+1) > f(bk+1), то x* Î[ak+1;bk],
если f(ak+1) £ f(bk+1), то x*Î[ak;bk+1]).
Вычисления проводятся до тех пор, пока не выполнится неравенство
где Dn – длина n-го отрезка неопределенности.
Заметим, что от итерации к итерации Dn убывает и при n® стремится к величине 2d, оставаясь больше этой величины. Поэтому добиться при некотором значении n длины отрезка неопределенности меньше заданной точности можно лишь выбирая 0<d<e/2.
Длину конечного интервала неопределенности, обеспечивающего заданную величину e, можно вычислить по формуле
Положив Dn = e, можно определить соответствующее количество итераций:
Пример 6.6.2-1. Найти минимум функции f(x)=x3-x+e-х на отрезке [0;1] c точностью e и вычислить количество итераций, требуемое для обеспечения точности.
Выберем d =0.001 и положим a = 0; b = 1;
n |
a |
b |
a1 |
b1 |
f(a1) |
f(b1) |
Dn |
1 |
0 |
1 |
0.499 |
0.501 |
0.23239 |
0.23067 |
0.501 |
2 |
0.499 |
1 |
0.7485 |
0.7505 |
0.14392 |
0.14435 |
0.2515 |
3 |
0.499 |
0.7505 |
0.62375 |
0.6257 |
0.15486 |
0.15413 |
0.12675 |
4 |
0.62375 |
0.7505 |
0.68613 |
0.6881 |
0.14040 |
0.14023 |
0.06437 |
… |
….. |
….. |
….. |
…. |
….. |
….. |
…. |
|
0.701719 |
0.71931 |
0.70951 |
0.7115 |
0.13954 |
0.13959 |
0.00979 |
При e = 0.1 x*=0.7183 f(x*)=0.1399, а при e = 0.01 x*=0.7066 f(x*)=0.13951.