Neka je korijen jednadžbe f(x)=0 odvojen na segmentu , a prvi i drugi izvod od f’(x) i f""(x) su kontinuirani i konstantnog predznaka za hn .

Neka se sljedeća aproksimacija korijenu x n dobije (izabere) u nekom koraku preciziranja korijena . Zatim pretpostavimo da je sljedeća aproksimacija dobivena uz pomoć korekcije h n , rezultira točnom vrijednošću korijena

x \u003d x n + h n. (1.2.3-6)

Brojanje h n male vrijednosti, predstavljamo f(x n + h n) kao Taylorov red, 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(h n + h n) = 0, dobijamo f(h n) + h n f ’(h n) » 0.

Dakle, h n "- f (x n) / f'(x n). Zamijenite vrijednost h n u (1.2.3-6) i umjesto tačne vrijednosti korijena x dobijamo još jednu aproksimaciju

Formula (1.2.3-8) vam omogućava da dobijete niz aproksimacija x 1, x 2, x 3 ..., koji, pod određenim uslovima, konvergira na tačnu vrijednost korijena x, to je

Geometrijska interpretacija Newtonove metode je kako slijedi
(Sl.1.2.3-6). Uzimamo desni kraj segmenta b kao početnu aproksimaciju x 0 i u odgovarajućoj tački B 0 na grafu funkcije y = f (x) konstruiramo tangentu. Tačka preseka tangente sa x-osom uzima se kao nova, preciznija aproksimacija x 1 . Ponavljanje ove procedure mnogo puta omogućava vam da dobijete 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 se može vidjeti da izbor 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: za početnu aproksimaciju treba uzeti takvu tačku x 0 n, u kojoj je f (x 0) × f '' (x 0) > 0, odnosno podudaraju se predznaci funkcije i njenog drugog izvoda.

Uslovi konvergencije za Newtonovu metodu su formulisani u sljedeć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 na 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 obračuna se prekida ako ,

gdje je navedena tačnost.

Osim toga, uslov za postizanje date tačnosti pri prečišćavanju korijena Newtonovom metodom može biti sledeće izraze:

Šema algoritma Newtonove metode prikazana 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. Algoritamski dijagram Newtonove metode

Primjer 1.2.3-3. Pročistite korijene jednačine x-ln(x+2) = 0 koristeći Newtonov metod, pod uslovom da su korijeni ove jednačine razdvojeni na segmentima x 1 n[-1.9;-1.1] i x 2 n [-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) \u003d 1 / (x + 2) 2\u003e 0 za bilo koji x.

