МЕТОД НЬЮТОНА

Метод Ньютона, так же как и градиентные методы, относится к методам спуска, т. е. предназначен для численного решения задач безусловной минимизации. Метод Ньютона основан на идее замены минимизируемой функции f (x) в окрестности точки x(к) квадратичной частью fk (x) ее разложения в ряд Тейлора ~к (x) = f (x(к)) + (f X x(к)),( x - x( к ^ +

+ ±((x - x<к))f'(x<к)),(x - x(k)

В методе Ньютона очередная точка x(к) в последовательности x(0),x(1),x(2),...

приближений к точке минимума x* выбирается по правилу

x(к) = x(к-1) + h(к) = x(к-1) - f'(x(к-1))(f'(x(к-1)))-1, к = 1,2,...,

-1

где Л~ - матрица, обратная матрице A.

Таким образом, метод Ньютона является методом второго порядка.

На практическом занятии рассматриваются два способа обращения невырожденной квадратной матрицы Л

ап аи...а1п

а21 а22 .. а2п

а а .. а

п1 п 2 пп

Первый способ заключается в непосредственном вычисле-

-1

нии Л из соотношения

Л11 Л21 .. Лп1

Л Л ... Л

12 22 п2

Л1п Л2п ..Лп

где d = |A| - определитель матрицы A ,

Ajj = (-1)+]М„ - алгебраическое дополнение элемента aij, М„

минор элемента aij- . Второй способ обращения матрицы A состоит в том, что сначала к матрице A справа присоединяется единичная матрица I того же размера. Затем с помощью элементарных операций над строками (умножение строки на произвольное отличное от нуля число; прибавление к одной строке другой строки, умноженной на некоторое число) матрица D0 = [AI] преобразуется к матрице

Dn ф"1 ] .

Пример. Найти матрицу A 1, обратную матрице A вида

3 -1 0 - 2 1 1 2 -1 4

Решение.

Первый способ

Вычисляем d и Ay, i = 1,3, j = 1,3 :

d = 3 • 1 • 4 + (-1)1 • 2 + (-2)(-1)0 - 0 -1 • 2 - (-2)(-1)4 - (-1)1 • 3

= 12 - 2 - 8 + 3 = 5; = 1.

= -3, A33 = (-1)

= -1, A3, = (-1)

A3: = (-1)

5

6

4

= 1,

= 12, A23 = (-1)

= 4, A22 = (-1)

A21 = (-1)

5

4

3

= 0,

= 10, Aj3 = (-1)'

= 5, A12 = (-1)3

A„ = (-1)2

-2 1 2 -1 3 -1 2 -1 3 -1 -2 1

1 1 1 4 1 0 -1 4 -1 0 1 1

-2 1

4

0

4

0 -2 1

Таким образом, Г Л11 Л21 Л31 1 4 1" d d d 5 5 4"1 = Л12 Л22 Л32 2 12 3 d d d 5 5 Л13 Л 23 Л33 o 1 1 d d d 5 5 3 -1 o U o o" ¦2 11 !0 1 0

Второй способ Записываем матрицу Do :

Do = [Л1 ] = 2 -1 4|0 0 1

Для преобразования первого столбца D0 к виду (100)г умножаем первую строку D0 на 1/3; прибавляем ко второй строке D0 первую строку D0, умноженную на 2/3; прибавляем к третьей строке D0 первую строку D0 , умноженную на (-2/3), т.е.

1 2 2

= — • 1 2 = 2 + 1 3 = 3 1

3 *o> zi 0^3 *o> Ji Jo 3 o'

А -1 1 1 o o o -3 3 1 2 o 1 1 o 3 3 -1 -2 o 4 o 1 -3 -3 Для преобразования второго столбца D1 к виду (o1o)r прибавляем к первой строке D1 вторую строку D1; умножаем

где через ij обозначена i-я строка матрицы Dj . В результате получаем матрицу D1:

вторую строку D1 на 3; прибавляем к третьей строке D1 вторую строку D1, т.е. 2 = 3 • 2

2

32 = 31 + 21

12 = 11 + 21, В результате получаем матрицу D2: Г 1 o 1 1 1 o" D2 = o 1 3 2 3 o o o 5 o 1 1 Для преобразования третьего столбца D2 к виду (oo1) прибавляем к первой строке D2 третью строку D2 , умноженную на (-1/5); прибавляем ко второй строке D2 третью строку D2, умноженную на (-3/5); умножаем третью строку D2 на 1/5, т.е.

2

•3

13

¦2 -3• 3 3

Л2 5 J2> J3

¦1 -1 • 3 2

2 5 J2> z3

