Metody numeryczne fizyki/Algebraiczne sposoby rozwiązywania układów równań liniowych

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania
Metody numeryczne fizyki
Metody numeryczne fizyki
Algebraiczne sposoby rozwiązywania układów równań liniowych

Licencja
Autor: Mirosław Makowiecki
Absolwent UMCS Fizyki Komputerowej Uniwersytetu Marii Curie-Skłodowskiej w Lublinie
Email: miroslaw.makowiecki@gmail.com
Dotyczy: książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami.
Użytkownika książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami nie zwalnia z odpowiedzialności prawnoautorskiej nieprzeczytanie warunków licencjonowania.
Umowa prawna: Creative Commons: uznanie autorstwa oraz miejsca pochodzenia książki i jej jakikolwiek części, a także treści, teksty, tabele, wykresy, rysunki, wzory i inne elementy oraz ich części zawarte w książce, i tą książkę, nawet w postaci przerobionej nie można umieszczać w jakikolwiek formie na czasopismach naukowych, archiwach prac, itp.
Autor tej książki dołożył wszelką staranność, aby informacje zawarte w książce były poprawne i najwyższej jakości, jednakże nie udzielana jest żadna gwarancja, czy też rękojma. Autor nie jest odpowiedzialny za wykorzystanie informacji zawarte w książce nawet jeśli wywołaby jakąś szkodę, straty w zyskach, zastoju w prowadzeniu firmy, przedsiębiorstwa lub spółki bądź utraty informacji niezależnie, czy autor (a nawet Wikibooks) został powiadomiony o możliwości wystąpienie szkód. Informacje zawarte w książce mogą być wykorzystane tylko na własną odpowiedzialność.


Będziemy się tutaj zajmowali rozwiązaniem algebraicznych układów równań, które możemy przedstawić w postaci macierzowej , gdzie jest macierzą o m wierszach i n kolumnach, a jest wektorem o n-niewiadomych, i jest wektorem o n wyrazach wolnych. Jeśli z tego równania macierzowego wyznaczymy wektor niewiadomych, to możemy wyznaczyć ten wektor znając macierz i macierz wyrazów wolnych. Jest to ścisły sposób wyznaczania wektora niewiadomych. Istnieją też numeryczne metody takiego wyznaczania wektora niewiadomych, które poniżej przedstawimy.

Wprowadzenie do pojęcia normy[edytuj]

Weźmy sobie przestrzeń , którego elementami są wektory pionowe , wtedy możemy wprowadzić poszczególne normy inaczej zdefiniowane stosowanych w obliczeniach numerycznych:

(5.1)
(5.2)
(5.3)

Normy (5.1), (5.2) i (5.3) spełniają warunki poniżej dla dowolnego wektora należącego do n-wymiarowej przestrzeni rzeczywistej, które to piszemy:

(5.4)

Określmy teraz macierz o m wierszach i n kolumnach, która może być traktowana jako operator przekształcający wektor należącej do n-wymiarowej przestrzeni rzeczywistej na m-wymiarową przestrzeń rzeczywistą, wtedy możemy określić normę tej naszej omawianej macierzy :

(5.5)

Symbole "p" i "q" oznaczają normy przedstawione w punktach (5.1), (5.2) i (5.3), dla którego definicja normy macierzy jest przedstawiona w punkcie (5.5). Zdefiniujmy teraz trzy kolejne normy macierzy, podobne do definicji norm wektora (5.1), (5.2) i (5.3), tylko że ich definicje wyglądają:

(5.6)
(5.7)
(5.8)

A także zdefiniujmy jako największa wartość własną macierzy . Wszystkie powyższe normy operatora możemy obliczyć łatwo numerycznie, tylko jest trudne do obliczenia. Przestrzeń z normą ||⋅||2 używa sie go w eulkidesowej normy macierzy, które często są zwane normami Schura lub normami Frobeniusza, którego definicja jest:

(5.9)

wtedy możemy napisać warunek zgodności dla n-wymiarowej przestrzeni rzeczywistej, do których należą elementy , zatem:

(5.10)

Dla dowolnej macierzy możemy powiedzieć, że zachodzi warunek, który jest zawsze prawdziwy:

(5.11)

Dla dowolnych dwóch macierzy i dla dowolnej definicji normy możemy napisać twierdzenie dla dowolnych indeksów p,q,r, która jest również słuszna dla dowolnej normy:


(5.12)

Również możemy powiedzieć z definicji macierzy podobnych, że normy macierzy podobnych mają równe wartości. Można też udowodnić, że jeśli λi jest jedną z wartości własnych macierzy , która może być również wartością zespoloną przy zdefiniowanej macierzy kwadratowej z pewną normą wektora nałożoną na macierz , to możemy napisać:

(5.13)

Wykorzystując definicję normy możemy napisać wniosek przy pomocy normy zdefiniowanej na macierzy wykorzystując twierdzenia (5.12):

(5.14)

Zdefiniujemy teraz dwa lematy, który są dla nas ważne wykorzystując niektóre dowodu napisane powyżej:

Lemat pierwszy
Jeśli norma macierzy spełnia warunek , to macierz jest macierzą nieosobliwą spełniającej warunek dla p=1,2,∞ przy jako macierzy jednostkowej:
(5.15)

Dowód
Jeśli macierz byłaby macierzą osobliwą, to wtedy dla niezerowego powinno być spełnione , to wtedy z definicji normy powinien być spełniony warunek:
(5.16)

stąd dla dowolnej macierzy warunek (5.18) z warunkiem lematu nie jest spełniony, stąd otrzymaliśmy sprzeczność. Z definicji elementu odwrotnego możemy powiedzieć:

(5.17)

Z obliczeń napisanej w punkcie (5.17) możemy napisać następujący wniosek:

(5.18)

Maksymalna wartość wartości własnej nazywamy promieniem spektralnym macierzy A i na podstawie wzoru (5.15) piszemy:

(5.19)
Lemat drugi
Dla każdej macierzy i dla liczby ε istnieje indukowana norma dla której zachodzi:
(5.20)

Dowód
Niech λ będzie jedną z największej wartości własnej, wtedy z definicji norm podanej powyżej dla macierzy zdiagonalizowanej, ta norma jej jest równa wartości własnej największej rozważanej macierzy, co stąd jeśli jest macierzą diagonalną, to możemy napisać z transformacji macierzy podobnych , to możemy powiedzieć:
(5.21)

Przeprowadźmy teraz dowód poprzez zaprzeczenie. Załózmy, że , wtedy da się wybrać takie k, by nierówność (5.21) była niespełniona, zatem . Analogicznie do (5.21) da się napisać tożsamość przy tym samym k:

(5.22)
Co przeprowadzając w dowodzie poprzez zaprzeczenie takie same wywody co dla (5.21) dochodzimy do wniosku , wtedy łącząc te dwie nierówności otrzymujemy, że normy macierzy podobnych są sobie równe.
Twierdzenie drugie
Ciąg wektorów jest zbieżny do zera, wtedy i tylko wtedy gdy promień spektralny macierzy jest mniejszy od jedynki.
Dowód
Udowodnijmy powyższe twierdzenie poprzez zaprzeczenie, zatem jeśli powyższy ciąg dąży zera, i promień spektralny jest większy lub równy niż zera, to powinno zachodzić na podstawie (5.21):
(5.23)

Ponieważ według (5.23) ciąg zależny od "i" dąży do zera i jednocześnie jest większy lub równy dla dowolnego , stad mamy sprzeczność. Udowodnijmy teraz twierdzenie odwrotne, jeśli ciąg jest rozbieżny od zera i promień spektralny jest mniejszy od zera dla dowolnie małego ε, to na podstawie wzoru (5.20) powiemy:

(5.24)
Stąd jeśli rozważany ciąg jest zbieżny do zera według obliczeń (5.24), to nie jest jednocześnie rozbieżny, stąd sprzeczność, więc udowodniane twierdzenie jest prawdziwe.

Błędy rozwiązań układów równań algebraicznych[edytuj]

Przypadek pierwszy

Weźmy sobie zamiast i wielkości i , wtedy równanie macierzowe możemy zapisać przy wzorem:

(5.25)

Dla dowolnej normy wektora zaburzenia zapisany przy pomocy normy macierzy dla równania macierzowego możemy zapisać , wtedy względne zaburzenie wielkości możemy zapisać przez względną zmianę wielkości , co daje nam w rezultacie przy oznaczeniu wielkości k:

(5.26)

wtedy w (5.26) zachodzi równość tylko dla ściśle określonego , a nierówność słaba dla , który należy od n-wymiarowej przestrzeni rzeczywistej. Jeśli skorzystamy z rozważanego równania macierzowego, wtedy definicję na czynnik "k" możemy przepisać w formie niezależącego od wektora zmiennych w postaci pewnej nierówności:

(5.27)

Liczbę Kpq będziemy nazywać wskaźnikiem uwarunkowania równania macierzowego , który symbolizuje pewien układ równań.

Przypadek drugi

Niech dalej i , wtedy możemy napisać:


(5.28)

Z obliczeń przeprowadzonych w punkcie (5.28) dochodzimy do wniosku przy odpowiedniej definicji k, że zachodzi:

(5.29)