Dakle, uslovi konvergencije su zadovoljeni. Pošto je f "" (x)> 0 u cijelom rasponu dozvoljenih vrijednosti, onda da se precizira korijen za početnu aproksimaciju x 1 odaberite x 0 \u003d -1,9 (pošto je 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 .

Da bismo precizirali korijen x 2 n[-0,9;2], biramo kao početne aproksimacije 0 =2 (f(2)×f”(2)>0). 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 pravi segment kroz tačke A i B. Sledeća aproksimacija x 1 je apscisa presečne tačke tetive sa 0x osom. Konstruirajmo jednačinu pravolinijskog segmenta:

Stavimo y=0 i pronađemo vrijednost x=x 1 (još jedna aproksimacija):

Ponavljamo proces izračunavanja kako bismo dobili sljedeću aproksimaciju korijenu - x 2 :

U našem slučaju (Sl.1.2.11) a formula za izračunavanje metode 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 rekurzivna formula za metodu akorda za ovaj slučaj ima oblik

Treba napomenuti da se za fiksnu tačku u metodi tetiva bira 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 po formuli tetiva biće isti kao kod tangentne metode (Newtonova metoda), ali 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 Newtonovom metodu tačka presjeka tangente sa osom 0X, au metodi tetiva - tačka presjeka tetive sa osom 0X - aproksimacije konvergiraju korijenu iz različite strane.

Procjena greške metode akorda određena je izrazom

(1.2.3-15)

Uslov završetka procesa iteracije metodom akorda

(1.2.3-16)

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

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

Provjerimo uvjet konvergencije:

Stoga, a=0 treba odabrati kao fiksnu tač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 .

Mučeći se u školi oko rješavanja jednačina na časovima matematike, mnogi učenici su često sigurni da gube vrijeme, a u međuvremenu će takva vještina dobro doći u životu ne samo onima koji odluče krenuti stopama Dekarta, Ojlera ili Lobachevsky.

U praksi, na primjer, u medicini ili ekonomiji, često se dešavaju situacije kada specijalista treba otkriti kada koncentracija aktivne tvari određenog lijeka dostigne potrebnu razinu u krvi pacijenta, ili je potrebno izračunati vrijeme potrebno da bi određeni posao postao profitabilan.

Najčešće mi pričamo o rješenju nelinearnih jednačina različitih tipova. Da se to uradi što je brže moguće, posebno uz upotrebu računara, numeričke metode dozvoljavaju. Dobro su proučeni i odavno su dokazali svoju efikasnost. Među njima je i Newtonova tangentna metoda, koja je predmet ovog članka.

Formulacija problema

U ovom slučaju postoji funkcija g, koja je data na intervalu (a, b) i na njoj uzima određene vrijednosti, tj. moguće je pridružiti određeni broj g (x) svakom x koji pripada ( a, b).

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, 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 važno je i za probleme optimizacije, za koje je uvjet lokalnog ekstrema konverzija derivacije funkcije u 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 učenik zna formule, pomoću kojih možete lako pronaći vrijednosti argumenta tačaka u kojima je kvadratni trinom nula.

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 elementarne algebarske jednačine. Za ostalo treba koristiti posebne numeričke metode. Lako ih je implementirati uz pomoć računara, koji vam omogućavaju da pronađete korijene sa potrebnom preciznošću.

Među njima je i takozvana numerička metoda tangenta, koju je krajem 17. veka predložio veliki naučnik Isak Njutn. 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 u pronalaženju takvih segmenata na OX na kojima postoji jedan korijen jednačine koja se rješava.

Razmotrimo segment. Ako g(x) na njemu nema diskontinuiteta i uzima vrijednosti različitih predznaka na krajnjim tačkama, tada između a i b ili samih po sebi postoji najmanje 1 korijen jednadžbe g(x) = 0. Da bi se biti jedinstven, potrebno je da je g(x) monoton. Kao što je poznato, imaće takvo svojstvo pod uslovom da je g’(x) konstantnog predznaka.

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

U ovom slučaju, trebate znati da ovaj kriterij neće raditi za korijene jednadžbi koje su višestruke.

Rješavanje jednačine dijeljenjem na pola

Prije nego što razmotrimo složenije numeričke tangente i njegove varijante), vrijedi se upoznati s najviše na jednostavan način identifikovanje korena. Zove se dihotomija i odnosi se na intuitivno pronalaženje korijena na temelju teoreme 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) jednaki su ili manji 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 tačnost određivanja korijena jednadžbe na .

Prednosti metode uključuju njenu pouzdanost i jednostavnost, a 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 sa ravnomjernom množinom. Osim toga, ne generalizira se na slučaj sistema jednačina ili kada su u pitanju kompleksni korijeni.

Primjer 1

Neka ž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 željene jednačine.

g "(x) \u003d 10x 4 + 1, tj. ovo je monotono rastuća funkcija, stoga postoji samo 1 korijen na odabranom segmentu.

Zamijenite krajnje tačke u jednadžbu. Imamo 0 i 1 respektivno. U prvom koraku kao rješenje uzimamo tačku 0,5. Tada je g(0,5) = -0,4375. Dakle, sljedeći segment za dijeljenje na pola bit će. Njegova sredina je 0,75. U njemu je vrijednost funkcije 0,226. Uzimamo u obzir segment i njegovu sredinu, koja se nalazi u tački 0,625. Izračunajte vrijednost g(x) do 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 tako da je f" C 1 , tada će sljedeća aproksimacija biti u tački gdje jednačina tangente na f(x) nestaje , tj.

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

Tada tangenta izgleda ovako:

Primjer 2

Pokušajmo koristiti klasičnu Newtonovu 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 otkriti korijene za x 3 + 4x - 3 = 0 sa određenom preciznošću, na primjer 0,001. Kao što znate, graf bilo koje funkcije u obliku polinoma neparnog stepena mora barem jednom prijeći osu OX, tj. nema razloga sumnjati u postojanje korijena.

Prije rješavanja našeg primjera metodom tangente, crtamo f (x) = x 3 + 4x - 3 tačku po tačku. To je vrlo lako učiniti, na primjer, koristeći Excel tabelu. Iz rezultirajućeg grafa vidjet će se da se siječe s OX osi i 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 izgledati kao x * 6.

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

Zatim, potrebno je odabrati početnu aproksimaciju, tj. odrediti koju tačku smatrati početnom (rev. x 0) za iterativni proces. Razmatramo krajeve segmenta. Za nas je pogodan onaj za koji je tačan uslov funkcije i njenog 2. izvoda na x 0. Kao što vidite, kada se zamjenjuje x 0 = 0, to se krši, ali je x 0 = 1 sasvim prikladno.

