gaus.pdf

(119 KB) Pobierz
Aproksymacja jest to przybliżanie, zastępowanie jednych wielkości drugimi
A =
Metoda eliminacji Gaussa polega na wyzerowaniu elementów znajdujących się pod
przekątną:
é
a
11
a
12
a
1
n
ù
ê
ú
a
a
a
A
0
)
=
A
=
ê
21
22
2
n
ú
ê
⋮
⋮
⋮
⋮
ú
ê
ú
ë
a
a
a
û
n
1
n
2
nn
Etapy metody:
od wierszy 2, 3, ..., n odejmujemy wiersz przemnożony tak, by wyraz w pierwszej kolumnie
był równy zero, przez:
a
l i
=
(
1
1
a
(
11
W efekcie otrzymujemy macierz:
é
a
(
11
a
(
12
a
(
1
n
ù
0
a
(
22
a
(
2
ê
ú
A
(
=
n
ê
⋮
⋮
⋮
⋮
ú
ê
ú
ë
0
a
(
2
a
(
û
n
nn
postępujemy tak samo zerując elementy pod przekątną w drugiej kolumnie macierzy A (1):
l i
i
=
a
(
2
2
a
(
22
aż do uzyskania macierzy A (n-1), która jest wyznaczaną macierzą trójkątną górną U :
é
a
(
11
n
-
1
a
(
12
n
-
1
a
(
1
n
n
-
1
ù
ê
ú
ê
0
a
(
22
n
-
1
a
n
n
-
1
ú
U
=
A
(
n
-
1
=
2
ê
⋮
⋮
⋮
⋮
ú
ê
ú
ë
0
0
a
n
nn
-
1
û
Macierzą dolną trójkątną L jest macierzą współczynników lij , przez które mnożone były
wiersze w czasie eliminacji (na przekątnej umieszczamy jedynki).
Elementem podstawowym nazywamy ten element macierzy, za pomocą którego
eliminowane są dalsze elementy w danej kolumnie. Do tego celu wykorzystywaliśmy
elementy leżące na przekątnej.
Gdyby element podstawowy był równy zero, to przeprowadzenie eliminacji byłoby
niemożliwe. Aby tego uniknąć stosuje się wybór elementu podstawowego (pivoting) . Przed
wykonaniem kroku eliminacji mającego na celu eliminację elementów znajdujących się w j -
tej kolumnie i wierszach i=j+1, ..., m zamieniamy wiersze tak, by j -tym elementem
diagonalnym był element o największym module spośród pozostałych ( i=j+1 ... ) elementów
znajdujących się w j -tej kolumnie macierzy.
1
3) Eliminacja Gaussa
Macierz A można przedstawić w postaci iloczynu macierzy dolnej i górnej: LU
(
i
ê
ú
(
(
245774981.002.png
Wyznacznik obliczamy mnożąc przez siebie elementy na przekątnej diagonalnej. W
przypadku pojawienia się na przekątnej diagonalnej zera, zamieniamy wiersz gdzie wystąpiło
zero z wierszem, w którym jest największa wartość w tej kolumnie.
Macierz P nazywamy macierzą permutacji (nieosobliwa macierz zero-jedynkowa), dla
której zachodzi związek: P -1= P (zamiana wierszy jest symetryczna).
Rozkład LU można wykorzystać do rozwiązania układu równań liniowych postaci: Ax=b .
Znamy rozkład macierzy A w postaci: A=PLU . Równanie przyjmuje wówczas postać:
PLUx=b , która jest równoważna postaci: LUx=Pb (ponieważ P=P -1). W celu obliczenia x
trzeba rozwiązać pomocniczy układ równań: Ly=Pb , a wyznaczony wektor y wstawić do
równania: Ux=y .
Rozwiązanie układu Ly=c ( c=Pb ) równań z macierzą trójkątną dolną z jedynkami na
przekątnej sprowadza się do wyznaczenia kolejnych współrzędnych wektora y : Rozkład
å =
i
y 1
i n
=
c
-
l
y
,
i
=
1
...,
;
i
ik
k
k
Równania z macierzą górną Ux=y :
æ
å +
n
ö
c
x ii
ç
è
-
u
x
÷
ø
i
ik
k
=
k
=
i
1
,
i
=
n
,
n
-
1
...,
1
i
u
4) Rozkład Cholesky’ego (zwany rozkładem Banachiewicza ) polega na zapisaniu macierzy
A w postaci iloczynu R T R gdzie macierz R jest macierzą trójkątną górną . Zakładając, że
liczby na przekątnej macierzy R są dodatnie, (zaś elementy pozadiagonalne „niezbyt duże”)
rozkła d R T R mo żna uzyskać dla dowolnej macierzy dodatnio określonej korzystając z:
å
i
-
1
r
=
a
-
r
2
,
dla
i
=
1
2
...,
n
;
ii
ii
ik
k
=
1
a
r ii
=
(
ji
-
r
jk
×
r
ik
)
,
dla
j
=
i
+
1
i
+
2
...,
n
ji
r
Rozkład Cholesky’ego realizuje w programie MATLAB funkcja chol . Rozkład ten
można stosować również w przypadku macierzy zespolonych. Każda macierz zespolona
którą podlega rozkładowi Cholesky’ego spełnia równanie A ’= A .
1) Aproksymacja jest to przybliżanie, zastępowanie jednych wielkości drugimi.
Aproksymacja może dotyczyć dowolnych wielkości matematycznych – liczb, funkcji,
krzywych, obszarów, wektorów, macierzy. Zastępowanie danej wielkości inną obarczone jest
pewnym błędem. Oszacowanie wielkości błędu pozwala na ocenę, czy dane przybliżenie jest
zadawalające, czy też nie.
Niech poszukiwana jest krzywa
y =
F
( x
)
dla zadanej liczby punktów: )
x
=
Aproksymacja stosowana jest wówczas, gdy ilość zadanych punktów m jest mniejsza od
ilości nieznanych współczynników n krzywej F(x) .
Zwykle nie można przeprowadzić krzywej przez wszystkie punkty. Poszukiwana jest
wówczas najbliższa krzywa w sensie minimum kwadratu błędu .
F n
(
x
)
c
1 x
f
1
(
x
)
+
c
2
f
2
(
x
)
+
...
+
c
n
f
(
)
2
( i
i y
,
jest opisana równaniem:
245774981.003.png
Najbardziej podstawową i najprostszą metodą aproksymacji średniokwadratowej jest
aproksymacja funkcją liniową czyli regresja liniowa . Wówczas:
f
1
(
x
)
= x
x
,
f
2
(
)
=
1
f j
Dla kolejnych punktów otrzymujemy:
(
x
)
=
1
ì
é
x
1
ù
é
y
ù
ï
c
x
+
c
=
y
1
1
ê
ú
ê
ú
ï
1
1
2
1
x
1
é
c
ù
y
ê
ú
ê
ú
í
c
x
+
c
=
y
lub
2
1
=
2
ë
û
1
2
2
2
ê
⋮
ú
c
ê
⋮
ú
ï
⋮
2
ê
ú
ê
ú
ï
x
1
y
ë
û
ë
û
î
c
x
+
c
=
y
m
m
n
m
2
m
= , gdzie: r – wektor pionowych odległości pomiędzy
poszukiwaną krzywą a zadanymi punktami. Szukane jest takie rozwiązanie, dla którego:
å =
yr -
m
i r
2
lub macierzowo r
r T osiąga minimum. Stąd:
i
1
r
T
r
=
(
y
-
Ac
) (
T
y
-
Ac
)
=
y
T
y
-
y
T
Ac
-
c
T
A
T
y
+
c
T
A
T
Ac
=
y
T
y
-
2
y
T
Ac
+
c
T
A
T
Ac
Iloczyn ten osiągnie minimum jeśli:
d T
( )
T
r
=
0
®
-
A
T
y
+
A
Ac
=
0
dc
=
Powyższe równanie nazywane jest równaniem aproksymacji .
( ) y
AA T
T
c
A
Równanie aproksymacji
( ) y
AA T
T
c
=
A
jest prawdziwe dla dowolnej funkcji aproksymacji:
xF n
(
)
=
c
11 x
f
(
x
)
+
c
2
f
2
(
x
)
+
...
+
c
n
f
(
)
gdzie: j
c - nieznane współczynniki,
f j - funkcje
( )
x
bazowe, zaś macierze A , c i y :
( )
é
f
1
x
1
f
2
( )
x
1
f
n
( )
x
1
ù
é
c
1
ù
é
y
1
ù
ê
ú
ê
ú
ê
ú
( )
( )
( )
ê
f
x
f
x
f
x
ú
ê
c
ú
ê
y
ú
A
=
1
2
2
2
n
2
,
c
=
2
,
y
=
2
ê
⋮
ú
ê
⋮
ú
ê
⋮
ú
ê
ú
ê
ú
ê
ú
ë
f
( ) ( )
x
f
x
f
( )
x
û
ë
c
û
ë
y
û
1
m
2
m
n
m
n
m
Aproksymacja funkcją liniową może okazać się nie wystarczająca wówczas, gdy między
danymi występuje bardziej złożona zależność. Stosuje się wówczas zazwyczaj aproksymację
wielomianem :
xW r
( )
=
a
x
r
+
a
1 ... a
x
-
1
+
+
a
x
+
r
r
-
1
0
2) Interpolacja polega na poszukiwaniu funkcji pomiędzy znanymi punktami (podobnie jak
aproksymacja). W odróżnieniu jednak od aproksymacji funkcja ta przechodzi przez te punkty.
Jeżeli poszukiwana jest funkcja poza zakresem zadanych punktów mamy do czynienia z
ekstrapolacją .
Wybrane metody interpolacji:
a) interpolacja wielomianem:
P
n c
11
( )
x
=
c
x
n
-
1
+
c
x
n
-
2
+
+
c
x
+
-
2
n
-
1
n
b) interpolacja
wielomianem
Lagrange’a:
( )
( )
( )
( )
( )
Õ ¹
n
x
-
x
P
x
=
y
L
x
+
y
L
x
+
+
y
L
x
,
gdzie
L
x
=
k
n
-
1
1
1
2
2
n
n
j
x
-
x
kk k
=
1
j
j
3
Pozostałe funkcje:
co można zapisać w postaci macierzowej Ac=y . Równanie to dla m>n nie ma dokładnego
rozwiązania, stąd: Ac
r
stąd:
245774981.004.png
 
c) interpolacja
wielomianem
Newtona:
P
-
1
( )
=
c
1
+
c
2
(
x
-
x
) (
c
3
x
-
x
1
)(
c
-
x
2
)
+
2
c
n
(
x
-
x
1
)(
x
-
x
) (
x
-
x
n
)
4
x
+
+
⋯
n
1
245774981.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin