vi4matshpori

Модифицированный м Ньютона

На каждом шаге процесса Ньютона приходится обращать м-уу предположим W^-1 (х(p)) ≈ W^-1 (х(0)) тогда х(p+1)=х(p)-W^-1 (х(0))*f(х(p)) итерационный процесс замечание: эта ф-ла в точности совпадает с ф-ой метода простой итерации ТЕОРЕМА при выполнении условий 1 якобиан преобраз W(х)=ðfi/ðхj имеет обратную м-цу Г0 причем !Г0!≤А 2 норма !Г0f(х(0))!≤В 3 Σ!ð²fi/ðхiðхj!≤С 4 множите ль μ0=2n*А*В *С<1 модифи цир метод Ньютона сходится к решению сис

Связь относит погрешн приблиз чис ла с кол-ом верных знаков

Утверждение: если положит при ближ числа а имеет nверных дес ятичн знаков превосх-т (1/10)n-1 деленную на 1ю значащ цифры этого числа σ≤ 1/αm*(1/10)n-1, αm-1 знач цифра Следствие: если число а имеет больше 2х пе рвых знаков то справедлива ф-ла σа ≤(1/2*αm) *(1/10)n-1 если приближен число имеет n 1овк ых десятичн знаков в широком смысле то эту оценка следует ув ел в 2 раза д/решения зад определения кол-ва n верных знаков числа пользуются ф-ой σ=∆/а если известна относит пр огреш а абсол прогреш ∆=σа учитывая десятичн разряд ∆ лег ко установить кол-во верных зна ков числа а

Действия над приближ числами

При сложении\ вычитании абсол приг-ти чисел Σ ∆(а±в)=∆а+∆в

При умнож\делен абсол погреш Σ σ(а*в(а/в))=σа=σв при возведе 1ов в степень приближ числа его относит погреш умнож на по казатель степени σак= к*σа На практике при ® приближ чисел поступ сл образом: 1 выдел чис ла запись кот обрываются ранее др и оставл их без изменения 2 остальн числа округл по образцу сохраняя один\два значащ деся тич знаков 3 производят ® дан ных чисел учитывая все сохр зна 1о 4 получ результат округл на 1 знак погрешности разности произв частного вычисл аналоги чно

Метод постой итерации решение сис лин Ур-ий При большом числе неизвест схема м Гаусса стано вится сложной поэтому удобнее пользоваться при ближ числен методами са мым простым из кот явл м простой итерации приме р Ах=в (1) где а11..а1n

х1 в1 А= а21 ..а2n

х=х2 в=в2 аm1..amn

хm вm пусть аii≠0 тогда х1=β1+α12х2+ …α1nхn хm=βm+αm1x1 +…αmn-1хn-1 где

βi=bi/aii αij= aij /aii αii =0 тогда

