UNIWERSYTET PAŃSTWOWY W SANKT PETERSBURGU

Wydział Matematyki Stosowanej - Procesy Sterowania

A. P. IWANOW

WARSZTATY Z METOD NUMERYCZNYCH

ROZWIĄZYWANIE UKŁADÓW LINIOWYCH RÓWNAŃ ALGEBRAJNYCH

Wytyczne

Sankt Petersburg

ROZDZIAŁ 1. INFORMACJE POMOCNICZE

W poradnik metodyczny podano klasyfikację metod rozwiązywania SLAE oraz algorytmy ich stosowania. Metody przedstawiono w formie umożliwiającej ich stosowanie bez odwoływania się do innych źródeł. Zakłada się, że macierz układu jest nieosobliwa, tj. det A 6= 0.

§1. Normy wektorów i macierzy

Przypomnijmy, że przestrzeń liniową Ω elementów x nazywamy znormalizowaną, jeśli zawiera funkcję k · kΩ , która jest zdefiniowana dla wszystkich elementów przestrzeni Ω i spełnia następujące warunki:

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

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

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

W przyszłości zgodzimy się oznaczać wektory małymi literami łacińskimi i będziemy je uważać za wektory kolumnowe, macierze będziemy oznaczać dużymi literami łacińskimi, a wielkości skalarne będziemy oznaczać literami greckimi (zachowując oznaczenia liczb całkowitych za literami ja, j, k, l, m, n) .

Do najczęściej używanych norm wektorowych należą:

2. kxk2 = u x2 ; T

3. kxk∞ = maks |xi |.

Zauważmy, że wszystkie normy w przestrzeni Rn są równoważne, tj. dowolne dwie normy kxki i kxkj są powiązane przez:

αij kxkj ≤ kxki ≤ βij kxkj ,

k k ≤ k k ≤ ˜ k k

α˜ ij x ja x j β ij x ja,

ponadto αij , βij , α˜ij , βij nie zależą od x. Co więcej, w przestrzeni o skończonych wymiarach dowolne dwie normy są równoważne.

Przestrzeń macierzy z naturalnie wprowadzonymi operacjami dodawania i mnożenia przez liczbę tworzy przestrzeń liniową, w której pojęcie normy można wprowadzać na wiele sposobów. Najczęściej jednak uwzględnia się tzw. normy podrzędne, tj. normy powiązane z normami wektorów zależnościami:

Oznaczając podrzędne normy macierzy tymi samymi indeksami, co odpowiadające im normy wektorów, możemy stwierdzić, że

Tutaj λi (AT A) oznacza wartość własną macierzy AT A, gdzie AT jest macierzą transponowaną do A. Oprócz trzech głównych właściwości normy wymienionych powyżej, zauważamy tutaj jeszcze dwie:

kABk ≤ kAk kBk,

kAxk ≤ kAk kxk,

ponadto w ostatniej nierówności norma macierzowa jest podporządkowana odpowiedniej normie wektorowej. Umówmy się, że dalej będziemy używać tylko norm macierzy podporządkowanych normom wektorów. Zauważ, że dla takich norm zachodzi równość: jeśli E jest macierzą tożsamości, to kEk = 1, .

§2. Macierze z dominacją diagonalną

Definicja 2.1. Macierz A z elementami (aij )n i,j=1 nazywana jest macierzą z przewagą diagonalną (wartości δ), jeśli nierówności

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

§3. Macierze dodatnio określone

Definicja 3.1. Symetryczna macierz A zostanie wywołana

dodatnio określona, ​​jeśli postać kwadratowa xT Ax z tą macierzą przyjmuje tylko wartości dodatnie dla dowolnego wektora x 6= 0.

Kryterium pozytywnej określoności macierzy może być dodatniość jej wartości własnych lub dodatniość jej drugorzędnych głównych.

§4. Numer warunku SLAE

Wiadomo, że przy rozwiązywaniu dowolnego problemu występują trzy rodzaje błędów: błąd krytyczny, błąd metodologiczny i błąd zaokrąglenia. Rozważmy wpływ błędu krytycznego danych początkowych na rozwiązanie SLAE, pomijając błąd zaokrągleń i uwzględniając brak błędu metodologicznego.

macierz A jest dokładnie znana, a prawa strona b zawiera nieusuwalny błąd δb.

Następnie dla błędu względnego rozwiązania kδxk/kxk

