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

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

U praksi se stalno pojavljuju problemi rješavanja jednadžbi, npr. u ekonomiji, kada se razvija posao, želite znati kada će profit dosegnuti određenu vrijednost, u medicini, kada se proučavaju učinci lijekova, važno je znati kada koncentracija tvari će dosegnuti zadanu razinu, itd.

U problemima optimizacije često je potrebno odrediti točke u kojima derivacija funkcije postaje 0, što je nužan uvjet lokalni ekstremno.

U statistici, kada konstruirate procjene pomoću metode najmanjih kvadrata ili metode najveće vjerojatnosti, također morate riješiti nelinearne jednadžbe i sustave jednadžbi.

Dakle, pojavljuje se cijela klasa problema vezanih uz pronalaženje rješenja nelinearni jednadžbe, kao što su jednadžbe ili jednadžbe itd.

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

Svaka vrijednost x iz ovog segmenta možemo usporediti broj, ovo je funkcionalni ovisnost, ključni pojam u matematici.

Moramo pronaći vrijednost pri kojoj se oni nazivaju korijenima funkcije

Vizualno trebamo odrediti sjecište grafa funkcijes osi apscisa.

Metoda prepolovljenja

Najjednostavnija metoda za pronalaženje korijena jednadžbe je metoda prepolovljenja, ili Dihotomija.

Ova metoda je intuitivna i svatko bi postupio na sličan način pri rješavanju problema.

Algoritam je sljedeći.

Pretpostavimo da smo pronašli dvije točke i , Takve da su drugačiji znakova, tada između tih točaka postoji barem jedan korijen funkcije.

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

Onda bilo , ili .

Ostavimo onu polovicu segmenta za koju su vrijednosti na krajevima različite znakove. Sada taj segment ponovno podijelimo na pola i ostavimo onaj dio na čijim granicama funkcija ima različite predznake, i tako dalje, kako bismo postigli potrebnu točnost.

Očigledno je da ćemo postupno sužavati područje gdje se nalazi korijen funkcije, te ćemo ga stoga odrediti s određenim stupnjem točnosti.

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

Prednosti metode prepolovljenja su visoka 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čito je da metoda nije primjenjiva za korijene parne množine, a također se ne može generalizirati na slučaj složenih korijena i na sustave jednadžbi.

Redoslijed konvergencije metode je linearan, u svakom koraku točnost se udvostručuje, što se više iteracija radi, točnije se određuje korijen.

Newtonova metoda: teorijske osnove

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

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

U jednadžbu tangente stavljamo i .

Tada je algoritam za sekvencijalne proračune u Newtonovoj metodi sljedeći:

Konvergencija metode tangente je kvadratna, red konvergencije je 2.

Stoga je konvergencija Newtonove tangentne metode vrlo brza.

Upamtite ovu divnu činjenicu!

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

Ako je korijen korijen druge množine ili više, tada red konvergencije pada i postaje linearan.

Vježba 1. Metodom tangente pronađite rješenje jednadžbe na segmentu (0, 2).

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

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

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

Vizualizacija Newtonove metode

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

1) funkcija g= f(x) definiran i kontinuiran na ;

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

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

Glavna ideja metode je sljedeća: na segmentu [ a; b] odabran je takav broj x 0 , na kojem f(x 0 ) ima isti znak kao f"" (x 0 ), tj. uvjet je zadovoljen f(x 0 )· f"" (x) > 0 . Tako je odabrana točka s apscisom x 0 , u kojoj je tangenta na krivulju g= f(x) na segmentu [ a; b] siječe os Vol. Po bodu x 0 Prvo, prikladno je odabrati jedan od krajeva segmenta.

Razmotrimo Newtonovu metodu na konkretnom primjeru.

Neka nam se daje sve već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

Jednadžba tangente u opći pogled ima ideju:

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

U našem slučaju: y-y 0 =2x 0 ·(x-x 0). Za točku x 0 izaberemo točku B 1 (b; f(b)) = (2,2). Nacrtajte tangentu na funkciju y = f(x) u točki B 1, a označavaju točku presjeka tangente i osi Vol točka x 1. Dobivamo jednadžbu prve tangente: y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Crtanje2. Rezultat prve iteracije

y=f(x) Vol kroz točku x 1, shvatili smo B 2 =(1,5; 0,25). Ponovno nacrtajte tangentu na funkciju y = f(x) u točki B 2, a označavaju točku presjeka tangente i osi Vol točka x 2.

Jednadžba druge tangente: g-0.25=2*1.5(x-1.5), g = 3 x - 4.25.

Sjecište tangente i osi Ox: x 2 =.

Crtanje3. Druga iteracija Newtonove metode

Zatim nalazimo sjecište funkcije y=f(x) a okomica povučena na os Vol kroz točku x 2, dobivamo točku B 3 i tako dalje.

Crtanje4. Treći korak metode tangente

Prva aproksimacija korijena određena je formulom:

= 1.5.

Druga aproksimacija korijena određena je formulom:

=

Treća aproksimacija korijena određena je formulom:

Tako , ja Aproksimacija korijena određena je formulom:

Izračuni se provode sve dok se decimalna mjesta potrebna u odgovoru ne poklope ili dok se ne postigne navedena preciznost e - dok se nejednakost zadovolji | xi- xi-1 | < e.

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

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

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

Na taj način možete izračunati vrijednost "kvadratnog korijena iz 2" s bilo kojim stupnjem točnosti. Ovu izvanrednu metodu izumio je Newton i omogućuje vam vrlo pronalaženje korijena složene jednadžbe.

Newtonova metoda: primjena u C++

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

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

Riža. 1. Početna stranica Visual C++ 2010 Express

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

Riža. 2. Izradite projekt

// Newton.cpp metoda: definira ulaznu točku za konzolnu aplikaciju #include "stdafx.h" #uključi 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 druge derivacije int _tmain(int argc, _TCHAR* argv) int izlaz = 0, i=0;//varijable za izlaz i petlju double x0,xn;//izračunate aproksimacije za korijen dupli a, b, eps; // granice segmenta i zahtijevana točnost cout<<"Please input \n=>"; cin>>a>>b; // unosimo granice segmenta na kojem ćemo tražiti korijen cout<<"\nPlease input epsilon\n=>"; cin>>eps; // unesite traženu točnost izračuna if (a > b) // ako je korisnik pomiješao granice segmenta, zamijeni ih if (f(a)*f(b)>0) // ako su predznaci funkcije na rubovima segmenta isti, tada ovdje nema korijena cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // za odabir početne točke označite f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // uzeti u obzir prvu aproksimaciju cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // nastavit će računati dok ne postignemo traženu točnost xn = x0-f(x0)/df(x0); // izravno Newtonova formula cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) dok (izlaz!=1); // dok korisnik ne unese izlaz = 1

Pogledajmo kako radi. Kliknite na zeleni trokut u gornjem lijevom kutu ekrana ili pritisnite F5.

Ako se pojavi pogreška kompilacije "Pogreška pogreške LNK1123: neuspjeh pretvaranja u COFF: datoteka je nevažeća ili oštećena", tada se to može izliječiti instaliranjem prvog servisnog paketa 1 ili u postavkama projekta Svojstva -> Povezivač onemogućavanjem inkrementalnog povezivanja.

Riža. 4. Rješavanje pogreške kompilacije projekta

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

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

Sada imamo prozor aplikacije:

Riža. 5. Unos ulaznih podataka

Uvedimo granice segmenta 3 i 5, a točnost je 0,05. Program je očekivano proizveo poruku o pogrešci da na ovom segmentu nema korijena.

Riža. 6. Greška "Nema korijena na ovom segmentu!"

Još nećemo otići, pa što je s porukom "Izlaz?" unesite "0".

Sada provjerimo aplikaciju pomoću točnih ulaznih podataka. Unesite segment i točnost 0,0001.

Riža. 7. Izračunavanje korijena sa potrebnom točnošću

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

Za izlaz iz aplikacije unesite "Izlaz?" => 1.

Metoda sekante

