Netiesinių lygčių sprendimas

Tarkime, kad turime išspręsti lygtį

Kur
– netiesinė nuolatinė funkcija.

Lygčių sprendimo metodai skirstomi į tiesioginius ir kartotinius. Tiesioginiai metodai yra metodai, leidžiantys apskaičiuoti sprendimą naudojant formulę (pavyzdžiui, rasti kvadratinės lygties šaknis). Iteraciniai metodai – tai metodai, kuriuose nurodomas tam tikras pradinis aproksimacija ir konverguojama tiksliam sprendimui aproksimacijų seka, o kiekviena paskesnė aproksimacija apskaičiuojama naudojant ankstesnes.

Visą problemos sprendimą galima suskirstyti į 3 etapus:

Nustatykite (1) lygties šaknų skaičių, pobūdį ir vietą.

Raskite apytiksles šaknų reikšmes, t.y. nurodykite intervalus, kuriais augs šaknys (atskirkite šaknis).

Reikiamu tikslumu raskite šaknų reikšmę (nurodykite šaknis).

Pirmoms dviem problemoms spręsti yra įvairių grafinių ir analitinių metodų.

Akivaizdžiausias būdas atskirti (1) lygties šaknis yra nustatyti funkcijos grafiko susikirtimo taškų koordinates.
su abscisių ašimi. Abscisos grafiko susikirtimo taškai
su ašimi
yra (1) lygties šaknys

Išskyrimo intervalus (1) lygties šaknims galima gauti analitiškai, remiantis teoremomis apie intervale ištisinių funkcijų savybes.

Jei, pavyzdžiui, funkcija
ištisinis segmente
Ir
, tada pagal Bolzano – Koši teoremą atkarpoje
yra bent viena (1) lygties šaknis (nelyginis šaknų skaičius).

Jei funkcija
atitinka Bolzano-Cauchy teoremos sąlygas ir yra monotoniškas šiame intervale, tada
yra tik viena (1) lygties šaknis.Taigi (1) lygtis turi
viena šaknis, jei tenkinamos šios sąlygos:

Jei funkcija yra nuolat diferencijuojama tam tikrame intervale, tada galime naudoti Rolle teoremos išvadą, pagal kurią tarp šaknų poros visada yra bent vienas stacionarus taškas. Problemos sprendimo algoritmas šiuo atveju bus toks:

Naudingas įrankis šaknims atskirti taip pat yra Šturmo teoremos panaudojimas.

Trečiojo uždavinio sprendimas vykdomas įvairiais iteraciniais (skaitiniais) metodais: dichotomijos metodu, paprastosios iteracijos metodu, Niutono metodu, akordo metodu ir kt.

Pavyzdys Išspręskime lygtį
metodas paprasta iteracija. Nustatykime
. Sukurkime funkcijos grafiką.

Grafikas rodo, kad mūsų lygties šaknis priklauso segmentui
, t.y.
yra mūsų lygties šaknies izoliacinis segmentas. Patikrinkime tai analitiškai, t.y. sąlygų įvykdymas (2):

Prisiminkime, kad pradinė lygtis (1) paprastosios iteracijos metodu transformuojama į formą
ir iteracijos atliekamos pagal formulę:

(3)

Skaičiavimų atlikimas naudojant (3) formulę vadinamas viena iteracija. Iteracijos sustoja, kai įvykdoma sąlyga
, Kur - absoliuti klaida ieškant šaknies, arba
, Kur - santykinė klaida.

Paprastas iteracijos metodas suartėja, jei tenkinama sąlyga
Dėl
. Funkcijos pasirinkimas
Iteracijų formulėje (3) galite paveikti metodo konvergenciją. Paprasčiausiu atveju
su pliuso arba minuso ženklu.

Praktikoje tai dažnai išreiškiama
tiesiai iš (1) lygties. Jei konvergencijos sąlyga neįvykdyta, transformuokite ją į formą (3) ir pasirinkite ją. Pavaizduokime savo lygtį formoje
(iš lygties išreikškite x). Patikrinkime metodo konvergencijos sąlygą:

Dėl
. Atkreipkite dėmesį, kad konvergencijos sąlyga netenkinama
, todėl paimame šaknies izoliacijos segmentą
. Praeidami pažymime, kad pateikdami savo lygtį formoje
, metodo konvergencijos sąlyga neįvykdyta:
segmente
. Grafikas tai rodo
didėja greičiau nei funkcija
(|tg| liestinės pasvirimo kampas į
segmente
)

Rinksim
. Iteracijas organizuojame pagal formulę:

Programiškai organizuojame iteracijos procesą tam tikru tikslumu:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

o abs(x1-x)> eps daro

x1:=f1(x):

spausdinti(evalf(x1,8)):

spausdinti(abs(x1-x)):

:printf("Iterijos skaičius = %d ",k):

galas:

19 iteracijoje mes gavome savo lygties šaknį

su absoliučia klaida

Išspręskime savo lygtį Niutono metodas. Niutono metodo iteracijos atliekamos pagal formulę:

Niutono metodas gali būti laikomas paprastos iteracijos su funkcija metodu, tada Niutono metodo konvergencijos sąlyga bus parašyta taip:

.

Mūsų užraše
ir konvergencijos sąlyga tenkinama intervale
, kaip matyti iš grafiko:

Prisiminkite, kad Niutono metodas konverguoja kvadratiniu greičiu ir pradinė aproksimacija turi būti parinkta pakankamai arti šaknies. Atlikime skaičiavimus:
, pradinis aproksimacija, . Iteracijas organizuojame pagal formulę:

Programiškai organizuojame iteracijos procesą tam tikru tikslumu. 4 iteracijoje gauname lygties šaknį

Su
Išnagrinėjome netiesinių lygčių sprendimo būdus, kaip pavyzdį naudodami kubines lygtis; natūralu, kad šie metodai išsprendžia įvairių tipų netiesines lygtis. Pavyzdžiui, sprendžiant lygtį

Niutono metodas su
, raskite lygties šaknį ties [-1,5;-1]:

Pratimas: Tiksliai išspręskite netiesines lygtis

0.

segmento padalijimas per pusę (dichotomija)

paprasta iteracija.

Niutonas (liestinės)

sekantai – akordai.

Užduočių parinktys apskaičiuojamos taip: skaičius sąraše yra padalintas iš 5 (
), sveikoji dalis atitinka lygties numerį, likusioji – metodo numerį.

LABORATORINIS DARBAS Nr.3-4.

5 variantas.

Darbo tikslas: išmokti spręsti netiesinių lygčių sistemas (SNE) naudojant paprastą iteracijos metodą (SI) ir Niutono metodą, naudojant kompiuterį.

1. Išstudijuokite MPI ir Niutono metodą netiesinių lygčių sistemoms spręsti.

2. Naudodamiesi konkrečiu pavyzdžiu išmokite netiesinių lygčių sistemų sprendimo MPI ir Niutono metodu procedūrą kompiuteriu.

3. Sukurkite programą ir naudodami ją spręskite lygčių sistemą tikslumu.

DARBO ATLIKIMO PAVYZDYS

Pratimas.

1. Analitiškai išspręskite SNE:

2. Sudarykite MPI ir Niutono metodo darbines formules sistemos skaitiniam sprendimui pradiniu aproksimavimu: .

3. Sukurkite programą bet kuria programavimo kalba, kuri įgyvendina sukonstruotą iteracinį procesą.

Sprendimas.

Analitinis metodas.

SDE analitinis sprendimas yra taškai ir .

Paprastų iteracijų metodas (SIM).

Norint sukurti veikiančias MPI formules, skirtas skaitiniam sistemos sprendimui, pirmiausia reikia ją pateikti į formą:

Norėdami tai padaryti, padauginkite pirmąją sistemos lygtį iš nežinomos konstantos, antrąją iš , tada sudėkite jas ir pridėkite prie abiejų lygties pusių. Gauname pirmąją transformuotos sistemos lygtį:

Nežinomas konstantas nustatome iš pakankamų sąlygų iteracinio proceso konvergencijai:

Parašykime šias sąlygas išsamiau:

Darant prielaidą, kad išraiškos po modulio ženklu yra lygios nuliui, gauname 4 eilės tiesinių algebrinių lygčių (SLAE) sistemą su 4 nežinomaisiais:

Norint išspręsti sistemą, reikia apskaičiuoti dalines išvestines:

Tada SLAE bus parašytas taip:

Atkreipkite dėmesį, kad jei dalinės išvestinės mažai keičiasi netoli pradinio aproksimavimo, tada:

Tada SLAE bus parašytas taip:

Šios sistemos sprendimas yra taškai , , , . Tada MPI darbo formulės, skirtos SNL išspręsti, bus tokios formos:

Norint įgyvendinti kompiuteryje, darbo formules galima perrašyti taip:

Iteracinį procesą galima pradėti nustatant pradinį aproksimaciją x 0 =-2, y 0 =-4. Procesas baigiasi, kai vienu metu įvykdomos dvi sąlygos: ir . Šiuo atveju reikšmės ir yra apytikslė vieno iš SNL sprendimų vertė.

Niutono metodas.

Formoje sudaryti Niutono metodo darbo formules

kur reikia:

1. Raskite dalinių išvestinių matricą:

2. Raskite šios matricos determinantą:

3. Apibrėžkite atvirkštinę matricą:

Atlikus transformaciją:

Gauname Niutono metodo darbo formulę, skirtą įgyvendinti kompiuteryje:

Blokinė schema MPI ir Niutono metodas SLE sprendimui parodyti 1 paveiksle.

1 pav. MPI ir Niutono metodo schemos.

Programos tekstai:

Programa P3_4; (Iteracijos)

naudoja Crt;

var n: sveikasis skaičius;

clrscr;

xn:=x-(x-y+2)+(1/2)*(x*y-3);

yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);

writeln (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5) ;

n:=n+1;

iki (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

readln;

2) Niutono metodas:

Programa P3_4; (Niutonas)

naudoja Crt;

var n: sveikasis skaičius;

x0,x,xn,y0,y,yn,eps,zx,zy:real;

clrscr;

n:=0; x0:=-2; x:=x0; y0:=-4; y:=y0; eps:=0,001;

writeln("n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i)");

xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);

yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);

writeln (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9: 5);

n:=n+1;

