Układy równań liniowych niepełnego rzędu
POD- I NADOKREŚLONE
UKŁADY ALGEBRAICZNYCH RÓWNAŃ LINIOWYCH
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Budownictwo, studia I stopnia, semestr III
rok akademicki 2010/2011
Instytut L-5, Wydział Inżynierii Lądowej, Politechnika Krakowska
Ewa Pabisek
Adam Wosatko
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Układy równań pełnego rzędu
Dotychczas zajmowaliśmy się wyłącznie takimi układami równań
A x = b, w których macierze współczynników były kwadratowe A
n×n
.
*
A
x
n
n
b
=
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Definicja
Definicja podokreślnego układu równań
Układy równań o macierzach
A
m×n
, gdzie
m < n
, nazywamy
podokreślonymi
.
b
x
m
n
*
A
=
Układ równań o macierzy podokreślonej charakteryzuje się przede wszystkim
tym, że liczba równań m jest mniejsza od liczby niewiadomych n. Zatem
jest oczywiste, że rozwiązanie w takim przypadku
nie może być jednoznaczne
i należy oczekiwać, że niektóre z niewiadomych pozostaną nieokreślone tzn.,
że mogą przybierać dowolne wartości.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Sposób rozwiązania
Metoda Gaussa-Jordana
dla podokreślonych układów równań
Załóżmy, że zadanie można rozwiązać za pomocą metody
Gaussa-Jordana. Układ równań przekształcamy i doprowadzamy
do postaci:
=
x
*
b
0
m
n
I
A
0
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Sposób rozwiązania
Metoda Gaussa-Jordana
dla podokreślonych układów równań
Przekształcony układ równań możemy zapisać w następujący sposób:
I x
1
+ A
0
x
2
= b
0
n − m
x
m+1
x
m+2
..
.
x
n
x
m
x
1
x
2
I
..
.
m
m
m
=
+
b
0
A
0
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Postać rozwiązania
Rozwiązanie podokreślonego układu równań
Po przeniesieniu drugiego składnika lewej strony na stronę prawą
otrzymujemy poszukiwane rozwiązanie:
x
1
= b
0
− A
0
x
2
n − m
x
m+1
x
m+2
..
.
x
n
m
=
x
1
x
2
..
.
x
m
b
0
−
A
0
Wartości niewiadomych, które tworzą wektor
x
2
= {x
m+1
, x
m+2
, · · · x
n
}
mogą być przyjmowane dowolnie
, natomiast wartości niewiadomych
x
1
= {x
1
, x
2
, · · · x
m
}
są już jednoznacznie określone.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Postać rozwiązania
Interpretacja graficzna rozwiązania
Rozwiązaniem zadania nie jest więc jeden określony punkt x
?
∈ R
n
, ale
tzw. rozmaitość liniowa n − m wymiarowa X
?
n−m
∈ R.
W przypadku, gdy n − m = 1 rozwiązaniem jest pewna prosta,
gdy n − m = 2 pewna płaszczyzna itd.
x
3
x
1
x
2
x
1
x
2
x
3
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Podokreślone układy równań
Przykład 1
Rozwiązać układ równań:
4 x
1
+
16 x
2
−
14 x
3
=
−8
2 x
1
+
9 x
2
−
8 x
3
=
−5
4
16
−14
|
−8
2
9
−8
|
−5
→
1
4
−3.5
|
−2
0
1
−1
|
−1
→
→
1
0
0.5
|
2
0
1
−1
|
−1
Rozwiązanie:
x
1
= 2.0 − 0.5 x
3
x
2
= −1.0 + x
3
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Podokreślone układy równań
Przykład 1 cd.
x
1
= 2.0 − 0.5x
3
x
2
= −1.0 + x
3
Otrzymane rozwiązanie określa
rozmaitość jednowymiarową
czyli prostą
nie przechodzącą przez początek układu współrzędnych.
3.0
2.0
1.5
−1.0
1.0
(1.5, 0.0, 1.0)
4.0
(2.0, −1.0, 0.0)
(0.0, 3.0, 4.0)
x
3
x
2
x
1
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Podokreślone układy równań
Przykład 2
Rozwiązać układ równań:
2x
1
+
6x
2
+
3x
3
=
6
2
6
3
|
6
→ 1 3 1.5 | 3
Rozwiązanie:
x
1
= 3 − 3x
2
− 1.5x
3
Rozwiązaniem jest
rozmaitość liniowa dwuwymiarowa
czyli płaszczyzna nie przechodząca przez początek układu współrzędnych.
(0.0, 0.0, 2.0)
(3.0, 0.0, 0.0)
(0.0, 1.0, 0.0)
(0.0, 0.5, 1.0)
x
2
x
3
x
1
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Definicja
Definicja nadokreślnego układu równań
Nadokreślonym
układem równań A x = b nazywamy taki układ,
którego współczynniki tworzą macierz
A
m×n
, gdzie
m > n
.
=
x
b
m
n
A
*
Dla takiego układu liczba m równań jest większa od liczby
n niewiadomych. W przypadku układów nadokreślonych
możliwe są dwie sytuacje:
1
układ nie ma rozwiązania – jest sprzeczny,
2
układ ma rozwiązanie – nie jest sprzeczny.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Sposób rozwiązania
Metoda Gaussa-Jordana
dla nadokreślonych układów równań
Powstają w związku z tym dwa problemy:
1
jak rozstrzygnąć kwestię, czy układ ma rozwiązanie
i jak je ewentualnie znaleźć,
2
jak potraktować przypadek, gdy układ jest sprzeczny.
Po ponownym zastosowaniu algorytmu Gaussa-Jordana przekształcony
układ równań przyjmuje postać:
*
m
n
=
x
a)
b)
0
I
b
0
1
b
0
2
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Postać rozwiązania
Rozwiązanie nadokreślonego układu równań
Otrzymujemy dwa układy równań:
a)
I x = b
0
1
b)
0 = b
0
2
,
1
Jeżeli
b
0
2
= 0,
to rozwiązanie układu istnieje i ma postać
x = b
0
1
.
Spełnione są wszystkie równania.
2
Jeżeli
b
0
2
6= 0,
to układ równań jest sprzeczny, otrzymujemy bowiem
0 = b
0
2
6= 0
.
W przypadku, gdy układ równań jest sprzeczny mamy do czynienia
z sytuacją, w której nie istnieje punkt x ∈ R
n
o współrzędnych
spełniających wszystkie równania.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Postać rozwiązania
Interpretacja graficzna rozwiązania
W przypadku gdy x
?
∈ R
2
(wektor x oznaczymy
?
) to możemy podać
graficzną interpretację kolejnych równań w postaci odpowiednich prostych
na płaszczyźnie. Sprzeczność równań oznacza wtedy brak wspólnego
punktu przecięcia się reprezentujących je prostych na płaszczyźnie.
x
2
x
?
x
1
x
2
x
1
x
?
Można jednak postawić następujące pytanie:
Jaki punkt x
?
∈ R
2
jest najmniej odległy od wszystkich prostych?
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Pojęcie pseudorozwiązania
Punkt najmniej odległy od wszystkich prostych możemy uznać
za tzw.
pseudorozwiązanie
czyli za rozwiązanie rozumiane
w sensie uogólnionym (szerszym od dotychczasowego).
x
2
x
?
x
1
x
2
x
1
x
?
Dotychczasowe pojęcie rozwiązania staje się przy takim podejściu
przypadkiem szczególnym pseudorozwiązania - w którym odległość
punktu x
?
od wszystkich prostych wynosi zero.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Odległość punktu od prostych
Odległość r
i
punktu x ∈ R
n
od i-tej prostej staje się równa zeru, gdy jej
równanie zostaje spełnione przez współrzędne punktu x:
a
i 1
x
1
+ a
i 2
x
2
+ · · · + a
in
x
n
≡ b
i
,
i = 1, 2, . . . , m
Jako umowną odległość możemy przyjąć wielkość określoną
w następujący sposób:
r
i
= a
i 1
x
1
+ a
i 2
x
2
+ · · · + a
in
x
n
− b
i
,
i = 1, 2, . . . , m
czyli tzw.
residuum i-tego równania
.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Residdum - odległość punktu od prostych
Umowna odległość punktu x od wszystkich prostych może być w tym
przypadku określona np. wzorem:
R = r
2
1
+ r
2
2
+ · · · + r
2
m
,
m > n
x
2
x
?
x
1
x
2
x
1
x
?
R
=
0
R 6
=
0
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Przypadek dla 3 równań
Jeśli założymy m = 3 (liczba równań) oraz n = 2 (liczba niewiadomych) to:
r
i
= a
i 1
x
1
+ a
i 2
x
2
− b
i
przyjmując i = 1, 2, 3 otrzymujemy:
r
1
= a
11
x
1
+ a
12
x
2
− b
1
r
2
= a
21
x
1
+ a
22
x
2
− b
2
r
3
= a
31
x
1
+ a
32
x
2
− b
3
(1)
Funkcja R = r
2
1
+ r
2
2
+ r
2
3
osiąga minimum gdy:
∂R
∂x
1
= 2 (a
11
r
1
+ a
21
r
2
+ a
31
r
3
) = 0
∂R
∂x
2
= 2 (a
12
r
1
+ a
22
r
2
+ a
32
r
3
) = 0
(2)
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Przypadek dla 3 równań
Po podstawieniu (1) do (2) otrzymujemy:
(a
11
a
11
+ a
21
a
21
+ a
31
a
31
) x
1
+ (a
11
a
12
+ a
21
a
22
+ a
31
a
32
) x
2
= a
11
b
1
+ a
21
b
2
+ a
31
b
3
(a
12
a
11
+ a
22
a
21
+ a
32
a
31
) x
1
+ (a
12
a
12
+ a
22
a
22
+ a
32
a
32
) x
2
= a
12
b
1
+ a
22
b
2
+ a
32
b
3
czyli ostatecznie układ 2 równań z 2 niewiadomymi:
s
11
x
1
+ s
12
x
2
= t
1
s
21
x
1
+ s
22
x
2
= t
2
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Uogólnienie
Dla przypadku ogólnego można otrzymać następujący układ równań:
∂R
∂x
k
=
∂
∂x
k
(
m
X
i =1
r
2
i
) =
m
X
i =1
∂r
2
i
∂x
k
= 2
m
X
i =1
r
i
∂r
i
∂x
k
=
2
m
X
i =1
a
ik
(a
i 1
x
1
+ a
i 2
x
2
+ · · · + a
in
x
n
) =
2 (s
k1
x
1
+ s
k2
x
2
+ · · · + s
kn
x
n
− t
k
) = 0
(3)
w którym
s
kj
=
m
X
i =1
a
ik
a
ij
,
t
k
=
m
X
i =1
a
ik
b
i
,
k, j = 1, 2, . . . , n,
lub w zapisie macierzowym:
S = A
T
A,
t = A
T
b.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Poszukiwanie pseudorozwiązania
Uogólnienie
Komplet warunków (3) koniecznych istnienia ekstremum funkcji R
przybiera więc postać zwykłego układu równań algebraicznych (n × n):
∂R
∂x
1
= s
11
x
1
+ s
12
x
2
+ · · · + s
1n
x
n
= t
1
∂R
∂x
2
= s
21
x
1
+ s
22
x
2
+ · · · + s
2n
x
n
= t
2
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
∂R
∂x
n
= s
n1
x
1
+ s
n2
x
2
+ · · · + s
nn
x
n
= t
n
lub
S x = t.
Pseudorozwiązaniem wyjściowego, nadokreślonego układu równań jest
rozwiązanie powyższego układu i będziemy nazywać go rozwiązaniem
w sensie metody najmniejszych kwadratów.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 1
Rozwiązać nadokreślony układ równań:
x
1
+
2x
2
=
3
−2x
1
+
4x
2
=
4
x
1
+
2x
2
=
5
Stosujemy algorytm Gaussa-Jordana
1
2
|
3
−2
4
|
4
1
2
|
5
→
1
2
|
3
0
8
|
10
0
0
|
2
→
1
2
|
3
0
1
|
1.25
0
0
|
2
→
1
0
|
0.5
0
1
|
1.25
0
0
|
2
→
x
?
1
= 0.5,
x
?
2
= 1.25,
0 = 2(!!)
Układ równań jest sprzeczny (0 6= 2) tzn. że obliczone niewiadome
nie spełniają wszystkich równań. W związku z tym szukamy
pseudorozwiązania w sensie metody najmniejszych kwadratów.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 1 cd.
S = A
T
A =
1
−2
1
2
4
2
1
2
−2
4
1
2
=
6
−4
−4
24
t = A
T
b =
1
−2
1
2
4
2
3
4
5
=
0
32
S x = t →
6
−4
−4
24
x
1
x
2
=
0
32
→
(
x
?
1
= 1.0
x
?
2
= 1.5
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 1 cd.
S x = t →
6
−4
−4
24
x
1
x
2
=
0
32
→
(
x
?
1
= 1.0
x
?
2
= 1.5
3.0
5.0
1.0
1.5
−2.0
1.0
2.5
x
?
x
1
x
2
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 2
Rozwiązać nadokreślony układ równań:
x
1
+
2x
2
=
3
−2x
1
+
4x
2
=
4
x
1
+
2x
2
=
3
Stosujemy algorytm Gaussa-Jordana:
1
2
|
3
−2
4
|
4
1
2
|
3
→
1
2
|
3
0
8
|
10
0
0
|
0
→
1
2
|
3
0
1
|
1.25
0
0
|
0
→
1
0
|
0.5
0
1
|
1.25
0
0
|
0
→
x
?
1
= 0.5, x
?
2
= 1.25, 0 = 0(!!)
Układ równań nie jest sprzeczny tzn. że obliczone niewiadome
spełniają wszystkie równania.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 2 cd.
Poszukajmy jednak pseudorozwiązania:
S = A
T
A =
1
−2
1
2
4
2
1
2
−2
4
1
2
=
6
−4
−4
24
t = A
T
b =
1
−2
1
2
4
2
3
4
3
=
−2
28
S x = t →
6
−4
−4
24
x
1
x
2
=
−2
28
→
(
x
?
1
= 0.5
x
?
2
= 1.25
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Nadokreślone układy równań
Przykład 2 cd.
S x = t →
6
−4
−4
24
x
1
x
2
=
−2
28
→
(
x
?
1
= 0.5
x
?
2
= 1.25
3.0
−2.0
1.0
1.25
0.5
1.5
x
2
x
1
x
?
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Układy równań liniowych niepełnego rzędu
Rozważane dotychczas układy równań miały tę wspólną cechę,
że macierze ich współczynników A
m×n
były pełnego rzędu.
Własność ta charakteryzuje taką strukturę macierzy, dzięki której zawsze
istnieje conajmniej jeden jej niezerowy minor (podwyznacznik) stopnia
k = min(n, m).
W tym przypadku wszystkie wiersze macierzy podokreślonej (k = m),
lub wszystkie kolumny macierzy nadokreśloej (k = n), były liniowo
niezależne.
Ta własność macierzy A
m×n
pozwoliła na dokonanie przekształceń
za pomocą algorytmu Gaussa-Jordana.
Analizowanie i rozwiązywanie układów równań niepełnego rzędu wymaga,
w przypadku ogólnym, stosowania metody Gaussa-Jordana z pełnym
wyborem elementów podstawowych (przestawianie wierszy i kolumn
macierzy A).
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 1
Dany jest układ równań:
x
1
+
2x
2
=
4
x
1
+
2x
2
=
6
x
1
+
2x
2
=
8
Stosujemy algorytm Gaussa-Jordana:
1
2
|
4
1
2
|
6
1
2
|
8
→
1
2
|
4
0
0
|
2
0
0
|
4
.
Skąd wynika, że macierz A jest niepełnego rzędu: rz = 1, k = 2,
a układ równań jest sprzeczny: 0=2, 0=4.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 1 cd.
Celem znalezienia pseudorozwiązania obliczamy:
S = A
T
A =
1
1
1
2
2
2
1
2
1
2
1
2
=
3
6
6
12
,
t = A
T
b =
1
1
1
2
2
2
4
6
8
=
18
36
S x = t →
3
6
6
12
x
1
x
2
=
18
36
→
(
x
?
1
= 6.0 − 2x
2
x
?
2
= 0.0
Otrzymane rozwiązanie jest rozmaitością jednowymiarową:
x =
x
1
x
2
,
x
?
1
= 6 − 2x
2
.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 1 cd.
Otrzymane rozwiązanie jest rozmaitością jednowymiarową:
x =
x
1
x
2
,
x
?
1
= 6 − 2x
2
.
3.0
4.0
2.0
4.0
6.0
8.0
x
1
x
2
x
?
1
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 2
Rozważmy układ równań:
x
1
+
2x
2
+
3x
3
=
1
x
1
+
2x
2
+
3x
3
=
2
Stosujemy algorytm Gaussa-Jordana:
1
2
3
|
1
1
2
3
|
2
→
1
2
3
|
1
0
0
0
|
1
.
Również i tym razem macierz A jest niepełnego rzędu,
rz = 1, k = 2, a układ jest sprzeczny: 0=1.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 2 cd.
Wyznaczmy pseudorozwiązanie:
S = A
T
A =
1
1
2
2
3
3
1
2
3
1
2
3
=
2
4
6
4
8
12
6
12
18
,
t = A
T
b =
1
1
2
2
3
3
1
2
=
3
6
9
.
S x = t →
2
4
6
4
8
12
6
12
18
x
1
x
2
x
3
=
3
6
9
→
x
?
1
+ 2x
2
+ 3x
3
= 1.5,
0 = 0
0 = 0
stąd:
x
?
1
= 1.5 − 2x
2
− 3x
3
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Układy równań liniowych niepełnego rzędu
Przykłady
Układy równań liniowych niepełnego rzędu
Przykład 2 cd.
x
?
1
= 1.5 − 2x
2
− 3x
3
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
000000000000000000
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
111111111111111111
x
2
x
3
x
1
x
?
1
MATEMATYKA STOSOWANA I METODY NUMERYCZNE