Svi ljudi po prirodi teže znanju. (Aristotel. Metafizika)

Numeričke metode: rješavanje nelinearnih jednadžbi

Problemi rješavanja jednačina se stalno javljaju u praksi, na primjer, u ekonomiji, kada se razvija biznis, želite da znate kada će profit dostići određenu vrijednost, u medicini, kada se proučava djelovanje lijekova, važno je znati kada je koncentracija supstance će dostići zadati nivo, itd.

U optimizacijskim problemima često je potrebno odrediti tačke u kojima derivacija funkcije postaje 0, što je neophodan uslov lokalni ekstrem.

U statistici, kada se konstruišu procjene koristeći metodu najmanjih kvadrata ili maksimalne vjerovatnoće, također morate riješiti nelinearne jednačine i sisteme jednačina.

Dakle, javlja se čitava klasa problema vezanih za pronalaženje rješenja nelinearni jednačine, kao što su jednačine ili jednačine, itd.

U najjednostavnijem slučaju, imamo funkciju definiranu na intervalu ( a, b) i uzimanje određenih vrijednosti.

Svaka vrijednost x iz ovog segmenta možemo uporediti broj, ovo je funkcionalan zavisnost, ključni pojam u matematici.

Moramo pronaći vrijednost na kojoj se to naziva korijenima funkcije

Vizuelno moramo odrediti presječnu točku grafa funkcijesa osom apscisa.

Metoda prepolovljenja

Najjednostavniji metod za pronalaženje korijena jednadžbe je metoda prepolovljenja, ili dihotomija.

Ova metoda je intuitivna i svi bi postupili na sličan način prilikom rješavanja problema.

Algoritam je sljedeći.

Pretpostavimo da smo pronašli dvije točke i , Takve da imaju drugačije znakova, onda između ovih tačaka postoji barem jedan korijen funkcije.

Podijelimo segment na pola i uđimo prosjek tačka .

Onda bilo , ili .

Ostavimo onu polovinu segmenta za koju vrijednosti na krajevima imaju različite predznake. Sada ponovo dijelimo ovaj segment na pola i ostavljamo onaj dio na čijim granicama funkcija ima različite predznake, i tako dalje, kako bismo postigli potrebnu tačnost.

Očigledno, postepeno ćemo sužavati područje u kojem se nalazi korijen funkcije, pa ćemo ga, prema tome, odrediti s određenim stupnjem tačnosti.

Imajte na umu da je opisani algoritam primjenjiv za bilo koju kontinuiranu funkciju.

Prednosti metode prepolovljenja uključuju visoku pouzdanost i jednostavnost.

Nedostatak metode je činjenica da prije nego što je počnete koristiti, morate pronaći dvije točke u kojima vrijednosti funkcije imaju različite predznake. Očigledno je da metoda nije primjenjiva za korijene parne višestrukosti, a također se ne može generalizirati na slučaj kompleksnih korijena i na sisteme jednačina.

Redoslijed konvergencije metode je linearan, na svakom koraku tačnost se udvostručuje; što se više iteracija radi, to je korijen preciznije određen.

Newtonova metoda: teorijske osnove

Newtonova klasična metoda ili tangente je da je if neka aproksimacija korijenu jednadžbe , tada je sljedeća aproksimacija definirana kao korijen tangente na funkciju nacrtanu u točki .

Jednadžba tangente na funkciju u tački ima oblik:

U jednadžbi tangente stavljamo i .

Tada je algoritam za sekvencijalne proračune u Newtonovom metodu sljedeći:

Konvergencija tangentne metode je kvadratna, red konvergencije je 2.

Dakle, konvergencija Newtonove tangentne metode je vrlo brza.

Zapamtite ovu divnu činjenicu!

Bez ikakvih promjena, metoda je generalizirana na složeni slučaj.

Ako je korijen korijen druge višestrukosti ili više, tada red konvergencije opada i postaje linearan.

Vježba 1. Koristeći metodu tangente, pronađite rješenje jednačine na segmentu (0, 2).

Vježba 2. Metodom tangente pronađite rješenje jednačine na segmentu (1, 3).

Nedostaci Newtonove metode uključuju njenu lokalnost, jer je zajamčeno da će konvergirati za proizvoljnu početnu aproksimaciju samo ako je uvjet svuda zadovoljen , u suprotnoj situaciji, konvergencija se događa samo u određenom susjedstvu korijena.

Nedostatak Njutnove metode je potreba za izračunavanjem derivata u svakom koraku.

Vizualizacija Newtonove metode

Newtonova metoda (metoda tangente) se koristi ako je jednadžba f(x) = 0 ima root i ispunjeni su sljedeći uslovi:

1) funkcija y= f(x) definisano i kontinuirano na ;

2) f(a)· f(b) < 0 (funkcija uzima vrijednosti različitih predznaka na krajevima segmenta [ a; b]);

3) derivati f"(x) I f""(x) sačuvaj znak na intervalu [ a; b] (tj. funkcija f(x) ili se povećava ili smanjuje na segmentu [ a; b], uz zadržavanje smjera konveksnosti);

Glavna ideja metode je sljedeća: na segmentu [ a; b] takav broj je odabran x 0 , na kojoj f(x 0 ) ima isti predznak kao f"" (x 0 ), tj. uslov je zadovoljen f(x 0 )· f"" (x) > 0 . Tako je odabrana tačka sa apscisom x 0 , u kojem je tangenta na krivu y= f(x) na segmentu [ a; b] siječe osu Ox. Po bodu x 0 Prvo, zgodno je odabrati jedan od krajeva segmenta.

Razmotrimo Newtonovu metodu na konkretnom primjeru.

