Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Конспект_Методы Оптимизации Систем Автоматизиро...doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

Модификации метода Ньютона. Метод Ньютона-Рафсона.

Стратегия поиска.Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения . Если находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Для ослабления влияния начальной точки на сходимость метода используется метод Ньютона-Рафсона. Стратегия метода Ньютона-Рафсона состоит в построении последовательности точек , k=0, 1, ... таких, что , k=0, 1, ...

Точки последовательности вычисляются по правилу:

где – задается пользователем, а направление спуска вычисляется по формуле:

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

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

Начальный этап

Задать , .

Найти градиент функции в произвольной точке

и матрицу Гессе H(x)

Положить k=0.

Основной этап

Шаг 1. Вычислить

Шаг 2. Проверить выполнение критерия останова

а) если критерий выполнен, расчет окончен,

б) если критерий не выполнен, то перейти к шагу 3.

Шаг 3. Вычислить матрицу Гессе

Шаг 4. Найти обратную матрицу

Шаг 5. Проверить положительную определенность матрицы

Шаг 6. Найти

Шаг 7. Найти величину шага из условия

Шаг 8. Вычислить

Шаг 9. Положить k= k +1 и перейти к шагу 1

Сходимость метода.

Теорема 5. Пусть функция f(x) дважды непрерывно дифференцируемая сильно выпуклая функция на , а ее матрица Гессе H(X) удовлетворяет условию Липшица

Тогда последовательность сходится независимо от выбора начальной точки к точке минимума с квадратичной скоростью

,

где m - оценка наименьшего собственного значения матрицы Гессе.

Пример.

Решение.

Начальный этап

Положим

Градиент функции есть:

Матрица Гессе

Положим k=0

Основной этап

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

по критерию Сильвестра является положительно определенной. Действительно . Точка есть точка глобального минимума функции f(X).

Метод Левенберга — Марквардта.

Стратегия поиска. При использовании метода Ньютона или метода Ньютона-Рафсона вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить.

Для обеспечения положительной определенности матрицы Гессе в точ-ках последовательности используется метод Левенберга — Маркардта (метод Ньютона с регулировкой матрицы). В методе Левенберга — Маркардта точки строятся по закону:

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

то , в противном случае

Очевидно, что если , то метод Левенберга — Маркардта представляет собой метод Ньютона, а если велико, то поскольку при больших метод Левенберга — Маркардта близок к градиентному методу. Поэтому, подбирая значения параметра , можно добиться, чтобы метод Левенберга — Маркардта сходился.

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

Начальный этап

Задать , .

Найти градиент функции в произвольной точке

и матрицу Гессе H(x)

Положить .

Основной этап

Шаг 1. Вычислить

Шаг 2. Проверить выполнение критерия останова

а) если критерий выполнен, расчет окончен,

б) если критерий не выполнен, то перейти к шагу 3.

Шаг 3. Вычислить матрицу Гессе

Шаг 4. Вычислить

Шаг 5. Найти обратную матрицу

Шаг 6. Вычислить

Шаг 7. Найти

Шаг 8. Проверить выполнение условия :

а) если неравенство выполнено, то положить , k= k +1 и перейти к шагу 1;

б) если нет, то положить и перейти к шагу 4.

Пример.

Решение.

Начальный этап

Положим

Градиент функции есть:

Матрица Гессе

Положим

Основной этап

70