Метод Ньютона в нелинейном программировании. Метод Ньютона. Сходимость метода Ньютона. Метод Ньютона в задачах на безусловный экстремум

 

 

Аннотация

Курсовая работа на тему: «Метод Ньютона в нелинейном программировании. Метод Ньютона. Сходимость метода Ньютона. Метод Ньютона в  задачах на безусловный экстремум».

Выполнила студентка первого  курса, группы БЭК-11ц Кулешова Галина Николаевна

Руководитель: Протасов Дмитрий Николаевич.

Работа представлена к  защите в 2013г.

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

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

Курсовая работа содержит 32 страницы.

 

 

 

 

 

 

 

 

 

 

 

 

Annotation

The term paper on the subject  “Newton’s method in nonlinear programming. Newton’s method. The convergence of Newton’s method. Newton’s method in problems on unconditional extremum”.

Written by the first-year student of group BEK-11ts Kuleshova Galina Nikolaevna

Head: Protasov Dmitriy Nikolaevich.

The work is presented to protection in 2013.

In its structure the work consists of introduction, four chapters, conclusion, list of the used sources. 

The purpose of this term paper is studying of Newton’s method and also the solution of 3 problems.

The term paper contains 32 pages.

 

 

 

 

 

 

 

 

 

 

 

Содержание

Введение………………………………………………………………………..  6

1. Задача 1. Метод Ньютона в нелинейном программировании.

Метод Ньютона. Сходимость метода Ньютона. Метод  Ньютона 

в задачах на безусловный  экстремум…………………….…………………..     7

2. Задача 2…………………………………………………………………..   17

3. Задача 3…………………………………………………………………..   21

4. Задача 4…………………………………………………………………..   26

Заключение………………………………………………….…………………   31

Список использованных источников…………………………………………  32

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

В настоящей  работе описаны базовые идеи метода Ньютона, сходимость метода, а так  же рассмотрение метода Ньютона в  задачах на безусловный экстремум.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Задача 1. Метод Ньютона в нелинейном программировании. Метод Ньютона. Сходимость метода Ньютона. Метод Ньютона в задачах на безусловный экстремум.

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

f(x)=0                                                        (1.1)

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

Пусть x_n – текущее приближение к корню x_r и Δx=x_r – x_n. Тогда можно записать следующее разложение функции f(x) в ряд Тейлора:

                      (1.2)

С учетом того, что f(x_r)=0, получим

                                  (1.3)

Выражение (1.3) представляет собой одну из форм записи уравнения (1.1). Она удобна тем, что находить приближенные решения, ограничиваясь конечным числом слагаемых в левой части (1.3). С учетом двух слогаемых находим приближение вида:

Если теперь точку  взять в качестве следующего за уточнения корня, то получим итерационную формулу метода Ньютона:

                                                      (1.4)

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

Геометрически интерпретируется как точка пересечения оси касательной к кривой y=f(x) в точке х_n (рис. 1.1).

 

Рис. 1.1 Метод  Ньютона

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

Это  разложение является более точным, так как  в нем используется некоторая точка , про которую известно лишь то, что она расположена между х и х_n. Положив в нем x=х_r, получим:

.

Разделим теперь это равенство на и преобразуем результат к виду:

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

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

Если функция f(x) сложна, то аналитическое дифференцирование сопряжено со значительными техническими трудностями. Еще большие проблемы возникают, когда f(x) вообще не задана аналитически. Одним из способов преодоления этих недостатков состоит в аппроксимации производной f’(x_n) конечными разночтями. f’(x_n) в формуле (1.4) заменяется приближенным выражением:

С системами  нелинейных уравнений при решении  физических задач приходится встречаться  не менее часто, чем с одним  нелинейным алгебраическим или трансцендентным  уравнением. Общая форма записи системы из n нелинейных  алгебраических или трансцендентных уравнений с n неизвестными имеет вид:

f₁(x₁,x₂,…,x_n)=0,

f₂(x₁,x₂,…,x_n)=0,

……………………                                         (1.5)

f_n(x₁,x₂,…,x_n)=0.

В основе метода Ньютона для систем уравнений лежит представление левых частей всех уравнений системы (1.5) рядами Тейлора. Пусть - текущее приближение корня Х=(Х₁,Х₂,…,Х_n)^T и Δх=Х-х^(k). Тогда можно записать следующее покомпонентное разложение функции f(X) в ряды Тейлора:

Здесь все производные  вычисляются в точке х^(k). С учетом того, что f(X)=0, получим систему уравнений, эквивалентную системе (1.5):

         (1.6)        

Если теперь в левых частях уравнений (1.6) оставить лишь слагаемые, содержащие нулевую и первую степени приращений Δx_i, то исходную нелинейную задачу удается свести к решению системы линейных уравнений вида:

                                    (1.7)

В этой системе  все функции и их производные вычисляются в точке х^(k). Так как полученная система линейных уравнений не является точной, то результат ее рушения не дает корень исходной нелинейной системы(1.5), а может лишь использоваться для расчета нового приближенного значения корня:

 i=1,2,…,n.                               (1.8)

Итерационный  процесс, определяемый формулами (1.8), в которых приращение Δх_i вычисляются путем решения системы линейных уравнений (1.7), представляет собой алгоритм метода Ньютона для системы нелинейных уравнений (1.5). Когда модули всех корректирующих приращений Δх_i становятся достаточно малыми: итерации прекращаются. Если абсолютные величины корней Х₁,Х₂,…,Х_n значительно отличаются друг от друга, то для прекращения счета следует пользоваться нормированными корректирующими приращениями.

Систему уравнений (1.7) можно записать в векторно-матричной  форме:

J(x^(k))Δx=-f(x^(k))                                         (1.9)

Формальная  запись решения системы (1.9) имеет вид: Δх=-J(x^(k))^-1f(x^(k), где J^-1 – матрица, обратная матрице Якоби. Если воспользоваться этим выражением, то итерационные формулы (1.8) можно записать как:

x^(k+1)= =x^(k)-J(x^(k))^-1f(x^(k).                                (1.10)

При n=2 система (1.7) имеет простое аналитическое решение с небольшим числом арифметических операций. Весьма распространена задача о нахождении комплексных корней нелинейного уравнения F(z)=0. Действительно, если ввести в рассмотрение функции f₁(x₁,x₂)=Re(F(x₁+jx₂)) и f₂(x₁,x₂)=Im(F(x₁+jx₂)), то вещественная часть x₁ и мнимая часть x₂ комплексного корня z находятся из ситемы уравнений: f₁(x₁,x₂)=0, f₂(x₁,x₂)=0.

Будем предполагать, что  для данной системы определитель матрицы Якоби отличен от нуля на каждой итерации:

Тогда система  имеет решение:

Теперь формулы  итераций (1.8) можно записать в явном  виде:

                             (1.11)

Все функции  и их производные в правых частях этих формул вычисляются в точке .

При условии, что  в окрестности корня вектор-функция f(x)  дважды непрерывна дифференцируема по всем аргументам и матрица J невырождена, многомерный метод Ньютона сходится квадратично:

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

Процесс сходимости итераций метода Ньютона от начального приближения x⁽⁰⁾=(2,2) к корню Х=(1,1) системы уравнений:

                                       (1.12)

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

 

 

Таблица 1.1

k
0	2.000000000	2.000000000	1.414213562	-
1	1.693548387	0.890322581	0.702167004	0.351
2	1.394511613	0.750180529	0.466957365	0.947
3	1.192344147	0.822840986	0.261498732	1.199
4	1.077447418	0.918968807	0.112089950	1.639
5	1.022252471	0.976124950	0.02637256	2.598
6	1.002942200	0.996839728	4.317853366Е-3	4.054
7	1.000065121	0.999930102	9.553233627Е-5	5.124
8	1.000000033	0.999999964	4.871185259Е-8	5.337
9	1.000000000	1.000000000	1.272646866Е-14	5.363

 

Как видно, итерации сходятся довольно быстро – результат с  семью верными цифрами после  десятичной точки толучается после  восьми итераций. Данные пятого столбца  таблицы 1.1 подтверждают положение о квадратичной сходимости метода. Правда, зависимость справедлива в довольно малой окрестности корня, а константа С достаточно велика: С ≈5,4.

Если производные  в матрице Якоби трудно или  невозможно задать аналитически, то это будет серьезным препятствием в использовании метода Ньютона. В таком случае можно попытаться аппроксимировать частные производные конечными разностями, используя приближения, полученные на предыдущих итерациях.