Neka nam je data rastuća funkcija y = f(x) =x 2 -2, kontinuirano na segmentu (0;2) i ima f"(x) = 2 x > 0 I f "" (x) = 2 > 0 .

Crtanje1 . f(x) =x 2 -2

Tangentna jednadžba u općem obliku ima sljedeći prikaz:

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

u našem slučaju: y-y 0 =2x 0 ·(x-x 0). Za tačku x 0 biramo tačku B 1 (b; f(b)) = (2,2). Nacrtajte tangentu na funkciju y = f(x) u tački B 1, i označimo tačku preseka tangente i ose Ox dot x 1. Dobijamo jednačinu prve tangente: y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Crtanje2. Rezultat prve iteracije

y=f(x) Ox kroz tačku x 1, shvatili smo poentu B 2 =(1,5; 0,25). Ponovo nacrtajte tangentu na funkciju y = f(x) u tački B 2, i označimo tačku preseka tangente i ose Ox dot x 2.

Jednačina druge tangente: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Točka preseka tangente i ose Vol: x 2 =.

Crtanje3. Druga iteracija Newtonove metode

Zatim nalazimo točku presjeka funkcije y=f(x) i okomicu povučenu na osu Ox kroz tačku x 2, dobijamo tačku B 3 i tako dalje.

Crtanje4. Treći korak tangentne metode

Prva aproksimacija korijena određena je formulom:

= 1.5.

Druga aproksimacija korijena određena je formulom:

Treća aproksimacija korijena određena je formulom:

Dakle , i th aproksimacija korijena određena je formulom:

Proračuni se vrše sve dok se decimalna mjesta koja su potrebna u odgovoru ne poklapaju, odnosno dok se ne postigne navedena preciznost e - dok se ne ispuni nejednakost | xi- xi-1 | < e.

U našem slučaju, uporedimo aproksimaciju dobijenu u trećem koraku sa stvarnim odgovorom izračunatim na kalkulatoru:

Slika 5. Korijen od 2, izračunat na kalkulatoru

Kao što vidite, već u trećem koraku dobili smo grešku manju od 0,000002.

Na ovaj način možete izračunati vrijednost "kvadratnog korijena od 2" sa bilo kojim stepenom tačnosti. Ovu izvanrednu metodu je izmislio Newton i omogućava vam da vrlo pronađete korijene složene jednačine.

Newtonova metoda: primjena u C++

U ovom članku ćemo automatizirati proces izračunavanja korijena jednadžbi pisanjem konzolne aplikacije u C++. Mi ćemo ga razviti u Visual C++ 2010 Express, ovo je besplatno i vrlo zgodno C++ razvojno okruženje.

Prvo, pokrenimo Visual C++ 2010 Express. Pojavit će se prozor za pokretanje programa. U lijevom kutu kliknite na "Kreiraj projekat".

Rice. 1. početna stranica Visual C++ 2010 Express

U izborniku koji se pojavi odaberite “Win32 Console Application” i unesite naziv aplikacije “Newton_Method”.

Rice. 2. Kreirajte projekat

// Newton.cpp metoda: definira ulaznu točku za aplikaciju konzole

#include "stdafx.h"

#include

korištenje imenskog prostora std;

float f(double x) //vraća vrijednost funkcije f(x) = x^2-2

float df(float x) //vraća vrijednost izvedenice

float d2f(float x) // vrijednost drugog izvoda

int _tmain(int argc, _TCHAR* argv)

int exit = 0, i=0;//varijable za izlaz i petlju

double x0,xn;//izračunate aproksimacije za korijen

dupli a, b, eps; // granice segmenta i potrebna točnost

cout<<"Please input \n=>";

cin>>a>>b; // unesemo granice segmenta na kojem ćemo tražiti korijen

cout<<"\nPlease input epsilon\n=>";

cin>>eps; // unesite potrebnu točnost proračuna

if (a > b) // ako je korisnik pomiješao granice segmenta, zamijenite ih

if (f(a)*f(b)>0) // ako su predznaci funkcije na rubovima segmenta isti, onda ovdje nema korijena

cout<<"\nError! No roots in this interval\n";

ako je (f(a)*d2f(a)>0) x0 = a; // da odaberete početnu tačku, provjerite f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // razmotrimo prvu aproksimaciju

cout<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // će nastaviti računati dok ne postignemo potrebnu tačnost

xn = x0-f(x0)/df(x0); // direktno Newtonova formula

cout<<++i<<"-th iteration = "<

cout<<"\nRoot = "<

cout<<"\nExit?=>";

) while (izlaz!=1); // dok korisnik ne uđe u izlaz = 1

Da vidimo kako to radi. Kliknite na zeleni trokut u gornjem lijevom uglu ekrana ili pritisnite F5.

Ako dođe do greške pri kompilaciji „Greška greške LNK1123: neuspjeh konverzije u COFF: datoteka je nevažeća ili oštećena“, onda se to može izliječiti ili instaliranjem prvog servisnog paketa 1, ili u postavkama projekta Svojstva -> Linker onemogućujući inkrementalno povezivanje.

Rice. 4. Rješavanje greške pri kompilaciji projekta

Tražit ćemo korijene funkcije f(x) =x2-2.

Prvo, provjerimo performanse aplikacije na “pogrešnim” ulaznim podacima. Na segmentu nema korijena, naš program bi trebao prikazati poruku o grešci.

Sada imamo prozor aplikacije:

Rice. 5. Unos ulaznih podataka

Uvedemo granice segmenta 3 i 5, a tačnost je 0,05. Program je, kao što se i očekivalo, proizveo poruku o grešci da na ovom segmentu nema root-a.

Rice. 6. Greška “Nema korijena na ovom segmentu!”

Nećemo još otići, pa šta je sa porukom “Izlaz?” unesite “0”.

Sada provjerimo aplikaciju koristeći ispravne ulazne podatke. Unesimo segment i tačnost 0,0001.

Rice. 7. Proračun korijena sa potrebnom tačnošću

Kao što vidimo, tražena tačnost je postignuta već na 4. iteraciji.

Da biste izašli iz aplikacije, unesite "Izlaz?" => 1.

Sekantna metoda

Da bi se izbjeglo izračunavanje izvoda, Newtonova metoda se može pojednostaviti zamjenom izvoda s aproksimacijom izračunatom iz prethodne dvije točke:

Iterativni proces izgleda ovako:

Ovo je iterativni proces u dva koraka jer koristi prethodna dva za pronalaženje sljedeće aproksimacije.

Red konvergencije metode sekansa je niži od reda tangentne metode i jednak je u slučaju jednog korijena.

Ova izuzetna količina naziva se zlatnim omjerom:

Provjerimo ovo, pretpostavljajući radi pogodnosti da .

Dakle, do infinitezimala višeg reda

Odbacivanjem ostatka člana, dobijamo rekurentnu relaciju čije se rješenje prirodno traži u obliku .

Nakon zamjene imamo: i

Za konvergenciju je potrebno da bude pozitivna, dakle .

Pošto poznavanje derivacije nije potrebno, sa istom količinom proračuna u metodi sekante (uprkos nižem redu konvergencije) može se postići veća tačnost nego u metodi tangente.

Imajte na umu da blizu korijena morate podijeliti s malim brojem, a to dovodi do gubitka točnosti (posebno u slučaju više korijena), stoga, nakon odabira relativno malog broja, izvršite proračune prije izvođenja i nastaviti ih sve dok se modul razlike između susjednih aproksimacija ne smanji.

Čim rast počne, proračuni se zaustavljaju i posljednja iteracija se ne koristi.

Ovaj postupak za određivanje kraja iteracija naziva se tehnika Garvika.

Parabola metoda

Razmotrimo metodu u tri koraka u kojoj je aproksimacija određena s tri prethodne točke , i .

Da bismo to učinili, zamjenjujemo, slično metodi sekante, funkciju s interpolacijskom parabolom koja prolazi kroz točke , i .

U Newtonovom obliku to izgleda ovako:

Tačka se definira kao jedan od korijena ovog polinoma koji je po apsolutnoj vrijednosti bliži tački.

Red konvergencije parabole metode je viši od reda sekantne metode, ali niži od Newtonove metode.

Važna razlika u odnosu na prethodno razmatrane metode je činjenica da čak i ako su realne za realne i ako su početne aproksimacije odabrane da budu realne, metoda parabole može dovesti do kompleksnog korijena originalnog problema.

Ova metoda je vrlo pogodna za pronalaženje korijena polinoma visokog stepena.

Jednostavna metoda iteracije

Problem nalaženja rješenja jednadžbi može se formulirati kao problem nalaženja korijena: , ili kao problem nalaženja fiksne točke.

Neka i - kompresija: (posebno činjenica da - kompresija, kao što je lako vidjeti, to znači).

Prema Banahovoj teoremi, postoji jedinstvena fiksna tačka

Može se naći kao granica jednostavne iterativne procedure

gdje je početna aproksimacija proizvoljna tačka u intervalu.

Ako je funkcija diferencibilna, tada je pogodan kriterij kompresije broj. Zaista, prema Lagrangeovoj teoremi

Dakle, ako je izvod manji od jedan, onda je to kompresija.

Stanje je bitno, jer ako je, na primjer, na , tada nema fiksne točke, iako je derivacija jednaka nuli. Brzina konvergencije ovisi o vrijednosti . Što je manji, to je brža konvergencija.

Neka je korijen jednadžbe f(x)=0 odvojen na segmentu , s prvim i drugim izvodom f’(x) i f""(x) su kontinuirani i konstantnog predznaka za xÎ.

Neka se u nekom koraku preciziranja korijena dobije sljedeća aproksimacija korijenu x n (odabrana) . Zatim pretpostavimo da je sljedeća aproksimacija dobivena korištenjem korekcije h n , dovodi do tačne vrijednosti korijena

x = xn + hn. (1.2.3-6)

Brojanje h n male vrijednosti, predstavljamo f(h n + h n) u obliku Taylorovog reda, ograničavajući se na linearne članove

f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)

Uzimajući u obzir da je f(x) = f(x n + h n) = 0, dobijamo f(x n) + h n f ’(x n) » 0.

Dakle, h n » - f(x n)/ f’(x n). Zamenimo vrednost h n u (1.2.3-6) i umjesto tačne vrijednosti korijena x dobijamo još jednu aproksimaciju

Formula (1.2.3-8) nam omogućava da dobijemo niz aproksimacija x 1, x 2, x 3 ..., koji, pod određenim uslovima, konvergira na tačnu vrednost korena x, to je

Geometrijska interpretacija Newtonove metode je kako slijedi
(Sl.1.2.3-6). Uzmimo desni kraj segmenta b kao početnu aproksimaciju x 0 i konstruirajmo tangentu u odgovarajućoj tački B 0 na grafu funkcije y = f(x). Tačka preseka tangente sa x-osom uzima se kao nova, preciznija aproksimacija x 1. Ponavljanje ove procedure mnogo puta nam omogućava da dobijemo niz aproksimacija x 0, x 1, x 2 , . . ., koji teži tačnoj vrijednosti korijena x.

