Newtonova modificirana metoda.

Navodimo nedostatke Newtonove metode, čiji je cilj eliminirati njezine različite modifikacije:

poteškoće postavljanja početne aproksimacije iz koje metoda konvergira;

potreba za izračunavanjem Jacobianove matrice pri svakoj iteraciji, što može zahtijevati značajne troškove računanja;

potreba rješavanja sustava linearnih algebarskih jednadžbi u svakoj iteraciji;

zahtjev da Jacobijeva matrica bude nedegenerirana.

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

Newtonova metoda s komadno konstantnom matricom.

Kako bi se smanjio računalni trošak ponavljanja, Jacobijeva matrica u ovoj modifikaciji ostaje konstantna tijekom nekoliko koraka. Broj koraka m, gdje J je konstantan, naveden je kao parametar u ovoj modifikaciji ili je trenutak ponovnog izračuna Jakobijeve matrice određen uvjetom

u kojem se npr. (Jacobijeva matrica ponovno izračunava samo ako je ovaj uvjet prekršen).

Učinkovitost metode postiže se u ovom slučaju ne samo smanjenjem broja izračuna Jacobijeve matrice, već uglavnom zbog činjenice da na m ponavljanja metode, potrebno je riješiti linearne sustave s istom matricom.

Newton-Raphsonova metoda.

Kako bi se osigurala konvergencija metode iz odabrane početne aproksimacije, primjenjuje se modifikacija nazvana Newton-Raphsonova metoda. izračun (k+ 1) aproksimacija u ovoj modifikaciji provodi se prema pravilu

gdje je parametar čija je vrijednost on k iteracija je odabrana iz uvjeta

Strategija za odabir parametra u iteraciji može biti sljedeća. U početku se uzima probna vrijednost ili se dalje ta vrijednost modificira dok se ne ispuni formulirani uvjet. Ovaj uvjet može zahtijevati višestruko vrednovanje vektora u trenutnoj iteraciji. Očito, pri , Newton-Raphsonova metoda podudara se s Newtonovom metodom.

Metode nastavka po parametru.

Ovim metodama je moguće osigurati konvergenciju Newtonove metode iz odabrane početne aproksimacije. Bit metoda nastavka po parametru je zamjena izvorni problem redoslijed zadataka, svaki sljedeći zadatak malo se razlikuje od prethodnog. Niz je konstruiran na takav način da prvi sustav ima rješenje, i najnoviji sustav odgovara izvornom problemu. Budući da se sustavi malo razlikuju, rješenje prethodnog problema bit će dobra početna aproksimacija za sljedeći. Rješavajući takav niz problema Newtonovom metodom, na kraju ćemo dobiti rješenje izvornog sustava. Razmotrite metodu za konstruiranje navedenog niza zadataka.

Neka pri rješavanju sustava

koristi se početna pretpostavka. Zamijenimo izvornu jednadžbu jednadžbom s parametrom

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

Možete odabrati funkcije kao

Podijelimo segment po točkama na intervale. Dobivamo željeni slijed sustava:

Newtonova metoda za loše uvjetovane probleme.

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

može biti značajan zbog pogrešaka zaokruživanja. Stoga, u

u slučaju loše uvjetovanih matrica, pri izračunavanju vektora korekcije, sustav

s numeričkim parametrom, gdje E-Matrica identiteta. Za , modificirani sustav se podudara s linearni sustav Newtonova standardna metoda, kada teži jedinici, uvjetni broj modificiranog sustava također teži jedinici. Međutim, brzina konvergencije odgovarajuće metode značajno se pogoršava, jer za , metoda degenerira u metodu jednostavnih iteracija.

Iskustvo pokazuje da u proučavanju nekvadratnih funkcija Newtonova metoda nije baš pouzdana. Dapače, ako je točka x(0) je na znatnoj udaljenosti od točke X*, Newtonov korak često se pokaže pretjerano velikim, š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 po ravnoj liniji, kao kod Cauchyjeve metode. Redoslijed ponavljanja izgrađen je u skladu s formulom

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

Izbor α provedena na način da

f(x) → min;

to jamči ispunjenje nejednakosti

f(x) ≤ f(x).

