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