Metody rozwiązań układów równań liniowych:

1. dokładne

1. eliminacyjne

• met. Gaussa

• met. Jordana

2. dekompozycyjne

• met. Gaussa-Crouta

• met. Gaussa- Dolittle'a

• met. Cholewskiego

1. przybliżone

• met. Iteracji prostej

• met. Gaussa-Seidla

• met. Nadrelaksacji

Met. Gaussa

I etap- eliminacji(Przekształcenie ukł. równań)

II etap - rekursja(krok wsteczny). Prowadzi do wyznaczenia niewiadomych.

Cechy:

1. Może się zdarzyć tak, że mimo iż det([A])≠0, że pewien dzielnik a_kk^(k-1) będzie równy zero. Wtedy algorytm nie zadziała. Wówczas należy przestawić wiersze, aby na gł. Przekątnej….

2. jeżeli det A=0 to zamiana wierszy nie usunie dzielenia przez 0, jeżeli detA≠0 to zawsze istnieje taka kombinacja wierszy, że wyrazy na gł. Przekątnej będą różne od 0.

3. Jeżeli w miejsce elementów na gł. Przekątnej zapisać wielkość dzielników, któ®e stosowaliśmy a_kk^(k-1) to można łatwo obliczyć wartość wyznacznika

4. Jeżeli macierz wsp. A jest dodatnia określona ……………..to wszystkie dzielniki d_k są większe od zera i otrzymujemy algorytm bez przestawień wierszy

5. Łączna liczba oper. Potrzebna do rozw. układu równań stopnia n metodą Gaussa jest szacowna na n³

6. Odmianą met. Gaussa jest wariant z wyborem elementu głównego. Rozw. w tym wariancie polega na: przed przystąpieniem do eliminacji i-tego wiersza zamieniamy wiersze i kolumny dolnej podmacierzy tak, aby uzyskać maksymalny wyraz d_i na głównej przekątnej

Met. Dekompozycyjne polegają na takim przekształceniu ukł. równań, aby nabrał on postaci odpowiedniej do rozwiązania ukł. równań.

Tw.

Każdą nieosobliwą macierz kwadratową A o rozm. nxn można rozłożyć na iloczyn dwóch macierzy trójkątnych jeżeli wszystkie minory główne mac. A są różne od zera.

Rozkład można dokonać na n sposobów dobierając dowolnie n elementów na głównej przekątnej macierzy L lub mac. U

Met. Gaussa-Crouta

Jeżeli l_kk=0 to stosujemy przestawianie wierszy. Jeżeli macierz jest dodatnio określona to mamy algorytm bez przestawiania wierszy.

Met. Gaussa-Dolittle'a

Jeżeli macierz wsp. jest dodatnio określona to można również tak: [A]=[L][D][L]^T

Dla dodatnio określonych macierzy symetrycznych metoda Cholewskiego(Komputer długo oblicza bo pierwiastek liczy przez szeregi)

Met. Iteracyjne:

• Met. Siedla

• Met. Iteracji Gaussa

• Met. Nadrelaksacji

Met. Iteracji Gaussa

1. Zakładamy dowolne wartości x₁, x₂, x₃ i podstawiamy je po prawej stronie ukł. równ

2. Z tych równ. Wyznaczamy wart. x₁, x₂, x₃ po lewej stronie

3. Te wartości ponownie podstawiamy do równań po prawej stronie

4. Proces ten kontynuujemy aż różnica między wartościami wyznaczonymi w iteracjach będzie mniejsza od założonego błędu ε

Uwagi:

Najważniejszą wadą jest to, że możliwość uzyskania rozwiązania, zależy od przyjętych na początku wartości x₁, x₂, x₃, gdyż może się okazać, że proces iteracyjny jest słabo zbieżny lub w ogóle rozbieżny.

Zaletą jest prostota rozwiązania.

Met. Gaussa-Seidla:

1. zakł. Wartości x₁, x₂, x₃

2. wstawiamy do pierwsz. Równania x₂, x₃ i wyznaczamy nową wartość x₁

3. do drugiego równania wstawiamy nowe x₁ i stare x₃ i wyzna. Nową wart. x₂

4. do 3 równania wstawiamy nowe wart. x₁, x₂ i wyznaczamy x₃

5. Powtarzamy kroki 2, 3 i 4, aż do uzyskania rozwiązania.

Uwagi:

Proces jest zbieżny, gdy macierz współczynników jest symetryczna i dodatnio określona.

Met. Nadrelaksacji:

1. zakładamy dowolne wart x₁, x₂, x₃

2. Z 1 równania obl. Poprawkę ∆x₁, za nową wartość x₁ przyjmujemy x₁=x₁+∆x₁*w gdzie w- wsp. Nadrelaksacji

3. Z drugiego równ. wyzn. ∆x₂ i przyjmujemy x₂=x₂+∆x₂*w

4. Z 3 równania wyznaczamy x₃ i przyjmujemy x₃=x₃+∆x₃*w

5. Powtarzamy kroki 2, 3 i 4, aż max(│∆x₁│, │∆x₂│,│ ∆x₃│)≤ ε

Uwaga:

Gdy macierz wsp. Jest symetryczna i dodatnio określona metoda nadrelaksacji jest zbieżna dla wsp. 0<w<2. Zazwyczaj stosuje się 1,2<w<1,5

