Практикум j практическое примщенше численных методов

/с — X

(x-x^k){x-x^k-^l)f{x^k,x^k-\х^к~²),
f
}{х^к,х^к \х^{к 2}) =
(x^{k 1},х^{к 2}) — f(x^k,x^k *)
_Tfc-2 _ -
р
2х^к+1 = х^к + х^к~¹


f{x^k,x^k~^l) ,
f(x^k, а;*^-1, ж*^-2) ’


(8.6)

азделенные разности первого и второго порядка соответственно. Решение задачи (8.5) приводит нас к следующей формуле для нового приближения для точки минимума
Для дифференцируемой функции }{х) строятся итерационные методы, осно­ванные на решении уравнения (необходимое условие минимума)
f\x) = 0. (8.7)
К
В итерационном методе Ньютона новое приближение для точки минимума " определяется в соответствии с формулой
/V)


_rk+1


к = 0,1,..


f"(x^kY
Различные модификации метода Ныотоиа рассматривались в главе ,


(8.8)

орень этого уравнения х* Е X является точкой минимума, если fⁿ(x) > 0 (достаточные условия минимума). Для приближенного решения нелинейного уравнения используются итерационные методы.
Минимизация функций многих переменных
Д
/'(*)


df


df . . df


df

ля функции многих переменных /(я), х = {х\,х₂\... ,&■„} определим вектор первых частных производных (градиент)
М
атрица вторых частных производный (гессиан) в точке х есть
Будем рассматривать задачу безусловной оптимизации (8.3). Пусть функция f(x) дифференцируема в точке локального минимума х = ж*, тогда (необхо­димые условия оптимальности)
/'00 = 0. (8.9)
Если функция f(x) дважды дифференцируема в точке х — х* и выполнено (8.9). Если матрица f"(x) положительно определена, т.е.
(f"{x*)y, у) >0, Чуф 0, (8.10)
тогда х* — точка локального минимума. Условия (8.9), (8.10) есть достаточ­ные условия оптимальности.
Для итерационных методов минимизации будем использовать обозначения
x^k+l = х^к + a_kh^k, к — 0,1,..., (8.11)
где h^k — вектор, который определяет направление (к+ 1)-го шага минимиза­ции, а коэффициент а_к — длину этого шага.
Вектор h задает направление убывания функции f(x) в точке х, если f(x + ah) < f(x) при достаточно малых а > 0. Если вектор h^k задает направление убывания функции f(x) в точке х^к, а а_к > 0 такое, что
f(x^k+1) < f(x^k),
то итерационный метод (8.11) называется методом спуска. В градиентном методе h^k = —/'(ж*), т.е.
х^к+1 = х^к - a_kf'(x^k), к = 0,1,... (8.12)
Особое внимание уделяется выбору итерационных параметров а_к, к = 0,1,. • • в методе (8.11). Их можно определять из условия
f(x^k + a_kh^k) = min f(x^k + ah^k),
a>0
т.е. из решения дополнительной одномерной задачи минимизации.
В вычислительной практике широко используется процедура дробления ша­га, когда параметр а уменьшается, например, в два раза, до тех пор пока не будет выполнено неравенство
}(х^к -\-ah^k) < f(x^k).
При применении метода Ньютона для решения системы нелинейных уравне­ний (8.9) получим
f
(8.13)

