1. UKŁADY ALGEBRAICZNYCH RÓWNAŃ LINIOWYCH (URL)

1.1. Definicja URL, formy zapisu

Niech będzie dany układ równań algebraicznych

(1.1)

Układ ten w zapisie macierzowym ma postać

(1.2)

lub

(1.3)

gdzie
 macierz współczynników układu (m. główna),

 macierz (wektor) niewiadomych,

 macierz (wektor) danych.

Układ (1.1) jest niejednorodny, gdy
, natomiast jest jednorodny, gdy
.

URL jest, [648] s.75:

• zgodny, gdy ma przynajmniej jedno rozwiązanie:

 oznaczony, gdy ma tylko jedno rozwiązanie,

 nieoznaczony, gdy ma nieskończenie wiele rozwiązań,

• sprzeczny, gdy nie ma rozwiązań.

Rozwiązanie układu (1.1) opiera się o twierdzenie Kroneckera-Capelliego. Twierdzenie to wymaga utworzenie macierzy rozszerzonej powstałej przez dołączenie do macierzy
kolumny wyrazów wolnych

(1.4)

Następnie określa się
- rząd macierzy A oraz
- rząd macierzy B.

Twierdzenie Kroneckera-Capelliego, [648] s.78,

Układ niejednorodny (1.1) jest rozwiązywalny wtedy i tylko wtedy, gdy
; możliwe są przypadki:

• 
  , wtedy istnieje dokładnie jedno rozwiązanie,

• 
  , wtedy istnieje nieskończenie wiele rozwiązań zależne od
  parametrów,

• 
  , wtedy układ jest sprzeczny.

 Twierdzenie K-C 

1.2. Ogólny podział metod rozwiązywania URL

Metody ścisłe (dokładne), [648] s.156; prowadzą do ścisłego rozwiązania URL za pomocą skończonej liczby działań pod warunkiem, że wszystkie działania są wykonywane bez zaokrągleń. Wśród metod ścisłych najważniejszymi są:

 wzory Cramera,

 eliminacji Gaussa:

 schemat jednego dzielenia,

 schemat elementów podstawowych,

 Banachiewicza; dotyczy układów o symetrycznej macierzy
,

 Cholesky'ego; wymaga rozkładu macierzy
na iloczyn macierzy
, gdzie
 macierz trójkątna dolna,
 macierz trójkątna górna,

 macierzy prawie trójkątnych (PT); wymaga rozkładu macierzy
na iloczyn macierzy prawie trójkątnych.

Metody przybliżone (iteracyjne) [648] s.189; przybliżone rozwiązanie jest granicą nieskończonego ciągu kolejnych jego przybliżeń. Idea tych metod polega na tym, że za początkowe przybliżenie rozwiązania przyjmuje się dowolny wektor
. Następnie, według określonego schematu tworzy się ciąg rozwiązań
tak, aby wektor
lepiej aproksymował rozwiązanie, niż
. Stąd wynika, że liczba działań zależy od wymaganej dokładności rozwiązania. Wśród metod przybliżonych najważniejszymi są:

 iteracji prostej,

 Seidla; jest modyfikacją metody iteracji prostej,

 macierzy prawie trójkątnych (PT).

Ogólna zasada wyboru metody zależy od postaci macierzy
, i tak:

 metody dokładne stosuje się wtedy, gdy macierz
jest pełna i mała
,

 metody przybliżone stosuje się wtedy, gdy macierz
jest duża i rzadka (szczególnie wtedy, gdy w pobliżu przekątnej głównej jest dużo elementów zerowych).

1.3. Rodzaje błędów

Bez względu na to, czy UKL rozwiązuje się metodami ścisłymi, czy przybliżonymi, zawsze istnieje wiele przyczyn, aby otrzymać rozwiązanie obarczone pewnym błędem (a więc rozwiązanie przybliżone). Na to składają się następujące rodzaje błędów:

 wejściowy, spowodowany niedokładnymi wartościami współczynników
,
pozyskiwanych eksperymentalnie lub innych obliczeń,

 zaokrągleń, wprowadzanych przez komputer podczas numerycznego wykonywania działań arytmetycznych,

 metody rozwiązywania URL.

Dwa pierwsze błędy mogą wystąpić w metodach ścisłych, natomiast wszystkie w metodach przybliżonych.

Błąd metody przybliżonej szacuje się poprzez normy wektorów i macierzy. Najważniejsze normy, i ich realizacje w Matlab przedstawiono w tabeli 1.

Tabela 1. Normy wektorów i macierzy oraz ich realizacja w Matlab

Normy wektorów	Normy macierzy	Matlab
	max suma modułów w kolumnie	norm(A,1)
	lub Euklidesa/ Schura/ Frobeniusza	norm(A, `fro')
		Norm(A,inf) norm(A,'inf')
		norm(A) norm(A,2)
	max suma modułów w wierszu

• 2. METODY ŚCISŁE

Metody ścisłe nie wnoszą do rozwiązania błędu metody. Niech również współczynniki
,
będą dokładne. Jednak nawet przy takich założeniach rozwiązanie URL może być przybliżone ze względu na błędy zaokrągleń działań arytmetycznych [276] s.193.

• 2.1. URL jednorodne

Zanim poda się przegląd niektórych metod ścisłych rozwiązywania układów równań niejednorodnych, poda się metodę rozwiązywania układów równań jednorodnych, która należy do metod ścisłych [648] s.82.

Niech będzie dany jednorodny URL

(2.1)

Twierdzenie 1

Układ m równań liniowych jednorodnych, dla którego
ma tylko jedno rozwiązanie zerowe, tzn.
.

 Twierdzenie 1 

Twierdzenie 2

Warunkiem koniecznym i dostatecznym, aby układ m-równań z n-niewiadomymi
miał rozwiązania niezerowe jest
.

 Twierdzenie 2 

Twierdzenie 3

Jeżeli
, a

(2.2)

gdzie
- dopełnienie algebraiczne.

Jeżeli
jest niezerowym rozwiązaniem układu (2.1), to
jest także rozwiązaniem tego układu, gdzie Cdowolna stała.

 Twierdzenie 3 

• Przykład 1

Niech będzie dany układ równań

(1)

Dla tego układu
,
, natomiast macierz dopełnień algebraicznych

(2)

Stąd według wzoru (2.2) np. dla
, jest

(3)

oraz

(4)

Należy zauważyć, że przyjmując
, rozwiązanie otrzyma się z wzoru (4) przyjmując
.

 Przykład 1 

• 2.1. Wzory Cramera

Wzory Cramera są przykładem metody ścisłej oraz pierwszym przypadkiem twierdzenia Kroneckera-Capelliego (
), [648] s.78, w którym dla małych URL rozwiązanie otrzymuje się ścisłe.

• Niech będzie dany URL (1.1). Tworzy się
  wyznaczniki zastępując w -kolumnach elementy macierzy
  przez elementy wektora danych
  , tzn.
  , wzór (2.3).

(2.3)

Następnie oblicza się wartości wyznaczników
,
. Jeżeli
to istnieje dokładnie jedno rozwiązanie układu w postaci (wzory Cramera)

…
(2.4)

Wyprowadzenie tych wzorów jest podane niżej.

• Przykład 2

Niech będzie dany układ równań

(1)

Zgodnie z wzorami Cramera jest

(2)

(3)

(4)

 Przykład 2 

• 2.1.1. Postać macierzowa wzorów Cramera

Niech będzie dany URL w postaci (1.3). Mnoży się to równanie przez macierz odwrotną
, stąd

(2.5)

Ponieważ
jest macierzą jednostkową, więc

(2.6)

Dojście do macierzy odwrotnej
odbywa się etapami:

 najpierw oblicza się macierz dopełnień algebraicznych
,

 dalej, macierz dołączoną
,

 stąd
.

Ostatni wzór należy wstawić do (2.6), stąd

(2.7)

Dowodzi się [648] s.77, że -wiersz wektora
, tzn.
, jest równy wartości wyznacznika
, wzór (2.3), a więc wzór
odpowiada wzorowi (2.4).

• Przykład 3

Niech będzie dany układ równań taki, jak w przykładzie 1, gdzie

(1)

Według wzoru (2.6) jest

(2)

 Przykład 3 

• Przykład 4

Niech będzie dany układ równań taki, jak w przykładzie 1. Układ ten należy rozwiązać według wzoru (2.7).

Zgodnie z tym wzorem jest

(1)

(2)

 Przykład 4 

xxxxxxxxxxxxxxxxxxxx I wy kadxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

• 2.1.2. URL źle uwarunkowane

W takich układach rozwiązanie jest wrażliwe na, pkt. 1.3, zaokrąglenia współczynników
,
oraz zaokrąglenia działań arytmetycznych. Istotę problemu ilustruje następny przykład.

Przykład 5, [9] s.315

Niech będzie dany układ równań

(1)

Dla tak zadanych współczynników
, rozwiązaniem tego układu, według wzoru (2.6), jest

(2)

Niech teraz współczynniki
będą zaokrąglone do dwóch miejsc dziesiętnych, natomiast
są dane ściśle. Wtedy macierz
ma postać

(3)

Rozwiązanie jest równe

(4)

Niech teraz współczynniki
będą zaokrąglone do czterech miejsc dziesiętnych, natomiast
są dane ściśle. Wtedy

(5)

Rozwiązanie jest równe

(6)

 Przykład 5 

• 2.1.2. Przybliżone szacowanie błędów rozwiązania

Podano sposób szacowania błędów spowodowanych zmianą tylko elementów
macierzy
, [9] s.316; bardziej zaawansowaną i ogólną metodę podano dalej.

Niech błąd macierzy
będzie
, a jego skutkiem jest błąd macierzy
oznaczony przez
. Wówczas zamiast równania (1.3) jest

(2.8)

lub

(2.9)

W (2.9) pomija się małą drugiego stopnia
oraz uwzględnia równanie (1.3), pozostaje

(2.10)

W ostatnim przykładzie ten błąd
dla rozwiązania (4), natomiast
dla rozwiązania (6). Jak widać, szczególnie w pierwszym przypadku, błąd (2.10) nie odzwierciedla rzeczywistej różnicy między rozwiązaniem ścisłym a rozwiązaniem z zaokrąglonymi współczynnikami
.

Kolejny przykład jeszcze bardziej uzasadnia istnienie macierzy źle uwarunkowanych.

• Przykład 6, [9] s

Niech będzie dany układ równań

(1)

Rozwiązaniem ścisłym tego układu jest wektor
.

Teraz niech nieznacznie zmienią się współczynnik
oraz

(2)

Rozwiązaniem tego układu jest wektor
. Stąd wniosek, że ten układ jest (bardzo) źle uwarunkowany.

 Przykład 6 

• 2.1.3. Układ m równań z n niewiadomymi

Wzory Cramera służą też do rozwiązywania układów ujętych w drugim przypadku twierdzenia Kroneckera-Capelliego, tzn. gdy
; wtedy istnieje nieskończenie wiele rozwiązań zależne od
parametrów.

• Przykład 7

• Niech będzie dany układ równań

(1)

Dla tego układu
, natomiast
. W takim przypadku bada się rzędy macierzy A oraz macierzy rozszerzonej B. Tutaj
oraz
; ponieważ
więc układ ma nieskończenie wiele rozwiązań zależnych od jednego parametru.

Rozważa się np. 2 pierwsze równania przyjmując za parametr

(2)

Teraz jest

(3)

(4)

Stąd

(5)

Gdyby dla układu (2)
, wówczas do rozważań należy wybrać dwa inne równania albo za parametr przyjąć inną zmienną, np.
.

 Przykład 7 

Dla ciągłości rozważań w kolejnym przykładzie zostanie rozpatrzony ostatni przypadek URL, ujęty w trzecim przypadku twierdzenia Kroneckera-Capelliego, tzn. gdy
; wtedy układ jest sprzeczny.

• Przykład 8

• Niech będzie dany układ równań

(1)

Dla tego układu
, natomiast
. Rzędy macierzy są odpowiednio równe:
,
; ponieważ
więc układ jest sprzeczny.

 Przykład 8 

2.2. Metoda eliminacji Gaussa, schemat jednego dzielenia

• 2.2.1. Układy równań z macierzą trójkątną

Wiele metod ścisłych rozwiązywania URL oparte jest na idei zamiany pełnej macierzy współczynników na macierz trójkątną lub na iloczyn macierzy trójkątnych. Stąd ważne jest, aby dostrzec zalety tej zamiany, mimo, że jest to dodatkowa operacja matematyczna. Ale, rozwiązywanie URL o macierzach trójkątnych jest znacznie prostsze niż o macierzach pełnych. Dla przykładu niech będzie dany układ o macierzy trójkątnej górnej U [295] cz.2,s.39; zakłada się, że macierz U jest nieosobliwa,
, tzn. wszystkie elementy diagonalne
.

(2.31)

Z postaci układu (2.31) wynika, że elementy wektora rozwiązania oblicza się „od końca”, a więc
, stąd

(2.32)

2.2.2. Metoda eliminacji Gaussa

Metoda ta polega na przekształceniu układu równań
do równoważnego układu o macierzy trójkątnej górnej U, [295] t.2, s.41. Jest to równoważne rozkładowi macierzy A na iloczyn macierzy dolnej L i górnej U, tzn.
, co jest równocześnie ideą metody Cholesky'ego. A więc, przy realizacji metody eliminacji Gaussa (schemat jednego dzielenia) można wyodrębnić metodę Cholesky'ego.

Niech będzie dany układ równań

(2.33)

(2.34)

(2.35)

1. Redukcja równania (2.34)

 równanie (2.33) mnoży się przez
, stąd

(2.36)

 od równania (2.34) odejmuje się (2.36), stąd

(2.37)

lub

(2.34*)

gdzie
,
,
- współczynniki przy
,
i prawa strona (2.37).

2. Redukcja równania (2.35)

 równanie (2.33) mnoży się przez
, stąd

(2.38)

 od równania (2.35) odejmuje się (2.38), stąd

(2.39)

lub

(2.35*)

gdzie
,
,
 współczynniki przy
,
i prawa strona (2.39).

 Pierwszy układ zredukowany („*”)

(2.33)  (2.33*)

(2.34*)

(2.35*)

Redukcja równań (2.34), (2.35) polega na wyeliminowaniu z nich
, co można zapisać

(2.40)

(2.41)

gdzie

(2.42)

Wzory (2.40), (2.41) można uznać za pierwszy etap metody Cholesky'ego.

• Przykład 9

• Niech będzie dany układ równań z przykładu 2. Sprowadzając go do układu „*”, poprzez (2.40), (2.41), można napisać

(1)

gdzie

(2)

gdzie
,
oblicza się z wzorów (2.40), (2.41) dla
,
. Według (1)
.

 Przykład 9 

3. Redukcja równania (2.35*)

 równanie (2.34*) mnoży się przez
, stąd

(2.43)

 od równania (2.35*) odejmuje się (2.43), stąd

(2.44)

lub

(2.35**)

 Drugi układ zredukowany („**”)

(2.33)  (2.33*)  (2.33**)

(2.34*)  (2.34**)

(2.35**)

Redukcja równania (2.35*) polega na wyeliminowaniu z niego
co można zapisać

(2.45)

(2.46)

gdzie

(2.47)

Wzory (2.45), (2.46) można uznać za drugi etap metody Cholesky'ego.

• Przykład 10

• Niech będzie dany układ równań z przykładu 9. Sprowadzając go do układu „**”, poprzez (2.45), (2.46), można napisać

(1)

gdzie

(2)

gdzie
,
oblicza się z wzorów (2.45), (2.46) dla
. Według (1)
.

 Przykład 10 

Metodę eliminacji Gaussa (schemat jednego dzielenia) łatwo jest uogólnić na dowolną liczbę równań. Odpowiednie wzory można wyprowadzić samodzielnie lub znaleźć np. w [295] cz.2,s.41, [648] s.156. Dla przykładu, przez podstawienie (2.40) w (2.45) i (2.41) w (2.46) odpowiednio otrzyma się

(2.48)

(2.49)

gdzie

(2.50)

Metoda ta może być stosowana wtedy, gdy wszystkie elementy
. Jeżeli ten warunek nie jest spełniony, można np. zmienić kolejność równań. Istotne jest też, aby
nie były zbyt małe. Tego z kolei problemu można uniknąć stosują schemat elementów podstawowych (wersja metody eliminacji Gaussa) [295] cz.2,s.45, [648] s.160.

• 2.3. Metoda Cholesky'ego, rozkład LU

Metoda Cholesky'ego jest związana z metodą eliminacji Gaussa, a jej idea oparta jest o …

Twierdzenie 2.1 [648] s.31

Macierz kwadratową A, której wszystkie minory kątowe

, (2.51)

można przedstawić w postaci iloczynu dwóch macierzy trójkątnych (dolnej
i górnej
), przy czym rozkład ten jest jednoznaczny pod warunkiem, że elementom leżącym na diagonalni jednej z macierzy nada się różne od zera wartości.

Niech będzie dany URL w postaci (1.3). Zgodnie z twierdzeniem 2.1, macierz A można zapisać w postaci (rozkład LU)

(2.52)

Podstawiając (2.52) do (1.3) otrzyma się

(2.53)

Niech

(2.54)

Natomiast (2.53) przyjmie postać

(2.55)

Jak widać, w metodzie Cholesky'ego rozwiązanie otrzymuje się w dwóch etapach. W pierwszym, rozwiązuje się układ (2.55), którego rozwiązaniem jest wektor
. Wektor ten wstawia się do (2.54), z którego oblicza się
 rozwiązanie zadanego URL.

Problemem jest znalezienie macierzy L i U. Rozwiązanie problemu jest w metodzie eliminacji Gaussa, a wzorem wyjściowym do rozważań jest (2.48). W tym wzorze macierz
jest macierzą trójkątną górną, a więc
, natomiast
jest macierzą wyjściową, tzn.
. Zamiast wzoru (2.48) można napisać

(2.56)

Mnożąc (2.56) przez
,
otrzyma się (2.52), gdzie

(2.57)

• Przykład 11

• Niech będzie dany układ równań z przykładu 2. Najpierw należy rozłożyć macierz A na macierze L i U. Wzór (2.50) przedstawia macierz
  , gdzie
  ,
  ,
  . Dalej, według (2.56) oblicza się U

(1)

• Natomiast według (2.57) oblicza się L

(2)

Należy zaznaczyć, że w MATLAB istnieje funkcja rozkładająca macierz A na macierze L i U i nie ma potrzeby korzystania z wzoru (1).

W pierwszym etapie metody Cholesky'ego rozwiązuje się równanie (2.55), skąd

(3)

W drugim etapie rozwiązuje się równanie (2.54), skąd

(4)

 Przykład 11 

Literatura

[9] R.E.D. Bishop, G.L.M. Gladwell, S. Michaelson, Macierzowa analiza drgań, PWN, Warszawa, 1972.

[276] Z. Fortuna, B. Macukow, J. Wąsowski, Metody numeryczne, WNT, Warszawa, 1993.

[295] J.M. Jankowscy, Przegląd metod i algorytmów numerycznych, WNT, Warszawa, 1981.

[648] B. Kowalczyk, Macierze i ich zastosowania, WNT, Warszawa, 1976.

Układy_równań_liniowych

- 1 -

---