iki (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

Programos vykdymo rezultatai:

· 2 pav. – programa, veikianti paprastų iteracijų metodu;

· 3 pav. – programa, veikianti pagal Niutono metodą.

2 pav. Atsakymas: x(16)≈-3,00023, y(16)≈-1,00001

3 pav. Atsakymas: x(8)≈-3,00000, y(8)≈-1,00000

Visi žmonės iš prigimties siekia žinių. (Aristotelis. Metafizika)

Skaitiniai metodai: netiesinių lygčių sprendimas

Praktikoje nuolat iškyla lygčių sprendimo problemos, pavyzdžiui, ekonomikoje, plėtojant verslą norisi žinoti, kada pelnas pasieks tam tikrą vertę, medicinoje, tiriant vaistų poveikį svarbu žinoti kada koncentracija medžiagos kiekis pasieks tam tikrą lygį ir pan.

Optimizavimo uždaviniuose dažnai reikia nustatyti taškus, kuriuose funkcijos išvestinė tampa 0, o tai yra būtina sąlyga vietinis ekstremumas.

Statistikoje, sudarant įverčius naudojant mažiausių kvadratų arba didžiausios tikimybės metodą, tenka spręsti ir netiesines lygtis bei lygčių sistemas.

Taigi iškyla visa klasė problemų, susijusių su sprendimų paieška netiesinis lygtys, pvz., lygtys arba lygtys ir kt.

Paprasčiausiu atveju turime funkciją, apibrėžtą intervale ( a, b ) ir imant tam tikras reikšmes.

Kiekviena vertė x iš šio segmento galime palyginti skaičių, tai yra funkcinis priklausomybė, pagrindinė matematikos sąvoka.

Turime rasti reikšmę, kuriai esant jos vadinamos funkcijos šaknimis

Vizualiai turime nustatyti funkcijos grafiko susikirtimo taškąsu abscisių ašimi.

Perpus sumažinimo metodas

Paprasčiausias būdas rasti lygties šaknis yra perpus sumažinimo metodas arba dichotomija.

Šis metodas yra intuityvus ir visi spręsdami problemą elgtųsi panašiai.

Algoritmas yra toks.

Tarkime, kad randame du taškus ir , Toks, kad jie turi skirtingaženklai, tada tarp šių taškų yra bent viena funkcijos šaknis.

Padalinkime segmentą per pusę ir įveskime vidutinis taškas .

Tada arba , arba .

Palikime tą segmento pusę, kurios vertės galuose turi skirtingus ženklus. Dabar šį segmentą vėl padalijame per pusę ir paliekame tą dalį, kurios ribose funkcija turi skirtingus ženklus ir pan., kad pasiektume reikiamą tikslumą.

Akivaizdu, kad palaipsniui susiaurinsime sritį, kurioje yra funkcijos šaknis, todėl ją nustatysime tam tikru tikslumu.

Atkreipkite dėmesį, kad aprašytas algoritmas taikomas bet kuriai nuolatinei funkcijai.

Perpus sumažinimo metodo pranašumai yra didelis patikimumas ir paprastumas.

Metodo trūkumas yra tai, kad prieš pradėdami jį naudoti, turite rasti du taškus, kuriuose funkcijos reikšmės turi skirtingus ženklus. Akivaizdu, kad metodas netaikomas tolygių daugybinių šaknų atveju, taip pat negali būti apibendrintas sudėtingų šaknų atveju ir lygčių sistemoms.

Metodo konvergencijos tvarka yra tiesinė, kiekviename žingsnyje tikslumas padvigubėja; kuo daugiau kartojama, tuo tiksliau nustatoma šaknis.

Niutono metodas: teoriniai pagrindai

Klasikinis Niutono metodas arba liestinės yra tai, kad jei yra lygties šaknies aproksimacija , tada kita aproksimacija apibrėžiama kaip taške nubrėžtos funkcijos liestinės šaknis.

Funkcijos liestinės lygtis taške yra tokia:

Į liestinės lygtį įdedame ir .

Tada Niutono metodo nuoseklių skaičiavimų algoritmas yra toks:

Tangentinio metodo konvergencija yra kvadratinė, konvergencijos tvarka yra 2.

Taigi Niutono tangentinio metodo konvergencija yra labai greita.

Prisiminkite šį nuostabų faktą!

Be jokių pakeitimų metodas apibendrintas sudėtingam atvejui.

Jei šaknis yra antrojo ar didesnio dauginio šaknis, tada konvergencijos tvarka krenta ir tampa tiesinė.

1 pratimas. Naudodami liestinės metodą atkarpoje (0, 2) raskite lygties sprendimą.

2 pratimas. Naudodami liestinės metodą atkarpoje (1, 3) raskite lygties sprendimą.

Niutono metodo trūkumai apima jo vietą, nes garantuojama, kad jis suartės savavališkam pradiniam aproksimavimui tik tada, kai sąlyga tenkinama visur. , priešingoje situacijoje konvergencija vyksta tik tam tikroje šaknies kaimynystėje.

Niutono metodo trūkumas yra būtinybė skaičiuoti išvestines kiekviename žingsnyje.

Niutono metodo vizualizacija

Niutono metodas (tangentinis metodas) naudojamas, jei lygtis f(x) = 0 turi šaknį ir tenkinamos šios sąlygos:

1) funkcija y= f(x) apibrėžtas ir tęstinis ;

2) f(a)· f(b) < 0 (funkcija paima skirtingų ženklų reikšmes segmento galuose [ a; b]);

3) dariniai f"(x) Ir f""(x) išsaugoti ženklą ant intervalo [ a; b] (t. y. funkcija f(x) segmente padidėja arba sumažėja [ a; b], išlaikant išgaubimo kryptį);