gdzie ν(A) = kAkkA−1k.

Liczba ν(A) nazywana jest numerem warunku systemu (4.1) (lub macierzą A). Okazuje się, że zawsze ν(A) ≥ 1 dla dowolnej macierzy A. Ponieważ wartość numeru warunku zależy od wyboru normy macierzowej, przy wyborze określonej normy będziemy indeksować odpowiednio ν(A) ν1 ( A), ν2 (A) lub ν ∞(A).

W przypadku ν(A) 1 mówi się, że układ (4.1) lub macierz A jest źle uwarunkowany. W tym przypadku, jak wynika z kosztorysu

(4.2) błąd rozwiązania układu (4.1) może okazać się niedopuszczalnie duży. Pojęcie dopuszczalności lub niedopuszczalności błędu określa sformułowanie problemu.

W przypadku macierzy z dominacją diagonalną łatwo jest uzyskać górne oszacowanie jej liczby warunków. Występuje

Twierdzenie 4.1. Niech A będzie macierzą z dominacją diagonalną δ > 0. Wtedy jest nieosobliwa i ν∞ (A) ≤ kAk∞ /δ.

§5. Przykład źle uwarunkowanego systemu.

Rozważ SLAE (4.1) , w którym

Ten system ma unikalne rozwiązanie x = (0, 0, ..., 0, 1) T . Niech prawa strona układu zawiera błąd δb = (0, 0, ..., 0, ε), ε > 0. Wtedy

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

Stąd,

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

Skoro kAk∞ = n, to kA−1 k∞ ≥ n−1 2 n−2 , chociaż det(A−1 ) = (det A)−1 = 1. Niech np. n = 102. Wtedy ν( A) ≥ 2100 > 1030. Co więcej, nawet jeśli ε = 10−15 otrzymamy kδxk∞ > 1015 . A to nie jest

Definicja.

System nazywamy systemem z dominacją diagonalną wierszy, jeśli elementy macierzyspełnić nierówności:

,

Nierówności oznaczają, że w każdym rzędzie macierzy element przekątny jest podświetlony: jego moduł jest większy niż suma modułów wszystkich innych elementów tego samego rzędu.

Twierdzenie

System z dominacją diagonalną jest zawsze rozwiązywalny, a ponadto jest unikalny.

Rozważ odpowiedni system jednorodny:

,

Załóżmy, że ma nietrywialne rozwiązanie , Niech składnik tego rozwiązania, który ma największy moduł, odpowiada indeksowi
, tj.

,
,
.

Zapiszmy równanie układu w postaci

i weź moduł obu stron tej równości. W rezultacie otrzymujemy:

.

Zmniejszenie nierówności o czynnik
, która zgodnie z nie jest równa zeru, dochodzimy do sprzeczności z nierównością wyrażającą dominację diagonalną. Wynikająca z tego sprzeczność pozwala nam konsekwentnie stwierdzić trzy stwierdzenia:

Ostatni z nich oznacza, że ​​dowód twierdzenia jest zakończony.

1. Układy z macierzą trójdiagonalną. Metoda zamiatania.

Przy rozwiązywaniu wielu problemów mamy do czynienia z układami równań liniowych postaci:

,
,

,
,

gdzie współczynniki
, prawa strona
znany wraz z liczbami I . Dodatkowe relacje są często nazywane warunkami brzegowymi systemu. W wielu przypadkach mogą mieć bardziej złożony wygląd. Na przykład:

;
,

Gdzie
podane są liczby. Aby jednak nie komplikować prezentacji, ograniczamy się do najprostszej postaci dodatkowych warunków.

Korzystając z faktu, że wartości I podane, przepisujemy system w postaci:

Macierz tego układu ma strukturę trójdiagonalną:

To znacznie upraszcza rozwiązanie układu dzięki specjalnej metodzie zwanej metodą przemiatania.

Metoda opiera się na założeniu, że pożądane są niewiadome I
powiązane relacją rekurencyjną

,
.

Tutaj ilości
,
, zwane współczynnikami przemiatania, należy określić na podstawie warunków problemu, . W rzeczywistości taka procedura oznacza zastąpienie bezpośredniej definicji niewiadomych zadanie określenia współczynników odchylenia z późniejszym obliczeniem ilości .

Aby zrealizować opisany program, wyrażamy za pomocą relacji
Poprzez
:

