Lipschitzov uvjet konvergencije nelinearne jednadžbe. Sustavi nelinearnih jednadžbi. Metoda jednostavne iteracije
Vježba:
1) Metodom iteracije riješiti sustav
2) Newtonovom metodom riješite sustav
nelinearne jednadžbe s točnošću od 0,001.
Zadatak №1 Metodom iteracije riješite sustav nelinearnih jednadžbi s točnošću 0,001.
Teorijski dio.
Metoda ponavljanja e zatim način numeričko rješenje matematički problemi. Njegova bit je pronaći algoritam pretraživanja za poznatu aproksimaciju (približnu vrijednost) željene vrijednosti sljedeće, točnije aproksimacije. Koristi se u slučaju kada niz aproksimacija prema navedenom algoritmu konvergira.
Ova metoda također se naziva metoda uzastopnih aproksimacija, metoda ponovljenih zamjena, metoda jednostavnih iteracija itd.
Newtonova metoda, Newtonov algoritam (također poznat kao tangentna metoda) 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.). Potraga za rješenjem provodi se konstruiranjem uzastopnih aproksimacija i temelji se na principima jednostavne iteracije. Metoda ima kvadratnu konvergenciju. Poboljšanje metode je metoda tetiva i tangenti. Također, Newtonova metoda može se koristiti za rješavanje optimizacijskih problema u kojima je potrebno odrediti nultu vrijednost prve derivacije ili gradijenta u slučaju višedimenzionalnog prostora. Obrazloženje
Da bi se jednadžba numerički riješila metodom jednostavne iteracije, mora se svesti na sljedeći oblik: , gdje je preslikavanje kontrakcije.
Za najbolju konvergenciju metode u točki sljedeće aproksimacije mora biti zadovoljen uvjet. Rješenje ove jednadžbe traži se u obliku , tada je:
Pod pretpostavkom da je točka pristupa "dovoljno blizu" korijenu, i to dana funkcija kontinuirana, konačna formula za je:
Imajući ovo na umu, funkcija je definirana izrazom:
Ova funkcija u blizini korijena izvodi kontrakcijsko preslikavanje, a algoritam za pronalaženje numeričkog rješenja jednadžbe svodi se na iterativni postupak izračuna:
.
Mogućnosti zadataka
№1. 1) 
2) 
№2. 1) 
2) 
№3. 1) 
2) 
№4. 1) 
2) 
№5. 1) 
2) 
№6. 1) 
2) 
№7. 1) 
2) 
№8. 1) 
2) 
№9. 1) 
2) 
№10.1) 
2) 
№11.1) 
2) 
№12.1) 
2) 
№13.1) 
2) 
№14.1) 
2) 
№15.1) 
2) 
№16.1) 
2) 
№17.1) 
2) 
№18.1) 
2) 
№19.1) 
2) 
№20.1) 
2) 
№21. 1) 
2) 
№22. 1) 
2) 
№23. 1) 
2) 
№24. 1) 
2) 
№25. 1) 
2) 
№26. 1) 
2) 
№27. 1) 
2) 
№28. 1) 
2) 
№29. 1) 
2) 
№30. 1) 
2) 
Primjer dovršetka zadatka
№1. 1) 
2) 
Primjer rješavanja sustava nelinearnih jednadžbi iteracijom
Prepišimo ovaj sustav kao:
Odvajanje korijena se vrši grafički (slika 1). Iz grafikona vidimo da sustav ima jedno rješenje zatvoreno u području D: 0<x<0,3;-2,2<g<-1,8.
Uvjerimo se da je iteracijska metoda primjenjiva za doradu rješenja sustava, za što je pišemo u sljedećem obliku:
Od imamo u regiji D
+ 
= ;
+ = 
Dakle, uvjeti konvergencije su zadovoljeni.
Tablica broj 2
| P |  |  |  |  |
||
| 0,15 | -2 | -0,45 | -0,4350 | -0,4161 | -0,1384 | |
| 0,1616 | -2,035 | -0,4384 | -0,4245 | -0,4477 | -0,1492 | |
| 0,1508 | -2.0245 | -0,4492 | -0,4342 | -0,4382 | -0,1461 | |
| 0.1539 | -2,0342. | -0,4461 | -0.4313 | -0,4470 | -0,1490 | |
| 0.1510 | -2,0313 | -0,4490 | -0,4341 | -0,4444 | -0.1481 | |
| 0,1519 | -2,0341 | -0,4481 | -0,4333 | -0,4469 | -0,1490 | |
| 0,1510 | -2.0333 | -0.449 | -0,4341 | -0.4462 | -0,1487 | |
| 0.1513 | -2.0341 | -0,4487 | -0,4340 | -0,4469 | -0.1490 | |
| 0.1510 | -2,0340 |
Uzimamo kao početne aproksimacije x o=0,15, y 0 =-2.
(tab. br. 2). Tada će odgovor biti:
Primjer rješavanja sustava nelinearnih jednadžbi Newtonovom metodom
Razdvajanje korijena vrši se grafički (slika 2). Za iscrtavanje grafova funkcija sastavit ćemo tablicu vrijednosti funkcija i , uključeni u prvu i drugu jednadžbu (Tablica I).
Vrijednosti za x mogu se uzeti na temelju sljedećih uvjeta: iz prve jednadžbe 1≤1,2x+0,4≤1, tj. 1,16≤h≤0,5; iz druge jednadžbe, tj. . Tako, .
Sustav ima dva rješenja. Pročistimo jednu od njih, koja pripada regiji D: 0,4<x<0,5;
0,76<g<0,73. За начальное приближение примем Имеем:
Tablica #3
| x | -1,1 | -1 | -0,8 | -0,6 | -0,2 | -0,4 | 0,2 | 0,4 | 0,5 | |
| x 2 | 1.21 | 0,64 | 0,36 | 0,04 | 0,16 | 0,04 | 0.16 | 0,25 | ||
| 0,8x 2 | 0,97 | 0,8 | 0,51 | 0,29 | 0,032 | 0,13 | 0,032 | 0,13 | 0,2 | |
| 1 -0,8x 2 | 0,03 | 0,2 | 0,49 | 0,71 | 0,97 | 0,87 | 0,97 | 0.87 | 0,8 | |
| 0,02 | 0,13 | 0,33 | 0,47 | 0,65 | 0,58 | 0,67 | 0,65 | 0,58 | 0.53 | |
| ±0,14 | ±0,36 | ±0,57 | ±0,69 | ±0,81 | ±0,76 | ±0,82 | ±0,81 | ±0,76 | ±0,73 | |
| 1,2x | -1,32 | -1,2 | -0,9b" | -0,72 | -0,24 | -0,48 | 0,24 | 0,48 | 0,6 | |
| 0,4+1,2x | -0,92 | -0,8 | -0,56 | -0,32 | 0,16 | -0,08 | 0,4 | 0,64 | 0.88 | |
| 2x-y | -1.17 | -0,93 | -0,59 | -0,33 | 0,16 | -0,08 | 0,41 | 0,69 | 2.06 1,08 | 1,57 |
| -1,03 | -1,07 | -1,01 | -0,87 | -0,56 | -0,72 | -0,41 | -0,29 | -1,26 -1,28 | -0.57 |
Pročišćavamo korijene Newtonovom metodom:
Gdje 
; 
;
; 
;
Svi izračuni su napravljeni prema tablici 3
| Tablica 3 | 0,10 | 0,017 | -0,0060 | 0,0247 | -0,0027 | -0,0256 | 0,0001 | 0,0004 | ||||||||
| 0,2701 | 0,0440 | -0,0193 | 0,0794 | -0,0080 | -0,0764 | -0,0003 | 0,0013 | |||||||||
| 2,6197 | 3,2199 | 2,9827 | 3,1673 | |||||||||||||
| -0,0208 | -2,25 | 0,1615 | -2,199 | 0,1251 | -2,1249 | 0,1452 | -2,2017 | |||||||||
| -1,1584 | 0,64 | -1,523 | 0,8 | -1,4502 | 0,7904 | -1,4904 | 0,7861 | |||||||||
| 0,1198 | -0,0282 | -0,0131 | 0,059 | -0,0007 | -0,0523 | -0,0002 | 0,0010 | |||||||||
| 0,9988 | 0,0208 | 0,9869 | -0,1615 | 0,9921 | -0,1251 | -0,9894 | -0,1452 | |||||||||
| 0,55 | 0,733 | 1,6963 | 1,7165 | |||||||||||||
| 0,128 | 0,8438 | 0,2 | 0,8059 | 0,1952 | 0,7525 | 0,1931 | 0,8079 | |||||||||
| 0,4 | 0,75 | 0,50 | -0,733 | 0,4940 | -0,7083 | 0,4913 | -0,7339 | 0,4912 | -0,7335 | Odgovor: x≈0,491 g≈ 0,734 | ||||||
| n | ||||||||||||||||
Kontrolna pitanja
1) Na grafu prikažite moguće slučajeve rješavanja sustava dviju nelinearnih jednadžbi.
2) Formulirajte postavku problema rješavanja sustava n-linearnih jednadžbi.
3) Navedite iterativne formule metode jednostavne iteracije u slučaju sustava dviju nelinearnih jednadžbi.
4) Formulirajte teorem o lokalnoj konvergenciji Newtonove metode.
5) Navedite poteškoće koje se javljaju pri korištenju Newtonove metode u praksi.
6) Objasnite kako se Newtonova metoda može modificirati.
7) Nacrtajte u obliku blok dijagrama algoritam za rješavanje sustava dviju nelinearnih jednadžbi jednostavnim iteracijskim i Newtonovim metodama.
Laboratorija #3
Dodjela usluge. Mrežni kalkulator dizajniran je za pronalaženje korijena jednadžbe metoda ponavljanja.Odluka se izrađuje u Word formatu.
Pravila unosa funkcija
Primjeri≡ x^2/(1+x)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)
Jedan od najučinkovitijih načina numeričkog rješavanja jednadžbi je metoda ponavljanja. Suština ove metode je sljedeća. Neka je dana jednadžba f(x)=0.
Zamijenimo je ekvivalentnom jednadžbom
Odaberemo početnu aproksimaciju korijena x 0 i zamijenimo je u desnu stranu jednadžbe (1). Onda dobijemo neki broj
x 1 \u003d φ (x 0). (2)
Zamjenjujući sada u desnu stranu (2) umjesto x 0 broj x 1 dobivamo broj x 2 \u003d φ (x 1). Ponavljajući ovaj proces, imat ćemo niz brojeva
x n =φ(x n-1) (n=1,2..). (3)
Ako je ovaj niz konvergentan, tj. postoji limes , tada prelazeći na limes u jednakosti (3) i pretpostavkom da je funkcija φ(x) kontinuirana, nalazimo
Ili ξ=φ(ξ).
Dakle, granica ξ je korijen jednadžbe (1) i može se izračunati iz formule (3) s bilo kojim stupnjem točnosti.
Riža. 1a sl. 1b
Riža. 2.
|φ′(x)|>1 - divergentni proces
Na slikama 1a, 1b, u blizini korijena |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, tada proces iteracije može biti divergentan (vidi sliku 2).
Dovoljni uvjeti za konvergenciju iteracijske metode
Teorem 7. Neka je funkcija φ(x) definirana i diferencijabilna na segmentu , a sve njezine vrijednosti φ(x)∈ i neka |φ′(x)|≤q<1 при x∈. Тогда процесс итерации x n = φ(x n -1) сходится независимо от начального значения x 0 ∈ и предельное значение является единственным корнем уравнения x= φ(x) на отрезке .Dokaz: Razmotrite dvije uzastopne aproksimacije x n = φ(x n -1) i x n +1 = φ(x n) i uzmite njihovu razliku x n+1 -x n =φ(x n)-φ(x n-1). Prema Lagrangeovom teoremu, desna strana se može prikazati kao
φ′(x n)(x n -x n-1)
Gdje je x n ∈
Onda dobivamo
|x n+1 -x n |≤φ′(x n)|x n -x n-1 |≤q|x n -x n-1 |
Uz pretpostavku n=1,2,...
|x 2 -x 1 |≤q|x 1 -x 0 |
|x 3 -x 2 |≤q|x 2 -x 1 |≤q²|x 1 -x 0 |
|x n+1 -x n ≤q n |x 1 -x 0 | (4)
Iz (4) zbog uvjeta q<1 видно, что последовательность {x n } сходится к некоторому числу ξ, то есть
, i zbog toga (zbog kontinuiteta funkcije φ(x)) ili ξ= φ(ξ) q.t.d.
Za pogrešku korijena ξ može se dobiti sljedeća formula.
Imamo x n =φ(x n-1).
Dalje ξ-x n =ξ-φ(x n-1) = φ(ξ)-φ(x n-1) →
Sada φ(x n-1)=φ(x n)-φ′(c)(x n -x n-1) →
φ(ξ)-φ(x n)+φ′(c)(x n -x n-1)
Kao rezultat toga, dobivamo
ξ-x n = φ′(c 1)(ξ-x n-1)+φ′(c)(x n -x n-1)
ili
|ξ-x n |≤q|ξ-x n |+q|x n -x n-1 |
Odavde
, (5)
odakle se vidi da je za q blizu 1 razlika |ξ -x n | može biti vrlo velik iako je |x n -x n -1 |<ε, где ε-заданная величина. Для того, чтобы вычислить ξ с точностью ε необходимо обеспечить
. (6)
Zatim zamjenom (6) u (5) dobivamo |ξ -x n |<ε.
Ako je q vrlo malen, tada se umjesto (6) može koristiti
|x n -x n -1 |<ε
Konvergencija iteracijske metode linearna s koeficijentom konvergencije α=q. Zaista, imamo
ξ-x n =φ(ξ)-φ n-1 = φ′(c) (ξ-x n-1), stoga je |ξ-x n |≤q·|ξ-x n-1 |.
Komentar. Neka u nekoj okolini korijena ξ∈(a,b) jednadžbe x= φ(x) derivacija φ’(x) zadrži konstantan predznak i nejednakost |φ’(x)|≤q<1. Тогда, если φ’(x) положительна, то последовательные приближения x n = φ(x n -1) сходятся к корню монотонно.
Ako je φ'(x) negativan, tada uzastopne aproksimacije osciliraju oko korijena.
Razmotrite način kako predstaviti jednadžbu f(x)=0 u obliku x= φ(x).
Funkcija φ(x) mora biti navedena tako da je |φ'(x)| bila mala u blizini korijena.
Neka su poznati m 1 i M 1 - najmanja i najveća vrijednost derivacije f’(x)
0
x = x - λf(x).
Neka je φ(x) = x- λf(x). Izaberimo parametar λ tako da u blizini korijena ξ vrijedi nejednakost
0≤|φ′(x)|=|1-λ f′(x)|≤q≤1
Dakle, na temelju (7), dobivamo
0≤|1-λM 1 |≤|1-λm 1 |≤q
Tada odabirom λ = 1/M 1 dobivamo
q = 1-m 1 /M 1< 1.
Ako je λ \u003d 1 / f '(x), tada iterativna formula x n \u003d φ (x n -1) ulazi u Newtonovu formulu
x n \u003d x n -1 - f (x n) / f '(x).
Metoda ponavljanja u Excelu
U ćeliju B2 upisujemo početak intervala a, u ćeliju B3 upisujemo kraj intervala b. Redak 4 dodijeljen je ispod naslova tablice. Proces iteracija organiziramo u ćelijama A5:D5.Proces pronalaženja nula funkcija iteracijom sastoji se od sljedećih koraka:
- Uzmite predložak pomoću ove usluge.
- Precizirajte intervale u ćelijama B2, B3.
- Kopirajte retke ponavljanja do tražene preciznosti (stupac D).
Primjer. Pronađite korijen jednadžbe e -x -x=0, x=∈, ε=0,001 (8)
Riješenje.
Jednadžbu (8) predstavljamo u obliku x=x-λ(e -x -x)
Odredi maksimalnu vrijednost derivacije funkcije f(x)= e - x -x.
max f′(x)=max(-(e -x +1)) ≈ -1,37. Značenje 
. Dakle, rješavamo sljedeću jednadžbu
x=x+0,73(e-x-x)
Vrijednosti uzastopnih aproksimacija dane su u tablici.
| n | x i | f(x i) |
| 1 | 0.0 | 1.0 |
| 2 | 0.73 | -0.2481 |
| 3 | 0.5489 | 0.0287 |
| 4 | 0.5698 | -0.0042 |
| 5 | 0.5668 | 0.0006 |
Sustav nelinearnih jednadžbi ima oblik:
Ovdje su nepoznate varijable, a sustav (7) nazivamo sustavom normalnog reda ako je barem jedna od funkcija nelinearna.
Rješavanje sustava nelinearnih jednadžbi jedan je od najtežih problema računalne matematike. Teškoća je utvrditi ima li sustav rješenja, i ako ima, koliko. Pročišćavanje rješenja u određenom području je jednostavniji zadatak.
Neka su funkcije definirane u područjima. Tada će regija biti regija u kojoj se može pronaći rješenje. Najčešće metode za pročišćavanje rješenja su metoda jednostavnih iteracija i Newtonova metoda.
Metoda jednostavnih iteracija za rješavanje sustava nelinearnih jednadžbi
Iz izvornog sustava (7) ekvivalentnim transformacijama prelazimo na sustav oblika:
Iterativni proces definiran formulama
možete početi davanjem početne aproksimacije. Dovoljan uvjet za konvergenciju iterativnog procesa je jedan od dva uvjeta:
Napišimo prvi uvjet:
Napišimo drugi uvjet:
Razmotrimo jedan od načina da se sustav (7) dovede do oblika (8) koji dopušta konvergentne iteracije.
Neka je dan sustav drugog reda oblika:
Potrebno ga je dovesti u obrazac:
Množimo prvu jednadžbu sustava s nepoznatom konstantom, drugu - s, zatim ih dodamo i dodamo na obje strane jednadžbe. Dobivamo prvu jednadžbu transformiranog sustava
Nepoznate konstante određujemo iz dovoljnih uvjeta konvergencije
Napišimo ove uvjete detaljnije:
Uz pretpostavku da su izrazi pod znakom modula jednaki nuli, dobivamo sustav od četiri jednadžbe s četiri nepoznanice za određivanje konstanti:
S takvim izborom parametara uvjeti konvergencije bit će ispunjeni ako se parcijalne derivacije funkcija i ne mijenjaju vrlo brzo u okolici točke.
Da biste riješili sustav, morate postaviti početnu aproksimaciju i izračunati vrijednosti izvedenica i, u ovom trenutku. Izračun se provodi u svakom koraku ponavljanja, dok,.
Metoda jednostavnih iteracija je samoispravljajuća, univerzalna i jednostavna za implementaciju na računalu. Ako sustav ima veliki red, tada se ne preporučuje korištenje ove metode, koja ima sporu stopu konvergencije. U ovom slučaju koristi se Newtonova metoda koja ima bržu konvergenciju.
Newtonova metoda za rješavanje sustava nelinearnih jednadžbi
Neka se traži rješavanje sustava nelinearnih jednadžbi oblika (7). Pretpostavimo da rješenje postoji u nekoj domeni u kojoj su sve funkcije kontinuirane i imaju barem prvu derivaciju. Newtonova metoda je iterativni proces, koji se provodi prema određenoj formuli sljedećeg oblika:
Poteškoće pri korištenju Newtonove metode:
postoji li inverzna matrica?
ide li van regije?
Newtonova modificirana metoda olakšava prvi zadatak. Modifikacija se sastoji u činjenici da se matrica ne izračunava u svakoj točki, već samo u početnoj. Dakle, modificirana Newtonova metoda ima sljedeću formulu:
Ali modificirana Newtonova metoda ne daje odgovor na drugo pitanje.
Iterativni proces prema formulama (8) ili (10) završava ako je zadovoljen sljedeći uvjet
Prednost Newtonove metode je njezina brza konvergencija u usporedbi s metodom jednostavnih iteracija.
Rješavanje nelinearnih jednadžbi
Neka je potrebno riješiti jednadžbu
Gdje 
je nelinearna kontinuirana funkcija.
Metode rješavanja jednadžbi dijele se na izravne i iterativne. Izravne metode su metode koje vam omogućuju izračunavanje rješenja pomoću formule (na primjer, pronalaženje korijena kvadratne jednadžbe). Iterativne metode su metode u kojima se specificira neka početna aproksimacija i konstruira se konvergentni niz aproksimacija za točno rješenje, pri čemu se svaka sljedeća aproksimacija izračunava korištenjem prethodnih.
Kompletno rješenje problema može se podijeliti u 3 faze:
Postavite broj, prirodu i položaj korijena jednadžbe (1).
Nađite približne vrijednosti korijena, tj. označiti praznine u kojima će se nalaziti korijenje (odvojiti korijenje).
Odredite vrijednost korijena s potrebnom točnošću (navedite korijene).
Za rješavanje prva dva problema postoje različite grafičke i analitičke metode.
Najilustrativnija metoda za odvajanje korijena jednadžbe (1) je određivanje koordinata presječnih točaka grafa funkcije 
s osi apscisa. Apscise 
točke presjeka grafa 
s osovinom 
su korijeni jednadžbe (1)
Intervali izolacije korijena jednadžbe (1) mogu se dobiti analitički, na temelju teorema o svojstvima funkcija koje su kontinuirane na segmentu.
Ako je npr. funkcija 
kontinuirano na segmentu 
I 
, zatim prema Bolzano-Cauchyjevom teoremu, na segmentu 
postoji barem jedan korijen jednadžbe (1) (neparan broj korijena).
Ako funkcija 
zadovoljava uvjete Bolzano-Cauchyjevog teorema i monoton je na ovom segmentu, zatim na 
postoji samo jedan korijen jednadžbe (1.) Dakle, jednadžba (1) ima on 
jedini korijen ako su ispunjeni uvjeti:
Ako je funkcija kontinuirano diferencijabilna na zadanom intervalu, tada možemo koristiti korolar Rolleovog teorema, prema kojem uvijek postoji barem jedna stacionarna točka između para korijena. Algoritam za rješavanje problema u ovom slučaju bit će sljedeći:
Koristan alat za odvajanje korijena također je korištenje Sturmovog teorema.
Rješavanje trećeg problema provodi se različitim iterativnim (numeričkim) metodama: metodom dihotomije, metodom jednostavne iteracije, Newtonovom metodom, metodom akorda itd.
Primjer Riješimo jednadžbu 
metoda jednostavna iteracija. Postavimo 
. Izgradimo graf funkcije.
Grafikon pokazuje da korijen naše jednadžbe pripada segmentu 
, tj. 
je izolacijski segment korijena naše jednadžbe. Provjerimo to analitički, tj. ispunjenje uvjeta (2):
Prisjetimo se da se izvorna jednadžba (1) u metodi jednostavne iteracije transformira u oblik 
a ponavljanja se provode prema formuli:
(3)
Izvođenje izračuna prema formuli (3) naziva se jedna iteracija. Iteracije se zaustavljaju kada se uvjet ispuni 
, Gdje 
je apsolutna pogreška u pronalaženju korijena, ili 
, Gdje 
- relativna greška.
Metoda jednostavne iteracije konvergira ako je uvjet 
Za 
. Odabir funkcije 
u formuli (3) za iteracije, može se utjecati na konvergenciju metode. U najjednostavnijem slučaju 
sa znakom plus ili minus.
U praksi se često izražava 
izravno iz jednadžbe (1). Ako uvjet konvergencije nije zadovoljen, pretvara se u oblik (3) i odabire. Predstavljamo našu jednadžbu u obliku 
(iz jednadžbe izražavamo x). Provjerimo uvjet konvergencije metode:
Za 
. Imajte na umu da uvjet konvergencije nije ispunjen 
, pa uzimamo segment izolacije korijena 
. Usput, napominjemo da kada predstavljamo našu jednadžbu u obliku 
, uvjet konvergencije metode nije ispunjen: 
na segmentu 
. Grafikon to pokazuje 
raste brže od funkcije 
(|tg| kut nagiba tangente na 
na segmentu 
)
Izaberimo 
. Iteracije organiziramo prema formuli:
Programski organiziramo proces ponavljanja sa zadanom točnošću:
> fv:=proc(f1,x0,eps)
> k:=0:
x:=x1+1:
dok abs(x1-x)> eps rade
x1:=f1(x):
ispis(evalf(x1,8)):
ispis(abs(x1-x)):
:printf("Broj ponavljanja=%d ",k):
kraj:
U iteraciji 19, dobili smo korijen naše jednadžbe 
s apsolutnom greškom 
Riješimo našu jednadžbu Newtonova metoda. Iteracije u Newtonovoj metodi provode se prema formuli:
Newtonova metoda se može smatrati metodom jednostavne iteracije s funkcijom, tada se uvjet konvergencije Newtonove metode može napisati kao:
.
U našoj oznaci 
a na intervalu je zadovoljen uvjet konvergencije 
što se može vidjeti na grafikonu:
Podsjetimo se da Newtonova metoda konvergira kvadratnom brzinom i početna aproksimacija mora biti odabrana dovoljno blizu korijenu. Napravimo izračune: 
, početna aproksimacija, . Iteracije organiziramo prema formuli:
Programski organiziramo proces ponavljanja sa zadanom točnošću. U 4 ponavljanja dobivamo korijen jednadžbe 
S 
Razmotrili smo metode za rješavanje nelinearnih jednadžbi na primjeru kubnih jednadžbi; naravno, ovim metodama se rješavaju različite vrste nelinearnih jednadžbi. Na primjer, rješavanje jednadžbe
Newtonova metoda sa 
, nalazimo korijen jednadžbe na [-1,5;-1]:
Vježbajte: Precizno riješite nelinearne jednadžbe 
0.
raspolavljanje segmenta (dihotomija)
jednostavna iteracija.
Newton (tangenta)
sekanta – akord.
Opcije zadatka izračunavaju se na sljedeći način: broj popisa podijeljen je s 5 ( 
), cijeli broj odgovara broju jednadžbe, ostatak odgovara broju metode.
MINISTARSTVO OBRAZOVANJA I ZNANOSTI UKRAJINE
DRŽAVNO SVEUČILIŠTE SUMY
Odjel za informatiku
NASTAVNI RAD
PO TEČAJU:
Numeričke metode
"Iterativne metode za rješavanje sustava nelinearnih jednadžbi"
1. Metode rješavanja sustava nelinearnih jednadžbi. opće informacije
2.1 Metoda jednostavnih iteracija
2.2 Aitkenova transformacija
2.3 Newtonova metoda
2.3.1 Modifikacije Newtonove metode
2.3.2 Kvazi-Newtonove metode
2.4 Ostale iterativne metode za rješavanje sustava nelinearnih jednadžbi
2.4.1 Picardova metoda
2.4.2 Metoda gradijentnog spuštanja
2.4.3 Metoda opuštanja
3. Implementacija iterativnih metoda programski i korištenjem matematičkog paketa Maple
3.1 Metoda jednostavne iteracije
3.2 Metoda gradijentnog spuštanja
3.3 Newtonova metoda
3.4 Modificirana Newtonova metoda
Popis korištene literature
1. Metode rješavanja nelinearnih jednadžbi. Opće informacije.
Neka nam je dan sustav jednadžbi, gdje je
- neki nelinearni operatori: (1.1)Također se može prikazati u obliku matrice:
(1.1)Njegovo rješenje naziva se takva vrijednost
, za kojiVrlo čest je računalni problem pronalaženja nekih ili svih rješenja sustava (1.1) iz n nelinearne algebarske ili transcendentalne jednadžbe sa n nepoznato.
Označimo sa x vektor stupca ( x 1 , X 2 ,..., x n)T i napišite sustav jednadžbi u obliku formule (1.2): F(x) = 0, gdje F=(f 1 , f 2 ,...,fn)T.
Takvi sustavi jednadžbi mogu nastati izravno, na primjer, pri projektiranju fizičkih sustava, ili neizravno. Tako npr. kod rješavanja problema minimiziranja određene funkcije G(x) često je potrebno odrediti one točke u kojima je gradijent ove funkcije jednak nuli. Pretpostavljajući F= dipl g, dobivamo nelinearni sustav.
Za razliku od sustava linearnih algebarskih jednadžbi, koji se mogu riješiti koristeći obje ravno(ili točan) i iterativni(ili približan) metodama, rješenje sustava nelinearnih jednadžbi može se dobiti samo aproksimativnim, iterativnim metodama. Oni omogućuju dobivanje niza aproksimacija
. Ako iterativni proces konvergira, tada je granična vrijednost rješenje zadanog sustava jednadžbi.Za potpuno razumijevanje metoda pronalaženja rješenja sustava potrebno je objasniti takav koncept kao što je "stopa konvergencije". Ako za slijed x n, konvergirajući do granice X *, formula je točna
(k je pozitivan realan broj), tada k naziva se brzina konvergencije zadanog niza.
2. Iterativne metode rješavanja sustava nelinearnih jednadžbi
2.1 Metoda jednostavnih iteracija
Metoda jednostavnih iteracija (uzastopnih aproksimacija) jedna je od glavnih u računalnoj matematici i koristi se za rješavanje široke klase jednadžbi. Opišimo i obrazložimo ovu metodu za sustave nelinearnih jednadžbi oblika
f i (x 1 ,x 2 ,...x n) = 0, ja=1,2,..n;
Sustav jednadžbi dovodimo u poseban oblik:
(2.1)Ili u vektorskom obliku
. (2.2)Štoviše, prijelaz na ovaj sustav trebao bi biti samo pod uvjetom da
je kontrakcijsko preslikavanje.Koristeći neku početnu aproksimaciju X(0) = (x 1 (0) ,x 2 (0) ,...x n (0))
konstruirati iterativni proces X (k+1) = (X (k)). Izračuni se nastavljaju dok se uvjet ne ispuni
. Tada je rješenje sustava jednadžbi fiksna točka preslikavanja .Opravdajmo metodu u određenoj normi
prostori.Predstavimo teorem o konvergenciji, čije ispunjenje uvjeta dovodi do pronalaska rješenja sustava.
Teorema (o konvergenciji). Neka
1). U domeni je definirana vektorska funkcija F(h).
; stanje3). poštena nejednakost
Zatim u iterativnom procesu:
, – rješenje sustava jednadžbi; ,Komentar. Nejednakost uvjeta 2) je Lipschitzov uvjet za vektorsku funkciju F(h) u domeni S s konstantom
(stanje kompresije). To pokazuje F je operator kontrakcije u domeni S, tj. jednadžba (2.2) podliježe principu kontrakcijskog preslikavanja. Izjave teorema znače da jednadžba (2.2) ima rješenje u području S, a uzastopne aproksimacije konvergiraju ovom rješenju brzinom geometrijskog niza s nazivnikom q.Dokaz. Jer
, tada za aproksimaciju, zbog pretpostavke 3), imamo . To znači da . Pokažimo da je , k=2,3,… i za susjedne aproksimacije nejednakost (2.3) ispunjenaArgumentirat ćemo indukcijom. Na
izjava je istinita, jer i . Pretpostavimo da aproksimacije pripadaju S i nejednakost (2.3) vrijedi za . Budući da , tada za uzimanje u obzir uvjeta 2) teorema imamo .Po induktivnoj hipotezi