Formula proračuna Newtonove metode (1.2.3-8) može se dobiti iz geometrijske konstrukcije. Dakle, u pravokutnom trokutu x 0 B 0 x 1 krak
x 0 x 1 = x 0 V 0 /tga. S obzirom da je tačka B 0 na grafu funkcije f(x), a hipotenuzu formira tangenta na graf f(x) u tački B 0, dobijamo

(1.2.3-9)

(1.2.3-10)

Ova formula se poklapa sa (1.2.3-8) za n-tu aproksimaciju.

Sa slike 1.2.3-6 jasno je da odabir tačke a kao početne aproksimacije može dovesti do činjenice da će sljedeća aproksimacija x 1 biti izvan segmenta na kojem je korijen odvojen x. U ovom slučaju, konvergencija procesa nije zagarantovana. U opštem slučaju, izbor početne aproksimacije vrši se u skladu sa sledećim pravilom: početnu aproksimaciju treba uzeti kao tačku x 0 O, u kojoj je f(x 0)×f''(x 0)>0 , odnosno znaci funkcije i njenog drugog izvoda se poklapaju.

Uslovi za konvergenciju Njutnove metode formulisani su u sledećoj teoremi.

Ako je korijen jednadžbe odvojen na segmentu, i f’(x 0) i f’’(x) razlikuju se od nule i zadržavaju svoje predznake kada xO, onda ako odaberemo takvu tačku kao početnu aproksimaciju x 0 O , Šta f(x 0).f¢¢(x 0)>0 , zatim korijen jednadžbe f(x)=0 može se izračunati sa bilo kojim stepenom tačnosti.

Procjena greške Newtonove metode određena je sljedećim izrazom:

(1.2.3-11)

gdje je najmanja vrijednost at

Najviša vrijednost at

Proces proračuna se zaustavlja ako ,

gdje je navedena tačnost.

Osim toga, sljedeći izrazi mogu poslužiti kao uvjet za postizanje zadane tačnosti prilikom pročišćavanja korijena pomoću Newtonove metode:

Dijagram algoritma Newtonove metode prikazan je na Sl. 1.2.3-7.

Lijeva strana originalne jednadžbe f(x) i njen izvod f’(x) u algoritmu su dizajnirani kao zasebni softverski moduli.

Rice. 1.2.3-7. Dijagram algoritma Newtonove metode

Primjer 1.2.3-3. Precizirajte korijene jednačine x-ln(x+2) = 0 koristeći Newtonov metod, pod uslovom da su korijeni ove jednačine odvojeni na segmentima x 1 O[-1.9;-1.1] i x 2 O [-0,9;2 ].

Prvi izvod f’(x) = 1 – 1/(x+2) zadržava svoj predznak na svakom od segmenata:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 na xO [-0,9; 2].

Drugi izvod f"(x) = 1/(x+2) 2 > 0 za bilo koje x.

Dakle, uslovi konvergencije su zadovoljeni. Budući da je f""(x)>0 u cijelom rasponu dozvoljenih vrijednosti, onda da razjasnimo korijen početne aproksimacije x 1 izaberite x 0 = -1,9 (pošto f(-1,9)×f”(-1,9)>0). Dobijamo niz aproksimacija:

Nastavljajući proračune, dobijamo sljedeći niz prve četiri aproksimacije: -1,9; –1,8552, -1,8421; -1,8414 . Vrijednost funkcije f(x) u tački x=-1,8414 jednaka je f(-1,8414)=-0,00003 .

Za pojašnjenje korijena x 2 O[-0.9;2] biramo 0 =2 (f(2)×f”(2)>0) kao početnu aproksimaciju. Na osnovu x 0 = 2, dobijamo niz aproksimacija: 2.0;1.1817; 1.1462; 1.1461. Vrijednost funkcije f(x) u tački x=1,1461 jednaka je f(1,1461)= -0,00006.

Newtonova metoda ima visoku stopu konvergencije, ali na svakom koraku zahtijeva izračunavanje ne samo vrijednosti funkcije, već i njenog izvoda.

Metoda akorda

Geometrijska interpretacija metode akorda je kako slijedi
(Sl.1.2.3-8).

Nacrtajmo segment kroz tačke A i B. Sledeća aproksimacija x 1 je apscisa tačke preseka tetive sa 0x osom. Konstruirajmo jednačinu pravolinijskog segmenta:

Postavimo y=0 i pronađemo vrijednost x=x 1 (sljedeća aproksimacija):

Ponovimo proces izračunavanja da dobijemo sljedeću aproksimaciju korijenu - x 2 :

U našem slučaju (slika 1.2.11) i formula za izračunavanje za metodu akorda će izgledati ovako

Ova formula važi kada se tačka b uzme kao fiksna tačka, a tačka a deluje kao početna aproksimacija.

Razmotrimo još jedan slučaj (sl. 1.2.3-9), kada .

Jednačina prave linije za ovaj slučaj ima oblik

Sljedeća aproksimacija x 1 na y = 0

Tada rekurentna formula metode akorda za ovaj slučaj ima oblik

Treba napomenuti da je fiksna tačka u metodi tetiva odabrana da bude kraj segmenta za koji je zadovoljen uslov f (x)∙f¢¢ (x)>0.

Dakle, ako se tačka a uzme kao fiksna tačka , tada x 0 = b djeluje kao početna aproksimacija, i obrnuto.

Dovoljni uslovi koji obezbeđuju izračunavanje korena jednačine f(x) = 0 pomoću formule tetive biće isti kao i za metod tangente (Newtonova metoda), samo što se umesto početne aproksimacije bira fiksna tačka. Metoda akorda je modifikacija Newtonove metode. Razlika je u tome što je sljedeća aproksimacija u Newtonovoj metodi tačka presjeka tangente sa osom 0X, au metodi tetiva - tačka presjeka tetive sa osom 0X - aproksimacije konvergiraju korijenu s različitih strana .

Procjena greške za metodu akorda data je izrazom

(1.2.3-15)

Uslov za završetak procesa iteracije metodom akorda

(1.2.3-16)

U slučaju M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Primjer 1.2.3-4. Pojasniti korijen jednačine e x – 3x = 0, odvojen na segmentu sa tačnošću od 10 -4.

Provjerimo uvjet konvergencije:

Prema tome, a=0 treba izabrati kao fiksnu tačku, a x 0 =1 treba uzeti kao početnu aproksimaciju, pošto je f(0)=1>0 i f(0)*f"(0)>0.

Dok se u školi muče s rješavanjem jednačina na časovima matematike, mnogi učenici su često uvjereni da potpuno uzalud troše vrijeme, a ipak će takva vještina biti od koristi u životu ne samo onima koji odluče krenuti stopama Dekarta, Euler ili Lobačevski.

U praksi, na primjer u medicini ili ekonomiji, često se dešavaju situacije kada specijalista treba da sazna kada je koncentracija aktivna supstanca određenog lijeka će dostići potrebnu razinu u krvi pacijenta ili je potrebno izračunati vrijeme potrebno da određeni posao postane profitabilan.

Najčešće govorimo o rješavanju nelinearnih jednačina razne vrste. Numeričke metode omogućavaju da se to uradi što je brže moguće, posebno korišćenjem računara. Oni su dobro proučeni i dugo su dokazali svoju efikasnost. To uključuje Newtonovu tangentnu metodu, koja je predmet ovog članka.

Formulacija problema

U ovom slučaju postoji funkcija g koja je definirana na segmentu (a, b) i na njemu poprima određene vrijednosti, tj. svaki x koji pripada (a, b) može biti povezan s određenim brojem g (x).

Potrebno je uspostaviti sve korijene jednadžbe iz intervala između tačaka a i b (uključujući krajeve), za koje je funkcija postavljena na nulu. Očigledno, to će biti tačke preseka y = g(x) sa OX.

U nekim slučajevima je zgodnije zamijeniti g(x)=0 sličnim, kao što je g 1 (x) = g 2 (x). U ovom slučaju, apscise (vrijednost x) presječnih tačaka grafova g 1 (x) i g 2 (x) djeluju kao korijeni.

Rješenje nelinearne jednadžbe također je važno za optimizacijske probleme za koje je uvjet za lokalni ekstrem da se derivacija funkcije okrene na 0. Drugim riječima, takav problem se može svesti na pronalaženje korijena jednadžbe p(x) = 0, gdje je p(x) identičan g"(x).

Metode rješenja

Za neke vrste nelinearnih jednadžbi, kao što su kvadratne ili jednostavne trigonometrijske jednadžbe, korijeni se mogu pronaći na prilično jednostavne načine. Konkretno, svaki školarac zna formule koje se mogu koristiti za lako pronalaženje vrijednosti argumenta tačaka u kojima kvadratni trinom nestaje.

Metode za vađenje korijena nelinearnih jednačina obično se dijele na analitičke (direktne) i iterativne. U prvom slučaju, željeno rješenje ima oblik formule, pomoću koje se u određenom broju aritmetičkih operacija može pronaći vrijednost željenih korijena. Slične metode su razvijene za eksponencijalne, trigonometrijske, logaritamske i jednostavne algebarske jednačine. Za ostalo, morate koristiti posebne numeričke metode. Lako ih je implementirati pomoću računara, koji vam omogućavaju da pronađete korijene sa potrebnom preciznošću.

Tu spadaju tzv numerička metoda Ovo poslednje je predložio veliki naučnik Isak Njutn krajem 17. veka. U narednim vekovima, metoda je više puta unapređivana.

Lokalizacija

Numeričke metode za rješavanje složenih jednačina koje nemaju analitička rješenja obično se izvode u 2 faze. Prvo ih morate lokalizirati. Ova operacija se sastoji od pronalaženja takvih segmenata na OX na kojima postoji jedan korijen jednačine koja se rješava.

Razmotrimo segment. Ako g(x) nema diskontinuiteta na sebi i uzima vrijednosti različitih predznaka na krajnjim tačkama, tada između a i b ili u njima postoji najmanje 1 korijen jednačine g(x) = 0. Da bi se biti jedinstven, potrebno je da g(x) nije monotona. Kao što je poznato, imaće ovo svojstvo pod uslovom da je predznak g’(x) konstantan.

Drugim riječima, ako g(x) nema diskontinuiteta i monotono raste ili opada, a njegove vrijednosti na krajnjim tačkama nemaju iste predznake, tada postoji 1 i samo 1 korijen od g(x).

Međutim, trebate znati da se ovaj kriterij neće primjenjivati na korijene jednadžbi koje su višestruke.

Rješavanje jednadžbe prepolovljavanjem

Prije razmatranja složenijih numeričkih tangenta i njihovih varijeteta, vrijedi se upoznati s najviše na jednostavan način identifikovanje korena. Zove se dihotomija i odnosi se na intuitivan način pronalaženja korijena, zasnovan na teoremi da ako je za g(x), kontinuirano, zadovoljen uvjet različitih predznaka, tada na segmentu koji se razmatra postoji najmanje 1 korijen g( x) = 0.

Da biste ga pronašli, trebate podijeliti segment na pola i odrediti sredinu kao x 2. Tada su moguće dvije opcije: g(x 0) * g(x 2) ili g(x 2) * g(x 1) su jednake ili manje od 0. Biramo onu za koju je jedna od ovih nejednakosti tačna. Ponavljamo gore opisani postupak sve dok dužina ne postane manja od određene unaprijed odabrane vrijednosti koja određuje točnost određivanja korijena jednadžbe na .