Określmy jaka jest graniczna wartość współczynnika wzmocnienia k0, jako wielkości granicznej współczynników k określonych we wzorze (5.28) jako czynnik, takiego że zachodzi równość (5.29) dla ściśle określonego , która dla każdej tej wielkości zachodzi w ogólności nierówność słaba, takiego że:

(5.30)

gdy zachodzi δ→0. Teraz będziemy wyznaczać oszacowanie wielkości k0, które wyznaczymy poniżej Weźmy sobie do rozważenia równość, którą jest tożsamościowo równa zero, i ją zapisujemy sposobem: . Weźmy sobie wektor , który przepiszemy w postaci:. Mając sobie funkcję , to wtedy na podstawie różniczki zupełnej tejże funkcji możemy powiedzieć:

(5.31)

wtedy możemy napisać wielkość , która jest macierzą nieosobliwą, a , zatem po wykorzystaniu tożsamości na i na , wtedy różniczkę wielkości możemy przepisać w następującej formie:

(5.32)

Z definicji normy możemy napisać oszacowanie czynnika stojącego przy występującego we wzorze (5.32):

(5.33)
stąd możemy napisać oszacowanie wielkości poprzez wielkość , zatem:
(5.34)

Czynnik stojący przy k0 możemy wyrazić przy pomocy definicji normy wektora (5.1), a także normy macierzy (5.8) w sposób , a k0 oblicza się jako iloczyn norm macierzy macierzy A i jego odwrotności przy normie (5.8), który jest iloczynem maksymalnych wartości modułów elementów macierzowych macierzy A i jego odwrotności.

Przypadek trzeci

Weźmy sobie, że różniczki wyrazów wolnych i macierzy , które są nierówne zero, a macierz jest macierzą nieosobliwą, wtedy:


(5.35)

Względny błąd wielkości możemy napisać po wykorzystaniu równania macierzowego , którą wykorzystamy do wyliczenia nierówności drugiej poniżej występującego w nawiasie po prawej stronie jako drugi czynnik w pierwszym składniku, które jest zawsze mniejsze od jedynki według dowodu , a także z małości zaburzenia będziemy mogli zapisać , w takim razie:




(5.36)

Układy równań algebraicznych o trójkątnej macierzy[edytuj]

Weźmy sobie układ równań, w której wszystkie wyrazy na diagonalnej są różne od zera, to możemy wyznaczyć zmienną wykonując małą liczbę działań arytmetycznych i dla małych błędów zaokrągleń przy wyznaczaniu poszczególnych elementów wspomnianego wektora, zatem ten nasz układ równań piszemy:

:a11x1+a12x2+...+a1nxn=b1
...........a22x2+...+a2nxn=b2
........................................
............................annxn=bn
(5.37)

Poszczególne elementy zmiennych xk możemy policzyć z poniższych wzorów:



(5.38)

Patrząc na powyższy układ równań można powiedzieć, że dla i=n jest wykonywane jedno dzielenie lub mnożenie, a dla i=n-1 jest wykonywane jedno mnożenie i jedno dzielenie, czyli dwa mnożenia i dzielenia, a przy x1 jest wykonywanych n dzieleń i mnożeń, wtedy ilość dzieleń i mnożeń jest:

(5.39)

Dla układu rozwiązań xi (5.34) dla xn mamy zero dodawań i odejmowań, dla xn-1 mamy jedno dodawanie lub odejmowanie, dla x1 mamy n-1 dodawań lub odejmowań, zatem liczba wszystkich dodawań lub odejmowań jakie należy wykonać jest:

(5.40)

Jeśli będziemy wykonywali działania na komputerze, jeśli nie możemy wsadzić w miejsce wektora wektora , to liczba komórek zajętych dla i=n jest 3, dla i=n-1 jest 4, i idać dalej dochodzimy aż do i=1 jest n+2 zajętych komórek pamięci, zatem liczba wszystkich komórek zajętych jest:

(5.41)

Wzory (5.38) możemy napisać z odpowiednim przybliżeniem uwzględniając, że wielkości xi i bi są napisane z pewnym zaokrągleniem:

(5.42)

Powyższa macierzowa "nierówność" stanowi układ 1+2+3+..+n=n(n+1)/2 nierówności. Z powyższego oszacowania możemy wyedukować, że dla dowolnej normy p=1,∞,E spełniona jest zawsze nierówność:

(5.43)

Jeśli wiadomo, że oszacowanie elementów macierzy z definicji normy ||⋅||1∞ od góry jest , wtedy macierz błędu z normą ||⋅||1 i ||⋅|| możemy przepisać:

(5.44)
(5.45)

Wprowadźmy definicję macierzy A diagonalnie dominującej, których moduły elementów na diagonali są większe od sumy elementów macierzy stojącej w danym wierszu bez elementu na diagonali. Jest to macierz spełniającej warunek dla i=1,2,...,n:

(5.46)

Macierzą silnie diagonalnie dominującą nazywamy taką macierz A o stopniu n, w której w (5.46) występuje nierówność ostra. Macierz (silnie) diagonalnie dominująca kolumnowo nazywamy macierz, dla której AT jest (silnie) diagonalnie dominująca, tzn. gdy spełniony jest warunek dla i=1,2,...,n:

(5.47)

Macierz A generowana przez (5.37) nazywamy diagonalnie dominującą, gdy spełniony jest warunek pierwszy poniżej, a także ta macierz jest diagonalnie dominująca kolumnowo, gdy spełniony jest drugi warunek poniżej:

(5.48)
(5.49)

Rozwiązania równań liniowych metodą eliminacji Gaussa[edytuj]

Będziemy rozwiązywać układ równań liniowych z pełną macierzą , i doprowadzać ten układ równań do postaci trójkątnej, czyli przy wykorzystaniu równań (5.38), by później obliczyć jej poszczególne zmienne. Na sam początek określmy równanie macierzowe , które możemy przepisać w postaci układu równań:



..........................................................

(5.50)

Odejmijmy i-te równanie i>1 od pierwszego równania pomnożonego przez układu równań (5.46), w ten sposób otrzymujemy równanie macierzowe , co po rozpisaniu jego na układ równań, otrzymujemy:



..........................................................

(5.51)

W powyższych równaniu wyeliminowaliśmy zmienną x1 dla równania o numerze więcej niż pierwszy. Idąc dalej tym sposobem od równania i>2 odejmujemy od równania drugiego pomnożonej przez , w ten sposób otrzymujemy układ macierzowy . Dokonując tą metodę dalej według schematu podanego powyżej otrzymujemy na samym końcu równanie macierzowe , które zapisujemy w postaci układu równań:



..........................................................

(5.52)

W uzyskanym układzie równań (5.52) rozwiązujemy xi metodą (5.38) dla macierzy trójkątnej. Liczba mnożeń i dzieleń jakie należy wykonać dla układu równań (5.50), by uzyskać macierz trójkątna dla układu równań (5.48) jest w ilości kroków:


(5.53)

Powyższy rozwiązanie należy uzyskać, jeśli dla pierwszego kroku należy wykonać dzielenie , które jest jedno, i wymnożenie jej przez n wyrazów pierwszego równania układu równań (5.50) poczynając od drugiego (bo pierwszy składnik chociaż jest wymnażany przez tą liczbę, ale tylko służy do wyzerowania pierwszego składnika w równania drugiego), tych dzieleń i mnożeń w sumie jest n+1, dla i=2,..,n, to aby przejść do układu równań (5.51) należy wykonać dodawań i mnożeń w ilości (n+1)(n-1), aby przejść od układu równań oznaczonej "i" na do i+1 należy wykonać działań (n+1-i)(n-1-i), czyli w sumie mamy takich naszych działań (5.53). Liczba dodawań i dzieleń jakie układ musi wykonać by układ (5.50) doprowadzić do postaci trójkątnej jest:


(5.54)

Powyższe rozwiązanie możemy uzyskać, gdy dla pierwszego układu równań przejdziemy do drugiego układu równań, to wtedy należy wykonać n(n-1) działań, to aby przejść z układu równań i-tego do i+1-ego, to należy wykonać (n-i)(n-1-i) dodawań, odejmowań, zatem całkowita ilość dodawań i odejmowań aby układ był w postaci trójkątnej jest uzyskana równaniem (5.54). Powyższy sposób przeprowadziliśmy bez ujawniania jawnego operacji macierzowych, tylko powiedzieliśmy co dokonaliśmy na poszczególnych równaniach, do tego problemu podejdźmy z innej strony, tzn. za pomocą operacji macierzowych, aby przejść do równoważnych równań macierzowych z do , to pierwsze z tych równań macierzowych należy pomnożyć obustronnie lewostronnie przez macierz:

(5.55)

Przy pomocy macierzy podanej w podpunkcie (5.55) możemy pomnożyć początkowe równanie macierzowe lewostronnie , w ten sposób uzyskując równanie macierzowe . By otrzymać równość macierzową , to drugie równanie macierzowe należy pomnożyć obustronnie lewostronnie przez macierz:

(5.56)

Macierz końcową , która jest macierzą trójkątną, to by go otrzymać należy macierz wymnożyć lewostronnie przez macierze , gdzie i=2,3,..n, a także to samo robimy uzyskując wektor wyrazów wolnych , co je napiszemy w jednej linijce:

(5.57)
(5.58)

Ponieważ macierze są macierzami nieosobliwymi, wtedy możemy równanie (5.57) równoważnie zapisać na w sposób:

(5.59)

