Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

Стратегия метода Ньютона состоит в построении последовательности точек , таких, что Точки последовательности вычисляются по правилу

где - задается пользователем, а направление спуска определяется для каждого значения k по формуле

(8)

Выбор по формуле (8) гарантирует выполнение требования при условии, что . Формула (8) получена из следующих соображений:

1. Функция f (x) аппроксимируется в каждой точке последовательности квадратичной функцией

2. Направление определяется из необходимого условия экстремума первого порядка: Таким образом, при выполнении требования последовательность является последовательностью точек минимумов квадратичных функций (рис.5.1).

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

 

Рисунок 5.1.

Построение последовательности заканчивается в точке , для которой , где - заданное малое положительное число, или при (М – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , где -малое положительное число.

Утверждение: Пусть f(x) дважды непрерывно дифференцируемая сильно выпуклая функция с константой l>0 на и удовлетворяет условию

где L>0, а начальная точка такова, что , т.е.

,

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

Алгоритм:

Шаг 1. Задать , М – предельное число итераций. Найти градиент и матрицу Гессе .

Шаг 2. Положить k = 0.

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

Шаг 4. Проверить выполнение критерия окончания :

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

б) в противном случае перейти к шагу 5.

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

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

б) в противном случае перейти к шагу 6.

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

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

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

а) если , то перейти к шагу 9;

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

Шаг 9. Определить .

Шаг 10. Найти точку ,

положив =1, если ,

или выбрав из условия , если .

Шаг 11. Проверить выполнение условий

:

а) если оба условия выполнены при текущем значении k и k = k - 1, то расчет окончен, ;

б) в противном случае положить k = k + 1 и перейти к шагу 3.

 

Пример: Методом Ньютона найти локальный минимум функции

Решение:

1. Зададим , M: , , M =10.

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

2. Положим k = 0.

30. Вычислим : .

40. Проверим условие : .

50. Проверим условие : .

60. Вычислим : .

70. Вычислим : .

80. Проверим выполнение условия . Т.к. , то согласно критерию Сильвестра .

90. Определим .

100. Вычислим .

110. Проверим условия: :

.

Полагаем k = 1, переходим к шагу 3.

31. Вычислим : .

41. Проверим условие : .

Расчет окончен. Найдена точка .

Проанализируем полученную точку:

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

Решение задачи представлено на рисунке 5.2.

Рисунок 5.2.


Дата добавления: 2015-07-20; просмотров: 115 | Нарушение авторских прав


Читайте в этой же книге: Общие принципы методов поиска безусловного экстремума | Метод конфигураций (метод Хука - Дживса) | Метод деформируемого многогранника | Метод вращающихся координат (метод Розенброка) | Метод сопряженных направлений (метод Пауэлла) | Методы первого порядка | Метод градиентного спуска с постоянным шагом | Метод наискорейшего градиентного спуска (Метод Коши) | Метод Марквардта | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Метод Гаусса - Зейделя| Метод Ньютона - Рафсона

mybiblioteka.su - 2015-2024 год. (0.011 сек.)