В результате получаем матрицу D3 : D =
= [/Л -]. 4 1" 1 o o 1 5 5 o 1 o 2 12 3 5 5 1 1 o o 1 o 5 5 _ Таким образом, Л"1 =

1 1 4 5 2 12 5 1 o 5 Алгоритм решения задачи безусловной минимизации методом Ньютона заключается в следующем.

Задаются ? x(0) ; вычисляются f (x(0)), f'(x(0)),

f '(x(0)) ; полагается k = 1.

Вычисляется f"(x(k-1)) .

Определяется (f"( x(k-1)))-1.

x «

Вычисляются Ax(k) =-f'( x(k-1))(f(x(k-1)))-1,

+ Ax(k), f X x(k)), f X x(k))

= x(k-1)

5. Проверяется условие окончания вычислений

f X x(k))

Если оно выполняется, то полагается x* = x(k), f *= f (x(k)) и вычисления завершаются.

Если условие не выполняется, то полагается k = k +1 и осуществляется переход к п.2.

Метод Ньютона находит минимум квадратичной функции

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

Пример. Решить методом Ньютона задачу безусловной минимизации

f (x) = -2 x23 + x1x2 + 2 xj2 - x1 + 3x2 + 4 ^ min

при ? = 0,1, x(0) = (4,-1) . Решение. Находим f" (x) : df _ -1 f __ 3 2 3.

X2 I -1, _— х2 + х1 + 3;.

дх2

дх1 11 1 - 3х

д2 f 1 д2 f д2 f „

дх22

—Т _ 1, 1, —~ _ -3х2 ^ f (х)

дх? дх1дх2 Г 3 - 1" " 1,5 - o,5 - 1 1 - o,5 o,5 Первая итерация Вычисляем Ах(1): 11 13

1

f'( х(o)) Ах(1) _-(2; 5,5)

^ (f '( х(o))) -1

2

1,5 - o,5 o,5 o,5

-(o,25; 1,75) _ (-o,25; -1,75). Вторая итерация Вычисляем Ах^2) :

1

f '( х(1)) _[1 1 1 8,25

Ах(2) _-(o; - 4,59)

^ (f"( х(1)))-1 _

1,14 - o,138 - o,138 o,138

8,25 -1 1 1

7,25

(-o,633; o,633). Третья итерация Вычисляем Ах(3) :

1

f '(х(2)) _[1 1

— 1

1 6,35 Ах(3) _-(o; - o,6o5)

^ (f '(х(2))) -1 _

1,19 - o,187 - o,187 o,187

6,35 -1 1 1

5,35

_ (-o,113; o,113). Результаты вычислений заносим в табл. 7.1. Номер итер. Ах1 Дх2 х1 х2 f ( х) f

дх1 df

дх2 И1 0 4 -1 1,5 2 5,5 5,85 1 -0,250 -1,75 3,75 -2,75 -0,88 0 -4,59 4,59 2 -0,633 0,633 3,12 -2,12 -2,46 0 -0,61 0,61 3 -0,113 0,113 3,00 -2,00 -2,50 0 0 0 Поскольку условие окончания вычислений выполнено (f'(х(3)) = 0 < ? = 0,l), то вычисления завершаются.

В результате решения задачи безусловной минимизации получаем х* = х(3) = (3,00; - 2,00), f * = f (х(3)) = -2,50. Ответ: х * = (3,00; - 2,00), f * =-2,50.

<< | >>
Источник: Харчистов Б.Ф.. Методы оптимизации. 2004

Еще по теме МЕТОД НЬЮТОНА:

  1. МЕТОД НЬЮТОНА
  2. МЕТОД НЬЮТОНА-РАФСОНА
  3. 7. МЕТОД НЬЮТОНА
  4. 7. Метод Ньютона
  5. Методы спуска. Приближенное решение задач выпуклого программирования градиентным методом
  6. Кассовый метод или метод начисления
  7. Понятие об ЛГ-методе (методе искусственного базиса)
  8. Кассовый метод и метод начисления
  9. Методы отсечения. Метод Гомори
  10. 3. Анализ (обобщение статистического материала на основе средних, индексных, выборочных методов; метода рядов динамики; кор-реляционного анализа и корреляционно-регрессионного анализа)
  11. Тема 9. Формы и методы государственного управления (административно-правовые формы и методы осуществления публичного управления)
  12. Глава 1.4. Методы экономического анализа 1.4.1. Общая характеристика методов экономического анализа
  13. § 4. Порядок признания доходов и расходов при методе начисления и порядок определения доходов и расходов при кассовом методе
  14. Административно-правовые методы Понятие административно-правовых методов
  15. МЕТОД МАРКВАРДТА
  16. ГРАДИЕНТНЫЕ МЕТОДЫ