Można udowodnić, że odwrotności macierzy (5.55) i (5.56), czyli macierze i , zapisujemy w formie:

(5.60)
(5.61)

Możemy również powiedzieć, że iloczyn odwrotności macierzy dla i=1,...,n-1 możemy zapisać przy pomocy liczb lij w formie:

(5.62)

Oznaczmy macierz oznaczoną (5.62) przez , a macierz przez , wtedy wyrażenie macierzowe (5.59) zapisujemy jako:

(5.63)

Macierz przedstawiona powyżej jest macierzą trójkątną dolną. Równanie macierzowe zapisujemy w formie , co można zapisać po przekształceniu , co jest równoważne rozwiązaniu układu równań macierzowych i , z których będziemy szukali rozwiązania . Jeśli znamy macierz LU, to ilość mnożeń jakich należy dokonać przy wyznaczeniu wektora "x" jest wyrażona przez , a ilość dodawań jakie musimy dokonać jest napisana przez .

Wyznaczanie macierzy L i U, a metoda Doolittle'a[edytuj]

Równanie macierzowe (5.63) możemy przepisać w postaci rozwiniętej w takiej postaci, tzn. w której napiszemy zamiast symboli macierzy wchodzących w skład tego równania ich postać rozwiniętą obrazująca poszczególne ich elementy:

(5.64)

Jeśli popatrzymy na równość macierzową (5.64) i wykonamy działanie w lewej jego stronie, to otrzymamy równość skalarną na elementy aij w których chcemy wyznaczyć lij i uij:

(5.65)

Równość (5.64) możemy przetransponować obustronnie, tzn. zamieniając wiersze z kolumnami, co w końcu otrzymujemy równość macierzową:

(5.66)

Mając do dyspozycji równość macierzową (5.66) możemy go przepisać ujmując poszczególne jej elementy dla j=i+1,i+2,...,n:

(5.67)

Ilość mnożeń w równaniach (5.65) i (5.67) jest wyrażona , a liczba dodawań w tych samych równaniach co poprzednio jest . Znając ile należy dokonać działań aby wyznaczyć wektor "x", gdy znamy macierz LU, to dodając te ilości do poprzednich M i D otrzymujemy liczbę dodawań i mnożeń taką samą jak przy metodzie Gaussa, tzn. ostateczną ilość mnożeń jaką musimy dokonać przy wyznaczeniu macierzy L i U, a potem do wyznaczania wektora "x" jest napisana , a liczba dodawań .

Zastosujmy zmodyfikowaną metodę eliminacją zwaną również częściowym wyborem elementu podstawowego. W tej metodzie elementem podstawowym nazywamy taki element macierzy A przy pomocy której eliminujemy zmienną w pozostałych równaniach. Te elementy zwykle przyjmuje się jako elementy diagonalne macierzy podstawowych A(k), gdzie k=1,2,..,n. Te elementy wybieramy w taki sposób by one leżały w k-tek kolumnie w k-tego macierzy, by ten elementem miał największy moduł w stosunku do pozostałych elementów w danym wierszu macierzy A, co można je uzyskać poprzestawiając poszczególne wiersze w macierzy A, by później leżały one na diagonali, oczywiste jest, że również musimy jednocześnie przedstawiać wiersze wektorów x i b. Ta wersja algorytmu Gaussa z częściowym wyborem elementy częściowego nazywamy metodą Gaussa-Crouta, którą w dalszym ciągu będziemy nazywać metodą GCW. Ta metoda gwarantuje, że proces poszukiwania x nie zatrzyma się na dzieleniu przez zero przy założeniu nieosobliwości macierzy A.

Błędy przybliżeń w metodzie Gaussa i Doolittle'a[edytuj]

Obie metody tutaj rozważane są ze sobą równoważne numeryczne o tej samej precyzji, aby wyznaczyć wektor "x" należy wyznaczyć macierz metodą Gaussa lub metodą Doolittle'a, a następnie znaleźć wektor "y" w równaniu macierzowym , i dalej wyznaczyć "x" w równaniu . Ponieważ macierze L i U są napisane z pewnym zaokrągleniem, to błąd zaokrąglenia LU napiszmy przez E, która jest błędem rozkładu i wtedy możemy powiedzieć . Znając błędu rozkładu L i U możemy napisać równości i , co na podstawie tego możemy powiedzieć
(5.68)

Z równości (5.68) możemy wyznaczyć błąd zaokrągleń macierzy A wiedząc jakie jest błąd zaokrąglenia macierzy E, zatem:

(5.69)

Jeśli będziemy przyjmować , to oszacowanie błędu macierzy LU dla poszczególnych jego elementów jest |eij|≤3,01εngij. Normy błędu zaokrągleń macierzy LU w metodzie GCW, pamiętając przy okazji , że g jest to największy moduł elementów macierzy określamy według:

(5.70)
(5.71)

W przypadku metody GCW wielkość g spełnia nierówność g≤2n-1||A||1∞, ale jak się okazuje, że dobrym ograniczeniem dla g od góry jest nierówność , a ponadto zachodzą również warunki , , wtedy na podstawie (5.70) i (5.71) można przejąć względne błędy macierzy A według oszacowań:

(5.72)
(5.73)

Jeśli dodatkowo uwzględnimy, że moduł poszczególnych elementów macierzy L jest mniejszy lub równy jeden, wtedy normy błędów macierzy L przepisujemy w formie:

(5.74)
(5.75)

A ilorazy błędu U przez jakąś normę A możemy przepisać w formie zależnego od stopnia n macierzy i zmiennej dowolnej ε:

(5.76)
(5.77)

Z definicji normy ||⋅||1 i ||⋅|| możemy napisać oszacowania dla norm macierzy U i L przy definicji parametru g i stopnia wspomnianych macierzy, które zapisujemy w formie ||U||1≤ng, ||U||≤ng, ||L||≤n, wtedy norma błędu bezwzględnego zaokrąglenia macierzy A według powyższych uwag przedstawiamy jako:


(5.78)

Jeśli popatrzymy na wzór (5.36) i oznaczymy , a także oznaczymy , a , wtedy błąd względny wektora x jest napisany według nierówności:

(5.79)

Podamy teraz twierdzenie opisującą eliminację metody GCW.

Twierdzenie
Dla macierzy A, która jest nieosobliwa i jest diagonalnie dominująca kolumnowo, to w metodzie eliminacji GCW nie musimy przedstawiać wierszy.
Dowód
Załóżmy, że wyeliminowaliśmy N wierszy, a pozostałe o numerach kolumny N+1,N+2,..,n tworzą macierz diagonalnie dominująco kolumnowo. Dla macierzy poszczególne elementy macierzy L możemy napisać jako dla k=2,3,..,n, przy której z definicji macierzy diagonalnie dolinującej kolumnowo (5.47) możemy napisać warunek . Elementy o numerach w wierszu 2,3,..,n możemy przepisać w formie dla numerów kolumn k=2,3,..,n. Dla macierzy A(2) elementy macierzy spełniają warunek na diagonali , a elementy leżące poza diagonalą spełniają warunek . Z definicji macierzy, diagonalnie dominująco kolumnowo (5.47) i powyższych rozważań, możemy napisać nierówność:
(5.80)
Z właśności, jeśli macierz A(1) jest diagonalnie dominująca kolumnowo, to macierz A(2) jest diagonalnie dominująca kolumnowo, ogólnie rzecz biorąc macierz A(k) dla k=1,2,..,n jest macierzą diagonalnie dominująca kolumnowo.

Rozwiązania równań liniowych metodą eliminacji Jordana (metodą eliminacji zupełnej)[edytuj]

Weźmy sobie układ równań, który przedstawimy w postaci macierzowej , który możemy rozbić na n równań odpowiadających temu równaniu macierzowemu:



........................................................

(5.81)

Pierwsze równanie układu równań (5.81) dzielimy obustronnie przez , a następnie od i-tego wiersza odejmujemy pierwszy wiersz pomnożonej przez , wtedy otrzymujemy następny układ równań, który zapisujemy w formie macierzowym rozpisując je w postaci n równań liniowych:



...........................................

(5.82)

Po (n-1) dokonanych eliminacjach otrzymujemy n równań algebraicznych linowych równoważnych równaniu (5.81), z których w sposób bardzo łatwy możemy policzyć niewiadome występujące w poniższym równaniu:



..............................................

(5.83)

Metoda eliminacji Jordana wymaga mnożeń i dodawań Jak widzimy, że metoda eliminacji Jordana wymaga około półtora więcej operacji niż metoda eliminacji Gaussa. Aby w tej metodzie nie nastąpiło dzielenie przez zero należy dokonać odpowiedni wybór elementu podstawowego.

Rozkład macierzy symetrycznej A na LDLT i LLT[edytuj]

Weźmy sobie macierz kwadratową symetryczną , którą rozłożymy na iloczyn dwóch macierzy , która jest macierzą dolną trójkątną z jedynkami na diagonali i macierzy , czyli , wtedy łatwo uzyskać rozkład macierzy symetrycznej w postaci , a macierz jest macierzą diagonalną o elementach na diagonali macierzy , a jest macierzą górną trójkątną, która jest macierzą na diagonali z jedynkami. Ponieważ jest macierzą symetryczną, to również dobrze można napisać , a także , co stąd oczekujemy, że wyjdzie , zatem dla macierzy symetrycznych spełniony jest związek:

(5.84)

Z równania (5.84) możemy powiedzieć d1=a11, a także możemy otrzymać dwa równania na lij i di dla i=2,3,..,n, i j=1,2,..,i-1 przy definicji cij=djlij , takiego że:

(5.85)
(5.86)

W celu wyznaczenia rozkładu (5.84) należy dokonać mnożeń i dodawań. Układ równań opisanej przez równanie macierzowe przy definicji macierzy (5.84) możemy rozłożyć na układ trzech równań macierzowych:

(5.87)

Ponieważ macierz jest macierzą symetryczną, znając dolną część macierzy wraz z wyrazami na diagonali zużyje nam komórek pamięci komputera.

Znamy jeszcze inny rozkład macierzy , która jest zwana rozkładem Banachiewicza, która jest również zwana rozkładem Cholesky'ego:

(5.88)

Zakładamy, że zachodzi tożsamość , co z oczywistych powodów możemy napisać równoważnie dla (5.88) , ale jest macierzą trójkątną dolną niekoniecznie z jedynkami na diagonali. Wzory na lii i lij dla i=1,2,..,n i dla j=i+1,i+2,..,n piszemy:

(5.89)
(5.90)

Dla spełnionej pierwszej równości (5.89) liczby lij mają ograniczoną wartość dla ograniczonych elementów aij. Błąd zaokrągleń Banachiewicza rozkładu LLT dla macierzy A piszemy , wtedy błąd ograniczenia na tą wielkość piszemy przez:

(5.91)
(5.92)

Równanie macierzowe z macierzą trójdiagonalną[edytuj]

Weźmy sobie równanie , w którym macierz jest macierzą trójdiagonalną napisaną na w sposób:

(5.93)

Macierz można rozłożyć na iloczyn dwóch macierzy i , czyli na , które mają specyficzny wygląd:

(5.94)
(5.95)

Wyznaczmy iloczyn macierzy (5.94) i (5.95), co w rezultacie po krótkich obliczeniach otrzymujemy:

(5.96)

Patrząc na obliczenia (5.96) i porównując ten wynik z (5.93), to możemy podać ogólny wynik na li i ui, który podajemy w postaci przepisu:

(5.97)
(5.98)
(5.99)

Mamy sobie równanie macierzowe , który po rozkładzie macierzy na iloczyn dwóch czynników macierzowych (5.94) i (5.95) zapisując jako równanie , który rozbijemy na dwa równania, tzn. na i , z których pierwsze równanie rozpiszemy w postaci równania yi jako:

(5.100)
(5.101)

a drugie równanie macierzowe rozpisujemy na element xi w zależności od zmiennej yi i xi+1 i ui:

(5.102)
(5.103)

Gdy jest macierzą diagonalnie dominująca kolumnowo, tzn. gdy zachodzą warunki: |b1|≥|a2|, |bi|≥|ci-1|+|ai+1| dla i=2, 3,..,n-1, |bn|≥|cn-1|, to ten nasz rozkład jest oparty z częściowych wyborem elementu podstawowego, a więc jest metodą niezawodną, tzn. przy niej nie występuje dzielenie przez zero. Natomiast, gdy macierz jest macierzą diagonalnie dominująca, tzn. gdy zachodzą nierówności: |b1|≥|c1|, |bi|≥|ai|+|ci| dla i=2,3,..,n-1, |bn|≥|an|, to również metoda eliminacji Gaussa w tym przypadku jest niezawodna.

Weźmy sobie inny rozkład macierzy na iloczyn dwóch czynników, które te macierze są zdefiniowane w formie:

(5.104)
(5.105)

Policzmy teraz iloczyn macierzy (5.104) i (5.105), który napiszemy według przepisu:


(5.106)

Patrząc na obliczenia (5.106) i porównując ten wynik z (5.93), to możemy podać ogólny wynik na li i ui, który podajemy w postaci przepisu:

(5.107)
(5.108)
(5.109)

Mamy sobie równanie macierzowe , który po rozkładzie macierzy na iloczyn dwóch czynników macierzowych (5.104) i (5.105) zapisując jako równanie , który rozbijemy na dwa równania, tzn. na i , z których pierwsze równanie rozpiszemy w postaci równania yi dla i=1,2,..,n-1 jako:

(5.110)
(5.111)

a drugie równanie macierzowe rozpisujemy na element xi w zależności od zmiennej yi i xi+1 i ui dla i=n-1,n-2,..,1:

(5.112)
(5.113)

