Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
МЕТОД НЬЮТОНА |
|
|
Метод Ньютона, так же как и градиентные методы, относится к методам спуска, т. е. предназначен для численного решения задач безусловной минимизации. Метод Ньютона основан на идее замены минимизируемой функции 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. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "МЕТОД НЬЮТОНА" |
|
|