Rozwiązywanie układów równań liniowych
Metody ścisłe:
metoda eliminacji częściowej (Gaussa)
metoda eliminacji zupełnej (Jordana)
metody macierzowe (wzory Cramera, macierz odwrotna)
komendy w Maple u: solve i LinearSolve
Sformułowanie zagadnienia
a11x1 + a12x2 + & + a1n xn = b1
a21x1 + a22x2 + & + a2n xn = b2
a31x1 + a32x2 + & + a3n xn = b3

an1x1 + an2x2 + & + ann xn = bn
A x = b
a11 a12 a1n x1 b1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚a a22 a2n śł ïÅ‚x śł ïÅ‚b śł
21 2 2
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
A = x = b =

ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚a an2 ann śł ïÅ‚x śł ïÅ‚b śł
ðÅ‚ n1 ûÅ‚ ðÅ‚ n ûÅ‚ ðÅ‚ n ûÅ‚
Z : det(A) `" 0
Idea metody eliminacji Gaussa
A x = b Tx = c
t11 t12 t1n
îÅ‚ Å‚Å‚
ïÅ‚
0 t22 t2n śł
ïÅ‚ śł
- macierz trójkątna górna
T =
ïÅ‚ śł
ïÅ‚
0 0 tnn śł
ðÅ‚ ûÅ‚
t11 t12 t1n x1 c1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
t11x1 + t12x2 + & + t1nxn = c1
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
0 t22 t2nśł ïÅ‚x2śł ïÅ‚c2śł t22x2 + & + t2nxn = c2
ïÅ‚
=
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł


ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
tnnxn = cn
ïÅ‚ śł
0 0 tnn śł ïÅ‚xn śł ïÅ‚cnûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚
x1
îÅ‚ Å‚Å‚
ïÅ‚x śł
2
ïÅ‚ śł
x =

ïÅ‚ śł
ïÅ‚x śł
ðÅ‚ n ûÅ‚
Metoda eliminacji Gaussa  eliminacja pierwsza
ai(0)
(0) (0) (0) (0) (0)
1
(1) a11 x1 + a12 x2 + a13 x3 + & + a1n xn = b1 Å" , (i) - (1), i = 2..n
(0)
a11
(0) (0) (0) (0) (0)
(2) a21 x1 + a22 x2 + a23 x3 + & + a2n xn = b2
(0) (0) (0) (0) (0)
(3) a31 x1 + a32 x2 + a33 x3 + + a3n xn = b3

(0) (0) (0) (0) (0)
(n) an1 x1 + an2 x2 + an3 x3 + & + ann xn = bn
(0) (0) (0) (0) (0)
(1) a11 x1 + a12 x2 + a13 x3 + & + a1n xn = b1
(1) (1) (1) (1)
(2) a22 x2 + a23 x3 + & + a2n xn = b2 Å„Å‚ (1) ( ai(0) (
1
- a10)
(1) (1) (1) (1)
(0)
(3) a32 x2 + a33 x3 + + a3n xn = b3 ôÅ‚aij = aij0)
a11 j
ôÅ‚
òÅ‚

ai(0) (0)
(1)
ôÅ‚b - b1
1
(1) (1) (1) (1)
(0)
(n) an2 x2 + an3 x3 + & + ann xn = bn ôÅ‚ i = bi(0)
a11
ół
i = 2,3..n
j =1,2..n
Metoda eliminacji Gaussa  eliminacja druga
(0) (0) (0) (0) (0)
(1) a11 x1 + a12 x2 + a13 x3 + & + a1n xn = b1
ai(1)
(1) (1) (1) (1)
2
(2) a22 x2 + a23 x3 + & + a2n xn = b2 Å" , (i) - (2), i = 3..n
(1)
a22
(1) (1) (1) (1)
(3) a32 x2 + a33 x3 + + a3n xn = b3

(1) (1) (1) (1)
(n) an2 x2 + an3 x3 + & + ann xn = bn
(0) (0) (0) (0) (0)
(1) a11 x1 + a12 x2 + a13 x3 + & + a1n xn = b1
(1) (1) (1) (1)
(2) a22 x2 + a23 x3 + & + a2n xn = b2
Å„Å‚
ai(1) (
(2) (2) (2)
(2) (
2
(3) a33 x3 + + a3n xn = b3
- a21)
ij
ôÅ‚a = aij1)
(1)
a22 j
ôÅ‚

òÅ‚
(2) (2) (2)
(2)
ôÅ‚b = bi(1) ai(1)
2
(n) an3 x3 + & + ann xn = bn (1) (
- b21)
i
ôÅ‚
a22
ół
i = 3,4..n
j = 2,3..n
Metoda eliminacji Gaussa  finał
Tx = c
(0) (0) (0) (0) (0) (0)
îÅ‚Å‚Å‚ îÅ‚ Å‚Å‚
a11 a12 a13 a1,n-1 a1n b1
ïÅ‚ ïÅ‚
(1) (1) (1) (1) (1)
0 a22 a23 a2,n-1 a2n śł b2 śł
ïłśł ïÅ‚ śł
(2) (2) (2) (2)
ïÅ‚ ïÅ‚
0 0 a33 a3,n-1 a3n śł b3 śł
T = c =
ïłśł ïÅ‚ śł

ïłśł ïÅ‚ śł
( ( (
ïÅ‚ ïÅ‚bnn-2) śł
0 0 0 0 ann-2) ann-2) śł
-1,n-1 -1,n -1
ïłśł ïÅ‚ śł
(n (n-1)
0 0 0 0 0 ann-1) ûÅ‚
ïłśł ïÅ‚ śł
ðÅ‚ ðÅ‚bn ûÅ‚
ai(k -1)
,k
(
k
k =1,2,...,n -1  numer eliminacji
ai(k ) = ai(k -1) -akk -1)
j j
(
akk -1) , j
, k
i  numer wiersza
i = k +1... n
ai(k -1)
j  numer kolumny
j = k... n
,k
(
bi(k ) = bi(k -1) -bkk -1)
(
akk -1)
, k
Wyznaczanie współrzędnych wektora niewiadomych x
(0) (0) (0) (0) (0) (0)
îÅ‚Å‚Å‚ x1 îÅ‚ Å‚Å‚
a11 a12 a13 a1,n-1 a1n îÅ‚ Å‚Å‚ b1
ïÅ‚
(1) (1) (1) (1)
x2 ïÅ‚ (1) śł
0 a22 a23 a2,n-1 a2n śł ïÅ‚ śł ïÅ‚ b2 śł
ïłśł
ïÅ‚ śł
(2) (2) (2) (
ïÅ‚ ïÅ‚
ïÅ‚ x3 śł
0 0 a33 a3,n-1 a3n śł b32) śł
Å"=śł
ïłśł ïÅ‚
ïÅ‚ śł

ïÅ‚ śł
ïłśł ïÅ‚ śł
( ( (
ïÅ‚
xn-1
0 0 0 0 ann-2) ann-2) śł ïÅ‚ śł ïÅ‚bnn-2) śł
-1,n-1 -1,n -1
ïłśł ïÅ‚ śł
ïÅ‚ śł
(n
xn ïÅ‚ (n-1) śł
0 0 0 0 0 ann-1) ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚bn ûÅ‚
ïłśł
ðÅ‚
( (i
aiii-1)xi + ai(i-1)xi+1 +...+ ai(i-1)xn-1 + ain-1)xn = bi(i-1)
,i+1 ,n-1
n
( (
aiii-1)xi + aiji-1)xj = bi(i-1)
"
j=i+1
n
ëÅ‚öÅ‚
1
(i-1)
xi =- ai(i-1)xj ÷Å‚, i = n,n -1, ...1
"
(
aiii-1) ìÅ‚bi j
j=i+1
íÅ‚Å‚Å‚
Przykład liczbowy
îÅ‚20 4 - 3 Å‚Å‚ Å‚Å‚
x1 îÅ‚ 19
20 4 - 3 x1 19 îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
ïÅ‚x śł
203 31 1717
ïÅ‚ śł ïÅ‚x śł ïÅ‚83śł
0 Å" =
Å" =
2 ïÅ‚ śł
ïÅ‚ śł
2
5 20 20
ïÅ‚ śł
ïÅ‚- 3 40 2 śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ 16659 ïÅ‚ śł
śł 49977
ïÅ‚ śł
ïÅ‚ 4 3 20ûÅ‚ ðÅ‚x3ûÅ‚ ðÅ‚70śł 0 0
śł ïÅ‚ śł ïÅ‚
ðÅ‚x3ûÅ‚
ðÅ‚ ûÅ‚
ðÅ‚ 812 ûÅ‚ ðÅ‚ 812 ûÅ‚
1
îÅ‚ Å‚Å‚
ïÅ‚2śł
x =
ïÅ‚ śł
ïÅ‚
ðÅ‚3śł
ûÅ‚
Idea metody eliminacji zupełnej (Jordana)
A x = b I x = c x = c
1 0 0
îÅ‚ Å‚Å‚
ïÅ‚ śł
ïÅ‚0 1 0śł - macierz jednostkowa
I =
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚0 0 1śł
ðÅ‚ ûÅ‚
1 0 0 x1 c1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x1 c1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚x śł ïÅ‚c śł
ïÅ‚0 1 0śł ïÅ‚x2śł ïÅ‚c2śł
2 2
ïÅ‚ śł ïÅ‚ śł
=
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł =

ïÅ‚ śł ïÅ‚ śł

ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚x śł ïÅ‚c śł
ïÅ‚0 0 1śł ïÅ‚x śł ïÅ‚c śł
ðÅ‚ n ûÅ‚ ðÅ‚ n ûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ nûÅ‚ ðÅ‚ n ûÅ‚
Metoda eliminacji Jordana  eliminacja pierwsza
(0) (0) (0) (0) (0) (0)
(1) a11 x1 + a12 x2 + a13 x3 + & + a1n xn = b1 ÷ a11 Å"ai(0) (i) - (1), i = 2..n
1
(0) (0) (0) (0) (0)
(2) a21 x1 + a22 x2 + a23 x3 + & + a2n xn = b2
(0) (0) (0) (0) (0)
(3) a31 x1 + a32 x2 + a33 x3 + + a3n xn = b3

(0) (0) (0) (0) (0)
(n) an1 x1 + an2 x2 + an3 x3 + & + ann xn = bn
(1) (1) (1) (1)
(1) x1 + a12 x2 + a13 x3 + & + a1n xn = b1
(1) (1) (1) (1)
(2) a22 x2 + a23 x3 + & + a2n xn = b2
(1) (1) (1) (1)
(3) a32 x2 + a33 x3 + + a3n xn = b3

(1) (1) (1) (1)
(n) an2 x2 + an3 x3 + & + ann xn = bn
Metoda eliminacji Jordana  eliminacja druga
(1) (1) (1) (1)
(1) x1 + a12 x2 + a13 x3 + & + a1n xn = b1
(1) (1) (1) (1) (1)
Å"ai(1) (i) - (2), i =1,3.
(2) a22 x2 + a23 x3 + & + a2n xn = b2 ÷ a22 2
(1) (1) (1) (1)
(3) a32 x2 + a33 x3 + + a3n xn = b3

(1) (1) (1) (1)
(n) an2 x2 + an3 x3 + & + ann xn = bn
(2) (2)
(1) x1 (2)
+ a13 x3 + & + a1n xn = b1
(2) (2) (2)
(2) x2 + a23 x3 + & + a2n xn = b2
(2) (2) (2)
(3) a33 x3 + + a3n xn = b3

(2) (2) (2)
(n) an3 x3 + & + ann xn = bn
Metoda eliminacji Jordana  eliminacja trzecia
(2) (2)
(1) x1 (2)
+ a13 x3 + & + a1n xn = b1
(2) (2) (2)
(2) x2 + a23 x3 + & + a2n xn = b2
(2)
(2) (2) (2)
Å"ai(2) (i) - (3), i =1,2,4..n
÷ a33
(3) a33 x3 + + a3n xn = b3
3

(2) (2) (2)
(n) an3 x3 + & + ann xn = bn
(3) (3) (3)
(1) x1 (3)
+ a14 x4 + a15 x5 + & + a1n xn = b1
(3) (3) 3)
(2) x2(3)
+ a24 x4 + a25 x5 + & + a2n xn = b2
(3) (3) (3) (3)
(3) x3 + a34 x4 + a35 x5 + & + a3n xn = b3
(3) (3) (3) (3)
(4) a44 x4 + a45 x5 + & + a4n xn = b4

(3) (3) (3) (3)
(n) an4 x4 + an5 x5 + & + ann xn = bn
Metoda eliminacji Jordana  finał
(1) x1 (n)
= b1
(2) x2 (
= b2n)
(3) x3 (
= b3n)

(
(n) xn = bnn)
Przykład liczbowy
1 0 0 x1 1
20 4 - 3 x1 19 îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚0 1 0śł ïÅ‚x śł ïÅ‚2śł
ïÅ‚ śł ïÅ‚x śł ïÅ‚83śł
Å" =
Å" =
2
2
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚- 3 40 2 śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ 4 3 20ûÅ‚ ðÅ‚x3ûÅ‚ ðÅ‚70śł
śł ïÅ‚ śł ïÅ‚
ðÅ‚0 0 1ûÅ‚ ïÅ‚ śł ïÅ‚ ûÅ‚
ðÅ‚x3ûÅ‚ ðÅ‚3śł
ðÅ‚ ûÅ‚
1
îÅ‚ Å‚Å‚
ïÅ‚2śł
x =
ïÅ‚ śł
ïÅ‚
ðÅ‚3śł
ûÅ‚
Wzory Cramera (metoda wyznaczników)
A x = b
Wj
x = , j = 1..n - wzory Cramera
j
W
a11 & a1, j-1 b1 a1, j+1 & a1n
W = A , Wj = , j = 1..n
an1 & a1, j-1 bn a1, j+1 & a1n
Metoda macierz odwrotnej
x = A-1b A-1 - macierz odwrotna
Komendy w Maple u: solve i LinearSolve
> solve({r||(1..n)},{seq(x[i],i=1..n)});
> with(LinearAlgebra):
> LinearSolve(A,b);