Метод Ньютона минимизации функции многих переменных

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

2014-07-08

47.99 KB

68 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Лекция №7

Метод Ньютона минимизации функции многих переменных

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

Опишем метод Ньютона для задачи

,

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

Отсюда видно, что поведение функции с точностью до величин порядка  описывается квадратичной функцией

 (7.1)

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

                    (7.2)

Пусть матрица Гессе  положительно определена при всех , следовательно, невырождена ). Тогда существует обратная матрица . Отметим, что квадратичная функция с положительно определенной матрицей  сильно выпукла и уравнение (7.2) определяет единственную точку глобального минимума функции . Умножим слева обе части равенства (7.2) на матрицу  и найдем точку минимума  квадратичной функции (7.1), аппроксимирующей  в окрестности точки :

             (7.3)

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

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

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

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

Отметим, что даже сходящаяся последовательность  метода Ньютона не всегда обеспечивает монотонное убывание , т.е. неравенство  для некоторых  может нарушаться. Этот недостаток устранен в обобщенном методе Ньютона:

,

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

Недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации.

Пример 7.1. Методом Ньютона решить задачу

,

Градиент , матрица Гессе

Найдем обратную матрицу . С помощью формулы (7.3) получаем  Так как , то задача решена: . Целевая функция квадратична, поэтому решение задачи получено за одну итерацию.

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

Теорема 7.1. Если  - дважды непрерывно дифференцируемая функция, удовлетворяющая условиям

                      (7.4)

при любых  и в методе ,  выбирается из условия

,                          (7.5)

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

Д о к а з а т е л ь с т в о. Если

,

то по теореме о среднем с учетом условия (7.4) получаем

Следовательно,

Воспользуемся выражением . Умножая это равенство слева на матрицу , получим , следовательно, . Тогда, умножая скалярно обе части последнего равенства на  получим .

Далее в силу (7.4) имеем

и, следовательно, .

Нетрудно видеть, что неравенство (7.5) будет обязательно выполняться, если , т.е. если . Тем самым показана обоснованность выбора  из условия (7.5). Так как  при , то из неравенства

                        (7.6)

следует, что  при любом . Отсюда с учетом ограниченности  снизу вытекает, что  при . Теперь из (7.6) нетрудно установить, что  при , а в силу того что

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

Контрольные вопросы

1. К методам какого порядка относится метод Ньютона минимизации функции многих переменных?

2. Дайте определение матрицы Гессе.

3. Что лежит в основе метода Ньютона минимизации функции многих переменных?

4. Опишите метод Ньютона минимизации функции многих переменных?

5. Какой итерационный процесс лежит в основе метода Ньютона минимизации функции многих переменных?

6. Что можно сказать о сходимости минимизирующей последовательности , построенной с помощью метода Ньютона для сильно выпуклой дважды дифференцируемой функции ?

7. В каких случаях последовательность , построенная с помощью метода Ньютона, может расходиться?

8. Опишите обобщенный метод Ньютона минимизации функции многих переменных?

9. Перечислите достоинства и недостатки метода Ньютона минимизации функции многих переменных

PAGE  78



 

Другие похожие работы, которые могут вас заинтересовать.
8631. Дифференциальное исчисление функции нескольких переменных 77.12 KB
  Дифференциальное исчисление функции нескольких переменных План. Неявные функции условия их существования. Формула Тейлора для функции нескольких переменных. Производная функции по направлению.
8732. ВЫЧИСЛИМЫЕ ФУНКЦИИ И ОПЕРАЦИИ СУПЕРПОЗИЦИИ, ПРИМИТИВНОЙ РЕКУРСИИ И МИНИМИЗАЦИИ. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА 77.59 KB
  Формальное определение алгоритма Лекция 34. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА План лекции: 1. Формальное определение алгоритма. Формальное определение алгоритма Определение.
7035. Экономическая теория: предмет, метод, функции 26.65 KB
  Предмет экономической теории. Функции экономической науки. Предмет экономической теории. Несмотря на неадекватное отражение теоретические модели полезны с позиций описания общей экономической картины выявления главных факторов получения приближенных представлений ориентиров.
21682. Предмет, метод, задачи и функции гражданского права 35.25 KB
  Важно знать так же предмет и метод гражданского права, принципы и систему. Предмет регулирует как имущественные, так и лично неимущественные отношения. Метод правового регулирования представляет собой комплекс правовых средств и способов воздействия соответствующей отрасли права на общественные отношения, составляющие ее предмет. Для того чтобы такое воздействие было эффективным, т. е. достигало результата, на который оно рассчитано, должны быть использованы средства, соответствующие природе регулируемых отношений.
7662. ПРЕДМЕТ, МЕТОД И ФУНКЦИИ ПРАВА СОЦИАЛЬНОГО ОБЕСПЕЧЕНИЯ, ЕГО ВЗАИМОДЕЙСТВИЕ С ДРУГИМИ ОТРАСЛЯМИ ПРАВА 37.72 KB
  Право на социального обеспечения закреплено в ст. В современный период право социального обеспечения динамично развивается на основе новых концепций и принципов охватывает области отношений которые ранее находились за рамками правовой регламентации. Государство создает систему социального обеспечения участвует в финансировании пенсий пособий компенсаций медицинских и других социальных услуг.
10899. Понятие и предмет гражданского права. Метод гражданско-правового регулирования. Принципы и функции гражданского права 28.68 KB
  Принципы и функции гражданского права. Понятие частного права. Гражданское право как отрасль права как наука как учебная дисциплина.
9173. Механика и методология Ньютона 17.2 KB
  Одним из первых, кто задумался о сущности движения, был Аристотель. Аристотель определяет движение как изменение положения тела в пространстве. Пространство, по Аристотелю, целиком заполнено материей, неким подобием эфира или прозрачной, как воздух субстанцией. Пустоты в природе нет («природа боится пустоты»).
7986. Математика переменных величин. Дифференциальное и интегральное исчисления 21.46 KB
  Такие задачи были в то время трех видов: определение касательных к кривым нахождение максимумов и минимумов функций и отыскание условий существования у алгебраических уравнений кратных корней. В частном виде в этой задаче речь идет о нахождении первообразных функций. В более сложных случаях Ньютон прибегал к представлению функций степенными рядами и к оперированию с этими рядами.
22. Интерполирование функций полинома методом Ньютона 215.52 KB
  Освоить методы алгоритмизации и программирования двух форм представления интерполяционного полинома: полиномов Лагранжа и Ньютона с равномерным расположением узлов интерполирования.3 Исследовать зависимость ошибки интерполирования функции от количества и расположения узлов интерполирования Лагранжа и Ньютона. ВЫВОД В результате выполнения данной работы были изучены методы алгоритмизации и программирования интерполяционного полинома Ньютона с равномерным расположением узлов интерполирования и исследована зависимость ошибки интерполирования....
1726. Вычисление корней нелинейных уравнений методом Ньютона 123.78 KB
  Целью данной курсовой работы является изучение и реализация в программном продукте решения нелинейных уравнений при помощи метода Ньютона. Первый раздел теоретический и содержит общие сведения о методе Ньютона.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.