i zastąpić
I , wyrażone przez
, do pierwotnych równań. W rezultacie otrzymujemy:

.

Te ostatnie relacje z pewnością będą spełnione, a ponadto niezależnie od rozwiązania, jeśli wymagane jest, aby o godz
doszło do równości:

Stąd postępuj zgodnie z rekurencyjnymi relacjami dla współczynników przemiatania:

,
,
.

Lewy warunek brzegowy
i stosunek
są spójne, jeśli umieścimy

.

Inne wartości współczynników przemiatania
I
znajdujemy, z którym i kończymy etap obliczania współczynników przemiatania.

.

Stąd możesz znaleźć resztę niewiadomych
w procesie wymiatania wstecznego przy użyciu formuły rekurencyjnej.

Liczba operacji wymaganych do rozwiązania ogólnego systemu za pomocą metody Gaussa rośnie wraz ze wzrostem proporcjonalnie . Metoda przemiatania jest zredukowana do dwóch cykli: najpierw obliczane są współczynniki przemiatania za pomocą wzorów, następnie za ich pomocą znajdowane są składniki rozwiązania systemowego za pomocą powtarzających się wzorów . Oznacza to, że wraz ze wzrostem rozmiaru systemu liczba operacji arytmetycznych będzie rosła proporcjonalnie , ale nie . Tym samym metoda omiatania w zakresie jej możliwego zastosowania jest znacznie bardziej ekonomiczna. Do tego należy dodać szczególną prostotę implementacji oprogramowania na komputerze.

W wielu zastosowanych problemach, które prowadzą do SLAE z macierzą trójdiagonalną, jej współczynniki spełniają nierówności:

,

które wyrażają właściwość dominacji diagonalnej. W szczególności z takimi systemami spotkamy się w rozdziałach trzecim i piątym.

Zgodnie z twierdzeniem z poprzedniej sekcji, rozwiązanie takich układów zawsze istnieje i jest unikalne. Zawierają również stwierdzenie, które jest ważne dla rzeczywistego obliczenia rozwiązania metodą wymiatania.

Lemat

Jeżeli dla układu z macierzą trójdiagonalną spełniony jest warunek dominacji diagonalnej, to współczynniki przemiatania spełniają nierówności:

.

Dowód przeprowadzimy przez indukcję. Według
, jem
twierdzenie lematu jest prawdziwe. Załóżmy teraz, że jest to prawdziwe dla i rozważyć
:

.

Więc indukcja od Do
uzasadnione, co kończy dowód lematu.

Nierówność dla współczynników przemiatania zapewnia stabilność biegu. Rzeczywiście, załóżmy, że składnik rozwiązania w wyniku procedury zaokrąglania jest obliczana z pewnym błędem. Następnie przy obliczaniu następnego składnika
zgodnie ze wzorem rekurencyjnym błąd ten ze względu na nierówność nie będzie się zwiększał.

NIEPOWTARZALNOŚĆ MATRYC I WŁASNOŚĆ DOMINACJI DIAGONALNEJ1

L. Cvetkovich, V. Kostic i L.A. Krzysiek

Cvetkovic Liliana - Profesor, Katedra Matematyki i Informatyki, Wydział Nauk, Uniwersytet w Nowym Sadzie, Serbia, Obradovica 4, Nowy Sad, Serbia, 21000, e-mail: [e-mail chroniony].

Kostic Vladimir - Adiunkt, Doktor, Katedra Matematyki i Informatyki, Wydział Nauk, Uniwersytet w Nowym Sadzie, Serbia, Obradovica 4, 21000, Nowy Sad, Serbia, email: [e-mail chroniony].

Krukier Lew Abramowicz - doktor nauk fizycznych i matematycznych, profesor, kierownik Katedry Wysokowydajnych Komputerów i Technologii Informacyjno-Komunikacyjnych, dyrektor Południowo-rosyjskiego Regionalnego Centrum Informatyzacji Południowego uniwersytet federalny, Stachki Ave. 200/1, bud. 2, Rostów nad Donem, 344090, e-mail: [e-mail chroniony]. ru.

Cvetkovic Ljiljana - Profesor, Katedra Matematyki i Informatyki, Wydział Nauk, Uniwersytet w Nowym Sadzie, Serbia, D. Obradovica 4, Nowy Sad, Serbia, 21000, e-mail: [e-mail chroniony].

Kostic Vladimir - Adiunkt, Katedra Matematyki i Informatyki, Wydział Nauk, Uniwersytet w Nowym Sadzie, Serbia, D. Obradovica 4, Nowy Sad, Serbia, 21000, e-mail: [e-mail chroniony].

Krukier Lew Abramowicz - doktor nauk fizycznych i matematycznych, profesor, kierownik Katedry Komputerów Dużej Wydajności i Technologii Informacyjno-Komunikacyjnych, dyrektor Centrum Komputerowego Południowego Uniwersytetu Federalnego, Stachki Ave, 200/1, bild. 2, Rostów nad Donem, Rosja, 344090, e-mail: [e-mail chroniony]. ru.

Dominacja diagonalna w macierzy wynosi prosty warunek, zapewniając jej niedegenerację. Właściwości macierzy, które uogólniają pojęcie dominacji diagonalnej, są zawsze bardzo poszukiwane. Są one uważane za warunki typu dominacji diagonalnej i pomagają zdefiniować podklasy macierzy (takie jak macierze H), które pozostają niezdegenerowane w tych warunkach. W tym artykule konstruujemy nowe klasy macierzy nieosobliwych, które zachowują zalety dominacji diagonalnej, ale pozostają poza klasą macierzy H. Te właściwości są szczególnie wygodne, ponieważ wiele zastosowań prowadzi do macierzy tej klasy, a teorię niezdegenerowania macierzy, które nie są macierzami H, można teraz rozszerzyć.

Słowa kluczowe: dominacja diagonalna, brak degeneracji, skalowanie.

Podczas gdy proste warunki, które zapewniają brak osobliwości macierzy, są zawsze mile widziane, wiele z nich, które można uznać za rodzaj dominacji diagonalnej, ma tendencję do tworzenia podklas dobrze znanych macierzy H. W tym artykule konstruujemy nowe klasy macierzy nieosobliwych, które zachowują przydatność dominacji diagonalnej, ale pozostają w ogólnym związku z klasą macierzy H. Ta właściwość jest szczególnie korzystna, ponieważ wiele zastosowań wynikających z teorii macierzy H można teraz rozszerzyć.

Słowa kluczowe: dominacja diagonalna, nieosobliwość, technika skalowania.

Numeryczne rozwiązanie problemów brzegowych fizyki matematycznej zwykle sprowadza pierwotny problem do rozwiązania układu liniowych równań algebraicznych. Wybierając algorytm rozwiązania, musimy wiedzieć, czy oryginalna macierz jest nieosobliwa? Ponadto kwestia niezdegenerowania macierzy jest istotna np. w teorii zbieżności metod iteracyjnych, lokalizacji wartości własnych, w szacowaniu wyznaczników, pierwiastków fartucha, promienia spektralnego, wartości osobliwych a matryca itp.

Zauważ, że jednym z najprostszych, ale niezwykle przydatnych warunków, które zapewniają niezdegenerowanie macierzy, jest dobrze znana właściwość ścisłej dominacji diagonalnej (i odniesienia do nich).

Twierdzenie 1. Niech będzie dana macierz A = e Cnxn taka, że

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

dla wszystkich i e N:= (1,2,...n).

Wtedy macierz A jest niezdegenerowana.

Macierze o własności (1) nazywane są macierzami o ścisłej dominacji diagonalnej

(macierze 8BB). Ich naturalnym uogólnieniem jest klasa macierzy z uogólnioną dominacją diagonalną (GBD), zdefiniowana następująco:

Definicja 1. Macierz A = [a^] e Cxn nazywamy macierzą sBB, jeśli istnieje nieosobliwa macierz diagonalna W taka, że ​​AW jest macierzą 8BB.

Wprowadzimy kilka definicji macierzy

A \u003d [ay] e Spxp.

Definicja 2

(A) = e Cn

nazywana jest macierzą porównawczą macierzy A.

Definicja 3. Macierz A = e C

\üj > 0, i = j

jest macierzą M, jeśli

aj< 0, i * j,

mata rewersyjna-

macierz A">0, czyli wszystkie jej elementy są dodatnie.

Oczywiście macierze z klasy wBB są również macierzami nieosobliwymi i mogą nimi być

1 Ta praca była częściowo wspierana przez Ministerstwo Edukacji i Nauki Serbii, grant 174019 oraz Ministerstwo Nauki i Rozwoju Technologicznego Wojwodiny, granty 2675 i 01850.

