IV.13.14.15 Metody numeryczne rozwiązywania układów liniowyc, IV


IV. 13. Metody numeryczne rozwiązywania układów liniowych równań algebraicznych.

1. Metody bezpośrednie:

E1 a11x1 + a12x2 +...+ a1nxn = b1

E2 a21x1 + a22x2 +...+ a2nxn = b2

* Ax = b

E1 a31x1 + a32x2 +...+ a3nxn = b3

rozwiązanie jest jednoznaczne gdy:

b ≠ 0 i det(A) ≠ 0

    1. Gaussa (eliminacji) - polega na sprowadzeniu równania Ax = b

do postaci górnotrójkątnej Ux = (b)<n>

U - macierz otrzymana w wyniku wykonania n operacji elementarnych na macierzy A

(b)<n> - wektor otrzymany w wyniku wykonania n operacji elementarnych ba

Def. Operacja elementarna nie zmienia wyniku równania np:

λEi → Ei λ ≠ 0

Ei +λEj → Ei

Ei ,Ej -wiersze równania.

Postępowanie wprzód

krok 1

0x01 graphic

krok 2 działanie

0x01 graphic
0x01 graphic

krok 3 działanie

0x01 graphic
0x01 graphic

koniec postępowania wprzód.

Postępowanie wstecz:

0x01 graphic
0x01 graphic
itd...

jeśli na przekątnej macierzy A znajduje się 0 to procedura zostaje przerwana.

Def. Macierz A nazywamy macierzą z silnie dominującą przekątną główną jeśli

0x01 graphic

Def. Macierz A nazywamy dodatnio określoną jeśli forma kwadratowa

xTAx > 0 dla dowolnego x=0

Tw. Gdy macierz A ma silnie dominującą przekątną główną jest nieosobliwa. Jest to warunek wystarczający.

Ponadto rozwiązanie równania Ax =b można otrzymać metodą Gaussa bez zmiany kolejnści wierszy i kolumn i rozwiązanie jest silnie stabilne ze wzgl edu na wzrost błędu zaokrąglenia.

Tw. Gdy macierz A jest dodatnio określona to jest nieosobliwa. Jest to warunek wystarczający. Ponadto rozwiązanie równania Ax =b można otrzymać metodą Gaussa bez zmiany kolejnści wierszy i kolumn i rozwiązanie jest silnie stabilne ze wzgl edu na wzrost błędu zaokrąglenia.

Tw. Silwestra. Macierz A jest dodatnio określona jeśli ma wszystkie wartości wlasne WKW

1.2. Metoda Gaussa z częściowym wyborem elementu wiodącego.

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
k

0x08 graphic
m szukamy p elementu wiodącego

k z warunku :

apk = maxaik

0_ ... p i = k....m

przestawiamy Ep na miejsce Ek ( należy notować liczbę

przestawień)

1.3. Metoda Gaussa z pełnym wyborem elementu wiodącego.

api = maxaij

i,j = k....m

1.4. Metoda Gaussa z częściowym wyborem elementu wiodącego i skalowaniem.

Definicja współczynnika si dla każdego wiersza si = maxaij

j = 1...m

dla otrzymania zer w pierwszej kolumnie ustalamy numer k równania z warunku

0x01 graphic
i dokonujemy zamiany E1 na Ek

j = 1...n

1.2. Metoda Dolittle'a lii = 1

Crouta uii = 1

Choleskiego uii = lii

Ax =b

A = LU L - mac. dolnotrójkątna U - mac. górnotrójkątna

LUx =b

Lc =b otrzymujemy c

Ux =c otrzymujemy x

wyznaczenie L i U

dane

0x01 graphic

po wymnożeniu macierzy L i U

u11 = a11

u12 = a12

u13 = a13 itd...

Dla macierzy symetrycznej i dodatnio określonej rozklad trójkątny upraszcza się do postaci

A = LLT

W metodzie Choleskiego dla uniknięcia pierwiastkowania korzystniejszy jest rozkład

A = LDLT L - macierz trójkątna z jedynkami na przekątnej

D - macierz diagonalna

Ax =b