Będziemy szukali błędów zaokrągleń przy liczeniu macierzy , którą liczymy ze wzoru . Błąd zaokrągleń będziemy liczyli w naszym przypadku ze wzoru , wtedy dla p=1,∞ możemy napisać ||E||p≤2ε||T||p. Jeśli natomiast (LL)y=d i (UU)x=y, wtedy powiemy: ||δL||p≤3ε, ||L||p≤2ε, a także zachodzą ||δU||p≤3ε||T||p i ||U||p≤2ε||T||p. Jeśli oznaczymy (AA)x=d, i ||δT||p≤14ε||T||p przy definicji ||A-1||p||A||p=Kp dla p=1,∞, a także wprowadzimy oznaczenie na parametr α=14εKp, wtedy wzór (5.36) przyjmuje taki sam wygląd jak wzór (5.79).

Równanie macierzowe z macierzą podobną do trójdiagonalnej[edytuj]

W matematyce spotykamy się też w równaniach macierzowych z macierzami podobnej do macierzy trójdiagonalnej (5.94), której przepis jest:

(5.114)

W porównaniu z macierzą trójdiaagonalną macierz powyższa róźni się od poprzedniej tym, że powyżej pojawiają się niezerowe elementy p1 i q1. Rozłóżmy macierz (5.114) na iloczyn stosując metodę Gaussa lub Doolittle'a. Macierz jest macierzą trójkatną dolną z jedynkami na diagonali, a macierz jest macierzą trójkątną górną niekoniecznie z jedynkami na diagonali, które przedstawiamy w formie:

(5.115)
(5.116)

Policzmy teraz iloczyn macierzy (5.115) i (5.116) i przyrównamy je do macierzy podobnej do trójdiagonalnej (5.114):


(5.117)

Porównując macierz końcową uzyskaną w wyniku obliczeń (5.117) i macierz (5.114), wtedy możemy napisać tożsamości na parametry pi, ui i qi:

Wzory na elementy macierzy L i U

...................................................................................................................................................

....
(5.118)

Mamy sobie równanie macierzowe , który po rozkładzie macierzy na iloczyn dwóch czynników macierzowych (5.115) i (5.116) zapisujemy je jako równanie , który rozbijemy na dwa równania, tzn. na i , z których pierwsze równanie rozpiszemy w postaci równania yi, a drugie xi dla i=1,2,..,n:





(5.118)




(5.119)

Podczas zaokrąglania macierzy przy liczeniu iloczynu LU powstaje błąd zaokrąglenia E=LU-A, wtedy norma błędu jest opisywana przez ||E||1≤ 2nε||A||1. Jeśli wyniki L i U są w pewien w sposób zaokrąglone, wtedy możemy napisać rozwiązanie równań macierzowych (LL)/y=d i (UU)/x=y, wtedy ograniczenia na normy i normy błędów dla macierzy L i U, przy zaokrągleniu, piszemy ||L||1≤2, ||δL||1≤ε||L||1, a także ||U||1≤2||A||1, ||δU||1≤5ε||U||1. Norma błędu zaokrąglenia macierzy A przedstawiamy w zależności od normy tejże macierzy w sposób: ||δA||1≤(6n+20+20nε)||A||1. Patrząc na wynik na normą błędu zaokrąglenia ostatnio napisany w tym rozdziale dowiadujemy się że nastąpiło pogorszenie osaczowania obliczeń dla naszej macierzy A w tym rozdziale niż dla macierzy całej A według jego normy błędu (5.78).

Wyznaczanie wartości wyznacznika oraz macierzy odwrotnej[edytuj]

Podczas wyznaczania wyznacznika macierzy należy wykonać n! obliczeń, co jest za dużo dla obecnych maszyn cyfrowych i dlatego stosuje się rozkład macierzy A na dwa macierze L i U do postaci A=LU według metody eliminacji Gaussa, wtedy po tym rozkładzie zastosujmy twierdzenie o wyznaczniku iloczynu dwóch macierzy:

(5.120)

Powyżej zastosowaliśmy to , że detL=1, oraz że macierz LU została policzona z błędem na maszynie cyfrowej z błędem E. Przybliżeniu wyznacznik macierzy A w przybliżeniu jest równy iloczynowi n elementów na przekątnej macierzy U.

Oznaczmy przez X odwrotność macierzy A, wtedy błąd liczenia iloczynu XA powinien być w przybliżeniu równy macierzy jednostkowej z błędem określonej E=I-XA, wtedy błąd bezwzględny przy wyznaczaniu X według normy ||⋅|| jest równy:

(5.121)

przez g oznaczymy największy element układu macierzy A(1),A(2),...,A(n)=U, które są otrzymane metodą eliminacji jakie dotychczas poznaliśmy. Wartość g możemy napisać według oszacowania g≤8||A||1∞. Jeśli mamy oszacowanie odwrotności macierzy A, wtedy błąd zmiennej x przepisujemy według (5.79). Oszacowanie błędu E według normy ||⋅||2 piszemy