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 Weźmy sobie przestrzeń , którego elementami są wektory pionowe , wtedy możemy wprowadzić poszczególne normy inaczej zdefiniowane stosowanych w obliczeniach numerycznych:
Normy , i spełniają warunki poniżej dla dowolnego wektora należącego do n-wymiarowej przestrzeni rzeczywistej, które to piszemy:
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 :
Symbole "p" i "q" oznaczają normy przedstawione w punktach , i , dla którego definicja normy macierzy jest przedstawiona w punkcie . Zdefiniujmy teraz trzy kolejne normy macierzy, podobne do definicji norm wektora , i , tylko że ich definicje wyglądają:
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ą ||⋅|| używa sie go w eulkidesowej normy macierzy, które często są zwane normami Schura lub normami Frobeniusza, którego definicja jest:
wtedy możemy napisać warunek zgodności dla n-wymiarowej przestrzeni rzeczywistej, do których należą elementy , zatem:
Dla dowolnej macierzy możemy powiedzieć, że zachodzi warunek, który jest zawsze prawdziwy:
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:
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 λ 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ć:
Wykorzystując definicję normy , możemy napisać wniosek przy pomocy normy zdefiniowanej na macierzy , wykorzystując twierdzenia :
Zdefiniujemy teraz dwa lematy, który są dla nas ważne wykorzystując niektóre dowodu napisane powyżej:
Maksymalna wartość wartości własnej nazywamy promieniem spektralnym macierzy A i na podstawie wzoru piszemy:
Błędy rozwiązań układów równań algebraicznych
Przypadek pierwszy
Weźmy sobie zamiast i wielkości i , wtedy równanie macierzowe możemy zapisać przy wzorem:
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:
wtedy w 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:
Liczbę K 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ć:
Z obliczeń przeprowadzonych w punkcie dochodzimy do wniosku przy odpowiedniej definicji k, że zachodzi:
Określmy jaka jest graniczna wartość współczynnika wzmocnienia k, jako wielkości granicznej współczynników k określonych we wzorze jako czynnik, takiego że zachodzi równość dla ściśle określonego , która dla każdej tej wielkości zachodzi w ogólności nierówność słaba, takiego że:
gdy zachodzi δ→0. Teraz będziemy wyznaczać oszacowanie wielkości k, 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ć:
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:
Z definicji normy możemy napisać oszacowanie czynnika stojącego przy występującego we wzorze :
stąd możemy napisać oszacowanie wielkości poprzez wielkość , zatem:
Czynnik stojący przy k możemy wyrazić przy pomocy definicji normy wektora , a także normy macierzy w sposób , a k oblicza się jako iloczyn norm macierzy macierzy A i jego odwrotności przy normie , 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:
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:
Układy równań algebraicznych o trójkątnej macierzy 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:
Poszczególne elementy zmiennych x możemy policzyć z poniższych wzorów:
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 x jest wykonywanych n dzieleń i mnożeń, wtedy ilość dzieleń i mnożeń jest:
Dla układu rozwiązań x dla x mamy zero dodawań i odejmowań, dla x mamy jedno dodawanie lub odejmowanie, dla x mamy n-1 dodawań lub odejmowań, zatem liczba wszystkich dodawań lub odejmowań jakie należy wykonać jest:
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:
Wzory możemy napisać z odpowiednim przybliżeniem uwzględniając, że wielkości x i b są napisane z pewnym zaokrągleniem:
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ść:
Jeśli wiadomo, że oszacowanie elementów macierzy z definicji normy ||⋅|| od góry jest , wtedy macierz błędu z normą ||⋅|| i ||⋅|| możemy przepisać:
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:
Macierzą silnie diagonalnie dominującą nazywamy taką macierz A o stopniu n, w której w występuje nierówność ostra. Macierz (silnie) diagonalnie dominująca kolumnowo nazywamy macierz, dla której A jest (silnie) diagonalnie dominująca, tzn. gdy spełniony jest warunek dla i=1,2,...,n:
Macierz generowana przez 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:
Rozwiązania równań liniowych metodą eliminacji Gaussa 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ń , 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ń:
Odejmijmy i-te równanie i>1 od pierwszego równania pomnożonego przez układu równań , w ten sposób otrzymujemy równanie macierzowe , co po rozpisaniu jego na układ równań, otrzymujemy:
W powyższych równaniu wyeliminowaliśmy zmienną x 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ń:
W uzyskanym układzie równań rozwiązujemy x metodą dla macierzy trójkątnej. Liczba mnożeń i dzieleń jakie należy wykonać dla układu równań , by uzyskać macierz trójkątna dla układu równań jest w ilości kroków:
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ń 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ń 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ń . Liczba dodawań i dzieleń jakie układ musi wykonać by układ doprowadzić do postaci trójkątnej jest:
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 . 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:
Przy pomocy macierzy podanej w podpunkcie 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:
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:
Ponieważ macierze są macierzami nieosobliwymi, wtedy możemy równanie równoważnie zapisać na w sposób:
Można udowodnić, że odwrotności macierzy i , czyli macierze i , zapisujemy w formie:
Możemy również powiedzieć, że iloczyn odwrotności macierzy dla i=1,...,n-1 możemy zapisać przy pomocy liczb l w formie:
Oznaczmy macierz oznaczoną przez , a macierz przez , wtedy wyrażenie macierzowe zapisujemy jako:
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 i , a metoda Doolittle'a