Newtonova modificirana metoda.

Navodimo nedostatke Newtonove metode, koji imaju za cilj eliminaciju njenih različitih modifikacija:

teškoća postavljanja početne aproksimacije od koje metoda konvergira;

potreba da se izračuna Jacobian matrica na svakoj iteraciji, što može zahtijevati značajne računske troškove;

potreba za rješavanjem sistema linearnih algebarskih jednačina na svakoj iteraciji;

zahtjev da Jacobijeva matrica bude nedegenerirana.

Razmotrimo modifikacije Newtonove metode, koje u određenoj mjeri otklanjaju navedene nedostatke.

Newtonova metoda sa matricom konstantne po komadima.

Da bi se smanjili računski troškovi iteracija, Jacobijeva matrica u ovoj modifikaciji ostaje konstantna u nekoliko koraka. Broj koraka m, gdje J je konstantan, specificiran je kao parametar u ovoj modifikaciji, ili je trenutak ponovnog izračunavanja Jacobian matrice određen uslovom

u kojoj se, na primjer, (Jacobijeva matrica preračunava samo ako je ovaj uvjet prekršen).

Efikasnost metode se u ovom slučaju postiže ne samo smanjenjem broja proračuna Jacobijeve matrice, već uglavnom zbog činjenice da je na m iteracije metode, potrebno je riješiti linearne sisteme sa istom matricom.

Newton-Raphsonova metoda.

Kako bi se osigurala konvergencija metode sa izabranom početnom aproksimacijom, primjenjuje se modifikacija nazvana Newton-Raphsonova metoda. proračun (k+ 1) aproksimacija u ovoj modifikaciji se vrši prema pravilu

gdje je parametar čija je vrijednost uključena k iteracija se bira iz uslova

Strategija za izbor parametra u iteraciji može biti sljedeća. U početku se uzima probna vrijednost ili, dalje, ova vrijednost se modificira dok se ne ispuni formulirani uvjet. Ovaj uvjet može zahtijevati višestruku evaluaciju vektora u trenutnoj iteraciji. Očigledno, kod , Newton-Raphsonova metoda se poklapa s Newtonovom metodom.

Metode nastavka po parametru.

Ove metode omogućavaju konvergenciju Njutnove metode sa izabranom početnom aproksimacijom.Suština metoda nastavka u odnosu na parametar je da se zameni originalni zadatak redoslijeda zadataka, svaki sljedeći zadatak malo se razlikuje od prethodnog. Niz je konstruisan na način da prvi sistem ima rešenje, i najnoviji sistem odgovara originalnom problemu. Budući da se sistemi malo razlikuju, rješenje prethodnog problema će biti dobra početna aproksimacija za sljedeći. Rješavajući takav slijed problema Newtonovom metodom, na kraju ćemo dobiti rješenje originalnog sistema. Razmotrite metodu za konstruisanje specificiranog niza zadataka.

Neka pri rješavanju sistema

koristi se početno nagađanje. Originalnu jednačinu zamjenjujemo jednadžbom s parametrom

koji za ima rješenje, a za se poklapa sa rješenjem izvornog problema, tj.

Možete odabrati funkcije kao

Podijelimo segment po tačkama na intervale. Dobijamo željeni niz sistema:

Newtonova metoda za loše uslovljene probleme.

Ako je Jacobijeva matrica loše uvjetovana, greška u rješavanju linearnog sistema

može biti značajno zbog grešaka zaokruživanja. Stoga, u

u slučaju loše uslovljenih matrica, kada se izračunava vektor korekcije, sistem

sa numeričkim parametrom, gdje E-matrica identiteta. Za , modificirani sistem se poklapa sa linearni sistem Njutnova standardna metoda, kada teži jedinstvu, broj uslova modifikovanog sistema takođe teži jedinici. Međutim, stopa konvergencije odgovarajuće metode značajno se pogoršava, jer se za , metoda degenerira u metodu jednostavnih iteracija.

