Вычмат-superpatch

1.Метод простой итерации. Решим сист. Ах=В (1) А= х= В= пусть аij нерав. 0 Х1=β1+£12Х2+£12Х3+…+£1nХn, Хn= βn+£n1Х1+£n2Х2+…+£nn-1An-1 где βi=вi/Aii £ij=Aij/Aii £ii=0 £= β= X= тогда сист.(1)прив. к сист.(2) Х=β+£х вид(2) наз.методом последов. приближений. За 0-е приближение столбец свобод. членов Х^0=β, тогда Х^1=β+£ Х^0 –перв. прибл.Если посл-ть х0,х2… имеет предел, то этим пределом будет решение системы т.е. Х^i=βi+(от j=1 до n)£ij*Xj^(^K^-1). Дост. услов. сходим. 1) ∑(от i=1 до n)|Aij|<1 для люб.Y 2) ∑(от j=1 до n)|Aij|<1 для люб.i Следствие: для сист. метод итер. сходит. если все модули диагонал. коэффициентов для каждого Ур-ия >, суммы модулей всех остал. коэффиц.|Aii|<∑(iнеравно j)|Aij|.	2.Метод Зейделя. Здесь при вычисл. (К+1)-го приближен. неизвест. Хi учитыв. уже вычеслен. (К+1)-е приближен. х1,х2,… Хi=βi+(∑ отj=1 до n)£ij*xi^K Предпол. что К-е приближ. известны тогда (К+1) иммет вид Xn^(^K^+1)=βn+(∑ отj=1 до n-1)£niXj^(^K^+1)+£nnXn^(^K^).Дост. услов. 1) ∑(от i=1 до n)|Aij|<1 для люб.Y 2) ∑(от j=1 до n)|Aij|<1 для люб.i Следствие: для сист. метод итер. сходит. если все модули диагонал. коэффициентов для каждого Ур-ия >, суммы модулей всех остал. коэффиц. |Aii| < ∑(i≠j)|Aij|.
3.Достат. услов. сходим. итерац. процесса Теорема: процесс итерац. для системы сходится к единств. решению если какая либо норма матр. £<1 а^K=£х^(^K^-1)+β, ||£||<1 Д-во: постр. последов. приближен., таких, что X^K=(£^(^K^-1)+£^(^K^-2)+…+ £+E)β+£^KX^0Т.к. норма матр.<1,то норма £к→0, при к→бесконеч. E+£+£^2+…+£^K^-1=(∑ отn=0 до K-1) £n| ||£||<1 |=(E-£)^-1 X=lim(k→бескон)X^к=lim[ (£^(^K^-1)+£^(^K^-2)+…+ £+E)β+£^KX^0 ]=(E-£)^-1β Т.о. сходим. доказана.	4. Отделение корней. Может происход. аналитич. или графически. Дано: f(x)=0 x*-решение.Теорема если непр. ф-ция f(x) приним. знач-я разн. знаков , на отрезке [a,b] т.е. f(a)*f(b)<0 то внутри этого отр. содерж. по меньш. мере один корень ур-ия (рисун.).
5. Метод половин. деления. f(x)=0, xc[a,b] f(a)*f(b)<0 пусть a0=a, b0=b предпол. что [ai,bi] построен, причем f(ai)*f(bi)<0 т.е. X*c[ai,bi] найдем (.)(C)ai=(ai+bi)/2 Если f(ci)=0 то (ci) точное решен. Если f(ci)нерав.0 то либо 1)f(ai)*f(ai)<0 2) f(ci)*f(bi)<0 если 1), то a(i+1)=ai b(i+1)=ci, если 2),то a(i+1)=ci, b(i+1)=bi В любом сл. получ. интервал вдвое < исход. причем f(ai+1)*f(bi+1)<0 Все заканчив. либо 1) когда f(ci)=0 2) Ci-корень 3)(ai-bi)<E –выбир. любую (.) и приним. ее за решен. ОЦЕНКА точности. f(ai)*f(bi)<0; bn-an=1/2^n X(с чертой)-an<=1/2^n(b-a) k-кол-во шагов k=log2((b-a)/E)+1. Решение нелин. ур-ий . Решен. осущ. в 2 этапа 1) локализация корней , т.е. нахожд. промежутков [a,b] котор. принадл. корень ур-ия 2)уточнение корней ,т.е. решение с задан. точностью.	6. Метод хорд. f(x)=0, xc[a,b] f(a)*f(b)<0 Для определенности положем, f(a)<0 f(b)>0 (рис.) Поделим [a,b] в отношен. f(a):f(b) ; (x-a)/(b-a)=(y-f(a))/(f(b)-f(a)); Положем X=X1, y=0; X1=(-f(a)/(f(b)-f(a)))*(b-a)+a по этой ф-ле можно зап. итерац. процесс X1=a+h; h1=-f(a)/(f(b)-f(a)) Докаж. сходим. итер. процесса будем предпол., что корень f(x) определ. и f ^’ ’(x) сохр. знак. на [a,b] (рис.) Имеем 2 сл. f(a)>0 и f(a)<0 для a>0 ; X(n+1)=Xn-(f(Xn)/(f(Xn)-f(a)))*(Xn-a) ; для a<0 X(n+1)=Xn-(f(Xn)/(f(b)-f(Xn)))*(b-Xn) Т.е.1) неподвиж. тот конец , для котор. знак ф-ции совпад. со знаком втор. производ. 2)Послед. приближен. Xn лежат по ту сторон. X*, где ф-ция f(x) имеет знак противополож. знаку ее втор. произв. Критерий остановки |X*-Xn|c|X(n+1)-Xn|<E X(с чертой)=Xn+1.
7.Метод касательных (Ньютона). y-y0=f^‘(X)(X-X0) пусть f^‘(X), f^‘ ‘(X) –непрер. и сохр. опред. знаки на отрезке [a,b] пусть f^‘ ‘(X)>0 и f(b)>0 (рис.) Ур-ие касат. y-f(Xn)= f^‘(Xn)(X-Xn) y=0, X=Xn+1; X(n+1)=Xn-(f(Xn)/ f^‘(Xn)) Исходя из геом. соображен. , вывед. тоже самое аналитич. X*=Xn+hn Прим. ф-лу Тэйлора 0=f(Xn+ hn)=f(Xn)+ hnf^‘(Xn); hn =-f(Xn)/f^‘(Xn) Выбор начал. точки f(X0)*f^‘ ‘(X0)>0. Теорема: если f(a)*f(b)<0 причем втор. произв. сохр. знак на [a,b] , то исходя из любого начал. приближен. X0c[a,b] удовл. условию f(X0)* f^‘ ‘(X0)>0 можно вычисл. корень ур-ия с любой степенью точности. Д-во: пусть f(a)<0 , f(b)>0 f ^‘(x)>0; f^‘ ‘(x)>0(вогнута) т.е. f(b)* f^‘ ‘(b)>0 ; X0=b-max точка. X(n+1)=Xn-(f(Xn)/ f^‘(Xn))>X*.	8. Теорема о сходимости метода Ньютона. При примен. метода Ньютона за нач. (.) прин. тот конец интервала АВ, которому отвечает ордината того же знака , что и знак 2-ой производ. f(a)*f’’(x)>0.Теорема: если ф-ция вблизи корня имеет большую кривизну, то метод Ньютона очень быстро сходится к решению; если же это не так , т.е. ф-ция прямая, то примен. этого метода не рационально. Критерий остановки |Xn-X(n-1)|<E.
9.Видоизмененный метод Ньютона. X(n+1)=Xn-f(Xn)/ f^‘(Xn). Если произв. исход. ф-ции меняется мало на [a,b] то можно предпол. f(Xn)(примерно =)f(X0) X(n+1)=Xn-f(Xn)/ f^‘(X0) это дает воз-ть не вычисл. зн-е произв. в каждой (.). Т.е. здесь касат. замен. на прямую || 1-ой касательн.МЕТОД ХОРД И КАСАТ. (комбиниров. метод). f(x) опред. на [a,b] f(a)*f(b)<0 , произв. сохр. знаки на [a,b] .Получ. метод, на кажд. шаге котор. получ. приближение по недостатку и избытку, точного корня X* ур-ия f(x)=0. Возм. 4 сл. 1)(рис.) f ^‘(x)>0 f ^‘ ‘(x)>0 X0-d начал. условие. 2) f ^‘ ‘(x)<0, f ^‘(x)<0 (рис.) f(a)* f ^‘(x)>0 3)(рис.) f ^‘ ‘(x)>0, f ^‘(x)<0 f(a)>0 4) f ^‘ ‘(x)<0, f ^‘(x)<0- ф-ция убыв. будучи выпуклой (рис.) Все эти сл. легко свести к 1-ому f(x)=0 ; -f(x)=0 Или же можно запис. все ф-лы аналогич. 1-ому сл. 1) f ^‘(x)>0 (X0=a), f ^‘ ‘(x)>0(X0(с чертой)=b), X(n+1)= Xn-(f(Xn)/(f(Xn(С чер.))-f(Xn)))*(Xn(с чер.)-Xn)(для сл. хорд); X(n+1)(c чертой)=Xn(c чер.)-f(Xn(c чер.))/f ^‘(Xn(c чер.)) Критер. остановки Xn(с чер.)-Xn<E за рез-т берем среднее арифметич. X*(c чер.)=1/2*(Xn(с чер.)-Xn).	10.Метод итерации(последов. приближений) f(x)=0, заменим x=φ(x) зададим начал. приближ. Х0, Х1=φ(х0), Хn=φ(Xn-1). X*=limXn(n→∞) X*=φ(x)Геометр. интерприт.(рис.). Если φ(х) возр. то послед. приближен. строится лесницой, убыв.-то строится по спирали.Приближен. к точн. корню происх. при |φ ^‘(x)|<1. Если |φ ^‘(x)|>1 то мы уходим от корня(рис.) Итерац. процесс нельзя строить исходя из начал. условий.
11.Теорема о сходим. метода итерации. Пусть φ(х) опред. и диф. на [a,b] тогда, если сущ. дробь q такая |φ ^‘(x)|<=q<1 Тогда 1) процесс итерации А(n+1)=φ(Xn) сход. независ. от Х0.2) Предельн. знач-е явл. единств. корнем ур-ия LimXn=X*(n→бескон).Д-во: рассмотр. Хn=φ(X(n-1)); X(n+1)=φ(Xn); вычтем, по теорем. Лагранжа будем иметь a(n+1)-Xn=(Xn-X(n-1))*φ’(Xn( с чер.));|X(n+1)-Xn|<= q|Xn-X(n-1)|. Пусть n=1,2… Тогда.|X(n+1)-Xn|<=q^n|Xn-X0|. Рассмотр. ряд Х0+(Х1-Х0)+(Х2-Х1)+… для этого ряда посл-ти приближен. явл. (n+1)-ми частными суммами Т.е. Xn=S(n+1) В силу неравенств все члены ряда < соотв. членов геом. прогрессии .У котор. знаменат. <1 поэт. ряд сход. абсолютно. LimSn+1=LimXn=X*(n-бескон.)-единств. решение.X(n+1)=φ(Xn), X*. Итер. процесс сход. тем быстрее, чем |φ ^‘(x)|<1.	12.Оценка итер. процесса: |X*-Xn|<=q ^n/(1-q)*|X1-X0|. Рассм. как свести ур-ие к виду, удобн. для итерации. f(x)=0; x=x-λf(x)-ур-ие равносил. исходному. x-λf(x)=φ(x); [x=φ(x)];Пусть f ’(x) удовл. неравенству 0<m<f ‘(x)<M. Нужно подобр. такое λ чтоб |φ’(x)|=|1-λf ‘’(x)|<1;Т.к.рассматр. положит. знач-я, то модули можно снять. φ’(x)=1-λf ‘(x); 1-λM1<1-λm1<=q<1;Т.о. можно положить λ=1/M1 . Исходя из этого вычисл. q; q=1-m/M; Этот спос. удобен если извест. интервал, в котор. нах. точное знач-е корня. Если задан. Х0, то λ наход. из ур-ия 1-λf ^‘(X0)=0.
13=14.Метод итерации решения сист. 2-х ур-ий. F1(x,y)=0, F2(x,y)=0(рис.)Каждое ур. в системе может быть приведено к виду x=φ1(x,y) y=φ2(x,y) Если X0,y0-начал. приближен. то X1=φ1(X0,y0) Y1=φ2(x0,y0). Теорема пусть в нек. замкн. окр-ти R={a<=x<=A; b<=y<=B} имеется только 1 пара (.)-к x=X*, y=y*-1 пара решений. Если 1) x=φ1(x,y) y=φ2(x,y) ф-ции φ1(x,y) φ2(x,y) опред. и непрерыв. в R 2)начал. приближ. х0 и у0 и все последующ. не вых. за рамки R 3)||Ф||<1 (норма матр.), где Ф=матрица ( 1)δφ1(x,y)/δx; 2)δφ1(x,y)/δy 3)δφ2(x,y)/δx 4) δφ2(x,y)/δy) –матр. сост. из част. произв.То процесс итер. сход. в X*и y* Итер. процесс сход. медленно, т.к. норма невелика.Процесс итер. может быть запис. в виде X ^(^P^+1)=φ(X ^P)(X-с чертой).В общем виде сист. имеет вид f(x)=0(c чертой) тогда X(с чер)=X(чер.)+ λf(c чер.)(x(c чер.)) λ-не особ. матр.( ее опред. не =0) λ=-[f ^‘(x(c чер.)^0]^-1 . Х(с чер.)(к+1) =Х(к)+λ f (x(к)(c чер.)).Метод Зейделя –учит. уже вычисл. приближение. Пусть задан. начал. услов. х0; X1(к+1)= С11Х1(к) +С12Х2(к)+…+С1nXn(к)+d1; Х2(к+1)=С21Х1(к+1)+С22Х2(к)+…+С2nXn(к)+d2; и т.д.	15.Метод Ньютона. 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) сумма|δ^2fi/δXiδXj|<=C 4)множитель μ0=2nABC<1 . При выпол. этих услов. процесс сходится. X(p+1)=Xp-W^-1(Xp)f(Xp).
16.Модиф. метод Ньютона. На каждом шаге процесса Ньют. приход. обращать матрицу. Предпол. что 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) сумма|δ^2fi/δXiδXj|<=C 4)множитель μ0=2nABC<1 , модиф. метод Ньютона сход. к решению системы.	17. Метод скорейшего спуска (градиента). Рассм. систему f(с чер.)(x)=0 f1(x1…xn)=0 fn(x1…xn)=0 (1) Пусть все ф-ции непрер. и диффер. Расм. ф-цию U(x)=(f(c чер.)(ч),f(x))=сумма(от i=1 до n)(fi(x))^2 (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=(fP,WP W^TP f ^P)/( WP W^TP f ^P, WP W^TP f ^P); X(i+1)=Xi- WP W^TP 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).
18.Ф-ла ТРАПЕЦИИ. (рис.) ∫f(x)dx, h=(b-a)/n; Sтрапец.=(a+b)*h/2; S=(y0+y1)*h/2+…+(y(n-1)+yn)*h/2; S=(сумма от 1 до n)(y(i-1)+yi)*h/2=(интеграл от a до b)ydx; Формула трапеции h*(∑ от i=1 до n-1)(((y0+yn)/2)+yi).	19.Отаточный член ф-лы трапеций. (рис.) R=(интеграл от x0 до x1)ydx-h/2 *(y(x0)+y(x1)); R(h)=R(0)+(интегр. от 0 до h )(R’(h)dh=-1/12 *h^3y’’(C1), Cc(x0,x1);R=-1/12 * h^3y’’(C); -распространим этот рез-т на любое число звеньев, т.е. на весь промежут. [a,b].R=∑(от i=1до n)(интегр. от X(i-1) до xi) (ydx-h/2 *(y(i-1)+yi))=h^3/12(∑ от i=1 до n )y’’(Ci); Cic(X(i-1);Xi);Рассмотр. среднее арифметич. μ=(∑ от 1 до n)y’’(Ci)/n; Значение μ заключ. м-у наибол. и наименьш. знач-ями 2-ой производной на [a,b] m2<=μ<=M2. А т.к. 2-ая производ. непрер. на [a,b] то она приним. все промежут. знач-я м-у M2 и м2; Т.е. μ=y’’(C)=(∑y’’(c))/n; R=-nh^3y’’(c)/12=-h^2(b-a)y’’(c)/12; Т.е. данная ф-ла явл. точной только для многочленов первого пор-ка. Иногда быв. неудобно вычисл. 2-ую произв. для вычисл. погрешн-ти, поэт. вычисл. интегр. с шагом h; Ih=∑h+Mh^2, где М-оценка (-(b-a)y’’(c))/12; Затем вычисл. I2h=∑2h+M4h^2; поэт. оценка может быть выраж. ф-лой R=(∑h- ∑2h)/3.
20.Формула СИМПСОНА (порабола). ∫f(x)dx (рис.). Число разбиен. должно быть четным, т.е. n=2m; h=(b-a)/n=(b-a)/2m;Через 3 (.)-ки будем провод. параболу y=A0+A1x+A2x^2; (x0,y0), (x1,y1), (x2,y2)-параб. прох. ч-з эти (.)-ки(x0, x0+h, x0+2h);-предпол. что x0=0, тогда получ. 0, h, 2h;Для нахожд. A0,A1,A2- подстав. эти (.)-ки в ур-ие параб. y0=A0; 2y1=2A0+2A1h+2A2h^2; y2=A0+2A1h+4A2h^2;Вычтем из 3-го 2-ое.A0=y0; A1=(-3y0+4y1-y2)/2h; A2=(y0-2y1+y2)/2h^2. Площадь 1-ого эл-та (интегр от 0 до 2h) (A0+A1x+A2x^2)=A02h+A1(4h^2)/2+A2h^38/3;Подставл. знач-я А0,А1,А2 получ. In=h/3*(y(n-2)+4y(n-1)+yn); Пусть y1+y3+…+y(2n-1)=δ(2n-1); y2+y4+…y(2n)=δ(2n); Формула Симпсона- (интегр от a до b)ydx= h/3* [y0+yn+4δ(2n-1)+2δ(2n)].	21. Остаточ. член ф-лы Симпсона. Оценка погрешности R=(инт. от X0 до X2)ydx-h/3(y0+4y1+y2);Продиф. ее 3 раза, R’’’(h)=(-2/3)*h^2y^IV(C3).Проинтегр. R=-h^5y^IV(c)/90 распростр. эту погреш. на весь промеж. a,b. R=-h^5/90 *(∑ от k=1 до m )y^IV(Ck);Ввиду непр-ти подинтегр. ф-ции можно сказ. что y^IV(с) явл. средним арифмет. всех знач-ий , отсюда R=-(b-a)h^4y^IV(c)/180; Шаг h=(корень 4-ой степени)180E/(b-a)M4, где M4=мах|y^IV(x)|.Если совпад. дост. кол-во знаков то это зрач-е счит. за значение интегр. Еще 1 спос. оценки – пусть у^IV(x) мен. медленно тогда R=Mh^4, где М будем счит. постоянной. Вычисл. знач-е интегр. с шагом h. I(h)=∑h+Mh^4; I(2h)=∑2h+M(2h)^4=∑2h+16Mh^4; Ошибка= R=(∑2h-∑h)/15; Тогда I= ∑h+(∑2h-∑h)/15; Вычисл. по ф-ле Симпсона удобно пров. с шагом делящ. на 4.
22.Диф. ур-ия. Метод Эйлера. (рис.) y’=f(x,y) y(x0)=y0-задача Коши. Разобьем ось х на промежут. Хi=x0+hi (рис.) В (.) M0-пров. касател. до пересеч. с прямой х=х1, соед. прямые. Получ. ломаную считаем решением y(i+1)=yi+hf(xi,yi)-ф-ла облад. малой точностью.(порядка h^2); y(xi+h)=y(xi)+y’(xi)h остал. члены разлож. в ряд Тэйлора (y(x)=y(x0)+y’(x0)(x-x0)+y’’(x0)(x-x0)^2/2!-поэт. точность порядка h^2.	23.Модифицированный метод Эйлера. (рис.) y’=f(x,y); y(x0)=y0; xi=x0+hi; Ч-з (.) (xi,yi) провод. касат. с tg угла наклона tg£1=f(xi,yi) до пересеч. с прямой xi+h/2; По Эйлеру вычисл. yi+1/2=yi+h/2(f(xi,yi)); Затем в (.) (xi+1/2; yi+1/2) вычисл. знач-е произв. f(i+1/2)=f(x(i+1/2), y(i+1/2)). Возвращ. в (.) (xi, yi) и из нее провод. прямую || 2-ой касательной. Касател. пров. до пересеч. с прямой x=x(i+1); Т.е. y(i+1)=yi+hf(i+1/2);-модиф. метод, y(x0)=y0; (Шагнули до x(i+1/2) вычислили направл. и из исход. (.) идем дальше). Метод Коши-Эйлера.(рис.) Ч-з (.) (xi,yi) провод. касательная до пересеч. с прямой x(i+1) и шаг по методу Эйлера. y(с чер.)(i+1)=yi+hfi. В получ. (.) найдем направление f(с чер.)(i+1)=f(x(i+1); y(с чер.) (i+1)). Возвращ. в исход. (.) и дел. шаг y(i+1)=(yi)+(h*(fi+f(с чер.)(i+1))/2)(Получаем какой-то угол и нах. сред. арифметич. , затем провод. касател. по этому углу.).
34.Метод Франка-Вульфа. Вычисл. град. целев. ф-ции ▼S(x1,x2); Шаг 0: в кач-ве нулев. итерации выбир. произвол. (.) обл-ти Д (х)0=(X1,…Xn)0; S0=S(x1…Xn)0; Шаг к: вычисл. ▼S(x)к рассм. вспом. ф-цию Sк(с чер.)=(▼S(x)к,х).Решим задач. лин. програм. Sк(с чер.)=(▼S(x)к,х)→max симплекс методом. Пусть (х)к(с чер.)-решен. След. прибл. (х)к+1 к решен. исход. задачи найдем по ф-ле (х)к+1=(х)к+ λ[(x)к(с чер.)-(х)к]; λ-найд из услов. λ=min{1,minS[(x)к+λ*((х)к(с чер.)-(х)к)]к+1}; Вычисл. S(x)к+1 и оценку |S(x)к-S(x)к+1|<E. Если она выполнена, то конец, если нет-перех. к след итерации.
24.Метод Рунге-Кутта. y’=f(x,y); y(x0)=y0; Разбив с шагом h ось Х; xi=x0+hi; yi=y(xi); Числа K^i1 = h* f(xi;yi); K^i2 = h* f(x(i+h/2);y(i+ K^i1/2)); K^i3 = h* f(x(i+h/2);y(i+ K^i2/2)); K^i4 = h* f(x(i+h);y(i+ K^i3)); Вычисляем y(i+1)=yi+▲yi; где ▲yi=1/6*( K^i1+2 K^i2+ 2K^i3+ K^i4); Погрешность этого метода на каждом шаге h^5; Эффективн. оценка этого метода затруднительна; Обычно на каждом этапе состоящ. из 2-х шагов делают 2-ой пересчет, с шагом h и 2h; Т.е. величину y(xi+2h) вычисл. 2-я способами: если расхождение не превыш. допустим. погрешности , то шаг можно увелич. в 2 раза. Если след. знач-я превосходят. допустим. погрешность, то шаг < в 2 раза	25.Метод наименьших квадратов. (матем. обработка данных).Пусть в рез-те исслед. некоторой величины Х знач-я Х1,Х2…Хn поставлены в соответствие др. знач-я …Xn→y1,y2…yn; Треб. подобрать вид аналитич. записи y=y(x) связыв. перемен. х и у; В задаче треб. найти некую прямую y=bx; Задача закл. в определен. пост. b; В методе наим. квадр. параметр b опред. из условий min суммы квадратов отклонений эксперим. данных yi от расчетных величин yi*; F=∑(от 1 до бесконеч.)(yi-bxi)^2→min; δF/δb =2∑((yi-bxi)*(-xi))=0; b=(∑xiyi)/(∑xi^2); В нек. случаях иском. прям. имеет вид y=a+bx; F=∑(yi-a-bxi)^2→min; δF/δb=2∑[(yi-a-bxi)(-xi)]; ∑(yixi-axi-bxi^2)=0; ∑yixi=∑(axi)+∑bxi^2; ∑xiyi=a∑xi+b∑xi^2; a= (∑yi-b∑xi)/n; n∑xiyi=∑xiyi-b(∑xi)^2+bn∑xi^2; b=(n∑xiyi-∑xi∑yi)/(n∑xi^2-(∑xi)^2).
26.Задан. задачи линейн.програмир. сведение одной формы к др. Каноническая: ∑(от j=1 до n)AijXj=bi; (i=1,m); Услов. неотрицат. Xj>=0, j=1,m; max Z; Стандартная: неравенства ∑(от j=1 до n)Aij<=bj (i=1,m); услов. неотр. Xj>=0; j=1,n; max Z или min Z; Общая: ур-ия и нерав. ∑(от j=1 до n)AijXj (<=;>=;=)bi (i=1,m); Xk>=0; k=1,e; max Z или min Z;пример Z=-2x1-x2+x3-2x4→min; 1) 2x1-x2+3x3+x4=4 2)x1+2x2+3x3+2x4=6; 3)3x1-x2-2x3+x4>=2; 4)5x1+3x2+x3<=6 5)2x1+x2-3x3-2x4<=4; Xi>=0; Привести к канон. форме –Z=2x1+x2-x3+2x4→max; (**)3x1-x2-2x3+x4=2; (*) 5x1+3x2+x3+x6=6; 2x1+x2-3x3-2x4+x7=4; Xi>=0; (1)Переход к неотр. Введем новые перемен. x3=x3’-x3’’; x4=x4’-x4’’;(x3’,x3’’,x4’,x4’’ >=0);Т.о. в исход. сист. будет 9 перемен. (2)способ перех. к неотр. Из ур-ия (*) выразим x3 x3=6-5x1-3x2-x6; и подстав. это выраж-е во все ур-ия и целев. ф-цию; после этого из 1-ого ур-ия (**) выразим х4; x4=-14-13x1+10x2+3x6; и также подстав. во все ур-ия; Тогда задач. имеет вид Z’=43x1+30x2+9x6-46 →max; 1)12x1+13x2+3x5=16; 2)13x1-10x2-3x6+x7=28; 3)-13x1-10x2-3x6+x7=6; Xi>=0; Задача свелась к канон ф.	27.Графич. решение ЗЛП.Рассм. линейн. ф-цию Z=C1x1+C2x2+…+CnXn→max; (целевая ф-ция); Max этой ф-ции нужно найти в обл-ти a11x1+a12x2+…+a1nXn<=b1; am1x1+…+AmnXn<=bn; Xn>=0; Целев. ф-ция явл. линейной ф-цией , сист. ограничений это линейные неравенства; Всякий вектор x= (x1,x2…xn) удовл. системе ограничен. наз. допустимым решением или план; Мн-во допуст. решений наз. обл-тью определения или допустимю обл-тью; Допустим. решен. на котор. целев. ф-ция достиг. своего max наз. оптимал. решением. Рассм. сл. когда задач. имеет 2 неизв. Прим. Z=4x1+2x2→max; 1)2x1+3x2<=18; 2) –x1+3x2<=9 3) 2x1-x2<=10; Xi>=0;(рис.) Строим эту обл-ть; Затем строим градиент целев. ф-ции (в дан. случае этот вектор имеет корд. 4;2), двигаясь перпендикулярно этому вектору придем в (.) max. x1=6; x2=2; Zmax=24+4=28;
28.Симплекс метод решен. ЗЛП. Пусть зад. линейно програмир. зад. в стандарт. форме на max; (c,x)→max; ax<=0; x>=0; a11x1+a12x2+…+a(1n)Xn+y1=b1; a(m1)x1+a(m2)x2+…+a(mn)Xn+ym=bm; ym>=0; y1=a11(-x1)+ a12(-x2)+…+a(1n)(-x)+b1; ym=a(m1)(-x1)+a(m2)(-x2)+…+a(mn)(-xn)+bm; Z=-C1(-x1)-…-Cn(-Xn);Задачи в канон. и прост. форм могут быть привед. к одному виду; Когда задач. привед. к такому виду ее можно занести в симплекс табл. (рис.) В послед. столбце все bi неотрицат. , иначе допустим. базисного реш. не сущ. Если в посл. строке нет ни одного отрицат. эл-та , то задач. решена . Пересчет табл. произв. след. образом 1) В послед. строке находим наиб. по модулю отрицат. число , сооотв. столбец наз. опорным (ведущ). 2)из всех строк с положит. эл-тами на пересеч. берем строку с наименьш. отношением свобод. члена. к соотв. эл-ту опор. столбца, соотв. строка опорная(ведущ). 3) меняем мест. неизвестные отвечающ. опорн. строке и столбцу. 4)разреш. эл-т замен. обратным числом 5) остал. эл-ты опорн. строки делим на разреш. эл-т. 6)остал. эл. опорн. столбца делим на разреш. эл. с противоп. знаком 7)остал. эл-ты табл. наход. по правилу прямоугол. (рис.) a(rs)-разреш. a’(ij)-новый. a’(ij)=(a(ij)a(rs)-a(rs)a(is))/a(rs); План решен. ЗЛП симплю методом 1)выд. базис и сост. 1-ую симпл. табл. 2)перех. к след. симпл. табл. по пунктам 1-6 3)решен. заканчив. когда послед. строки( за искл. послед. эл-та) положит. Послед. столбец послед. симпл. табл. задает оптим. решение.	29. Двойств. симпекс. метод. Раб. с теме же табл. что и прямой метод; (рис.) где -С1,-C2…-Cn-все положит. числа. Если все bi положит. то задач. решена, и решен. (y1,y2…0..0) явл. оптимал. Если среди bi есть отрицат. то поступ. след. образом 1)в послед. столбце наход. наиб. по модулю отрицат. число.Соотв. строка ведущ. 2)если в ней нет отр. эл-тов то целев. ф-ция неогранич. и задач. не имеет реш.3)среди отр. эл. ведущ. строки наход. эл.-ты с наименьш. отнош. эл-тов целев. ф-ции к модулю соотв. эл-та. Выбр. столбец ведущ. Выбр. эл.-разрешающ. Далее 4) меняем мест. неизвестные отвечающ. опорн. строке и столбцу. 5)разреш. эл-т замен. обратным числом 6) остал. эл-ты опорн. строки делим на разреш. эл-т. 7)остал. эл. опорн. столбца делим на разреш. эл. с противоп. знаком 8)остал. эл-ты табл. наход. по правилу прямоугол. (рис.) a(rs)-разреш. a’(ij)-новый. a’(ij)=(a(ij)a(rs)-a(rs)a(is))/a(rs); План решен. ЗЛП симплю методом 1)выд. базис и сост. 1-ую симпл. табл. 2)перех. к след. симпл. табл. по пунктам 1-6 3)решен. заканчив. когда послед. строки( за искл. послед. эл-та) положит. Послед. столбец послед. симпл. табл. задает оптим. решение.
30. Нахожд. минимума ф-ции. пусть на нек. мн-ве опред. ф-ция f(x) Мы нах. min этой ф-ции. Сам прост. явл. метод перебора на [a,b] ищем f min(x) с точн. Е. Для этого разоб. [a,b] на части Xi=a+i(b-a)/n и вычисл. знач. ф-ции в этих (.) f(Xm)=min(f(Xi)); E=(b-a)/n погрешность.Метод деления отрезка пополам. (рис.) X1(n-1)= (a(n-1)+b(n-1)-δ)/2; X2(n-1)= (a(n-1)+b(n-1)-δ)/2; Если f(x1(n-1))<=f(x2(n-1)) то An=A(n-1); bn=x2(n-1); Если f(x1(n-1))>=f(x2(n-1)) то An=x1(n-1); bn=b(n-1).	31. Выпуклые ф-ции, пров.ф-ции на выпукл.,градиент. Опр. мн-во U наз. выпукл. если вместе с любыми 2-я (.) х1 и х2 оно содерж. весь отрезок соед. эти (.) Т.е. £x1+(1-£)x2 cU, £c[0,1];(рис.) Опр. ф-ция f(x)наз. выпукл. если для любых 2-х (.) х1 и х2 и для любого £с[0,1] справедл. нер-во f(£x1+(1-£)x2)<=£(f(x1)+(1-£)f(x2)); Иначе f(c)<=(f(a)+f(b))/2;Градиент. Пусть ф-ция f(x) дважды диф. на выпукл. мн-ве и матрица втор. произв. положит. определена для всех Х из выпукл. мн-ва. |f ‘’(x)|=||δ^2f(x)/δxiδxj||; то ф-ция f(x) явл. выпукл. Иначе все углов. миноры матр. f ‘’(x) положит. то ф-ция выпукла.
32.Градиентный метод нахожд. экстремума. В начал. (.) вычисл. градиент и напр. наискорейшего убыв. ф-ции (антиград.) В этом направл. любым методом ищется min целевой ф-ции. В найд. (.) провер. услов. оконч. расчетов. Если оно не выполн. то снова наход. градиент и новое направл. поисков. Св-ва градиента: 1)град. всегда направл. в стор. возраст. ф-ции 2)град. перпендик. линии ур-ня проход. ч\з ту (.) в котор. он вычисл. 3)в (.) экстремума grad f(x1,x2)=0. Град. метод нах. безусловн. экстремума. Пусть f(x) выпукл. дифф. во всем пр-ве ф-ции. Выберем произвол. х0 и постр. посл-ть. X(к+1)=Xк-£кf ‘ (Xк), где £к-берутся дост. малыми. чтоб выполн. услов. f(X(к+1))<f(Xк) (*)-критер. остановки явл. близость к 0 град. f ‘(Xк) или норма град. ||f ‘(Xк)||=(корень)[∑(δfi(к)/δXj)]<0; Если на каком-либо шаге услов.(*) нарушается, то £к уменьш. в 2 раза и т.д.	33.Метод наискор. спуска. Этот метод также реш. задачу нахожд. экстремума , но отлич. способом опред. £к. Фк(£к)=minФк(£), где Фк(£)=f[Xк-£f ‘(Xк)], такой выбор £ обеспеч. макс. возможное уменьш. ф-ции f(x) вдоль его антиградиента. ПРИМЕР шаг 0: x0=(0,0); f ‘(x0)=1;1 Ф0(£)=f(0-£*1; 0-£*1)=3£^2-e^-2£(найти min); Таблица: £ 0.18 0.2 0.22 0.24 0.26 Ф0(£) 0.7944 0.7909 0.7892(min) 0.7916 0.7973 ; £=£0=0.22 ; X’=(0.0)- 0.22(1;1)=(-0,22;-0,22) шаг 1 f ‘(X’)=(0.204; -0.236); Ф1(£)=(-0.22;-0.204£)^2+(-0.22;0.236£)^2+ е^0.44+0.032£ Минимиз.Ф(£1) £ 0.28 0.3 0.32 0.34 0.36 Ф(£1) 0.774 0.7738 0.7736(min) 0.77387 0.77408 £=£1=0.32 X2=(-0.22; -0.22)-(0.32(0.204; -0.236))=(-0.2853; -0.1445) На след. шаге указ. точность будет достигнута.