Takva se metoda naziva modificirana Newtonova metoda iu slučajevima kada izračun točnih vrijednosti prvog i drugog izvoda nije povezan sa značajnim poteškoćama, ispada da je pouzdan i učinkovit. Međutim, kada se koristi modificirana Newtonova metoda, pri svakoj iteraciji postaje potrebno konstruirati i riješiti_linearnu jednadžbu koja sadrži elemente Hesseove matrice f().

Marquardtova metoda

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

s(x(k)) = – [H(k) + λ (k) ja] -1 f (x(k)). (3,57)

U ovom slučaju, u formuli (3.42) treba staviti α (k) = +1, budući da parametar λ omogućuje ne samo promjenu smjera pretraživanja, već i podešavanje duljine koraka. Simbol ja ovdje je označena matrica identiteta, tj. matrica čiji su svi elementi jednaki nuli, osim dijagonalnih elemenata jednakih +1. Na početno stanje dodijeljen je parametar pretraživanja λ (0). veliki značaj(npr. 10 4), dakle

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

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

Marquardtov algoritam

Korak 1. Postavite x(0) - početna aproksimacija do X*; M- najveći (dopušteni) broj ponavljanja; ε je parametar konvergencije.

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

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

Korak 4. Vrijedi li nejednakost?

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

Da: idite na korak 11.

Korak 5. Vrijedi li nejednakost? k ≥ M?

Da: idite na korak 11.

Ne: prijeđite na sljedeći korak.

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

Korak 7. Stavite x = xs(x).

Korak 8. Vrijedi li 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 Ispišite rezultate i zaustavite se.

Marquardtovu metodu karakterizira relativna jednostavnost, svojstvo opadanja funkcije cilja pri prijelazu iz iteracije u iteraciju, visoka stopa konvergencije u blizini minimalne točke. x*, i također izostankom postupka traženja po ravnoj liniji. Glavni nedostatak metode je potreba za izračunavanjem H(k) i naknadno rješenje sustava linearne jednadžbešto odgovara (3.57). Ova metoda ima široku primjenu u rješavanju problema u kojima f(x) zapisuje se kao zbroj kvadrata 1) , tj.

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

Upravo je ovaj problem razmatrao Marquardt. Powell i Bard su na temelju računalnih 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 pravog 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 pogreš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 pogreške kao u metodi jednostavne iteracije, s obzirom na to da je Newtonova metoda

sx) = x – p ――

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

f′(x0)

koristi se kada se želi izbjeći ponavljanje izračuna derivacije ¦¢(xk).

U Newtonovoj metodi potrebno je izračunati derivaciju funkcije, što nije uvijek zgodno. Derivaciju možete zamijeniti prvom podijeljenom razlikom pronađenom tijekom zadnje dvije iteracije. Tada umjesto Newtonove metode (8.6) dobivamo 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 dijeljenjem segmenta na pola (ako je moguće) s točnošću od 0,1.

3. Pročistiti korijene zadanom metodom sa zadanom točnošću.

Za Newtonovu metodu i metodu jednostavne iteracije, broj iteracija potrebnih za postizanje zadane točnosti odabire se unaprijed ručnom procjenom pogreške. Za druge metode, iteracije prestaju nakon razlike od dva uzastopne aproksimacije postaje manja od navedene toč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

s točnošću od 0,0001 metodom a) Newtona b) sekante.

2. Pronađite sve korijene jednadžbe

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

s točnošću 0,001 a) Newtonova metoda b) Modificirana Newtonova metoda.

3. Pronađite sve korijene jednadžbe

na segmentu s točnošću od 0,001 Newtonovom metodom.

4. Pronađite sve korijene jednadžbe

5. Pronađite korijen jednadžbe

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

na intervalu [-1,1] s točnošću 0,0001 Newtonovom metodom s parametrima

dana točnost.

6. Pronađite korijen jednadžbe

7. Pronađite sve korijene jednadžbe

x5 - 3x2 + 1 = 0

paraboličnom metodom s točnošću od 0,0005.

8. Pronađite prave korijene jednadžbe

9. Odredite koji od korijena 0, 1, -1 jednadžbe

Newtonova metoda konvergira ako pođemo 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

metoda jednostavne iteracije s toč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

točnost do 0,001 a) Newtonova metoda b) modificirana Newtonova metoda.

12. Pronađite korijen jednadžbe

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 jednadžbe

x 3 - grijeh (2x) \u003d 1

paraboličnom metodom s točnošću od 0,001.

15. Pronađite sve korijene jednadžbe

x 3 - 1777x 2 + 777 = 0

