7.Układy równań liniowych.pdf

(111 KB) Pobierz
116013940 UNPDF
Rozdzial 7
Uklady rownan liniowych
W tym rozdziale zajmiemy si e rozwi azywaniem ukladow rownan liniowych
(2.2). Stosuj ac zapis macierzowy zadanie formulujemy nast ej aco. Dla danej
macierzy (wspolczynnikow) A2K m;n oraz wektora (wyrazow wolnych) b2
K m nalezy znalezc wszystkie wektory (niewiadome) x spelniaj ace rownosc
Ax = b:
(7.1)
7.1 Zbior rozwi azan
7.1.1 Twierdzenie Croneckera-Capelliego
Mamy trzy mozliwosci:
(i)8x2K n
Ax 6= b =)uklad jest sprzeczny
(ii)9x2K n
Ax = b =)uklad jest niesprzeczny
(iii) !9x2K n
Ax = b =)uklad jest oznaczony
1
Twierdzenie 7.1 (Kroneckera-Capelliego)
Uklad Ax = b jest niesprzeczny wtedy i tylko wtedy gdy
rz(A) = rz([A;b]);
tzn. rz ad macierzy A jest rowny rz edowi A rozszerzonej o wektor b.
1 Symbol \!9" czytamy jako \istnieje dokladnie jeden".
61
116013940.001.png
62
ROZDZIAL 7. UKLADY R OWNA N LINIOWYCH
Dowod. Jesli rz([A;b]) = rz(A) to wektor b nalezy do pzrestrzeni rozpi etej
przez wektory-kolumny macierzy A. To zas oznacza, ze b jest liniow a kom-
binacj a tych wektorow. Wspolczynniki tej kombinacji tworz a rozwi azanie x
ukladu.
Z drugiej strony, jesli istnieje x2K n taki, ze Ax = b tob jest kombinacj a
liniow a wektorow-kolumn macierzy A, czyli b nalezy do przestrzeni rozpi etej
na tych wektorach. To zas implikuje ze rz([A;b]) = rz(A) i konczy dowod.
Mozemy rownowaznie stwierdzic, ze uklad Ax = b jest niesprzeczny
wtedy i tylko wtedy gdy b2R(A), czyli wektor wyrazow wolnych lezy w
obrazie macierzy wspolczynnikow.
7.1.2 Zbior rozwi azan jako warstwa
Niech L(A;b) =fx2K n : Ax = bg
b edzie zbiorem wszystkich rozwi azan ukladu Ax = b.
Denicja 7.1 Powiemy, ze dwa uklady, A 1 x = b 1 oraz A 2 x = b 2 , s a
rownowazne gdy maj a ten sam zbior rozwi azan, tzn. gdy
L(A 1 ;b 1 ) =L(A 2 ;b 2 ):
Twierdzenie 7.2 Jesli uklad Ax = b jest niesprzeczny to zbior rozwi azan
L(A;b) =fx 0 + y : y2N(A)g= W (x 0 ;N(A)) ;
gdzie x 0 jest dowolnych rozwi azaniem szczegolnym ukladu.
Dowod. Jesli x 0 jest rozwi azaniem szczegolnym i y2N(A) to
A(x 0 + y) = Ax 0 + Ay = b +0 = b;
czyli x 0 + y jest tez rozwi azaniem. To zas implikuje ze W (x 0 ;N(A))
L(A;b).
Z drugiej strony, jesli Ax = b to A(xx 0 ) = bb = 0, czyli (xx 0 )2
N(A). A wi ec x = x 0 + (xx 0 ) jest z jednej strony rozwi azaniem ukladu, a
z drugiej elementem warstwy W (x 0 ;N(A)). St adL(A;b)W (x 0 ;N(A)).
7.2. EFEKTYWNA METODA ROZWI AZANIA
63
7.1.3 Uklady nieosobliwe
Rozpatrzmy przez chwil e uklady z macierzami kwadratowymi.
Twierdzenie 7.3 Macierz kwadratowa A2K n;n jest nieosobliwa wtedy i
tylko wtedy gdy rz(A) = n.
Dowod. Wobec nierownosci
n = rz(I n ) = rz(AA 1 )min
rz(A); rz(A 1 )
mamy, ze jesli A jest nieosobliwa to rz(A) = n = rz(A 1 ). Z drugiej strony,
jesli rz(A) = n to kolumny A s a wektorami liniowo niezaleznymi. St ad
istnieje macierz X2K n;n taka, ze AX = I n . Podobnie, istnieje Y2K n;n
taka, ze A T Y = I n , czyli Y T A = I n . Ponadto
Y T = Y T I n = (Y T A)X = I n X = X;
tzn. odwrotnosci lewostronna i prawostronna istniej a i s a sobie rowne, A 1 =
X = Y T . To konczy dowod.
Wiemy, ze jesli macierz kwadratowa A jest nieosobliwa to rozwi azaniem
ukladu Ax = b jest x := A 1 b i jest to jedyne rozwi azanie, tzn. uklad jest
oznaczony. Ale tez odwrotnie, jesli uklad Ax = b z macierz a kwadratow a
A jest oznaczony dla pewnego b to macierz A jest nieosobliwa. Rzeczywiscie,
wtedy j adroN(A) =f0g. To znaczy, ze wektory-kolumny macierzy tworz a
uklad liniowo niezalezny i rz(A) = n. Na podstawie twierdzenia 2.1 wnio-
skujemy ze A jest nieosobliwa.
Wniosek 7.1 Niech A b edzie macierz a kwadratow a. Uklad Ax = b jest
oznaczony wtedy i tylko wtedy gdy A jest nieosobliwa.
7.2 Efektywna metoda rozwi azania
Dla danej macierzy A2K m;n i wektora b2K m chcemy zbadac, czy uklad
(7.1) jest niesprzeczny, a jesli tak to znalezc zbior jego rozwi azan (warstw e)
L(A;b) = x 0 +N(A);
gdzieN(A) = span(z s+1 ;z s+2 ;:::;z n ) i s = rz(A).
64
ROZDZIAL 7. UKLADY R OWNA N LINIOWYCH
7.2.1 Ogolny schemat
Najpierw wyznaczymy s = rz(A) i t = rz([A;b]), a nast epnie w przypadku
s = t skonstruujemy rozwi azanie szczegolne x 0 oraz baz e z s+1 ;:::;z n j adra
N(A).
Ogolny schemat post epowania prowadz acy do postaci rownania, z ktorego
mozna juz stosunkowo latwo odczytac rozwi azanie jest nast epuj acy. Star-
tuj ac z ukladu wyjsciowego (7.1), ktory oznaczymy przez (U 0 ), kolejno dla
k = 1; 2;:::;s konstruujemy \prostsze" i (prawie) rownowazne (U 0 ) uklady
(U k ) z macierzami A (k)
tego samego formatu co A. Macierz A (s)
ukladu
docelowego (U s ) okaze si e trojk atn a gorn a.
Dopuszczamy przy tym nast epuj ace operacje na ukladnie rownan:
(i) zamiana kolejnosci rownan (wierszy macierzy),
(ii) zamiana kolejnosci niewiadomych (kolumn macierzy),
(iii) dodanie do jednego z rownan innego rownania pomnozonego przez ska-
lar.
Zauwazmy, ze operacje (i) oraz (iii) prowadz a do ukladow rownowaznych,
zas (ii) powoduje jedynie zmian e kolejnosci niewiadomych. W szczegolnosci,
rz ad macierzy ukladu nie ulega zmianie.
Schemat sprowadzania ukladu wyjsciowego do postaci z macierz a troj-
k atn a gorn a przy pomocy zdeniowanych operacji, ktory teraz dokladniej
opiszemy, nazywamy Eliminacj a Gaussa.
7.2.2 Eliminacja Gaussa
Zalozmy, ze wykonalismy juz k przeksztalcen ukladu wyjsciowego,
(U 0 )!(U 1 )!:::!(U k );
gdzie 0ks1, otrzymuj ac uklad
A (k) x (k)
= b (k)
z nacierz a
R k T k
0 V k
A (k) =
;
7.2. EFEKTYWNA METODA ROZWI AZANIA
65
gdzie R k 2TRIU k;k jest kwadratow a i nieosobliw a macierz a trojk atn a gorn a.
Oczywiscie, zalozenie to jest spelnione dla k = 0, czyli dla ukladu wyjscio-
wego, bowiem wtedy A (0) = V 0 = A.
Krok (k + 1)-szy eliminacji
1. Wybieramy w V k element rozny od zera, powiedzmy v p;q 6= 0, k + 1
pm, k + 1qn. (Taki element istnieje, bo inaczej mielibysmy
rz(A (k) ) = k < s = rz(A).)
2. Przestawiamy wiersze (k + 1)-szy z p-tym oraz kolumny (niewiadome)
(k + 1)-sz a z q-t a.
3. Dokonujemy eliminacji (k + 1)-szej niewiadomej z rownan od (k + 1)-
szego do m-tego odejmuj ac od rownania i-tego rownanie (k + 1)-sze
pomnozone przez l i;k+1 := a (k)
i;k+1 =a (k)
k+1;k+1 , i = k+1;k+2;:::;m. (Tutaj
i;j oznacza tu element aktualnie stoj acy na przeci eciu i-tego wiersza
i j-tej kolumny macierzy ukladu).
Po wykonaniu (k + 1)-szego kroku metody dostajemy uklad z macierz a
A (k+1) , ktora ma wyzerowane wspolczynniki o indeksach (i;j) dla 1j
k + 1, j < im.
Po wykonaniu s = rz(A) krokow dostajemy uklad (U s ) postaci
A (s) x (s)
= b (s) ;
przy czym
R s T s
0 0
A (s)
=
;
a wektor x (s) rozni si e od x (0) jedynie przestawieniem (permutacj a) wspol-
rz ednych. Rzeczywiscie, gdyby odpowiednia podmacierz V s macierzy A (s)
byla niezerowa to mielibysmy rz(A) = rz(A (s) ) > s.
Dodajmy jeszcze, ze w przypadkach s = 0 i s = min(m;n) niektore bloki
macierzy A (s)
s a puste.
7.2.3 Konstrukcja rozwi azania ogolnego
Przyjmuj ac
"
x (s)
#
"
b (s)
#
x (s)
=
I
x (s)
;
b (s)
=
I
b (s)
;
II
II
a (k)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin