Reševanje nelinearnih enačb

Recimo, da moramo rešiti enačbo

kje
– nelinearna zvezna funkcija.

Metode za reševanje enačb delimo na neposredne in iterativne. Neposredne metode so metode, ki vam omogočajo izračun rešitve z uporabo formule (na primer iskanje korenin kvadratne enačbe).

Iterativne metode so metode, pri katerih je določen začetni približek in konstruirano konvergentno zaporedje približkov k natančni rešitvi, pri čemer je vsak naslednji približek izračunan z uporabo prejšnjih

Celovito rešitev problema lahko razdelimo na 3 stopnje:

Določite število, naravo in lokacijo korenin enačbe (1).

Poiščite približne vrednosti korenin, tj.

navedite intervale, v katerih bodo korenine rasle (ločite korenine).

Poiščite vrednost korenin z zahtevano natančnostjo (določite korenine).
Za reševanje prvih dveh problemov obstajajo različne grafične in analitične metode. Najbolj očitna metoda za ločevanje korenin enačbe (1) je določitev koordinat presečišč grafa funkcije
z abscisno osjo. Abscise
presečišča grafov

z osjo

so koreni enačbe (1)
Izolacijske intervale za korenine enačbe (1) lahko dobimo analitično na podlagi izrekov o lastnostih funkcij, zveznih na intervalu.
Če je npr
neprekinjeno na segmentu
in

, nato v skladu z Bolzano–Cauchyjevim izrekom na segmentu
obstaja vsaj en koren enačbe (1) (liho število korenov).
Če funkcija
izpolnjuje pogoje Bolzano-Cauchyjevega izreka in je monoton na tem intervalu, potem na

obstaja samo en koren enačbe (1). Tako ima enačba (1).

en sam koren, če so izpolnjeni naslednji pogoji:

Če je funkcija zvezno diferencibilna na danem intervalu, potem lahko uporabimo posledico iz Rollejevega izreka, po katerem je med parom korenin vedno vsaj ena stacionarna točka. Algoritem za rešitev problema v tem primeru bo naslednji:

Uporabno orodje za ločevanje korenov je tudi uporaba Sturmovega izreka. Rešitev tretjega problema se izvaja z različnimi iterativnimi (numeričnimi) metodami: metoda dihotomije, metoda preproste iteracije, Newtonova metoda, metoda akordov itd.
Primer Rešimo enačbo metoda
. Zgradimo graf funkcije.

Graf kaže, da koren naše enačbe pripada segmentu
, tj.
je izolacijski segment korena naše enačbe. Preverimo to analitično, tj. izpolnjevanje pogojev (2):

Spomnimo se, da se izvirna enačba (1) v metodi enostavne iteracije pretvori v obliko
in ponovitve se izvajajo po formuli:

(3)

Izvajanje izračunov z uporabo formule (3) se imenuje ena iteracija. Ponovitve se ustavijo, ko je pogoj izpolnjen
, Kje - absolutna napaka pri iskanju korena, oz
, Kje - relativna napaka.

Metoda preproste iteracije konvergira, če je pogoj izpolnjen
Za
. Izbira funkcije
v formuli (3) za iteracije lahko vplivate na konvergenco metode. V najpreprostejšem primeru
z znakom plus ali minus.

V praksi se pogosto izraža
neposredno iz enačbe (1). Če konvergenčni pogoj ni izpolnjen, ga transformirajte v obliko (3) in ga izberite. Predstavimo našo enačbo v obliki
(iz enačbe izrazi x). Preverimo konvergenčni pogoj metode:

Za
. Upoštevajte, da pogoj konvergence ni izpolnjen
, zato vzamemo segment korenske izolacije
. Mimogrede opazimo, da pri predstavitvi naše enačbe v obliki
, konvergenčni pogoj metode ni izpolnjen:
na segmentu
. Graf to kaže
narašča hitreje kot funkcija
(|tg| kot naklona tangente na
na segmentu
)

Izberimo
. Iteracije organiziramo po formuli:

Proces iteracije programsko organiziramo z dano natančnostjo:

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

> k:=0:

x:=x1+1:

medtem ko abs(x1-x)> eps

x1:=f1(x):

natisni (evalf (x1,8)):

natisni (abs(x1-x)):

:printf("Število iter.=%d ",k):

konec:

Pri iteraciji 19 smo dobili koren naše enačbe

z absolutno napako

Rešimo našo enačbo Newtonova metoda. Ponovitve v Newtonovi metodi se izvajajo po formuli:

Newtonovo metodo lahko obravnavamo kot metodo enostavne iteracije s funkcijo, potem bo pogoj za konvergenco Newtonove metode zapisan kot:

.

