ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 5
Скачиваний: 0
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное автономное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
КАФЕДРА 41
|
ОЦЕНКА
ПРЕПОДАВАТЕЛЬ
старший преподаватель |
|
|
|
Н. Н. Григорьева |
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
КОНТРОЛЬНАЯ РАБОТА |
Прикладные методы оптимизации
|
по дисциплине: Прикладные методы оптимизации |
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. № |
Z9411 |
|
|
|
Р. С. Кафка |
|
номер группы |
|
подпись, дата |
|
инициалы, фамилия |
Студенческий билет № |
2019/3603 |
|
|
|
Шифр ИНДО |
|
Санкт-Петербург 2023
-
Нахождение производной сложной функции (вариант 8).
Цель работы: закрепление навыков вычисления производных сложных функций, изучение возможностей среды MathCAD в применении к вычислению производной сложной функции.
Задание: вычислить производные сложных функций в соответствии с вариантом задания вручную и с использованием среды MathCAD.
1.
2.
3.
4.
5.
6.
7.
-
Решение одномерной задачи оптимизации (вариант 8)
Цель работы: изучение алгоритмов поиска экстремума унимодальной функции, определение сравнительной эффективности методов одномерной оптимизации.
Задание: реализовать алгоритмы каждого из описанных методов поиска экстремума функции в указанном интервале с требуемой погрешностью в соответствии с вариантом задания, рассчитать значения критерия оптимальности каждого из алгоритмов.
№ варианта |
Функция Ф(x) |
Интервал [a; b] |
Погрешность определения экстремума Ex |
8 |
|
[4,2; 5,3] |
2-21 |
Посчитать вручную значение точки экстремума для заданной функции на указанном интервале.
Чтобы найти точку экстремума функции f(x)=x2-9x+8 на указанном интервале [4.2; 5.3], необходимо найти производную этой функции и приравнять ее к нулю. Производная функции f’(x) = 2x - 9. Приравнивая ее к нулю, получаем уравнение 2x - 9 = 0, откуда x = 4.5. Так как 4.5 лежит внутри интервала [4.2; 5.3], то это и есть точка экстремума функции на этом интервале.
Произвести исследование заданной функции на экстремум на указанном интервале с помощью алгоритмов:
-
Алгоритм равномерного поиска
Алгоритм равномерного поиска - это метод оптимизации, который используется для поиска экстремума функции одной переменной на заданном отрезке. Он заключается в том, что отрезок делится на равные части и вычисляется значение функции в каждой точке деления. Затем выбирается тот отрезок, на котором значение функции наименьшее (для поиска минимума) или наибольшее (для поиска максимума), и процесс повторяется для этого отрезка.
Чтобы произвести исследование заданной функции f(x)=x2-9x+8 на экстремум на указанном интервале [4.2; 5.3] с помощью алгоритма равномерного поиска с погрешностью определения экстремума Ex = 2-21, необходимо выполнить следующие шаги:
-
Выбрать число точек деления n (чем больше n, тем точнее будет результат).
-
Разделить отрезок [4.2; 5.3] на n равных частей.
-
Вычислить значение функции f(x)=(x^2)-9x+8 в каждой точке деления.
-
Выбрать тот отрезок, на котором значение функции наименьшее (для поиска минимума) или наибольшее (для поиска максимума).
-
Повторить шаги 2-4 для выбранного отрезка до тех пор, пока длина отрезка не станет меньше заданной погрешности Ex = 2^-21.
Количество итераций, необходимых для выполнения задания варианта, зависит от выбранного числа точек деления n и заданной погрешности Ex = 2^-21.
-
Метод дихотомии
Метод дихотомии - это метод оптимизации, который используется для поиска минимума или максимума функции на заданном интервале. Для использования этого метода необходимо знать следующие параметры
Произведем исследование заданной функции f(x)=x^2-9x+8 на экстремум на указанном интервале [4.2; 5.3] с помощью метода дихотомии. Для этого нам необходимо выбрать значение delta (Δ), которое должно быть меньше, чем погрешность определения экстремума Ex = 2^-21. Допустим, мы выберем Δ = Ex/2.
Начальные границы интервала [a; b] = [4.2; 5.3]. На первой итерации мы вычисляем две пробные точки x1 и x2: x1 = (a + b - Δ)/2 и x2 = (a + b + Δ)/2. В нашем случае x1 = (4.2 + 5.3 - Δ)/2 и x2 = (4.2 + 5.3 + Δ)/2.
Затем мы вычисляем значения функции f(x) в точках x1 и x2: f(x1) и f(x2). Если f(x1) < f(x2), то новые границы интервала будут [a; x2], в противном случае [x1; b]. Этот процесс повторяется до тех пор, пока длина интервала не станет меньше или равной погрешности определения экстремума Ex.
Задание требует вычисления числа итераций, необходимых для выполнения задания варианта с помощью метода дихотомии. Число итераций можно вычислить как log((b-a)/Ex)/log(2). В нашем случае это будет log((5.3-4.2)/Ex)/log(2) ≈ 21.
Таким образом, для выполнения задания варианта с помощью метода дихотомии потребуется примерно 21 итерация.
-
Метод золотого сечения
Метод золотого сечения - это метод оптимизации, который использует пропорцию золотого сечения для разделения интервала на две части.
Начальные границы интервала [a; b] = [4.2; 5.3]. На первой итерации мы вычисляем две пробные точки x1 и x2: x1 = a + (b-a)*0.618 и x2 = a + (b-a)*0.618. В нашем случае x1 = 4.2 + (5.3-4.2)*0.618 и x2 = 4.2 + (5.3-4.2)*0.618.
Затем мы вычисляем значения функции f(x) в точках x1 и x2: f(x1) и f(x2). Если f(x1) < f(x2), то новые границы интервала будут [a; x2], в противном случае [x1; b]. Этот процесс повторяется до тех пор, пока длина интервала не станет меньше или равной погрешности определения экстремума Ex.
Задание требует вычисления числа итераций, необходимых для выполнения задания варианта с помощью метода золотого сечения. Число итераций можно вычислить как log((b-a)/Ex)/log((√5+1)/2). В вашем случае это будет log((5.3-4.2)/Ex)/log((0.618) ≈ 31.
Таким образом, для выполнения задания варианта с помощью метода золотого сечения потребуется примерно 31 итерация.
-
Метод Фибоначчи
Метод Фибоначчи - это метод оптимизации, который использует числа Фибоначчи для разделения интервала на две части.
Начальные границы интервала [a; b] = [4.2; 5.3]. На первой итерации мы вычисляем две пробные точки x1 и x2: x1 = a + (b-a)*F(n-2)/F(n) и x2 = a + (b-a)*F(n-1)/F(n), где F(n) - это n-е число Фибоначчи, а n - это номер итерации. В нашем случае x1 = 4.2 + (5.3-4.2)*F(n-2)/F(n) и x2 = 4.2 + (5.3-4.2)*F(n-1)/F(n).
Затем мы вычисляем значения функции f(x) в точках x1 и x2: f(x1) и f(x2). Если f(x1) < f(x2), то новые границы интервала будут [a; x2], в противном случае [x1; b]. Этот процесс повторяется до тех пор, пока длина интервала не станет меньше или равной погрешности определения экстремума Ex.
Задание требует вычисления числа итераций, необходимых для выполнения задания варианта с помощью метода Фибоначчи. Число итераций можно вычислить как log((b-a)/Ex)/log(φ), где φ - золотое сечение (примерно равно 1.618). В вашем случае это будет log((5.3-4.2)/Ex)/log(φ) ≈ 27.
Таким образом, для выполнения задания варианта с помощью метода Фибоначчи потребуется примерно 27 итераций.
Результаты работы методов
Ниже представлен код на языке Python, который реализует алгоритм равномерного поиска, метод дихотомии, метод золотого сечения и метод Фибоначчи для поиска экстремума заданной функции f(x)=(x^2)-9x+8 на указанном интервале [4.2; 5.3] с заданной погрешностью определения экстремума Ex = 2^-21.
Листинг 1 – Код программы
import numpy as np from matplotlib import pyplot as plt
writer = lambda a, b, steps: {'a':a,'b':b,'steps':steps} f = lambda x0: (x0**2)-9*x0+8 eps = 2**(-21) a = 4.2 b = 5.3 eps0 = [[],[],[],[]] res = []
#1 Алгоритм равномерного поиска n = 10 steps = 0 a1, b1 = a, b while (abs(b1-a1) > eps): x = np.arange(a1, b1, (b1-a1)/n) vals = [f(i) for i in x[0:-1]] ch = vals.index(min(vals)) a1, b1 = x[ch-1], x[ch+1] steps += 1 eps0[0].append(b1-a1) res.append(writer(a1, b1, steps))
#2 Алгоритм дихтомии(алгоритм деления пополам) steps = 0 a1, b1 = a, b while (abs(b1-a1) > eps): n = (a1+b1)/2 x = [(a1+n)/2, (b1+n)/ 2] vals = [f(i) for i in x] if vals[0] < vals[1]: b1 = n else: a1 = n steps += 1 eps0[1].append(b1-a1) res.append(writer(a1, b1, steps))
#3 Метод золотого сечения steps = 0 a1, b1 = a, b while (abs(b1-a1) > eps): x = [b1-(b1-a1)*0.618, a1+(b1-a1)*0.618] vals = [f(i) for i in x] if vals[0] < vals[1]: b1 = x[1] else: a1 = x[0] steps += 1 eps0[2].append(b1-a1) res.append(writer(a1, b1, steps))
#4 Метод Фибоначчи steps = 1 a1, b1 = a, b fib = [1, 1] while ((b1 - a1) / fib[-1] > eps): fib.append(fib[-2] + fib[-1]) while (abs(b1-a1) > eps): x = [a1 + (b1 - a1) * (fib[len(fib) - 1 - steps] / fib[len(fib) - steps]), a1 + (b1 - a1) * (fib[len(fib) - 1 - steps] / fib[len(fib) - steps])] if x[0] == x[1]: x[1] = x[0] + (b1 - a1)/10 vals = [f(i) for i in x] if vals[1] < vals[0]: a1 = x[0] else: b1 = x[1] steps += 1 eps0[3].append(b1-a1) res.append(writer(a1, b1, steps-1))
lbls = ['Алгоритм равномерного поиска', 'Метод дихтомии', 'Метод золотого сечения', 'Метод Фибоначчи'] [print(lbls[i],'\n',res[i]) for i in range(len(res))] plt.plot(range(res[0]['steps']),eps0[0], label = lbls[0]) plt.plot(range(res[1]['steps']),eps0[1], label = lbls[1]) plt.plot(range(res[2]['steps']),eps0[2], label = lbls[2]) plt.plot(range(res[3]['steps']),eps0[3], label = lbls[3]) plt.legend() plt.show() |