3) Eliminacja Gaussa
Macierz A można przedstawić w postaci iloczynu macierzy dolnej i górnej: A = LU
Metoda eliminacji Gaussa polega na wyzerowaniu elementów znajdujących się pod
przekÄ…tnÄ…:
a11 a12 ‹Ä… a1n
îÅ‚ Å‚Å‚
ïÅ‚
a21 a22 ‹Ä… a2n śł
ïÅ‚ śł
A(0) = A =
ïÅ‚ śł
î" î" î" î"
ïÅ‚
an1 an2 ‹Ä… ann śł
ðÅ‚ ûÅ‚
Etapy metody:
od wierszy 2, 3, ..., n odejmujemy wiersz przemnożony tak, by wyraz w pierwszej kolumnie
był równy zero, przez:
1)
ai(1
li1 =
(1
a11)
W efekcie otrzymujemy macierz:
(1 (1 (
îÅ‚ Å‚Å‚
a11) a12) ‹Ä… a11)
n
ïÅ‚
(1 (
0 a22) ‹Ä… an1) śł
2
ïÅ‚ śł
A(1) =
ïÅ‚ śł
î" î" î" î"
ïÅ‚ śł
( (1
0 an1) ‹Ä… ann) ûÅ‚
ïÅ‚ śł
ðÅ‚ 2
postępujemy tak samo zerując elementy pod przekątną w drugiej kolumnie macierzy A(1):
1
ai(2)
li2 =
(1
a22)
aż do uzyskania macierzy A(n-1), która jest wyznaczaną macierzą trójkątną górną U:
(n- (n- (n-
îÅ‚ Å‚Å‚
a11 1) a12 1) ‹Ä… a1n 1)
ïÅ‚
(n (
0 a22- 1) ‹Ä… ann- 1) śł
2
ïÅ‚ śł
U = A(n- 1) =
ïÅ‚ śł
î" î" î" î"
ïÅ‚ śł
(n
0 0 ‹Ä… ann- 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
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
yi = ci - lik yk , i = 1, ..., n;
"
k = 1
Równania z macierzą górną Ux=y:
n
ëÅ‚ öÅ‚
ìÅ‚ ci - uik xk ÷Å‚
"
íÅ‚ k = i+ 1 Å‚Å‚
xi = , i = n, n - 1, ...,1
uii
4) Rozkład Cholesky ego (zwany rozkładem Banachiewicza) polega na zapisaniu macierzy
A w postaci iloczynu RTR 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ład RTR można uzyskać dla dowolnej macierzy dodatnio określonej korzystając z:
i- 1
2
rii = aii - rik , dla i = 1, 2, ..., n;
"
k = 1
(a - rjk Å" rik ), dla j = i + 1, i + 2, ..., n
ji
rji =
rii
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.
y = F(x) (xi, yi )
Niech poszukiwana jest krzywa dla zadanej liczby punktów:
F(x) = c1 f1(x) + c2 f2(x) + ...+ cn fn(x)
jest opisana równaniem:
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.
2
Najbardziej podstawową i najprostszą metodą aproksymacji średniokwadratowej jest
f1(x) = x, f2(x) = 1
aproksymacja funkcją liniową czyli regresja liniowa. Wówczas:
f (x) = 1
Pozostałe funkcje:
j
Dla kolejnych punktów otrzymujemy:
Å„Å‚
x1 1 y1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ôÅ‚
c1x1 + c2 = y1 ïÅ‚
x2 1śł c1 ïÅ‚ y2 śł
ôÅ‚ îÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
c1x2 + c2 = y2 lub =
òÅ‚
ïÅ‚
ïÅ‚ śł ïÅ‚ śł
î" c2 śł î"
ðÅ‚ ûÅ‚
ôÅ‚ î"
ïÅ‚ śł ïÅ‚ śł
ôÅ‚
cnxm + c2 = ym ðÅ‚ xm 1ûÅ‚ ðÅ‚ ym ûÅ‚
ół
co można zapisać w postaci macierzowej Ac=y. Równanie to dla m>n nie ma dokładnego
r = y
rozwiÄ…zania, stÄ…d: - Ac
, gdzie: r  wektor pionowych odległości pomiędzy
poszukiwaną krzywą a zadanymi punktami. Szukane jest takie rozwiązanie, dla którego:
m
ri2
lub macierzowo osiÄ…ga minimum. StÄ…d:
" rTr
i= 1
T
rT r = ( y - Ac) ( y - Ac)
= yT y - yT Ac - cT AT y + cT AT Ac
= yT y - 2yT Ac + cT AT Ac
d
(rT r) = 0 - AT y + AT Ac = 0
Iloczyn ten osiągnie minimum jeśli:
dc
stÄ…d: (AT A)c = AT y
Powyższe równanie nazywane jest równaniem aproksymacji.
Równanie aproksymacji (AT A)c = AT y jest prawdziwe dla dowolnej funkcji aproksymacji:
f ( x)
F(x) = c1 f1(x) + c2 f2(x) + ...+ cn fn (x)
gdzie: cj - nieznane współczynniki, - funkcje
j
bazowe, zaÅ› macierze A, c i y:
f1( x1) f2( x1) ‹Ä… fn(x1) c1 y1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚ śł
f1( x2) f2( x2) ‹Ä… fn( x2)śł , c = ïÅ‚ c2 śł y2
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
A = , y =
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
î" î" î"
ïÅ‚ ïÅ‚ śł ïÅ‚ śł
f1( xm) f2( xm) ‹Ä… fn(xm)śł cn ym
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
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ę
W ( x) = ar xr + ar- 1xr- 1 + ...+ a1x + a0
wielomianem:
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:
Pn- 1( x) = c1xn- 1 + c2xn- 2 + ‹Ä… + cn- 1x + cn
a) interpolacja wielomianem:
b) interpolacja wielomianem Lagrange a:
n
x - xk
Pn- 1(x) = y1L1(x) + y2L2(x) + ‹Ä… + ynLn( x), gdzie Lj(x) =
"
xj - xk
k = 1,k `" j
3
c) interpolacja wielomianem Newtona:
Pn- 1(x) = c1 + c2( x - x1) + c3(x - x1)(c - x2) + ‹Ä… + cn( x - x1)( x - x2)ï"( x - xn)
4