Prednosti metode uključuju njegovu pouzdanost i jednostavnost, ali nedostatak je potreba da se na početku identifikuju tačke u kojima g(x) poprima različite predznake, tako da se ne može koristiti za korijene čak i višestrukosti. Osim toga, ne generalizira se na slučaj sistema jednačina ili ako govorimo o kompleksnim korijenima.

Primjer 1

Želimo da riješimo jednačinu g(x) = 2x 5 + x - 1 = 0. Da ne bismo dugo tražili odgovarajući segment, gradimo graf koristeći, na primjer, poznati Excel program . Vidimo da je bolje uzeti vrijednosti iz intervala kao segment za lokalizaciju korijena. Možemo biti sigurni da na njemu postoji barem jedan korijen tražene jednačine.

g"(x) = 10x 4 + 1, tj. to je monotono rastuća funkcija, tako da postoji samo 1 korijen na odabranom segmentu.

Zamjenjujemo krajnje tačke u jednačinu. Imamo 0 i 1 respektivno. U prvom koraku uzimamo tačku 0,5 kao rješenje. Tada je g(0,5) = -0,4375. To znači da će sljedeći segment za prepolovljenje biti . Njegovo midpoint- 0,75. U njemu je vrijednost funkcije 0,226. Uzimamo u obzir segment i njegovu sredinu, koja se nalazi u tački 0,625. Računamo da je vrijednost g(x) 0,625. Jednako je sa -0,11, odnosno negativno. Na osnovu ovog rezultata biramo segment. Dobijamo x = 0,6875. Tada je g(x) = -0,00532. Ako je tačnost rješenja 0,01, onda možemo pretpostaviti da je željeni rezultat 0,6875.

Teorijska osnova

Ova metoda pronalaženja korijena korištenjem Newtonove tangentne metode je popularna zbog svoje vrlo brze konvergencije.

Zasniva se na dokazanoj činjenici da ako je x n aproksimacija korijenu f(x) = 0, takva da je f" C 1, tada će sljedeća aproksimacija biti u tački u kojoj je jednadžba tangente na f(x) je nula, tj.

Zamijenite x = x n+1 i postavite y na nulu.

Tada tangente izgledaju ovako:

Primjer 2

Pokušajmo koristiti Newtonovu klasičnu tangentnu metodu i pronaći rješenje neke nelinearne jednačine koje je teško ili nemoguće analitički pronaći.

Neka je potrebno identificirati korijene za x 3 + 4x - 3 = 0 sa određenom preciznošću, na primjer 0,001. Kao što je poznato, graf bilo koje funkcije u obliku polinoma neparnog stepena mora barem jednom presjeći osu OX, tj. nema sumnje u postojanje korijena.

Prije rješavanja našeg primjera metodom tangente, gradimo graf f(x) = x 3 + 4x - 3 u tački. To je vrlo lako učiniti, na primjer, korištenjem Excel procesora proračunskih tablica. Iz rezultirajućeg grafika bit će jasno da se ne siječe sa OX osom i da funkcija y = x 3 + 4x - 3 monotono raste. Možemo biti sigurni da jednačina x 3 + 4x - 3 = 0 ima rješenje i da je jedinstvena.

Algoritam

Svako rješenje jednadžbi tangentnom metodom počinje izračunavanjem f "(x). Imamo:

Tada će drugi izvod biti x * 6.

Koristeći ove izraze, možemo napisati formulu za identifikaciju korijena jednadžbe koristeći tangentnu metodu u obliku:

Zatim morate odabrati početnu aproksimaciju, tj. odlučiti koju tačku smatrati početnom (volumen x 0) za iterativni proces. Razmatramo krajeve segmenta. Koristićemo onu za koju je tačan uslov da su funkcija i njen 2. izvod na x 0 različitih predznaka. Kao što vidimo, kada se zameni x 0 = 0, on je prekinut, ali je x 0 = 1 sasvim prikladan.

onda ako nas zanima rješavanje tangentne metode sa tačnošću e, onda se može smatrati da vrijednost x n zadovoljava zahtjeve problema, pod uslovom da je nejednakost |f(x n) / f’(x n)|< e.

Na prvom koraku tangente imamo:

x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
pošto uslov nije ispunjen, idemo dalje;
dobijamo novu vrijednost za x 2, koja je jednaka 0,674;
primijetimo da je omjer vrijednosti funkcije i njenog izvoda u x 2 manji od 0,0063, zaustavljamo proces.

Metoda tangente u Excelu

Prethodni primjer možete riješiti mnogo lakše i brže ako proračune ne izvodite ručno (na kalkulatoru), već koristite mogućnosti Microsoftovog procesora proračunskih tablica.

Da biste to učinili, morate kreirati novu stranicu u Excelu i ispuniti njene ćelije sljedećim formulama:

u C7 pišemo “= STEPEN (B7;3) + 4 * B7 - 3”;
u D7 unosimo “= 4 + 3 * STEPEN (B7;2)”;
u E7 pišemo “= (STEPEN (B7;3)- 3 + 4 * B7) / (3* STEPEN (B7;2) + 4)”;
u D7 unosimo izraz “=B7 - E7”;
u B8 unosimo formulu uslova „=IF(E7< 0,001;"Завершение итераций"; D7)».

U konkretnom zadatku će se u ćeliji B10 pojaviti natpis „Završavanje iteracija“, a da biste riješili problem, trebat ćete uzeti broj napisan u ćeliji koja se nalazi jedan red iznad. Također možete odabrati zaseban stupac koji se može rastegnuti za njega tako što ćete tamo unijeti formula-uvjet, prema kojem će rezultat biti upisan tamo ako sadržaj u jednoj ili drugoj ćeliji stupca B poprimi oblik "Završetak iteracija".