V našem zapisu
in konvergenčni pogoj je na segmentu izpolnjen
, kot je razvidno iz grafa:

Spomnimo se, da Newtonova metoda konvergira s kvadratno hitrostjo in da mora biti začetni približek izbran dovolj blizu korenu. Naredimo izračune:
, začetni približek, . Iteracije organiziramo po formuli:

Proces iteracije programsko organiziramo z dano natančnostjo. Pri iteraciji 4 dobimo koren enačbe

z
Ogledali smo si metode za reševanje nelinearnih enačb na primeru kubičnih enačb; seveda te metode rešujejo različne vrste nelinearnih enačb. Na primer, reševanje enačbe

Newtonova metoda z
, poiščite koren enačbe pri [-1,5;-1]:

telovadba: Natančno rešite nelinearne enačbe

0.

delitev segmenta na pol (dihotomija)

preprosta ponovitev.

Newton (tangente)

sekante - akordi.

Možnosti nalog se izračunajo na naslednji način: število na seznamu se deli s 5 (
), celo število ustreza številki enačbe, preostanek pa številki metode.

LABORATORIJSKO DELO št. 3-4.

Možnost št. 5.

Namen dela: naučijo se reševati sisteme nelinearnih enačb (SNE) z metodo preproste iteracije (SI) in Newtonovo metodo z uporabo računalnika.

1. Preučite MPI in Newtonovo metodo za reševanje sistemov nelinearnih enačb.

2. Na konkretnem primeru spoznajte postopek reševanja sistemov nelinearnih enačb z MPI in Newtonovo metodo z uporabo računalnika.

3. Ustvarite program in z njim rešite sistem enačb z natančnostjo .

PRIMER DELOVNE USPEŠNOSTI

telovadba.

1. Analitično rešite SNE:

2. Sestavite delovne formule MPI in Newtonove metode za numerično rešitev sistema v začetnem približku: .

3. Sestavite program v poljubnem programskem jeziku, ki izvaja konstruirani iterativni proces.

rešitev.

Analitična metoda.

Analitična rešitev SDE je točka in .

Metoda preprostih iteracij (SIM).

Za sestavo delujočih formul MPI za numerično rešitev sistema jo je treba najprej pripeljati do oblike:

Če želite to narediti, pomnožite prvo enačbo sistema z neznano konstanto, drugo z , nato ju seštejte in dodajte obema stranema enačbe. Dobimo prvo enačbo transformiranega sistema:

Neznane konstante določimo iz zadostnih pogojev za konvergenco iterativnega procesa:

Zapišimo te pogoje podrobneje:

Ob predpostavki, da so izrazi pod znakom modula enaki nič, dobimo sistem linearnih algebrskih enačb (SLAE) 4. reda s 4 neznankami:

Za rešitev sistema je potrebno izračunati delne odvode:

Potem bo SLAE zapisan takole:

Upoštevajte, da če se delni odvodi malo spremenijo v bližini začetnega približka, potem:

Potem bo SLAE zapisan takole:

Rešitev tega sistema so točke , , , . Nato bodo delovne formule MPI za reševanje SNL dobile obliko:

Za izvedbo v računalniku lahko delovne formule prepišemo na naslednji način:

Iterativni proces se lahko začne z nastavitvijo začetnega približka x 0 =-2, y 0 =-4. Proces se konča, ko sta hkrati izpolnjena dva pogoja: in . V tem primeru sta vrednosti in približna vrednost ene od rešitev SNL.

Newtonova metoda.

Izdelati delovne formule za Newtonovo metodo v obliki

kjer je potrebno:

1. Poiščite matriko delnih odvodov:

2. Poiščite determinanto te matrike:

3. Definirajte inverzno matriko:

Po izvedbi preobrazbe:

Dobimo delovno formulo Newtonove metode za izvedbo na računalniku:

Blok diagram MPI in Newtonova metoda za reševanje SLE sta prikazana na sliki 1.

Sl.1 Sheme MPI in Newtonove metode.

Programska besedila:

Program P3_4; (Ponovitve)

uporablja Crt;

var n: celo število;

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;

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

readln;

2) Newtonova metoda:

Program P3_4; (Newton)

uporablja Crt;

var n: celo število;

x0,x,xn,y0,y,yn,eps,zx,zy:resnično;

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;

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

Rezultati izvajanja programa:

· Slika 2 – program, ki deluje po metodi preprostih iteracij;

· Slika 3 – program, ki deluje po Newtonovi metodi.

Slika 2 Odgovor: x(16)≈-3,00023, y(16)≈-1,00001

Slika 3 Odgovor: x(8)≈-3,00000, y(8)≈-1,00000

Vsi ljudje po naravi težimo k znanju. (Aristotel. Metafizika)

