DRŽAVNI UNIVERZITET SANKT PETERBURG

Fakultet primijenjene matematike - Kontrolni procesi

A. P. IVANOV

RADIONICA NUMERIČKIH METODA

RJEŠENJE SISTEMA LINEARNIH ALGEBRSKIH JEDNAČINA

Smjernice

Sankt Peterburg

POGLAVLJE 1. PODRŠNE INFORMACIJE

IN metodološki vodič data je klasifikacija metoda za rješavanje SLAE i algoritmi za njihovu primjenu. Metode su predstavljene u obliku koji dozvoljava njihovu upotrebu bez pozivanja na druge izvore. Pretpostavlja se da je matrica sistema nesingularna, tj. det A 6= 0.

§1. Norme vektora i matrica

Podsjetimo da se linearni prostor Ω elemenata x naziva normaliziranim ako sadrži funkciju k · kΩ , koja je definirana za sve elemente prostora Ω i zadovoljava sljedeće uvjete:

1. kxk Ω ≥ 0, i kxkΩ = 0 x = 0Ω ;

2. kλxk Ω = |λ| kxkΩ ;

3. kx + ykΩ ≤ kxkΩ + kykΩ .

Ubuduće ćemo se dogovoriti da vektori označavamo malim latiničnim slovima i smatraćemo ih vektorima kolona, ​​matrice ćemo označavati velikim latiničnim slovima, a skalarne veličine označavaćemo grčkim slovima (zadržavajući oznake za cele brojeve iza slova i, j, k, l, m, n) .

Najčešće korištene vektorske norme uključuju sljedeće:

2. kxk2 = u x2 ; t

3. kxk∞ = maxi |xi |.

Imajte na umu da su sve norme u prostoru Rn ekvivalentne, tj. bilo koje dvije norme kxki i kxkj povezane su:

αij kxkj ≤ kxki ≤ βij kxkj ,

k k ≤ k k ≤ ˜ k k

α˜ ij x i x j β ij x i,

štaviše, αij , βij , α˜ij , βij ne zavise od x. Štaviše, u konačnodimenzionalnom prostoru, bilo koje dvije norme su ekvivalentne.

Prostor matrica sa prirodno uvedenim operacijama sabiranja i množenja brojem čine linearni prostor u koji se pojam norme može uvesti na mnogo načina. Međutim, najčešće se razmatraju takozvane podređene norme, tj. norme vezane za norme vektora relacijama:

Označavajući podređene norme matrica sa istim indeksima kao i odgovarajuće norme vektora, možemo utvrditi da

Ovdje λi (AT A) označava vlastitu vrijednost matrice AT A, gdje je AT matrica transponirana u A. Pored tri glavna svojstva norme koja su gore navedena, ovdje napominjemo još dva:

kABk ≤ kAk kBk,

kAxk ≤ kAk kxk,

štaviše, u posljednjoj nejednakosti, matrična norma je podređena odgovarajućoj vektorskoj normi. Složimo se da u nastavku koristimo samo norme matrica koje su podređene normama vektora. Imajte na umu da za takve norme vrijedi jednakost: ako je E matrica identiteta, tada je kEk = 1, .

§2. Matrice sa dijagonalnom dominacijom

Definicija 2.1. Matrica A sa elementima (aij)n i,j=1 naziva se matrica sa dijagonalnom dominacijom (vrijednosti δ) ako su nejednakosti

|ai | − |aij| ≥ δ > 0, i = 1, n .

§3. Pozitivno određene matrice

Definicija 3.1. Pozvat će se simetrična matrica A

pozitivno određen ako kvadratni oblik xT Ax sa ovom matricom uzima samo pozitivne vrijednosti za bilo koji vektor x 6= 0.

Kriterijum za pozitivnu određenost matrice može biti pozitivnost njenih sopstvenih vrednosti ili pozitivnost njenih glavnih minora.

§4. Broj stanja SLAE

Prilikom rješavanja bilo kojeg problema, kao što je poznato, postoje tri vrste grešaka: fatalna greška, metodološka greška i greška zaokruživanja. Razmotrimo utjecaj fatalne greške početnih podataka na rješenje SLAE, zanemarujući grešku zaokruživanja i uzimajući u obzir odsustvo metodološke greške.

matrica A je tačno poznata, a desna strana b sadrži neotklonjivu grešku δb.