Kako bi se izbjegao izračun derivacije, Newtonova metoda može se pojednostaviti zamjenom derivacije 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 sekante niži je od one metode tangente i jednak je u slučaju jednog korijena.

Ova izvanredna veličina naziva se zlatni rez:

Provjerite ovo, pod pretpostavkom da je .

Dakle, do infinitezimala višeg reda

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

Nakon supstitucije imamo: i

Za konvergenciju je potrebno da ona bude pozitivna, dakle .

Budući da nije potrebno poznavanje derivacije, istom količinom izračuna u metodi sekanti (unatoč nižem redu konvergencije) može se postići veća točnost nego u metodi tangente.

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

Čim započne rast, izračuni se zaustavljaju i posljednja se iteracija ne koristi.

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

Metoda parabole

Razmotrimo metodu u tri koraka u kojoj je aproksimacija određena trima prethodnim točkama , i .

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

U Newtonovom obliku to izgleda ovako:

Točka je definirana kao onaj od korijena ovog polinoma koji je po apsolutnoj vrijednosti bliži točki.

Red konvergencije metode parabole viši je od one metode sekante, ali niži od one Newtonove metode.

Važna razlika u odnosu na prethodno razmatrane metode je činjenica da čak i ako se stvarno za stvarno i početne aproksimacije izaberu kao stvarne, metoda parabole može dovesti do složenog korijena izvornog problema.

Ova metoda je vrlo zgodna za pronalaženje korijena polinoma visokog stupnja.

Metoda jednostavne 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: (osobito, činjenica da - kompresija, kao što je lako vidjeti, znači to).

Prema Banachovu teoremu, postoji jedinstvena fiksna točka

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

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

Ako je funkcija diferencijabilna, tada je prikladan kriterij kompresije broj . Doista, prema Lagrangeovom teoremu

Dakle, ako je derivacija manja od jedan, onda je to kompresija.

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

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

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

x = xn + hn. (1.2.3-6)

Brojanje h n male vrijednosti, predstavljamo f(h n + h n) u obliku Taylorovog niza, 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, dobivamo f(x n) + h n f ’(x n) » 0.

Stoga je h n » - f(x n)/ f’(x n). Zamijenimo vrijednost h n u (1.2.3-6) i umjesto točne vrijednosti korijena x dobivamo još jednu aproksimaciju

Formula (1.2.3-8) nam omogućuje da dobijemo niz aproksimacija x 1, x 2, x 3 ..., koji pod određenim uvjetima konvergira na točnu vrijednost korijena 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 točki B 0 na grafu funkcije y = f(x). Točka sjecišta tangente s x-osi uzima se kao nova, točnija aproksimacija x 1. Ponavljanje ovog postupka više puta omogućuje nam dobivanje niza aproksimacija x 0, x 1, x 2 , . . ., koji teži točnoj vrijednosti korijena x.

Izračunska formula 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 se točka B 0 nalazi na grafu funkcije f(x), a hipotenuzu tvori tangenta na graf f(x) u točki B 0, dobivamo

(1.2.3-9)

(1.2.3-10)

Ova se formula podudara s (1.2.3-8) za n-tu aproksimaciju.

Iz slike 1.2.3-6 jasno je da odabir toč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 tom slučaju nije zajamčena konvergencija procesa. U općem slučaju, odabir početne aproksimacije vrši se u skladu sa sljedećim pravilom: početna aproksimacija treba se uzeti kao točka x 0 O, u kojoj je f(x 0)×f''(x 0)>0 , odnosno da se predznaci funkcije i njezine druge derivacije podudaraju.

Uvjeti konvergencije Newtonove metode formulirani su u sljedećem teoremu.

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 točku kao početnu aproksimaciju x 0 O , Što f(x 0).f¢¢(x 0)>0 , tada je korijen jednadžbe f(x)=0 može se izračunati s bilo kojim stupnjem točnosti.

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

(1.2.3-11)

gdje je najmanja vrijednost na

Najveća vrijednost na

Proces izračuna se zaustavlja ako ,

gdje je navedena točnost.

Osim toga, sljedeći izrazi mogu poslužiti kao uvjet za postizanje zadane točnosti pri prečišćavanju korijena pomoću Newtonove metode:

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

Lijeva strana izvorne jednadžbe f(x) i njezina derivacija f’(x) u algoritmu su dizajnirani kao zasebni programski moduli.

Riža. 1.2.3-7. Dijagram algoritma Newtonove metode

Primjer 1.2.3-3. Precizirajte korijene jednadžbe x-ln(x+2) = 0 pomoću Newtonove metode, pod uvjetom da su korijeni ove jednadžbe odvojeni na segmentima x 1 O[-1.9;-1.1] i x 2 O [-0,9;2].

Prva derivacija f’(x) = 1 – 1/(x+2) zadržava svoj predznak na svakom segmentu:

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

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

Druga derivacija f"(x) = 1/(x+2) 2 > 0 za bilo koji x.

Dakle, uvjeti konvergencije su zadovoljeni. Budući da je f""(x)>0 u cijelom rasponu dopuštenih vrijednosti, tada da razjasnimo korijen početne aproksimacije x 1 odaberite x 0 = -1,9 (budući da je f(-1,9)×f”(-1,9)>0). Dobivamo niz aproksimacija:

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

Da pojasnimo korijen x 2 O[-0.9;2] biramo 0 =2 (f(2)×f”(2)>0) kao početnu aproksimaciju. Na temelju x 0 = 2 dobivamo niz aproksimacija: 2,0;1,1817; 1,1462; 1.1461. Vrijednost funkcije f(x) u točki x=1,1461 jednaka je f(1,1461)= -0,00006.

Newtonova metoda ima visoku stopu konvergencije, ali u svakom koraku zahtijeva izračunavanje ne samo vrijednosti funkcije, već i njezine derivacije.

Metoda akorda

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

Nacrtajmo dužinu kroz točke A i B. Sljedeća aproksimacija x 1 je apscisa točke presjeka tetive s 0x osi. Konstruirajmo jednadžbu segmenta ravne linije:

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

Ponovimo postupak izračuna kako bismo dobili sljedeću aproksimaciju korijena - x 2 :

U našem slučaju (sl. 1.2.11) a formula za izračun metode akorda izgledat će ovako

Ova formula vrijedi kada se točka b uzme kao fiksna točka, a točka a djeluje kao početna aproksimacija.

Razmotrimo drugi slučaj (sl. 1.2.3-9), kada .

Jednadžba ravne linije za ovaj slučaj ima oblik

Sljedeća aproksimacija x 1 pri y = 0

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

Treba napomenuti da je fiksna točka u metodi tetive odabrana kao kraj segmenta za koji je zadovoljen uvjet f (x)∙f¢¢ (x)>0.

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

Dovoljni uvjeti koji osiguravaju izračun korijena jednadžbe f(x) = 0 pomoću formule tetive bit će isti kao i za metodu tangente (Newtonova metoda), samo se umjesto početne aproksimacije bira fiksna točka. Metoda akorda je modifikacija Newtonove metode. Razlika je u tome što je sljedeća aproksimacija u Newtonovoj metodi točka presjeka tangente s osi 0X, au metodi tetive - točka presjeka tetive s osi 0X - aproksimacije konvergiraju korijenu s različitih strana. .

Procjena pogreške za metodu akorda dana je izrazom

(1.2.3-15)

Uvjet za završetak iteracijskog procesa metodom akorda

(1.2.3-16)

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

Primjer 1.2.3-4. Pojasnite korijen jednadžbe e x – 3x = 0, odvojen na segmentu s točnošću od 10 -4.

Provjerimo uvjet konvergencije:

Posljedično, a=0 treba odabrati kao fiksnu točku, a x 0 =1 treba uzeti kao početnu aproksimaciju, budući da je f(0)=1>0 i f(0)*f"(0)>0.

Newtonova metoda (tangente) za traženje korijena

Ovo je izumljena iterativna metoda Isaac Newton(Isaak Newton) oko 1664. Međutim, ova se metoda ponekad naziva Newton-Raphsonova metoda, budući da je Raphson izumio isti algoritam nekoliko godina kasnije od Newtona, ali je njegov rad objavljen mnogo ranije.

Zadatak je sljedeći. S obzirom na jednadžbu:

Potrebno je riješiti ovu jednadžbu, točnije, pronaći jedan od njezinih korijena (pod pretpostavkom da korijen postoji). Pretpostavlja se da je neprekidan i diferencijabilan na intervalu.

Algoritam

Ulazni parametar algoritma, osim funkcije, također je početna aproksimacija— neke , od kojih počinje algoritam.

Izračunajmo već , izračunajmo to na sljedeći način. Povucimo tangentu na graf funkcije u točki , te pronađimo točku presjeka te tangente s osi apscisa. postavimo je jednaku pronađenoj točki i ponovimo cijeli proces iz početka.

Lako je dobiti sljedeću formulu:

Intuitivno je jasno da ako je funkcija dovoljno “dobra” (glatka) i nalazi se dovoljno blizu korijena, tada će biti još bliže željenom korijenu.

Stopa konvergencije je kvadratni, što, relativno govoreći, znači da se broj točnih znamenki u približnoj vrijednosti udvostručuje sa svakom iteracijom.

Aplikacija za izračun kvadratnog korijena

Razmotrimo Newtonovu metodu na primjeru izračuna kvadratnog korijena.

Ako zamijenimo , tada nakon pojednostavljenja izraza dobivamo:

Prva tipična verzija problema je kada se daje razlomački broj, a trebate izračunati njegov korijen s određenom točnošću:

dvostruko n; cin >> n; const dvostruki EPS = 1E-15 ; dvostruko x = 1; za (;; ) ( dvostruko nx = (x + n / x) / 2 ; ako (abs (x - nx)< EPS) break ; x = nx; } printf ("%.15lf" , x) ;

Još jedna uobičajena inačica problema je kada trebate izračunati korijen cijelog broja (za zadani, pronađite najveći tako da je ). Ovdje moramo malo promijeniti uvjet zaustavljanja algoritma, jer se može dogoditi da počne “skakati” blizu odgovora. Stoga dodajemo uvjet da ako se vrijednost u prethodnom koraku smanji, ali u trenutnom koraku pokuša porasti, tada se algoritam mora zaustaviti.

int n; cin >> n; int x = 1; bool smanjen = laž; za (;; ) ( int nx = (x + n / x) >> 1 ; if (x == nx || nx > x && smanjeno) prekid ; smanjeno = nx< x; x = nx; } cout << x;

Na kraju, predstavljamo treću opciju - za slučaj duge aritmetike. Budući da broj može biti prilično velik, ima smisla obratiti pozornost na početnu aproksimaciju. Očito, što je bliže korijenu, brže će se postići rezultat. Bit će prilično jednostavno i učinkovito uzeti broj kao početnu aproksimaciju, gdje je broj bitova u broju. Ovdje je Java kod koji demonstrira ovu opciju:

VelikiInteger n; // ulazni podaci BigInteger a = BigInteger.ONE.shiftLeft(n.bitLength()/2); boolean p_dec = false; for (;; ) ( BigInteger b = n.divide (a) .add (a) .shiftRight (1) ; if (a.compareTo (b) == 0 || a.compareTo (b)< 0 && p_dec) break ; p_dec = a.compareTo (b) >0 ; a = b; )

Na primjer, ova verzija koda radi za broj u milisekundama, ali ako uklonimo poboljšani izbor početne aproksimacije (samo počnite s), pokrenut će se za oko milisekundi.

Dok se u školi muče s rješavanjem jednadžbi na satovima matematike, mnogi su učenici često uvjereni da vrijeme gube potpuno uzalud, a ipak će takva vještina u životu dobro doći ne samo onima koji odluče krenuti Descartesovim stopama, već Euler ili Lobačevski.

U praksi, primjerice u medicini ili ekonomiji, česte su situacije kada specijalist treba otkriti kada je koncentracija djelatna tvar pojedinog lijeka postići potrebnu razinu u krvi pacijenta ili je potrebno izračunati vrijeme potrebno da pojedini posao postane isplativ.

Češće govorimo o na rješavanje nelinearnih jednadžbi raznih vrsta. Numeričke metode omogućuju da se to učini što je brže moguće, posebno pomoću računala. Dobro su proučeni i dugo su dokazali svoju učinkovitost. 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. svakom x koji pripada (a, b) može se pridružiti određeni broj g (x).

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

U nekim je slučajevima prikladnije zamijeniti g(x)=0 sa sličnim, npr. g 1 (x) = g 2 (x). U ovom slučaju, apscise (vrijednost x) sjecišta 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 se problem 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 jednostavno pronalaženje vrijednosti argumenta točaka u kojima kvadratni trinom nestaje.

Metode za izdvajanje korijena nelinearnih jednadžbi obično se dijele na analitičke (izravne) i iterativne. U prvom slučaju, željeno rješenje ima oblik formule, koja se koristi za određeni broj aritmetičke operacije možete pronaći značenje korijena koje tražite. Slične metode razvijene su za eksponencijalne, trigonometrijske, logaritamske i jednostavne metode algebarske jednadžbe. Za ostalo morate koristiti posebne numeričke metode. Lako ih je implementirati pomoću računala, koja vam omogućuju pronalaženje korijena s potrebnom točnošću.

To uključuje takozvanu numeričku tangentnu metodu, koju je predložio veliki znanstvenik Isaac Newton krajem 17. stoljeća. U narednim stoljećima metoda je više puta poboljšana.

Lokalizacija

Numeričke metode rješavanja složenih jednadžbi koje nemaju analitička rješenja obično se provode u 2 faze. Najprije ih morate lokalizirati. Ova se operacija sastoji od pronalaženja takvih segmenata na OX na kojima se nalazi jedan korijen jednadžbe koja se rješava.

Razmotrimo segment. Ako g(x) na sebi nema diskontinuiteta i poprima vrijednosti različitih predznaka na krajnjim točkama, tada između a i b ili u njima postoji barem 1 korijen jednadžbe g(x) = 0. Da bi bude jedinstven, potrebno je da g(x) nije monoton. Kao što je poznato, to će svojstvo imati pod uvjetom da je predznak g’(x) konstantan.

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

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

Rješavanje jednadžbe prepolovljavanjem

Prije nego što razmotrimo složenije numeričke tangente i njihove varijante, vrijedi se upoznati s na jednostavan način identificiranje korijena. Zove se dihotomija i odnosi se na intuitivan način pronalaženja korijena, temeljen na teoremu da ako je za g(x), kontinuirano, zadovoljen uvjet različitih predznaka, tada na segmentu koji se razmatra postoji barem 1 korijen g( x) = 0.

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

Prednosti metode su njezina pouzdanost i jednostavnost, ali nedostatak je potreba da se početno identificiraju točke u kojima g(x) ima različite predznake, tako da se ne može koristiti za korijene parne množine. Osim toga, ne generalizira se na slučaj sustava jednadžbi ili ako govorimo o složenim korijenima.

Primjer 1

Želimo riješiti jednadžbu g(x) = 2x 5 + x - 1 = 0. Kako ne bismo dugo tražili odgovarajući segment, gradimo graf koristeći, na primjer, dobro poznati program Excel . 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 jednadžbe.

g"(x) = 10x 4 + 1, tj. radi se o monotono rastućoj funkciji, pa je na odabranom segmentu samo 1 korijen.

Zamjenjujemo krajnje točke u jednadžbu. Imamo 0 odnosno 1. U prvom koraku kao rješenje uzimamo točku 0.5. Tada je g(0,5) = -0,4375. To znači da će sljedeći segment za prepolovljenje biti . Njegova središnja točka je 0,75. U njemu je vrijednost funkcije 0,226. Uzimamo u obzir segment i njegovu sredinu, koja se nalazi u točki 0,625. Računamo da vrijednost g(x) iznosi 0,625. Jednako je -0,11, tj. negativno. Na temelju ovog rezultata odabiremo segment. Dobivamo x = 0,6875. Tada je g(x) = -0,00532. Ako je točnost rješenja 0,01, tada možemo pretpostaviti da je željeni rezultat 0,6875.

Teorijska osnova

Ova metoda pronalaženja korijena pomoću Newtonove metode tangente popularna je zbog svoje vrlo brze konvergencije.

Temelji se na dokazanoj činjenici da ako je x n aproksimacija korijena f(x) = 0, tako da je f" C 1, tada će sljedeća aproksimacija biti u točki gdje jednadžba tangente na f(x) postavljen je na nulu, tj.

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

Tada tangente izgledaju ovako:

Primjer 2

Pokušajmo upotrijebiti Newtonovu klasičnu tangentnu metodu i pronaći rješenje neke nelinearne jednadžbe koju je teško ili nemoguće pronaći analitički.

Neka je potrebno identificirati korijene za x 3 + 4x - 3 = 0 s određenom točnošću, na primjer 0,001. Kao što je poznato, graf bilo koje funkcije u obliku polinoma neparnog stupnja mora barem jednom presijecati os OX, tj. nema sumnje u postojanje korijena.

Prije rješavanja našeg primjera metodom tangente, gradimo graf f(x) = x 3 + 4x - 3 po točkama. To je vrlo jednostavno učiniti, na primjer, pomoću procesora proračunskih tablica programa Excel. Iz dobivenog grafa bit će jasno da se ne siječe s osi OX i da funkcija y = x 3 + 4x - 3 monotono raste. Možemo biti sigurni da jednadžba x 3 + 4x - 3 = 0 ima rješenje i ono je jedinstveno.

Algoritam

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

Tada će druga derivacija biti x * 6.

Koristeći ove izraze, možemo napisati formulu za identificiranje korijena jednadžbe pomoću metode tangente u obliku:

Zatim trebate odabrati početnu aproksimaciju, tj. odlučiti koju ćete točku uzeti u obzir kao početnu točku (volumen x 0) za iterativni proces. Razmatramo krajeve segmenta. Koristit ćemo onu za koju vrijedi uvjet da su funkcija i njena 2. derivacija u x 0 različitih predznaka. Kao što vidimo, pri zamjeni x 0 = 0 ono je pokvareno, ali x 0 = 1 je sasvim prikladno.

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

Na prvom tangentnom koraku imamo:

• x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
• budući da uvjet nije ispunjen, idemo dalje;
• dobivamo novu vrijednost za x 2, koja je jednaka 0,674;
• primijetimo da je omjer vrijednosti funkcije i njezine derivacije u x 2 manji od 0,0063, zaustavljamo proces.

Metoda tangente u Excelu

Prethodni primjer možete puno lakše i brže riješiti ako ne računate ručno (na kalkulatoru), već koristite mogućnosti stolni procesor od Microsofta.

Da biste to učinili, trebate stvoriti novu stranicu u Excelu i ispuniti njezine ćelije sljedećim formulama:

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

U određenom problemu u ćeliji B10 pojavit će se natpis “Dovršavanje iteracija”, a za rješavanje problema trebat ćete uzeti broj napisan u ćeliji koja se nalazi jedan redak iznad. Također možete odabrati zaseban "rastegljiv" stupac za njega unosom formule-uvjeta, prema kojem će rezultat biti zapisan tamo ako sadržaj u jednoj ili drugoj ćeliji stupca B ima oblik "Završetak ponavljanja".

Implementacija u Pascalu

Pokušajmo dobiti rješenje nelinearne jednadžbe y = x 4 - 4 - 2 * x pomoću metode tangente u Pascalu.

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

Program je prepoznatljiv po tome što ne zahtijeva ručni izračun derivacije.

Metoda akorda

Razmotrimo još jedan način identificiranja korijena nelinearnih jednadžbi. Proces iteracije sastoji se u tome da se kao uzastopne aproksimacije željenog korijena za f(x) = 0 uzimaju vrijednosti točaka presjeka tetive s apscisom krajnjih točaka a i b s OX, označen kao x 1, ..., x n. Imamo:

Za točku u kojoj tetiva siječe os OX, izraz će biti napisan kao:

Neka je druga derivacija pozitivna za x £ (suprotan slučaj će se svesti na razmatrani ako napišemo f(x) = 0). U ovom slučaju, graf y = f(x) je krivulja, konveksna na dnu i smještena ispod tetive AB. Mogu postojati 2 slučaja: kada funkcija ima pozitivnu vrijednost u točki a ili je negativna u točki b.

U prvom slučaju odabiremo kraj a kao fiksni, a točku b uzimamo kao x 0. Tada uzastopne aproksimacije prema gornjoj formuli tvore niz koji monotono opada.

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

Dakle, možemo reći da:

• u metodi akorda fiksni kraj segmenta je onaj na kojem se predznaci funkcije i njezine druge derivacije ne poklapaju;
• aproksimacije za korijen x - x m - leže od njega na strani gdje f(x) ima predznak koji se ne poklapa s predznakom f"" (x).

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

Modificirana metoda

Kombinirana metoda akorda i tangenti omogućuje vam da utvrdite korijene jednadžbe pristupajući im s različitih strana. Ova vrijednost, pri kojoj graf f(x) siječe OX, omogućuje preciziranje rješenja mnogo brže nego korištenje svake 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 s početnom aproksimacijom koja odgovara uvjetu da su prva i druga derivacija različitih predznaka u određenoj točki x.

Pod takvim uvjetima, rješavanje nelinearnih jednadžbi metodom tangente omogućuje pronalaženje korijena s viškom ako je x 0 =b, a metoda koja koristi tetive s fiksnim krajem b dovodi do pronalaženja približnog korijena s nedostatkom.

Korištene formule:

Sada se traženi korijen x mora tražiti u intervalu. U sljedećem koraku trebate primijeniti kombiniranu metodu na ovaj segment. Postupajući na ovaj način, dobivamo formule oblika:

Ako prva i druga derivacija imaju različite predznake, tada, razmišljajući na sličan način, da razjasnimo korijen, dobivamo sljedeće rekurentne formule:

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

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

Kombinirana metoda se lako implementira u TURBO PASCAL okruženju. Ako stvarno želite, možete pokušati izvršiti sve izračune koristeći tabelarnu metodu u Excelu.

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

U ovom slučaju, svaki se redak koristi za bilježenje izračuna u određenom koraku iteracije pomoću dvije metode. Zatim se na lijevoj strani područja rješenja na aktivnoj radnoj stranici označava stupac u koji se upisuje rezultat izračuna modula razlike vrijednosti sljedećeg iterativnog koraka za svaku od metoda. Drugi se može koristiti za unos rezultata izračuna temeljenih na formuli za izračun logičke konstrukcije "IF", koja se koristi za otkrivanje je li uvjet istinit ili ne.

Sada znate kako riješiti složene jednadžbe. Metoda tangente, kao što ste već vidjeli, implementirana je vrlo 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 aproksimacija. Pojam P. ponekad se koristi u smislu približavanja objekta (na primjer, inicijal P.) ... Matematička enciklopedija

Newtonova metoda- Newtonova metoda, Newtonov algoritam (također poznata kao metoda tangente) je iterativna numerička metoda za pronalaženje korijena (nule) zadane funkcije. Metodu je prvi predložio engleski fizičar, matematičar i astronom Isaac Newton... ... Wikipedia

Jedna tangentna metoda

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

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

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

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

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

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

Numeričko rješavanje jednadžbi- i njihovih sustava sastoji se od približnog određivanja korijena ili korijena jednadžbe ili sustava jednadžbi i koristi se u slučajevima kada je nemoguće ili vrlo naporno izračunati točnu vrijednost. Sadržaj 1 Prikaz problema 2 Numeričke metode ... Wikipedia

Metoda sukcesivne aproksimacije- metoda za rješavanje matematičkih problema korištenjem niza aproksimacija koje konvergiraju u rješenje i konstruiraju se rekurzivno (tj. svaka nova aproksimacija izračunava se na temelju prethodne; početna aproksimacija odabire se u ... ... Velika sovjetska enciklopedija