Numerične metode: reševanje nelinearnih enačb

Težave reševanja enačb se v praksi nenehno pojavljajo, na primer v ekonomiji, ko razvijate podjetje, želite vedeti, kdaj bo dobiček dosegel določeno vrednost, v medicini, ko proučujete učinke zdravil, je pomembno vedeti, kdaj koncentracija snovi bo dosegla določeno raven itd.

Pri optimizacijskih problemih je pogosto treba določiti točke, v katerih odvod funkcije postane 0, kar je nujen pogoj lokalni ekstrem.

V statistiki morate pri konstruiranju ocen z uporabo metode najmanjših kvadratov ali največje verjetnosti rešiti tudi nelinearne enačbe in sisteme enačb.

Tako se pojavi cel razred problemov, povezanih z iskanjem rešitev nelinearno enačbe, kot so enačbe ali enačbe itd.

V najpreprostejšem primeru imamo funkcijo definirano na intervalu ( a, b) in ob določenih vrednostih.

Vsaka vrednost x iz tega segmenta lahko primerjamo število, to je funkcionalno odvisnost, ključni koncept v matematiki.

Najti moramo vrednost, pri kateri se ti imenujejo koreni funkcije

Vizualno moramo določiti presečišče funkcijskega grafaz abscisno osjo.

Metoda razpolovitve

Najenostavnejša metoda iskanja korenov enačbe je metoda razpolovitve oz dihotomija.

Ta metoda je intuitivna in vsak bi ravnal na podoben način pri reševanju problema.

Algoritem je naslednji.

Recimo, da najdemo dve točki in , Tako da imajo drugačen znaki, potem je med tema točkama vsaj en koren funkcije.

Razdelimo segment na pol in vstopimo povprečje točka .

Potem bodisi , oz .

Pustimo tisto polovico segmenta, za katero imajo vrednosti na koncih različne znake. Zdaj ta segment ponovno razdelimo na polovico in pustimo tisti del, na mejah katerega ima funkcija različne predznake in tako naprej, da dosežemo zahtevano natančnost.

Očitno bomo postopoma zožili območje, kjer se nahaja koren funkcije, in ga bomo zato določili z določeno stopnjo natančnosti.

Upoštevajte, da je opisani algoritem uporaben za katero koli zvezno funkcijo.

Prednosti metode razpolovitve so njena visoka zanesljivost in enostavnost.

Pomanjkljivost metode je dejstvo, da morate, preden jo začnete uporabljati, najti dve točki, kjer imata funkcijski vrednosti različne znake. Očitno je, da metoda ni uporabna za sode množinske korene in je tudi ni mogoče posplošiti na primer kompleksnih korenin in na sisteme enačb.

Vrstni red konvergence metode je linearen, pri vsakem koraku se natančnost podvoji; čim bolj natančno je določen koren.

Newtonova metoda: teoretične osnove

Newtonova klasična metoda oz tangente je, da je if nek približek korenu enačbe , potem je naslednji približek definiran kot koren tangente na funkcijo, narisano v točki .

Tangentna enačba na funkcijo v točki ima obliko:

V tangentni enačbi postavimo in .

Potem je algoritem za zaporedne izračune v Newtonovi metodi naslednji:

Konvergenca tangentne metode je kvadratna, vrstni red konvergence je 2.

Tako je konvergenca Newtonove tangentne metode zelo hitra.

Zapomnite si to čudovito dejstvo!

Brez sprememb je metoda posplošena na kompleksen primer.

Če je koren koren druge množitve ali višje, se vrstni red konvergence zmanjša in postane linearen.

1. vaja. Z metodo tangente poiščite rešitev enačbe na odseku (0, 2).

vaja 2. Z metodo tangente poiščite rešitev enačbe na odseku (1, 3).

Slabosti Newtonove metode so njena lokalnost, saj je zagotovljena konvergacija za poljuben začetni približek le, če je pogoj povsod izpolnjen , v nasprotnem primeru pride do konvergence le v določeni okolici korena.

Pomanjkljivost Newtonove metode je potreba po izračunu derivatov na vsakem koraku.

Vizualizacija Newtonove metode

Newtonova metoda (tangentna metoda) se uporablja, če enačba f(x) = 0 ima koren in so izpolnjeni naslednji pogoji:

1) funkcija l= f(x) definiran in zvezen pri ;

2) f(a)· f(b) < 0 (funkcija zavzame vrednosti različnih predznakov na koncih segmenta [ a; b]);

3) izvedeni finančni instrumenti f"(x) in f""(x) ohrani znak na intervalu [ a; b] (tj. funkcija f(x) poveča ali zmanjša na segmentu [ a; b], ob ohranjanju smeri konveksnosti);

