Rozwiązywanie układów liniowych
Układ równań liniowych możemy zapisać w postaci macierzowej
a11 a12 a13 ... a1 j ... a1n îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ x1 b1
ïÅ‚a a22 a23 ... a2 ... a2n śł
ïÅ‚x śł ïÅ‚b śł
21 j
2 2
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
AX = B W postaci rozwiniętej
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
=
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
równania te mają postać
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚an1 an2 an3 ... anj ... ann śł
ïÅ‚xn śł ïÅ‚bn śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
Podstawowe informacje o macierzach
Macierz jednostkowa
Macierz diagonalna
1 0 0 ... 0 ... 0
îÅ‚ Å‚Å‚
ïÅ‚0 1 0 ... 0 ... 0śł
a11 0 0 ... 0 ... 0
îÅ‚ Å‚Å‚
ïÅ‚ śł
ïÅ‚ śł
0 a22 0 ... 0 ... 0
ïÅ‚0 1 0śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ 0 a33 0 śł
I = 1
ïÅ‚... śł
ïÅ‚ śł
I = ... ...
ïÅ‚ śł
1
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
aii
1
ïÅ‚ śł
ïÅ‚ śł
...
ïÅ‚0 0 0 ... 0 ... 1śł
ïÅ‚ śł
ðÅ‚ ûÅ‚
ïÅ‚
0 0 0 ... 0 ... ann śł
ðÅ‚ ûÅ‚
Rozwiązywanie układów liniowych
Macierz symetryczna
a11 a12 a13 ... a1 j ... a1n
îÅ‚ Å‚Å‚
ïÅ‚a a22 a23 ... a2 ... a2nśł
12 j
ïÅ‚ śł
ïÅ‚a13 a3n śł
aij = a
W postaci rozwiniętej
ji
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚a1n a2n a3n ... a jn ... ann śł
ðÅ‚ ûÅ‚
Macierze symetryczne bardzo często występują w zagadnieniach technicznych tzn.
Macierze sztywności, bezwładności w dynamice konstrukcji, w obliczeniach MES
Rozwiązywanie układów liniowych
Macierz trójkątna górna Macierz trójkątna dolna
a11 a12 a13 ... a1i ... a1n a11 0 0 ... 0 ... 0
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚a a22 0 ... 0 ... 0 śł
0 a22 a23 ... a2i ... a2n śł
21
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ 0 a33 0 śł ïÅ‚a31 a33 0 śł
ïÅ‚ śł ïÅ‚ śł
U = ... ... L = ... ...
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
aii aii
ïÅ‚ śł ïÅ‚ śł
... ...
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ ïÅ‚an1 an2 an3 ... ani ... ann śł
0 0 0 ... 0 ... ann śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Twierdzenie o rozkładzie trójkątnym
Niech A będzie macierzą n x n. Niech Ak oznacza macierz kxk utworzoną z k pierwszych wierszy i kolumn z
A. Jeśli det(Ak) `" 0 (k = 1,2,...,n-1), to istnieje jedyny rozkład A = LU na czynniki takie, że macierz L = (mij)
jest macierzą trójkątna dolną i ma elementy mij równe 1 (i = 1,2, ....,n) a macierz U jest macierzą trójkątną
górną.
Rozwiązywanie układów liniowych
Macierz pasmowa (wstęgowa)
a11 a12 a13 a14 0 ... 0
îÅ‚ Å‚Å‚
ïÅ‚a a22 a23 ... a2i ... 0 śł
21
ïÅ‚ śł
ïÅ‚a31 a32 a33 a34 0 śł
ïÅ‚ śł
W =
ïÅ‚a41 a42 a43 ... śł
ïÅ‚ śł
0 aii
ïÅ‚ śł
... ...
ïÅ‚ śł
ïÅ‚
0 0 0 ... 0 ... annśł
ðÅ‚ ûÅ‚
aij = 0, jeśeś j > i + p lub i > j + q
Szerokość wstęgi w = p + q + 1
Rozwiązywanie układów liniowych
Macierz pasmowa (wstęgowa) symetryczna
a11 a12 a13 a14 0 ... 0
îÅ‚ Å‚Å‚
ïÅ‚a a22 a23 ... a2i ... 0 śł
12
ïÅ‚ śł
ïÅ‚a13 a23 a33 a34 0 śł
ïÅ‚ śł
W =
ïÅ‚a14 a24 a34 ... śł
ïÅ‚ śł
0 aii
ïÅ‚ śł
... ...
ïÅ‚ śł
ïÅ‚
0 0 0 ... 0 ... annśł
ðÅ‚ ûÅ‚
aij = 0, jeśeś j > i + p lub i > j + p
Szerokość półpasma m = p - 1
Rozwiązywanie układów liniowych
Macierz pasmowa (wstęgowa)
Zapis tylko pasma
a11 a12 a13 a14 a15
îÅ‚ Å‚Å‚
ïÅ‚
a22 a23 a24 a25 a26 śł
ïÅ‚ śł
ïÅ‚ a33 a34 a35 a36 a37 śł
ïÅ‚
a44 a45 a46 a47 a48 śł
ïÅ‚ śł
ïÅ‚ śł
a55 a56 a57 a58 a59
ïÅ‚ śł
a66 a67 a69 a69 a6,10śł
ïÅ‚
ïÅ‚ śł
a77 a78 a79 a7,10 0
ïÅ‚ śł
a88 a89 a8,10 0 0
ïÅ‚ śł
ïÅ‚ śł
a99 a9,10 0 0 0
ïÅ‚ śł
0 0 0 0
ïÅ‚a śł
10,10
ðÅ‚ ûÅ‚
p
Rozwiązywanie układów liniowych
Macierz pasmowa (wstęgowa)
Zapis profilu macierzy
a11 a12 0 0 0 0 0
îÅ‚ Å‚Å‚
ïÅ‚a a22 a23 0 a25 0 a27śł
12
ïÅ‚ śł
ïÅ‚ 0 a23 a33 a34 a35 a36 0 śł
ïÅ‚
W = 0 0 a34 a44 a45 a46 a47śł
ïÅ‚ śł
ïÅ‚ śł
0 a25 a35 a45 a55 a56 a57
ïÅ‚ śł
0 0 a36 a46 a47 a66 a67śł
ïÅ‚
ïÅ‚
0 a27 0 a47 a57 a67 a77śł
ðÅ‚ ûÅ‚
Rozwiązywanie układów liniowych
a11
îÅ‚ Å‚Å‚
ïÅ‚a śł
22
Macierz pasmowa (wstÄ™gowa) ïÅ‚ śł
ïÅ‚a21śł
Zapis profilu macierzy
ïÅ‚ śł
ïÅ‚a33 śł
1
îÅ‚ Å‚Å‚
ïÅ‚ śł
a23
ïÅ‚ śł
2
ïÅ‚ śł
ïÅ‚ śł
K
ïÅ‚ śł
ïÅ‚ 4 śł
ïÅ‚a55 śł
ïÅ‚ śł
6
ïÅ‚ śł
ïÅ‚ śł
A = NMAX =
45
ïÅ‚a śł
ïÅ‚ śł
8
ïÅ‚a35 śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚12śł
ïÅ‚a śł
25
ïÅ‚16śł
ïÅ‚a66 śł
ïÅ‚ śł
ïÅ‚ śł
ðÅ‚17ûÅ‚
a56
ïÅ‚ śł
ïÅ‚a śł
46
ïÅ‚ śł
a36
ïÅ‚ śł
ïÅ‚ śł
K
ðÅ‚ ûÅ‚
Rozwiązywanie układów liniowych
Przykład przekształcenia macierzy współczynników układu równań liniowych do
macierzy trójkątnej górnej
Niech będzie dany układ równań liniowych. Pierwsze równanie zostanie podzielone przez pierwszy
współczynnik (5), następnie przemnożone przez pierwszy współczynnik drugiego równania (-4). Tak
przekształcone pierwsze równanie zostanie odjęte od drugiego. Podobnie pierwsze równanie zostanie
podzielone przez pierwszy współczynnik (5), następnie przemnożone przez pierwszy współczynnik
trzeciego równania (1) i odjęte o trzeciego równania.
Rozwiązywany układ równań
5 - 4 1 0 U1 0
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚U śł ïÅ‚1śł
2
ïÅ‚- 4 6 - 4 1 śł ïÅ‚ śł ïÅ‚ śł
=
ïÅ‚ 1 - 4 6 - 4śł ïÅ‚U3śł ïÅ‚0śł
ïÅ‚ śł ïÅ‚U śł ïÅ‚0śł
0 1 - 4 5
ðÅ‚ ûÅ‚ ðÅ‚ 4ûÅ‚ ðÅ‚ ûÅ‚
Pierwsze równanie zostanie podzielone następnie przemnożone przez pierwszy współczynnik
przez pierwszy współczynnik (5), drugiego równania (-4), i odjęte od drugiego
4 1 16 4
îÅ‚1 - îÅ‚ îÅ‚ 16 4 Å‚Å‚ 14 16
ëÅ‚ öÅ‚ îÅ‚0
0Å‚Å‚ *(-4) = 4 - 0Å‚Å‚
- 1Å‚Å‚
ïÅ‚ śł ïÅ‚- śł ïÅ‚- 4 - (-4) 6 - - 4 - ìÅ‚- ÷Å‚ 1- 0śł =
ïÅ‚ śł
5 5 5 5
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ 5 5 5 5
íÅ‚ Å‚Å‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
Rozwiązywanie układów liniowych
Pierwsze równanie zostanie podzielone następnie przemnożone przez pierwszy współczynnik
przez pierwszy współczynnik (5), trzeciego równania (1) o odjęte od trzeciego równania.
4 1 4 1
îÅ‚1 - îÅ‚1 îÅ‚ 4 1 Å‚Å‚ 16 29
ëÅ‚ öÅ‚ îÅ‚0
0Å‚Å‚ *(1) = - 0Å‚Å‚
- 4Å‚Å‚
ïÅ‚ śł ïÅ‚ śł ïÅ‚1-1 - 4 - ìÅ‚ - ÷Å‚ 6 - - 4 - 0śł = -
ïÅ‚ śł
5 5 5 5
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ 5 5 5 5
íÅ‚ Å‚Å‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
Otrzymujemy następujący układ równań
5 - 4 1 0
îÅ‚ Å‚Å‚
U1 0
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚0 14 16 1 śł
-
ïÅ‚U śł ïÅ‚1śł
ïÅ‚ śł
2
5 5
ïÅ‚ śł ïÅ‚ śł
=
ïÅ‚ śł
16 29
- 4śł ïÅ‚U3śł ïÅ‚0śł
ïÅ‚0 -
ïÅ‚U śł ïÅ‚0śł
5 5
ïÅ‚ śł
ðÅ‚ 4ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚0 1 - 4 5 ûÅ‚
Podobnie postępujemy
5 - 4 1 0
îÅ‚ Å‚Å‚
0
ïÅ‚0 14 16 1 śł U1 îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚
ïÅ‚ śł
-
1
ïÅ‚ śł
ïÅ‚U śł
5 5
ïÅ‚ śł
ïÅ‚
15 20śł ïÅ‚ 2śł ïÅ‚ 8 śł
=
-
ïÅ‚0 - 0 śł
ïÅ‚U3śł
7
ïÅ‚ śł
7 7
ïÅ‚ śł
ïÅ‚U śł
5
ïÅ‚ śł
ðÅ‚ 4ûÅ‚
ïÅ‚0 0 - 20 65 śł
ïÅ‚-
ðÅ‚ 14śł
ûÅ‚
ïÅ‚ śł
ðÅ‚ 7 14 ûÅ‚
Rozwiązywanie układów liniowych
5 - 4 1 0
NastÄ™pnie îÅ‚ Å‚Å‚
0
îÅ‚ Å‚Å‚
ïÅ‚0 14 16 1 śł U1 ïÅ‚1śł
îÅ‚ Å‚Å‚
-
ïÅ‚ śł
ïÅ‚U śł
5 5
ïÅ‚8śł
ïÅ‚
15 20śł ïÅ‚ 2śł ïÅ‚ śł
=
-
ïÅ‚0 - 0 śł
ïÅ‚U3śł
ïÅ‚7śł
7 7
ïÅ‚ śł
ïÅ‚U śł
ïÅ‚7śł
ðÅ‚ 4ûÅ‚
ïÅ‚0 0 0 5 śł
ïÅ‚6śł
ðÅ‚ ûÅ‚
ïÅ‚ śł
ðÅ‚ 6 ûÅ‚
Zastosowaną powyżej metodę nazywamy Metodą Eliminacji Gausa
Następnie możemy obliczyć wartości poszczególnych niewiadomych stosując
postępowanie odwrotne (zastępowanie powrotne)
7 6 7 15 8 20 7 8 7 20 7 8 28 36 12
U4 = = U3 = + U4,Ò! U3 = + = + = =
6 5 5 7 7 7 15 7 15 7 5 15 15 15 5
14 16 5 5 16 12 5 7 5 96 1 13
U2 = 1+ U3 -U4,Ò! U2 = + - = - - =
5 5 14 14 5 5 14 5 14 35 2 5
4 13 1 12 52 12 40 8
5U1 = 0 + 4U2 -U3 - 0,Ò! U1 = - = - = =
5 5 5 5 25 25 25 5
Rozwiązywanie układów liniowych
Powyższy schemat można zapisać następująco
Oznaczając przekształcone współczynniki jak poniżej
(1 (1 (1 (1) (1 (
Przyjmując, że
îÅ‚ Å‚Å‚ x1 îÅ‚ Å‚Å‚
a11) a12) a13) ... a1i ... a1n) îÅ‚ Å‚Å‚ b11)
ïÅ‚
(2 (2 ( (
0 a22) a23) ... a22) ... a2k )śł ïÅ‚x2śł ïÅ‚b(2)śł
i n 2
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
(3 (3) ( (
ïÅ‚ ïÅ‚b33) śł
ïÅ‚x3śł
0 a33) ... a3i ... a33) śł
n
ai(k ) = bi(k ) (1 d" k d" i d" n)
,n=+1
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
=
... ... ...
ïÅ‚ śł ïÅ‚ śł
ïÅ‚...śł
(
ïÅ‚ śł
ïÅ‚ śł
xi ïÅ‚bi(i) śł
aiii)
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
...
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
(n (
ïÅ‚
0 0 0 ... 0 ... ann)śł ïÅ‚xn śł ïÅ‚bnn)śł
ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Wtedy wzory można określić następująco. Eliminacje wykonuje się w n-1 krokach o numerach
(
aijk )
k = 1,2,... ,n-1. W k-tym kroku elementy dla j, j > k przekształca się według wzorów
(
aikk )
( ( (k
mik = , aijk+1) = aijk ) - mikakj )
(k
akk )
(i = k +1,k + 2,...n; j = k +1,k + 2,....n +1)