"(x^k)(x^k+1 - х^к) + f'(x^k) =0, к = 0,1,...
Он записывается в виде (8.11) при
а_к = 1, ft* = ~(f"(x^k))-^lf(x^k). (8.14)
Среди модификаций метода Ньютона отметим метод Ньютона с регулиров­кой шага, когда вместо (8.14) используется
a_fc > 0, h^k = -(f"(x^k))-¹f'(x^k).
В квазииыотоновских методах
h^k = -H_kf'{x%
где Hk — матрица, которая аппроксимирует матрицу (/"(z^fc))^-1.
Задачи условной минимизации
При минимизации функций с ограничениями широко используются подходы, которые аналогичны тем, которые разработаны для задач безусловной мини­мизации. Наиболее просто это реализуется при переходе от задачи условной минимизации к задаче минимизации без ограничений.
Рассмотрим задачу минимизации с ограничениями типа равенств:
f(x) —> min, g%{x) = 0, г = 1,2,... ,га. (8.15)
Эту задачу можно записать в общем виде (8.1), задав допустимое множество
X = {х е Rⁿ | Qi(x) = 0, г = 1,2,... ,га}.
При некоторых ограничениях задача условной минимизации (8.15) эквива­лентна задаче безусловной минимизации функции Лагранжа
т
Цх,у) = f{x) +J2yi9i(^X)’
i=1
где yi — неизвестные множители Лагранжа. Тем самым мы приходим к задаче минимизации функции п + т переменных.
Б
т.е. в (8.1)


f(x) —> min, gi{x) < 0, i = 1,2,...,rn, X = {x E Rⁿ | gi(x) <0, г = 1,2,... ,m}.


(8.16)

олее сложно перейти к задаче безусловной оптимизации при учете ограни­чений в виде неравенств. Рассмотрим, например, задачу
Вместо функции f(x) в методе штрафов минимизируется функция
Ф
(8.17)

(ж,е) = f(x) + ф(х,е),
где *ф(х,£) — штрафная функция, е > 0 — параметр штрафа. Выбор штрафа ной функции на допустимом множестве подчинен условиям
Ф{х,е)>0, Ф(х,£) —> 0, если е —> 0, х е X,
а вне допустимого множества —
ф(х,£) —> оо, если £ —> 0, х 0 X.
В качестве характерного примера приведем штрафную функцию для задачи условной минимизации (8.16):
1 т
ф(х,е) = -^[тах{0,&(а:)}]².
⁶ г=1
После этого рассматривается задача безусловной минимизации
Ф(ж,б) —> min, х е Rⁿ.
Помимо выбора штрафной функции в методах этого класс очень важен выбор величины параметра штрафа е.

3. 
   Упражнения
   

Упражнение 8.1 Напишите программу для нахооюдения минимума функ­ции одной переменной f(x) на интервале [а, Ь] методом золотого сечения. С ее помощью найдите минимум функции (х² — 6х + 12) (ж² + 6я + 12)^-1 на интервале [0,20].
Точка х¹ является точкой золотого сечения, если
Ъ — а х¹ — а х¹ — а b — х¹
Исходя из этого определения имеем
х¹ = а Н —(Ъ — а).
&
Аналогично для х² имеем
х¹ — а х² — а х² — а х¹ — х²
и поэтому
о 3 — у/Ъ. _ч
х² = а-\ ^—(Ь-а).
На основе сравнения значений функции /(;х) в этих точках проводится итера­ционное уточнение интервала, на котором функция имеет минимум. ЧисЛ° итераций п для достижения необходимой точности е в определении точки минимума определяется равенством
,, - „ \/5-1
\b-a\c =е, с= —-—.
]3 модуле golden функция golden() обеспечивает нахождение минимума функции одной переменной f(x) на интервале [а, Ь].
Модуль golden
import math as mt
def golden(f, a, b, tol=l.0e-10):
и и и
Golden section method for determining x that minimizes the scalar function f(x).
The minimum must be bracketed in (a,b).
и и и
cl = (mt.sqrt(5.) - 1.) / 2. c2 = 1. - cl
nit = int(mt.ceil(mt.log(tol / abs(b-a)) / mt.log(cl)))

• 
  First step
  

xl = cl*a + c2*b x2 = c2*a + cl*b fl = f(xl) f2 = f(x2)

• 
  Iteration
  

for i in range(nit): if fl > f2: a = xl xl = x2 fl = f2
x2 = c2*a + cl*b f 2 = f(x2) else:
b = x2 x2 = xl f 2 = fl
xl = cl*a + c2*b fl = f(xl) if fl < f2:
return xl,fl else:
return x2,f2


Рис. 8.1 График функции у = {х² - 6х + 12){х² + 6х + 12)~^х



Для оценки интервала, па котором функция f(x) достигает минимума, будем использовать график у = f(x). С учетом этого для нахождения минимума функции (х² - 6х + 12)(ж² + 6х + 12)^-1 используется следующая программа.
import пшпру as пр import matplotlib.pyplot as pit from golden import golden def f (x):
return (x**2 - 6.*x + 12.) / (x**2 + 6.*x + 12.) a = 0. b = 20.
x = np.linspace(a, b, 200)
у = f(x)
pit.plot(x, y)
pit.xlabel(’x’)
pit.grid(True)
pit. showO
xMin, fMin = golden(f, a, b)
_r^_nt ’xMin =’, xMin print ’fMin = \ fMin
IVXin - 3.46410163303 fjylin = 0.0717967697245
интервале [0,20] найдены одна точка минимума (см. рис. 8.1).
упражнение 8.2 Напишите программу для нахождения минимума функ­ции нескольких переменной f(x) градиентным методом при выборе ите­рационных параметров из минимума функции одной переменной, который находиться методом золотого сечения (модуль golden). Проиллюстрируйте работу программы при минимизации функции 10(г₂ — х\)² + (1 — .Ti)².
Б модуле grad функция grad О находиться минимум функции многих пере­менных при аналитическом задании ее градиента.
Ь г; Ш': ^^:i;: : j^;li-;
import numpy as np
import math as mt
from golden import golden
def grad(F, GradF, x, d=0.5, tol=l.e-10): и и и
Gradient method for determining vector x that minimizes the function F(x),
GradF(x) is function for grad(F), x is starting point.
и и и
# Line function along h def f(al):
return F(x + al*h) grO = - GradF(x) h = grO.copyO F0 = F (x) itMax = 500
for i in range(itMax):
# Minimization ID function
al, fMin = golden(f, 0, d)
x = x + al*h
FI = F(x)
grl = - GradF(x)
if (mt,sqrt(np.dot(grl,grl)) <= tol) or (abs(F0 - FI) < tol): return x, i+1 h = grl
grO = grl.copy()
FO = FI
print "Gradient method did not converge (500 iterations)"