Glavna ideja metode je naslednja: na segmentu [ a; b] je izbrana taka številka x 0 , pri kateri f(x 0 ) ima isti znak kot f"" (x 0 ), torej je pogoj izpolnjen f(x 0 )· f"" (x) > 0 . Tako je izbrana točka z absciso x 0 , v kateri je tangenta na krivuljo l= f(x) na segmentu [ a; b] seka os Ox. Na točko x 0 Najprej je priročno izbrati enega od koncev segmenta.

Oglejmo si Newtonovo metodo na konkretnem primeru.

Naj nam bo dana vedno večja funkcija y = f(x) =x 2 -2, zvezna na segmentu (0;2) in ima f"(x) = 2 x > 0 in f "" (x) = 2 > 0 .

risanje1 . f(x) =x 2 -2

Tangentna enačba ima v splošni obliki naslednjo predstavitev:

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

V našem primeru: y-y 0 =2x 0 ·(x-x 0). Za točko x 0 izberemo točko B 1 (b; f(b)) = (2,2). Narišite tangento na funkcijo y = f(x) v točki B 1 in označite presečišče tangente in osi Ox pika x 1. Dobimo enačbo prve tangente: y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

risanje2. Rezultat prve ponovitve

y=f(x) Ox skozi točko x 1, razumemo bistvo B 2 =(1,5; 0,25). Ponovno nariši tangento na funkcijo y = f(x) v točki B 2 in označite presečišče tangente in osi Ox pika x 2.

Enačba druge tangente: l-0.25=2*1.5(x-1.5), l = 3 x - 4.25.

Presečišče tangente in osi Ox: x 2 =.

risanje3. Druga ponovitev Newtonove metode

Nato poiščemo presečišče funkcije y=f(x) in na os narisano navpičnico Ox skozi točko x 2 dobimo točko B 3 in tako naprej.

risanje4. Tretji korak tangentne metode

Prvi približek korena je določen s formulo:

= 1.5.

Drugi približek korena je določen s formulo:

=

Tretji približek korena je določen s formulo:

torej , i Približek korena je določen s formulo:

Izračuni se izvajajo, dokler se decimalna mesta, ki jih potrebuje odgovor, ne ujemajo, oziroma dokler ni dosežena podana natančnost e – dokler ni izpolnjena neenakost | xi- xi-1 | < e.

V našem primeru primerjajmo približek, dobljen v tretjem koraku, z realnim odgovorom, izračunanim na kalkulatorju:

Slika 5. Koren iz 2, izračunan na kalkulatorju

Kot lahko vidite, smo že pri tretjem koraku prejeli napako manjšo od 0,000002.

Na ta način lahko izračunate vrednost "kvadratnega korena iz 2" s poljubno stopnjo natančnosti. To izjemno metodo je izumil Newton in omogoča iskanje korenin zelo zapletenih enačb.

Newtonova metoda: uporaba v C++

V tem članku bomo avtomatizirali postopek izračunavanja korenov enačb s pisanjem konzolne aplikacije v C++. Razvili ga bomo v Visual C++ 2010 Express, to je brezplačno in zelo priročno razvojno okolje C++.

Najprej zaženimo Visual C++ 2010 Express. Prikaže se okno za zagon programa. V levem kotu kliknite »Ustvari projekt«.

riž. 1. Domača stran Visual C++ 2010 Express

V meniju, ki se prikaže, izberite “Win32 Console Application” in vnesite ime aplikacije “Newton_Method”.

riž. 2. Ustvarite projekt

// Metoda Newton.cpp: definira vstopno točko za konzolno aplikacijo #vključi "stdafx.h" #vključi uporaba imenskega prostora std; float f(double x) //vrne vrednost funkcije f(x) = x^2-2 float df(float x) //vrne izpeljano vrednost float d2f(float x) // vrednost drugega derivata int _tmain(int argc, _TCHAR* argv) int izhod = 0, i=0;//spremenljivke za izhod in zanko dvojni x0,xn;//izračunani približki za koren dvojni a, b, eps; // meje segmenta in zahtevana natančnost cout<<"Please input \n=>"; cin>>a>>b; // vnesemo meje odseka, na katerem bomo iskali koren cout<<"\nPlease input epsilon\n=>"; cin>>eps; // vnesite zahtevano natančnost izračuna if (a > b) // če je uporabnik pomešal meje segmenta, jih zamenjaj if (f(a)*f(b)>0) // če so predznaki funkcije na robovih segmenta enaki, potem tukaj ni korena cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // za izbiro začetne točke označite f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // upoštevajte prvi približek cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // bo nadaljeval z izračunom, dokler ne dosežemo zahtevane natančnosti xn = x0-f(x0)/df(x0); // neposredno Newtonova formula cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) medtem ko (izhod!=1); // dokler uporabnik ne vnese exit = 1