Zatim za relativnu grešku rješenja kδxk/kxk

gdje je ν(A) = kAkkA−1k.

Broj ν(A) naziva se uslovni broj sistema (4.1) (ili matrice A). Ispada da je uvijek ν(A) ≥ 1 za bilo koju matricu A. Pošto vrijednost broja uvjeta ovisi o izboru norme matrice, prilikom odabira određene norme indeksiraćemo ν(A) , odnosno: ν1 ( A), ν2 (A), ili ν ∞(A).

U slučaju ν(A) 1, sistem (4.1) ili matrica A kaže se da je loše uslovljen. U ovom slučaju, kako slijedi iz procjene

(4.2), greška u rješenju sistema (4.1) može se pokazati neprihvatljivo velikom. Koncept prihvatljivosti ili neprihvatljivosti greške određen je formulacijom problema.

Za matricu sa dijagonalnom dominacijom, lako je dobiti gornju procjenu njenog broja uvjeta. Javlja se

Teorema 4.1. Neka je A matrica sa dijagonalnom dominacijom od δ > 0. Tada je nesingularna i ν∞ (A) ≤ kAk∞ /δ.

§5. Primjer loše uvjetovanog sistema.

Razmotrimo SLAE (4.1) , u kojoj

Ovaj sistem ima jedinstveno rješenje x = (0, 0, . . . , 0, 1)T . Neka desna strana sistema sadrži grešku δb = (0, 0, . . . , 0, ε), ε > 0. Tada

δxn = ε, δxn−1 = ε, δxn−2 = 2 ε, δxn−k = 2 k−1 ε, . . . , δx1 = 2n−2ε.

dakle,

ν∞ (A) ≥ kδxk ∞ : kδbk ∞ = 2n−2 . kxk ∞ kbk ∞

Kako je kAk∞ = n, onda je kA−1 k∞ ≥ n−1 2 n−2 , iako je det(A−1 ) = (det A)−1 = 1. Neka je, na primjer, n = 102. Tada je ν( A ) ≥ 2100 > 1030 . Štaviše, čak i ako je ε = 10−15 dobijamo kδxk∞ > 1015 . A to nije

Definicija.

Sistemom nazivamo sistem sa dominacijom dijagonale reda ako su elementi matricezadovoljiti nejednakosti:

,

Nejednakosti znače da u svakom redu matrice dijagonalni element je istaknut: njegov modul je veći od zbira modula svih ostalih elemenata istog reda.

Teorema

Sistem sa dijagonalnom dominacijom uvijek je rješiv i, štaviše, jedinstven.

Razmotrimo odgovarajući homogeni sistem:

,

Pretpostavimo da ima netrivijalno rješenje , Neka komponenta ovog rješenja, koja ima najveći modul, odgovara indeksu
, tj.

,
,
.

Hajde da zapišemo jednačina sistema u obliku

i uzmimo modul obje strane ove jednakosti. Kao rezultat, dobijamo:

.

Smanjenje nejednakosti za faktor
, što prema tome nije jednako nuli, dolazimo do kontradikcije sa nejednakošću koja izražava dijagonalnu dominaciju. Nastala kontradikcija nam omogućava da dosljedno navodimo tri tvrdnje:

Posljednji od njih znači da je dokaz teoreme završen.

1. Sistemi sa tridijagonalnom matricom. Sweep metoda.

Prilikom rješavanja mnogih problema potrebno je raditi sa sistemima linearnih jednačina oblika:

,
,

,
,

gdje su koeficijenti
, desne strane
poznati zajedno sa brojevima I . Dodatne relacije se često nazivaju graničnim uslovima za sistem. U mnogim slučajevima mogu imati složeniji izgled. Na primjer:

;
,

Gdje
su dati brojevi. Međutim, da ne bismo komplicirali prezentaciju, ograničavamo se na najjednostavniji oblik dodatnih uvjeta.

Koristeći činjenicu da su vrijednosti I dato, prepisujemo sistem u obliku:

Matrica ovog sistema ima tridijagonalnu strukturu:

Ovo uvelike pojednostavljuje rješenje sistema zahvaljujući posebnoj metodi koja se zove metoda sweep.

Metoda se zasniva na pretpostavci da su željene nepoznanice I
povezane relacijom recidiva

,
.

