g4 (542467), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

В качестве , если нет никаких специальных соображений, удобно выбирать единичную матрицу.

Пример 2.

Найти точку минимума с точностью .

Решение

В качестве выберем единичную матрицу

Положим

(Заметим, что эту же задачу мы решали методом Ньютона).

найдем как параметр, минимизирующий классическим методом, то есть приравниванием производной нулю

.

Тогда

Вычисления производятся с 5 знаками после запятой.

удовлетворяет следующему соотношению:

Отсюда

Делаем вторую итерацию

Ранее эта задача была решена, и мы видим, что в пределах точности последнее решение совпадает с точным. Матрица совпадает с обратной матрицей вторых производных. Квазиньютоновские методы всегда сходятся к точному решению за n шагов.

Формально эти методы относятся к методам первого порядка, однако, их сходимость выше сходимости указанных методов в силу хорошей аппроксимации обратной матрицы вторых производных, что обеспечивает их широкую применимость.

4.3.2Градиентные методы.

Известно, что функция многих переменных наиболее сильно убывает в направлении антиградиента функции в этой точке, то есть в направлении вектора .

Это локальное свойство положено в основу целой серии методов, называемых градиентными и задаваемых отношением

,

- вектор начального приближения;

- шаг метода.

4.3.2.1Метод наискорейшего спуска.

Если на каждом шаге выбирать как значение, обеспечивающее , то мы и получим метод наискорейшего спуска, то есть на каждой итерации необходимо решать задачу одномерной минимизации, которая в основном решается численно.

Итак, для того чтобы использовать метод наискорейшего спуска, необходимо задать правила вычислений , (предварительно продифференцировав ), выбрать метод одномерной минимизации.

На рисунке 3.1 представлена укрупненная блок-схема такого алгоритма, где критерием окончания счета выбрана близость градиента нулю. Рассмотрим предыдущий пример. Найти минимум

Методом наискорейшего спуска вычисления будут производится по расчетной формуле

Как и в предыдущих случаях в качестве начального приближения возьмем

на каждой итерации находится классическим методом, то есть приравниванием производной нулю.

Рисунок 4.3.2 Блок-схема метода наискорейшего спуска.

Результаты вычислений по итерациям представлены в таблице.

Как показано выше, точным решением этой задачи является , проведенные 9 итераций не обеспечили получение приближенного решения с точностью .

Интересным является тот факт, что рассмотренный выше квазиньютоновский метод(тоже метод 1-го порядка) обеспечивает для той же задачи получение точного решения за 2 шага, в то время, как метод наискорейшего спуска требует существенно большего числа итераций.

На рисунке 3.2 для трех рассмотренных выше методов представлены траектории движения из начальной точки в точку минимума .

Сплошная линия соответствует методу наискорейшего спуска, пунктирная - квазиньютоновскому методу, пунктирная с точками - методу Ньютона.

Рисунок 4.3.3 Траектория движения из точки в точку минимума функции

Ломаная траектории метода наискорейшего спуска удивляет своим характером.

Изменим немного вид исходной функции. Пусть

.

Нетрудно показать, что точкой минимума и этой функции будет . Применим метод наискорейшего спуска, начав с точки .

Расчетная формула метода имеет вид

,

Найдем из условия

Отсюда , то есть за один шаг попали в точку минимума.

Чем же разнятся эти задачи, дающие разные по трудоемкости вычислительные процедуры?

Представим линии уровня каждой из функций.

Для

линиями уровня будут кривые

или

Получили каноническое уравнение эллипса, из которого видно, что одна из полуосей в 3 раза меньше другой, то есть эллипс вытянут вдоль оси .

Для линиями уровня будут концентрические окружности с центром в точке .

На рисунке с нанесенными на плоскость линиями уровня представлена траектории движения из точки в точку , соответствующая методу наискорейшего спуска для функции

На рисунке 3.4 то же проделано для функции

Рисунок 4.3.4 Траектория движения из точки в точку функции

Рисунок 4.3.5 Траектория движения из точки в точку функции

Чем больше вытянуты линии уровня, тем сильнее будет эффект «зигзага» траектории. В этом случае функция имеет так называемый «овражный» характер, то есть небольшое изменение переменной приводит к резкому изменению значений функции, а по переменной функция меняется незначительно. В процессе реализации градиентного метода очередные приближения будут прыгать со склона на склон, что может сильно замедлить сходимость метода. Этой проблеме уделяется достаточно серьезное внимание, в настоящее время существуют специальные методы.

4.3.2.2Градиентный метод с дроблением шага.

В методе наискорейшего спуска на каждом шаге необходимо решать задачу одномерной минимизации, для чего используется один из методов одномерной минимизации, предполагающих наличие одного минимума внутри некоторого отрезка, в чем не всегда бывает уверенность. Поэтому широко используется градиентный метод без одномерной минимизации, основанный на пошаговой корректировке коэффициента . По-прежнему расчетной будет формула

,

задаемся некоторым . Полагаем . Если при этом , то удваиваем шаг: . Процесс удвоения продолжаем до тех пор, пока убывание не прекратится.

Если , то полагаем: , если при этом не произошло уменьшение значения функции, то процесс дробления продолжаем до тех пор, пока не наступит убывание.

Эта логика работает на каждом шаге.

Этот метод сойдется, если выпукла и не является «овражной».

Рисунок 4.3 .6 - блок - схема градиентного метода с дроблением (другой вариант градиентного метода с дроблением шага).

Рисунок 4.3.6 Блок-схема градиентного метода с дроблением шага.

4.4Методы нулевого порядка.

В практических задачах нередки случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление производных с нужной точностью является слишком трудоемким. В таких случаях применяют методы минимизации, которые требуют лишь вычисления значений функций, то есть методы 0-го порядка. Из методов этого типа рассмотрим 2 наиболее распространенных: метод покоординатного спуска и метод случайного поиска.

4.4.1Метод покоординатного спуска.

Суть метода состоит в том, что задав начальное приближение выбирается направление движения по одной из покоординатных осей, причем, на последующих шагах идет циклический перебор направлений по координатным осям.

Наиболее распространенным является метод покоординатного спуска с дроблением шага.

Обозначим - единичный координатный(базисный) вектор, у которого i - я координата равна 1, а остальные равны 0.

Положим ; , - целая часть числа .

Будем иметь

Опишем подробно одну итерацию.

Пусть получено . Будем искать .

Вычислим значение функции в точке и проверим неравенство .

Если это неравенство выполняется, то полагаем

.

В случае, если неравенство не выполняется, то вычисляем и проверим неравенство .

В случае выполнения последнего неравенства полагаем

.

В случае невыполнения обоих неравенств полагаем

,

- параметр метода; .

Последние условия означают, что если за один цикл из n итераций при переборе направлений всех координатных осей с шагом реализовалась хотя бы одна удачная итерация, то длина шага не дробится и сохраняется по крайне мере на протяжении следующего цикла из n итераций.

Характеристики

Список файлов книги