na intervalu [-1,1] paraboličnom metodom s točnošću od 0,0001

16. Pronađite sve korijene jednadžbe

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

s točnošću od 0,00001 metodom a) Newtona b) sekante.

17. Pronađite korijen jednadžbe

arctan(7x) = 0,2

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

osamnaest . Pronađite korijen jednadžbe

grijeh (x 4) = 1 - 2x

paraboličnom metodom s točnošću od 0,0001.

19 . Pronađite korijen jednadžbe

s točnošću od 0,001 Newtonovom metodom. Izvodite iteracije sve dok razlika između susjednih iteracija ne postane manja od navedene točnosti. Usporedi potrebne količine ponavljanja.

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 jednadžbe

arcsin(x) + e x = 2

metodom jednostavne iteracije s točnošću od 0,001 izradom preliminarne procjene pogreške.

22. Pronađite sve korijene jednadžbe

54x4 + x2 - 0,0000001 =0

s točnošću od 0,00001 metodom a) Newtona b) sekante.

23. Pronađite sve korijene jednadžbe

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

paraboličnom metodom s točnošću od 0,001.

24. Pronađite sve korijene jednadžbe

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

na segmentu [-3,5,3] s točnošću od 0,0001 Newtonovom metodom s parametrima

p=1 i p=2. Usporedite broj ponavljanja potrebnih za postizanje

dana točnost.

25 . Pronađite korijen jednadžbe

s točnošću od 0,0001 Newtonovom metodom i modificiranom Newtonovom metodom. Izvodite iteracije sve dok razlika između susjednih iteracija ne postane manja od navedene točnosti. Usporedite potreban broj ponavljanja.

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 temelji se na Newtonovoj metodi. Ako se derivat neznatno mijenja na segmentu, tada možemo pretpostaviti.

Odavde, za korijen jednadžbe, dobivamo uzastopne aproksimacije

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

Geometrijski, ova metoda znači da tangente u točkama zamijenimo linijama paralelnim s tangentama na krivulju u fiksnoj točki.

Ova metoda vam omogućuje da odbijete ponovljeni izračun derivata u točkama. Modificirana Newtonova metoda koristi se za rješavanje jednadžbi u kojima je izračun derivacije naporan i relativno dugotrajan. U ostalim 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 jamči dijeljenje s nulom ako je .

Primjer. Jednadžba.

Primijeniti Newtonovu metodu s parametrom, jer korijen ima višestrukost p=2. Uzimamo početnu aproksimaciju i dobivamo. Pronađen korijen.

Primjer. Jednadžba.

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

Newtonova metoda konvergira u 5 iteracija, modificirana Newtonova metoda u 19 iteracija, metoda polovična podjela za 22 ponavljanja. Konvergencija iteracijske metode ovisi o izboru parametra. Pri čemu se konvergencija postiže u 24 iteracije, konvergencija u 11 iteracija, konvergencija u 6 iteracija, konvergencija u 25 iteracija.

Metoda sekante

Metoda sekante dobiva se iz Newtonove metode zamjenom podijeljene razlike

izračunati poznatim aproksimacijama i.

Prema tome, dobiva se sljedeća formula metode sekante

. (1.18)

Ova metoda se sastoji od dva koraka (jer trebate znati prethodna dva koraka da biste izvršili novi korak). U tome se razlikuje od svih dosad danih metoda – jednostupanjska.

Za metodu sekante prvo se odabire početna aproksimacija. Nadalje, 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 dana na intervalu. Konstruirajmo particiju odsječka s točkom i djelomičnim odsječcima:

Duljina segmenata je.

Nazovimo integralni zbroj

Određeni integral funkcije na segmentu naziva se

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 pri rješavanju problema na računalu? Moguće je, ali ne uvijek (budući da antiderivat ne postoji uvijek).

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

To nam omogućuje da zaključimo da Newton-Leibnizova formula ne pruža opću, univerzalnu metodu za pronalaženje određenog integrala proizvoljne funkcije, te se ne preporučuje njezina uporaba u profesionalnim računalnim programima. Newton-Leibnizova formula se koristi samo za testiranje novorazvijenih programa u kojima su implementirane druge metode približne integracije funkcija.

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

Odgovarajuće formule nazivaju se numeričke integracijske formule ili kvadraturne formule 5 .

Korak dijeljenja u ovom slučaju izračunava se formulom.