Skaitinis lygčių sprendimas o jų sistemos susideda iš apytikslės lygties ar lygčių sistemos šaknų nustatymo ir naudojamos tais atvejais, kai tikslus sprendimo būdas nežinomas arba reikalauja daug darbo.
Problemos pareiškimas[ | ]
Panagrinėkime lygčių ir lygčių sistemų skaitmeninio sprendimo būdus:
f (x 1 , x 2 , … , x n) = 0 (\displaystyle f(x_(1),x_(2),\ldots ,x_(n))=0)( f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 (\displaystyle \left\((\begin(masyvas)(lcr)f_(1)) )(x_(1),x_(2),\ltaškai ,x_(n))&=&0\\\ltaškai &&\\f_(n)(x_(1),x_(2),\ltaškai ,x_( n))&=&0\end(masyvas))\right.)
Skaitiniai lygčių sprendimo metodai[ | ]
Parodykime, kaip galite išspręsti pradinę lygčių sistemą nesinaudodami optimizavimo metodais. Jei mūsų sistema yra SLAE, patartina naudoti tokius metodus kaip Gauso metodas arba Richardson metodas. Tačiau vis tiek remsimės prielaida, kad funkcijos forma mums nežinoma, ir naudosime vieną iš iteracinių skaitinio sprendimo būdų. Tarp gausybės jų pasirinksime vieną žinomiausių – Niutono metodą. Šis metodas, savo ruožtu, yra pagrįstas gniuždomojo kartografavimo principu. Todėl pirmiausia bus nubrėžta pastarojo esmė.
Kompresinis kartografavimas[ | ]
Apibrėžkime terminologiją:
Teigiama, kad funkcija atlieka gniuždomasis kartografavimas ant jei
Tada galioja ši pagrindinė teorema:
| Banacho teorema (susitraukimo atvaizdavimo principas). Jeigu φ (\displaystyle \varphi )- suspaudžiamas ekranas įjungtas [a , b ] (\displaystyle), Tai: |
Iš paskutinio teoremos punkto išplaukia, kad bet kurio metodo, pagrįsto susitraukimų atvaizdais, konvergencijos greitis yra ne mažesnis nei tiesinis.
Paaiškinkime parametro reikšmę α (\displaystyle \alpha ) vieno kintamojo atveju. Pagal Lagrange'o teoremą turime:
φ (x) ∈ C 1 [ a , b ] .< x 2 ∃ ξ ∈ (x 1 , x 2) : φ ′ (ξ) (x 2 − x 1) = φ (x 2) − φ (x 1) {\displaystyle \varphi (x)\in C^{1}.\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{1}∀ x 1 , x 2 ∈ (a , b), x 1 Iš to išplaukiaα ≈ | φ ′ (ξ) |
(\displaystyle \alpha \approx |\varphi "(\xi)|)[ | ]
. Taigi, kad metodas suartėtų, pakanka to nuoseklių aproksimacijų metodas arba paprastu iteracijos metodu. Tačiau lygtį galima skirtingais būdais transformuoti į susitraukimo žemėlapį, turintį tą pačią šaknį. Dėl to atsiranda keletas konkrečių metodų, kurie turi tiek tiesinį, tiek didesnį konvergencijos rodiklį.
Kalbant apie SLAU[ | ]
Apsvarstykite sistemą:
( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(masyvas)(ccc)a_(11)x_(1)+) \ltaškai +a_(1n)x_(n)&=&b_(1)\\\ltaškai &&\\a_(n1)x_(1)+\ltaškai +a_(nn)x_(n)&=&b_(n) \end(masyvas))\right.)
Tam iteracinis skaičiavimas atrodys taip:
(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(masyvas)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end (masyvas))\right)^(i+1)=\left((\begin(masyvas)(cccc)a_(11)+1&a_(12)&\ltaškai &a_(1n)\\a_(21)&a_( 22)+1&\ltaškai &a_(2n)\\\vtaškai &\vtaškai &\dtaškai &\vtaškai \\a_(n1)&a_(n2)&\ltaškai &a_(nn)+1\pabaiga (masyvas))\dešinė )\left((\begin(masyvas)(c)x_(1)\\x_(2)\\\vtaškai \\x_(n)\end(masyvas))\right)^(i)-\left( (\begin(masyvas)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(masyvas))\right))
Metodas susilies su tiesiniu greičiu, jei ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}
Dvigubos vertikalios juostos rodo tam tikrą matricos normą.
Lygties f(x)=0 sprendimas Niutono metodu, pradinė aproksimacija: x 1 =a.
Niutono metodas (tangentinis metodas)[ | ]
Vienmatis korpusas[ | ]
Pradinės lygties transformacijos optimizavimas f (x) = 0 (\displaystyle f(x)=0)į suspaudžiamą ekraną x = φ (x) (\displaystyle x=\varphi (x)) leidžia gauti metodą su kvadratine konvergencijos sparta.
Kad atvaizdavimas būtų efektyviausias, kitos iteracijos taške būtina x ∗ (\displaystyle x^(*)) atlikti φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Šios lygties sprendimo ieškosime formoje φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), Tada:
φ ′ (x ∗) = 1 + α ′ (x ∗) f (x ∗) + α (x ∗) f ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=1+ \alpha "(x^(*))f(x^(*))+\alpha (x^(*))f"(x^(*))=0)Pasinaudokime tuo faktu f (x) = 0 (\displaystyle f(x)=0), ir gauname galutinę formulę α (x) (\displaystyle \alpha (x)):
α (x) = − 1 f ′ (x) (\displaystyle \alpha (x)=-(\frac (1)(f"(x))))Atsižvelgiant į tai, suspaudimo funkcija bus tokia:
φ (x) = x − f (x) f ′ (x) (\displaystyle \varphi (x)=x-(\frac (f(x))(f"(x))))Tada lygties skaitinio sprendimo paieškos algoritmas f (x) = 0 (\displaystyle f(x)=0) sumažina iki pasikartojančios skaičiavimo procedūros:
x i + 1 = x i − f (x i) f ′ (x i) (\displaystyle x_(i+1)=x_(i)-(\frac (f(x_(i)))(f"(x_(i) ))))1. Žinome atkarpą, kurioje yra viena lygties šaknis f(x) = 0. Funkcija f yra tolydžio diferencijavimo funkcija šiame atkarpoje (f(x)ОC 1 ). Jei šios sąlygos yra įvykdytos, galima naudoti paprastą iteracijos metodą.
2. Naudojant funkciją f(x), sukonstruojama funkcija j(x), kuri tenkina tris sąlygas: ji turi būti nuolat diferencijuojama (j(x)ОC 1 ), kad lygtis x = j(x) yra lygiavertis lygčiai f(x)=0; taip pat turėtų išversti segmentą į save.
Sakysime, kad funkcija j ( x ) verčia segmentą [ a , b ] į save, jei kam x Î [ a , b ], y = j ( x ) taip pat priklauso[ a , b ] ( y Î [ a , b ]).
Trečioji sąlyga taikoma funkcijai j(x):
Metodo formulė: x n +1 = j(xn).
3. Jei šios trys sąlygos atitinka bet kurį pradinį aproksimaciją x 0 О iteracijų seka x n +1 = j(x n) konverguoja į lygties šaknį: x = j(x) atkarpoje ().
Paprastai kaip x 0 pasirenkamas vienas iš galų.
,
kur e yra nurodytas tikslumas
Skaičius x n +1 kai įvykdoma iteracinio proceso sustabdymo sąlyga, tai yra apytikslė lygties šaknies reikšmė f(x) = 0 atkarpoje , rasta paprastu iteracijos metodu su tikslumu e .
Sukurkite algoritmą, kad paaiškintumėte lygties šaknį: x 3 + 5x – 1 = 0 atkarpoje naudojant paprastos iteracijos metodą tikslumu e .
1. Funkcija f(x) = x 3 +5x-1 yra nuolat diferencijuojamas intervale, kuriame yra viena lygties šaknis.
2. Didžiausias paprastos iteracijos metodo sunkumas yra funkcijos j(x), kuri tenkina visas sąlygas, sukūrimas:
Apsvarstykite: 
.
Lygtis x = j 1 (x) yra lygiavertis lygčiai f(x) = 0, bet funkcija j 1 (x) intervale nėra nuolat diferencijuojama.
Ryžiai. 2.4. Funkcijos j 2 (x) grafikas
Kita vertus, todėl. Vadinasi: yra nuolat diferencijuojama funkcija. Atkreipkite dėmesį, kad lygtis: x = j 2 (x) yra lygiavertė lygčiai f(x) = 0 . Iš grafiko (2.4 pav.) aišku, kad funkcija j 2 (x) paverčia atkarpą į save.
Sąlyga, kad funkcija j(x) paima atkarpą į save, gali būti performuluojama taip: tegul yra funkcijos j(x) apibrėžimo sritis, o tegul j(x) variacijos sritis.
Jei atkarpa priklauso atkarpai , tai funkcija j(x) perima atkarpą į save.
, 
.
Tenkinamos visos funkcijos j(x) sąlygos.
Iteracinė proceso formulė: x n +1 = j 2(xn).
3. Pradinė aproksimacija: x 0 = 0.
4. Pakartotinio proceso sustabdymo sąlyga:
Ryžiai. 2.5. Geometrinė paprastos iteracijos metodo reikšmė
.
Jei ši sąlyga įvykdoma x n +1 – apytikslė atkarpos šaknies vertė, randama naudojant paprastą iteraciją su tikslumu e. Fig. 2.5. Pavaizduotas paprastos iteracijos metodo taikymas.
Konvergencijos teorema ir paklaidos įvertinimas
Tegul segmentas yra viena lygties šaknis x = j(x), funkcija j(x ) yra nuolat diferencijuojamas intervale , verčia segmentą į save, ir sąlyga yra įvykdyta:
.
Tada bet kokiam pradiniam aproksimavimui x 0 О seka konverguoja į lygties šaknį y = j(x ) segmente ir klaidų įvertinimas yra teisingas:
.
Paprastos iteracijos metodo stabilumas. Kai tenkinamos konvergencijos teoremos sąlygos, paprastos iteracijos metodo algoritmas yra stabilus.
Paprastos iteracijos metodo sudėtingumas. Kompiuterio atminties kiekis, reikalingas paprastos iteracijos metodui įgyvendinti, yra nereikšmingas. Kiekviename žingsnyje reikia išsaugoti x n , x n +1 , q Ir e.
Įvertinkime aritmetinių operacijų, reikalingų paprastos iteracijos metodui įgyvendinti, skaičių. Užrašykime tokį skaičių n 0 = n 0 (e), kad visiems n ³ n 0 galiotų nelygybė: 
Iš šio įvertinimo matyti, kad kuo q arčiau vieneto, tuo lėčiau metodas konverguoja.
komentuoti. Nėra bendros taisyklės, kaip sudaryti j(x) iš f(x), kad būtų įvykdytos visos konvergencijos teoremos sąlygos. Dažnai naudojamas toks metodas: funkcija j(x) = x + k× f(x) pasirenkama kaip funkcija j, kur k – pastovus.
Programuojant paprastą iteracijos metodą, norint sustabdyti kartotinį procesą, dažnai reikia vienu metu įvykdyti dvi sąlygas:
Ir .
Visi kiti iteraciniai metodai, kuriuos svarstysime, yra ypatingi paprasto iteracijos metodo atvejai. Pavyzdžiui, kada 
Niutono metodas yra ypatingas paprastos iteracijos metodo atvejis.
Paprastas iteracijos metodas pagrįstas pradinės lygties pakeitimu lygiaverte lygtimi:
Tegul yra žinomas pradinis aproksimacija iki šaknies x = x 0. Pakeitę jį į dešinę (2.7) lygties pusę, gauname naują aproksimaciją 
, tada panašiu būdu gauname 
ir tt:
. (2.8)
 |
Ne visomis sąlygomis iteracinis procesas susilieja su lygties šaknimi X. Pažvelkime į šį procesą atidžiau. 2.6 paveiksle parodyta grafinė vienpusio konvergencinio ir divergentinio proceso interpretacija. 2.7 paveiksle pavaizduoti dvipusiai konvergentiniai ir divergentiniai procesai. Skirtingam procesui būdingas greitas argumento ir funkcijos reikšmių padidėjimas ir nenormalus atitinkamos programos nutraukimas.
 |
Naudojant dvipusį procesą, galimas cikliškumas, tai yra begalinis tos pačios funkcijos ir argumentų reikšmių kartojimas. Kilpų sudarymas atskiria divergentinį procesą nuo susiliejančio.
Iš grafikų matyti, kad tiek vienpusiams, tiek dvipusiams procesams konvergenciją į šaknį lemia kreivės nuolydis šalia šaknies. Kuo mažesnis nuolydis, tuo geriau konvergencija. Kaip žinoma, kreivės nuolydžio liestinė yra lygi kreivės išvestinei tam tikrame taške.
Todėl kuo mažesnis skaičius šalia šaknies, tuo greičiau procesas susilieja.
Kad iteracijos procesas būtų konvergentiškas, šalia šaknies turi būti įvykdyta ši nelygybė:
Perėjimas nuo (2.1) lygties prie (2.7) gali būti atliekamas įvairiais būdais, priklausomai nuo funkcijos tipo f(x). Tokiame perėjime funkciją reikia sukonstruoti taip, kad būtų įvykdyta konvergencijos sąlyga (2.9).
Panagrinėkime vieną iš bendrųjų perėjimo iš (2.1) lygties į (2.7) lygtį algoritmų.
Padauginkime kairę ir dešinę lygties (2.1) puses iš savavališkos konstantos b ir pridėti nežinomąjį prie abiejų dalių X. Tokiu atveju pradinės lygties šaknys nepasikeis:
Supažindinkime su užrašu 
ir pereikime nuo santykio (2.10) prie lygties (2.8).
 |
Savavališkas konstantos pasirinkimas b užtikrins konvergencijos sąlygos (2.9) įvykdymą. Iteracinio proceso pabaigos kriterijus bus sąlyga (2.2). 2.8 paveiksle pateiktas paprastų iteracijų metodo grafinis aiškinimas naudojant aprašytą vaizdavimo būdą (masteliai išilgai X ir Y ašių skiriasi).
Jei funkcija pasirinkta formoje , tada šios funkcijos išvestinė bus . Tada didžiausias konvergencijos greitis bus 
o iteracijos formulė (2.11) virsta Niutono formule. Taigi, Niutono metodas turi aukščiausią visų iteracinių procesų konvergencijos laipsnį.
Paprastos iteracijos metodo programinė įranga įdiegta paprogramės procedūros forma Iteras(2.1 PROGRAMA).
Visa procedūra praktiškai susideda iš vieno kartojimo ... iki ciklo, įgyvendinant formulę (2.11), atsižvelgiant į pasikartojančio proceso sustabdymo sąlygą (formulė (2.2)).
Procedūra turi įmontuotą kilpų apsaugą, skaičiuojant kilpų skaičių naudojant Niter kintamąjį. Praktiniuose užsiėmimuose, paleisdami programą, turite įsitikinti, kaip veikia koeficiento pasirinkimas b ir pradinis aproksimavimas ieškant šaknies. Keičiant koeficientą b kinta tiriamos funkcijos iteracijos proceso pobūdis. Iš pradžių jis tampa dvipusis, o paskui kilpinis (2.9 pav.). Ašies svarstyklės X Ir Y yra skirtingi. Dar didesnė modulio b reikšmė lemia skirtingą procesą.
Apytikslių lygčių sprendimo metodų palyginimas
Aukščiau aprašytų lygčių skaitinio sprendimo metodų palyginimas atliktas naudojant programą, leidžiančią kompiuterio ekrane grafine forma stebėti šaknies radimo procesą. Į šią programą įtrauktos ir palygintus metodus įgyvendinančios procedūros pateiktos žemiau (PROGRAMOS 2.1).
Ryžiai. 2.3–2.5, 2.8, 2.9 yra kompiuterio ekrano kopijos iteracijos proceso pabaigoje.
Visais atvejais kaip tiriama funkcija buvo imta kvadratinė lygtis x 2 -x-6 = 0, kurios analitinis sprendimas x 1 = -2 ir x 2 = 3. Priimta, kad visų metodų paklaida ir pradinės aproksimacijos yra lygios. Šakninės paieškos rezultatai x= 3, pateikti paveiksluose, yra tokie. Dichotomijos metodas konverguoja lėčiausiai - 22 iteracijos, greičiausias yra paprastas iteracijos metodas su b = -0,2 - 5 iteracijos. Čia nėra prieštaravimo teiginiui, kad Niutono metodas yra greičiausias.
Taške tiriamos funkcijos išvestinė X= 3 yra lygus -0,2, tai yra, skaičiavimas šiuo atveju buvo atliktas praktiškai Niutono metodu su išvestinės reikšme lygties šaknies taške. Keičiant koeficientą b konvergencijos greitis mažėja, o palaipsniui konvergencinis procesas pirmiausia vyksta ciklais, o paskui tampa divergentiškas.