Evo količine
,
, koji se nazivaju koeficijenti sweep-a, određuju se na osnovu uslova problema, . U stvari, takav postupak znači zamjenu direktne definicije nepoznatih zadatak određivanja koeficijenata sweep-a sa naknadnim proračunom veličina .

Za implementaciju opisanog programa izražavamo pomoću relacije
kroz
:

i zamena
I , izraženo kroz
, u originalne jednadžbe. Kao rezultat, dobijamo:

.

Posljednji odnosi će svakako biti zadovoljeni i, štaviše, bez obzira na rješenje, ako se zahtijeva da se na
desile su se jednakosti:

Odavde slijede rekurzivne relacije za koeficijente sweep-a:

,
,
.

Lijevo granično stanje
i omjer
su dosljedne ako stavimo

.

Ostale vrijednosti koeficijenata sweep-a
I
nalazimo od, sa kojim i završavamo fazu izračunavanja koeficijenata sweep-a.

.

Odavde možete pronaći ostale nepoznanice
u procesu pomicanja unazad koristeći rekurzivnu formulu.

Broj operacija potrebnih za rješavanje općeg sistema korištenjem Gaussove metode raste s povećanjem proporcionalno . Metoda sweep-a se svodi na dva ciklusa: prvo se izračunavaju koeficijenti sweep-a pomoću formula, a zatim se pomoću njih komponente sistemskog rješenja pronalaze pomoću rekurentnih formula . To znači da kako se veličina sistema povećava, broj aritmetičkih operacija će rasti proporcionalno , ali ne . Stoga je metoda sweep-a u okviru svoje moguće primjene znatno ekonomičnija. Ovome treba dodati posebnu jednostavnost njegove softverske implementacije na računaru.

U mnogim primijenjenim problemima koji vode do SLAE sa tridijagonalnom matricom, njeni koeficijenti zadovoljavaju nejednakosti:

,

koji izražavaju svojstvo dijagonalne dominacije. Konkretno, takve sisteme ćemo sresti u trećem i petom poglavlju.

Prema teoremi iz prethodnog odjeljka, rješenje takvih sistema uvijek postoji i jedinstveno je. Oni također imaju izjavu koja je važna za stvarni proračun rješenja korištenjem metode sweep.

Lemma

Ako je za sistem sa tridijagonalnom matricom uslov dijagonalne dominacije zadovoljen, tada koeficijenti sweep-a zadovoljavaju nejednakosti:

.

Dokaz ćemo izvesti indukcijom. Prema
, ja jedem
tvrdnja leme je tačna. Pretpostavimo sada da je to tačno za i razmotriti
:

.

Dakle, indukcija iz To
opravdano, čime je završen dokaz leme.

Nejednakost za koeficijente sweep-a čini trčanje stabilnim. Zaista, pretpostavimo da je komponenta rješenja kao rezultat postupka zaokruživanja izračunava se sa određenom greškom. Zatim prilikom izračunavanja sljedeće komponente
prema rekurzivnoj formuli, ova greška se zbog nejednakosti neće povećati.

NEDEGENERNOST MATRICA I SVOJSTVO DIJAGONALNE DOMINANCIJE1

L. Cvetkovich, V. Kostić i L.A. Crookier

Cvetković Lilijana - profesor, Departman za matematiku i informatiku, Prirodno-matematički fakultet Univerziteta u Novom Sadu, Srbija, Obradovića 4, Novi Sad, Srbija, 21000, e-mail: [email protected]

Kostić Vladimir - docent, doktor, Departman za matematiku i informatiku, Prirodno-matematički fakultet Univerziteta u Novom Sadu, Srbija, Obradovića 4, 21000, Novi Sad, Srbija, email: [email protected]

Krukier Lev Abramovič - doktor fizičko-matematičkih nauka, profesor, šef katedre za računarstvo visokih performansi i informaciono-komunikacionih tehnologija, direktor Južnoruskog regionalnog centra za informatizaciju juga federalni univerzitet Stački 200/1, bul. 2, Rostov na Donu, 344090, e-mail: [email protected] ru.

Cvetković Ljiljana - profesor, Departman za matematiku i informatiku, Prirodno-matematički fakultet Univerziteta u Novom Sadu, Srbija, D. Obradovića 4, Novi Sad, Srbija, 21000, e-mail: [email protected]

Kostić Vladimir - docent, Departman za matematiku i informatiku, Prirodno-matematički fakultet Univerziteta u Novom Sadu, Srbija, D. Obradovića 4, Novi Sad, Srbija, 21000, e-mail: [email protected]

Krukier Lev Abramovič - doktor fizičko-matematičkih nauka, profesor, šef Katedre za računarstvo visokih performansi i informaciono-komunikacione tehnologije, direktor Računskog centra Južnog federalnog univerziteta, Stački Ave, 200/1, bild. 2, Rostov na Donu, Rusija, 344090, e-mail: [email protected] ru.

Dijagonalna dominacija u matrici je jednostavno stanje, osiguravajući njegovu nedegeneraciju. Svojstva matrice koja generaliziraju pojam dijagonalne dominacije uvijek su veoma tražena. Oni se smatraju uslovima tipa dijagonalne dominacije i pomažu da se definišu podklase matrica (poput H-matrica) koje ostaju nedegenerisane pod ovim uslovima. U ovom radu konstruiramo nove klase nesingularnih matrica koje zadržavaju prednosti dijagonalne dominacije, ali ostaju izvan klase H-matrica. Ova svojstva su posebno pogodna jer mnoge aplikacije vode do matrica u ovoj klasi, a teorija nedegeneracije matrica koje nisu H-matrice sada se može proširiti.

Ključne riječi: dijagonalna dominacija, nedegeneracija, skaliranje.

Dok su jednostavni uvjeti koji osiguravaju nesingularnost matrica uvijek vrlo dobrodošli, mnogi od njih koji se mogu smatrati tipom dijagonalne dominacije imaju tendenciju da proizvode podklase dobro poznatih H-matrica. U ovom radu konstruišemo nove klase nesingularnih matrica koje zadržavaju korisnost dijagonalne dominacije, ali stoje u opštem odnosu sa klasom H-matrica. Ovo svojstvo je posebno povoljno, budući da se mnoge primjene koje proizlaze iz teorije H-matrice sada mogu proširiti.

Ključne riječi: dijagonalna dominacija, nesingularnost, tehnika skaliranja.

Numeričko rješenje graničnih problema matematičke fizike obično svodi originalni problem na rješenje sistema linearnih algebarskih jednačina. Kada biramo algoritam rješenja, moramo znati da li je originalna matrica nesingularna? Osim toga, pitanje nedegeneracije matrice je relevantno, na primjer, u teoriji konvergencije iterativnih metoda, lokalizaciji vlastitih vrijednosti, u procjeni determinanti, korijenima pregača, spektralnom radijusu, singularnim vrijednostima a matrica itd.

Imajte na umu da je jedan od najjednostavnijih, ali izuzetno korisnih uvjeta koji osiguravaju nedegeneraciju matrice dobro poznato svojstvo stroge dijagonalne dominacije (i reference na njih).

Teorema 1. Neka je data matrica A = e Cnxn takva da je

s > r (a):= S k l, (1)

za sve i e N:= (1,2,...n).

Tada je matrica A nedegenerirana.

Matrice sa svojstvom (1) nazivaju se matrice sa strogom dijagonalnom dominacijom

(8BB matrice). Njihova prirodna generalizacija je klasa matrica sa generalizovanom dijagonalnom dominacijom (GBD), definisana na sledeći način:

Definicija 1. Matrica A = [a^] e Cxn naziva se sBB matrica ako postoji nesingularna dijagonalna matrica W takva da je AW matrica od 8BB.

Uvodimo nekoliko definicija za matricu

A \u003d [ay] e Spxp.

Definicija 2

(A) = e Cn

naziva se matrica poređenja matrice A.

Definicija 3. Matrica A = e C

\üj > 0, i = j

je M-matrica ako

aj< 0, i * j,

obrnuti mat-

matrica A">0, tj. svi njeni elementi su pozitivni.

Očigledno, matrice iz wBB klase su također nesingularne matrice i mogu biti

1Ovaj rad je delimično podržalo Ministarstvo prosvete i nauke Srbije, grant 174019, i Ministarstvo nauke i tehnološkog razvoja Vojvodine, grantovi 2675 i 01850.

nalazi se u literaturi pod nazivom nedegenerisane H-matrice. Oni se mogu definisati korišćenjem sledećeg neophodnog i dovoljnog uslova:

Teorema 2. Matrica A \u003d [ay ]e xi

matrica ako i samo ako je njena matrica poređenja nedegenerirana M-matrica.

Do sada su mnoge podklase nedegenerisanih H-matrica već proučavane, ali su sve one razmatrane sa stanovišta generalizacije svojstva striktno dijagonalne dominacije (vidi i reference u njima).

U ovom radu razmatramo mogućnost prevazilaženja klase H-matrica generalizacijom SBB klase na drugačiji način. Glavna ideja je nastaviti koristiti pristup skaliranja, ali s matricama koje nisu dijagonalne.

Razmotrimo matricu A = [ay ] e spxn i indeks

Uvodimo matricu

r (A):= £ a R (A):= £

ßk (A) := £ i yk (A) := aü - ^

Lako je provjeriti da elementi matrice bk Abk imaju sljedeći oblik:

ßk (A), Y k (A), akj,

i=j=k, i=j*k,

i = k, j * k, i * k, j = k,

A inöaeüiüö neo^äyö.

Ako primijenimo teoremu 1 na gore opisanu matricu bk Abk1 i njenu transponovanu, onda ćemo dobiti dvije glavne teoreme.

Teorema 3. Neka je data bilo koja matrica

A \u003d [ay ] e spxn s dijagonalnim elementima koji nisu nula. Ako postoji k e N takvo da je > Rk (A), i za svako i e N \ (k),

onda je matrica A nedegenerisana.

Teorema 4. Neka je data bilo koja matrica

A \u003d [ay ] e spxn s dijagonalnim elementima koji nisu nula. Ako postoji k e N takvo da je > Jk (A), i za svako i e N \ (k),

Tada je matrica A nedegenerirana. Postavlja se prirodno pitanje o odnosu između

matrice iz prethodne dvije teoreme: L^ - BOO -matrice ( definisana formulom(5)) i

bk - BOO-matrice (definirane formulom (6)) i klasa H-matrica. Sljedeći jednostavan primjer to čini jasnim.

Primjer. Razmotrite sljedeće 4 matrice:

i razmotrimo matricu bk Abk, k e N, sličnu originalnoj A. Nađimo uslove kada će ova matrica imati svojstvo SDD-matrice (po redovima ili kolonama).

U cijelom članku, za r,k eN:= (1,2,.../?) koristit ćemo notaciju:

2 2 1 1 3 -1 1 1 1

" 2 11 -1 2 1 1 2 3

2 1 1 1 2 -1 1 1 5

Teoreme o nedegeneraciji

Svi su nedegenerisani:

A1 je b - BOO, uprkos činjenici da nije bk - BOO za bilo koji k = (1,2,3). Takođe nije H-matrica, pošto (A^1 nije nenegativna;

A2 je, zbog simetrije, istovremeno LH - BOO i L<2 - БОО, так же как ЬЯ - БОО и

b<3 - БОО, но не является Н-матрицей, так как (А2) вырожденная;

A3 je b9 - BOO, ali nije ni jedno ni drugo

Lr je SDD (za k = (1,2,3)), niti H-matrica jer je (A3 ^ takođe degenerisana;

A4 je H-matrica jer (A^ je nesingularna, a ^A4) 1 > 0, iako nije ni LR - SDD ni Lk - SDD za bilo koji k = (1,2,3).

Slika prikazuje opšti odnos između

Lr - SDD , Lk - SDD i H-matrice zajedno sa matricama iz prethodnog primjera.

Komunikacija između lR - SDD, lC - SDD i

pakao min(|au - r (A)|) "

Počevši od nejednakosti

i primjenom ovog rezultata na matricu bk ab ^ dobijamo

Teorema 5. Neka je data proizvoljna matrica A = [a--] e Cxn sa nenultim dijagonalnim elementima.

policajci. Ako A pripada klasi - BOO, onda

1 + max^ i*k \acc\

H-matrice

Zanimljivo je napomenuti da iako imamo

klasa LC BOO-matrica primjenom teoreme 1 na matricu dobijenu transponovanjem matrice LC AL^1, ova klasa se ne poklapa sa klasom dobijenom primjenom teoreme 2 na matricu Am.

Uvodimo definicije.

Definicija 4. Matrica A se zove ( bk -boo po redovima) ako je AT ( bk -boo).

Definicija 5. Matrica A se zove ( bsk -boo po redovima) ako je AT ( bsk -boo ).

Primjeri pokazuju da klase W - BOO,

bc-boo, (bk-boo po redu) i (b^-boo po redu) su međusobno povezani. Dakle, proširili smo klasu H-matrica na četiri različita načina.

Primjena novih teorema

Ilustrujmo korisnost novih rezultata u procjeni C-norme inverzne matrice.

Za proizvoljnu matricu A sa strogom dijagonalnom dominacijom, dobro poznata Varahova teorema (Varah) daje procjenu

min[|pf(A)| - mk (A), min(|yk (A)| - qk(A) - |af (A)|)]" i i (Ff ii ii

Slično, dobijamo sljedeći rezultat za matrice Lk - SDD po ​​stupcima.

Teorema 6. Neka je data proizvoljna matrica A = e xi sa nenultim dijagonalnim elementima. Ako A pripada klasi bk -SDD po ​​stupcima, onda

Ik-lll<_ie#|akk|_

" "mln[|pf(A)| - Rf (AT), milion(|uk (A)|- qk (AT)- |na krmi |)]"

Važnost ovog rezultata leži u činjenici da za mnoge podklase nesingularnih H-matrica postoje ograničenja ovog tipa, ali za one nesingularne matrice koje nisu H-matrice, ovo je netrivijalan problem. Stoga su ograničenja ove vrste, kao iu prethodnoj teoremi, veoma tražena.

Književnost

Levy L. Sur le possibilité du l "equlibre electrique C. R. Acad. Paris, 1881. Vol. 93. P. 706-708.

Horn R.A., Johnson C.R. matrična analiza. Cambridge, 1994. Varga R.S. Gersgorin i njegovi krugovi // Springer Series in Computational Mathematics. 2004 Vol. 36.226 str. Berman A., Plemons R.J. Nenegativne matrice u matematičkim naukama. SIAM Series Classics in Applied Mathematics. 1994 Vol. 9. 340 rubalja

Cvetković Lj. Teorija H-matrice vs. lokalizacija vlastitih vrijednosti // Numer. Algor. 2006 Vol. 42. P. 229-245. Cvetković Lj., Kostić V., Kovačević M., Szulc T. Dalji rezultati o H-matricama i njihovim Schur komplementima // Appl. Math. Račun. 1982. P. 506-510.

Varah J.M. Donja granica za najmanju vrijednost matrice // Linearna algebra Appl. 1975 Vol. 11. str. 3-5.

Primio urednik

Definicija.

Sistemom nazivamo sistem sa dominacijom dijagonale reda ako su elementi matricezadovoljiti nejednakosti:

,

Nejednakosti znače da u svakom redu matrice dijagonalni element je istaknut: njegov modul je veći od zbira modula svih ostalih elemenata istog reda.

Teorema

Sistem sa dijagonalnom dominacijom uvijek je rješiv i, štaviše, jedinstven.

Razmotrimo odgovarajući homogeni sistem:

,

Pretpostavimo da ima netrivijalno rješenje , Neka komponenta ovog rješenja, koja ima najveći modul, odgovara indeksu
, tj.

,
,
.

Hajde da zapišemo jednačina sistema u obliku

i uzmimo modul obje strane ove jednakosti. Kao rezultat, dobijamo:

.

Smanjenje nejednakosti za faktor
, što prema tome nije jednako nuli, dolazimo do kontradikcije sa nejednakošću koja izražava dijagonalnu dominaciju. Nastala kontradikcija nam omogućava da dosljedno navodimo tri tvrdnje:

Posljednji od njih znači da je dokaz teoreme završen.

1. Sistemi sa tridijagonalnom matricom. Sweep metoda.

Prilikom rješavanja mnogih problema potrebno je raditi sa sistemima linearnih jednačina oblika:

,
,

,
,

gdje su koeficijenti
, desne strane
poznati zajedno sa brojevima I . Dodatne relacije se često nazivaju graničnim uslovima za sistem. U mnogim slučajevima mogu imati složeniji izgled. Na primjer:

;
,

Gdje
su dati brojevi. Međutim, da ne bismo komplicirali prezentaciju, ograničavamo se na najjednostavniji oblik dodatnih uvjeta.

Koristeći činjenicu da su vrijednosti I dato, prepisujemo sistem u obliku:

Matrica ovog sistema ima tridijagonalnu strukturu:

Ovo uvelike pojednostavljuje rješenje sistema zahvaljujući posebnoj metodi koja se zove metoda sweep.

Metoda se zasniva na pretpostavci da su željene nepoznanice I
povezane relacijom recidiva

,
.

Evo količine
,
, koji se nazivaju koeficijenti sweep-a, određuju se na osnovu uslova problema, . U stvari, takav postupak znači zamjenu direktne definicije nepoznatih zadatak određivanja koeficijenata sweep-a sa naknadnim proračunom veličina .

Za implementaciju opisanog programa izražavamo pomoću relacije
kroz
:

i zamena
I , izraženo kroz
, u originalne jednadžbe. Kao rezultat, dobijamo:

.

Posljednji odnosi će svakako biti zadovoljeni i, štaviše, bez obzira na rješenje, ako se zahtijeva da se na
desile su se jednakosti:

Odavde slijede rekurzivne relacije za koeficijente sweep-a:

,
,
.

Lijevo granično stanje
i omjer
su dosljedne ako stavimo

.

Ostale vrijednosti koeficijenata sweep-a
I
nalazimo od, sa kojim i završavamo fazu izračunavanja koeficijenata sweep-a.

.

Odavde možete pronaći ostale nepoznanice
u procesu pomicanja unazad koristeći rekurzivnu formulu.

Broj operacija potrebnih za rješavanje općeg sistema korištenjem Gaussove metode raste s povećanjem proporcionalno . Metoda sweep-a se svodi na dva ciklusa: prvo se izračunavaju koeficijenti sweep-a pomoću formula, a zatim se pomoću njih komponente sistemskog rješenja pronalaze pomoću rekurentnih formula . To znači da kako se veličina sistema povećava, broj aritmetičkih operacija će rasti proporcionalno , ali ne . Stoga je metoda sweep-a u okviru svoje moguće primjene znatno ekonomičnija. Ovome treba dodati posebnu jednostavnost njegove softverske implementacije na računaru.

U mnogim primijenjenim problemima koji vode do SLAE sa tridijagonalnom matricom, njeni koeficijenti zadovoljavaju nejednakosti:

,

koji izražavaju svojstvo dijagonalne dominacije. Konkretno, takve sisteme ćemo sresti u trećem i petom poglavlju.

Prema teoremi iz prethodnog odjeljka, rješenje takvih sistema uvijek postoji i jedinstveno je. Oni također imaju izjavu koja je važna za stvarni proračun rješenja korištenjem metode sweep.

Lemma

Ako je za sistem sa tridijagonalnom matricom uslov dijagonalne dominacije zadovoljen, tada koeficijenti sweep-a zadovoljavaju nejednakosti:

.

Dokaz ćemo izvesti indukcijom. Prema
, ja jedem
tvrdnja leme je tačna. Pretpostavimo sada da je to tačno za i razmotriti
:

.

Dakle, indukcija iz To
opravdano, čime je završen dokaz leme.

Nejednakost za koeficijente sweep-a čini trčanje stabilnim. Zaista, pretpostavimo da je komponenta rješenja kao rezultat postupka zaokruživanja izračunava se sa određenom greškom. Zatim prilikom izračunavanja sljedeće komponente
prema rekurzivnoj formuli, ova greška se zbog nejednakosti neće povećati.

$|a\_(ii)|\; \backslash geqslant\; \backslash sum\_(j\; \backslash neq\; i)\; |a\_(ij)|,\backslash qquad\; i\; =\; 1,\; \backslash dots,\; n,$

i barem jedna nejednakost je stroga. Ako su sve nejednakosti stroge, onda se kaže da je matrica $A\_(nn)$ ima strog dijagonalna dominacija.

Matrice sa dijagonalnom dominacijom se često pojavljuju u aplikacijama. Njihova glavna prednost je u tome što iterativne metode za rješavanje SLAE s takvom matricom (jednostavna metoda iteracije, Seidelova metoda) konvergiraju do egzaktnog rješenja koje postoji i jedinstveno je za sve desne strane.

Svojstva

• Matrica sa strogom dijagonalnom dominacijom je nedegenerirana.

vidi takođe

Napišite recenziju na članak "Dijagonalna dominacija"

Odlomak koji karakterizira dijagonalnu prevlast