INTERPOLACJA
Na czym polega zadanie interpolacji ?
Zadaniem interpolacji jest wyznaczenie przybliżonych wartości funkcji w punktach nie będących węzłami oraz oszacowanie błędu tych przybliżonych wartości .W tym celu należy znaleźć funkcje p(x), zwaną funkcją interpolacyjną , którą w węzłach interpolacji przyjmujemy takie same wartości co funkcja f(x). Dla pełnego zdefiniowania zadania interpolacji należy ,jeszcze określić zbiór , w którym szukamy funkcji p(x) spełniające warunki interpolacji .
Jaki jest wpływ rozmieszczenia węzłów na dokładność interpolacji ?
Wraz ze wzrostem ilości węzłów błędy powinny maleć dla odpowiednich metod.
Na czym polega zbieżność procesu interpolacji?
Dla odpowiedniej funkcji musi być dobrana odpowiednia metoda oraz wraz ze wzrostem ilości węzłów powinny maleć błędy.
Aby zmierzyć dokładność interpolacji należy :Zwiększyć ilość węzłów, dobrać odpowiednią metodę, dobrać odpowiednie rozmieszczenie węzłów.
INTERPOLACJA WIELOMIANOWA
Interpolacja wielomianowa: Mamy n węzłów i n wartości. Stopień wielo
mianu n-1
Wielomian jest postaci:
Żeby obliczyć n współczyn. mamy n punktów.
to spełnia układ równań normalnych;
Macierz Vandermoude’a
Jeżeli detA¹0 – mamy jedno rozwiazanie
OPISZ METODĘ INTERPOLACJI LAGRANGE’a
Zadaniem interpolacyjne Lagrange’a polega na polega na znalezieniu wielomianu spełniającego dla zadanych węzłów (x0,x1,...,xn) i wartości (f0,f1,...fn) warunki :dla 0<=i<=n
Algorytm sprowadza się do wykorzystania jawnej postaci rozwiązania tego zadania , zapisanego następująco :
INTERPOLACJA NEWTONA
Mamy (n+1) par węzłów, na których budujemy wzór interpolacji Newtona za pomocą ilorazów różnicowych. Ogólny wzór:
Aby wyznaczyć kolejne bi podstawiamy x = xi.
INTERPOLACJA ODWROTNA
Polega na wyznaczeniu wartości zmiennej niezależnej x, której odpowiada dana wartość funkcji nie występująca w tablicy wartości. Po wyznaczeniu tych wartości stosujemy któryś ze znanych wzorów interpolacyjnych, zamieniając miejscami zmienne x i y w tablicy i we wzorze.
INTERPOLACJA HERMITE’A
Przypadek interpolacji za pomocą wielomianu Wm(x) stopnia m = n + r + 1, który w węzłach od x0 do xn przyjmuje wartości y0 do yn f-cji f(x) oraz w pewnych węzłach od x0 do xr (r <= n) wartości od y’0 do y’r pochodnej f-cji f’(x).
Gdzie są wielomianami stopnia m = n + r + 1.
OPISZ METODĘ INTERPOLACJI FUNKCJĄ SKLEJANĄ.
W przedstawionych powyżej algorytmach interpolacji zakładano , że istnieje jedna funkcja interpolacyjna w całym przedziale <a,b>. Przy tym założeniu jedyną metodą uzyskania lepszego przybliżenia jest zwiększanie stopnia wielomianu interpolacyjnego . Można jednak podzielić przedział <a,b> na N części , tzn. a=x0<x1<...<xn= b
W każdym z przedziałów <xi,xi+1> możemy przeprowadzić interpolację inną funkcją ,istotne jest przy tym aby była to funkcja ciągła wraz z odpowiednimi pochodnymi na całym przedziale <a,b>. Funkcje o tych samych własnościach nazywają się funkcjami sklejanymi. Znajdowanie funkcji sklejanych stopnia 3 spełniającej warunki interpolacji gdzie funkcja s(xi) należy C(2) [x0,x1] i ponadto spełniają warunki :
- dla xi-1£x£xi
-
Warunki te można zapisać w postaci układu równań liniowych z macierzą trojdiagonalną .
OPISZ METODĘ INTERPOLACJI THELIEGO.
Jest to metoda konstrukcji wymiernej funkcji interpolującej spełniającej warunki:
P(x i)/Q(x i) = f i dla 0\<i \<n
P należy ? l , Q należy ? m gdzie m = n/2 , l = n – m
Rozwiązanie ma postać ułamka łańcuchowego. Współczynniki tego ułamka są znajdowane na podstawie tablicy odwrotności ilorazów liczonych według wzoru: h( xo ,...,xl, xm, xn) = (xm - xn) / [h( xo ,...,xl, xm) – h(( xo ,...,xl, xn)]
Rozwiązanie może nie istnieć, gdy któraś odwrotność ilorazu różnicowego jest równa
UKŁADY RÓWNAŃ LINIOWYCH
TWIERDZENIE CRONECKERA-CAPELLIEGO
Warunkiem koniecznym i wystarczającym rozwiązalności ogólnego układu równań liniowych jest równość rzędu macierzy W współczynników układu i rzędu macierzy uzupełnionej U:
r = r(W) = r(U)
Gdy wspólny rząd r tych macierzy jest równy liczbie niewiadomych n, to Układ r-nań ma dokładnie 1 rozwiązanie, gdy r < n, to układ ma nieskończenie wiele rozwiązań, które zależą od n-r dowolnych parametrów. Zawsze r(W) <= n. Gdy rząd r(W) <> r(U), to układ jest sprzeczny.
METODA ELIMINACJI GAUSSA
Rozwiązywanie układu równań liniowych metodą eliminacji Gaussa przebiega w dwóch etapach:
* pierwszy etap jest nazywany etapem postępowania prostego (etapem eliminacji niewiadomych),
* drugi etapem - postępowania odwrotnego.
Na etapie postępowania prostego wyjściowy układ równań zostaje przekształcony do postaci równoważnej (tzn. takiej, która posiada dokładnie takie same rozwiązania co układ wyjściowy) z trójkątną górną macierzą główną układu. Przekształcenie to jest realizowane w n krokach.
Krok 1 (eliminacja niewiadomej x1 z równań 2, 3, ... ,n).
Krok 2 (eliminacja niewiadomej x2 z równań 3, 4, ... ,n).
Aż do wyeliminowania zmiennej xn-1 z równania n
Na etapie postępowania odwrotnego trzeba obliczać kolejne pierwiastki
od xn do x0.
METODA ELIMINACJI GAUSSA Z PEŁNYM WYBOREM ELEMENTU PODSTAWOWEGO
Załóżmy, że układ równań rozwiązujemy metodą eliminacji Gaussa i zostało już wykonanych k-1 kroków etapu postępowania prostego. Wyjściowy układ równań został przekształcony do układu postaci
Algorytm z pełnym wyborem elementu podstawowego jest następujący:
1) wyszukujemy element ars spełniający warunek:
,
2) przestawiamy w układzie równanie r z równaniem k oraz kolumnę s
z kolumną k,
3) eliminujemy niewiadomą xk z równań k + 1, k + 2, …, n
zgodnie z algorytmem k-tego kroku prostej eliminacji Gaussa. Jeżeli , to żaden element podstawowy w tej metodzie nie będzie równy zeru.
SCHEMAT ELYMINACJI GAUSSA Z CZĘŚCIOWYM WYBOREM
ELEMENTU GŁÓWNEGO
Postępowanie w k-tym kroku
1. Wybrać r:
2. Przestawić wiersze k i r , przestawienie zapamiętać
3. Obliczyć
4. Obliczyć
Ostatecznie
METODA GAUSSA-JORDANA***************
W tej metodzie rozwiązanie układu równań liniowych uzyskujemy w jednym etapie. Podobnie jak w metodzie eliminacji Gaussa, obliczenia przebiegają w n krokach.
Krok 1 (eliminacja niewiadomej x1 z równań 2, 3, ... , n).
Krok 2 (eliminacja niewiadomej x2 z równań 1, 3, ... , n).
Kroki 3, 4, ... ,n
W k-tym (k=3,4,..,n) kroku algorytmu eliminujemy niewiadomą
xk z równań 1,2, …, k-1, k+1, …, n postępując podobnie jak w
krokach 1 i 2 metody. W konsekwencji po n-tym kroku
otrzymujemy układ równań
reprezentujący gotowe rozwiązanie układu
METODA GAUSSA-JORDANA**********************
ROZKŁAD LU
1.Metoda Doolittle’a: macierz L ma 1-nki na diagonali i jest macierzą trójkątną dolną (wartości na dole), U – macierz trójkątna górna. Współczynniki macierzy L i U wyznaczamy albo jako przyrównanie elementu macierzy A z elementem macierzy L*U, albo przy użyciu metody eliminacji Gaussa:
a)wyznaczenie L(i) - macierz na diagonali ma 1-nki, reszta elementów – zera oprócz i-tej kolumny, poniżej danej 1-nki. Wartości te obliczamy ze
wzoru gdzie j = 1, …, n i = j + 1, …, n
b)wyznaczenie macierz A(k) = L(k-1)*A(k-1) przy założeniu, że A(1) = A. punkty a wykonujemy (n-1) razy, punkt b - n razy i macierz
U = A(n)
2.Metoda Crouta: macierz U ma jedynki na diagonali i jest macierzą trójkątną górną, a macierz L jest macierzą trójkątną dolną. Współczynniki macierzy L i U wyznaczamy jako przyrównanie elementu macierzy A z elementem macierzy L*U.
3.Metoda Cholesky’ego: macierz U jest macierzą
trójkątną górną, a macierz L jest macierzą trójkątną dolną., przy czym lii = uii. Współczynniki macierzy L i U wyznaczamy jako przyrównanie elementu macierzy A z elementem macierzy L*U.
...
lukaszzychzych