α =(α11 α12 α1n

αn1 αn2 αnn

β=(β1 х= (х1

βn) хn) тогда сис (1) превр в сис (2)

х=β +αх (2) т е сис (1) привели к сис (2) вид (2) назыв м после доват приб лижений как правило за 0 приближ принима ют стол бец свободных членов тогда х(1)=β+αх(0)-первое приближен х(к)=β+αх(к-1) если послед х(0) х(1)..х(к) имеет предел то этим пре делом будет решение исх сис limхк= х (к → ∞) тогда х(к)=βi +Σαij xj(к-1) j=1,n ф-ла простой итерации замечание: в некот случаях удобно делать так что бы на диаго нали Эл-ты ≠ 0 замечание о точности расчета: если все коэф и свободные чле ны задан сис явл точными числами то ее реш итерац ион мето дом может быть получено с любым числом m десят знаков при этом в значении следует удержи вать m+1 десят знаков вы числяя надо до их совпа дения после этого можно округ рез ТЕОРЕМА достаточн усл сходимо сти если д\привед сис выполнимо по меньшей мере 1 из усл 1 Σ!аij! <1 i=1,n 2 Σ!аj!<1 j=1.n то процесс итерации сходит ся к един решен этой сис независимо от выбора нач приближ Следствие:д\сис Σ аijхj=вi j=1,n м итерации сходится если все модули диагонал коэф д\кажд ур-ия больше Σ модулей всех ост коэф !аi! > Σ!аij! i ≠ j это нерав м б выполнимо либо по строке либо по столбцу при нахождении лин комбинации все строк и д б задействованны инач е сис лин ур-ий будет име ть бесчисленное мн-во ре

Метод Зейделя

В этом методе при вычислении (к+1) приближ неизвест хi учитываются уже вычисленные (к+1) приближения х1,х2…хi т е пусть дана привед сис хi±βi+Σαij хj j=1,n i=1,n х1(0),х2(0),…хn(0)

нулев приближ предположим что к-е приближения корней извест тогда к+1 имеет вид х1(к+1)=β1+Σα1jхj(к) первое приближ тогда

х2(к+1)=β2+α21х1(к+1)+Σα2jхj(к)

хn(к+1)=βn+Σαnjхj(k+1)+αnnхn(к)

достаточные усл сходимости вер

ны и д\метода Зейделя

Норма матрицы

Под нормой м-ы !!А!!понимается действительное число удовлет сл свойствам 1 !А!≥0 причем = достигается только в сл 0-ой м-ы 2 !αА!=!α!*!А! (!А!=!-А!) 3 !А+В!=!А!+!В! 4 !А*В!=!А!*!В! основные нормы !А!1=max(i)Σ!аij! !А!2=max (j)Σ !аij! !А!3=√Σ!аij!²

Достаточ усл сходим итерационного процесса ТЕОРЕМА процесс ите рац х=αх+β д\сис сходится к еди нствен решению если к-л норма м-ы α меньше 1 т е д\итерацион ного процесса х(к)=αх(к-1)+β достат усл сходимости явл усл норма м-ы !α! < 1 док-во построим последовательность приближений х(0), х(1)=αх(0)+β .., х(к)=αх(к-1)+β т е можно запи сать х(к)=(α(к-1)+α(к-2)+ …+α+Е)β+α(к)х(0) т к норма м-цы !α!<1 то норма !α(к)!→0 при к→∞ Е+α+α²+α³+…+α^к-1 =Σαⁿ(при n=0,к-1) (т к !α!<1 то) = (Е-α)^-1 х=limх(к)(при к→∞) =lim(α(к-1)+α(к-2)+…+α+Е)β+ +α(к)х(0))=(Е-α)^-1β т о сходимос ть доказана

Решение не лин ур-ий будем решать алгебраи ческие или странсинден циальные ур-ия итера цион методом т е ур-ия f(х)=0 будем строить последовательность х(0), х(1),..х(к) limх(к)=х* (при к→∞) х*-точное решение χ-при ближен ное решение ур-ия реше ние осушествляется в 2 этапа 1 локализация кор ней т е нахождение про межутков {а,в} кот прин адлеж корень ур-ия х€{а, в} 2 уточнение корней т е решение ур-ия с задан ной точностью на данн ом промежутке отделен ие корней может проис xодить аналитически ил и графически пусть дано ур-ие f(х)=0 х*-его реш-е f(х*)=0 ТЕОРЕМА если непрерывная фун-ия f(х) принимает значе ние разных знаков на от резке {а,в} т е f(а)*f(в)<0 то внутри этого отрезка содержится по меньшей мере1 корень ур f(х)=0

Метод половинного ыделения f(х)=0 х€[а,в] f(а)*f(в)<0 пусть а0=а в0=в предположим что отрез ок[а,в] построен f(аi)*f(вi)<0 т е значение корня х*€[а,в] найдем точку сi=(аi+вi)/2 середина отре зка если f(сi)=0 то сi-точное реш ение исходного ур-ия если f(сi)≠ 0 то имеем либо f(аi)*f(сi)< 0 (1) либо f(сi)*f(вi)<0 (2) если (1) то аi+i=аi, вi+i=сi если (2) то аi+i=сi,вi+i=вi В любом случае получим интервал в двое мень ше исходного причем f(аi+1)* f(вi+1)<0 процесс заканчивается либо 1 f(ci)=0 ci-корень 2 !аn-вn!<ε тогда выбираем любую то чку χ€[аn,вn]причем реш ур-ия вn-аn=1/2(в-а) χ-аn≤(1/2ⁿ)*(в-а) к=log₂((в-а)/ε)+1 где ε – точность к – кол-во шагов

Метод хорд пусть дана ф-ия f(х)=0 ур-е f(х) определена на [а,в] f(а)*f(в)<0 д\определен предположим что f(а)<0,f(в)>0

