- •Раздел 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.3. Метод золотого сечения
В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения, такого, что отношение длины его большей части ко всей длине отрезка равно отношению длины его меньшей части к длине его большей части:
l
l2 l1
Положим l =1, тогда l22= 1 - l2 , а l22 + l2 -1= 0, откуда
где k1, k2 - коэффициенты золотого сечения.
В методе золотого сечения каждая точка (х1 и х2)осуществляет золотое сечение отрезка (рис. 6.6.3-1).
Рис. 6.6.3-1
или
Нетрудно проверить, что точка х1 осуществляет золотое сечение не только отрезка [a;b], но и отрезка [a;х2]. Точно так же точка х2 осуществляет золотое сечение не только отрезка [a;b], но и отрезка [х1;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.
После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности Dn = 0.618nD0, где D0= (b-a) – начальная длина отрезка.
Условие окончания процесса итераций Dn e. Отсюда можно найти количество итераций, необходимое для достижения точки минимума:
отсюда логарифмируя, получим
Пример 6.6.3-1. Пусть минимум функции f(x) = x3 – x + e-x отделен на отрезке [0;1]. Определить количества итераций и конечные длины отрезков неопределенности, необходимые для достижения заданных точностей e=0.1 и e=0.01.
-
N
a
b
x1
x2
f(x1)
f(x2)
Dn
1
0
1
0.38196
0.61803
0.35628
0.15704
0.61803
2
0.38196
1
0.61803
0.76393
0.15704
0.14772
0.382
3
0.61803
1
0.76393
0.85410
0.14772
0.19462
0.236
4
0.61803
0.85410
0.70820
0.76393
0.13953
0.14772
0.146
5
0.61803
0.76393
0.67376
0.70820
0.14188
0.13953
0.090
При e = 0.1 x*=0.718847, f(x*)=0.139925.
При e = 0.01 x*=0.704139, f(x*)=0.139516.
6.6.4. Сравнение методов
На каждой итерации при использовании метода дихотомии отрезок неопределенности сокращается практически в два раза, а при использовании метода золотого сечения в 1.618 раз.
Конечная длина отрезка неопределенности при использовании метода дихотомии , а при использовании метода золотого сечения - , поэтому для обеспечения одного и того же значения погрешности методом дихотомии требуется произвести меньше итераций, чем при использовании метода золотого сечения.
На каждой итерации в методе дихотомии целевая функция вычисляется два раза, а в методе золотого сечения только один раз, следовательно, метод золотого сечения менее трудоемок с точки зрения вычислений.