Implementacija u Pascal-u

Pokušajmo dobiti rješenje nelinearne jednačine y = x 4 - 4 - 2 * x koristeći tangentnu metodu u Pascalu.

Koristimo pomoćnu funkciju koja će pomoći da se izvrši približno izračunavanje f"(x) = (f(x + delta) - f(x)) / delta. Kao uslov za završetak iterativnog procesa biramo ispunjenje nejednakost |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Program je prepoznatljiv po tome što ne zahtijeva ručno izračunavanje izvedenice.

Metoda akorda

Hajde da razmotrimo drugi način da identifikujemo korene nelinearnih jednačina. Proces iteracije se sastoji u tome da se kao uzastopne aproksimacije željenom korijenu za f(x) = 0 uzimaju vrijednosti točaka presjeka tetive sa apscisom krajnjih tačaka a i b sa OX, označeno kao x 1, ..., x n. Imamo:

Za tačku u kojoj tetiva seče osu OX, izraz će biti zapisan kao:

Neka je drugi izvod pozitivan za x £ (suprotan slučaj će se svesti na onaj koji se razmatra ako zapišemo f(x) = 0). U ovom slučaju, graf y = f(x) je kriva, konveksna na dnu i smještena ispod tetive AB. Mogu postojati 2 slučaja: kada funkcija ima pozitivnu vrijednost u tački a ili je negativna u tački b.

U prvom slučaju biramo kraj a kao fiksni, a tačku b uzimamo kao x 0. Tada uzastopne aproksimacije prema gornjoj formuli formiraju niz koji se monotono smanjuje.

U drugom slučaju, kraj b je fiksiran na x 0 = a. Vrijednosti x dobivene u svakom koraku iteracije formiraju niz koji se monotono povećava.

Dakle, možemo konstatovati da:

u metodi tetiva, fiksni kraj segmenta je onaj kod kojeg se znaci funkcije i njenog drugog izvoda ne poklapaju;
aproksimacije za korijen x - x m - leže od njega na strani gdje f(x) ima predznak koji se ne poklapa sa predznakom f"" (x).

Iteracije se mogu nastaviti sve dok se ne ispune uslovi za blizinu korijena u ovom i prethodnom koraku iteracije po modulu abs(x m - x m - 1)< e.

Modifikovana metoda

Kombinirana metoda tetiva i tangenta omogućava vam da uspostavite korijene jednadžbe tako što ćete im pristupiti s različitih strana. Ova vrijednost, pri kojoj graf f(x) siječe OX, omogućava vam da precizirate rješenje mnogo brže nego da koristite svaku od metoda zasebno.

Pretpostavimo da trebamo pronaći korijene f(x)=0, ako postoje na . Možete primijeniti bilo koju od gore opisanih metoda. Međutim, bolje je isprobati njihovu kombinaciju, što će značajno poboljšati točnost korijena.

Razmatramo slučaj sa početnom aproksimacijom koja odgovara uslovu da su prvi i drugi izvod različitih predznaka u određenoj tački x.

U takvim uslovima, rešavanje nelinearnih jednadžbi tangentnom metodom omogućava da se pronađe koren sa viškom ako je x 0 =b, a metoda pomoću tetiva sa fiksnim krajem b dovodi do pronalaženja približnog korena sa nedostatkom.

Korišćene formule:

Sada se u intervalu mora tražiti traženi korijen x. U sljedećem koraku morate primijeniti kombinovani metod na ovaj segment. Postupajući na ovaj način, dobijamo formule oblika:

Ako prvi i drugi izvod imaju različite predznake, onda, razmišljajući na sličan način, da bismo razjasnili korijen dobijamo sljedeće rekurentne formule:

Uvjet koji se koristi je procijenjena nejednakost| b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Ako je gornja nejednakost tačna, onda kao korijen nelinearne jednadžbe na datom segmentu uzmite tačku koja je tačno na pola puta između rješenja pronađenih u određenom koraku iteracije.

Kombinovani metod se lako implementira u TURBO PASCAL okruženju. Ako zaista želite, možete pokušati izvršiti sve proračune koristeći tabelarni način u Excelu.

U potonjem slučaju, nekoliko stupaca se dodjeljuje za rješavanje problema pomoću akorda i odvojeno za metodu koju je predložio Isaac Newton.

U ovom slučaju, svaki red se koristi za snimanje proračuna u određenom koraku iteracije koristeći dvije metode. Zatim, na lijevoj strani područja rješenja, na aktivnoj radnoj stranici je istaknut stupac u koji se unosi rezultat izračunavanja modula razlike vrijednosti sljedećeg iterativnog koraka za svaku od metoda. Drugi se može koristiti za unos rezultata proračuna na osnovu formule za izračunavanje logičke konstrukcije „IF“, koja se koristi da se sazna da li je uslov tačan ili ne.

Sada znate kako riješiti složene jednadžbe. Metoda tangente, kao što ste već vidjeli, implementirana je prilično jednostavno, kako u Pascalu tako iu Excelu. Stoga uvijek možete odrediti korijene jednadžbe koju je teško ili nemoguće riješiti pomoću formula.

Isto kao i aproksimacija. Termin P. se ponekad koristi u smislu približavanja objekta (na primjer, inicijala P.) ... Mathematical Encyclopedia

Newtonova metoda- Newtonova metoda, Newtonov algoritam (također poznat kao tangentna metoda) je iterativni numerički metod za pronalaženje korijena (nule) date funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isak Njutn... ... Wikipedia

