Кокуев А.Г. Решение задач оптимизации в среде MATLAB
Подождите немного. Документ загружается.
11
б) если
)(
k
yf
≥
)(
c
k
xf
, перейти к шагу 6.
Шаг 6. Сравнить
)(
k
zf
c
)(
c
k
xf
:
а) если
)(
k
zf
<
)(
c
k
xf
, исключить интервал
),[
c
kk
xa
, положив
c
kk
xa
1
,
kk
bb
1
. Средней точкой нового интервала становится точка
z
k
:
k
c
k
zx
1
. (рис. 1.4, б). Перейти к шагу 7;
б) если
)(
k
zf
≥
)(
c
k
xf
исключить интервалы
),[
kk
ya
и
],(
kk
bz
,
положив
kk
ya
1
,
kk
zb
1
. Средней точкой нового интервала останется
c
k
x
:
c
k
c
k
xx
1
. (рис. 1.4, в).
Рис. 1.4 Уменьшение интервала неопределенности
а)
б)
f(x)
x
текущий интервал
y
k
c
k
x
z
k
b
k
a
k
новый интервал
y
k
c
k
x
z
k
b
k
a
k
f(x)
x
текущий интервал
новый интервал
в)
новый интервал
y
k
c
k
x
z
k
b
k
a
k
f(x)
x
текущий интервал
12
Шаг 7. Вычислить
11)1(2 kkk
abL
и проверить условие
окончания:
а) если
)1(2 k
L
≤ l, процесс поиска завершается и
11)1(2
*
,
kkk
baLx
. В качестве приближенного решения можно взять
середину последнего интервала:
c
k
xx
1
*
,
б) если
)1(2 k
L
> l, то положить k = k + 1 и перейти к шагу 4.
Сходимость
Для метода деления интервала пополам характеристика относительного
уменьшения начального интервала неопределенности находится по
формуле
2
2
1
)(
N
NR
, где N – количество вычислений функции.
Замечания 1.3:
1. Средняя точка последовательно получаемых интервалов всегда
совпадает с одной из трех пробных точек, найденных на предыдущей итерации.
Следовательно, на каждой итерации требуются два новых вычисления функции.
2. Если задана величина R(N), то требуемое для достижения желаемой
точности количество вычислений функции находится как наименьшее целое,
удовлетворяющее условию
5,0ln
)(ln2 NR
N
.
3. Текущие интервалы имеют четные номера L
0
,L
2
,L
4
,..., где индекс ука-
зывает на сделанное количество вычислений функции.
1.4 Метод дихотомии
Постановка задачи
13
Требуется найти безусловный минимум функции f(x) одной переменной
т.е. такую точку
Rx
*
, что
Rx
xfxf )(min)(
*
.
Стратегия поиска
Метод относится к последовательным стратегиям. Задается начальный
интервал неопределенности и требуемая точность. Алгоритм опирается на
анализ значений функции в двух точках (см. рис. 1.2). Для их нахождения
текущий интервал неопределенности делится пополам и в обе стороны от
середины откладывается по
2
, где – малое положительное число. Условия
окончания процесса поиска стандартные: поиск заканчивается, когда длина
текущего интервала неопределенности оказывается меньше установленной
величины.
Алгоритм
Шаг 1. Задать начальный интервал неопределенности L
0
= [a
0
, b
0
],
> 0 – малое положительное число и l > 0 – точность.
Шаг 2. Положить k = 0.
Шаг 3. Вычислить
2
kk
k
ba
y
, f(y
k
),
2
kk
k
ba
z
, f(z
k
).
Шаг 4. Сравнить f(y
k
) и f(z
k
).
а) если f(y
k
) ≤ f(z
k
), положить a
k+1
= a
k
, b
k+1
= z
k
(рис. 1.5, а) и перейти к
шагу 5.
б) если f(y
k
) > f(z
k
), положить a
k+1
= y
k
, b
k+1
= b
k
(рис. 1.5, б).
Рис. 1.5 Уменьшение интервала неопределенности
f(x)
x
текущий интервал
новый интервал
y
k
z
k
b
k
a
k
2
2
а)
б)
f(x)
x
текущий интервал
новый интервал
2
y
k
z
k
b
k
a
k
2
14
Шаг 5. Вычислить
11)1(2 kkk
abL
и проверить условие окончания:
а) если
)1(2 k
L
≤ l, процесс поиска завершается и
11)1(2
*
,
kkk
baLx
. В качестве приближенного решения можно взять
середину последнего интервала:
2
11
*
kk
ba
x
,
б) если
)1(2 k
L
> l, то положить k = k + 1 и перейти к шагу 3.
Сходимость
Для метода дихотомии характеристика относительного уменьшения на-
чального интервала неопределенности находится по формуле
2
2
1
)(
N
NR
,
где N – количество вычислений функции.
Замечания 1.4:
1. Текущие интервалы имеют четные номера L
0
,L
2
,L
4
,..., где индекс ука-
зывает на сделанное количество вычислений функции, как и в методе деления
интервала пополам.
2. Эффективность методов дихотомии и деления интервала пополам
при малых можно считать одинаковой.
1.5 Метод золотого сечения
Постановка задачи
Требуется найти безусловный минимум функции f(x) одной переменной
т.е. такую точку
Rx
*
, что
Rx
xfxf )(min)(
*
.
Для построения конкретного метода одномерной минимизации,
работающего по принципу последовательного сокращения интервала
15
неопределенности, следует задать правило выбора на каждом шаге двух
внутренних точек. Желательно, чтобы одна из них всегда использовалась в
качестве внутренней и для следующего интервала. Тогда число вычислений
функции сократится вдвое и одна итерация потребует расчета только одного
нового значения функции. В методе золотого сечения в качестве двух
внутренних точек выбираются точки золотого сечения.
Определение: Точка производит "золотое сечение" отрезка, если
отношение длины всего отрезка к большей части равно отношению большей
части к меньшей.
На отрезке [a
0
, b
0
]имеются две симметричные относительно его концов
точки у
0
и z
0
:
618,1
2
51
00
00
00
00
00
00
00
00
zb
az
az
ab
ay
yb
yb
ab
Кроме того, точка у
0
производит золотое сечение отрезка [a
0
, z
0
], a точка
z
0
– отрезка [y
0
,b
0
]:
Стратегия поиска
Метод относится к последовательным стратегиям. Задается начальный
интервал неопределенности и требуемая точность. Алгоритм уменьшения
интервала опирается на анализ значений функции в двух точках (см. рис. 1.2). В
качестве точек вычисления функции выбираются точки золотого сечения. Тогда
с учетом свойств золотого сечения на каждой итерации, кроме первой,
требуется только одно новое вычисление функции. Условия окончания
процесса поиска стандартные: поиск заканчивается, когда длина текущего
интервала неопределенности оказывается меньше установленной величины.
Алгоритм
Шаг 1. Задать начальный интервал неопределенности L
0
= [a
0
, b
0
]
и l > 0 – точность.
Шаг 2. Положить k = 0.
a
0
y
0
z
0
b
0
16
Шаг 3. Вычислить
)(
2
53
0000
abay
,
0000
ybaz
.
Шаг 4. Вычислить f(y
k
) и f(z
k
).
Шаг 5. Сравнить f(y
k
) и f(z
k
).
а) если f(y
k
) ≤ f(z
k
), положить a
k+1
= a
k
, b
k+1
= z
k
и y
k+1
= a
k+1
+b
k+1
-z
k
,
z
k+1
= y
k
(рис. 1.6, а) и перейти к шагу 6.
б) если f(y
k
) > f(z
k
), положить a
k+1
= y
k
, b
k+1
= b
k
и y
k+1
= z
k
,
z
k+1
= a
k+1
+b
k+1
- z
k
(рис. 1.6, б).
Шаг 6. Вычислить
11 kk
ab
и проверить условие окончания:
а) если ≤ l, процесс поиска завершается и
11
*
,
kk
bax
. В качестве
приближенного решения можно взять середину последнего интервала:
2
11
*
kk
ba
x
,
б) если > l, то положить k = k + 1 и перейти к шагу 4.
Сходимость
Для метода золотого сечения характеристика относительного
уменьшения начального интервала неопределенности находится по формуле
1
)618,0()(
N
NR
, где N - количество вычислений функции.
Рис. 1.6 Уменьшение интервала неопределенности
а)
б)
f(x)
x
текущий интервал
новый интервал
y
k
= z
k
+1
z
k
b
k
a
k
f(x)
x
текущий интервал
новый интервал
y
k
z
k
= y
k
+1
b
k
a
k
17
Замечания 1.5.
1. Текущие интервалы неопределенности имеют следующий
вид: L
0
,L
2
,L
3
, L
4
,...,. Они отражают тот факт, что на первой итерации
производится два вычисления функции, а на последующих – по одному.
2. Сокращение длины интервала неопределенности постоянно:
618,1
2
51
...
4
3
3
2
2
0
L
L
L
L
L
L
3. Если задана величина R(N), то требуемое для достижения желаемой
точности количество вычислений функции находится как наименьшее целое
число, удовлетворяющее условию
618,0ln
)(ln
1
NR
N
2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ПО РАБОТЕ В СРЕДЕ
MATLAB
2.1 Рабочая среда MATLAB
18
При запуске MATLAB на экране открывается рабочая среда MATLAB,
изображенная на рис. 1.1.
Основными элементами рабочей среды являются:
меню;
панель инструментов с кнопками и раскрывающимся списком;
окна с вкладками Workspace и Current Directory для просмотра
переменных и установки текущего каталога;
окно Command Window, служащее для ввода команд и вывода
результата;
окно Command History, предназначенное для просмотра и
повторного выполнения ранее введенных команд (окно Command
History может быть не пустым, если до этого пакет MATLAB
использовался);
Рис. 1 Рабочая среда MATLAB
19
строка состояния с кнопкой Start.
Окно Command Window состоит из следующих элементов:
заголовка с названием окна и двумя кнопками справа;
рабочей области с командной строкой, в которой находится
мигающий вертикальный курсор;
полос скроллинга.
Все команды, следует набирать в командной строке. Сам символ >>
приглашения командной строки, набирать не нужно. Для просмотра рабочей
области командного окна удобно использовать полосы скроллинга или клавиши
<Home>, <End> для перемещения влево или вправо и <PageUp>, <PageDown>
для перемещения вверх или вниз. Если вдруг после перемещения по рабочей
области командного окна пропала командная строка с мигающим курсором,
просто нажмите <Enter>.
Набор любой команды или выражения должен заканчиваться нажатием
на <Enter>, для того чтобы программа MATLAB выполнила эту команду или
вычислила выражение.
2.2 Простейшие вычисления
Выберите вид рабочей среды "по умолчанию", наберите в командной
строке 1+2 и нажмите <Enter>. В результате в командном окне MATLAB
отображается следующее:
>> 1 + 2
ans = 3
>>
Что сделала программа MATLAB? Сначала она вычислила сумму 1 + 2,
затем записала результат в специальную переменную ans и вывела ее значение,
равное 3, в командное окно. Переменная ans автоматически создается, когда
вычисляемое выражение не присваивается некоторой переменной.
20
2.3 Использование элементарных функций
Предположим, что требуется вычислить значение следующего
выражения:
3,3
78,3cos45,2sin
)3,11(ln
3,05,2
tg
e
Введите в командной строке это выражение в соответствии с правилами
MATLAB и нажмите <Enter>.
>> exp(-2.5)*log(11.3)^0,3-sqrt((sin(2,45*pi)+cos(3.78*pi))/tan(3.3))
Ответ выводится в командное окно:
ans =
-3.2105
При вводе выражения использованы встроенные функции MATLAB
для вычисления экспоненты, натурального логарифма, квадратного корня и
тригонометрических функций. Аргументы функций заключаются в круглые
скобки, имена функций набираются строчными буквами. Для ввода числа π
достаточно набрать pi в командной строке.
Арифметические операции в MATLAB выполняются в обычном
порядке, свойственном большинству языков программирования:
возведение в степень — ^;
умножение и деление — *, /;
сложение и вычитание — +, -.
Для изменения порядка выполнения арифметических операторов
следует использовать круглые скобки.
2.4 М-файлы
В предыдущих разделах рассмотрены достаточно простые примеры,
для выполнения которых требуется набрать несколько команд в командной
строке. Для более сложных задач число команд возрастает, и работа в
командной строке становится непродуктивной. Использование истории команд,
сохранение переменных рабочей среды или ведение дневника при помощи diary
незначительно повышают производительность работы. Эффективное решение
состоит в оформлении собственных алгоритмов в виде программ (М-файлов),