Iskustvo pokazuje da u proučavanju nekvadratnih funkcija Newtonova metoda nije baš pouzdana. Zaista, ako je poenta X(0) je na znatnoj udaljenosti od tačke X*, Njutnov korak se često pokaže prevelikim, što može dovesti do nedostatka konvergencije. Metoda se može prilično lako modificirati kako bi se smanjila ciljna funkcija od iteracije do iteracije i traženje duž prave linije, kao u Cauchy metodi. Niz iteracija se gradi u skladu sa formulom

x = x -α f(x)f(x).(3.56)

Izbor α izvedeno na takav način da

f(x) → min;

ovo garantuje ispunjenje nejednakosti

f(x) ≤ f(x).

Takav metod se zove modifikovana Newtonova metoda a u slučajevima kada izračunavanje točnih vrijednosti prve i druge derivacije nije povezano sa značajnim poteškoćama, pokazalo se da je pouzdano i efikasno. Međutim, kada se koristi modificirana Newtonova metoda, na svakoj iteraciji postaje potrebno konstruirati i riješiti linearnu jednadžbu koja sadrži elemente Hesseove matrice f().

Marquardtova metoda

Metoda koja se razmatra je kombinacija Cauchyjeve i Newtonove metode, koja uspješno kombinuje pozitivna svojstva obje metode. Međutim, kada se koristi Marquardtova metoda potrebno informacije o vrijednostima drugih izvoda ciljne funkcije. Gore je napomenuto da gradijent označava smjer najvećeg lokalnog porasta funkcije, a kretanje u smjeru suprotnom od gradijenta od tačke X(0) nalazi se na znatnoj udaljenosti od minimalne tačke X*, obično dovodi do značajnog smanjenja ciljne funkcije. S druge strane, pravci efektivne pretrage u blizini tačke minimuma određuju se Njutnovom metodom. jednostavna ideja Kombinacija Cauchyjeve i Newtonove metode bila je osnova algoritma koji je razvio Marquardt 1963. godine. U skladu sa ovom metodom, smjer pretraživanja je određen jednakošću

s(x(k)) = – [H(k) + λ (k) I] -1 f (x(k)). (3.57)

U ovom slučaju u formulu (3.42) treba staviti α (k) = +1, jer parametar λ omogućava ne samo promjenu smjera pretraživanja, već i podešavanje dužine koraka. Simbol I ovdje se označava matrica identiteta, odnosno matrica, čiji su svi elementi jednaki nuli, osim dijagonalnih elemenata jednakih +1. Na početna faza dodijeljen je parametar pretraživanja λ (0). veliki značaj(npr. 10 4), dakle

[H(0) +λ(0) I] -1 = [λ(0) I] -1 = I. (3.58)

Na ovaj način, velike vrijednostiλ (0) odgovara smjeru pretraživanja s( x (0)) → f (x(0)).Iz formule (3.57) možemo zaključiti da opadanjem λ do nule s(x) mijenja iz smjera suprotnog gradijentu u smjer koji je određen Newtonovom metodom. Ako se nakon prvog koraka dobije točka sa manjom vrijednošću funkcije cilja (tj. f(X (1)) < f(x(0))), treba izabrati λ (1)< λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β >1 i ponovo implementirajte prethodni korak. Ispod su koraci algoritma.

Marquardtov algoritam

Korak 1. Postavite X(0) - početna aproksimacija X*; M- maksimalni (dozvoljeni) broj iteracija; ε je parametar konvergencije.

Korak 2. Stavite k= 0, λ (0) = 10 4 .

Korak 3. Izračunajte komponente f (x(k)).

Korak 4. Da li vrijedi nejednakost?

|| f (x(k))||< ε?

Da: idite na korak 11.

Korak 5. Da li vrijedi nejednakost? k ≥ M?

Da: idite na korak 11.

Ne: idite na sljedeći korak.

Korak 6. Izračunajte s(x(k)) = – [H(k) + λ (k) I] -1 f (x(k)).

Korak 7. Stavite x = xs(x).

Korak 8. Da li vrijedi nejednakost? f(x) < f(x)?

Da: idite na korak 9.

Ne: Idite na korak 10.

Korak 9. Postavite λ (k +1) = ½ λ (k) i k = k+ 1. Idite na korak 3.

Korak 10. Stavite λ (k) = 2λ (k) . Idite na korak 6.

