Newtonova metoda (tangentna metoda)
Neka je korijen jednadžbe f(x)=0 odvojen na segmentu , s prvim i drugim izvodom f’(x) i f""(x) su kontinuirani i konstantnog predznaka za xÎ.
Neka se u nekom koraku preciziranja korijena dobije sljedeća aproksimacija korijenu x n (odabrana) . Zatim pretpostavimo da je sljedeća aproksimacija dobivena korištenjem korekcije h n , dovodi do tačne vrijednosti korijena
x = xn + hn. (1.2.3-6)
Brojanje h n male vrijednosti, predstavljamo f(h n + h n) u obliku Taylorovog reda, ograničavajući se na linearne članove
f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)
Uzimajući u obzir da je f(x) = f(x n + h n) = 0, dobijamo f(x n) + h n f ’(x n) » 0.
Dakle, h n » - f(x n)/ f’(x n). Zamenimo vrednost h n u (1.2.3-6) i umjesto tačne vrijednosti korijena x dobijamo još jednu aproksimaciju
Formula (1.2.3-8) nam omogućava da dobijemo niz aproksimacija x 1, x 2, x 3 ..., koji, pod određenim uslovima, konvergira na tačnu vrednost korena x, to je 
Geometrijska interpretacija Newtonove metode je kako slijedi
(Sl.1.2.3-6). Uzmimo desni kraj segmenta b kao početnu aproksimaciju x 0 i konstruirajmo tangentu u odgovarajućoj tački B 0 na grafu funkcije y = f(x). Tačka preseka tangente sa x-osom uzima se kao nova, preciznija aproksimacija x 1. Ponavljanje ove procedure mnogo puta nam omogućava da dobijemo 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 geometrijska konstrukcija. Dakle unutra pravougaonog trougla x 0 B 0 x 1 noga
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 jasno je da odabir 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. IN opšti slučaj izbor početne aproksimacije se vrši u skladu sa sledeće pravilo: početnu aproksimaciju treba uzeti kao tačku x 0 O, u kojoj se f(x 0)×f’’(x 0)>0, odnosno poklapaju se predznaci funkcije i njenog drugog izvoda.
Uslovi za konvergenciju Njutnove metode formulisani su u sledeć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 kada 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 -- najmanju vrijednost 
at 
at 
Proces proračuna se zaustavlja ako 
,
gdje je navedena tačnost.
Osim toga, sljedeći izrazi mogu poslužiti kao uvjet za postizanje zadane tačnosti prilikom pročišćavanja korijena pomoću Newtonove metode:
Dijagram algoritma Newtonove metode prikazan 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. Dijagram algoritma Newtonove metode
Primjer 1.2.3-3. Precizirajte korijene jednačine x-ln(x+2) = 0 koristeći Newtonov metod, pod uslovom da su korijeni ove jednačine odvojeni na segmentima x 1 O[-1.9;-1.1] i x 2 O [-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) = 1/(x+2) 2 > 0 za bilo koje x.
Dakle, uslovi konvergencije su zadovoljeni. Pošto je f""(x)>0 po cijeloj površini prihvatljive vrijednosti, zatim da se precizira korijen za početnu aproksimaciju x 1 izaberite x 0 = -1,9 (pošto 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 .
Za pojašnjenje korijena x 2 O[-0.9;2] biramo 0 =2 (f(2)×f”(2)>0) kao početnu aproksimaciju. 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 segment kroz tačke A i B. Sledeća aproksimacija x 1 je apscisa tačke preseka tetive sa 0x osom. Konstruirajmo jednačinu pravolinijskog segmenta:
Postavimo y=0 i pronađemo vrijednost x=x 1 (sljedeća aproksimacija):
Ponovimo proces izračunavanja da dobijemo sljedeću aproksimaciju korijenu - x 2 :
U našem slučaju (slika 1.2.11) 
i formula za izračunavanje za metodu 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 rekurentna formula metode akorda za ovaj slučaj ima oblik
Treba napomenuti da je fiksna tačka u metodi tetiva odabrana da bude 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 daju izračunavanje korijena jednadžbe f(x) = 0 pomoću formule tetive, bit će isti kao i za tangentnu metodu (Newtonova metoda), samo što se umjesto početne aproksimacije bira fiksna točka. Metoda akorda je modifikacija Newtonove metode. Razlika je u tome što je sljedeća aproksimacija u Newtonovoj metodi tačka presjeka tangente sa osom 0X, au metodi tetiva - tačka presjeka tetive sa osom 0X - aproksimacije konvergiraju korijenu s različitih strana .
Procjena greške za metodu akorda data je izrazom
(1.2.3-15)
Uslov za završetak procesa iteracije metodom akorda
(1.2.3-16)
U slučaju M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.
Primjer 1.2.3-4. Pojasniti korijen jednačine e x – 3x = 0, odvojen na segmentu sa tačnošću od 10 -4.
Provjerimo uvjet konvergencije:
Prema tome, a=0 treba izabrati kao fiksnu tačku, a x 0 =1 treba uzeti kao početnu aproksimaciju, pošto je f(0)=1>0 i f(0)*f"(0)>0.
Federalna agencija za obrazovanje
Sochi Državni univerzitet turizam i odmaralište
fakultet informacione tehnologije i matematičari
Katedra za opštu matematiku
Nastavni rad u disciplini
„Njutnova metoda i njene modifikacije za rešavanje sistema nelinearne jednačine»
Izvedeno:
Student 3. godine
grupe 06-INF
Lavrenko M.V.
Provjereno:
vanredni profesor, kandidat
pedagoške nauke
U vezi sa razvojem nove računarske tehnologije, inženjerska praksa se danas sve više susreće matematički problemi, čije je tačno rješenje vrlo teško ili nemoguće dobiti. U tim slučajevima obično se pribjegava jednom ili drugom približnom proračunu. Zbog toga aproksimativne i numeričke metode matematička analiza primljeno za poslednjih godinaširoko rasprostranjen razvoj i postali su izuzetno važni.
U ovom rad na kursu Razmatrana je poznata Newtonova metoda i njena modifikacija za rješavanje sistema nelinearnih jednačina. Rješavanje sistema nelinearnih jednačina jedan je od teških problema računske matematike. Teškoća je odrediti da li sistem ima rješenje, i, ako ima, koliko. Proučava se konvergencija osnovne i pojednostavljene Newtonove metode i metode dobivene Newtonovom metodom korištenjem iterativnog procesa za približnu inverziju Jacobijevih matrica.
Oni također ukratko opisuju: metode lažne pozicije, metodu sekante, Steffensenovu metodu, za koju se često ispostavi da je najbolji izbor za rješavanje sistema nelinearnih jednačina umjesto metode sekante ili metode lažnog položaja.
Njutnova poznata metoda je jedna od najpoznatijih efikasne metode rješavanje raznih nelinearnih problema. Formula proračuna metode može se dobiti različitim pristupima. Pogledajmo dva od njih.
1) Metoda tangente.
Izvedemo proračunsku formulu metode za rješavanje nelinearne jednačine
iz jednostavnih geometrijskih razmatranja. Neka je zadana početna aproksimacija korijenu. U tački s koordinatama povlačimo tangentu na graf funkcije i uzimamo apscisu točke presjeka ove tangente sa osom kao novu aproksimaciju. Slično, uzimamo apscisu tačke preseka sa osom tangente povučene na graf u tački sa koordinatama kao aproksimaciju. Nastavljajući ovaj proces dalje, dobijamo niz
blizu korena. Jednadžba tangente povučene na graf funkcije
u tački ima oblik: . (1.1)Uz pretpostavku jednakosti (1.1)
, primjećujemo da ako je ispunjen uslov apscise, tačka presjeka tangente sa osom zadovoljava jednakost: . (1.2)Izražavanje iz toga
, dobijamo formulu za proračun Newtonova metoda :
, . (1.3)
Zbog ove geometrijske interpretacije ova metoda se često naziva tangentna metoda .
Neka je potrebno riješiti sistem jednačina
(1) - dati, nelinearni (uključujući i linearne) funkcije realne vrijednosti P realne varijable
. Nakon što je odredio,
, ovaj sistem (2.1) se može zapisati jednom jednačinom
(2)u odnosu na vektorsku funkciju F vektorski argument x. Dakle, originalni problem se može smatrati problemom o nulama nelinearne karte
U ovoj formulaciji, to je direktna generalizacija glavnog problema iz prethodnog poglavlja - problema konstruisanja metoda za pronalaženje nula jednodimenzionalnih nelinearnih preslikavanja. Zapravo, ovo je isti problem, samo u prostorima veće dimenzije. Stoga je moguće ili rekonstruisati metode za njegovo rješavanje na osnovu gore razvijenih pristupa ili izvršiti formalni prijenos proračunskih formula izvedenih za skalarni slučaj. U svakom slučaju, treba voditi računa o valjanosti određenih operacija nad vektorskim varijablama i vektorskim funkcijama, kao i o konvergenciji iterativnih procesa dobijenih na ovaj način. Često su teoreme konvergencije za ove procese trivijalne generalizacije odgovarajućih rezultata dobijenih za metode za rješavanje skalarnih jednačina. Međutim, ne mogu se svi rezultati i sve metode prenijeti iz slučaja. P= 1 u slučaju P≥2. Na primjer, metode dihotomije ovdje više neće raditi, jer skup vektora nije uređen. Istovremeno, tranzicija iz n= 1 do n ≥ 2 unosi svoje specifičnosti u problem pronalaženja nula nelinearnog preslikavanja, uzimajući u obzir što dovodi do novih metoda i raznih modifikacija postojećih. Konkretno, velika varijabilnost metoda za rješavanje nelinearnih sistema povezana je s različitim načinima na koje se mogu riješiti linearni algebarski problemi koji nastaju tokom linearizacije korak po korak date nelinearne vektorske funkcije. F ( x ).2) Metoda linearizacije.
2. Newtonova metoda za rješavanje sistema nelinearnih jednačina.
Ova metoda ima mnogo bržu konvergenciju od jednostavne iteracijske metode. Newtonova metoda za sistem jednadžbi (1.1) zasniva se na korištenju proširenja funkcije
, Gdje 
(2.1)
u Tejlorovom nizu, sa terminima koji sadrže drugi ili više visoke narudžbe derivati se odbacuju. Ovaj pristup omogućava da se rješenje jednog nelinearnog sistema (1.1) zamijeni rješenjem većeg broja linearnih sistema.
Dakle, riješit ćemo sistem (1.1) Newtonovom metodom. U regiji D izaberite bilo koju tačku 
i nazvati je nultom aproksimacijom tačnog rješenja originalnog sistema. Proširimo sada funkcije (2.1) u Taylorov red u susjedstvu tačke . Imat će
Jer leve strane (2.2) moraju nestati prema (1.1), a zatim i desne strane (2.2) takođe moraju nestati. Dakle, iz (2.2) imamo
Sve parcijalne derivacije u (2.3) moraju se izračunati u tački .
(2.3) je sistem linearnih algebarske jednačine u odnosu na nepoznanice Ovaj sistem se može riješiti Cramerovom metodom ako je njegova glavna determinanta različita od nule i količine se mogu pronaći
Sada možemo precizirati nultu aproksimaciju konstruiranjem prve aproksimacije sa koordinatama
one. 
. (2.6)
Hajde da saznamo da li je aproksimacija (2.6) dobijena sa dovoljnim stepenom tačnosti. Da bismo to učinili, provjerimo stanje
, 
(2.7)
Gdje 
unaprijed određen mali pozitivan broj (tačnost s kojom se sistem (1.1) mora riješiti). Ako je uslov (2.7) zadovoljen, onda biramo (2.6) kao aproksimativno rješenje sistema (1.1) i završavamo proračune. Ako uslov (2.7) nije zadovoljen, tada izvodimo sljedeću radnju. U sistemu (2.3), umjesto 
uzmimo ažurirane vrijednosti
, (2.8)
one. hajde da uradimo sledeće
. (2.9)
Nakon toga, sistem (2.3) će biti sistem linearnih algebarskih jednadžbi za veličine. Odredivši ove veličine, sljedeća druga aproksimacija 
do rješenja sistema (1.1) nalazimo pomoću formula
Sada provjerimo uslov (2.7) 
Ako je ovaj uslov ispunjen, onda završavamo proračune uzimajući drugu aproksimaciju kao približno rješenje sistema (1.1) 
. Ako ovaj uslov nije ispunjen, nastavljamo s konstruiranjem sljedeće aproksimacije, uzimajući u obzir (2.3) 
Potrebno je graditi aproksimacije sve dok uslov nije zadovoljen.
Radne formule Njutnove metode za rešavanje sistema (1.1) mogu se zapisati u obliku.
Izračunaj sekvencu
Evo 
su rješenje za sistem
Formulirajmo algoritam proračuna koristeći formule (2.11)-(2.13).
1. Odaberimo nultu aproksimaciju koja pripada području D.
2. U sistemu linearnih algebarskih jednačina (2.13) postavljamo 
,A .
3. Riješimo sistem (2.13) i pronađemo količine 
.
4. U formule (2.12) stavljamo 
i izračunajte komponente sljedeće aproksimacije.
5. Provjerimo uslov (2.7) za: (Pogledajte algoritam za izračunavanje maksimuma od nekoliko veličina.)
6. Ako je ovaj uslov ispunjen, onda završavamo proračune odabirom aproksimacije kao približnog rješenja sistema (1.1). Ako ovaj uvjet nije ispunjen, prijeđite na korak 7.
7. Stavimo 
za sve .
8. Izvršimo korak 3, stavljanje 
.
Geometrijski, ovaj algoritam se može napisati kao:
Algoritam. Izračunavanje maksimuma od nekoliko veličina.
Primjer. Razmotrimo korištenje Newtonove metode za rješavanje sistema od dvije jednačine.
Koristeći Newtonov metod, riješite sljedeći sistem nelinearnih jednačina do određene preciznosti
, (2.14)
Evo 
. Odaberimo nultu aproksimaciju 
, koji pripada domenu D. Konstruirajmo sistem linearnih algebarskih jednadžbi (2.3). Ona će izgledati
(2.15)
Označimo
Rešimo sistem (2.15) u odnosu na nepoznanice 
, na primjer Cramer metoda. Zapisujemo Cramerove formule u obliku
(2.17)
gdje je glavna determinanta sistema (2.15)
(2.18)
a pomoćne determinante sistema (2.15) imaju oblik
.
Pronađene vrijednosti zamjenjujemo u (2.16) i nalazimo komponente prve aproksimacije 
na rješenje sistema (2.15).
Hajde da proverimo stanje
, (2.19)
ako je ovaj uslov ispunjen, onda završavamo proračune uzimajući prvu aproksimaciju kao približno rješenje sistema (2.15), tj. 
. Ako uslov (2.19) nije zadovoljen, postavljamo 
, 
a mi ćemo izgraditi novi sistem linearne algebarske jednadžbe (2.15). Nakon što smo ga riješili, nalazimo drugu aproksimaciju 
. Hajde da to proverimo. Ako je ovaj uslov zadovoljen, tada biramo kao približno rješenje sistema (2.15) 
. Ako uslov na nije zadovoljen, postavljamo 
, 
i konstruišite sledeći sistem (2.15) da biste pronašli 
itd.
Zadaci
Svi zadaci zahtijevaju:
Napraviti program za numeričku implementaciju metode prema predloženom algoritmu.
Dobijte rezultate proračuna.
Provjerite svoje rezultate.
Dat je sistem dvije nelinearne jednačine.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10.
11. 
12. 
13. 
14. 
15. 
.
Poglavlje 3. Numeričke metode za rješavanje sistema linearnih algebarskih jednačina (SLAE).
Cilj rada. Upoznavanje sa nekim aproksimativnim metodama za rešavanje SLAE-a i njihovom numeričkom implementacijom na računaru.
Preliminarne napomene. Sve metode za rješavanje SLAE obično se dijele na dvije velike grupe. Prva grupa uključuje metode koje se obično nazivaju tačnima. Ove metode nam omogućavaju da pronađemo za bilo koji sistem tačne vrijednosti nepoznanice nakon konačnog broja aritmetičkih operacija, od kojih se svaka izvodi tačno.
U drugu grupu spadaju sve metode koje nisu tačne. Zovu se iterativni, numerički ili približni. Tačno rješenje, kada se koriste takve metode, dobija se kao rezultat beskonačnog procesa aproksimacija. Atraktivna karakteristika takvih metoda je njihova samoispravka i lakoća implementacije na PC-u.
Razmotrimo neke približne metode za rješavanje SLAE i konstruiramo algoritme za njihovu numeričku implementaciju. Dobićemo približno rješenje SLAE s tačnošću , gdje je neki vrlo mali pozitivan broj.
1. Metoda iteracije.
Neka je SLAE dat u obliku
(1.1)
Ovaj sistem se može zapisati u matričnom obliku
, (1.2)
Gdje 
- matrica koeficijenata za nepoznate u sistemu (1.1), 
- kolona slobodnih članova, 
- kolona nepoznanica sistema (1.1).
. (1.3)
Rešimo sistem (1.1) metodom iteracije. Da bismo to učinili, izvršit ćemo sljedeće korake.
Prvo. Odaberimo nultu aproksimaciju
(1.4)
na tačno rješenje (1.3) sistema (1.1). Komponente nulte aproksimacije mogu biti bilo koji brojevi. Ali zgodnije je uzeti bilo koju nulu za komponente nulte aproksimacije 
, ili slobodni uslovi sistema (1.1) 
Drugo. Komponente nulte aproksimacije zamjenjujemo u desna strana sistema (1.1) i izračunaj
(1.5)
Količine lijevo u (1.5) su komponente prve aproksimacije 
Radnje koje su rezultirale prvom aproksimacijom nazivaju se iteracija.
Treće. Provjerimo nultu i prvu aproksimaciju za
(1.6)
Ako su svi uslovi (1.6) ispunjeni, tada za približno rješenje sistema (1.1) biramo ili , ili nije bitno, jer razlikuju se jedno od drugog samo za i završimo proračune. Ako barem jedan od uslova (1.6) nije ispunjen, prelazimo na sljedeću radnju.
Četvrto. Izvršimo sljedeću iteraciju, tj. u desnu stranu sistema (1.1) zamjenjujemo komponente prve aproksimacije i izračunavamo komponente druge aproksimacije 
, Gdje
Peto. Hajde da proverimo 
i na , tj. Provjerimo uslov (1.6) za ove aproksimacije. Ako su svi uslovi (1.6) ispunjeni, tada ćemo za približno rješenje sistema (1.1) izabrati ili , ili nije bitno, jer razlikuju se jedni od drugih za ne više od . U suprotnom ćemo konstruisati sljedeću iteraciju zamjenom komponenti druge aproksimacije u desnu stranu sistema (1.1).
Iteracije se moraju izgraditi do dvije susjedne aproksimacije 
i međusobno će se razlikovati za ne više od .
Radna formula metoda iteracije za rješavanje sistema (1.1) može se zapisati u obliku
Algoritam za numeričku implementaciju formule (1.7) može biti sljedeći.
Dovoljni uslovi za konvergenciju metode iteracije za sistem (1.1) imaju oblik
1. 
, .
2. 
, 
.
3. 
2. Jednostavna metoda iteracije.
Neka je sistem linearnih algebarskih jednadžbi (SLAE) dat u obliku
(2.1)
Da bi se sistem (2.1) riješio jednostavnim iteracijskim metodom, prvo se mora svesti na oblik
(2.2)
U sistemu (2.2) 
-ta jednačina je -ta jednačina sistema (2.1), riješena u odnosu na -tu nepoznatu ( 
).
Metoda za rješavanje sistema (2.1), koja se sastoji od njegovog svođenja na sistem (2.2) nakon čega slijedi rješavanje sistema (2.2) korištenjem iteracijske metode, naziva se jednostavna metoda iteracije za sistem (2.1).
Tako će radne formule jednostavne iteracijske metode za rješavanje sistema (2.1) imati oblik
(2.3)
Formule (2.3) se mogu napisati u obliku
Algoritam za numeričku implementaciju jednostavne iteracijske metode za sistem (2.1) prema formulama (2.4) može biti sljedeći.
Ovaj algoritam se može napisati geometrijski.
Dovoljni uslovi za konvergenciju jednostavne iteracijske metode za sistem (2.1) imaju oblik
1. 
, .
2. 
, 
.
3. 
3. Stacionarna Seidelova metoda.
Seidelova metoda za rješavanje SLAE razlikuje se od metode iteracije po tome što nakon što smo pronašli neku aproksimaciju za -tu komponentu, odmah je koristimo da pronađemo sljedeću 
, 
, …, 
-th komponenta. Ovaj pristup omogućava veću stopu konvergencije Seidelove metode u poređenju sa metodom iteracije.
Neka je SLAE dat u obliku
(3.1)
Neka 
- nulta aproksimacija do tačnog rješenja 
sistemi (3.1). I neka se nađe 
th aproksimacija 
. Hajde da definišemo komponente 
th aproksimacija pomoću formula
(3.2)
Formule (3.2) se mogu napisati u kompaktnom obliku
, 
, 
(3.3)
Algoritam za numeričku implementaciju Seidelove metode za rješavanje sistema (3.1) korištenjem formula (3.3) može biti sljedeći.
1. Odaberimo npr. 
, 
2. Stavimo .
3. Izračunajmo za sve.
4. Provjerićemo uslove za sve 
.
5. Ako su ispunjeni svi uslovi iz stava 4, onda ćemo izabrati jedno ili kao približno rješenje sistema (3.1) i završiti proračune. Ako barem jedan uvjet u koraku 4 nije ispunjen, prijeđite na korak 6.
6. Spustimo ga i pređimo na korak 3.
Ovaj algoritam se može napisati geometrijski.
Dovoljan uslov za konvergenciju Seidelove metode za sistem (3.1) ima oblik 
, .
4. Nestacionarna Seidelova metoda.
Ova metoda rješavanja SLAE (3.1) omogućava još veću brzinu konvergencije Seidelove metode.
Hajde da nekako pronađemo komponente th aproksimacije i th aproksimacije za sistem (3.1).
Izračunajmo vektor korekcije
Izračunajmo vrijednosti
, (4.2)
Složimo količine 
, u opadajućem redoslijedu.
Istim redosledom prepisujemo jednačine u sistemu (3.1) i nepoznanice u ovom sistemu: Linearnoalgebra I nelinearni ... MenadžmentZa laboratorija radiBy ... metodološki instrukcije ZapraktičnoradiBy Zastudenti ...
Obrazovna literatura (prirodna i tehnička) 2000-2011 OP ciklus – 10 godina CD ciklus – 5 godina
Književnost... Prirodnonauke općenito 1. Astronomija [Tekst]: priručnik Za ... Numeričkimetode: Linearnoalgebra I nelinearni ... MenadžmentZa laboratorija radiBy ... metodološki instrukcije ZapraktičnoradiBy disciplina "Ekonomika transporta" Zastudenti ...
- prirodne nauke (1)
Tutorial... menadžmentZastudenti i nastavnici, namijenjeni Za koristiti ne samo za učenje metoderad... proizvodnja praktično vještine korištenja stvarnih podataka. Metodički preporuke By ispunjenje testa radBy ovo...
- prirodne nauke - fizičke i matematičke nauke - hemijske nauke - nauke o zemlji (geodetske geofizičke geološke i geografske nauke)
Dokument... Zastudentiprirodno- ... radiBy disciplina "Genetika i selekcija", posvećena trenutni problemi ovo nauke. Sistematizovana samostalna PosaostudentiBy teorijski i praktično ... linearno, nelinearni, dinamičan. Sve metode ...
- prirodne nauke - fizičke i matematičke nauke - hemijske nauke - nauke o zemlji (geodetske geofizičke geološke i geografske nauke) (7)
Spisak udžbenikaEreminova determinanta linearno I nelinearnialgebra : linearno I nelinearni programiranje: novo metoda/ Eremin, Mihail... Zastudenti i nastavnici geoloških specijalnosti na univerzitetima. kh-1 1794549 99. D3 P 693 PraktičnomenadžmentBy ...
Na primjer:
Postavimo zadatak da pronađemo validan korijene ove jednačine.
I definitivno ih ima! - iz članaka o grafovi funkcija I jednačine više matematike dobro znaš kakav je raspored polinomska funkcija neparan stepen siječe osu barem jednom, stoga naša jednačina ima najmanje jedan pravi koren. Jedan. Ili dva. Ili tri.
Prvo, treba provjeriti dostupnost racionalno korijenje. Prema odgovarajuća teorema, samo brojevi 1, –1, 3, –3 mogu dobiti ovu “titulu”, a direktnom zamjenom lako je osigurati da nijedan od njih “ne odgovara”. Dakle, iracionalne vrijednosti ostaju. Iracionalni korijen(korijeni) polinoma stepena 3 mogu se naći upravo (izraziti kroz radikale) koristeći tzv Cardano formule , međutim, ova metoda je prilično glomazna. I za polinome 5. i višim stepenima uopšte ne postoji opšta analitička metoda, a osim toga, u praksi postoje mnoge druge jednačine u kojima tačne vrijednosti nemoguće je dobiti prave korijene (iako postoje).
Međutim, u primijenjenom (na primjer, inženjering) problema, više je nego prihvatljivo koristiti izračunate približne vrijednosti sa određenom tačnošću.
Postavimo tačnost za naš primjer. Šta to znači? To znači da moramo pronaći TAKVU približnu vrijednost korijena (korijeni) u kojoj smo Garantovano je da grešimo za najviše 0,001 (hiljaditi dio) .
Apsolutno je jasno da se rješenje ne može pokrenuti “nasumično” i stoga u prvom koraku korijeni odvojeno. Odvojiti korijen znači pronaći dovoljno mali (obično jedan) segment kojem ovaj korijen pripada i na kojem nema drugih korijena. Najjednostavniji i najpristupačniji grafička metoda razdvajanja korijena. Hajde da gradimo tačku po tačku graf funkcije 
:
Iz crteža slijedi da jednačina, po svemu sudeći, ima jedan realni korijen koji pripada segmentu. Na krajevima ovog intervala funkcija 
uzima vrijednosti različitih predznaka: , i iz činjenice kontinuitet funkcije na segmentu elementarni način da se razjasni korijen je odmah vidljiv: podijelite interval na pola i odaberite segment na čijim krajevima zauzima funkcija različiti znakovi. U ovom slučaju, očigledno se radi o segmentu. Dobiveni interval podijelimo na pola i ponovo izaberemo segment "drugačiji znak". I tako dalje. Takve sekvencijalne radnje se nazivaju iteracije. U ovom slučaju, treba ih izvoditi sve dok dužina segmenta ne postane manja od dvostruke točnosti proračuna, a sredinu posljednjeg segmenta „različitih znakova“ treba odabrati kao približnu vrijednost korijena.
Razmatrana šema dobila je prirodno ime - metoda poludijeljenja. A nedostatak ove metode je brzina. Polako. Tako sporo. Biće previše iteracija pre nego što postignemo potrebnu tačnost. Sa razvojem kompjuterske tehnologije to, naravno, nije problem, ali matematika je ono čemu matematika služi, da traži najracionalnija rješenja.
I jedan od više efikasne načine pronalaženje približne vrijednosti korijena je precizno tangentna metoda. Brief geometrijska suština metoda je sljedeća: prvo, korištenjem posebnog kriterija (više o tome malo kasnije) odabran je jedan od krajeva segmenta. Ovaj kraj se zove početni aproksimacija korijena, u našem primjeru: . Sada crtamo tangentu na graf funkcije 
na apscisi (plava tačka i ljubičasta tangenta):
Ova tangenta je prešla x-osu u žutoj tački, i imajte na umu da smo u prvom koraku skoro “pogodili korijen”! Biti će prvo root pristup. Zatim spuštamo žutu okomicu na graf funkcije i "dolazimo" do narančaste točke. Ponovo povlačimo tangentu kroz narandžastu tačku, koja će presjeći osu još bliže korijenu! I tako dalje. Nije teško shvatiti da se metodom tangente približavamo cilju skokovima i granicama, a za postizanje tačnosti potrebno je doslovno nekoliko iteracija.
Pošto je tangenta definisana kroz derivacija funkcije, onda je ova lekcija završila u odjeljku „Derivati“ kao jedna od njegovih primjena. I ne ulazeći u detalje teorijsko opravdanje metode, razmotrit ću tehničku stranu pitanja. U praksi se gore opisani problem javlja otprilike u sljedećoj formulaciji:
Primjer 1
Korišćenjem grafička metoda pronaći interval na kojem se nalazi pravi korijen jednadžbe. Koristeći Newtonovu metodu, dobijte približnu vrijednost korijena s točnošću od 0,001
Evo "poštedne verzije" zadatka, u kojoj se odmah navodi prisustvo jednog važećeg korijena.
Rješenje: na prvom koraku korijen treba grafički odvojiti. Ovo se može uraditi iscrtavanjem 
(pogledajte ilustracije iznad), ali ovaj pristup ima niz nedostataka. Prvo, nije činjenica da je graf jednostavan (ne znamo unaprijed), A softver– nije uvek pri ruci. I drugo (posledica od 1.), sa velikom vjerovatnoćom rezultat neće biti čak ni šematski crtež, već grubi crtež, što, naravno, nije dobro.
Pa, zašto su nam potrebne nepotrebne poteškoće? Hajde da zamislimo jednačina u obliku, PAŽLJIVO konstruišite grafikone i označite koren na crtežu („X“ koordinata tačke preseka grafika):
Ocigledna prednost ovu metodu je da se grafovi ovih funkcija grade ručno mnogo preciznije i mnogo brže. Usput, zapazite to ravno prešao kubna parabola u jednoj tački, što znači da predložena jednačina zapravo ima samo jedan pravi korijen. Vjerujte, ali provjerite ;-)
Dakle, naš „klijent“ pripada segmentu i „na oko“ je otprilike jednako 0,65-0,7.
Na drugom koraku treba izabrati početna aproksimacija root Obično je ovo jedan od krajeva segmenta. Početna aproksimacija mora zadovoljiti sljedeći uvjet: 
Hajde da nađemo prvo I sekunda izvedene funkcije 
:
i provjerite lijevi kraj segmenta: 
Dakle, nula „nije odgovarala“.
Provjera desnog kraja segmenta:
- Sve je uredu! Mi biramo kao početnu aproksimaciju.
Na trećem korakuČeka nas put do korena. Svaka sljedeća korijenska aproksimacija izračunava se iz prethodnih podataka koristeći sljedeće ponavljajuća formule: 
Proces se završava kada se ispuni uslov, gdje je unaprijed određena tačnost proračuna. Kao rezultat, "n-ta" aproksimacija se uzima kao približna vrijednost korijena: .
Slijede rutinski proračuni: 
(zaokruživanje se obično vrši na 5-6 decimala)
Budući da je dobivena vrijednost veća od , prelazimo na 1. aproksimaciju korijena: 
Računamo: 
, pa je potrebno prijeći na 2. aproksimaciju:
Idemo dalje u sljedeću rundu: 
, time su iteracije završene, a 2. aproksimaciju treba uzeti kao približnu vrijednost korijena, koju u skladu sa zadatom preciznošću treba zaokružiti na hiljaditi dio:
U praksi je zgodno uneti rezultate proračuna u tabelu; kako bi se unos donekle skratio, razlomak se često označava sa: 
Ako je moguće, bolje je izvršiti same izračune u Excelu - mnogo je praktičnije i brže:
Odgovori: tačno do 0,001
Da vas podsjetim da ova fraza implicira činjenicu da smo pogriješili u procjeni pravo značenje korijen za ne više od 0,001. Oni koji sumnjaju mogu uzeti mikrokalkulator i još jednom zamijeniti približnu vrijednost od 0,674 na lijevoj strani jednačine.
Sada hajde da "skeniramo" desnu kolonu tabele od vrha do dna i primetimo da vrednosti konstantno opadaju u apsolutnoj vrednosti. Ovaj efekat se zove konvergencija metoda koja nam omogućava da izračunamo korijen sa proizvoljno visokom preciznošću. Ali ne dolazi uvijek do konvergencije - ona je osigurana niz uslova, o čemu sam ćutao. Posebno, segment na kojem je korijen izoliran mora biti dovoljno mali– inače će se vrijednosti nasumično mijenjati i nećemo moći dovršiti algoritam.
Šta učiniti u takvim slučajevima? Provjerite da li su ispunjeni navedeni uvjeti (vidi link iznad), i, ako je potrebno, smanjite segment. Dakle, relativno govoreći, ako u analiziranom primjeru interval nije odgovarao za nas, onda bismo trebali razmotriti, na primjer, segment. U praksi sam se susreo sa takvim slučajevima, a ova tehnika zaista pomaže! Isto se mora učiniti ako oba kraja “širokog” segmenta ne zadovoljavaju uvjet 
(tj. nijedan od njih nije prikladan kao početna aproksimacija).
Ali obično sve radi kao sat, iako ne bez zamki:
Primjer 2
Odredite grafički broj realnih korijena jednadžbe, odvojite ove korijene i pomoću Newtonove metode pronađite približne vrijednosti korijena s točnošću
Uvjet problema je postao primjetno stroži: prvo, sadrži jak nagovještaj da jednačina nema ni jedan korijen, drugo, povećan je zahtjev za preciznošću, i treće, sa grafikom funkcije 
mnogo teže izaći na kraj.
I zbog toga rješenje Počnimo s trikom za uštedu: zamislite jednadžbu u obliku i nacrtajte grafikone: 
Iz crteža slijedi da naša jednadžba ima dva realna korijena:
Algoritam, kao što razumete, treba dvaput da se „pokrene“. Ali to je čak iu najtežim slučajevima; ponekad morate pregledati 3-4 korijena.
1) Korištenje kriterija 
Hajde da saznamo koji kraj segmenta izabrati kao početnu aproksimaciju prvog korena. Pronalaženje izvoda funkcija 
:
Testiranje lijevog kraja segmenta:
- došao gore!
Dakle, to je početna aproksimacija.
Pročistit ćemo korijen koristeći Newtonovu metodu koristeći rekurentnu formulu: 
- do razlomka modulo neće biti manja od tražene tačnosti: 
I ovdje riječ "modul" dobija neiluzornu važnost, jer su vrijednosti negativne: 
Iz istog razloga, posebnu pažnju treba obratiti pri prelasku na svaku sljedeću aproksimaciju:
Unatoč prilično visokim zahtjevima za preciznošću, proces je opet završio na 2. aproksimaciji: , dakle:
Precizno do 0,0001
2) Nađimo približnu vrijednost korijena.
Provjeravamo lijevi kraj segmenta za vaške: 
, stoga nije pogodan kao početna aproksimacija.
Problem nalaženja rješenja za sistem od n nelinearnih algebarskih ili transcendentalnih jednadžbi sa n nepoznatih oblika
f 1(x 1, x 2, … x n) = 0, | ||
f 2(x 1, x 2, … x n) = 0, | ||
…………………… |
||
f n (x 1 ,x 2 ,… x n ) = 0, |
široko razmatrana u računarskoj praksi. Slični sistemi jednačina mogu nastati, na primjer, tokom numeričkog modeliranja nelinearnih fizičkih sistema u fazi traženja njihovih stacionarnih stanja. U velikom broju slučajeva sistemi oblika (6.1) se dobijaju indirektno, u procesu rešavanja nekog drugog računarskog problema. Na primjer, kada pokušavate minimizirati funkciju nekoliko varijabli, možete tražiti one točke u višedimenzionalnom prostoru gdje je gradijent funkcije nula. U ovom slučaju potrebno je riješiti sistem jednačina (6.1) sa lijevom stranom - projekcijama gradijenta na koordinatne ose.
U vektorskoj notaciji, sistem (6.1) se može zapisati u kompaktnijem obliku
vektorski stupac funkcija, simbol () T označava operaciju transponiranja
Pronalaženje rješenja za sistem nelinearnih jednačina je mnogo složeniji zadatak od rješavanja jedne nelinearne jednačine. Ipak, brojne iterativne metode za rješavanje nelinearnih jednačina mogu se proširiti na sisteme nelinearnih jednačina.
Jednostavna metoda iteracije
Jednostavna metoda iteracije za sisteme nelinearnih jednačina je u suštini generalizacija istoimene metode za jednu jednačinu. Zasnovan je na činjenici da se sistem jednačina (6.1) svodi na oblik
x 1= g 1(x 1, x 2, … , x n) , x 2= g 2(x 1, x 2, … , x n) ,
……………………
x n= g n(x 1 , x 2 , … , x n) ,
a iteracije se izvode prema formulama
x 1 (k + 1 )= g 1 (x 1 (k ), x 2 (k ), ... , x n (k )), x 2 (k + 1 )= g 2 (x 1 (k ), x 2 (k ), … , x n (k )) ,
……………………………
x n (k + 1)= g n (x 1 (k), x 2 (k), ..., x n (k)).
Ovdje gornji indeks označava aproksimacijski broj. Iterativni proces (6.3) počinje nekom početnom aproksimacijom
(x 1 (0) ,x 2 (0) ,… ,x n (0) ) i nastavite dok se moduli ne povećaju
svi argumenti nakon jedne k-iteracije neće postati manji od date vrijednosti ε : x i (k + 1 ) − x i (k )< ε дляi = 1,2,… ,n .
Iako jednostavna metoda iteracije vodi direktno do rješenja i lako se programira, ona ima dva značajna nedostatka. Jedna od njih je spora konvergencija. Drugi je da ako je početna aproksimacija odabrana daleko od pravog rješenja (X 1,X 2,…,X n), tada će konvergencija
metoda nije zagarantovana. Jasno je da problem izbora početne aproksimacije, koji nije jednostavan ni za jednu jednačinu, postaje veoma složen za nelinearne sisteme.
Riješite sistem nelinearnih jednačina:
(x... | ) =0 | |||
F n (x 1 ... | x n) = 0 . | |||
Ne postoje direktne metode za rješavanje nelinearnih sistema opšti pogled. Samo u nekim slučajevima sistem (4.1) se može riješiti direktno. Na primjer, u slučaju dvije jednačine, ponekad je moguće izraziti jednu nepoznatu u terminima druge i tako svesti problem na rješavanje jedne nelinearne jednačine u odnosu na jednu nepoznatu.
Iterativne metode se obično koriste za rješavanje sistema nelinearnih jednačina.
Newtonova metoda
U slučaju jedne jednačine F(x) = 0, algoritam Njutnove metode je lako dobijen upisivanjem tangentnih jednačina na krivu y = F(x). Newtonova metoda za sisteme jednačina zasniva se na korištenju ekspanzije funkcija F 1 (x 1 ...x n) u Taylorov red, te pojmova koji sadrže
postojeći derivati drugog (i višeg reda) se odbacuju. Neka su približne vrijednosti nepoznanica sistema (4.1) jednake
odgovoran a 1 ,a 2 ,....,a n . Zadatak je pronaći inkremente (po
uređivanja) na ove vrijednosti | x 1 ,x 2 ,..., | x n , zahvaljujući čemu je rješenje sistema |
|
teme će biti napisane kao: | |||
x 1= a 1+ x 1, | x 2= a 2+ | x 2, .... ,x n = a n + x n. | |
Proširimo lijeve strane jednadžbe (4.1) uzimajući u obzir proširenje Taylorovog reda, ograničavajući se samo na linearne članove relativne
tačno povećava: | ||||||
F1 (x1 ... xn ) ≈ F1 (a1 ... an ) + | ∂ F 1 | x 1+ | + ∂ F 1 | xn, |
||
∂x | ∂x | |||||
F2 (x1 ... xn ) ≈ F2 (a1 ... an ) + | ∂ F 2 | x 1+ | ∂ F 2 | xn, |
||
∂x | ∂x | |||||
................................... | ||||||
F n(x 1 ... x n) ≈ F n(a 1 ... a n) + | ∂Fn | x 1+ | ∂Fn | xn |
||
∂x | ∂x | |||||
Zamjenom u sistem (4.1) dobijamo sljedeći sistem linearnih algebarskih jednačina za inkremente:
∂ F 1 | ∂ F 1 | + ∂ F 1 | = −F , |
||||||
∂x | ∂x | ∂x | |||||||
∂ F 2 | ∂ F 2 | ∂ F 2 | = −F , |
||||||
∂x | ∂x | ∂x | |||||||
.............................. | |||||||||
∂Fn | ∂Fn | ∂Fn | = −F . |
||||||
∂x | ∂x | ∂x | |||||||
Vrijednosti F 1... | derivati | obračunavaju se na |
|||||||
x 2 = a 2, …x n = a n.
Odrednica sistema (4.3) je Jakobijan:
∂ F 1 | ∂ F 1 |
|
∂x | ∂x |
|
∂ F 2 | ∂ F 2 |
|
J = ∂ x | ∂x. |
|
… … … …
∂ F n… … ∂ F n∂ x 1 ∂ x n
x 1= a 1,
Za postojanje jedino rešenje Jakobijan sistema mora biti različit od nule na svakoj iteraciji.
Dakle, iterativni proces rješavanja sistema jednadžbi Newtonovom metodom sastoji se od određivanja priraštaja x 1 , x 2 , ..., x n do vrijednosti nepoznatih na svakoj iteraciji rješavanjem sistema linearnih algebarskih jednadžbi ( 4.3). Brojanje se zaustavlja ako svi priraštaji postanu mali u apsolutnoj vrijednosti: maxx i< ε . В ме-
U Newtonovoj metodi, dobar izbor početne aproksimacije je također važan kako bi se osigurala dobra konvergencija. Konvergencija se pogoršava kako se broj jednačina u sistemu povećava.
Kao primjer, razmotrite korištenje Newtonove metode za rješavanje sistema od dvije jednačine:
∂ ∂ F 1. x
Količine na desnoj strani izračunate su pri x = a,y = b.
Ako su uslovi ispunjeni | y−b | < εи | x−a | za dato M, onda |
|||||
prikazane su vrijednosti x i y, | inače | dolazi do izlaza |
|||||||
x ,y ,M . | |||||||||