20. Метод Ньютона-Рафсона.

Метод предназначен для реш-я СНЛУ: g₁(x^→)=0, g₂(x^→)=0,….,g_n(x^→)=0,(1), в кот.число уравнений = числу неизвестных. Этот метод явл.методом 1-го пор. В частности этот метод м.б.применен при поиске стац.точек целевой ф-и, когда необх решить сист.ур-ний, задаваемую соотн-ем: ▼f(х^→)=0. Обосн-е метода: В основе метода лежит ф-ла Тейлора. Пусть точка у^→ реш-е с-мы (1), а точ.х^→ расположена недалеко от у^→. Тогда, разлагая каждую ф-ю g_i(х^→) по ф-ле Тейлора в точ.х^→ с точностью до производных 1-го порядка по ф-ле Тейлора имеют след. Соотн-е : g_i(y^→)~g_i(x^→)+∑ⁿ_j=1((dg_i(x^→)\dx_j))(y_j-x_j),i=1,n, (2). Т.к. g_i(y^→)=0 для каждой i=1,n, то из соотнош.(2) можем получить след.соотнош.: g^→(x^→)+R_g→-(x^→)(y^→-x^→)=0,(3), где R_g→ -это матрица Якоби ф-ции g₁(x^→ )

g^→(x^→)= g₂(x^→)

…..

g_n(x^→), компонентами кот.явл.ф-ции исходной с-мы ур-й. Предполож, м-ца Якоби R_g→ в точке х^→ не вырождена, т.е.имеет нулевой опред-ль. Это означ-, что у неё есть обратная м-ца R_g→^-1(х^→).

Умножая соотн-е (3) слева на R_g→^-1(х^→), получ- соотн., кот.лежит в основе алгоритма Ньютона-Рафсона: y^→~x^→-R^-1_g(x^→)g^→(x^→),(4). Описание алгоритма:

Итерация 0. Выбир-ся точ.начального приближения х^→(0), точность решения ε>0.

Итерация к.

(а) производится вычисления R_g→^-1(х^→(к)).

(б)вычисляется приближение х^→(к+1)=х^→(к)- R_g→^-1(х^→(к))g^→(x^→(k)), (5), кот.явл.следствием (4).

(в)производится проверка условия: |х^→(к+1)-х^→(к)|<ε, если проверка выполнена, то алгоритм завершается, т.е.х^→*=х^→(к+1).

19. Метод Ньютона.

предназн для поиска экстремума целевой ф-ции. Он явл.методом 2-го уровня. В основе метода лежит метод Ньютона-Рафсона и тот факт, что м-ца Якоби R_▼f градиента ф-ций явл.м-цей Гессе этой ф-ции.

Т.к.экстремум находится в стац.точке, то для его опред-я необх найти эту точку, решив с-му ур-ний,опред соотнош-м: ▼f (х^→)=0. это можно сделать методом Ньютона –Рафсона. Описание метода:

Итерация 0. точ.начального приближения х^→(0), точность реш-я ε>0.

Итерация к.

(а)выч-ся м-ца Гессе Н(х^→(к)) целевой ф-ции f(х^→) в тчо.х^→(к) и нах-ся обратная м-ца Н^-1(х^→(к)).

(б)выч-ся очередное приближение: х^→(к+1)= х^→(к)-Н^-1(х^→(к))▼f(х^→(к)), (1).

(в)проверяется усл-е: |х^→(к+1)-х^→(к)|<ε,если это усл-е выполнено, то стац.точ.найдена, т.е.х*^→=х^→(к+1).

(г)выясняется тип опред-ти м-цы Гессе в найденной стац.точ. Н(х^→*). И делается вывод о типе экстремума.

З. как правило сходимость численных методов зависит от выбора. Это особенно важно, когда исходная целевые ф-ции имеют несколько экстремумов и начальное приближение д.б.близко к нужному.

21. Динамическое программирование(Дин.П.)

Дин.П.-совок. моделей и методов оптимизации сложных операций путем их разложений на сов-ти более простых операций.

Постановка задачи Дин.П.

Предполож, что некот. операция над некот. С-мой пред. собой совок. из n более простых операций.На к-ом шаге происх переход с-мы из состояния Sk-1 в состояние Sk под возд-ем «упр-я» x_k.Начальное сост-е S₀ и конечное сост-е S_n с-мы заданы.

Треб-ся найти такое оптим упр-е X^*=(x^*_1,x^*_2,…,x^*_n) всей многошаговй операции в целом,т.е.решить задачу:

W=F(S₀,X)→_X€D max, (1).

Где F(S₀,X)-показатель эфф-ти (целевая ф-я ) задачи Дин.П.