Równania liniowe
Układ równań
(0.0.1)
AX = B
A ∈ M (m, n), B ∈ R
m
układ m równań o n niewiadomych.
X =
x
1
..
.
x
n
∈ M (n, 1), B =
b
1
..
.
b
m
∈ M (m, 1),
a
11
· · ·
a
1n
· · ·
· · ·
· · ·
a
m1
· · ·
a
mn
x
1
..
.
x
n
=
b
1
..
.
b
m
a
11
x
1
+ · · · + a
1n
x
n
=
b
1
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
m1
x
1
+ · · · + a
mn
x
n
=
b
m
wektor X ∈ R
n
- niewiadoma.
A = (a
ij
) - macierz układu
b
1
, . . . , b
m
- wyrazy wolne
B - kolumna wyrazów wolnych
Rozwiązanie - każdy wektor X
0
∈ R
n
dla którego
AX
0
= B.
Układ jest sprzeczny, jeśli nie istnieje rozwiązanie (zbiór rozwiązań
jest zbiorem pustym).
Równanie jednorodne
(0.0.2)
AX = Θ
(B = θ).
Równanie 0.0.2 nazywamy równaniem jednorodnym stowarzy-
szonym z równaniem 0.0.1.
Równanie jednorodne zawsze posiada co najmniej jedno rozwiązanie
- wektor Θ.
1
2
Przykład
x
1
− x
3
+ x
4
+ 5x
5
=
2
x
2
− x
4
+ x
6
= −1
Macierz układu:
A =
1 0 −1
1 5 0
0 1
0 −1 0 1
Zapis macierzowy:
1 0 −1
1 5 0
0 1
0 −1 0 1
x
1
x
2
x
3
x
4
x
5
x
6
=
2
−1
Równanie jednorodne stowarzyszone:
x
1
− x
3
+ x
4
+ 5x
5
= 0
x
2
− x
4
+ x
6
= 0
1 0 −1
1 5 0
0 1
0 −1 0 1
x
1
x
2
x
3
x
4
x
5
x
6
=
0
0
RÓWNANIA LINIOWE
3
Układ Cramera
A ∈ M
o
(n), X, B ∈ M (n, 1)
(0.0.3)
AX = B
a
11
· · ·
a
1n
· · ·
· · ·
· · ·
a
n1
· · ·
a
nn
x
1
..
.
x
n
=
b
1
..
.
b
n
a
11
x
1
+ · · · + a
1n
x
n
=
b
1
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
n1
x
1
+ · · · + a
nn
x
n
=
b
n
Ilość równań równa jest ilości niewiadomych.
Macierz A jest kwadratowa i odwracalna.
Dla każdego wektora B, układ Cramera posiada dokładnie jedno
rozwiązanie:
X = A
−1
B
Z własności macierzy, wyznacznika i definicji rzędu wynika, że
• układ 0.0.3 jest układem Cramera wtedy i tylko wtedy gdy
rzA = n
• układ 0.0.3 jest układem Cramera wtedy i tylko wtedy gdy
|A| 6= 0
Macierz układu Cramera wyznacza wzajemnie jednoznaczne przekształ-
cenie liniowe przestrzeni R
n
w siebie.
Rozwiązanie układu Cramera 0.0.3:
A = [A
1
. . . A
j
. . . A
n
] ∈ M
o
(n) - macierz układu,
dla j = 1, . . . , n
A
j ozn
= [A
1
. . . B . . . A
n
]
B jest j-tą kolumną.
Rozwiązaniem układu 0.0.3 jest wektor X =
x
1
..
.
x
n
, gdzie
dla j = 1, . . . , n
x
j
=
|A
j
|
|A|
4
Przykład
x
1
− x
2
+ x
3
=
0
−x
1
+ x
2
+ x
3
=
1
2x
1
+ x
2
− x
3
= −1
A =
1 −1
1
−1
1
1
2
1 −1
,
|A| = −6
A
1
=
0 −1
1
1
1
1
−1
1 −1
,
A
1
= 2
A
2
=
1
0
1
−1
1
1
2 −1 −1
,
A
2
= −1
A
3
=
1 −1
0
−1
1
1
2
1 −1
,
|A| = −3
x
1
= −
1
3
,
x
2
=
1
6
,
x
3
=
1
2
,
RÓWNANIA LINIOWE
5
Układ jednorodny
A ∈ M (m, n), rzA = k
AX = Θ
a
11
x
1
+ . . . + a
1n
x
n
=
0
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
m1
x
1
+ . . . + a
mn
x
n
=
0
Zbiór rozwiązań:
• jest przestrzenią wektorową
X
1
, X
2
- rozwiązania, to X
1
+ X
2
rozwiązanie
X- rozwiązanie, to ∀a ∈ R aX rozwiązanie
X
1
, . . . , X
p
- rozwiązania, to ∀a
1
, . . . , a
p
∈ R
p
X
i=1
a
i
X
i
rozwiązanie
• wymiar przestrzeni rozwiązań n − k.
Aby rozwiązać jednorodny układ równań wyznaczamy bazę przestrzeni
rozwiązań:
X
1
, . . . , X
n−k
n − k liniowo niezależnych wektorów, które są rozwiązaniami.
Przestrzeń rozwiązań:
(
n−k
X
i=1
a
i
X
i
: a
1
, . . . , a
n−k
∈ R
)
Jeśli n > m, (ilość niewiadomych jest większa od ilości równań), to
istnieje rozwiązanie niezerowe.
n − k ≥ n − m > 0.
6
Algorytm 1
wyznaczania wektorów X
1
, . . . , X
n−k
(1) Wykreślamy z macierzy A liniowo zależne wiersze.
Otrzymujemy macierz [D
1
. . . D
k
. . . D
n
] ∈ M (k, n) oraz układ
k równań:
a
11
x
1
+ . . . + a
1n
x
n
=
0
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
k1
x
1
+ . . . + a
kn
x
n
=
0
(2) Dla i = 1, ..., n − k podstawiamy:
x
k+i
= 1
oraz dla pozostałych czyli j 6= i, j = 1, ..., n − k
x
k+j
= 0
Otrzymujemy n − k układów równań:
a
11
x
1
+ . . . + a
1k
x
k
=
−a
1k+i
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
k1
x
1
+ . . . + a
kk
x
k
=
−a
kk+i
(3) Oznaczamy macierz D = [D
1
. . . D
k
] - jest to macierz kwadra-
towa o wyznaczniku różnym od 0:
D = [D
1
. . . D
k
] ∈ M
o
(k)
(Macierz D powstaje z macierzy A przez wykreślenie liniowo
zależnych kolumn i wierszy. Układy równań z punktu 2. są
układami Cramera)
RÓWNANIA LINIOWE
7
(4) Rozwiązujemy n − k układów Cramera:
DX = −D
k+i
dla i = 1, . . . , n − k.
X
i
=
x
i
1
..
.
x
i
k
- rozwiazanie i-tego układu
(5) Definiujemy n − k wektorów:
X
1
=
x
1
1
..
.
x
1
k
1
..
.
0
=
X
1
1
..
.
0
. . . . . . . . . . . .
X
i
=
x
i
1
..
.
x
i
k
0
..
.
1
..
.
0
=
X
i
0
..
.
1
..
.
0
. . . . . . . . . . . .
X
n−k
=
x
n−k
1
..
.
x
n−k
k
0
..
.
1
=
X
n−k
0
..
.
1
• każdy z tych wektorów jest rozwiązaniem układu wyjściowego
0.0.1
• jest to układ liniowo niezależny
X
1
, . . . , X
n−k
- baza przestrzeni rozwiązań.
Dowolne rozwiazanie - ogólne jest w postaci:
X =
n−k
X
i=1
a
i
X
i
8
Przykład
(1)
x
1
+ 2x
2
= 0
−x
1
− 2x
2
= 0
A =
1
2
−1 −2
, rzA = 1, n − k = 1
D = [1], |D| = 1, X = [x
1
], D
2
= [2]
x
1
= −2, DX = −D
2
,
X = [−2]
X =
−2
1
Dowolne rozwiazanie:
X =
−2a
a
Przestrzeń rozwiązań:
{(−2a, a) : a ∈ R}
RÓWNANIA LINIOWE
9
(2)
x
1
− x
3
+ 5x
5
= 0
x
2
− x
4
+ x
6
= 0
A =
1 0 −1
0 5 0
0 1
0 −1 0 1
, rzA = 2,
n − k = 6 − 2 = 4
D =
1 0
0 1
, |D| = 1,
X =
x
1
x
2
D
3
=
−1
0
, D
4
=
0
−1
, D
5
=
5
0
, D
6
=
0
1
x
1
= 1
x
2
= 0
DX = −D
3
,
X
1
=
1
0
x
1
= 0
x
2
= 1
DX = −D
4
,
X
2
=
0
1
x
1
= −5
x
2
=
0
DX = −D
5
,
X
3
=
−5
0
x
1
=
0
x
2
= −1
DX = −D
6
,
X
1
=
0
−1
X
1
=
1
0
1
0
0
0
, X
2
=
0
1
0
1
0
0
, X
3
=
−5
0
0
0
1
0
, X
4
=
0
−1
0
0
0
1
Dowolne rozwiązanie:
X = aX
1
+ bX
2
+ cX
3
+ dX
4
=
a − 5c
b − d
a
b
c
d
Przestrzeń rozwiązań:
{(a − 5c, b − d, a, b, c, d) : a, b, c, d ∈ R}
10
(3)
x
1
+ 2x
2
− x
3
= 0
−x
1
− 2x
2
= 0
−x
3
= 0
A =
1
2 −1
−1 −2
0
0
0 −1
, |A| = 0, rzA = 2
n − k = 3 − 2 = 1
D =
1 −1
−1
0
, |D| = −1,
D
2
=
2
−2
,
X =
x
1
x
3
x
1
− x
3
= −2
−x
1
=
2
DX = −D
2
x
1
=
−2 −1
2
0
|D|
= −2, x
3
=
1 −2
−1
2
|D|
= 0, X =
−2
1
0
Dowolne rozwiązanie
X =
−2a
a
0
Przestrzeń rozwiązań:
{(−2a, a, 0) : a ∈ R}
Układ dowolny
A ∈ M (m, n), rzA = k
AX = B
a
11
x
1
+ . . . + a
1n
x
n
=
b
1
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a
m1
x
1
+ . . . + a
mn
x
n
=
b
m
b
A = [A B] = [A
1
. . . A
n
B] ∈ M (m, n + 1) - macierz uzupełniona
Układ posiada rozwiązanie (jest niesprzeczny) wtedy i tylko
wtedy gdy rzA = rz b
A.
RÓWNANIA LINIOWE
11
Zbiór rozwiązań:
(
X
0
+
n−k
X
i=1
a
i
X
i
: a
1
, . . . , a
n−k
∈ R
)
(1) X
1
, . . . , X
n−k
- liniowo niezależne wektory, które są rozwiąza-
niami układu jednorodnego stowarzyszonego: AX = Θ,
(2) X
0
- jedno, dowolnie wybrane rozwiązanie układu: AX = B
Wektory X
1
, . . . , X
n−k
wyznaczamy zgodnie z algorytmem podanym
dla układów jednorodnych.
12
Algorytm
(1) Wyznaczamy rzA i rz b
A
(a) jeśli rz b
A > rzA, to układ jest sprzeczny
(b) jeśli rz b
A = rzA, to przechodzimy do punktu2
(2) Wyznaczamy rozwiązania X
1
, . . . , X
n−k
układu jednorodnego
stowarzyszonego, zgodnie z algorytmem 1
(3) wyznaczamy X
0
:
Rozwiązujemy układ Cramera:
DX = B
D - macierz wyznaczona według punktu 1 i 2 algorytmu 1
X
0
=
x
0
1
..
.
x
0
k
-rozwiązanie
(4)
X
0
=
x
0
1
..
.
x
0
k
0
..
.
0
=
X
0
0
..
.
0
szczególne rozwiązanie danego układu.
Rozwiązanie dowolne:
X = X
0
+
n−k
X
i=1
a
i
X
i
RÓWNANIA LINIOWE
13
Przykład :
(1)
x
1
+ 2x
2
= 1
−x
1
− 2x
2
= 2
A =
1
2
−1 −2
, rzA = 1, b
A =
1
2 1
−1 −2 2
, rz b
A = 2
rz b
A > rzA - układ sprzeczny
(2)
x
1
+ 2x
2
=
1
−x
1
− 2x
2
= −1
A =
1
2
−1 −2
, rzA = 1, b
A =
1
2
1
−1 −2 −1
, rz b
A = 1,
rz b
A = rzA, n − k = 1
układ jednorodny stowarzyszony jest rozwiązany w przykła-
dzie 1(wyk-11).
D = [1], |D| = 1
X
1
=
−2
1
Szukamy rozwiązania szczególnego
- przyjmujemy x
2
= 0, wtedy
x
1
= 1
X
0
=
1
0
Dowolne rozwiazanie:
X = X
0
+ aX
1
=
1 − 2a
a
Zbiór rozwiązań:
{(1 − 2a, a) : a ∈ R}
14
(3)
x
1
− x
3
+ 5x
5
= −1
x
2
− x
4
+ x
6
=
1
A =
1 0 −1
0 5 0
0 1
0 −1 0 1
, rzA = 2,
b
A =
1 0 −1
0 5 0 −1
0 1
0 −1 0 1
1
, rz b
A = 2,
rz b
A = rzA , n − k = 6 − 2 = 4
Rozwiązania układu jednorodnego stowarzyszonego z przykładu 1
(wyk-11)
X = aX
1
+ bX
2
+ cX
3
+ dX
4
=
a − 5c
b − d
a
b
c
d
szukamy rozwiązania szczególnego
przyjmujemy: x
3
= x
4
= x
5
= x
6
= 0
D =
1 0
0 1
, |D| = 1,
X
0
=
x
0
1
x
0
2
x
1
= −1
x
2
=
1
X
0
=
−1
1
0
0
0
0
Dowolne rozwiazanie:
X = X
0
+ aX
1
+ bX
2
+ cX
3
+ dX
4
=
a − 5c − 1
b − d + 1
a
b
c
d
Zbiór rozwiązań:
{(a − 5c − 1, b − d + 1, a, b, c, d) : a, b, c, d ∈ R}
RÓWNANIA LINIOWE
15
(4)
x
1
+ 2x
2
− x
3
=
1
−x
1
− 2x
2
= −1
−x
3
=
2
A =
1
2 −1
−1 −2
0
0
0 −1
, |A| = 0, rzA = 2,
b
A =
1
2 −1
1
−1 −2
0 −1
0
0 −1
2
,
1 −1
1
−1
0 −1
0 −1
2
= −2
rz b
A = 3 > rzA
Uklad sprzeczny
16
(5)
x
1
+ 2x
2
− x
3
=
1
−x
1
− 2x
2
= −1
−x
3
=
0
b
A =
1
2 −1
1
−1 −2
0 −1
0
0 −1
0
, rz b
A = 2 = rzA
Rozwiązania układu jednorodnego stowarzyszonego
X = aX
1
=
−2a
a
0
Rozwiązanie szczególne
D =
1 −1
−1
0
, |D| = −1, X =
x
1
x
3
x
1
− x
3
=
1
−x
1
= −1
x
0
1
=
1 −1
−1
0
|D|
= 1, x
0
3
=
1
1
−1 −1
|D|
= 0,
X
0
=
1
0
0
Dowolne rozwiazanie:
X = X
0
+ aX
1
=
1 − 2a
a
0
Zbiór rozwiązań:
{(1 − 2a, a, 0) : a ∈ R}
RÓWNANIA LINIOWE
17
Algorytm rozwiązywania układu równań:
-
nie
układ sprzeczny
D
b
b
b
b
b
b
b
"
"
"
"
"
"
"
b
b
b
b
b
b
b
"
"
"
"
"
"
"
rzA = rz b
A
?
tak
X
0
+
n−m
X
i=1
a
i
X
i
H
H
H
H
H
H
j
9
=
@
@
@
@
@
@
@
R
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
j
DX
1
= −D
k+1
DX
n−k
= −D
n
DX
0
= B
. . . . . . . . . . . . . . .