поделим отрезок [а,в] в отношении f(а)/f(в); (х-а)/(в-а)=(у-f(а))/(f(в)-f(а)) положим х=х1 и у=0 тогда х1®(f(а)/(f(в)-f(а))*(в-а)+а по этой ф-ле можно записать итерацион процесс т е х1=а+h1 где h1®f(а)/(f(в)-f(а) докажем сходимость итерац процесса будем предполагать что корень f(х) определен а f''(х)сохраняет знак на [а,в]

Имеем 2 случая 1 f(а)>0 хn+1=хn(f(хn)/(f(хn)-f(а))*(хn-а) (рис 2) 2 f(а)<0 хn+1=хn-(f(хn)/f(в)-f(хn))*(в-хn) (рис 1) 1 неподвижен тот конец д\кот знак ф-ии совпадает со знаком второй произв 2 последоват приближения хn лежат по ту сторону х* где ф-ия f(х) имеет знак противоположн знаку ее второй производной в обоих случ кажд приближение ближе к х*-точному решению чем предыдушее док-м это χ=limхn (при n→∞) lim сущ т к ф-ия последов ограничен и монотонна рассм 1 случ χ=χ –( f(χ)/(f(χ)-f(а))*(χ-а) 0=(f(χ)*(χ-а))/f(χ)-f(а) => f(х)=0 аналогично и д\2 случ критерии остановки вычисл процесса !х*-хn!€!хn+1-хn!<ε χ=хn+1

Метод касательных (Ньтона)

Пустьf'(х)- f''(х) непрерыв и сох раняют определен знак на отре зке [а,в] пустьf''(х)>0 и f(в)>0

у-у0=f’(х0)*(х-х0) у-f(хn)=f’(хn) *(х-хn) – ур касат у=0 х=хn+1 с итерацион процесс выведим то же самое аналитически х*=хn+hn где hn-малая величина применим ф-ию Тейлора f(х)=f(а)+(f'(а)/1!)(х-а) +(f’’(а)/2!) (х-а)² 0=f(хn+hn)= =f(хn)+hnf’(хn) hn®f(хn)/f’(хn) => хn+1=хn-f(хn)/f’(хn) выбор начальной точки f(х0)*f’’(х0)>0 ТЕОРЕМА если f(а)*f(в)<0 причем вторая производная сохран знак на отрезке[а,в] то исходя из любого начального приближения х0€[а,в] удовлет вор услов f(х0)*f''(х0)>0 можно вычислить корень ур-ия с любой степенью точности Док-во пус ть f(а)<0 f(в)>0 f'(х)>0 f''(х)>0 т е f(в)*f''(в)>0 х0=в нач точка мето дом мат индукции док-м что все приближения хn>х* =>f(хn)>0 очевидно х0>х* пусть хn=х* представим х*=хn+(х*-хn) по ф-м Тейлора f(х*)=f(хn)+1/2f'(хn) (х*-хn)+1/2f''(хn)(х*-хn)² т е f(хn)+f'(хn)(х*-хn)<0 хn+1=хn-f(хn)/f'(хn)>х* при применении метода Ньютона за нач точку выбирается тот конец интервала[а в] кот отвечает ордината этого же знака что и знак второй производ f''(х) f(а) f'(х) f(в) f(а)*f''(х) или f(в)*f''(х)>0 =>х0=а(в) замечание если ф-ия в близи корня имеет большую кривизну то м Ньютона очень быстро сходится к решению ес ли ли же не так то применять метод нерационально критерии оста овки !хn-хn-1!<ε

Метод скорейшего спуска (градиен та) рассм сис ƒ(х)=0 f1(х1…хn)=0

fn(х1…хn)=0 (1) пусть все ф-ии непрерывны и диффер рассм ф-ию U(х)=(ƒ(х),f(х))=Σ(fi(х))² (при i=1,n) (2) очевидно что решение сис (1) будут решении ями сис (2) и наоборот поэтому решать будем сис(2) причем это решение будет точкой min сис (2) пусть х-решение сис, х(0) нулевое приближ, вычислим U(х(0))- поверхность уровня (эллипсоид) из точки х(0) будем двигаться по нормали к поверх ности U(х(0)) до тех пор пока эта нормаль не коснется в неко торой точки х1(1) другой пов-ти уровня в этой точке проводим нормаль до др пов-ти уровня

Двигаясь по градиентам придем в точку min ф-ии U(х) – эта точ ка решение ∆ОМ1М2 х(1)=х(0)-λ▼U(х(0)) где λ0-коэф ▼U(х (0))-градиент в общем виде х(p+1)=х(p)-λp▼U(х(p))-итерац процесс метода градиента однако величина λp неизвестна д\ее нахождения рассм ф-ию Ф(λ)=Ф(х(p)-λp▼U(х(p)) это ур-ие задает изменение уровня гра диента необходимое решение находится в точке min т е множи тель λ нужно выбрать тек чтобы ðФ(λ)/ðλ=0 наименьший поло жительный корень и будет искомым значением х это ур-ие решается численно в результате вывода μp=2λp=(f(p),WpWp^Tf^p)/ (WpWp^Tf(p), WpWp^Tf^p) x(p+1)=x(p)-μpWp^Tf(p)

Метод Эйлера геометрически у'=f(х,у) у(х0)=у0- задача Коши разобьем ось на проме жутки

К М0 проведем касател ьную до пересечения с прямой х=х1 получим точку М1 опустимся на интеграл кривую и т д полученную ломанную будем считать решением (yi+1-yi)/n=f(x,y) yi+1=yi+nf(xi,yi) пошаговый процесс эта ф-ла обладает малой точ ностью поэтому ее используют редко точность метода порядка n2 у(х)=y(х0)+у'(х0)/1* (х-х0)+у''(х0)/2!*(х-х0)+… -ряд Тейлора y(xi+h)=y(xi)+y'(xi)*h оставшиеся члены ряда отброшены yi+1=yi+ hf(xi,yi) м Эйлера

Видоизмен м Ньютона хn+1=хn(хn) /f'(хn) м Ньютона если произв одная исх ф-ии меняется мало на [а,в] то можно предположить что f(хn)≈ f(х0) хn+1=хn-f(хn)/f'(хn) это дает возможность не вычислять значение про изводной в каждой точке Геометри чески

Т е здесь касательная за меняется на прямую парал ельную первой касател

Метод итерации f(х)=0 заменим α=φ(х) зададим нач альное приближ х0 х1=φ(х0) х2=φ(х1) х0 х1 х2 …послед-е приближ х*=limхn (при n→∞) х*=φ(х*) геометрическая инте рпритация м простой итераци

Если ф-ия φ(х) возрастает то послед-е приближение строя тся лесенкой

Если ф-ия φ(х) убывает то приближен строятся по спира ли в рассмотр случаях прибл иж стремятся к точному зна чению корня это происходит т к !φ’(х)!<1 если !φ’(х)!>0 то

Поэтому итерацион процесс нельзя строить как в предыду щих методах исходя из нача льных условий

ТЕОРЕМА о сходимости м итерации

Пусть φ(х) определенна и диф-ма на[а,в] причем все значения φ(х)€[а,в] тогда если сущ пра вильная дробь g такая что !φ'(у)!≤у<1 тогда 1 процесс итерации хn+1=φ(хn) сходится независимо от начального приб лиж х0€[а,в] 2 предельное значе ние limхn=х* (при n→∞) явл единственным корнем ур-ия

Док-во рассм хn=φ(хn+1) хn+1=φ(хn) вычтем хn+1-хn =φ(хn)-φ(хn-1) по т Лагранжа будем иметь хn+1-хn=(хn-хn-1) *φ'(χ) где χn средняя точ ка € (х0 х1…) !хn+1-хn!=!х n-хn-1! *!φ’(χn)!≤!хn-хn-1!*g !хn+1-хn! ≤ g*!хn-хn-1!-(*) пусть n=1,2,3 имеем из (*) !х2-х1! ≤ g*!х1-х0! !х3-х2! ≤ g*!х2-х1! ≤ g²*!х1-х0! !х4-х3! ≤ g*!х3-х2! ≤ g³*!х1-х0! … !хn+1-хn! ≤ gⁿ*!х1-х0!

Рассмотрим ряд х0+(х1-х0)+(х2-х1)+… для этого ряда последов приближ явл n+1 частными сум мами т е хn=Sn+1 в силу нера венства все члены ряда меньше соответств членов геометрич прогрессии у кот знаменатель < 1 поэтому ряд сходится особе нно lim sn+1=limxn=x* (при n→∞) – единственное решение т е итерацион процесс хn+1= φ(хn) будет сходится к точному решению х* и этом промежутке др решений нет Итерацион про цесс будет сходится тем быстрее чем !φ'(х)!<1 оценка приближе ний !xn+p-xn! ≤ !xn+p-xn+p-1! +!xn+p-1+xn+p-2!++!xn+1-xn! ≤ g^n+p-1*!x1-x0!+g^n+p-2+...+gⁿ!x1-x0! =gⁿ !x1-x0!*(g^n-1+g^n-2+...+1)(геом прогрес)= !x1-x0! gⁿ /1-g в том случае если p→ ∞ то limxn+p =x* (при n→∞) то решение !х*-хn!ы≤ (gⁿ/1-g)*!х1-х0!

Рассм как свести ур-е к виду удобному для итерации f(x)=0 х=х-λf(x)-ур-е равносильно исхо дному х-λf(х)=φ(х) [х=φ(х)] пус ть f’(х) удовлетворяет этому 0<m1<f(х)<M2 нужно подобрать такое λ чтобы !φ’(х)!=!1-λf’(х)! <1т к рассматриваем только по ложительные значения то моду ль можно опустить если это не так то всегда можно рассмотре ть ф-ию (-f(х)) φ'(х)=1-λf’(х) 1-λ *M2<1-λm1≤ g<1 т о можно пре дположить что λ=1/M1 исходя из этого можно вычислить g: g=1-m1/M2 этот способ удобен если известен интервал в кот на ходится точное значение корня если же задача ставится так что задано нулевое приближ х0 то λ наидется из ур-ия 1-λf’(х0)=0

М итерации д\решения сис 2х ур-ий м Зейделя будем решать только сис состоящие из 2х ур-ий с 2я неизвестными F1(х,у)=0 и F2(х,у)=0 нач приближ

Каждое ур-ие в сис может быть приведено к виду х=φ1(х,у) у=φ2(х,у) если х0 у0 нулевое проближен тогда х1=φ1(х0,у0) у1=φ2(х0,у0) х2=φ1(х1,у1) у2=φ2(х1,у1) х1,х2,…,хn у1,у2,…,уn => limхn=х* (при n→∞) и limуn=у* (при n→∞) то точное решение найдем ТЕОРЕ МА пусть в некоторой замкну той окресности R={а ≤ х < А; в ≤ у ≤ В}имеется только одна па ра точек х=х* у=у* если 1 х=φ1(х,у) у=φ2(х,у) ф-ии φ1(х,у) и φ2(х,у) определенны и непре рыв в R 2 нач приближен х0,у0 и все последующие не выходят за рамки R 3 !!Ф!!<1 – норма матрицы где

Ф=(ðφ1/ðх ðφ1/ðу

ðφ2/ðх ðφ2/ðу) состоит из частных производ (якобиан) то процесс сходится к значен х*и у* !!Ф!!=max(!а11!+!а12!, !а21! +!а22!)

14 Метод простой итерации в общем случае х1=φ1(х1,х2…хn) х2=φ2(х1,х2…хn) хn=φn(х1,…хn ) т е дано n ур-ий линейных кот имеет n неизвестных все ф-ии φ1 …φn непрерыв и диф в окрестнос ти решения (х1*,…хn*) запишем эту сис в векторной форме х=(х1…хn) φ(х)=(φ1(х)…φn(х)) х=φх – векторная запись исх сис процесс итерации записывается х^p+1=φ(х(p)) если процесс итер сходится то он сходится к корню векторного ур-ия В общем виде сис ур-ий имеет вид ƒ(х)=0 сис эквивалентна х=х+λf(хi) где λ-неособенная м-ца это значит что ее определитель ≠0 (detλ≠0) φ(х)=х+λf(х) х=φ(х) к этой сис можно применить процесс итера ции Найдем м-цу λ д\этого найде м производн φ’ φ’(х)=Е+λf’(х) исходя из предыдушего можно ожидать что процесс итер юудет сход если норма м-цы !!φ’!! < 1 д\этого φ’(х(0))=Е+λf’(х(0))=0 за дадим λ =-[f’(х(0))]^-1 если f’(х(0)) ≠0 то можно начинать процесс итер х(к+1)=х(к)+λf(х(к))

Метод Ньютона рассм вектор ное ур-е f(х)=0 f1(х1бх2,..хn)=0 f2(х1,х2,..хn)=0 fn(х1,..хn)=0 сис ур-ий может быть любой предпо ложим что найдено х(p)=(х1(p), х2(p)..хn(p)) приближение одного из корн ей тогда этот корень может быть представлен в виде х= х(p)+ε(p) где ε(p)=(ε1(p),ε2(p)…εn(p)) ε- погрешность корня иначе исходное ур-е можно перепи са ть в виде f(х(p)+ε(p))=0 разложи м это ур-е по степе ни ε(p) огран ичиваясь линей ным слогаемым f(х(p)+ε(p))= f(х(p))+f’(х(p))*ε(p) выпиш ем это ур-е в развернутом виде т е f1(х1(p)+ε1(p), х2(p)+ε2 (p),..хn(p)+εn(p))= f1(х1(p),х2(p)…хn(p))+f1’*х1(х1(p),х2(p)..хn(p))*ε1(p)+f1’*х2(х1(p),х2(p)..хn(p))*ε(p)+.. +f1’хn(х1(p),х2(p)..хn(p))*εn(p)=0 fn(х1(p)+ε1(p)..хn(p)+εn(p))=fn(х1(p),х2(p)..хn(p))+fn’х1(х1(p),х2(p)..хn(p))*ε1(p)+..+fn’хn(х1(p),х2(p)..хn(p))*εn(p) т о f'(x)=W9x)=ðf1/ðxi якобиан преобразования иначе эту сис можно записать f(x(p))+ W(x(p))*ε(p)=0 ε(p)=-W^-1 (x(p))*f(x(p)) x(p+1)=x(p)-W¹(x(p))*f(x(p))-метод Нью тона ТЕОРЕМА пусть дана нелин сис f(х)=0 (f1..fn=0)все ф-ии fi определенны и непре рывн вместе со своими частн ыми производ 1 и 2 порядка Пусть х0-нач приближ прич ем выполнен условия 1 якобиан преобраз W(х)=ðfi/ðхj имеет обратную м-цу Г0 причем !Г0!≤А 2 норма !Г0f(х(0))!≤В 3 Σ!ð²fi/ðхiðхj!≤С огранич 2х производных 4 множитель μ0=2n*А*В *С<1 метод Нью тона сходится т е !!x(p)-x(p-1)!!≤ε=2В в кач-ве нормы уд обно принять !!А!!=maxΣ!aij!

Метод скорейшего спус ка лин сис рассм f=ax-b W=ðf/ðx= a11,a12..a1n

an1,an2..ann

x(p+1)=x(p)-μА^тr^p=Ax(p)-b где r^p – невязка

μ=( r^p-А^т*А*r^p)/( А^т*А*r^p, А^т*А*r^p)

Ф-ла трапеции ∫f(x)dx (a,b -границы)

h-шаг=b-a/n Sтрапеции = (a+b/2)*h (y0+y1/2)* *h+(y1+y2/2)*h+...+(yn++yn+1/2)*h=S Σ(yi-1+ +yi/2)*h=S=∫ydx ∫=h*Σ((y0+yn)/2+y1+y2+..yn-1)=h*Σ((y0+yn)/2+yi) -ф-ла трапеции

Модифиц м Эйлера y’=f(x,y) y(x0)=y0 xi-x0+ih

ч\з точку (xi,yi) проводи тся касательная с α1=f(xi, yi) до пересечения с пря мой (xi+h/2)=xi+1/2 по м Эйлера вычисляется yi+1/2=yi+h/2f(xi,yi) затем в точке (xi+1/2,yi+1/2) вы числяется значение произ водной fi+1/2=f(xi+1/2, yi+1/2) возвращаемся в точку (xi,yi) и из нее про водим прямую паралле льную второй касательной касательная проводится до пересечения с прямой x=xi+1; yi+hfi+1/2 y(x0)= y0 – модиф м Эйлера

Метод Рунги-Кутта y’=f(x,y) y(x0)=yo ось х разбиваем xi= x0+ih предположим yi=y(xi) рассматриваем числа k1(i)=h*f(xi,yi) k2(i)= h*f(xi+ h/2,yi+h/2) k3(i)=h *f(xi+h/2, yi+k2(i)/2) k4(i)= h*f(xi+h,yi+ k3(i)) yi+1=yi+∆yi ∆yi=1/6*(k1(i)+2k2(i)+2k3(i)+k4(i)) погрешность этого мето да на кажд шаге h⁵ эффектив ная оценка погрешности это го метода затруднительна Обычно на каждом этапе сост из 2х шагов делают двойной пересчет с шагом h и 2h т е величину y(xi+2h) вычисляют двумя способами если расхо ждения не превышают допус тимую погрешность то шаг можно увеличить в двое если следующие значение превы шает допустимую погрешнос ть то шаг уменьшают в двое

Метод наимен квадратов пусть в результате исследований некоторой величины х значе ниям х1,х2, хn поставлены в соответствия др значения у1, у2 уn требуется подобрать вид аналитической зависи мости у=у(х) связывающие перемен х и у (у=b*х) в мето де наим квадратов параметр b определяется из условий min суммы квадратов откло нений эксперемент данных уi от расчетных вычислений yi* F=Σ(yi-bxi)²→ min df/db=2Σ((yi-bxi)*(-xi))=0 b=Σxiyi/Σxi² в большинстве случаев искомая переменная имеет вид y=a+bx F=Σ(yi-bxi)²→ min df/da=2Σ(yi-a-bxi) df/db=2Σ((yi-a-bxi)*(-xi)) Σ(yi-a-bxi)=0 Σ((yixi-axi-bxi²)=0 Σyi=Σ(a+bxi)= bΣxi+an Σyixi=Σaxi+Σbxi²= aΣxi+bΣxi² Σyi=an+bΣxi Σyixi= aΣxi+bΣxi² a=(Σyi-bΣxi)/n b=(nΣxiyi-Σxi Σyi) /(nΣxi²-(Σxi)²

Симплекс метод из геометриче ских соображений понятно что допусти мая обл предста вляет собой многогранное мн-во (на плоскости много угольники) и оптималь ного зн-ия целевая ф-ия будет достигать в вершине этого многогранного мн-ва поэтому нужен алгоритм перебора всех вершин 1 в начале рассм задачу в канонической форме z=Σcjxj→max Σajxj=fci= =1mxj ≥0 j=1n если m<n т е ур-ий меньше чем неизвестных то исх сис ограничений может быть приведена к виду a11x1+ a1n-mxn-m+xn-m+1=0 ... am1x1+amn-mxn-m+xn= bm (**)если коэф aij bi определяются однозначно исходными данными если переме х1,х2, xn-m положить =0 то по лучим xn-m+1=b1 xn-m+2=b2… xn=bm – это решение назыв базисным а перемен базис переем (базисом) ос тальные перемен свобод ные Если среди перемен базисного решен есть отри цат то такое решение наз недоступным Доступным решением (опорным прла ном) наз такое базис реш которое одновременно и допустимо переобозначим в сис (**) базисные пере мен ч\з у1,у2 ..yn y1=a11 (-х1)+a1n-m(-xn-m) +(-xn-m+1)+ b1 ...ym= am1(-x1) +amn-m (-xn-m)+(-xn)+bm целевая ф-ия z=-c1(-x1)-...-cn-m(-xn-m)

2 пусть задача лин програм задана в станда ртной форме на max в сигнатурной форме на max (c,x)→max Ax≤b х≥0 a11x1+ a1nxn+y1= b1 ... am1x1+ amnxn+ ym=bm где y1,y2..ym≥0 y1=a11 (-х1)+a1n(-xn) + b1 ...ym= am1(-x1) +amn (-xn)+bm целевая ф-ия z=-c1(-x1)-…-cn(-xn) задачи в стандартной и канонич форме могут бы ть приведены к одному виду Когда задача приве дена к такому виду ее мо жно внести в симплексн ую табл.

В последнем столбце все bi положит иначе допус тимого базисн реш нет Если в последней строке нет ни одного отриц эл-та то задача решена Пе ресчет табл будем произ водить сл образом 1 в посл строке находим на иб по модулюотрицат число соотв стол- опор ный 2 из всех строк с по ложит эл-ми на пересече нии берем строкус наи мен отклонением свобод ного члена соотв эл-ту опрного столбца (строка опорная ведущая) Эл-т стоящий на пересечении строки и столбца наз раз решающим

3 меняем местами неизвес тные отвечающие опорно строке и столбцу 4 разрещ эл-т заменяем обратным числом 5 остальные эл-ты опорной строки делим на раз эл-т остальные эл-ты столбца делим на раз с противопол знаком 6 оста льные эл-тыслед симпл табл находим по правилу прямоугольника

aij ________ais aij-новый

ari________ars ars-разреш

aij=(aij*ars-arj*ais)/ars

решение закан тогда когда эл-ты последней строки (искл послед эл-т) положи тельны последний стол бец посл симпл табл зада ет оптимальное решение Замечание в целя удобс тва в начале нужно Перес читать послед строку

Двоиственный симпл метод работает с теми же симпл та бл что и прямой если все bi положительны то задача реше на и ее решение (y1,y2,..ym, 0...0)явл оптимальным если среди bi есть олрицательн то поступают сл образом 1 в пос леднем столбце находят наиб по модулю отриц число соотв строка – ведущая 2 если в это й строке нет отрицат эл-ов то целевая ф-ия не ограничена и задача не имеет реш-ий 3 сре ди отриц эл-ов вед строки на ходим эл-т с наименьшим от ношением эл-ов целевой ф-ии к модулю соотв эл-та выбран столбец ведущий эл-т разреш Далее проводим стандартное преобразование симпл табл (шаги 3-6 прямого метода)

30 Нахождение экстремума пус ть на некотором мн-ве опре деленна ф-ияf(x) мы будем находить min этой ф-ии зада ча на max явл симметричной (f(x)→max, -f(x)→min) сам ым простым явл метод пере бора т е на [a,b] будем искать fmin(x) с точностью ε Д\это го разобьем [a,b] на части xi=a+i((b-a)/n) и вычислим значение ф-ии в этих точках f(xm)=min(f(xi))- это значе ние явл наименьшим погре шность εn=(b-a)/n

31 безусловная минимиз ф-ии нескольких перемен мн-во U назыв выпуклым если вме сте с любыми 2 точками х1,х2 онон содержит весь отрезок соедин эти точки αх1+(1-2)х2€U α€[0,1] Ф-ия F(x) наз выпуклой если д\любых 2х точек х1,х2 и д\любого α€[0,1] справед ливо неравенство f(αx1+ +(1-2)x2≤αf(x1)+(1-2)f(x2) иначе f(c)≤(f(a)+f(b))/α про верка ф-ии на выпуклость пусть ф-ия f(x) дважды диффер на выпуклом мн-ве и м-ца вторых произво дных положительна опре делена д\всех х из выпук лого мн-ва то ф-ия f(x) явл выпуклой !f'' (x)!=!!ðf(x)/ ðxiyi!! иначе если все усло вные миноры м-цы f''(x) положит то ф-ция выпукла

Градиентные методы пои ска экстремума в нач точ ке вычисляется градиент и направление наискор убывания ф-ии (антигра диент) в этом направле нии любым методом ищется min целевой ф-ии В найденной точке проверяют условие око нчания расчетов Если оно не выполнено то сно во находим градиент и новое направление поис ка Св-ва градиента 1 град всегда направлен в сторону возрастания ф-ии 2 град ┴-ен линии уровня проходяшей ч\з ту точку в которой он вычисляется ы в точке экстремума grad=0 gradf(x1,x2)=(ðf(x1,x2)/ðx1)*τ+(ðf(x1,x2)/ðx2)j

Градиентный метод нахожде ния безуслов экстремума пусть f(x) выпуклая, диф во всем пространстве ф-ия Выберим произвольно нач приближение х(0) и пост роим послед-ть х(к+1)=х (к)-αкf’(х(к)) где величии ны αк-ые берутся достато чно малыми Что бы выпол нялось условие fx(к+1)< f(х(к)) (*) критерием остановки явл близость к 0 градиента f'(х(к)) или норма градиента !! f'(х(к)) !!=√Σ ðfi(k)/ðxj <ε или модуль градиента !f'(х(к))! <ε если на к-л шаге (*) условие не выполняется то αк уменьшают в двое и т д

33 метод наискирейшего спуска этот метод решает ту же зада чу, но отличается то предыду щего способом определения величины αк αк находится из условия Фк(αк)=minФк(α) где Фк(α)=f[х(к)-αf'(х(к))] (min среди всех α>0) такой выбор α обеспечивает max возмож ное уменьшение ф-ии f(х) вдо ль его антиградиента антигра ыдиент -f'(х(к)) в точке х(к)