Мегаобучалка Главная | О нас | Обратная связь  


Методы второго порядка




Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

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

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

Стратегия поиска

Стратегия метода Ньютона [ Newton I. ] состоит в построении последова­тельности точек {х k}, k = 0,1,..., таких, что  k = 0,1,.... Точки последовательности вычисляются по правилу

                          (5)

где х0 задается пользователем; величина шага  определяется для каждого значения k по формуле

.                               (6)

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

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



2. Направление  определяется из необходимого условия экстремума пер­вого порядка:  Таким образом, при выполнении требования  последовательность является последовательностью точек минимумов квадратич­ных функций Fk , k = 0,1,... (рис. 8). Чтобы обеспечить выполнение требования , k = 0,1,..., даже в тех случаях, когда для каких-либо значений матрица Гессе  не окажется положительно определенной, рекомендуется для соответствующих значений k вычислить точку   по методу градиентного спуска  с выбором величины шага     из условия .

 

Рис. 8

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

Сходимость

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

,

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

,

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

Замечание 1. Сходимость метода Ньютона доказана лишь для сильно выпуклых функ­ций и для достаточно хорошего начального приближения, определяемого услови­ем , практическое использование которого крайне затруднено, так как по­стоянные l и L , как правило, неизвестны или требуют трудоемкого исследования для их определения. Поэтому при практическом использовании метода Ньютона следует:

а) анализировать матрицу Н(х k)на выполнение условия Н(х k) < 0  и заменять формулу  на формулу  в случае его невыполнения;

б) производить анализ точки х k с целью выяснения, является ли она най­денным приближением искомой точки х*.

Замечание 2. При решении задачи поиска безусловного максимума формула (6) не изменяется, так как в этом случае Н(х k ) < 0.




Читайте также:
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (119)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.01 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7