Лабораторные работы / Отчеты / Методы одномерной оптимизации - Епишкин - Вариант 17 - Павлов - 2006 / Одномерная Оптимизация
.docРоссийский химико-технологический университет им. Д.И.Менделеева
Кафедра вычислительной математики
ОТЧЕТ
Методы Одномерной Оптимизации
Вариант 17
Выполнил: Павлов В.А. гр. И-24
Проверил: Епишкин А.П.
Москва 2006
Методы одномерной оптимизации
Дана некоторая функция от одной переменной , надо определить такое значение , при котором функция принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек. Нахождение этих точек с заданной точностью можно разбить на два этапа. Сначала экстремальные точки отделяют, т.е. определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности . Отделение можно осуществить, как графически, так и табулированием. Все методы уточнения точек экстремумов будем рассматривать относительно уточнения минимума на заданном отрезке.
Метод деления на три равных отрезка.
1. Дан отрезок , на котором определена функция и точность . Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек и . И вычислим Z=1/3.
2. Делим отрезок на три равные части и определяем точку и точку . Вычисляем значения функции в этих точках , .
3. Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как , а , иначе , а .
4. Проверяем условие окончания итерационного процесса . Если оно выполняется, то определим решение, как и значение функции в этой точке . Иначе перейдем на пункт 2.
Метод деления отрезка пополам.
1. Дан отрезок , на котором определена функция и точность . Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек и .
2. Делим отрезок пополам и определяем точку середины и точку , отстоящую на незначительное расстояние от середины . Вычисляем значения функции в этих точках , .
3. Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если , то границы нового отрезка определим как , а , иначе а .
4. Проверяем условие окончания итерационного процесса . Если оно выполняется, то определим решение, как и значение функции в этой точке . Иначе перейдем на пункт 2.
Метод золотого сечения.
1. Дан отрезок , на котором определена функция и точность . Надо уточнить точку минимума с заданной точностью. Вычислим и введём новое обозначение точек и
2. Делим отрезок на три части и определяем точку и точку . Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).
3. Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то пункт 4, иначе пункт 5
4. Границы нового отрезка определим как x1=x1, x4=x3, а x3=x2, F3=F2, x2=x1+Z(x4-x1) и F2=f(x2) пункт 6
5. Границы нового отрезка определим как x1=x2, x4=x4, а x2=x3, F2=F3, x3=x4-Z(x4-x1) и F3=f(x3) пункт 6
6. Проверяем условие окончания итерационного процесса | x4-x1 | ≤ 2ε. Если оно выполняется, то определим решение, как и значение функции в этой точке . Иначе перейдем на пункт 3.
Программа по методу половинного деления, методу золотого сечения,
методу деления на три отрезка:
Private Sub CommandButton1_Click()
Dim i As Byte, x!(21), f!(21), h!, e!, s!, a!, b!, Fa!, Fb!, k!, Fk!, R!, bet!, xn!
e = 0.01
h = 0.5
s = -5
For i = 0 To 20
x(i) = s
s = s + h
Cells(1, 1) = "i"
Cells(1, 2) = "X(i)"
Cells(i + 2, 1) = i
Cells(i + 2, 2) = x(i)
Next i
For i = 0 To 20
f(i) = x(i) ^ 3 + 0.518 * x(i) ^ 2 - 10.805 * x(i) - 2.598
Cells(1, 3) = "f(i)"
Cells(i + 2, 3) = f(i)
Next i
End Sub
Function f!(x!)
f = x ^ 3 + 0.518 * x ^ 2 - 10.805 * x - 2.598
End Function
Private Sub commandbutton2_click()
Dim a!, b!, e!, x1!, x2!, x3!, x4!, z!, f2!, f3!, x!
a = Cells(14, 2)
b = Cells(16, 2)
e = 0.01
x1 = a
x4 = b
z = 1 / 3
i = 0
met1:
x2 = x1 + z * (x4 - x1)
x3 = x4 - z * (x4 - x1)
f2 = f(x2)
f3 = f(x3)
Cells(5 + i, 5) = x1
Cells(5 + i, 6) = x2
Cells(5 + i, 7) = x3
Cells(5 + i, 8) = x4
Cells(5 + i, 9) = f2
Cells(5 + i, 10) = f3
Cells(5 + i, 11) = Abs(x4 - x1)
i = i + 1
If f2 < f3 Then x4 = x3 Else x1 = x2
If Abs(x4 - x1) <= 2 * e Then x = (x1 + x4) / 2: GoTo met2 Else GoTo met1
met2:
Cells(25, 2) = x
Cells(25, 3) = f(x)
End Sub
Private Sub commandbutton3_click()
Dim a!, b!, e!, x1!, x2!, x3!, x4!, f2!, f3!, x!
a = Cells(14, 2)
b = Cells(16, 2)
e = 0.01
x1 = a
x4 = b
met1:
x2 = (x1 + x4) / 2
x3 = x2 + (x4 - x1) / 100
f2 = f(x2)
f3 = f(x3)
Cells(23 + i, 5) = x1
Cells(23 + i, 6) = x2
Cells(23 + i, 7) = x3
Cells(23 + i, 8) = x4
Cells(23 + i, 9) = f2
Cells(23 + i, 10) = f3
Cells(23 + i, 11) = Abs(x4 - x1)
i = i + 1
If f2 < f3 Then x4 = x3 Else x1 = x2
If Abs(x4 - x1) <= 2 * e Then x = (x1 + x4) / 2: GoTo met2 Else GoTo met1
met2:
Cells(26, 2) = x
Cells(26, 3) = f(x)
End Sub
Private Sub commandbutton4_click()
Dim a!, b!, e!, x1!, x2!, x3!, x4!, z!, f2!, f3!, x!
a = Cells(14, 2)
b = Cells(16, 2)
e = 0.01
x1 = a
x4 = b
z = (3 - Sqr(5)) / 2
i = 0
met1:
x2 = x1 + z * (x4 - x1)
x3 = x4 - z * (x4 - x1)
f2 = f(x2)
f3 = f(x3)
Cells(36 + i, 5) = x1
Cells(36 + i, 6) = x2
Cells(36 + i, 7) = x3
Cells(36 + i, 8) = x4
Cells(36 + i, 9) = f2
Cells(36 + i, 10) = f3
Cells(36 + i, 11) = Abs(x4 - x1)
i = i + 1
If f2 < f3 Then x4 = x3: x3 = x2: f3 = f2: x2 = x1 + z * (x4 - x1): f2 = f(x2) Else x1 = x2: x2 = x3: f2 = f3: x3 = x4 - z * (x4 - x1): f3 = f(x3)
If Abs(x4 - x1) <= 2 * e Then x = (x1 + x4) / 2: GoTo met2 Else GoTo met1
met2:
Cells(27, 2) = x
Cells(27, 3) = f(x)
End Sub