onda ako nas zanima rješenje po metodi tangenta sa tačnošću e, onda se za vrijednost x n može smatrati da 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 kalkulacije ne radite ručno (na kalkulatoru), već koristite mogućnosti Microsoftovog procesora proračunskih tablica.

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

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

U određenom zadatku, već u ćeliji B10, pojavit će se natpis "Završetak iteracija", a za rješavanje problema morat ćete uzeti broj napisan u ćeliji koja se nalazi jedan red iznad. Za njega možete odabrati i zaseban stupac koji se može rastegnuti tako da tamo unesete uvjetnu formulu, prema kojoj ć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) \u003d (f (x + delta) - f (x)) / delta. Kao uslov za završetak iterativnog procesa, odabrat ćemo ispunjenje nejednakosti |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

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

metoda akorda

Razmotrite još jedan način za identifikaciju korijena 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 apscisama krajnjih tačaka a i b sa OX , označeno kao x 1 , ..., x n . Imamo:

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

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

U prvom slučaju biramo kraj a kao fiksni, a za x 0 uzimamo tačku b. 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:

• fiksiran u metodi tetiva je onaj kraj segmenta gdje 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 zadovolje 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, približavajući im se s različitih strana. Takva vrijednost, pri kojoj f(x) graf 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 koristiti bilo koju od gore opisanih metoda. Međutim, bolje je isprobati njihovu kombinaciju, što će značajno povećati točnost korijena.

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

Pod takvim uvjetima, rješenje nelinearnih jednadžbi tangentnom metodom omogućava pronalaženje korijena s viškom ako je x 0 =b, a metoda koja koristi tetive na fiksnom kraju b dovodi do pronalaženja približnog korijena s nedostatkom.

Korišćene formule:

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

Ako postoji razlika u predznaku između prve i druge derivacije, onda, argumentirajući na sličan način, da preciziramo korijen, dobijamo sljedeće rekurzivne formule:

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

Ako je gornja nejednakost tačna, tada se kao korijen nelinearne jednadžbe na datom intervalu uzima tačka, koja je tačno u sredini između rješenja pronađenih u određenom koraku iteracije.

Kombinovani metod se lako implementira u TURBO PASCAL okruženju. Uz veliku želju, možete pokušati izvršiti sve proračune pomoću tabelarne metode u programu Excel.

U potonjem slučaju odabire se nekoliko stupaca 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 iterativnom koraku za dvije metode. Zatim, u lijevom dijelu područja rješenja, na aktivnoj radnoj stranici, istaknut je stupac u koji se unosi rezultat izračunavanja modula razlike vrijednosti sljedećeg koraka iteracije za svaku od metoda. Drugi se može koristiti za unos rezultata proračuna prema formuli proračuna logičke konstrukcije "IF", kojom se utvrđuje da li je uslov ispunjen 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 uspostaviti korijene jednadžbe koju je teško ili nemoguće riješiti pomoću formula.

Svi ljudi prirodno traže znanje. (Aristotel. Metafizika)

Numeričke metode: rješavanje nelinearnih jednačina

Problemi rješavanja jednačina se stalno javljaju u praksi, na primjer, u ekonomiji, kada se razvija posao, želite da znate kada profit dostigne određenu vrijednost, u medicini, kada se proučava djelovanje lijekova, važno je znati kada je koncentracija supstance dostigne određeni 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 metodu najveće vjerovatnoće, također se moraju rješavati nelinearne jednačine i sistemi jednačina.

Dakle, postoji čitava klasa problema vezanih za pronalaženje rješenja nelinearne jednačine, npr. jednačine ili jednačine, itd.

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

Svaka vrijednost x iz ovog segmenta možemo upariti broj , ovo je funkcionalan zavisnost, ključni koncept matematike.

Moramo pronaći takvu vrijednost na kojoj se takvi nazivaju korijenima funkcije

Vizuelno moramo odrediti tačku presjeka grafa funkcijesa osom apscisa.

Metoda bisekcije

Najjednostavniji metod za pronalaženje korijena jednadžbe je metoda bisekcije, 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 tačke i takve da i imamo razne znakova, onda između ovih točaka postoji barem jedan korijen funkcije .

Podijelite segment na pola i unesite srednji 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 njegov 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 bisekcije uključuju njenu visoku pouzdanost i jednostavnost.

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

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

Newtonova metoda: teorijske osnove

Newtonova klasična metoda ili tangente leži u činjenici 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 tangentnoj jednadžbi stavljamo i .