Korak 11 Odštampajte rezultate i zaustavite se.

Marquardtovu metodu karakterizira relativna jednostavnost, svojstvo smanjenja ciljne funkcije u prijelazu s iteracije na iteraciju, visoka stopa konvergencije u blizini minimalne tačke x* , i takođe zbog odsustva postupka pretraživanja duž prave linije. Glavni nedostatak metode je potreba za proračunom H(k) i naknadno rješenje sistema linearne jednačine odgovara (3.57). Ova metoda se široko koristi u rješavanju problema u kojima f(x) zapisuje se kao zbir kvadrata 1) , tj.

f(x) = f(x) + f(x) +…+ f(x). (3.59)

Marquardt je razmatrao ovaj problem. Powell i Bard su, na osnovu kompjuterskih eksperimenata, pokazali da se Marquardtova metoda razlikuje visoka efikasnost prilikom rješavanja problema ove vrste.

Newtonova metoda i metoda sekante

Newtonova metoda u slučaju jednostavnog realnog korijena ima oblik

x k+1 = x k - ――― , k = 1,2,…. (8.6)

f′(xk)

u slučaju korijena višestrukosti r

x k +1 - x k

f ′(x k)―――― + f(x k) = 0 .

Procjena greške je sljedeća:

|x k - x *| £ q |x 0 - x *|, k = 1,2,….

M p+1 |x 0 - x * |

q = ―――――< 1.

m p p(p + 1)

Možete koristiti procjenu greške kao u jednostavnoj metodi iteracije, s obzirom na tu Newtonovu metodu

sx) = x – p ――

x k+1 = x k - ――― , k = 0, 1, ….

f′(x0)

koristi se kada želite izbjeći ponovljeno izračunavanje izvoda ¦¢(xk).

U Newtonovoj metodi potrebno je izračunati derivaciju funkcije, što nije uvijek zgodno. Izvod možete zamijeniti prvom podijeljenom razlikom pronađenom u posljednje dvije iteracije. Tada umjesto Newtonove metode (8.6) dobijamo sekantna metoda

(x k – x k -1)f(x k)

x k+1 = x k - ――――――

f(x k) – f(x k-1)

Da biste započeli proces, morate znati vrijednosti x 0 i x 1 .

ZADACI ZA LABORATORIJSKI RAD.

1. Odvojite realne korijene analitički ili grafički.

2. Pročistite korijene tako što ćete segment podijeliti na pola (ako je moguće) s tačnošću od 0,1.

3. Pročistiti korijene datom metodom sa datom tačnošću.

Za Newtonovu metodu i metodu jednostavne iteracije, broj iteracija potrebnih za postizanje date tačnosti se bira unaprijed ručnim procjenom greške. Za druge metode, iteracije se zaustavljaju nakon razlike dva uzastopne aproksimacije postaje manja od navedene tačnosti.

4. Provjerite rezultate zamjenom pronađenih vrijednosti u jednadžbu.

OPCIJE

1. Pronađite sve korijene jednadžbe

1000000 x 4 - 3000 x 3 + 1000002 x 2 - 3000 x + 2 = 0

sa tačnošću od 0,0001 metodom a) Njutna b) sekante.

2. Pronađite sve korijene jednadžbe

x 4 - 10001,01 x 3 -9800,01 x 2 - 999901 x + 10000 = 0

sa tačnošću od 0,001 a) Njutnova metoda b) Modifikovana Njutnova metoda.

3. Pronađite sve korijene jednadžbe

na segmentu sa tačnošću od 0,001 Njutnovom metodom.

4. Pronađite sve korijene jednadžbe

5. Pronađite korijen jednačine

x 4 - 20 x 3 + 101 x 2 - 20 x + 1 = 0

na intervalu [-1,1] sa tačnošću od 0,0001 Njutnovom metodom sa parametrima

data tačnost.

6. Pronađite korijen jednačine

7. Pronađite sve korijene jednadžbe

x5 - 3x2 + 1 = 0

paraboličkom metodom sa tačnošću od 0,0005.

8. Pronađite prave korijene jednačine

9. Saznajte koji od korijena 0, 1, -1 jednačine

Newtonova metoda konvergira ako krenemo od proizvoljne početne aproksimacije. Koje početne aproksimacije daju divergenciju metode?

10. Pronađite sve korijene jednadžbe

x 3 + 3 x 2 - 1 = 0

jednostavna metoda iteracije sa tačnošću od 0,0005.

11. Pronađite sve korijene jednadžbe

x 4 - 10000,01 x 3 +101 x 2 - 10000,01 x + 100 = 0

tačna do 0,001 a) Newtonova metoda b) modificirana Newtonova metoda.

12. Pronađite korijen jednačine

arccos (x/2) = x 2

na intervalu a) Newtonovom metodom b) modificiranom Newtonovom metodom.

13. Pronađite sve korijene jednadžbe

x 4 - 0,015x 3 + 0,3x 2 + x - 1 = 0

14. Pronađite korijen jednačine

x 3 - sin (2x) \u003d 1

paraboličkom metodom sa tačnošću od 0,001.

15. Pronađite sve korijene jednadžbe

x 3 - 1777x 2 + 777 = 0

na intervalu [-1,1] paraboličkom metodom sa tačnošću od 0,0001

16. Pronađite sve korijene jednadžbe

5555x 4 - 555x 3 - 55x 2 - 5x = 0

sa tačnošću od 0,00001 metodom a) Njutna b) sekante.

17. Pronađite korijen jednačine

arctan(7x) = 0,2

na intervalu [-1,1] a) Newtonova metoda b) modificirana Newtonova metoda.

osamnaest . Pronađite korijen jednačine

sin (x 4) = 1 - 2x

paraboličkom metodom sa tačnošću od 0,0001.

19 . Pronađite korijen jednačine

sa tačnošću od 0,001 po Njutnovoj metodi. Izvodite iteracije sve dok razlika između susjednih iteracija ne postane manja od navedene točnosti. Uporedite potrebne količine iteracije.

20. Pronađite sve korijene jednadžbe

x 3 - 45x 2 + 43 = 0

na segmentu [-2,1] a) modificirana Newtonova metoda b) metoda sekante.

21 . Pronađite korijen jednačine

arcsin(x) + e x = 2

metodom jednostavne iteracije sa tačnošću od 0,001 preliminarnom procenom greške.

22. Pronađite sve korijene jednadžbe

54x4 + x2 - 0,0000001 =0

sa tačnošću od 0,00001 metodom a) Njutna b) sekante.

23. Pronađite sve korijene jednadžbe

tg (x / 3) - x 3 \u003d 0

paraboličkom metodom sa tačnošću od 0,001.

24. Pronađite sve korijene jednadžbe

12x4 + 11x3 -10x2 -999 = 0

na segmentu [-3,5,3] sa tačnošću od 0,0001 Njutnovom metodom sa parametrima

p=1 i p=2. Uporedite broj iteracija potrebnih za postizanje

data tačnost.

25 . Pronađite korijen jednačine

sa tačnošću od 0,0001 po Newton metodi i modifikovanoj Newton metodi. Izvodite iteracije sve dok razlika između susjednih iteracija ne postane manja od navedene točnosti. Uporedite potreban broj iteracija.

ODGOVORI:1) 0,0100; 0,0200 2) 0,688; 10000 3) 0,107; 0,155; 0,361 4) –1,32; 0; 1,32 5) 0,0917; 0,1125 6) 0 7) –0,5611; 0,5992; 1,348 8) –0,637; 1,41 9) –1; 0; 1 10) -2,879; -0,6527; 0,5321 11) 0,231; 10000 12) 1,01817183 13) –1,1468; 0,66935; 1 14) 1,191 15) -0,6611; 0,6614 16) –0,09811;0,19695 17) 0,028959 18) 0,4746 19) 0,987 20) –0,9672; 0,9884; 44,98 21) 0,4369 22) +/- 0,0003 23) +/- 0,581; 0 24) -3,36; 2,875 25) 1,2784.

Modificirana Newtonova metoda je zasnovana na Newtonovoj metodi. Ako se derivacija malo promijeni na segmentu, onda možemo pretpostaviti.

