лаб2_Лопатина_П-41
.docxМинистерство образования и науки Российской Федерации
Федеральное государственное автономное образовательное
учреждение высшего образования
Национальный исследовательский университет “МИЭТ”
Институт Системной и программной инженерии и информационных технологий
Дисциплина: Методы оптимизации
Отчёт по лабораторной работе №2
Вариант 6
Выполнил:
Студент П-41
Лопатина Татьяна
Москва, 2021
Методы минимизации функций одной переменной, использующие информацию о производных целевой функции
Постановка задачи. Требуется найти безусловный минимум функции одной переменной f(x), то есть такую точку x* ∈ U, что f(x*) = min f (x). Значение точки минимума вычислить приближенно с заданной точностью ε.
f ‘(x) = 0; точку x∈ U0 = [a;b] (1)
Функция
Функция. Нахождение производной
Метод средней точки
Теория
Если определение производной f ’(x) в (1) не представляет затруднений, то в процедуре исключения отрезков методом дихотомии вычисление двух значений f(x) вблизи середины очередного отрезка можно заменить вычислением одного значения f ‘(x) в его средней точке x_ = (a+b)/2 . Сравнивая f ‘(x_) с нулем, делим отрезок поиска точки x* ровно вдвое, причем на каждой итерации вычисляется только одно значение f ‘(x).
Алгоритм
Скрипт
Результат работы программы
Метод хорд
Теория
Пусть на концах отрезка [a;b] производная f ‘(x) имеет разные знаки, т.е.
f ‘(a)*f ‘(b) < 0. Тогда на интервале (a;b) найдется точка, в которой f ‘(x) обращается в нуль. В этом случае поиск точки минимума f (x) на отрезке [a;b] эквивалентен решению уравнения f ‘(x) = 0 на интервале (a;b).
Сущность метода хорд приближенного решения уравнения f ‘(x) = 0 на отрезке [a;b] при f ‘(a)*f ‘(b) < 0 состоит в исключении отрезков путем определения точки x~ - точки пересечения с осью Ox хорды графика функции f ‘(x) на [a;b].
Координата точки x~ равна: x~ = a – (f ‘(x) / (f ‘(a) – f ‘(b))) * (a – b) (2)
Отрезок дальнейшего поиска точки x* (отрезок [a;x~] или [x~;b] ) выбирается в зависимости от знака f ‘(x~) так же, как в методе средней точки. На каждой итерации, кроме первой, необходимо вычислять только одно новое значение f ‘(x).
Алгоритм
Скрипт
Результат работы программы
Метод Ньютона
Теория
Для приближенного решения уравнения (1) используется метод касательных. Пусть x ∈ [a;b] – нулевое, или начальное приближение к искомой точке x*. Линеаризуем функцию f(x) = f ‘(x) в окрестности начальной точки, приближенно заменив дугу графика этой функции касательной в точке (x0, f ‘(x0)) :
F(x) ≈ F(x0)+ F ‘(x0)*(x – x0) (3)
Выберем в качестве следующего приближения к x* точку x1 пересечения касательной с осью абсцисс. Приравнивая к нулю правую часть в (3), получим
первый элемент x1= x0–F(x0)/ F ‘(x0) итерационной последовательности {xk}, k = 1, 2, … .
В очередной точке xk строится линейная аппроксимация функции F(x) и точка,
в которой эта аппроксимирующая функция обращается в нуль, используется в
качестве следующего приближения xk+1.
Уравнение касательной к графику F(x) в точке x = xk имеет вид
y = F(xk) + F ‘(xk)*(x – xk), поэтому точка x = xk+1, найденная из условия y = 0 ,
определяется формулой xk+1 = xk – F(xk)/ F ‘(xk).
Вычисления по формуле xk+1 = xk – f ‘(xk)/ f ‘‘(xk) производятся до тех пор, пока не выполнится неравенство |f ‘(xk)| ≤ ε , после чего полагают x* ≈ xk , f* ≈ f (xk)/
Скрипт
Результат работы программы
Сравнительная таблица различных методов
Метод |
х* |
f* |
Количество итераций |
Количество вычислений целевой функции |
Метод средней точки |
1.2599 |
1.8899 |
14 |
14 |
Метод хорд |
1.2599 |
1.8899 |
14 |
14 |
Метод Ньютона |
1.2599 |
1.8899 |
5 |
5 |
Вывод: В ходе лабораторной работы были изучены методы минимизации функции одной переменной и были приобретены навыки программирования методов минимизации функции. Исходя из результатов сравнения, можно сделать вывод, что значения х очень близки по значению при вычислениях каждым методом. Также можно увидеть, что наиболее эффективным является метод Ньютона, метод средней точки и метод хорд обладают меньшей эффективностью, так как количество их итераций равно между собой и больше количества итераций, чем в методе Ньютона.