[ Pobierz całość w formacie PDF ]
Rozdział 1
Układy równa« liniowych
1.1
Poj¦cia wst¦pne
Załó»my, »e dane s¡ liczby rzeczywiste
a
ij
, gdzie
i
= 1
,
2
,...,m
,
j
= 1
,
2
,...,n
, oraz
b
i
,
gdzie
i
= 1
,
2
,...,m
. Rozwa»my układ równa« liniowych z niewiadomymi
x
1
,
x
2
,
...
,
x
n
:
8
<
a
11
x
1
+
a
12
x
2
+
...
+
a
1
n
x
n
=
b
1
,
a
21
x
1
+
a
22
x
2
+
...
+
a
2
n
x
n
=
b
2
,
(1.1)
:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a
m
1
x
1
+
a
m
2
x
2
+
...
+
a
mn
x
n
=
b
m
.
Macierz
2
3
a
11
a
12
...a
1
n
b
1
a
21
a
22
...a
2
n
b
2
. . . . .
a
m
1
a
m
2
...a
mn
b
m
4
5
(1.2)
b¦dziemy nazywa¢
macierz¡ układu
(1.1), za± macierze
2
3
2
3
a
11
a
12
...a
1
n
a
21
a
22
...a
2
n
. . . .
a
m
1
a
m
2
...a
mn
b
1
b
2
.
b
m
4
5
4
5
A
=
oraz
B
=
(1.3)
b¦dziemy odpowiednio nazywa¢
macierz¡ współczynników
i
macierz¡ wyrazów wol-
nych
tego układu równa«. Macierz
A
okre±la si¦ równie» jako
macierz główn¡
, za± ma-
cierz
B
jako
wektor prawych stron
układu równa« (1.1).
1
Przy oznaczeniach wprowadzonych równo±ciami (1.3) macierz (1.2) zapisuje si¦ cz¦sto
w
postaci blokowej
:
[
AB
]
,
za± układ równa« liniowych (1.1) w postaci macierzowej:
AX
=
B,
(1.4)
gdzie
2
3
x
1
x
2
.
x
m
4
5
X
=
jest
wektorem niewiadomych
. Jest oczywiste, »e współrz¦dne ka»dego wektora
X
speł-
niaj¡cego równanie macierzowe (1.4) tworz¡ rozwi¡zanie układu równa« liniowych (1.1) i
odwrotnie.
1.2
Bazowa posta¢ układu równa« liniowych
W celu uproszczenia zapisu w dalszym ci¡gu rozwa»a« b¦dziemy zakłada¢, »e spełnione
jest nast¦puj¡ce zało»enie:
Zało»enie:
Je»eli nie zostanie wyra¹nie powiedziane inaczej, to b¦dziemy
przyjmowa¢, »e przy powy»szych oznaczeniach spełnione s¡ nast¦puj¡ce warun-
ki:
m
¬
n
oraz
rz¡d
A
=
m,
a wi¦c wiersze macierzy
A
, traktowane jako wektory, tworz¡ układ liniowo nieza-
le»ny i w±ród kolumn macierzy
A
(równie» traktowanych jako wektory) mo»na
znale¹¢
m
kolumn liniowo niezale»nych.
Zgodnie z przyj¦tym zało»eniem przyjmijmy, »e kolumny macierzy
A
o numerach
j
1
,
j
2
,
...
,
j
m
, tworz¡cych ci¡g rosn¡cy, s¡ liniowo niezale»ne i oznaczmy:
2
4
3
5
a
1
j
1
a
1
j
2
...a
1
j
m
a
2
j
1
a
2
j
2
...a
2
j
m
. . . .
a
mj
1
a
mj
2
...a
mj
m
A
b
=
,
(1.5)
2
za± przez
A
n
oznaczmy macierz otrzyman¡ z macierzy
A
po usuni¦ciu z niej kolumn o
numerach
j
1
,
j
2
,
...
,
j
m
. Dalej przyjmijmy oznaczenie:
2
4
3
5
x
j
1
x
j
2
.
x
j
m
X
b
=
i niech
X
n
oznacza wektor otrzymany z wektora
X
przez usuni¦cie z niego współrz¦dnych
o numerach
j
1
,
j
2
,
...
,
j
m
. Przy tych oznaczeniach układ równa« liniowych (1.6)
AX
=
B
mo»na zapisa¢ w nast¦puj¡cej postaci:
A
b
X
b
+
A
n
X
n
=
B
(1.6)
Poniewa» macierz
A
b
jest macierz¡ kwadratow¡ wymiaru
m
×
m
i jej rz¡d wynosi
m
(bo
ma tyle liniowo niezale»nych kolumn), wi¦c jest macierz¡ odwracaln¡. Mno»¡c obie strony
równo±ci (1.6) przez macierz (
A
b
)
−
1
otrzymujemy
X
b
+ (
A
b
)
−
1
A
n
X
n
= (
A
b
)
−
1
B.
(1.7)
Otrzyman¡ posta¢ układu równa« liniowych nazywamy
bazow¡ postaci¡
układu równa«
liniowych (1.1).
1.3
Rozwi¡zania bazowe
Z równo±ci (1.7) otrzymujemy natychmiast
X
b
= (
A
b
)
−
1
(
B
−
A
n
X
n
)
.
(1.8)
Zauwa»my, »e warto±ci zmiennych
x
i
wyst¦puj¡ce w wektorze
X
n
mo»na ustali¢ dowolnie,
a nast¦pnie, za pomoc¡ wzoru (1.8), obliczy¢ warto±ci współrz¦dnych wektora
X
b
. Wzór
(1.8) pozwala wi¦c na znalezienie wszystkich rozwi¡za« układu równa« liniowych (1.1) (lub,
równowa»nie, układu (1.4)). W rozwi¡zaniach tych
n
−
m
niewiadomych mo»e przyjmowa¢
dowolne warto±ci — nazywamy je
zmiennymi niezale»nymi
lub
niebazowymi
i mówi-
my, »e rozwi¡zanie zale»y od
n
−
m
parametrów. Pozostałe niewiadome:
x
j
1
,
x
j
2
,
...
,
x
j
m
nazywane s¡
zmiennymi zale»nymi
lub
bazowymi
i zale»¡ od zmiennych niebazowych
w sposób opisany wzorem (1.8).
Nale»y podkre±li¢, »e to czy dana niewiadoma w układzie równa« liniowych zostanie
sklasyfikowana jako zmienna bazowa, czy te» niebazowa, zal¦»y od wyboru macierzy
A
b
:
3
konstruujemy j¡ wybieraj¡c z macierzy
Am
liniowo niezale»nych kolumn i zmienne o nu-
merach tych kolumn staj¡ si¦ zmiennymi bazowymi. Inny wybór macierzy
A
b
prowadzi do
innego „przydziału ról” niewiadomym. Wynika st¡d, »e liczba mo»liwych wyborów zmien-
nych bazowych w układzie równa« liniowych (1.1) jest równa liczbie mozliwych wyborów
macierzy kwadratowej
A
b
rz¦du
m
. Poniewa» budujemy tak¡ macierz wybieraj¡c
m
ko-
lumn spo±ród
n
kolumn macierzy
A
, wi¦c maksymaln¡ liczb¡ wyborów ró»nych układów
zmiennych bazowych jest
!
n
m
.
Definicja 1. Rozwi¡zaniem bazowym
układu równa« liniowych (1.1) nazywamy ka»de
rozwi¡zanie tego układu, w którym zmienne niebazowe przyjmuj¡ warto±¢ 0.
Dopuszczal-
nym rozwi¡zaniem bazowym
nazywamy takie rozwi¡zanie bazowe, w którym warto±ci
wszystkich zmiennych s¡ nieujemne.
Bezpo±rednio z uwag poprzedzaj¡cych t¦ definicj¦ wynika twierdzenie:
Twierdzenie 1.
Układrówna«liniowych(1.1)mo»emie¢conajwy»ej
n
m
rozwi¡za«
bazowych.
Zauwa»my, »e rozwi¡zanie bazowe otrzymujemy podstawiaj¡c
X
n
= [0 0
...
0]
T
we
wzorze (1.8). Wobec tego
X
b
= (
A
b
)
−
1
B
i, w konsekwencji, w celu wyznaczenia rozwi¡zania bazowego nie potrzeba u»ywa¢ macierzy
A
n
.
Przykład
1
.
Rozwa»my układ równa« liniowych:
8
<
:
2
x
1
+
x
2
−
2
x
3
+ 2
x
4
= 3
,
x
1
+
x
2
−
x
3
+ 2
x
4
= 2
.
Z kolumn macierzy głównej tego układu
2
4
2
3
1
−
2
2
A
=
5
1
1
−
1
2
mo»na utworzy¢ sze±¢ macierzy kwadratowych stopnia 2, ale w±ród nich tylko cztery na-
st¦puj¡ce maj¡ rz¡d równy 2:
2
4
2
3
5
,A
b
2
=
2
4
2
3
5
,A
b
3
=
2
4
1
−
2
1
−
1
3
5
,A
b
4
=
2
4
−
2
3
5
1
2
2
A
b
1
=
1
1
1
2
−
1
2
4
i odpowiadaj¡ kolejno nast¦puj¡cym układom zmiennych bazowych:
(
x
1
,x
2
)
,
(
x
1
,x
4
)
,
(
x
2
,x
3
)
,
(
x
3
,x
4
)
.
Wynika st¡d, »e rozwa»any układ równa« ma dokładnie cztery rozwi¡zania bazowe. Aby
je znale¹¢ nale»y wyznaczy¢ wektory zmiennych bazowych korzystaj¡c ze wzoru:
2
4
3
2
3
5
, i
= 1
,
2
,
3
,
4
.
X
b
i
= (
A
b
i
)
−
1
B,
gdzie
B
=
Poniewa»
2
3
2
3
2
4
−
1
3
2
4
−
1 1
−
1
2
1
3
−
1
−
1
−
1
−
1
1
−
1
−
1
1
−
1
−
1
2
1
2
A
b
1
A
b
2
A
b
3
A
b
4
=
4
5
,
=
4
5
,
=
5
,
=
5
2
−
1
1
dostajemy kolejno:
2
4
x
1
x
2
3
2
3
2
4
3
2
3
2
4
1
1
3
1
−
1
−
1
X
b
1
=
5
=
4
5
5
=
5
,
2
2
4
x
1
x
4
3
2
3
2
4
3
2
3
2
4
1
1
2
3
1
−
1
−
1
2
1
X
b
2
=
5
=
4
5
5
=
5
,
2
4
x
2
x
3
3
2
4
−
1
3
2
4
3
2
3
2
3
2
1
−
1
X
b
3
=
5
=
5
5
=
4
5
,
−
1
1
2
4
x
3
x
4
3
2
4
−
1 1
−
1
2
1
3
2
4
3
2
3
2
4
−
1
1
2
3
X
b
4
=
5
=
5
5
=
5
.
Wobec tego otrzymujemy cztery rozwi¡zania bazowe:
2
3
2
3
2
3
2
3
1
1
0
0
1
0
0
1
2
0
1
−
1
0
0
0
−
1
1
2
4
5
4
5
4
5
4
5
X
1
=
, X
2
=
, X
3
=
, X
4
=
,
z których tylko dwa pierwsze s¡ dopuszczalnymi rozwi¡zaniami bazowymi.
1.4
Znajdowanie rozwi¡za« bazowych
W praktyce, chc¡c znale¹¢ rozwi¡zanie bazowe układu równa« liniowych, sprowadzamy ten
układ do postaci bazowej (zrdukowanej) korzystaj¡c z metody eliminacji Gaussa-Jordana.
W trakcie stosowania tej metody decydujemy kolejno, które zmienne b¦dziemy traktowa¢
jako zmienne bazowe. Układ równa«, jaki otrzymujemy po zako«czeniu procedury elimina-
cji, jest
defacto
układem postaci (1.7), jednak podczas jego tworzenia nie było konieczne
wyznaczanie macierzy
A
b
ani macierzy do niej odwrotnej.
5
[ Pobierz całość w formacie PDF ]