Odavde, za koren jednačine, dobijamo uzastopne aproksimacije

N=0,1,2... (1.16)

Geometrijski, ova metoda znači da tangente u tačkama zamjenjujemo linijama paralelnim sa tangentom krive u fiksnoj tački.

Ova metoda vam omogućava da odbijete ponovljeno izračunavanje derivata u tačkama. Modificirana Newtonova metoda se koristi za rješavanje jednačina u kojima je proračun izvoda naporan i relativno dugotrajan. U drugim slučajevima, bolje je koristiti standardnu ​​Newtonovu metodu.

Ograničenja funkcije i početne aproksimacije za modificiranu i standardnu ​​Newtonovu metodu su ista. Algoritam obje metode je gotovo isti.

Modificirana Newtonova metoda ima linearnu konvergenciju

Metoda ne garantuje dijeljenje nulom ako je .

Primjer. Jednačina.

Primijenite Newtonov metod s parametrom, jer korijen ima višestrukost p=2. Uzimamo početnu aproksimaciju i dobijamo. Root pronađen.

Primjer. Jednačina.

Korijen je izoliran na rezu. Eps greška je 0,000001

Newtonova metoda konvergira u 5 iteracija, modificirana Newtonova metoda u 19 iteracija, metoda pola divizije za 22 iteracije. Konvergencija metode iteracije zavisi od izbora parametra. Sa konvergencijom se postiže u 24 iteracije, konvergencija u 11 iteracija, konvergencija u 6 iteracija, konvergencija u 25 iteracija.

Metoda sekante

Metoda sekante se dobiva iz Newtonove metode zamjenom podijeljene razlike

izračunato poznatim aproksimacijama i.

Shodno tome, dobijena je sljedeća formula metode sekante

. (1.18)

Ova metoda je dvostepena (jer morate znati prethodna dva koraka da biste izvršili novi korak). Po tome se razlikuje od svih prethodno navedenih metoda - jednokorak.

Za metodu sekante prvo se bira početna aproksimacija. Dalje, koristeći formulu druge metode ili na drugi način, izračunava se druga početna aproksimacija. I tek tada, za izračunavanje naknadnih aproksimacija, koristi se formula metode sekante.

Integracija funkcija Izjava problema

Neka je kontinuirana funkcija data na intervalu. Napravimo particiju segmenta sa tačkom i parcijalnim segmentima:

Dužina segmenata je .

Nazovimo integralni zbir

Poziva se definitivni integral funkcije na segmentu

Klase integrabilnih funkcija i njihova svojstva razmatraju se u teoriji matematičke analize i ovdje se ne raspravljaju. Pretpostavit ćemo da je naša funkcija integrabilna na intervalu .

Kako se integral može izračunati u praksi? Za to se obično koristi Newton-Leibnizova formula:

gdje P(x) - antiderivat funkcije F(x) , tj.

Newton-Leibnizova formula igra važnu ulogu u matematička analiza. Ali može li se koristiti prilikom rješavanja problema na računaru? Moguće je, ali ne uvijek (pošto antiderivat ne postoji uvijek).

Da li ga je zgodno koristiti u programiranju? Ne, morate znati primitivce. Osim toga, ako je funkcija data grafom ili tablicom, tada se integral iz nje ne može izračunati ovom formulom.

Ovo nam omogućava da zaključimo da Newton-Leibnizova formula ne daje opću, univerzalnu metodu za pronalaženje određenog integrala proizvoljne funkcije, te se ne preporučuje korištenje u profesionalnim računalnim programima. Newton-Leibniz formula se koristi samo za testiranje novorazvijenih programa u kojima su implementirane druge metode aproksimativne integracije funkcija.

U nastavku će biti predstavljeni univerzalni računski algoritmi za rješavanje problema numeričke integracije. Takve metode omogućavaju izračunavanje integrala direktno iz vrijednosti integranda i ne ovise o načinu na koji je on specificiran.

Odgovarajuće formule se nazivaju numeričkim integracijskim formulama ili kvadraturnim formulama 5 .

Korak particioniranja u ovom slučaju se izračunava po formuli .