Wykład 1
Operacje macierzowe
oraz
metody rozwiązywania układów równań
Metody Numeryczne
Wykład 1/1
dr inż. Mirosław Dziewoński
e-mail:
Pok. 151
Wykład 1
Operacje macierzowe
oraz
metody rozwiązywania układów równań
Metody Numeryczne
Wykład 1/1
dr inż. Mirosław Dziewoński
e-mail:
Pok. 151
Metody Numeryczne
Wykład 1/2
Podręcznik:
Ewa Majchrzak, Bohdan Mochnacki
„Metody numeryczne.
Podstawy teoretyczne,
aspekty praktyczne i algorytmy”
Treść wykładów oraz dodatkowe informacje:
www.kwmimkm.polsl.pl
Wykład 1/3
Wykład 1/
Warunki zaliczenia
Wykład 1/3
Zaliczenie z przedmiotu:
Ocena końcowa z przedmiotu metody numeryczne jest
średnią
ważoną
oceny z kartkówek
i
oceny z laboratorium
(50% kartkówki,
50% laboratorium).
Wszystkie oceny (z laboratorium i z kartkówek) muszą być
pozytywne
(min. 2,86)
Obecność
na zajęciach laboratoryjnych
jest obowiązkowa
.
Wykład 1/4
Metody numeryczne
są jedną z dziedzin
matematyki stosowanej
.
Metody numeryczne
mają ogromne zastosowanie w praktyce
inżynierskiej, w szczególności w czasie tworzenia programów
komputerowych mających na celu przeprowadzanie
obliczeń
matematycznych.
Znajomość metod numerycznych umożliwia nam nie tylko
odpowiedzieć na pytanie
:
„Jaki jest wynik?”,
ale również
pozwala na udzielenie odpowiedzi:
„W jaki sposób wynik został
osiągnięty oraz czy uzyskany wynik jest wiarygodny?”
Czym są metody numeryczne?
Wykład 1/5
Operacje macierzowe
Metody rozwiązywania układów równań liniowych
Aproksymacja funkcji jednej zmiennej
Interpolacja funkcji
Całkowanie numeryczne
Metody rozwiązywania równań liniowych
Tematyka wykładów
Tematami kolejnych wykładów
w ramach przedmiotu
„Metody numeryczne” będą:
Wykład 1/6
Operacje macierzowe
Wykład 1/7
Operacje macierzowe
Podstawowe operacje macierzowe:
Dodawanie i odejmowanie macierzy
Mnożenie macierzy
Obliczanie wyznacznika macierzy
Odwracanie macierzy
Wykład 1/8
Mnożenie macierzy
Rozważamy dwie macierze A
[m,
n] i B
[n,
k]:
1,1
1,2
1,
1,1
1,2
1,
2,1
2,2
2,
2,1
2,2
2,
,1
,2
,
,1
,2
,
,
n
k
n
k
m
m
m n
n
n
n k
a
a
a
b
b
b
a
a
a
b
b
b
a
a
a
b
b
b
A
B
Iloczyn macierzy
C = A
B
obliczymy następująco:
,
,
,
1
1, 2,
,
1, 2,
n
i j
i s s j
s
c
a b
i
m
j
k
Wykład 1/9
Odwracanie macierzy
Bierzemy po uwagę macierz kwadratową
A
o wymiarach
n
×
n
1,1
1,2
1,
2,1
2,2
2,
,1
,2
,
n
n
n
n
n n
a
a
a
a
a
a
a
a
a
A
Wykład 1/10
Odwracanie macierzy
1,1
1,2
1,
2,1
2,2
2,
,1
,2
,
1
0
0
0
1
0
0
0
1
n
n
n
n
n n
a
a
a
a
a
a
a
a
a
E
A
B
Tworzymy macierz
B
rozbudowując macierz
A
o macierz jednostkową
E
Wykład 1/11
Odwracanie macierzy
1
1,1
1,2
1,
2,1
2,2
2,
,1
,2
,
ˆ
ˆ
ˆ
1
0
0
ˆ
ˆ
ˆ
0
1
0
ˆ
ˆ
ˆ
0
0
1
n
n
n
n
n n
a
a
a
a
a
a
a
a
a
E
A
B
Aby uzyskać macierz odwrotną musimy tak przekształcać macierz
B
by w miejsce podmacierzy
A
otrzymać macierz jednostkową. Po
takich przekształceniach w miejscu macierzy
E
otrzymamy macierz
odwrotną
A
1
.
Wykład 1/12
Odwracanie macierzy
7
2
3
0
A
Znaleźć macierz odwrotną do macierzy:
Tworzymy macierz B:
7
2
1
0
3
0
0
1
B
Wykład 1/13
Odwracanie macierzy
Elementy pierwszego wiersza dzielimy przez 7, a następnie mnożymy
razy 3 i odejmujemy od wiersza drugiego:
7
2
1
0
1
2 / 7 1/ 7
0
1
2 / 7
1/ 7
0
3
0
0
1
3
0
0
1
0
6 / 7
3/ 7
1
B
W drugim kroku elementy wiersza drugiego dzielimy przez
6/7, a
następnie mnożymy razy 2/7 i odejmujemy od wiersza pierwszego:
2
1
2
1
1
1
0
1
0
1
0
0
7
7
7
7
3
6
3
1
7
1
7
0
1
0
1
0
1
7
7
2
6
2
6
B
Wykład 1/14
Odwracanie macierzy
Macierz odwrotna do A jest następująca
1
1
0
3
1
7
2
6
A
Szczegółowy algorytm znajdziemy w literaturze!
Wykład 1/15
Rozwiązywanie układów
równań liniowych
Metody rozwiązywania układów równań
Metody rozwiązywania układów równań liniowych można podzielić na
dwie grupy:
Metody dokładne
metoda dla macierzy jednoprzekątniowej
metoda dla macierzy trójkątnej
metoda Thomasa
metoda eliminacji Gaussa
Metody iteracyjne
metoda iteracji prostej
metoda Gaussa – Seidla
metoda nadrelaksacji
Wykład 1/16
Metody rozwiązywania układów równań
Wykład 1/17
Rozpatruje się układ
n
- równań liniowych zawierających
n
– niewiadomych
11 1
12
2
1
1
21 1
22
2
2
2
1 1
2
2
...
...
.............................................
...
n
n
n
n
n
n
nn
n
n
a x
a x
a x
b
a x
a x
a x
b
a x
a x
a x
b
który można zapisać w postaci macierzowej
A X
B
Metody rozwiązywania układów równań
Wykład 1/18
11
12
1
1
1
21
22
2
2
2
1
2
...
...
...................
...
n
n
n
n
n
n
nn
a a
a
x
b
a a
a
x
b
x
b
a a
a
A
X
B
Układ równań posiada
jedno rozwiązanie
wtedy i tylko wtedy gdy jest
oznaczony
, tzn. że
macierz główna układu równań A nie jest osobliwa
(wyznacznik z tej macierzy jest różny od zera).
1
X
A
B
Układ równań z elementami na głównej przekątnej macierzy A
Wykład 1/19
Układ równań, w którym tylko główna przekątna macierzy A posiada
elementy niezerowe:
11 1
1
22
2
2
...
...
nn
n
n
a x
b
a x
b
a x
b
rozwiązuje się „natychmiastowo”:
,
0,
1, 2,...,
i
i
ii
ii
b
x
a
i
n
a
Trójkątny układ równań
Wykład 1/20
Jeżeli układ równań ma następującą postać:
nazywamy go
układem trójkątnym
.
11 1
12
2
1
1
22
2
2
2
...
...
...
...
n
n
n
n
nn
n
n
a x
a x
a x
b
a x
a x
b
a x
b
Trójkątny układ równań
Wykład 1/21
Rozwiązanie takiego układu jest stosunkowo proste. Z ostatniego równania
wyznaczamy
x
i
, z przedostatniego
x
i-1
itd.:
1
,
1,
2, ... ,1
n
n
n n
n
i
i s
s
s i
i
i i
b
x
a
b
a
x
x
i
n
n
a
przy założeniu, że
0 ,
1, 2, ... ,
i i
a
i
n
Trójkątny układ równań
Wykład 1/22
Przykład 1:
Rozwiązać następujący układ równań
1
2
3
2
3
3
2
8
2
1
2
6
x
x
x
x
x
x
Trójkątny układ równań
Wykład 1/23
Macierz główna układu i wektor wyrazów wolnych mają postać
1
2
1
8
0
2
1
1
0
0
2
6
A
B
Z ostatniego równania wyznaczamy
3
3
33
6
3
2
b
x
a
Trójkątny układ równań
Wykład 1/24
a następnie
2
23
3
2
2 2
1 ( 1) 3
2
2
b
a
x
x
a
1
12
2
13
3
1
11
8 2 2 1 3
1
1
b
a
x
a
x
x
a
Metoda eliminacji Gaussa
Wykład 4/25
Układ równań liniowych
11 1
12
2
1
1
21 1
22
2
2
2
1 1
2
2
...
...
.............................................
...
n
n
n
n
n
n
nn
n
n
a x
a x
a x
b
a x
a x
a x
b
a x
a x
a x
b
zapisuje się w postaci macierzy
C
, w której macierz główną
A
uzupełnia się
dodatkową kolumną zawierającą wektor wyrazów wolnych
B
.
Metoda eliminacji Gaussa
Wykład 4/26
czyli:
11
12
1
1,
1
11
12
1
1,
1
21
22
2
2,
1
21
22
2
2,
1
1
2
,
1
1
2
,
1
n
n
n
n
n
n
n
n
n
n
nn
n n
n
n
nn
n n
a
a
a
b
c
c
c
c
a
a
a
b
c
c
c
c
a
a
a
b
c
c
c
c
C
n
pierwszych kolumn stanowią elementy macierzy
A
n+1
kolumnę stanowią elementy wektora
B
Metoda eliminacji Gaussa
Wykład 4/27
Wariant podstawowy metody eliminacji Gaussa polega na przekształceniu
macierzy
C
, tak aby otrzymać równoważny układ równań, w którym
n
pierwszych kolumn macierzy
C
tworzyło macierz trójkątną, a następnie
rozwiązać ten układ równań odpowiednią metodą (przedstawioną
wcześniej).
Metoda eliminacji Gaussa
Wykład 4/28
W pierwszym kroku algorytmu odejmujemy pierwsze równanie pomnożone
przez
c
i1
/c
11
od
i
– tego równania (
i = 2, 3, ... , n
) i po wykonaniu obliczeń
otrzymujemy następujący układ równań:
11 1
12
2
13 3
1
1,
1
(1)
(1)
(1)
(1)
22
2
23
3
2
2,
1
(1)
(1)
(1)
(1)
32
2
33
3
3
3,
1
(1)
(1)
(1)
2
2
3
3
,
...
...
...
...................................................
...
n
n
n
n
n
n
n
n
n
n
n
nn
n
n n
c x
c x
c x
c x
c
c x
c x
c x
c
c x
c x
c x
c
c x
c x
c x
c
(1)
1
Metoda eliminacji Gaussa
Wykład 4/29
który odpowiada sprowadzeniu macierzy
C
do
C
1
11
12
13
1
1,
1
(1)
(1)
(1)
(1)
22
23
2
2,
1
(1)
(1)
(1)
(1)
32
33
3
3,
1
1
(1)
(1)
(1)
(1)
2
3
,
1
0
0
0
n
n
n
n
n
n
n
n
nn
n n
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
C
za pomocą wzorów określających nowe współczynniki
1
(1)
1
11
2, 3, ... ,
2, 3, ... ,
1
i
i j
i j
j
c
c
c
c
i
n
j
n
c
dla
oraz
Metoda eliminacji Gaussa
Wykład 4/30
W drugim kroku odejmujemy drugie równanie pomnożone przez
c
i2
(1)
/c
22
(1)
od
i
– tego równania (
i = 3, 4, ... , n
) i po wykonaniu obliczeń otrzymujemy
kolejny układ równań:
11 1
12
2
13 3
1
1,
1
(1)
(1)
(1)
(1)
22
2
23
3
2
2,
1
(2)
(2)
(2)
33
3
3
3,
1
(2)
(2)
(2)
3
3
,
1
...
...
...
........................................
...
n
n
n
n
n
n
n
n
n
n
nn
n
n n
c x
c x
c x
c x
c
c x
c x
c x
c
c
x
c
x
c
c
x
c
x
c
Metoda eliminacji Gaussa
Wykład 4/31
który odpowiada sprowadzeniu macierzy
C
do
C
1
za pomocą wzorów określających nowe współczynniki
1
2
1
1
(2)
2
1
2 2
3, 4, ... ,
3, 4, ... ,
1
i
i j
i j
j
c
c
c
c
i
n
j
n
c
dla
oraz
11
12
13
1
1,
1
(1)
(1)
(1)
(1)
22
23
2
2,
1
(2)
(2)
(2)
33
3
3,
1
2
(2)
(2)
(2)
3
,
1
0
0
0
0
0
n
n
n
n
n
n
n
nn
n n
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
C
Metoda eliminacji Gaussa
Wykład 4/32
Kontynuując takie postępowanie, po wykonaniu
n
kroków dochodzimy do
trójkątnego układu równań
11 1
12
2
13 3
1
1,
1
(1)
(1)
(1)
(1)
22
2
23
3
2
2,
1
(2)
(2)
(2)
33
3
3
3,
1
(
1)
(
1)
,
1
...
...
...
.......................................
n
n
n
n
n
n
n
n
n
n
n
n n
n
n n
c x
c x
c x
c x
c
c x
c x
c x
c
c
x
c
x
c
c
x
c
Metoda eliminacji Gaussa
Wykład 4/33
któremu odpowiada przekształcona macierz
C
n-1
11
12
13
1
1,
1
(1)
(1)
(1)
(1)
22
23
2
2,
1
(2)
(2)
(2)
33
3
3,
1
1
(
1)
(
1)
,
1
0
0
0
0
0
0
n
n
n
n
n
n
n
n
n
nn
n n
c
c
c
c
c
c
c
c
c
c
c
c
c
c
C
Tak zbudowany układ równań rozwiązuje się przedstawioną wcześniej
metodą
dla
układów
trójkątnych
zakładając,
że
n
– pierwszych kolumn macierzy
C
n -1
stanowi
macierz
A
, a kolumna
n +1
jest wektorem
B
.
Metoda eliminacji Gaussa
Wykład 4/34
Przejście od układu równań liniowych do układu trójkątnego realizowane
jest zatem za pomocą następującego wzoru iteracyjnego:
(
1)
( )
(
1)
(
1)
(
1)
1 , 2 , ... ,
1
1 ,
2 , ... ,
,
1,
2, ... ,
1
s
i s
s
s
s
i j
i j
s j
s
s s
s
n
i
s
s
n
c
c
c
c
j
s
s
n
c
Metoda eliminacji Gaussa
Wykład 4/35
Przykład:
Rozwiązać następujący układ równań metodą eliminacji Gaussa
1
2
3
1
2
3
1
2
3
2
3
1
3
2
2
3
2
3
x
x
x
x
x
x
x
x
x
Macierz główna układu i wektor wyrazów wolnych mają postać:
2
1
3
3
2
1
1
3
2
A
1
2
3
B
Metoda eliminacji Gaussa
Wykład 4/36
Tworzymy macierz
C
2
1
3
1
3
2
1
2
1
3
2
3
C
Macierz główna układu i wektor wyrazów wolnych mają postać:
2
1
3
3
2
1
1
3
2
A
1
2
3
B
Metoda eliminacji Gaussa
Wykład 4/37
Obliczamy elementy macierzy
C
1
:
1
(1)
1
11
2,3
2,3, 4
i
i j
i j
j
c
c
c
c
i
j
c
dla
oraz
(1)
21
2 2
2 2
12
11
(1)
(1)
(1)
(1)
(1)
23
2 4
32
33
34
3
2
1
0.5
2
3.5
0.5
2.5
0.5
3.5
c
c
c
c
c
c
c
c
c
c
1
2
1
3
1
0
0.5
3.5
0.5
0
2.5
0.5 3.5
C
i otrzymujemy
:
Metoda eliminacji Gaussa
Wykład 4/38
Obliczamy elementy macierzy
C
2
i otrzymujemy
:
1
2
1
1
(2)
2
1
2 2
3
3, 4
i
i j
i j
j
c
c
c
c
i
j
c
dla
oraz
(2)
(2)
33
34
18,
6
c
c
2
2
1
3
1
0
0.5
3.5
0.5
0
0
18
6
C
Metoda eliminacji Gaussa
Wykład 4/39
Macierz
C
2
przedstawia teraz następujący trójkątny układ równań:
1
2
3
2
3
3
2
3
1
0.5
3.5
0.5
18
6
x
x
x
x
x
x
który można zapisać następująco:
2
1
3
0
0.5
3.5
0
0
18
A
1
0.5
6
B
Metoda eliminacji Gaussa
Wykład 4/40
3
3
33
6
1
18
3
b
x
a
2
23
3
2
2 2
1
7
1
1
2
2
3
1
1
3
2
b
a
x
x
a
1
12
2
13
3
1
11
1
1
1 ( 1) 1
3
2
3
3
1
2
3
b
a
x
a
x
x
a
Metoda Thomasa
Wykład 1/41
Algorytm Thomasa (zwany metodą progonki) stosowany jest między innymi
dla trójprzekątniowego układu równań:
1
1
1
1
2
2
2
2
2
3
3
3
3
3
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
.
.
.
.
.
.
.
.
.
0
0
0
0
0
0
0
0
0
n
n
n
n
n
n
n
n
n
b
c
x
d
a
b
c
x
d
a
b
c
x
d
a
b
c
x
d
a
b
x
d
który można zapisać również w następujący sposób
1
1
1
,
0,
0,
1, 2, ... ,
i
i
i
i
i
i
i
n
a x
b x
c x
d
a
c
i
n
Metoda Thomasa
Wykład 1/42
Rozwiązanie tego układu równań poszukuje się w postaci
lub inaczej zapisując
1
i
i
i
i
x
x
1
1
1
i
i
i
i
x
x
gdzie
i
i
i
są nieznanymi współczynnikami.
Metoda Thomasa
Wykład 1/43
Po podstawieniu
do
i uporządkowaniu otrzymujemy:
1
i
i
i
i
i
c
a
b
1
1
i
i
i
i
i
i
i
d
a
a
b
Metoda Thomasa
Wykład 1/44
Z danych przedstawionych w równaniu
można wyznaczyć wartości
początkowe (dla
i = 1
)
1
1
1
1
1
1
,
c
d
b
b
oraz wartość ostatniej niewiadomej (dla
i = n
)
1
1
n
n
n
n
n
n
n
n
d
a
x
a
b
Po wyznaczeniu wartości
x
n
kolejne niewiadome obliczamy z równania
dla
i = n-1, n-2, ... , 1
Metoda Thomasa
Wykład 14/45
Rozwiązać następujący układ równań metodą Thomasa
Przykład 3:
1
2
1
2
3
2
3
4
3
4
5
4
5
3
1
2
2
2
3
2
4
3
5
x
x
x
x
x
x
x
x
x
x
x
x
x
Rozwiązać następujący układ równań metodą Thomasa
Metoda Thomasa
Wykład 1/46
Macierz główną układu i wektor wyrazów wolnych można zapisać
następująco:
1
3
0
0
0
1
1
2
1
0
0
2
0
1
2
1
0
3
0
0
1
2
1
4
0
0
0
3
1
5
A
D
Obliczamy wartości początkowe współczynników
1
1
1
1
1
1
3 ,
1
c
d
b
b
Metoda Thomasa
Wykład 1/47
Następnie wyznaczamy pozostałe wartości współczynników dla
i = 2, ..., n
1
1
1
,
i
i
i
i
i
i
i
i
i
i
i
i
c
d
a
a
b
a
b
3
1
1
1
0.333
1.333
0.6
1.6
0
0.25
Metoda Thomasa
Wykład 1/48
Obliczamy wartość ostatniej niewiadomej
x
n
5
0.25
n
n
x
x
oraz pozostałe wartości niewiadomych
i = n-1, n-2, ... , 1
:
1
i
i
i
i
x
x
1.75
0.25
0.75
1.75
0.25
x