LDLTx =b

DLTx = c

Lc =b otrzymujemyc

Dd =c otrzymujemyd

LTx =d otrzymujemyx

1.6. Metoda Gaussa - Jordana.

Ax =b

A-1Ax =b

x = A-1b

wyznaczenie macierzy A-1 -postępowanie podobnie jak w metodzie Gaussa.

0x01 graphic

2.1. Układy równań podokreślone.

A-macierz o wymiarze m*n gdzie m < n

metoda Gaussa - Jordana

0x08 graphic
0x08 graphic
0x08 graphic

Ix1 -Ax2 =b

2.2. Układy nadokreślone.

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

3. Metody iteracyjne - polegają na przyjeciu wektora startowego x0 oraz generowanie ciągu wektorów xk zbieżnych do rozwiązania x.

3.1. Metoda Jacobiego.

Ax =b

A = D - L - U

x<k> = T(x )<k-1>+c

(D-L-U)x =b

D(x)<k> = (L-U) (x)<k-1>+b

Zakończenie iteracji gdy norma względna

0x01 graphic
dąży do zera.

3.2. Metoda Gaussa - Seidela

(D-L-U)x =b

(x)<k> = (D-L)-1U (x)<k-1>+(D-L)-1b

Warunkiem wystarczającym by proces był zbieżny dla dowolnego x0 jest aby mac. A miała silnie dominującą przekątną główną.

3.3. Metoda relaksacyjna

Def. Wektor reziduum r =b - Ax

0x01 graphic

0x01 graphic

ω - wsp. relaksacji gdy 0< ω<1 - podrelaksacja

ω>1 - nadrelaksacja

IV. 14. Metody aproksymacji funkcji jednej zmiennej.

Aproksymację stosujemy gdy :

  1. złożoną funkcję chcemy przedstawić w prostej postaci.

  2. funkcja dana jest w postaci tablicy

  3. funkcja jest nieznana ( poszukiwanie równań różniczkowych )

Ogólnie - przedstawiamy funkcję w postaci kombinacji liniowej pewnych danych funkcji bazowych.

φ(x) = a0u0(x) + a1u1(x) + ... + anun(x) ≈ f(x)

B_(x) = [ u0(x), u1(x), ..., un(x) ] - macierz funkcji bazowych ( liniowo niezależne)

aT = [ a0, a1, ... , an ] - wektor nieznanych współczynników

φ(x) = B_(x)a

1.Aproksymacja punktowa.

- Funkcja f(x) dana jest w postaci tablicy x_= [x0, x1, ... , xn ] i odpowiadających wartości F = [f0, f1, ... , fn ].

-Należy dobrać współczynniki ai i=0,1...n tak aby

0x01 graphic

możliwie najlepiej przybliżał F(x) , ( baza B_(x) ułożona z jednomianów )

-Należy rostrzygnąć stopień wielomianu i kryterium jakości aproksymacji, najczęściej stosuje się kryterium najmniejszych kwadratów.

0x01 graphic

Dla przypadku wielomianu uogólnionego:

φ(x) = a0u0(x) + a1u1(x) + ... + amum(x) powstaje układ równań o postaci :

0x01 graphic
0x01 graphic

w zapisie macierzowym:

UTUa = UTF

gdzie:

0x01 graphic

Równania znacznie się upraszczają gdy funkcje uk(x) są ortogonalne

0x01 graphic

wtedy UTU przyjmie postać:

0x01 graphic

np.: funkcje Czebyszewa,

0x01 graphic

2. Aproksymacja calkowa.

Funkcja f(x) jest określona i ciągla w przedziale [a,b]

0x01 graphic

metoda najmniejszych kwadratów

0x01 graphic
0x01 graphic
0x01 graphic

np.: dla m = 2

0x01 graphic

0x01 graphic
0x01 graphic

3. Aproksymacja funkcjami ortogonalnymi.

Def. Funkcja wagowa - taka funkcja w(x) , że w(x) ≥ 0 , w [a,b] , lub w(x)≠0 w pewnym przedziale [a,b], np.:

0x01 graphic
w∈[-1,1]

0x01 graphic

0x01 graphic
- błąd średni kwadratowy z wagą w .

0x01 graphic

0x08 graphic

1) 0 j≠k

2) αj > 0 j=k - funkcja ortogonalna z wagą

3) αj = 1 j=k - funkcja ortogonalna

Wielomiany Legendra w(x)1 w [-1,1] - ortogonalne

Funkcja Czebyszewa

0x01 graphic
w [-1,1] - ortogonalne

Jeśli f(x) jest aproksymowalne w [a,b] to dokonujemy przekształcenia na przedział [-1,1] według wz:

0x01 graphic
t ∈ [-1,1]

0x01 graphic

IV. 15. Metody numeryczne rozwiązywania równań nieliniowych.

1)Dobór algorytmu gwarantującego zbieżność iteracji.

2)Dobór punktu startowego.

1. Metoda bisekcji polega na systematycznym okrojeniu przedziału w którym istnieje pierwiastek.

f(x) ∈ (a,b) f(a)f(b) < 0

0x01 graphic

gdy : f(a1)f(ρ1) > 0 to a2 = ρ1 b2 = b1

f(a1)f(ρ1) < 0 to a2 = a1 b21

warunek zakończenia iteracji ρn - ρn-1 < ε1 i f( ρn ) < ε2

2. Metoda punktu stałego.

Def. Punktem stałym przekształcenia g nazywamy pierwiastek x = ρ , g(x) = x , f(x) = 0

Przykład :

ex = x+2 ex-2=x g(x)=ex-2

ρn+1 = g(ρn)

ρn+1 = eρn - 2

3. Metoda stycznych Newtona - Raphsona.

zał: f(x) ∈ C2 w (a,b) x ∈ [a,b] i jest przybliżeniem pierwiastka takim że,

f `(x ) ≠0 , x -p - małe

f(x)=f(x +( x-x ))=f(x )+f `(x )(x-x)+ ...

gdy : x=p to f(p)≡0 ≈ f(x )+f `(x )(p-x )

0x01 graphic

Wzór iteracyjny

0x01 graphic
n=1,2...

4. Metoda siecznych.

0x01 graphic

wzór iteracyjny:

0x01 graphic

wadą jest to, że muszą być dwa punkty startowe.

5. Metoda Reguła-Falsi

- zmodyfikowana metoda siecznych tak aby w procesie iteracji pierwiastek był zawsze zawarty w przedziale [ai ,bi] , f(ai )f(bi ) < 0

0x01 graphic

lub:

an=an-1 ; bn = pn gdy f(an-1)f(pn) < 0

an=pn ; bn = bn-1 gdy f(an-1)f(pn) > 0

0x01 graphic

0x01 graphic

0x01 graphic

1 0_

1

1

1

0_ 1

0x01 graphic

G_

0x01 graphic

1 0_

1

1

0_ 1



Wyszukiwarka

Podobne podstrony:
4 Metody numeryczne rozwiązywania układów równań2
4 Metody numeryczne rozwiązywania układów równań
MN energetyka zadania od wykładowcy 09-05-14, STARE, Metody Numeryczne, Część wykładowa Sem IV
MN energetyka zadania od wykładowcy 09-05-14, STARE, Metody Numeryczne, Część wykładowa Sem IV
Kalend.-Ćwiczeń-z-Now.-Met.-Anal.-Żywn.-13-14, Nowoczesne metody analizy żywności
wspolczesna zagadnienia, MOJE 13,14,15,16, Halina Poświatowska
wug 2,3,4,5,11,12,13,14,15
3 Metody numeryczne rozwiązywania równań algebraicznych
midnight sun 13 14 15
Lab 13 14 15 16 Multimedia Klasa 4 2011 2012 Lista4, Informatyka, Technikum, Grafika
klima pytania, 13 14 15 16 17 18, Pytanie nr
Metody numeryczne rozwiązywania równań Maxwella w kwazijednowymiarowych strukturach fotnicznych
13 14 15
Przepowiednia 13, 14 i 15 nowy porządek świata, zmiany po III wojnie światowej
13 14 15 16

więcej podobnych podstron