Tada je algoritam sekvencijalnih proračuna 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 i više, tada red konvergencije opada i postaje linearan.

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

Vježba 2. Metodom tangenta pronađite rješenje jednačine na intervalu (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 , inače postoji konvergencija samo u nekom susjedstvu korijena.

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

Vizualizacija Newtonove metode

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

1) funkcija y= f(x) je definiran i kontinuiran za ;

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

3) derivati f"(x) i f""(x) zadrži znak na segmentu [ 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 intervalu [ a; b] takav broj se bira x 0 , pod kojim f(x 0 ) ima isti predznak kao f"" (x 0 ), odnosno uslov f(x 0 )· f"" (x) > 0 . Tako se bira tačka sa apscisom x 0 , gdje je tangenta na krivu y= f(x) na segmentu [ a; b] prelazi osu Ox. Za bod 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 intervalu (0;2) i ima f"(x) = 2 x > 0 i f "" (x) = 2 > 0 .

Slika1 . f(x)=x 2 -2

Tangentna jednadžba u opšti pogled ima reprezentaciju:

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

u našem slučaju: y-y 0 \u003d 2x 0 (x-x 0). Kao tačku x 0 izaberite tačku B 1 (b; f(b)) = (2,2). Povlačimo 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 =

Slika2. Rezultat prve iteracije

y=f(x) Ox kroz tačku x 1, dobili smo poen 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 x2.

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 =.

Slika3. Druga iteracija Newtonove metode

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

Slika4. 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:

Na ovaj način , i-ta aproksimacija korijena određena je formulom:

Proračuni se vrše sve dok se ne poklapaju decimalna mjesta koja su potrebna u odgovoru, odnosno dok se ne postigne navedena tačnost 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.

Tako je moguće izračunati vrijednost vrijednosti "kvadratni korijen iz 2" sa bilo kojim stepenom tačnosti. Ovu divnu metodu je izumio Newton i omogućava vam da pronađete korijene vrlo složenih jednadžbi.

Newtonova metoda: C++ aplikacija

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

Počnimo sa Visual C++ 2010 Express. Pojavit će se početni prozor programa. U lijevom kutu kliknite na "Kreiraj projekat".

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

U izborniku koji se pojavi odaberite "Win32 Console Application", unesite naziv aplikacije "Newton_Method".

Rice. 2. Kreirajte projekat

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 tretira ili instaliranjem prvog servisnog paketa 1, ili u postavkama projekta Svojstva -> Linker, onemogućite inkrementalno povezivanje.

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

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

Prvo, testirajmo aplikaciju na "pogrešnim" ulaznim podacima. Na segmentu nema korijena, naš program bi trebao dati poruku o grešci.

Imamo prozor aplikacije:

Rice. 5. Unos ulaznih podataka

Uvodimo granice segmenta 3 i 5, a tačnost je 0,05. Program je, kako i treba, dao poruku o grešci da nema root-a na ovom segmentu.

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

Nećemo još krenuti, pa će se pojaviti poruka “Izlaz?” unesite "0".

Sada testirajmo aplikaciju na ispravnim ulaznim podacima. Hajde da uvedemo segment i tačnost od 0,0001.

Rice. 7. Izračunavanje korijena sa potrebnom preciznošću

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

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

Metoda sekante

Da bi se izbjeglo izračunavanje derivata, Newtonova metoda se može pojednostaviti zamjenom izvoda s približnom vrijednošću izračunatom iz dvije prethodne 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 divna vrijednost se zove zlatni omjer:

Provjeravamo ovo pretpostavljajući radi pogodnosti da .

Dakle, do infinitezimima 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, onda se sa istom količinom proračuna u metodi sekante (uprkos nižem redu konvergencije) može postići veća tačnost nego u metodi tangente.

Imajte na umu da u blizini korijena treba podijeliti s malim brojem, a to dovodi do gubitka tačnosti (posebno u slučaju više korijena), stoga, odabirom relativno malog , vrši se izračunavanje do izvrš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 Harvick.

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 je definirana kao ona korijena ovog polinoma, koji je po modulu 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 je realno za realno i ako su početne aproksimacije odabrane da budu realne, metoda parabole može dovesti do kompleksnog korijena originalnog problema.

Ova metoda je vrlo korisna 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 kontrakcija.

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

U problemu minimiziranja funkcije od najveće je važnosti dobar izbor početne aproksimacije.Naravno, nemoguće je doći do opšteg 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 za mali broj intrinzično nelinearnih parametara. Često su funkcije raspoređene na takav način da prilikom fiksiranja vrijednosti nekih parametara (koje zapravo nazivamo nelinearnim), ostali parametri postaju linearni.

S obzirom na tada donju i gornju granicu za nelinearne parametre, uz određeni korak, moguće je nabrojati opcije na rezultujućoj mreži vrijednosti ovih odgovarajućih nelinearnih parametara i identificirati linearnu regresiju koja vodi do minimalni zbir kvadrata.

Kao primjer, razmotrite funkciju

Ovdje će stvarni nelinearni parametar biti . Pretpostavimo da to znamo. Neka je h korak za parametar . Izračunaj linearne regresije

gdje i pronaći za svaki od njih minimalni zbir kvadrata. Najmanji od njih odgovara optimalnoj početnoj aproksimaciji. U principu, korak, o kojem ovisi "gustoća" 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. Konverzija modela.

Ponekad, nekom transformacijom, model se može svesti na linearni, ili se broj intrinzično nelinearnih parametara može smanjiti (vidi Odjeljak 6.2.3). Pokazujemo kako se to može postići na primjeru logističke krive

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

Označavajući 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 aditivno ušla u izvornu jednačinu, nakon transformacije, općenito govoreći, više neće biti aditivna.

Koristeći proširenje u Taylorov niz i označavajući transformaciju kroz dobijamo, zanemarujući uslove reda

Otuda to sledi

Posljednja jednakost može se uzeti kao osnova za analizu problema s 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 proseke preko y i preko X, koje označavamo redom m. Rešavamo sistem nelinearnih jednačina za

Rješenje ovog sistema ć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 smislu parametara. Da biste pronašli grubu početnu aproksimaciju, ponekad je korisno aproksimirati regresiju proširivanjem u Taylorov niz u smislu nezavisnih varijabli. Radi jednostavnosti, pretpostavićemo da je jednodimenzionalan. Neka - prosječna vrijednost, zatim približno

Označimo , tako dolazimo do linearnog modela

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

Newtonova (tangentna) metoda za pronalaženje korijena

Ovo je iterativni metod izmišljen Isaac Newton(Isaak Newton) oko 1664. Međutim, ponekad se ova metoda naziva Newton-Raphsonova metoda (Raphson), 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 jednačinu:

Potrebno je riješiti ovu jednačinu, tačnije pronaći jedan od njenih korijena (pretpostavlja se da korijen postoji). Pretpostavlja se da je kontinuirano i diferencibilno na segmentu .

Algoritam

Ulazni parametar algoritma, pored funkcije, je i početna aproksimacija- neki , od kojih algoritam počinje da ide.

Neka je već izračunato, izračunajte na sljedeći način. Nacrtajmo tangentu na graf funkcije u tački , i pronađemo tačku presjeka ove tangente sa x-osom. postavite jednaku pronađenoj tački i ponovite cijeli proces od početka.

Lako je dobiti sljedeću formulu:

Intuitivno je jasno da ako je funkcija dovoljno "dobra" (glatka) i dovoljno blizu korijenu, onda će biti još bliže željenom korijenu.

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

Aplikacija za izračunavanje kvadratnog korijena

Razmotrimo Newtonovu metodu koristeći primjer izračunavanja kvadratnog korijena.

Ako zamijenimo , tada nakon pojednostavljenja izraza dobivamo:

Prva tipična verzija problema je kada je dat razlomak i morate izračunati njegov korijen s određenom preciznošću:

Druga uobičajena verzija problema je kada trebate izračunati cjelobrojni korijen (za dati, pronaći najveći takav da ). Ovdje moramo malo promijeniti uslov zaustavljanja algoritma, jer se može dogoditi da počne da "skače" blizu odgovora. Stoga dodajemo uslov da ako se vrijednost u prethodnom koraku smanjila, a u trenutnom se pokuša povećati, tada algoritam mora biti zaustavljen.

Konačno, dajemo treću opciju - za slučaj duge aritmetike. Budući da broj može biti prilično velik, ima smisla obratiti pažnju na početnu aproksimaciju. Očigledno, što je bliže korijenu, brže će se postići rezultat. Biće prilično jednostavno i efikasno uzeti kao početnu aproksimaciju broj, gde je broj bitova u broju. Evo Java koda koji demonstrira ovu opciju:

BigIntegern; // ulazni podaci BigInteger a = BigInteger.ONE .shiftLeft (n.bitLength () / 2 ) ; boolean p_dec = false; za (;; ) ( BigInteger b = n.podijeli (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 varijanta koda radi za broj u milisekundama, a ako uklonite poboljšani izbor početne aproksimacije (samo počnite sa ), tada će se pokrenuti za otprilike milisekunde.