Poglejmo, kako deluje. Kliknite na zeleni trikotnik v zgornjem levem kotu zaslona ali pritisnite tipko F5.

Če pride do napake pri prevajanju »Napaka napake LNK1123: neuspešna pretvorba v COFF: datoteka je neveljavna ali poškodovana,« je to mogoče odpraviti z namestitvijo prvega servisnega paketa 1 ali v nastavitvah projekta Lastnosti -> Povezovalnik, ki onemogoči inkrementalno povezovanje.

riž. 4. Odpravljanje napake pri prevajanju projekta

Iskali bomo korenine funkcije f(x) =x2-2.

Najprej preverimo delovanje aplikacije na “napačnih” vhodnih podatkih. Na segmentu ni korenin, naš program bi moral prikazati sporočilo o napaki.

Zdaj imamo okno aplikacije:

riž. 5. Vnos vhodnih podatkov

Vstavimo meje segmenta 3 in 5, natančnost pa je 0,05. Program je po pričakovanjih izdelal sporočilo o napaki, da na tem segmentu ni korenin.

riž. 6. Napaka "Na tem segmentu ni korenin!"

Ne bomo še odšli, kaj pa sporočilo "Izhod?" vnesite "0".

Zdaj pa preverimo aplikacijo s pravilnimi vhodnimi podatki. Vnesemo segment in natančnost 0,0001.

riž. 7. Izračun korena z zahtevano natančnostjo

Kot vidimo, je bila zahtevana natančnost dosežena že pri 4. ponovitvi.

Za izhod iz aplikacije vnesite »Exit?« => 1.

Metoda sekanta

Da bi se izognili izračunu odvoda, lahko Newtonovo metodo poenostavimo tako, da odvod zamenjamo s približkom, izračunanim iz prejšnjih dveh točk:

Iterativni postopek izgleda takole:

To je iterativni postopek v dveh korakih, ker uporablja prejšnja dva za iskanje naslednjega približka.

Vrstni red konvergence sekantne metode je nižji kot pri tangentni metodi in je enak v primeru enega korena.

Ta izjemna količina se imenuje zlati rez:

Preverimo to, pri čemer zaradi priročnosti predpostavimo, da .

Torej do infinitezimalij višjega reda

Če zavržemo preostali člen, dobimo povratno zvezo, katere rešitev seveda iščemo v obliki .

Po zamenjavi imamo: in

Za konvergenco je potrebno, da je pozitivna, torej .

Ker poznavanje odvoda ni potrebno, lahko z enako količino izračunov pri sekantni metodi (kljub nižjemu redu konvergence) dosežemo večjo natančnost kot pri tangentni metodi.

Upoštevajte, da morate blizu korena deliti z majhnim številom, kar vodi do izgube natančnosti (zlasti v primeru več korenin), zato, ko ste izbrali relativno majhno število, pred izvedbo izvedite izračune in jih nadaljujte, dokler se modul razlike med sosednjima približkoma ne zmanjša.

Takoj ko se začne rast, se izračuni ustavijo in zadnja ponovitev se ne uporabi.

Ta postopek za določanje konca iteracij se imenuje tehnika Garvika.

Metoda parabole

Oglejmo si tristopenjsko metodo, pri kateri je približek določen s tremi prejšnjimi točkami , in .

Da bi to naredili, zamenjamo, podobno kot pri metodi sekante, funkcijo z interpolacijsko parabolo, ki poteka skozi točki , in .

V Newtonovi obliki je videti takole:

Točka je definirana kot tista od korenin tega polinoma, ki je po absolutni vrednosti bližja točki.

Vrstni red konvergence metode parabole je višji kot pri metodi sekante, vendar nižji kot pri Newtonovi metodi.

Pomembna razlika od predhodno obravnavanih metod je dejstvo, da tudi če je realno za realno in so začetni približki izbrani kot realni, lahko metoda parabole vodi do kompleksnega korena prvotnega problema.

Ta metoda je zelo priročna za iskanje korenin polinomov visoke stopnje.

Enostavna iteracijska metoda

Problem iskanja rešitev enačb lahko formuliramo kot problem iskanja korenin: ali kot problem iskanja fiksne točke.

Naj in - stiskanje: (zlasti dejstvo, da - stiskanje, kot je lahko videti, pomeni to).

Po Banachovem izreku obstaja edinstvena fiksna točka

Najdemo ga kot mejo preprostega iterativnega postopka

kjer je začetni približek poljubna točka v intervalu.

Če je funkcija diferenciabilna, je primeren kriterij stiskanja število . Dejansko po Lagrangeovem izreku

Torej, če je izpeljanka manjša od ena, je to kompresija.

