Общая задача нелинейного программирования. Метод Нъютона.
Как известно, общая задача математического программирования формулируется следующим образом: найти вектор
X=( x1, x2,........, xn)
удовлетворяющей системе ограничений
gi (x1, x2....., xn)=bi, i=1, 2, ..., k gi (x1, x2, . ...., xn)<bi, i=k+1, k+2, ..., m
и доставляющей, требуемый максимум или минимум функции
z=f(x1, x2, ....., xn)®min(max)
При этом предполагается, что известны функции
gi (x1, x2, ....., xn) и f(x1, x2, ....., xn)
Обычно на некоторые переменные x1, x2, ....., xn накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных. n Если gi (x1, x2, ....., xn)= å a ij,x j, i=1,2,.....m. (3) j=1 n и Z=f (x1, x2, ....., xn)= å cjxj, (4) j=1
где a ij,, cj -известные константы, то при условие неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования не удовлетворяющую условиям (3) и (4) условимся считать нелинейной. Если в задачах линейного программирования точка экстремума являют вершинами многогранников решений, то как следует в задачах с нелинейной целевой функцией они могут лежать внутри области, на ребре (грани) и в вершине многогранника. Требуется найти решение систем нелинейных алгебраических уравнений fi (х1 ,х2 ,...,хn)=0 ,i=1,2,3,...,n (1) Пусть известно решение системы (1) в к - ом шаге x1(k) ,x2(k),...,xn(k) необходимо найти (к+1) - ое приближенное решение x1(k+1) ,x2(k+1) ,...,xn(k+1) . Для решения данной задачи введем обозначения: Dxi(k) =xi -xi(k) или xi =xi(k)+Dxi(k) ,i=1,2, ... ,n. (2) Разлогая функцию fi(х1,,х2,,...,хn) по степеням Dxik в ряд Тейлора, притом ограничимся с первой производной Системы уравнений (3) можем написать таким образом:
Если написать в матричном виде (5)
Системы уравнений (5) решаем относительно , (i=1,n) и получим (6) Теперь обозначая для определения приближенного вычисления в (к+1)- шаге имеем формулу : (7)
Полученная система называется формулой Ньютона в матричном виде ,k=0,1,2,...,n.(8)
Здесь ,матрица Якоби или называется Якобианом. Для модифицированного метода Ньютона формула (8) имеет следующий вид: , k=0,1,2, . . .,n. (9) В модифицированном варианте метода Ньютона количество выполняемых арифметических операций намного меньшие чем самого метода Ньютона, так как в модифицированном варианте Якобиан вычисляется один раз, только для начального приближения.
Метод Ньютон для решения систем нелинейных алгебраических уравнений