Wadą metod iteracyjnych jest, że nie da się określić, która metoda jest lepsza i krótsza dla jakiego ukł.

Metody te są efektywne, gdy macierze są duże, ale wiele tych WSP. Jest równych lub też gdy macierz wsp. Jest rzadka tzn. występuje wiele wsp.=0

Ma niewątpliwie zalety w przypadku obliczeń ręcznych, bo jest nie wrażliwa na błędy w trakcie obliczeń. Popełnienie błędu rachunkowego przy obl. Wart. powoduje jedynie zwiększenie liczby iteracji a nie prowadzi do uzyskania błędnego rozw.

Unikamy zaokrągleń matematycznych związanych z przekształceniem układów równań.

Met. iteracyjne są szczególnie skuteczne w przypadku komputerów o małej pamięci.

Do innych met. iteracyjnych zaliczamy:

• met. gradientów sprzężonych

• met. Aitkina

Standaryzacja- przejście z jednej postaci do drugiej.

Tw1.

Dowolna macierz kwadratowa [A] stopnia n ma dokładnie n rzeczywistych bądź zespolonych wartości własnych.

Tw2.

Macierz [A] ma wtedy i tylko wtedy wartość własną λ=0, gdy jest macierzą osobliwą.

Def.

Niezerowy wektor {x}i spełniający związek [A]{x}ⁱ= λ_i{x}ⁱ, gdzie λ_i jest wartością własną macierzy [A] nazywamy wektorem własnym macierzy [A] odpowiadającym wart. wł. λ_i. Każdy wektor własny jest określony z dokładnością do stałej k, gdzie k jest dowolną liczbą różną od 0.

Zazwyczaj liczbę k dobiera się w sposób szczególny, a mianowicie tak, aby:

• suma kwadratów składowych wektora {x}ⁱ była równa jedności

• pierwsza składowa wektora {x}ⁱ była równa 1

• największa składowa wektora {x}ⁱ była równa 1

• suma modułów składowych wektora {x}ⁱ była równa 1

Wektor spełniający jeden z tych warunków nazywamy wektorem własnym znormalizowanym albo unormowanym.

Tw3.

Jeżeli wielomian charakteryst. mac. [A] ma n różnych pierwiastków (wart. własn.) to wektory własne mac. [A] odpowiadające parom różnych wart. własnych są liniowo niezależne.

Tw4.

Jeżeli wartościami własnymi nieosobliwej mac. [A] są liczby λ_i gdzie i=1,2,…,n to wartościami własnymi mac. odwrotnej są liczby λ_i^-1 gdzie i-1,2,…,n.

Tw5.

Jeżeli wszystkie wartości własne mac. [A] są różne to istnieje przekształcenie przez podobieństwo [P]^-1[A][P]=[Ω], gdzie [Ω]=diag{λ₁,λ₂,…,λ_n}.

Najczęściej stosowane metody:

• met. Jacobiego

• met. Givensa

• met. wsp. do mac. trójdiagonalnej

• met. Housenholdera(przekszt. ma. wsp. do mac. trójdiagonalnej, ale nie przy pomocy mac. obrotu)

• metody LR i QR(znalezienie częstości oparte na kolejnych rozkładach mac. wsp. na mac. trójkątne)

• met. potęgowa(służy do wyliczania tylko jednej wartości własnej, największej albo najmniejszej)

Interpolacja polega na znalezieniu takiego przepisu y=f(x), aby funkcja ta przechodziła przez wszystkie punkty (x_i, y_i) i aby można było obliczyć wszystkie wartości funkcji dla x_imin≤x≤_xjmax

Ekstrapolacja - jeżeli szukamy funkcji, która przechodzi przez wszystkie punkty (x_i, y_i) ale chcemy znać wartości funkcji poza przedziałem.

Def.

Aproksymacja jest to poszukiwanie jednej f-cji, która w przedziale (x₁, x_n) najlepiej przybliża wartości f-cji od y₁ do y_n.

Sposoby interpolacji:

• interpolacja liniowa - poszukujemy interpolacji liniowe, która przechodzi przez p-kty (x_i, y_i)

• interpolacja kwadratowa- Chcąc wyznaczyć wartość f-cji w dowolnym p-cie x wybieramy 3 najbliższe temu p-ktowi wartości x_i-1,x_i,x_i+1, a następnie tak dobieramy wielomian II stopnia aby otrzymana f-cja przechodziła przez punkty y_i-1, y_i,y_i+1.

Metoda kolokacji

Poszukujemy f-cji y=f_(x) zadanej w nast. sposób. y=a₁f_1(x)+a₂f_2(x)+…+a_nf_n(x)

gdzie f-cje: f₁,f₂,…,f_n - są z góry założone tak, aby dobrze oddawały charakter opisywanej f-cji.

Kryteria aproksymacji:

1. Minimum sumy różnic: H=min∑∆y_i

2. Minimum sum wartości bezwzględnych różnych H=min∑│∆y_i │

3. Minimalizowanie maksymalnej różnicy H=min(max ∆y_i)

4. Minimum sumy kwadratów(metoda najmniejszych kwadratów)

Analiza statystyczna błędu:

1. standardowy błąd przybliżenia

2. Błąd standardowy różnicy

3. Współczynnik korelacji

Dwa kryteria oceny:

1. Aby wynik aproksymacji można uznać za wiarygodny S_y/x<S_y