znaleźć w literaturze pod nazwą niezdegenerowanych macierzy H. Można je zdefiniować za pomocą następującego warunku koniecznego i wystarczającego:

Twierdzenie 2. Macierz A \u003d [ay ]e xi

macierz wtedy i tylko wtedy, gdy jej macierz porównań jest niezdegenerowaną macierzą M.

Do tej pory zbadano już wiele podklas niezdegenerowanych macierzy H, ale wszystkie z nich są rozpatrywane z punktu widzenia uogólnień właściwości ściśle diagonalnej dominacji (patrz także odniesienia tam).

W tym artykule rozważamy możliwość wyjścia poza klasę macierzy H poprzez uogólnienie klasy SBB w inny sposób. Główną ideą jest dalsze stosowanie podejścia skalowania, ale z macierzami, które nie są diagonalne.

Rozważ macierz A \u003d [ay ] e spxn i indeks

Wprowadzamy macierz

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

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

Łatwo sprawdzić, że elementy macierzy bk Abk mają następującą postać:

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

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

ja = k, j * k, ja * k, j = k,

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

Jeśli zastosujemy Twierdzenie 1 do opisanej powyżej macierzy bk Abk1 i jej transponowanej, to otrzymamy dwa główne twierdzenia.

Twierdzenie 3. Niech będzie dana macierz

A \u003d [ay ] e spxn z niezerowymi elementami ukośnymi. Jeśli istnieje k e N takie, że > ​​Rk (A), i dla każdego i e N \ (k),

wtedy macierz A jest niezdegenerowana.

Twierdzenie 4. Niech będzie dana dowolna macierz

A \u003d [ay ] e spxn z niezerowymi elementami ukośnymi. Jeżeli istnieje k e N takie, że > Jk (A), i dla każdego i e N \ (k),

Wtedy macierz A jest niezdegenerowana. Powstaje naturalne pytanie o związek między

macierze z dwóch poprzednich twierdzeń: L^ - BOO -macierze ( określone wzorem(5)) i

bk - macierze BOO (określone wzorem (6)) i klasa macierzy H. Poniższy prosty przykład wyjaśnia to.

Przykład. Rozważ następujące 4 macierze:

i rozważmy macierz bk Abk, k e N, podobną do oryginalnej A. Znajdźmy warunki, kiedy ta macierz będzie miała właściwość macierzy SDD (wierszami lub kolumnami).

W całym artykule dla r,k eN:= (1,2,.../?) będziemy używać notacji:

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

Twierdzenia o niedegeneracji

Wszystkie nie są zdegenerowane:

A1 to b - BOO, mimo że nie jest to bk - BOO dla dowolnego k = (1,2,3). Nie jest to również macierz H, ponieważ (A^1 nie jest nieujemne;

A2, ze względu na symetrię, to jednocześnie LH - BOO i L<2 - БОО, так же как ЬЯ - БОО и

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

A3 to b9 - BOO, ale nie jest żadnym z nich

Lr jest SDD (dla k = (1,2,3)), ani macierzą H, ponieważ (A3 ^ jest również zdegenerowany;

A4 jest macierzą H, ponieważ (A^ jest liczbą nieosobliwą, a ^A4) 1 > 0, chociaż nie jest ani LR - SDD, ani Lk - SDD dla dowolnego k = (1,2,3).

Na rysunku przedstawiono ogólną zależność między

Macierze Lr - SDD , Lk - SDD i H wraz z macierzami z poprzedniego przykładu.

Komunikacja między lR - SDD, lC - SDD i

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

Zaczynając od nierówności

i stosując ten wynik do macierzy bk ab ^, otrzymujemy

Twierdzenie 5. Niech będzie dana dowolna macierz A = [a--] e Cxn z niezerowymi elementami przekątnymi.

gliny. Jeśli A należy do klasy - BOO, to

1 + max^ i*k \acc\

macierze H

Warto zauważyć, że chociaż mamy

klasa macierzy LC BOO przez zastosowanie Twierdzenia 1 do macierzy otrzymanej przez transpozycję macierzy LC AL^1, klasa ta nie pokrywa się z klasą otrzymaną przez zastosowanie Twierdzenia 2 do macierzy Am.

Wprowadzamy definicje.

Definicja 4. Macierz A jest wywoływana ( bk -boo przez wiersze) jeśli AT ( bk -boo ).

Definicja 5. Macierz A jest wywoływana ( bsk -boo przez wiersze) jeśli AT ( bsk -boo ).

Przykłady pokazują, że klasy W - BOO,

bc-boo, (bk-boo po rzędzie) i (b^-boo po rzędzie) są ze sobą powiązane. W ten sposób rozszerzyliśmy klasę macierzy H na cztery różne sposoby.

Zastosowanie nowych twierdzeń

Zilustrujmy przydatność nowych wyników do szacowania C-normy macierzy odwrotnej.

Dla dowolnej macierzy A ze ścisłą dominacją przekątnej dobrze znane twierdzenie Varah (Varah) daje oszacowanie

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

Podobnie otrzymamy następujący wynik dla macierzy Lk - SDD według kolumn.

Twierdzenie 6. Niech dana jest dowolna macierz A = e xi o niezerowych elementach przekątnych. Jeśli A należy do klasy bk -SDD według kolumn, to

Ik-lll<_ie#|akk|_

" "mln[|pf(A)| - Rf (AT), mln(|уk (A)|- qk (AT)- |aft |)]"

Znaczenie tego wyniku polega na tym, że dla wielu podklas nieosobliwych macierzy H istnieją ograniczenia tego typu, ale dla tych nieosobliwych macierzy, które nie są macierzami H, jest to problem nietrywialny. Dlatego ograniczenia tego rodzaju, podobnie jak w poprzednim twierdzeniu, są bardzo pożądane.

Literatura

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

Horn RA, Johnson CR analiza macierzowa. Cambridge, 1994. Varga R.S. Gersgorin i jego kręgi // Seria Springera w matematyce obliczeniowej. 2004 Cz. 36.226 str. Berman A., Plemons R.J. Macierze nieujemne w naukach matematycznych. Klasyka serii SIAM w matematyce stosowanej. 1994 Cz. 9. 340 rubli

Cvetkovic Lj. Teoria macierzy H vs. lokalizacja wartości własnej // Liczba. algorytm. 2006 Cz. 42. s. 229-245. Cvetkovic Lj., Kostic V., Kovacevic M., Szulc T. Dalsze wyniki dotyczące macierzy H i ich uzupełnień Schura // Appl. Matematyka Oblicz. 1982. s. 506-510.

Varah J.M. Dolna granica dla najmniejszej wartości macierzy // Algebra liniowa Appl. 1975 Cz. 11. s. 3-5.

Otrzymał od redakcji

Definicja.

System nazywamy systemem z dominacją diagonalną wierszy, jeśli elementy macierzyspełnić nierówności:

,

Nierówności oznaczają, że w każdym rzędzie macierzy element przekątny jest podświetlony: jego moduł jest większy niż suma modułów wszystkich innych elementów tego samego rzędu.

Twierdzenie

System z dominacją diagonalną jest zawsze rozwiązywalny, a ponadto jest unikalny.

Rozważ odpowiedni system jednorodny:

,

Załóżmy, że ma nietrywialne rozwiązanie , Niech składnik tego rozwiązania, który ma największy moduł, odpowiada indeksowi
, tj.

,
,
.

Zapiszmy równanie układu w postaci

i weź moduł obu stron tej równości. W rezultacie otrzymujemy:

.

Zmniejszenie nierówności o czynnik
, która zgodnie z nie jest równa zeru, dochodzimy do sprzeczności z nierównością wyrażającą dominację diagonalną. Wynikająca z tego sprzeczność pozwala nam konsekwentnie stwierdzić trzy stwierdzenia:

Ostatni z nich oznacza, że ​​dowód twierdzenia jest zakończony.

1. Układy z macierzą trójdiagonalną. Metoda zamiatania.

Przy rozwiązywaniu wielu problemów mamy do czynienia z układami równań liniowych postaci:

,
,

,
,

gdzie współczynniki
, prawa strona
znany wraz z liczbami I . Dodatkowe relacje są często nazywane warunkami brzegowymi systemu. W wielu przypadkach mogą mieć bardziej złożony wygląd. Na przykład:

;
,

Gdzie
podane są liczby. Aby jednak nie komplikować prezentacji, ograniczamy się do najprostszej postaci dodatkowych warunków.

Korzystając z faktu, że wartości I podane, przepisujemy system w postaci:

Macierz tego układu ma strukturę trójdiagonalną:

To znacznie upraszcza rozwiązanie układu dzięki specjalnej metodzie zwanej metodą przemiatania.

Metoda opiera się na założeniu, że pożądane są niewiadome I
powiązane relacją rekurencyjną

,
.

Tutaj ilości
,
, zwane współczynnikami przemiatania, należy określić na podstawie warunków problemu, . W rzeczywistości taka procedura oznacza zastąpienie bezpośredniej definicji niewiadomych zadanie określenia współczynników odchylenia z późniejszym obliczeniem ilości .

Aby zrealizować opisany program, wyrażamy za pomocą relacji
Poprzez
:

i zastąpić
I , wyrażone przez
, do pierwotnych równań. W rezultacie otrzymujemy:

.

Te ostatnie relacje z pewnością będą spełnione, a ponadto niezależnie od rozwiązania, jeśli wymagane jest, aby o godz
doszło do równości:

Stąd postępuj zgodnie z rekurencyjnymi relacjami dla współczynników przemiatania:

,
,
.

Lewy warunek brzegowy
i stosunek
są spójne, jeśli umieścimy

.

Inne wartości współczynników przemiatania
I
znajdujemy, z którym i kończymy etap obliczania współczynników przemiatania.

.

Stąd możesz znaleźć resztę niewiadomych
w procesie wymiatania wstecznego przy użyciu formuły rekurencyjnej.

Liczba operacji wymaganych do rozwiązania ogólnego systemu za pomocą metody Gaussa rośnie wraz ze wzrostem proporcjonalnie . Metoda przemiatania jest zredukowana do dwóch cykli: najpierw obliczane są współczynniki przemiatania za pomocą wzorów, następnie za ich pomocą znajdowane są składniki rozwiązania systemowego za pomocą powtarzających się wzorów . Oznacza to, że wraz ze wzrostem rozmiaru systemu liczba operacji arytmetycznych będzie rosła proporcjonalnie , ale nie . Tym samym metoda omiatania w zakresie jej możliwego zastosowania jest znacznie bardziej ekonomiczna. Do tego należy dodać szczególną prostotę implementacji oprogramowania na komputerze.

W wielu zastosowanych problemach, które prowadzą do SLAE z macierzą trójdiagonalną, jej współczynniki spełniają nierówności:

,

które wyrażają właściwość dominacji diagonalnej. W szczególności z takimi systemami spotkamy się w rozdziałach trzecim i piątym.

Zgodnie z twierdzeniem z poprzedniej sekcji, rozwiązanie takich układów zawsze istnieje i jest unikalne. Zawierają również stwierdzenie, które jest ważne dla rzeczywistego obliczenia rozwiązania metodą wymiatania.

Lemat

Jeżeli dla układu z macierzą trójdiagonalną spełniony jest warunek dominacji diagonalnej, to współczynniki przemiatania spełniają nierówności:

.

Dowód przeprowadzimy przez indukcję. Według
, jem
twierdzenie lematu jest prawdziwe. Załóżmy teraz, że jest to prawdziwe dla i rozważyć
:

.

Więc indukcja od Do
uzasadnione, co kończy dowód lematu.

Nierówność dla współczynników przemiatania zapewnia stabilność biegu. Rzeczywiście, załóżmy, że składnik rozwiązania w wyniku procedury zaokrąglania jest obliczana z pewnym błędem. Następnie przy obliczaniu następnego składnika
zgodnie ze wzorem rekurencyjnym błąd ten ze względu na nierówność nie będzie się zwiększał.

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

i co najmniej jedna nierówność jest ścisła. Jeśli wszystkie nierówności są ścisłe, to mówi się, że macierz jest $A\_(nn)$ ma ścisły dominacja diagonalna.

Macierze z przewagą diagonalną dość często pojawiają się w aplikacjach. Ich główną zaletą jest to, że iteracyjne metody rozwiązywania SLAE z taką macierzą (prosta metoda iteracji, metoda Seidela) zbiegają się do dokładnego rozwiązania, które istnieje i jest unikalne dla każdej prawej strony.

Nieruchomości

• Macierz ze ścisłą dominacją diagonalną jest niezdegenerowana.

Zobacz też

Napisz recenzję artykułu „Dominacja diagonalna”

Fragment charakteryzujący przewagę diagonalną