Pagrindinė metodo idėja yra tokia: segmente [ a; b] pasirenkamas toks skaičius x 0 , kuriame f(x 0 ) turi tą patį ženklą kaip f"" (x 0 ), y., sąlyga tenkinama f(x 0 )· f"" (x) > 0 . Taigi pasirenkamas taškas su abscisėmis x 0 , kurioje kreivės liestinė y= f(x) segmente [ a; b] kerta ašį Jautis. Už tašką x 0 Pirma, patogu pasirinkti vieną iš segmento galų.

Panagrinėkime Niutono metodą naudodami konkretų pavyzdį.

Suteikime mums didėjančią funkciją y = f(x) =x 2-2, ištisinis atkarpoje (0;2), ir turintis f"(x) = 2 x > 0 Ir f "" (x) = 2 > 0 .

Piešimas1 . f(x) =x 2 -2

Bendrosios formos liestinės lygtis turi tokį vaizdą:

y-y 0 = f" (x 0)·(x-x 0).

Mūsų atveju: y-y 0 =2x 0 · (x-x 0). Taškui x 0 pasirenkame tašką B 1 (b; f (b)) = (2,2). Nubrėžkite funkcijos liestinę y = f(x) taške B 1 ir pažymime liestinės ir ašies susikirtimo tašką Jautis taškas x 1. Gauname pirmosios liestinės lygtį: y-2=2·2(x-2), y=4x-6.

Jautis: x 1 =

Piešimas2. Pirmosios iteracijos rezultatas

y=f(x) Jautis per tašką x 1, supratome esmę B 2 =(1,5; 0,25). Dar kartą nubrėžkite funkcijos liestinę y = f(x) taške B 2 ir pažymime liestinės ir ašies susikirtimo tašką Jautis taškas x 2.

Antrosios liestinės lygtis: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Liestinės ir ašies susikirtimo taškas Jautis: x 2 =.

Piešimas3. Antroji Niutono metodo iteracija

Tada randame funkcijos susikirtimo tašką y=f(x) ir ašiai nubrėžtą statmeną Jautis per tašką x 2 gauname tašką B 3 ir pan.

Piešimas4. Trečias liestinės metodo žingsnis

Pirmasis šaknies apytikslis nustatymas nustatomas pagal formulę:

= 1.5.

Antrasis šaknies aproksimavimas nustatomas pagal formulę:

=

Trečiasis šaknies aproksimavimas nustatomas pagal formulę:

Taigi , iŠaknies aproksimacija nustatoma pagal formulę:

Skaičiavimai atliekami tol, kol sutampa tie skaičiai po kablelio, kurių reikia atsakyme, arba pasiekiamas nurodytas tikslumas e – kol įvykdoma nelygybė | xi- xi-1 | < e.

Mūsų atveju palyginkime trečiajame žingsnyje gautą aproksimaciją su tikru skaičiuotuvu apskaičiuotu atsakymu:

5 pav. 2 šaknis, apskaičiuota skaičiuotuvu

Kaip matote, jau trečiame žingsnyje gavome mažesnę nei 0,000002 klaidą.

Tokiu būdu galite bet kokiu tikslumu apskaičiuoti „2 kvadratinės šaknies“ reikšmę. Šį nuostabų metodą išrado Niutonas ir jis leidžia rasti labai sudėtingų lygčių šaknis.

Niutono metodas: taikymas C++

Šiame straipsnyje mes automatizuosime lygčių šaknų skaičiavimo procesą, parašydami konsolės programą C++ kalba. Kursime jį Visual C++ 2010 Express, tai nemokama ir labai patogi C++ kūrimo aplinka.

Pirmiausia paleiskite „Visual C++ 2010 Express“. Pasirodys programos pradžios langas. Kairiajame kampe spustelėkite „Sukurti projektą“.

Ryžiai. 1. Visual C++ 2010 Express pagrindinis puslapis

Pasirodžiusiame meniu pasirinkite „Win32 Console Application“ ir įveskite programos pavadinimą „Newton_Method“.

Ryžiai. 2. Sukurkite projektą

// Newton.cpp metodas: apibrėžia konsolės programos įėjimo tašką #include "stdafx.h" #įtraukti naudojant vardų sritį std; float f(double x) //pateikia funkcijos f(x) = x^2-2 reikšmę float df(float x) //pateikia išvestinę reikšmę float d2f(float x) // antrosios išvestinės reikšmė int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//išėjimo ir ciklo kintamieji dvigubas x0,xn;//apskaičiuotos šaknies aproksimacijos dvigubas a, b, eps; // atkarpos ribos ir reikalingas tikslumas cout<<"Please input \n=>"; cin>>a>>b; // įveskite segmento, kuriame ieškosime šaknies, ribas cout<<"\nPlease input epsilon\n=>"; cin>>eps; // įveskite reikiamą skaičiavimo tikslumą if (a > b) // jei vartotojas sumaišė segmento ribas, pakeiskite jas if (f(a)*f(b)>0) // jei funkcijos ženklai atkarpos kraštuose yra vienodi, tai čia nėra šaknies cout<<"\nError! No roots in this interval\n"; jei (f(a)*d2f(a)>0) x0 = a; // norėdami pasirinkti pradžios tašką, pažymėkite f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // apsvarstykite pirmąjį aproksimaciją cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // toliau skaičiuos, kol pasieksime reikiamą tikslumą xn = x0-f(x0)/df(x0); // tiesiogiai Niutono formulė cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) while (išeiti!=1); // kol vartotojas įves exit = 1

