ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 689
Скачиваний: 1
6
Шаг
4
.
Сравнить
1
J
и
2
J
.
Если
2
1
J
J
,
то
2
u
b
и
перейти
к
шагу
5
.
Если
2
1
J
J
,
то
1
u
a
и
перейти
к
шагу
5
.
Если
2
1
J
J
,
то
1
2
,
u
a
u
b
и
перейти
к
шагу
5
.
Шаг
5
.
Если
)
(
a
b
,
то
перейти
к
шагу
2
,
иначе
положить
2
/
)
(
*
a
b
u
,
)
(
*
*
u
J
J
.
Все
описанные
выше
шаги
выполняются
до
тех
пор
,
пока
длина
рассматриваемого
отрезка
больше
или
равна
заданного
малого
числа
.
Чтобы
вычисления
были
максимально
точными
,
число
необходимо
выбирать
достаточно
маленьким
.
Если
оно
большое
,
то
полагают
2
/
и
вычисления
повторяют
.
МЕТОД
«
ЗОЛОТОГО
СЕЧЕНИЯ
»
Рассмотрим
метод
"
золотого
сечения
",
предполагая
,
что
целевая
функция
является
унимодальной
на
рассматриваемом
отрезке
.
Напомним
,
что
нахождение
точки
b
a
u
,
доставляющей
локальный
минимум
,
осуществляется
путём
последовательного
уменьшения
отрезка
,
содержащего
точку
минимума
.
В
методе
"
золотого
сечения
"
для
сужения
отрезка
унимодальности
будут
использоваться
две
точки
1
u
и
2
u
,
выполняющие
"
золотое
сечение
"
данного
отрезка
.
Определение
.
Будем
говорить
,
что
точка
u
осуществляет
"
золотое
сечение
"
отрезка
]
,
0
[
A
,
если
выполняется
соотношение
u
A
u
u
A
,
т
.
е
.
если
отношение
длины
отрезка
к
большей
его
части
равно
отношению
большей
части
к
меньшей
(
см
.
рис
. 3).
7
Рис
. 3
Пусть
точка
1
u
осуществляет
"
золотое
сечение
"
отрезка
b
a
,
.
Поскольку
b
a
u
,
,
то
)
(
a
b
a
u
,
1
0
.
Если
длина
отрезка
u
a
,
больше
длины
отрезка
b
u
,
,
то
удовлетворяет
соотношению
1
1
.
Откуда
,
учитывая
положительность
,
получаем
,
что
2
1
5
.
Если
же
большей
является
длина
отрезка
b
u
,
,
то
удовлетворяет
соотношению
1
1
1
.
Откуда
в
силу
того
,
что
1
,
получаем
2
5
3
.
Значит
,
мы
показали
,
что
точки
1
u
и
2
u
,
вычисляемые
соответственно
по
формулам
a
a
b
u
2
5
3
1
и
a
a
b
u
2
1
5
2
осуществляют
"
золотое
сечение
"
отрезка
]
,
[
b
a
.
Эти
точки
расположены
симметрично
относительно
середины
отрезка
.
Кроме
того
,
точка
1
u
является
"
золотым
сечением
"
отрезка
2
,
u
a
(
1
2
1
u
u
a
u
);
а
точка
2
u
является
"
золотым
сечением
"
отрезка
b
u
,
1
(
1
2
2
u
u
u
b
);.
Отметим
,
что
2
5
3
2
1
5
2
.
АЛГОРИТМ
Шаг
1
.
Положить
0
n
,
задать
,
,
b
a
.
Положить
2
1
5
и
2
5
3
1
.
Шаг
2
.
Положить
)
(
1
1
a
b
a
u
,
)
(
2
a
b
a
u
.
Шаг
3
.
Положить
1
n
n
и
вычислить
)
(
1
1
u
J
J
,
)
(
2
2
u
J
J
.
Шаг
4
.
Сравнить
1
J
и
2
J
.
Если
2
1
J
J
,
то
положить
2
u
b
,
1
2
u
u
,
1
2
J
J
,
)
(
1
1
a
b
a
u
,
)
(
1
1
u
J
J
.
Перейти
к
шагу
5
.
Если
2
1
J
J
,
то
положить
1
u
a
,
2
1
u
u
,
2
1
J
J
,
)
(
2
a
b
a
u
,
)
(
2
2
u
J
J
.
Перейти
к
шагу
5
.
Если
2
1
J
J
,
то
1
2
,
u
a
u
b
,
)
(
1
1
a
b
a
u
,
)
(
2
a
b
a
u
,
)
(
1
1
u
J
J
,
)
(
2
2
u
J
J
.
Перейти
к
шагу
5
.
Шаг
5
.
Если
)
(
a
b
,
то
перейти
к
шагу
3
,
иначе
положить
2
/
)
(
*
a
b
u
,
)
(
*
*
u
J
J
.
Все
описанные
выше
шаги
выполняются
до
тех
пор
,
пока
длина
рассматриваемого
отрезка
больше
или
равна
заданного
малого
числа
.
8
МЕТОД
ПАРАБОЛ
Рассмотрим
метод
парабол
.
Предполагаем
,
что
целевая
функция
является
унимодальной
на
рассматриваемом
отрезке
.
Суть
метода
состоит
в
последовательном
сужении
отрезка
,
содержащего
точку
минимума
,
используя
аппроксимацию
функции
на
этом
отрезке
полиномом
второго
порядка
.
Определение
.
Тройка
точек
3
2
1
,
,
u
u
u
является
выпуклой
для
функции
)
(
u
J
,
если
справедливы
следующие
неравенства
0
)
(
)
(
2
1
u
J
u
J
,
0
)
(
)
(
2
3
u
J
u
J
, 0
.
Рис
. 4
Пусть
наша
тройка
выпукла
.
Тогда
можно
провести
параболу
2
1
2
0
)
(
u
u
u
f
через
точки
с
координатами
))
(
,
(
)),
(
,
(
)),
(
,
(
3
3
2
2
1
1
u
J
u
u
J
u
u
J
u
.
Функция
)
(
u
f
будет
совпадать
с
многочленом
Лагранжа
,
построенным
по
указанным
точкам
.
Причём
точка
w
-
точка
минимума
построенной
параболы
вычисляется
по
следующей
формуле
)
)
(
)
((
2
)
(
)
(
1
2
2
3
2
1
2
2
2
3
2
u
u
u
u
u
u
u
u
u
w
.
Возможны
следующие
варианты
1.
Точка
минимума
параболы
расположена
слева
от
точки
2
u
,
т
.
е
.
2
u
w
.
1.1.
Если
)
(
)
(
2
u
J
w
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
2
1
u
w
u
, (
т
.
е
.
промежуток
унимодальности
функции
]
,
[
2
1
u
u
).
9
1.2.
Если
)
(
)
(
2
u
J
w
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
3
2
u
u
w
, (
т
.
е
.
промежуток
унимодальности
функции
]
,
[
3
u
w
).
1.3.
Если
)
(
)
(
2
u
J
w
J
,
тогда
:
1.3.1.
Если
)
(
)
(
2
1
u
J
u
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
2
1
u
w
u
.
1.3.2.
Если
)
(
)
(
3
2
u
J
u
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
3
2
u
u
w
.
2.
Точка
минимума
параболы
расположена
справа
от
точки
2
u
,
т
.
е
.
2
u
w
.
2.1.
Если
)
(
)
(
2
u
J
w
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
3
2
u
w
u
, (
т
.
е
.
промежуток
унимодальности
функции
]
,
[
3
2
u
u
).
2.2.
Если
)
(
)
(
2
u
J
w
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
2
1
w
u
u
, (
т
.
е
.
промежуток
унимодальности
функции
]
,
[
1
w
u
).
2.3.
Если
)
(
)
(
2
u
J
w
J
,
тогда
:
2.3.1.
Если
)
(
)
(
2
3
u
J
u
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
3
2
u
w
u
.
2.3.2.
Если
)
(
)
(
2
1
u
J
u
J
,
то
новой
выпуклой
тройкой
считаем
)
,
,
(
2
1
w
u
u
.
3.
Точка
минимума
параболы
совпадает
с
2
u
,
т
.
е
.
2
u
w
.
В
этом
случае
в
качестве
новой
тройки
берём
)
,
~
,
(
3
2
1
u
u
u
,
где
2
~
u
-
любая
точка
отрезка
)
,
(
3
1
u
u
,
в
которой
)
(
)
~
(
2
2
u
J
u
J
и
)
(
)
~
(
1
2
u
J
u
J
.
Например
,
можно
положить
2
2
~
u
u
или
2
2
~
u
u
в
зависимости
от
того
,
что
меньше
)
(
)
(
2
2
u
J
u
J
или
)
(
)
(
2
2
u
J
u
J
.
Если
в
обоих
случаях
значение
функции
в
точке
2
u
меньше
,
то
уменьшаем
,
пока
либо
не
получим
новую
выпуклую
тройку
,
либо
не
будет
меньше
заданной
величины
.
В
этом
случае
полагаем
2
*
u
u
.
МЕТОД
НЬЮТОНА
ОДНОМЕРНОЙ
МИНИМИЗАЦИИ
Метод
Ньютона
является
последовательным
методом
второго
порядка
.
Предполагается
,
что
функция
)
(
u
J
дважды
дифференцируема
,
причём
0
)
(
u
J
(
условие
гарантирующее
выпуклость
функции
)
(
u
J
).
В
этом
случае
корень
уравнения
0
)
(
u
J
можно
приближённо
искать
методом
касательных
.
В
отличие
от
предыдущих
методов
,
метод
Ньютона
не
относится
к
методу
сокращения
промежутков
.
Для
начала
работы
метода
вместо
задания
начального
промежутка
неопределённости
требуется
задание
начальной
точки
0
u
,
в
которой
вычисляется
0
)
(
0
u
J
и
0
)
(
0
u
J
.
В
процессе
работы
метода
генерируется
последовательность
,...
2
,
1
,
k
u
k
.
В
очередной
точке
k
u
строится
линейная
аппроксимация
функции
)
(
u
J
(
касательная
к
графику
)
(
u
J
).
Точка
,
в
которой
линейная
аппроксимирующая
функция
обращается
в
нуль
,
используется
в
качестве
следующего
приближения
1
k
u
.
Уравнение
касательной
к
графику
)
(
u
J
в
точке
k
u
имеет
вид
)
)(
(
)
(
k
k
k
u
u
u
J
u
J
v
,
поэтому
точка
1
k
u
,
найденная
из
условия
0
v
,
определяется
формулой
10
)
(
)
(
1
k
k
k
k
u
J
u
J
u
u
.
Процедура
нахождения
точек
k
u
продолжается
до
тех
пор
,
пока
не
будет
достигнута
требуемая
точность
,
т
.
е
.
|
)
(
|
k
u
J
.
АЛГОРИТМ
Шаг
1
.
Задать
начальную
точку
0
u
,
0
-
требуемую
точность
.
Положить
0
k
.
Шаг
2
.
Вычислить
)
(
k
u
J
.
Шаг
3
.
Если
|
)
(
|
k
u
J
,
то
положить
k
u
u
*
и
)
(
)
(
*
k
u
J
u
J
и
поиск
завершить
.
Иначе
перейти
к
шагу
4
.
Шаг
4
.
Вычислить
)
(
)
(
1
k
k
k
k
u
J
u
J
u
u
.
Шаг
5
.
Положить
1
k
k
.
Перейти
к
шагу
2
.
Исследования
метода
Ньютона
показывают
,
что
при
достаточно
близком
к
точке
минимума
*
u
выборе
начального
приближения
0
u
,
гарантируется
скорость
сходимости
последовательности
,...
2
,
1
,
0
,
k
u
k
к
*
u
вида
k
Cq
u
u
k
2
*
|
|
,
где
)
1
,
0
(
q
,
0
C
;
q
и
C
зависят
от
выбора
функции
)
(
u
J
и
выбора
0
u
.
Если
начальное
приближение
0
u
выбрано
не
достаточно
близко
к
точке
*
u
,
то
последовательность
,...
2
,
1
,
0
,
k
u
k
метода
Ньютона
может
расходиться
.
В
подобных
случаях
необходимо
найти
лучшее
начальное
приближение
0
u
,
например
,
с
помощью
нескольких
итераций
метода
"
золотого
сечения
".
ПРИМЕРЫ
1.
И
сследовать
на
минимум
функцию
)
1
(
)
(
2
3
u
u
u
J
при
условии
,
что
]
1
,
0
[
u
.
Сделаем
несколько
итераций
методом
деления
отрезка
пополам
.
Пусть
2
,
0
;
2
,
0
.
Тогда
значения
переменных
2
1
,
u
u
на
первом
шаге
вычислений
соответственно
равны
6
,
0
;
4
,
0
2
1
u
u
.
Целевая
функция
в
посчитанных
точках
имеет
значения
13824
,
0
)
(
;
05376
,
0
)
(
2
1
u
J
u
J
.
Так
как
)
(
)
(
2
1
u
J
u
J
,
то
полагаем
1
;
4
,
0
1
1
1
b
b
u
a
.
На
втором
шаге
вычисляем
значения
точек
8
,
0
;
6
,
0
2
1
u
u
и
соответствующие
значения
целевой
функции
в
посчитанных
точках
18432
,
0
)
(
;
13824
,
0
)
(
2
1
u
J
u
J
.
Так
как
)
(
)
(
2
1
u
J
u
J
,
то
полагаем
1
;
6
,
0
2
1
2
b
b
u
a
.
Третий
шаг
вычислительной
процедуры
позволяет
посчитать