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

. . . . . . . . . . . . . . .