Pažiūrėkime, kaip tai veikia. Spustelėkite žalią trikampį viršutiniame kairiajame ekrano kampe arba paspauskite F5.

Jei įvyksta kompiliavimo klaida „Klaida LNK1123: nepavyko konvertuoti į COFF: failas netinkamas arba sugadintas“, ją galima ištaisyti įdiegus pirmąjį 1 pakeitimų paketą arba projekto nustatymuose Ypatybės -> Linker išjungiant laipsnišką susiejimą.

Ryžiai. 4. Projekto kompiliavimo klaidos sprendimas

Ieškosime funkcijos šaknų f(x) =x2-2.

Pirmiausia patikrinkime, kaip programa veikia naudojant „neteisingus“ įvesties duomenis. Segmente nėra šaknų, mūsų programa turėtų parodyti klaidos pranešimą.

Dabar turime programos langą:

Ryžiai. 5. Įvesties duomenų įvedimas

Įveskime atkarpų 3 ir 5 ribas, kurių tikslumas yra 0,05. Programa, kaip ir tikėtasi, pateikė klaidos pranešimą, kad šiame segmente nėra šaknų.

Ryžiai. 6. Klaida „Šiame segmente nėra šaknų!“

Mes dar nesiruošiame išvykti, o kaip dėl pranešimo „Išeiti? įveskite „0“.

Dabar patikrinkime programą naudodami teisingus įvesties duomenis. Įveskime segmentą ir tikslumu 0,0001.

Ryžiai. 7. Šaknies apskaičiavimas reikiamu tikslumu

Kaip matome, reikiamas tikslumas buvo pasiektas jau per 4 iteraciją.

Norėdami išeiti iš programos, įveskite "Išeiti?" => 1.

Sekantinis metodas

Kad nereikėtų skaičiuoti išvestinės, Niutono metodą galima supaprastinti, pakeičiant išvestinę apytikslę vertę, apskaičiuotą iš ankstesnių dviejų taškų:

Iteracinis procesas atrodo taip:

Tai dviejų pakopų kartotinis procesas, nes jis naudoja ankstesnius du, kad surastų kitą aproksimaciją.

Sekantinio metodo konvergencijos tvarka yra mažesnė nei tangentinio metodo ir yra lygi vienos šaknies atveju.

Šis puikus dydis vadinamas auksiniu pjūviu:

Patikrinkime tai, patogumo dėlei darydami prielaidą, kad .

Taigi, iki aukštesnės eilės begalinių mažųjų

Atmetus likusį terminą, gauname pasikartojimo ryšį, kurio sprendimo natūraliai ieškoma formoje .

Po pakeitimo turime: ir

Konvergencijai būtina, kad ji būtų teigiama, todėl .

Kadangi išvestinės žinios nebūtinos, taikant tą patį skaičiavimų skaičių sekantiniu metodu (nepaisant mažesnės konvergencijos eilės), galima pasiekti didesnį tikslumą nei naudojant tangentinį metodą.

Atkreipkite dėmesį, kad šalia šaknies reikia dalyti iš nedidelio skaičiaus, o tai praranda tikslumą (ypač kelių šaknų atveju), todėl pasirinkę palyginti nedidelį skaičių, prieš atlikdami atlikite skaičiavimus ir tęskite juos tol, kol gretimų aproksimacijų skirtumo modulis sumažės.

Kai tik prasideda augimas, skaičiavimai sustabdomi ir paskutinė iteracija nenaudojama.

Ši iteracijų pabaigos nustatymo procedūra vadinama technika Garvika.

Parabolės metodas

Panagrinėkime trijų pakopų metodą, kai aproksimacija nustatoma pagal tris ankstesnius taškus ir .

Norėdami tai padaryti, funkciją, panašiai kaip sekantinis metodas, pakeičiame interpoliacijos parabole, einančia per taškus ir .

Niutono pavidalu tai atrodo taip:

Taškas apibrėžiamas kaip viena iš šio daugianario šaknų, kuri absoliučia verte yra arčiau taško.

Parabolės metodo konvergencijos tvarka yra didesnė nei sekantinio metodo, bet mažesnė nei Niutono metodo.

Svarbus skirtumas nuo anksčiau svarstytų metodų yra tai, kad net jei realus už realų ir pradinės aproksimacijos pasirenkamos kaip tikros, parabolės metodas gali sukelti sudėtingą pradinės problemos šaknį.

Šis metodas yra labai patogus ieškant aukšto laipsnio daugianario šaknis.

Paprastas iteracijos metodas

Lygčių sprendinių paieškos problemą galima suformuluoti kaip šaknų radimo problemą: , arba kaip fiksuoto taško radimo problemą.

Leisti ir - suspaudimas: (ypač tai, kad - suspaudimas, kaip lengva suprasti, tai reiškia).

Pagal Banacho teoremą yra unikalus fiksuotas taškas

Tai galima rasti kaip paprastos kartotinės procedūros ribą

kur pradinė aproksimacija yra savavališkas intervalo taškas.

Jei funkcija yra diferencijuojama, patogus suspaudimo kriterijus yra skaičius . Iš tiesų, pagal Lagrange’o teoremą

Taigi, jei išvestinė yra mažesnė už vieną, tai yra suspaudimas.