Pogoj je bistveno, ker če je na primer na , potem ni fiksne točke, čeprav je odvod enak nič. Hitrost konvergence je odvisna od količine. Manjši kot je , hitrejša je konvergenca.

Oddelek za fizikalno kemijo SFU (RSU)
NUMERIČNE METODE IN PROGRAMIRANJE
Gradivo za predavanje
Predavatelj – čl. Rev. Ščerbakov I.N.

Sistemi nelinearnih enačb

Pri reševanju problemov modeliranja obnašanja kemijskih sistemov je pogosto treba reševati sisteme enačb, ki so nelinearne glede na spremenljivke. Sistemi n

Linearne enačbe z n neznankami x 1, x 2, ..., x n so na splošno zapisane takole:

kjer so F 1, F 2,…, F n poljubne funkcije neodvisnih spremenljivk, vključno z nelinearnimi glede na neznanke.

Tako kot v primeru sistemov linearnih enačb je rešitev sistema vektor (ali vektorji) (X *), ki ob substituciji hkrati spremeni vse enačbe sistema v identitete.

Sistem enačb morda nima rešitev, lahko ima eno samo rešitev, končno ali neskončno število rešitev. Vprašanje števila rešitev je treba rešiti za vsak konkreten problem posebej.

Oglejmo si nekaj najpreprostejših iterativnih metod za reševanje sistemov nelinearnih enačb, in sicer metodo preproste iteracije, Seidelovo metodo in Newtonovo metodo.

Enostavna iteracijska metoda

Za izvedbo te metode je treba sistem enačb, ki jih je treba rešiti, z algebrskimi transformacijami prenesti v naslednjo obliko, pri čemer se ena spremenljivka iz vsake enačbe izrazi na naslednji način:

nadomestite v transformirani sistem enačb.

Iz prve enačbe dobimo nov približek prve spremenljivke, iz druge - druge, itd. Dobljena prečiščena vrednost spremenljivk se ponovno nadomesti v te enačbe itd. Tako je na (i+1) koraku iterativnega postopka, ki ga imamo

Seidelova metoda

Seidelova modifikacija algoritma preproste iteracije je sestavljena iz uporabe rafiniranih vrednosti spremenljivk že v trenutnem koraku iteracije.

Torej, za razjasnitev vrednosti prve spremenljivke se uporabljajo samo vrednosti prejšnjega koraka, za drugo spremenljivko - vrednost x 1 trenutnega koraka, ostalo pa iz prejšnjega itd. : Newton-Raphsonova metoda 1 , Newton-Raphsonova metoda 2 , Matematična osnova metode je linearizacija funkcij F Fn(nastanejo leve strani enačb) z razširitvijo v Taylorjevo vrsto v bližini točke začetnega pristopa k rešitvi in ​​zanemarimo vse člene serije razen linearnih glede na

povečanja

spremenljivke. Newton-Raphsonova metoda 1 , Newton-Raphsonova metoda 2 Oglejmo si metodo na primeru sistema dveh enačb z dvema neznankama:

Linearizirajmo funkcije

z razširitvijo v Taylorjevo vrsto blizu določene točke (začetni približek) in zanemarjanjem vseh členov vrste, razen tistih, ki so linearni glede na prirastke spremenljivk.

Spomnimo se, da ima za funkcijo ene spremenljivke razširitev Taylorjevega niza v okolici neke točke x 0 naslednjo obliko:

po zanemaritvi vseh členov razen linearnega:

Za funkcijo več spremenljivk se razširitev izvede podobno. Newton-Raphsonova metoda Za rešitev sistema enačb izberimo začetni približek

Napišimo za funkcijo

1 2-spremenljivi linearni del razširitve Taylorjevega niza v bližini izbrane točke x 1 za drugo enačbo, podobno x 2 Če so vrednosti spremenljivk

in

sta rešitev, potem morata obe enačbi sistema izginiti, zato nastale razširitve enačimo z nič.

Za kratkost uvajamo naslednji zapis: Newton-Raphsonova metoda Povečanje i-te spremenljivke

Vrednost prvega delnega odvoda funkcije

j s spremenljivko x i pri vrednosti spremenljivk

– vrednost j -te funkcije z ustreznimi vrednostmi spremenljivk, to je neskladje j -te enačbe.

Dobimo sistem linearnih enačb 2 x 2 glede na prirast spremenljivk Ali v matrični obliki, kjer se matrika vrednosti delnih odvodov imenuje Jacobijeva matrika (ali

jakobski

). Rešitev tega sistema daje vektor popravkov začetnega približka.

1. Izberemo začetni približek, sistem reduciramo na normalno obliko in parcialne odvode desnih strani enačb sistema glede na vse spremenljivke najdemo v analitični obliki.