Metoda jedne tangente

Gauss-Newton metoda- Newtonova metoda (također poznata kao tangentna metoda) je iterativna numerička metoda za pronalaženje korijena (nule) date funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isak Njutn (1643-1727), pod imenom ... ... Wikipedia

Newton-Raphsonova metoda- Newtonova metoda (također poznata kao tangentna metoda) je iterativna numerička metoda za pronalaženje korijena (nule) date funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isak Njutn (1643-1727), pod imenom ... ... Wikipedia

Metoda tangente- Newtonova metoda (također poznata kao tangentna metoda) je iterativna numerička metoda za pronalaženje korijena (nule) date funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isak Njutn (1643-1727), pod imenom ... ... Wikipedia

Metoda tangente (Newtonova metoda)- Newtonova metoda (također poznata kao tangentna metoda) je iterativna numerička metoda za pronalaženje korijena (nule) date funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isak Njutn (1643-1727), pod imenom ... ... Wikipedia

Numeričko rješenje jednačina- i njihovi sistemi se sastoje od približnog određivanja korena ili korena jednačine ili sistema jednačina i koristi se u slučajevima kada je nemoguće ili veoma naporno izračunati tačnu vrednost. Sadržaj 1 Prikaz problema 2 Numeričke metode ... Wikipedia

Metoda sukcesivne aproksimacije- metoda za rješavanje matematičkih problema korištenjem niza aproksimacija koji konvergira rješenju i konstruiše se rekurzivno (tj. svaka nova aproksimacija se izračunava na osnovu prethodne; početna aproksimacija se bira u ... ... Velika sovjetska enciklopedija

U problemu minimiziranja funkcije od najveće je važnosti uspješan izbor početne aproksimacije.Naravno, nemoguće je doći do općeg pravila koje bi bilo zadovoljavajuće za sve slučajeve, odnosno za sve moguće nelinearne funkcije. Svaki put morate tražiti vlastito rješenje. U nastavku predlažemo skup nekih metoda za pronalaženje grubih početnih aproksimacija, koje u praksi mogu poslužiti kao polazna tačka za traženje zadovoljavajućih aproksimacija u određenom problemu.

9.6.1. Pretraga po mreži. Ova metoda je posebno efikasna sa malim brojem stvarnih nelinearnih parametara. Često su funkcije dizajnirane na način da kada su vrijednosti nekih parametara (koje nazivamo nelinearnim) fiksne, ostali parametri postaju linearni.

Nakon što su zatim specificirane donje i gornje granice za nelinearne parametre, uz određeni korak moguće je nabrojati opcije na rezultirajućoj mreži vrijednosti samih nelinearnih parametara i identificirati linearnu regresiju koja vodi do minimalnog zbroja kvadrata. .

Kao primjer, razmotrite funkciju

Ovdje će stvarni nelinearni parametar biti . Recimo da je poznato da . Neka je h korak za parametar. Izračunajmo linearne regresije

gdje nalazimo minimalni zbir kvadrata za svaki od njih. Najmanji od njih odgovara optimalnoj početnoj aproksimaciji. U principu, korak od kojeg zavisi "gustina" mreže može varirati, tako da se smanjenjem vrijednosti h mogu pronaći vrijednosti parametara s bilo kojom točnošću.

9.6.2. Transformacija modela.

Ponekad, nekom transformacijom, model se može svesti na linearan ili se broj stvarnih nelinearnih parametara može smanjiti (vidi odjeljak 6.2.3). Pokažimo kako se to može postići na primjeru logističke krive

Izvođenjem inverzne transformacije na odgovarajućim jednadžbama regresije dobijamo

Označavanjem dolazimo do nove funkcije čiji se broj linearnih parametara povećao sa jednog na dva. Procjena za parametar u novom modelu može se pronaći, na primjer, korištenjem prethodne metode.

Ovdje je prikladno dati sljedeću primjedbu o transformacijama regresionih modela. Treba imati na umu da greška koja je bila aditivna u izvornoj jednačini, općenito govoreći, nakon transformacije više neće biti aditivna.

Koristeći proširenje Taylorovog reda i označavajući transformaciju zanemarujući termine reda

Iz toga slijedi

Posljednja jednakost se može uzeti kao osnova za analizu problema sa transformiranim modelom.

9.6.3. Podjela uzorka na poduzorke.

Da biste pronašli početnu aproksimaciju, možete podijeliti cijeli uzorak na poduzorke (sa približno jednakim volumenom), gdje je broj nepoznatih parametara. Za svaki poduzorak nalazimo prosječne vrijednosti preko y i X, koje označavamo sa m, respektivno. Riješimo sistem nelinearnih jednadžbi za

Rješenje za ovaj sistem će biti početna aproksimacija parametara. Očigledno, da bi ova metoda „funkcionisala“, potrebno je da se ovaj sistem nelinearnih jednačina reši prilično lako, na primer analitički.

9.6.4. Proširenje Taylorovog reda u nezavisnim varijablama.

Osnova iterativne minimizacije zbira kvadrata je proširenje funkcije regresije u Taylorovom nizu na linearne članove u parametrima. Da bi se pronašla gruba početna aproksimacija, ponekad je korisna procedura regresijske aproksimacije proširenjem u Taylorov niz u nezavisnim varijablama. Radi jednostavnosti, pretpostavićemo da je jednodimenzionalan. Neka je prosječna vrijednost, a zatim približno

Označavamo , tako dolazimo do linearnog modela

Neka su procjene najmanjih kvadrata parametara ove linearne regresije. Kao početne aproksimacije uzet ćemo rješenje nelinearnog sistema jednačina u odnosu na