Būklė yra esminis, nes jei, pavyzdžiui, on , tai fiksuoto taško nėra, nors išvestinė lygi nuliui. Konvergencijos greitis priklauso nuo reikšmės. Kuo mažesnis, tuo greitesnis konvergencija.

Fizikinės chemijos katedra SFU (RSU)
SKAITINIAI METODAI IR PROGRAMAVIMAS
Medžiaga paskaitų kursui
Lektorius – str. Rev. Ščerbakovas I. N.

Netiesinių lygčių sistemos

Sprendžiant cheminių sistemų elgsenos modeliavimo uždavinius, dažnai reikia spręsti lygčių sistemas, kurios yra netiesinės kintamųjų atžvilgiu. Sistemos n Tiesinės lygtys su n nežinomųjų x 1, x 2, ..., x n paprastai rašomos taip:

kur F 1, F 2,..., F n yra bet kokios nepriklausomų kintamųjų funkcijos, įskaitant ir netiesines nežinomųjų atžvilgiu.

Kaip ir tiesinių lygčių sistemų atveju, sistemos sprendimas yra vektorius (arba vektoriai) (X *), kuris pakeitus visas sistemos lygtis vienu metu paverčia tapatybėmis.

Lygčių sistema gali neturėti sprendinių, turėti vieną sprendinį, baigtinį arba begalinį sprendinių skaičių. Sprendimų skaičiaus klausimas turi būti sprendžiamas kiekvienai konkrečiai problemai atskirai.

Panagrinėkime kelis paprasčiausius iteracinius netiesinių lygčių sistemų sprendimo metodus, būtent paprastą iteracijos metodą, Seidelio metodą ir Niutono metodą.

Paprastas iteracijos metodas

Norint įgyvendinti šį metodą, sprendžiamų lygčių sistema turi būti suformuota į tokią formą algebrinėmis transformacijomis, išreiškiant po vieną kintamąjį iš kiekvienos lygties taip:

Tada pasirenkamas pradinis aproksimacijos vektorius

pakeiskite jį į transformuotą lygčių sistemą. Iš pirmosios lygties gaunamas naujas pirmojo kintamojo aproksimacija, iš antrosios - antrojo ir tt Gauta patikslinta kintamųjų reikšmė vėl pakeičiama į šias lygtis ir tt Taigi, (i+1) žingsnyje iš kartotinės procedūros, kurią turime

Seidelio metodas

„Seidel“ paprasto iteracijos algoritmo modifikaciją sudaro patobulintų kintamųjų verčių naudojimas jau dabartiniame iteracijos etape. Taigi, norint išsiaiškinti pirmojo kintamojo reikšmes, naudojamos tik ankstesnio žingsnio reikšmės, antrajam kintamajam - dabartinio žingsnio reikšmė x 1, o likusios - iš ankstesnio ir kt. :

Niutono-Rafsono metodas

Matematinis metodo pagrindas yra funkcijų tiesinimas F 1 , F 2 , Fn (susidarančios lygčių kairiosios pusės), išplečiant į Teiloro eilutę netoli pradinio priartėjimo prie sprendinio taško ir neatsižvelgiant į visas eilutės sąlygas, išskyrus tiesines. prieaugiais kintamieji.

Panagrinėkime metodą naudodami dviejų lygčių su dviem nežinomaisiais sistemos pavyzdį:

Linearizuokime funkcijas F 1 , F 2 išplečiant Taylor eilutę netoli tam tikro taško (pradinis aproksimacija) ir nepaisant visų eilutės sąlygų, išskyrus tiesines kintamųjų prieaugio atžvilgiu.

Prisiminkite, kad vieno kintamojo funkcijai Taylor serijos išplėtimas, esantis šalia kurio nors taško x 0, turi tokią formą:

nepaisydami visų terminų, išskyrus linijinį:

Kelių kintamųjų funkcijai išplėtimas atliekamas panašiai.

Norėdami rasti lygčių sistemos sprendimą, parinkkime tam tikrą pradinį aproksimaciją

Parašykime funkciją F 1 2 kintamoji linijinė Taylor serijos išplėtimo dalis šalia pasirinkto taško

antrosios lygties atveju, panašiai

Jei kintamųjų reikšmės x 1 Ir x 2 yra sprendimas, tada abi sistemos lygtys turi išnykti, todėl gautus išplėtimus prilyginsime nuliui.

Trumpumo dėlei pateikiame tokį užrašą:

I-ojo kintamojo padidėjimas

Funkcijos pirmosios dalinės išvestinės reikšmė F j pagal kintamąjį x i kintamųjų reikšme

– j-osios funkcijos reikšmė su atitinkamomis kintamųjų reikšmėmis, tai yra, j-osios lygties neatitikimas.

Gauname tiesinių lygčių 2 x 2 sistemą kintamųjų prieaugio atžvilgiu

Arba matricos forma

kur dalinių išvestinių verčių matrica vadinama Jacobi matrica (arba jakobiečių). Šios sistemos sprendimas suteikia pradinės aproksimacijos pataisų vektorių.

Pridėjus jį prie pradinio aproksimacijos vektoriaus, gaunamos naujos kintamųjų reikšmės.

Taigi, sprendimo procedūra yra tokia:

1. Pasirinkta pradinė aproksimacija, sistema redukuojama į normaliąją formą ir analitine forma randamos sistemos lygčių dešiniųjų pusių dalinės išvestinės visų kintamųjų atžvilgiu.