2. Izračuna se Jacobianova matrika vrednosti parcialnih odvodov na točki začetnega približka

3. Sistem linearnih enačb je rešen za prirastke spremenljivk.

4. vektor prirastka se doda vektorju začetnega približka

5. Konvergenčni pogoj se preveri in, če ni dosežen, se postopek ponovi od 2. koraka.

Metodo je enostavno posplošiti na sistem enačb poljubne dimenzije.

Za funkcijo F 1 n spremenljivke linearni del raztezanja Taylorjevega niza v okolici točke napisano takole

Po razgradnji vseh enačb sistema in uporabi prej uvedenega zapisa dobimo po transformaciji sistem linearnih enačb reda n glede na prirastek spremenljivk Δ x i

– vrednost j -te funkcije z ustreznimi vrednostmi spremenljivk, to je neskladje j -te enačbe.

V skrajšani obliki lahko zapišemo takole - (F" )(Δ x ) = - (F ) , kjer se imenuje matrika delnih odvodnih vrednosti - (F" ) - Jakobova matrika oz Ali v matrični obliki, sistemi enačb.

Rešitev tega sistema daje vektor popravkov začetnega približka. Dodajanje k začetnemu vektorju približka daje nove, prečiščene vrednosti spremenljivk.

Za izračun so potrebni delni izpeljanki Jacobijeve matrike, lahko izračunamo analitično ali, če je to nemogoče ali težko, dobimo z uporabo približnih diferenciacijskih formul, na primer kot razmerje med prirastkom funkcije in prirastkom argumenta

kje epsilon– dokaj majhno število.

Metode za nadzor konvergence iterativnih metod
sistemske rešitve

Konvergenco iterativnega procesa reševanja sistema nelinearnih enačb je mogoče nadzorovati na več načinov, na primer:

1. Norma (evklidska ali -maksimalna) rezidualnega vektorja

2. Evklidska norma vektorja relativnih odklonov spremenljivk

3. Norma-maksimalni vektor relativnih odstopanj

Za rešitev sistema enačb uporabimo Newtonovo metodo

Matrika delnih odvodov (v analitični obliki)

Sistem linearnih enačb

Lahko se reši analitično ali s Cramerjevo metodo ali metodo matrične inverzije. Vzemimo začetni približek x = 0,15, y = 0,17

Prva ponovitev:

Jacobijeva matrika - vektor funkcijskih vrednosti Izračunani vektor popravkov Nov približek x = 0,15 + 0,028704 = 0,178704, y = 0,17 + 0,090926 = 0,260926 Druga ponovitev: Izračunani korekcijski vektor Nov približek x = 0,196656, y = 0,293359 Tretja ponovitev: Izračunani korekcijski vektor Nov približek x = 0,199867, y = 0,299739 Že pri 6. iteraciji je evklidska norma vektorja ostanka 2,8∙10 -13, največja relativna sprememba spremenljivk je 1,6∙10 -12 in rešitev konvergira k x = 0,2, y = 0,3 z absolutno napako, manjšo od 5∙10 -7. Preprosta iteracijska metoda pri enakih začetnih pogojih konvergira s takšno natančnostjo na 33. koraku, Seidelova modifikacija - na 31. koraku. Na spodnji sliki je prikazan primer organizacije izračunov pri reševanju obravnavanega sistema v MS Excelu.
Pojasnila: Celici B3 in B4 vsebujeta začetne približke rešitve sistema (vrednosti x 0 oziroma y 0). V območju celic D3:E4 so formule za izračun Jacobijeve matrike, pod pogojem, da je x v celici B3, y pa v celici B4 (formule so prikazane na spodnji sliki). V celicah G3:G4 se izračuna vrednost vektorja ostankov z negativnim predznakom.
V celici H3 se izračuna evklidska norma rezidualnega vektorja. V celicah I3:I4 se rešuje sistem linearnih enačb in izračuna vektor popravkov rešitve. Za to se matrika sistemskih koeficientov (Jacobijeva matrika) obrne in pomnoži s stolpčnim vektorjem prostih členov (negativni vektor ostankov). Formula v tem obsegu celic se vnese kot matrična formula. V bližini - v celici J3 - se izračuna norma korekcijskega vektorja za nadzor konvergence (glejte formule na spodnji sliki).
Korekcijske vrednosti, dobljene v celicah I3:I4 v drugem iteracijskem ciklu, se dodajo začetnemu približku (v celicah B6:B7) in nato se izračuni ponovijo podobno kot v prvem ciklu. Formule, vnesene v vrstici 6 in 7 delovnega lista, lahko kopirate, dokler ne dosežete zahtevane natančnosti.

Problemi, ki se zmanjšajo na reševanje sistema nelinearnih enačb

Primer problema, ki uporablja rešitev sistemov nelinearnih enačb, je aproksimacija v tabeli podane funkcije z uporabo matematičnih modelov, ki so nelinearni glede na parametre. Prej je bilo podrobno opisano. Če aproksimirajoča funkcija in njeni definirajoči parametri a i označite kot sledi Drug primer je iskanje ekstrema (minimuma ali maksimuma) funkcije več spremenljivk, pogoj za ekstrem je sočasna enakost vseh parcialnih odvodov funkcije. Tako je treba rešiti sistem enačb naslednje oblike, ki bo v splošnem primeru nelinearna

Metoda enostavne ponovitve, imenovana tudi metoda zaporednega približevanja, je matematični algoritem za iskanje vrednosti neznane količine s postopnim izboljšanjem. Bistvo te metode je v tem, da, kot že ime pove, s postopnim izražanjem naslednjih od začetnega približka dobimo vedno bolj izpopolnjene rezultate. Ta metoda se uporablja za iskanje vrednosti spremenljivke v dani funkciji, pa tudi pri reševanju sistemov linearnih in nelinearnih enačb.

Poglejmo, kako se ta metoda izvaja pri reševanju SLAE. Preprosta iteracijska metoda ima naslednji algoritem:

1. Preverjanje izpolnjevanja konvergenčnega pogoja v izvirni matriki. Konvergenčni izrek: če ima prvotna matrika sistema diagonalno prevlado (tj. v vsaki vrstici morajo biti elementi glavne diagonale večji po absolutni vrednosti od vsote elementov sekundarnih diagonal po absolutni vrednosti), potem je preprosta iteracijska metoda je konvergentna.

2. Matrika izvirnega sistema nima vedno diagonalne prevlade. V takih primerih je mogoče sistem pretvoriti. Enačbe, ki izpolnjujejo konvergenčni pogoj, ostanejo nedotaknjene, linearne kombinacije pa se naredijo s tistimi, ki ne izpolnjujejo, tj. enačbe množimo, odštevamo, seštevamo, dokler ne dobimo želenega rezultata.

Če v dobljenem sistemu na glavni diagonali obstajajo neprijetni koeficienti, se na obe strani takšne enačbe dodajo členi oblike z i * x i, katerih znaki morajo sovpadati z znaki diagonalnih elementov.

3. Pretvorba nastalega sistema v normalno obliko:

x - =β - +α*x -

To je mogoče storiti na več načinov, na primer takole: iz prve enačbe izrazite x 1 glede na druge neznanke, iz druge - x 2, iz tretje - x 3 itd. V tem primeru uporabljamo formule:

α ij = -(a ij / a ii)

i = b i /a ii
Ponovno se morate prepričati, da nastali sistem normalne oblike izpolnjuje konvergenčni pogoj:

∑ (j=1) |α ij |≤ 1, medtem ko je i= 1,2,...n

4. Začnemo uporabljati pravzaprav samo metodo zaporednih približkov.

x (0) je začetni približek, x (1) bomo izrazili skozi njega, nato bomo x (2) izrazili skozi x (1). Splošna formula v matrični obliki izgleda takole:

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

Računamo, dokler ne dosežemo zahtevane natančnosti:

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

Torej, uporabimo preprosto iteracijsko metodo v praksi. primer:
Reši SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 z natančnostjo ε=10 -3

Poglejmo, ali v modulu prevladujejo diagonalni elementi.

Vidimo, da samo tretja enačba izpolnjuje konvergenčni pogoj. Pretvorimo prvo in drugo ter dodamo drugo prvi enačbi:

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

Od tretjega odštejemo prvega:

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

Prvotni sistem smo pretvorili v enakovrednega:

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

Zdaj pa sistem pripeljemo v normalno obliko:

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

Preverimo konvergenco iterativnega procesa:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, tj. pogoj je izpolnjen.

0,3947
Začetno ugibanje x(0) = 0,4762
0,8511

Če nadomestimo te vrednosti v enačbo normalne oblike, dobimo naslednje vrednosti:

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

Če zamenjamo nove vrednosti, dobimo:

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

Nadaljujemo z izračuni, dokler se ne približamo vrednostim, ki izpolnjujejo dani pogoj.

x(7) = 0,441091

Preverimo pravilnost dobljenih rezultatov:

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

Rezultati, dobljeni s substitucijo ugotovljenih vrednosti v izvirnih enačbah, v celoti izpolnjujejo pogoje enačbe.

Kot lahko vidimo, preprosta iteracijska metoda daje dokaj natančne rezultate, vendar smo morali za rešitev te enačbe porabiti veliko časa in narediti okorne izračune.