Рис 5. Графическое пояснение метода Коши

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

2. Метод Ньютона

Описание алгоритма:

Этот метод использует информацию о вторых производных целевой функции. Эта информация появляется при квадратичной аппроксимации целевой функции, когда при её разложении в ряд Тейлора учитываются члены ряда до второго порядка включительно. Алгоритм метода выглядит следующим образом:

, где:

- гессиан (матрица Гессе)

В случае, когда гессиан положительно определён, направление по методу Ньютона оказывается направлением спуска.

Алгоритм метода:

Шаг 1. Задать: начальную точку х⁽⁰⁾. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска в виде

s(x^(k)) = – .

Шаг 3. Найти новое приближение (являющееся решением задачи для квадратичной функции)

x^(k+1) = x^(k) + s(x^(k)) = x^(k) –.

Шаг 4. Проверка на условие окончания вычислений.

Да: закончить процесс;

Нет: перейти к шагу 2.

Ход решения:

Исходные данные:

- целевая функция;

Шаг 1.

- начальная точка;

Шаг 2.

_{Шаг 3.}

;

Таким образом, точка минимума , значение функции в которойнайдена за одну итерацию.

Рис 6. Графическое пояснение метода Ньютона

2. Метод сопряженных градиентов

Описание алгоритма:

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

Операции аргумента проводятся по формуле:

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

В этом случае направление будет-сопряжено со всеми ранее построенными направлениями поиска.

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

Используемые в методе формулы:

Изменение градиента при переходе от точки к точке:

Изменения аргумента:

Направление поиска:

, ,.

(рекуррентная формула Флетчера-Ривса).

Алгоритм метода:

Шаг 1. Задать: начальную точку х⁽⁰⁾. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска. Произвести поиск вдоль прямой .

Шаг 3. Вычислено ли N-1 направлений.

Да: закончить поиск;

Нет: перейти к шагу 2.

Ход решения:

Исходные данные:

_{Шаг 1.}

- начальная точка;

Шаг 2.

Поиск вдоль прямой:

Шаг 3.

Определим направление

Поиск вдоль прямой:

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