2. Apskaičiuojama dalinių išvestinių verčių Jakobijos matrica pradinio aproksimavimo taške

3. Išspręsta tiesinių lygčių sistema kintamųjų prieaugiams.

4. prie pradinio aproksimacijos vektoriaus pridedamas prieaugio vektorius

5. Patikrinama konvergencijos sąlyga ir, jei ji nepasiekiama, procedūra kartojama nuo 2 veiksmo.

Metodas lengvai apibendrinamas bet kokio matmens lygčių sistemai.

Funkcijai F 1 n kintamieji yra tiesinė Taylor serijos išplėtimo dalis taško kaimynystėje parašyta šitaip

Išskaidžius visas sistemos lygtis ir panaudojus anksčiau įvestą žymėjimą, po transformacijos gauname n eilės tiesinių lygčių sistemą kintamųjų prieaugio Δ x i atžvilgiu.

Arba matricos forma

Sutrumpintai galime parašyti taip - (F" )(Δ x ) = - (F ) , kur vadinama dalinių išvestinių reikšmių matrica - (F" ) - Jakobijos matrica arba jakobiečių lygčių sistemos.

Šios sistemos sprendimas suteikia pradinės aproksimacijos pataisų vektorių. Pridėjus jį prie pradinio aproksimacijos vektoriaus, gaunamos naujos, patobulintos kintamųjų reikšmės.

Skaičiavimui reikalingos dalinės išvestinės priemonės Jakobijos matricos, gali būti apskaičiuotas analitiškai arba, jei tai neįmanoma arba sunku, gauti naudojant apytiksles diferenciacijos formules, pavyzdžiui, kaip funkcijos padidėjimo ir argumento prieaugio santykį.

Kur epsilonas– gana mažas skaičius.

Iteracinių metodų konvergencijos valdymo metodai
sistemų sprendimai

Iteratyvaus netiesinių lygčių sistemos sprendimo proceso konvergencija gali būti kontroliuojama keliais būdais, pavyzdžiui:

1. Liekamojo vektoriaus norma (euklidinis arba -maksimumas).

2. Kintamųjų santykinių nuokrypių vektoriaus euklidinė norma

3. Norma-maksimalus santykinių nuokrypių vektorius

Lygčių sistemai išspręsti pritaikykime Niutono metodą

Dalinė išvestinė matrica (analitinės formos)

Tiesinių lygčių sistema

Galima išspręsti analitiškai arba Cramerio metodu arba matricos inversijos metodu. Paimkime pradinį aproksimaciją x = 0,15, y = 0,17

Pirma iteracija:

Jacobi matrica - Funkcijos reikšmių vektorius Apskaičiuotas pataisų vektorius Naujas aproksimacija x = 0,15 + 0,028704 = 0,178704, y = 0,17 + 0,090926 = 0,260926 Antroji iteracija: Apskaičiuotas korekcijos vektorius Nauja aproksimacija x = 0,196656, y = 0,293359 Trečias pakartojimas: Apskaičiuotas pataisos vektorius Nauja aproksimacija x = 0,199867, y = 0,299739 Jau 6-oje iteracijoje liekamojo vektoriaus Euklido norma yra 2,8∙10 -13, maksimalus santykinis kintamųjų pokytis yra 1,6∙10, o sprendimas yra -12. = 0,2 , y = 0,3, kai absoliuti paklaida mažesnė nei 5∙10 -7. Paprastas iteracijos metodas tomis pačiomis pradinėmis sąlygomis susilieja tokiu pačiu tikslumu 33 žingsnyje, Seidel modifikacija - 31 žingsnyje. Žemiau esančiame paveikslėlyje parodytas skaičiavimų organizavimo pavyzdys sprendžiant nagrinėjamą sistemą MS Excel.
Paaiškinimai: Ląstelėse B3 ir B4 yra pradinės sistemos sprendimo apytikslės reikšmės (atitinkamai x 0 ir y 0). D3:E4 langelių diapazone yra Jakobijos matricos skaičiavimo formulės, jei x yra langelyje B3, o y yra langelyje B4 (formulės parodytos paveikslėlyje žemiau). Ląstelėse G3:G4 apskaičiuojama likučių su neigiamu ženklu vektoriaus reikšmė.
Ląstelėje H3 apskaičiuojama liekamojo vektoriaus Euklido norma. Ląstelėse I3:I4 sprendžiama tiesinių lygčių sistema ir apskaičiuojamas sprendinio pataisų vektorius. Tam sistemos koeficientų matrica (Jacobi matrica) apverčiama ir padauginama iš laisvųjų dėmenų stulpelio vektoriaus (neigiamas likučių vektorius). Šio langelių diapazono formulė įvedama kaip masyvo formulė. Netoliese – langelyje J3 – apskaičiuojama korekcijos vektoriaus norma konvergencijai kontroliuoti (žr. toliau pateiktame paveikslėlyje esančias formules).
Korekcinės reikšmės, gautos langeliuose I3:I4 antrajame iteracijos cikle, pridedamos prie pradinio aproksimacijos (ląstelėse B6:B7), o tada skaičiavimai kartojami panašiai kaip ir pirmame cikle. Darbo lapo 6 ir 7 eilutėse įvestas formules galima kopijuoti tol, kol bus pasiektas reikiamas tikslumas.

Uždaviniai, redukuojami į netiesinių lygčių sistemos sprendimą

