UKA
ADY RÓWNAC

LINIOWYCH
- Metody dokładne
Układy równań liniowych
Rozpatruje się układ n równań liniowych zawierających n
niewiadomych:
a11x1 + a12x2 + ... + a1nxn = b1
Å„Å‚
ôÅ‚
a21x1 + a22x2 + ... + a2nxn = b2
ôÅ‚
òÅ‚
.............................................
ôÅ‚
ôÅ‚
an1x1 + an2x2 + ... + annxn = bn
ół
który można zapisać w postaci macierzowej:
A Å" X = B
2
Układy równań liniowych
gdzie:
a11 a12 ... a1n x1 b1
îÅ‚Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚x śł ïÅ‚b śł
a21 a22 ... a2n śł
2 2
ïłśłX = ïÅ‚ śł ïÅ‚ śł
A = B =
ïłśł ïÅ‚ śł ïÅ‚ śł
...................
ïÅ‚ ïÅ‚x śł ïÅ‚b śł
an1 an2 ... ann śł
ðÅ‚ûÅ‚ ðÅ‚ n ûÅ‚ ðÅ‚ n ûÅ‚
A  macierz główna układu
X  wektor niewiadomych
B  wektor wyrazów wolnych
3
Układy równań liniowych
Założenie:
Układ równań jest oznaczony, (tzn. posiada jedno rozwiązanie)
Macierz główna układu równań A nie jest osobliwa (wyznacznik
tej macierzy jest różny od zera)
4
Zastosowanie macierzy
odwrotnej
Zastosowanie macierzy odwrotnej
Układ równań:
A Å" X = B
Można rozwiązać obliczając macierz odwrotną do macierzy
głównej układu:
X = A-1 Å"B
6
Układ równań, w którym tylko
główna przekątna macierzy A
ma elementy niezerowe
Układ równań z niezerową główną przekątną macierzy A
a11x1 = b1
Å„Å‚
ôÅ‚
a22x2 = b2
ôÅ‚
òÅ‚
...
ôÅ‚
ôÅ‚
annxn = bn
ół
Algorytm:
bi
xi = , aii `" 0, i =1, 2,..., n
aii
8
Trójkątny układ równań
Trójkątny układ równań
a11x1 + a12x2 +...+ a1nxn = b1
Å„Å‚
ôÅ‚
a22x2 +...+ a2nxn = b2
ôÅ‚
òÅ‚
...
ôÅ‚
ôÅ‚
annxn = bn
ół
10
Trójkątny układ równań
Algorytm:
bn
xn =
ann
n
bi - aisxs
"
s=i+1
xi = , i = n -1,n - 2,...,1
aii
Przy spełnionym warunku:
aii `" 0, i =1,2,...,n
11
Trójkątny układ równań
Przykład
Rozwiązać trójkątny układ równań:
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
ïÅ‚ śłïÅ‚ śł
4 1 3 2
x1
îÅ‚ Å‚Å‚
ïÅ‚ śłïÅ‚1 śł
ïÅ‚x śł
ïÅ‚0 15 1 śłïÅ‚ śł
Å"=
2
ïÅ‚ śł
ïÅ‚ 4 4śłïÅ‚ 2śł
ïÅ‚x3 śł
ïÅ‚ śł ðÅ‚ ûÅ‚ ïÅ‚8 śł
1
0 0
ïÅ‚ śłïÅ‚ śł
ðÅ‚ 33
ûÅ‚ðÅ‚ ûÅ‚
12
Trójkątny układ równań
8
b3
3
=
x3 =
= 8
1
a33
3
1 1
- Å"8
b2 - a23x3
2
2 4
x2 =
=
=-
15
a22
5
4
2
öÅ‚
2 -1Å"ëÅ‚ - - 3Å"8
ìÅ‚÷Å‚
b1 - a12x2 - a13x3 = 5 27
íÅ‚Å‚Å‚
x1 = =-
4
a11 5
13
Wzory Cramera
(metoda wyznacznikowa)
Wzory Cramera (metoda wyznacznikowa)
Układ równań liniowych zapisujemy w postaci macierzowej.
Przez W oznaczamy macierz główną układu równań, czyli:
a11 a12 ... a1n
îÅ‚ Å‚Å‚
ïÅ‚
a21 a22 ... a2n śł
ïÅ‚ śł
W =
ïÅ‚ śł
...................
ïÅ‚
an1 an2 ... ann śł
ðÅ‚ ûÅ‚
W
Obliczamy wyznacznik tej macierzy:
15
Wzory Cramera (metoda wyznacznikowa)
Jeżeli |W| `" 0 to obliczamy wyznaczniki macierzy pomocniczych:
a11 b1 ... a1n
b1 a12 ... a1n
a21 b2 ... a2n
b2 a22 ... a2n
W2 =
W1 =
itd..
...................
...................
an1 bn ... ann
bn an2 ... ann
16
Wzory Cramera (metoda wyznacznikowa)
Następnie obliczamy elementy wektora niewiadomych X:
W1 W2 W3
itd..
x1 = x2 = x3 =
W W W
17
Wzory Cramera (metoda wyznacznikowa)
Przykład
Rozwiązać układ równań metodą wyznacznikową:
2 3 2 x1 22
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚4 8 4śł ïÅ‚x śł ïÅ‚48śł
Å"=
2
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śłðÅ‚x ûÅ‚ ðÅ‚32śł
3
ðÅ‚5 1 3ûÅ‚ ïÅ‚ śł ïÅ‚ ûÅ‚
W =-8
18
Wzory Cramera (metoda wyznacznikowa)
22 3 2
îÅ‚Å‚Å‚
ïÅ‚48 8 4śł
W1 =
W1 =-24
ïłśł
ïłśł
ðÅ‚32 1 3ûÅ‚
2 22 2
îÅ‚Å‚Å‚
W2 =-16
ïÅ‚4 48 4śł
W2 =
ïłśł
ïłśł
ðÅ‚5 32 3ûÅ‚
2 3 22
îÅ‚Å‚Å‚
ïÅ‚4 8 48śł
W3 = W3 =-40
ïłśł
ïłśł
ðÅ‚5 1 32ûÅ‚
19
Wzory Cramera (metoda wyznacznikowa)
-24
W1
=
= 3
x1 =
-8
W
W2
-16
x2 =
=
= 2
W
-8
-40
W3
=
= 5
x3 =
-8
W
20
Metoda Thomasa dla
układów trójprzekątniowych
Metoda Thomasa dla układów trójprzekątniowych
Trójprzekątniowy układ równań:
b1 c1 x1 d1
îÅ‚Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
a1 = 0
ïÅ‚a b2 c2 śł ïÅ‚
x2 śł ïÅ‚ d2 śł
2
ïłśł ïÅ‚ śł ïÅ‚ śł
a3 b3 c2 śł ïÅ‚
ïłśł ïÅ‚ x3 d3 śł
Å"=
ïłśł ïÅ‚ śł ïÅ‚ śł
.. .
ïłśł ïÅ‚ śł ïÅ‚ śł
ïłśł ïÅ‚ śł ïÅ‚ śł
an-1 bn-1 cn-1 xn-1dn-1
ïÅ‚
an bn śł ïÅ‚ xn śł ïÅ‚ dn śł
ðÅ‚ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
cn = 0
22
Metoda Thomasa dla układów trójprzekątniowych
Układ można zapisać w następujący sposób:
axi-1 + bxi + cixi+1 = di , i =1, 2, ... ,n
i i
(1)
a1 = 0, cn = 0
Rozwiązania tego układu równań poszukuje się w postaci:
xi = ²i xi+1 + Å‚i
(2)
lub inaczej zapisujÄ…c:
xi-1 = ²i-1 xi + Å‚i-1
(3)
²i, Å‚i  nieznane współczynniki
23
Metoda Thomasa dla układów trójprzekątniowych
Po podstawieniu (3) do (1) i obliczeniu xi:
ci di - aiłi-1
xi =- xi+1 +
(4)
ai²i-1 + bi ai²i-1 + bi
Z porównania prawych stron (2) i (4):
ci di - aiłi-1
²i = - Å‚i =
(5)
ai ²i-1 + bi ai ²i-1 + bi
24
Metoda Thomasa dla układów trójprzekątniowych
Na podstawie równania (1) można wyznaczyć wartości
poczÄ…tkowe (dla i = 1):
c1 d1
x1 =- x2 +
(6)
bx1 + cx2 = d1
1 1
b1 b1
Ponieważ z (2) dla i = 1 wynika, że:
(7)
x1 = ²1x2 + Å‚1
więc:
c1 d1
²1 = - , Å‚1 =
(8)
b1 b1
25
Metoda Thomasa dla układów trójprzekątniowych
Do ostatniego równania układu (1), czyli:
anxn-1 + bnxn = dn
(9)
wstawiamy zależność (3) (dla i = n):
an ²n-1xn + Å‚n-1 + bnxn = dn
()
(10)
skÄ…d otrzymujemy:
dn - an Å‚n-1
(11)
xn == Å‚n
an ²n-1 + bn
26
Metoda Thomasa dla układów trójprzekątniowych
Po wyznaczeniu wartości xn kolejne niewiadome obliczamy z
równania (3) dla i = n - 1, n - 2, ...,1
27
Metoda Thomasa dla układów trójprzekątniowych
Algorytm:
c1 d1
²1 =- Å‚1 =
b1 b1
ci di - aiłi-1
²i = - Å‚i =
i = 2,3,...,n
ai ²i-1 + bi ai ²i-1 + bi
xn = Å‚n
i = n -1,n - 2,& ,1
xi = ²ixi+1 + Å‚i
28
Metoda Thomasa dla układów trójprzekątniowych
Przykład
Rozwiązać układ równań metodą Thomasa:
2 2 0 0 0 x1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚3 1 1 0 0śł ïÅ‚x śł ïÅ‚6śł
2
ïÅ‚ śł
ïÅ‚ śłïÅ‚ śł
Å" x3 =
0 1 2 4 0 ïÅ‚ śł 4
ïÅ‚ śłïÅ‚ śł
ïÅ‚0 0 1 1 1 śł ïÅ‚x śł ïÅ‚1 śł
4
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
ðÅ‚0 0 0 2 2ûÅ‚ ïÅ‚ śł ïÅ‚ ûÅ‚
ðÅ‚x5 ûÅ‚ ðÅ‚4śł
29
Metoda Thomasa dla układów trójprzekątniowych
c1 2
²1 =- =- =-1
b1 2
c2 11
²2 = - =- =
a2²1 + b2 3Å"(-1) +1 2
c3 48
²3 = - =- =-
a3²2 + b3 1Å"(1/ 2) + 2 5
c4 15
²4 = - =- =
a4²3 + b4 1Å"(-8/5) +1 3
c5 0
²5 = - =- = 0
a5²4 + b5 2Å"(5/3) + 2
30
Metoda Thomasa dla układów trójprzekątniowych
d1 2
Å‚1 = = =1
b1 2
d2 - a2Å‚1 6 - 3Å"1 3
Å‚2 = == -
a2²1 + b2 3Å"(-1) +1 2
d3 - a3Å‚2 4 -1Å"(-3/ 2) 11
Å‚3 = ==
a3²2 + b3 1Å"(1/ 2) + 2 5
d4 - a4Å‚3 1-1Å"(11/5)
Å‚4 = == 2
a4²3 + b4 1Å"(-8/5) +1
4 - 2Å" 2
d5 - a5Å‚4 == 0
Å‚5 =
2Å"(5/ 3) + 2
a5²4 + b5
31
Metoda Thomasa dla układów trójprzekątniowych
x5 = Å‚5 = 0
5
x4 = ²4x5 + Å‚4 = Å"0 + 2 = 2
3
811
x3 = ²3x4 + Å‚3 =- Å" 2 + =-1
55
13
= Å" -1 + - = -2
x2 = ²2x3 + Å‚
( )ëÅ‚öÅ‚
ìÅ‚÷Å‚
22
íÅ‚Å‚Å‚
=-1Å"(-2) +1 = 3
x1 = ²1x2 + Å‚1
32
Metoda eliminacji Gaussa
Metoda eliminacji Gaussa
Macierz główną układu równań i wektor wyrazów wolnych:
a11 a12 ... a1n b1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚b śł
a21 a22 ... a2n śł
2
ïÅ‚ śł ïÅ‚ śł
A = B =
ïÅ‚ śł ïÅ‚ śł
................... z"
ïÅ‚ ïÅ‚b śł
an1 an2 ... ann śł
ðÅ‚ ûÅ‚ ðÅ‚ n ûÅ‚
Zapisujemy w postaci macierzy C:
a11 a12 ... a1n b1 c11 c12 ... c1n c1,n+1
îÅ‚Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚aa22 ... a2n b2 śł ïÅ‚cc22 ... c2n c2,n+1śł
21 21
ïłśł ïÅ‚ śł
C =
=
... ... ... ... ... ... ... ... ... ...
ïłśł ïÅ‚ śł
ïÅ‚aan2 ... ann bn śł ïÅ‚ccn2 ... cnn cn,n+1śł
ðÅ‚ n1 ûÅ‚ n1
ðÅ‚ ûÅ‚
34
Metoda eliminacji Gaussa
Podstawowy wariant metody:
1. etap:
Przekształcenie macierzy C w taki sposób, aby n pierwszych
kolumn tworzyło macierz trójkątną.
2. etap:
Rozwiązanie trójkątnego układu równań.
35
Metoda eliminacji Gaussa
Jeżeli c11 `" 0
ci1
Pierwsze równanie mnożymy przez:
c11
Odejmujemy to równanie od każdego kolejnego, i  tego
równania (i = 2, 3, ..., n)
Obliczone współczynniki zapisujemy na miejscu poprzednich.
36
Metoda eliminacji Gaussa
Otrzymujemy następujący układ równań:
c11x1 + c12x2 + c13x3 + ...+ c1nxn = c1,n+1
Å„Å‚
ôÅ‚ (1) (1) (1) (1)
c22 x2 + c23 x3 + ...+ c2n xn = c2,n+1
ôÅ‚
ôÅ‚
(1) (1) (1) (1)
c32 x2 + c33 x3 + ...+ c3n xn = c3,n+1
òÅ‚
ôÅ‚
...
ôÅ‚
(1) (1) (1) (1)
cn2 x2 + cn3 x3 + ...+ cnn xn = cn,n+1
ôÅ‚
ół
37
Metoda eliminacji Gaussa
Układ ten odpowiada sprowadzeniu macierzy C do C1:
c11 c12 c13 ... c1n c1,n+1
îÅ‚ Å‚Å‚
(1) (1) (1) (1)
ïÅ‚0 c22 c23 ... c2n c2,n+1śł
ïÅ‚ śł
(1) (1) (1) (1)
0 c32 c33 ... c3n c3,n+1
ïÅ‚ śł
C1 =
ïÅ‚... ... ... ... ... ... śł
ïÅ‚ śł
(1) (1) (1) (1)
ïÅ‚ śł
ðÅ‚0 cn2 cn3 ... cnn cn,n+1ûÅ‚
za pomocą wzorów określających nowe współczynniki:
ci1
(1)
cij = cij - cij, i = 2,3,...,n j =2,3,...,n +1
c11
38
Metoda eliminacji Gaussa
(1)
c22 `" 0
Jeżeli
ci(1)
2
Drugie równanie mnożymy przez:
(1)
c22
Odejmujemy to równanie od każdego kolejnego, i  tego
równania (i = 3, 4, ..., n)
Obliczone współczynniki zapisujemy na miejscu poprzednich.
39
Metoda eliminacji Gaussa
Otrzymujemy następujący układ równań:
c11x1 + c12x2 + c13x3 + ...+ c1nxn = c1,n+1
Å„Å‚
ôÅ‚ (1) (1) (1) (1)
c22 x2 + c23 x3 + ...+ c2n xn = c2,n+1
ôÅ‚
ôÅ‚
(2) (2) (2)
c33 x3 + ...+ c3n xn = c3,n+1
òÅ‚
ôÅ‚
...
ôÅ‚
(2) (2) (2)
cn3 x3 + ...+ cnn xn = cn,n+1
ôÅ‚
ół
40
Metoda eliminacji Gaussa
Układ ten odpowiada sprowadzeniu macierzy C1 do C2:
c11 c12 c13 ... c1n c1,n+1
îÅ‚ Å‚Å‚
(1) (1) (1) (1)
ïÅ‚0 c22 c23 ... c2n c2,n+1śł
ïÅ‚ śł
(2) (2) (2)
0 0
ïÅ‚ c33 ... c3n c3,n+1 śł
C2 =
ïÅ‚... ... ... śł
... ... ...
ïÅ‚ śł
(2) (2) (2)
ïÅ‚ śł
cn3 ... cnn cn,n+1ûÅ‚
ðÅ‚0 0
za pomocą wzorów określających nowe współczynniki:
ci(1) (
(2) (
2
cij = cij1) -c21), i = 3,4,...,n j =3,4,...,n +1
(1)
c22 j
41
Metoda eliminacji Gaussa
Po wykonaniu n kroków otrzymujemy trójkątny układ równań:
c11x1 + c12x2 + c13x3 + ...+ c1nxn = c1,n+1
Å„Å‚
ôÅ‚ (1) (1) (1) (1)
c22 x2 + c23 x3 + ...+ c2n xn = c2,n+1
ôÅ‚
ôÅ‚
(2) (2) (2)
c33 x3 + ...+ c3n xn = c3,n+1
òÅ‚
ôÅ‚
...
ôÅ‚
(n (
cnn-1)xn = cnn-1)
ôÅ‚
,n+1
ół
42
Metoda eliminacji Gaussa
Dla tego układu macierz Cn-1 ma postać:
c11 c12 c13 ... c1n c1,n+1
îÅ‚ Å‚Å‚
(1) (1) (1)
ïÅ‚0 c22 c23 ... c2n (1)
c2,n+1śł
ïÅ‚ śł
(2) (2) (2)
0 0
ïÅ‚ c33 ... c3n c3,n+1 śł
Cn-1 =
ïÅ‚... ... ... śł
... ... ...
ïÅ‚ śł
(n (
ïÅ‚ śł
0 ... cnn-1) cnn-1) ûÅ‚
,n+1
ðÅ‚0 0
43
Metoda eliminacji Gaussa
Algorytm:
s =1,2,...,n -1
Å„Å‚
ôÅ‚Å„Å‚i = s +1,s + 2,...,n
ôÅ‚
òÅ‚ôÅ‚
(
( (
ôÅ‚òÅ‚cijs) = cijs-1) ciss-1) (
-csjs-1), j = s +1,s + 2,...,n +1
(s-1)
ôÅ‚ôÅ‚
css
ół
ół
44
Metoda eliminacji Gaussa
Przykład
Rozwiązać układ równań metodą eliminacji Gaussa:
4 1 3 x1 2
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚1 4 1śłïÅ‚x2 śł ïÅ‚1śł
=
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
ïÅ‚ śłïÅ‚
ðÅ‚2 3 2ûÅ‚ðÅ‚x3 śł ïÅ‚ ûÅ‚
ûÅ‚ ðÅ‚4śł
4 1 3 2
îÅ‚ Å‚Å‚
ïÅ‚1 4 1 1 śł
C =
ïÅ‚ śł
ïÅ‚ śł
ðÅ‚2 3 2 4ûÅ‚
45
Metoda eliminacji Gaussa
s =1
i = 2
c21 1 15
(1)
c22 = c22 - c12 = 4 - Å"1 =
c11 4 4
c21 1 1
(1)
c23 = c23 - c13 =1- Å"3 =
c11 4 4
c21 1
(1)
1
c24 = c24 - c14 =
=1- Å" 22
c11
4
46
Metoda eliminacji Gaussa
i = 3
c31 2 5
(1)
c32 = c32 - c12 = 3 - Å"1 =
c11 4 2
c31 2 1
(1)
c33 = c33 - c13 = 2 - Å"3 =
c11 4 2
c31
(1)
c34 = c34 - c14 = 4 - 2 2 = 3
Å"
c11
4
47
Metoda eliminacji Gaussa
îÅ‚ Å‚Å‚
ïÅ‚4 1 3 2 śł
ïÅ‚ śł
ïÅ‚0 15 1 1 śł
C1 =
ïÅ‚ 4 4 2
śł
ïÅ‚ śł
5 1
03
ïÅ‚ śł
ðÅ‚ 2 2 ûÅ‚
48
Metoda eliminacji Gaussa
s = 2
i = 3
(1)
1 5 4 1 1
c32 (1
(2) (1
= - Å" Å" =
c33 = c33) -c23)
(1)
2 2 15 4 3
c22
(1)
8
c32 (1
5 4 1
(2) (1
=
c34 = c34) -c24)
= 3 - Å" Å"
(1)
3
c22
2 15 2
49
Metoda eliminacji Gaussa
îÅ‚ Å‚Å‚
ïÅ‚ śł
4 1 3 2
ïÅ‚ śł
ïÅ‚0 15 1 1 śł
C2 =
ïÅ‚ 4 4 2śł
ïÅ‚ śł
1 8
0 0
ïÅ‚ śł
ðÅ‚ 3 3 ûÅ‚
Macierz odpowiada trójkątnemu układowi równań.
Rozwiązanie takiego układu równań:
patrz wcześniejszy przykład
50