7. Выбор коэф-та в методе итераций.

Нужно учитывать, что в ур-и x=(x), (x) должно удовл-ть условию |’(x)|<1. Этого можно доб-ся, например, таким способом: Рассм-м ур-е f(x)=0 это ур-е равносильно x=x-f(x) отсюда (x)=x-f(x), где - выб-ся таким образом чтобы 0<=1-f’(x)<=q<1 По условию задачи m1<=f’(x)<=M1 на [a,b] то =1/М1 q=1-m1/M1<1

Метод итерации решения нелинейных систем второго порядка.

/ F1(x,y)=0

\ F2(x,y)=0

(x,y) – решение системы

При локализации корня граф-м способом удобно эти значения принять за нулевое приближение (x0,y0). Из первого ур-я явно выразим х

запишем итерац-й процесс

/ x=1(x,y)

\ y=2(x,y)

/ x1=1(x0,y0) / x2=1(x1,y1) / xn=1(xn-1,yn-1)

\ y1=2(x0,y0) \ y2=2(x1,y1) \ yn=2(xn-1,yn-1)

Если limn-xn=x*; limn-yn=y* => решение исх-й сис-mы Теорема: Пусть в замкнутой окрестности R={a<=x<=A, b<=y<=B} имеется только одна пара корней

1) Если ф-ии 1(x,y), 2(x,y) определены и непрерывно диф-мы в R

2)Начальное приближение (x0,y0) и последующие (xn,yn) принад-т R

3) В R выполнено |1/x|+|2/y|<=q1<1 |1/y|+|2/x|<=q2<1

то процесс сх-ся.

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

f(c чер.)(x)=0 f1(x1..xn)=0, fn(x1..xn)=0 предпол. что Xp(c чер.)=(X1p,…Xnp) найдено 1-ого из корней, тогда этот корень X=Xp(c чер.)+E(c чер.)p, где E(c чер.)p=(E1p…Enp). E-погрешн. f(x)= f(a)+ f ^‘ (a)(x-a). Выпиш. это ур-ие в разв. виде fn(…Xnp+Enp)=fn(…Xnp)+f ^‘ n(X1)*(…Xnp)*E1p+…

+f ^‘n(Xn)*(X1p…Xnp)*Enp. т.о f ^‘(х)=W(X)=(матрица)( 1) f ^‘1(Х1)… f ^‘1Хn 2) f ^‘nX1… f ^‘nXn)- Якобиан

Исход. сист. можно зап. в виде f(Xp)+W(Xp)Ep=0; Ep=-W(Xp)f(Xp). Итерац. процесс X(p+1)=Xp-W^–1 (Xp)f(Xp). Теорема: пусть Х0-нач. приближ. причем вып. условия 1) W(X)-якобиан имеет обр. матр. Г0= W^-1(x0), ||Г0||<=A 2)норма ||Г0f(x0)||<=B 3) сумма|δ² fi/δXiδXj|<=C 4)множитель μ0=2nABC<1 . При выпол. этих услов. процесс сходится. X(p+1)=Xp-W^-1(Xp)f(Xp).

Модиф. метод Ньютона.

На каждом шаге процесса Ньют. приход. обращать матрицу. Предпол. что W^-1(Xp)(примерно =) W^-1(x0). Тогда X(p+1)=Xp- W^-1(x0)f(Xp)-эта ф-ла в точности совпад. с фор-лой метода прост. итерации.Теорема: при выполн. услов. 1) W(X)-якобиан имеет обр. матр. Г0= W^-1(x0), ||Г0||<=A 2)норма ||Г0f(x0)||<=B 3) сумма|δ² fi/δXiδXj|<=C 4)множитель μ0=2nABC<1 , модиф. метод Ньютона сход. к решению системы.

9. Метод скорейшего спуска (градиента).

Рассм. систему f(с чер.)(x)=0 f1(x1…xn)=0 fn(x1…xn)=0 (1)

Пусть все ф-ции непрер. и диффер. Расм. ф-цию U(x)=(f(c чер.)(ч),f(x))=сумма(от i=1 до n)(fi(x))² (2). Очевидно, что решен. сист.1 будут решениями 2, и наоборот.Поэт. решать будем (2), и реш. будет (.) миним. сист.(2). Х0-0-ое приближение.Из (.) х0 двигаемся по нормали к пов-ти U(X0) до тех пор, пока эта нормаль не коснется в некот. (.) х1, друг. пов-ти ур-ия.Двигаясь по градиентам, придем в(.) миним. ф-ции U(x). Эта (.) и будет решением. ▲=Ом1м2: Х1=Х0-λ0▼U(x0) где λ0-коэфициент. В общем виде

x(p+1)=xp-λp▼U(xp).Для нахожд. λ рассм. ф-цию Ф(λ)=Ф(хp-λp▼U(xp))-это ур-ие задает

изменение ур-ня градиента, необх. решен. нах. в (.) мин. Т.е. λ-нужно подобр. так, что dФ(λ)/dλ=0.В рез-те вывода μp=2λp=(f_P,W_P W^T_P f ^P)/( W_P W^T_P f ^P, W_P W^T_P f ^P ); X(i+1)=Xi- W_P W^T_P f ^P.Метод скорейшего спуска для линейных систем. f=Ax-b; W=δf/δx=(матрица)(a11, a12,…a1n; an1…ann); X(p+1)=Xp-μA^Tr^P, где r-невязка=Ax(p)-b; μ=(r^P-A^TAr^P )/( A^TAr^P, A^TAr^P).