Problemos, kurioje naudojamas netiesinių lygčių sistemų sprendimas, pavyzdys yra lentelėje nurodytos funkcijos aproksimacija naudojant matematinius modelius, kurie yra netiesiniai parametrų atžvilgiu. Tai buvo išsamiai aprašyta anksčiau. Jei aproksimacinė funkcija ir ją apibrėžiantys parametrai a i paskirti taip tada funkcijos grafiko perėjimo per visus lentelės taškus sąlygą galima parašyti tokios sistemos forma: Kitas pavyzdys – kelių kintamųjų funkcijos ekstremumo (minimalaus arba didžiausio) paieška Ekstremo sąlyga – visų funkcijos dalinių išvestinių lygiagreti lygybė nuliui. Taigi reikia išspręsti tokios formos lygčių sistemą, kuri bendru atveju bus netiesinė

Paprastas iteracijos metodas, dar vadinamas nuosekliuoju aproksimacijos metodu, yra matematinis algoritmas, skirtas rasti nežinomo dydžio vertę palaipsniui jį tobulinant. Šio metodo esmė yra ta, kad, kaip rodo pavadinimas, palaipsniui išreiškiant vėlesnius iš pradinio aproksimavimo, gaunami vis tobulesni rezultatai. Šis metodas naudojamas ieškant tam tikros funkcijos kintamojo reikšmės, taip pat sprendžiant lygčių sistemas, tiek tiesines, tiek netiesines.

Panagrinėkime, kaip šis metodas įgyvendinamas sprendžiant SLAE. Paprastas iteracijos metodas turi tokį algoritmą:

1. Konvergencijos sąlygos įvykdymo tikrinimas pradinėje matricoje. Konvergencijos teorema: jei pradinė sistemos matrica turi įstrižainės dominavimą (t. y. kiekvienoje eilutėje pagrindinės įstrižainės elementai turi būti didesni absoliučia verte nei antrinių įstrižainių elementų suma absoliučia verte), tai paprasta iteracijos metodas yra konvergentinis.

2. Pirminės sistemos matrica ne visada turi įstrižainės dominavimą. Tokiais atvejais sistema gali būti konvertuojama. Lygtys, kurios tenkina konvergencijos sąlygą, paliekamos nepaliestos, o tiesinės kombinacijos daromos su netenkinančiomis, t.y. dauginti, atimti, sudėti lygtis viena su kita, kol gaunamas norimas rezultatas.

Jei gautoje sistemoje pagrindinėje įstrižainėje yra nepatogūs koeficientai, tai formos terminai su i * x i pridedami prie abiejų tokios lygties pusių, kurių ženklai turi sutapti su įstrižainių elementų ženklais.

3. Gautos sistemos pavertimas normalia forma:

x - =β - +α*x -

Tai galima padaryti įvairiais būdais, pavyzdžiui, taip: iš pirmosios lygties išreikškite x 1 kitų nežinomųjų atžvilgiu, iš antrosios - x 2, iš trečiosios - x 3 ir tt. Šiuo atveju naudojame formules:

α ij = -(a ij / a ii)

i = b i /a ii
Turėtumėte dar kartą įsitikinti, kad gauta normalios formos sistema atitinka konvergencijos sąlygą:

∑ (j=1) |α ij |≤ 1, o i = 1,2,...n

4. Iš tikrųjų pradedame taikyti patį nuosekliųjų aproksimacijų metodą.

x (0) yra pradinis aproksimacija, per jį išreikšime x (1), tada išreikšime x (2) per x (1). Bendroji formulė matricos pavidalu atrodo taip:

x (n) = β – +α*x (n-1)

Skaičiuojame, kol pasieksime reikiamą tikslumą:

max |x i (k)-x i (k+1) ≤ ε

Taigi, įgyvendinkime paprastą iteracijos metodą. Pavyzdys:
Išspręskite SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 tikslumu ε=10 -3

Pažiūrėkime, ar modulyje vyrauja įstrižainės.

Matome, kad tik trečioji lygtis tenkina konvergencijos sąlygą. Paverskime pirmąjį ir antrąjį, o antrąjį pridėkime prie pirmosios lygties:

7,6x1+0,6x2+2,4x3=3

Iš trečiojo atimame pirmąjį:

2,7x1+4,2x2+1,2x3=2

Pradinę sistemą pavertėme lygiaverte:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Dabar grąžinkime sistemą į įprastą formą:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3 = 0,8511-0,383x1-0,5319x2

Mes patikriname iteracinio proceso konvergenciją:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, t.y. sąlyga įvykdyta.

0,3947
Pradinis spėjimas x(0) = 0,4762
0,8511

Pakeitę šias reikšmes į normalios formos lygtį, gauname šias reikšmes:

0,08835
x(1) = 0,486793
0,446639

Pakeisdami naujas reikšmes, gauname:

0,215243
x(2) = 0,405396
0,558336

Tęsiame skaičiavimus, kol pasiekiame reikšmes, kurios atitinka nurodytą sąlygą.

x (7) = 0,441091

Patikrinkime gautų rezultatų teisingumą:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Rezultatai, gauti pakeitus rastas reikšmes į pradines lygtis, visiškai atitinka lygties sąlygas.

Kaip matome, paprastas iteracijos metodas duoda gana tikslius rezultatus, tačiau norint išspręsti šią lygtį, teko sugaišti daug laiko ir atlikti sudėtingus skaičiavimus.