|
PODSTAWY METOD NUMERYCZNYCH
Metody numeryczne jest to dział nauki zajmujący się rozwiązywaniem różnych zagadnień matematycznych za pomocą komputera. Podczas reprezentacji komputerowej dochodzi do wielu uproszczeń ponieważ nie każda liczba jest reprezentowana - nie istnieje pojęcie nieskończoności, dowolnie dużej dokładności, powstają luki („gaps”) w reprezentacji liczb rzeczywistych.
Źródła błędów w czasie obliczeń:
Błąd danych wejściowych - każdy pomiar jest zaokrąglony
Błędy zaokrągleń w czasie obliczeń
Błąd obcięcia błędy zaokrągleń w czasie obliczeń
Reprezentacja liczby ex jako rozwinięcie w szereg:
Liczby w komputerze zapisujemy w reprezentacji zmiennopozycyjnej:
x - liczba rzeczywista, znormalizowana reprezentacja dziesiętna:
x=sთmთ2C gdzie: |m|=0.1...1
Znormalizowana reprezentacja dwójkowa:
x=sთmთ2C |m|=0.5...1
gdzie : s - znak, m - mantysa (część ułamkowa), c - cecha (część całkowita)
Na zapis liczby poświęcamy odpowiednią liczbę bitów, przy czym:
- za dokładność zapisu odpowiada mantysa - im większą pamięć jej poświęcimy dostaniemy dokładniejszą reprezentację
- za zakres zapisu odpowiada cecha - zwiększenie ilości bitów na cechę odpowiada zwiększenie zakresu reprezenatacj
Przyjmijmy, że przeznaczmy na zapis liczby d bitów pamięci. Na mantysę przeznaczamy t bitów, natomiast na zapis cechy d-t-1 bitów (jeden bit odejmujemy na znak)
Ponieważ maksymalna cecha cmax = -c min= 2^d-t-1, a mantysa mt należy do przedziału <1/2, 1)
reprezentowane są liczby spełniające warunek:
Wynika z tego, iż liczby będące poza tym zakresem nie mogą być zapisane w naszym systemie
Pojawia się problem niedoboru i nadmiaru:
- dla liczb, których cecha < cmin - niedobór
- dla liczb, których cecha c>cmax - nadmiar
Reprezentacja zmiennopozycyjna jest uniwersalna, natomiast gdy chcemy operować na liczbach całkowitych
możemy stosować reprezentację stałopozycyjną:
a - liczba całkowita, na zapis przeznaczamy d bitów pamięci
zakres liczb reprezentowanych a należy do przedziału <-2^d+1,2^d-1>
Przy reprezentacji stałopozycyjnej mamy pewność dokładności wykonywanych działań
INTERPOLACJA
Zadaniem interpolacji jest utworzenie funkcji, która przebiega przez zadane punkty. Stosuje się różne klasy funkcji do interpolowania - wielomiany algebraiczne, funkcje sklejane, funkcje trygonometryczne.
Zadanie interpolacji możemy sformułować następująco:
W przedziale [a,b] mamy danych n+1 różnych punktów x0,x1,...,xn (węzły interpolacji) oraz wartości funkcji y=f(x) w tych punktach f(x0)=y0,f(x1)=y1,...,f(xn)=yn . Znaleźć funkcję F(x), która w węzłach interpolacji ma te same wartości co f(x) i przybliża f(x) w punktach.
I. Interpolacja wielomianowa:
Twierdzenie
Istnieje dokładnie jeden wielomian interpolacyjny stopnia co najwyżej n (nႳ0), który w punktach x0, x1,...,xn przyjmuje wartości y0,y1,...,yn
Wzór Lagrange'a
x0, x1,...,xn - zadany zbiór punktów
y0,y1,...,yn - zadane wartości funkcji w punktach
oznaczmy Wn+1=(x-x0)(x-x1)...(x-xn)
- jest to wzór interpolacyjny Lagrange'a, podstawiając do
niego zadane wartości otrzymujemy wzór wielomianu przechodzącego przez zadane punkty
II. Interpolacja funkcjami sklejanymi
Interpolacja funkcjami sklejanymi polega na „łączeniu punktów”, w każdym odcinku przybliżamy funkcję wielomianem ustalonego (niskiego) stopnia, tak aby funkcja przybliżająca była ciągła wraz z pochodnymi na przedziale interpolacji [a,b]
Interpolacja funkcjami sklejanymi stopnia pierwszego
Załóżmy, że dysponujemy zbiorem n+1 węzłów interpolacji wraz z wartościami funkcji
(x0,y0), (x1,y1), ..., (xn,yn). W przypadku wielomianowych metod interpolacji może się zdarzyć,
że charakter interpolowanej funkcji uniemożliwia dobre odwzorowanie za pomocą
wielomianu interpolującego. Możemy w takich przypadkach spróbować zastosować liniową
interpolację pomiędzy poszczególnymi węzłami:
sk(x)=yk+dk(x-xk) gdzie 
W ten sposób otrzymamy zestaw funkcji interpolujących przebieg pomiędzy węzłami
dzielącymi przedział interpolacji na podprzedziały. Sklejając te funkcje razem otrzymamy
funkcję interpolującą następującej postaci:
Można zwrócić uwagę na to, że pochodna funkcji s(x) jest nieciągła we wszystkich punktach
xk dla k=1,...,n-1
APROKSYMACJA
Zadaniem aproksymacji jest przybliżenie funkcji F(x) (albo tablicy charakteryzujących funkcję) funkcją f(x) tak aby była ona do niej najbardziej podobna.
F(x) - znana funkcja lub określona tablica
f(x) - funkcja aproksymująca
Przybliżenie obarczone jest błędem aproksymacji.
Aproksymacja liniowa
X - przestrzeń liniowa unormowana (skończenie lub nieskończenie wymiarowa)
F(x) X - funkcja aproksymująca Xn - n wymiarowa podprzestrzeń przestrzeni X
Aproksymacja funkcji F(x) polega na wyznaczeniu takich współczynników a0,a1,...,an funkcji:
f(x)= a0ၪ0(x)+ a1ၪ1(x)+….+ anၪn(x)
gdzie: ၪ0,ၪ1,…,ၪn są funkcjami bazowymi n+1 wymiarowej podprzestrzeni liniowej Xn+1, aby f(x) spełniała pewne warunki np. minimalizowała normę różnicy | f(x) - F(x) |
Aproksymacja wymierna
gdzie ၪi(x), ၹi(x) są elementami tej samej bazy k-wymiarowej podprzestrzeni liniowej k=max(n,m), zaś ai,bi są stałymi współczynnikami, które należy wyznaczyć.
W aproksymacji liniowej należy określić:
- odpowiednią podprzestrzeń liniową Xn i związaną bazę
- odpowiednią miarę.
Wybór podprzestrzeni:
Jeśli funkcja F(x) jest ciągła na przedziale (a,b) (F(x)C(a,b)) to funkcje ၪk(x) będą elementami pewnej n+1 wymiarowej podprzestrzeni C(a,b).
Jeśli F(x) jest okresowa, to przydatna jest podprzestrzeń funkcji trygonometrycznych z bazą:
1, sinx, cosx, sin2x, cos2x, ..., sinkx, coskx
Podprzestrzeń wielomianów - stopnia co najwyżej n z bazą jednomianów :
1, x, x2,..., xn lub bazą wielomianów Czebyszewa T0(x),T1(x), T2(x),..., Tn(x)
- funkcje bazowe mało wrażliwe na błędy
Można też użyć bazy wielomianów Lagrange'a
RÓWNANIA RÓŻNICZKOWE
Równania rzędu pierwszego
Równanie różniczkowe rzędu pierwszego ma postać y'=f(x,y)
Równanie to posiada nieskończenie wiele rozwiązań różniących się stałą.
Rozwiązanie możemy ustalić mając dany warunek początkowy Cauchy'ego.
Metoda uzyskiwania rozwiązanie szczególnego
Dane:
warunek początkowy f0=(x0,y0)
znając funkcję f(x,y) można obliczyć wartość pochodnej w punkcie początkowym
p0=f(x0,y0)თdy/dx - współczynnik kierunkowy w punkcie A0( prosta A0T0).
Przybliżamy na odcinku h krzywą przy pomocy prostej stycznej i wyznaczamy punkt N1 jako przybliżoną wartość y1 (zamiast punktu M1);
y1=y0+၄y ၄y=p0თh=hთf(x0,y0)
Startując z N1 obliczamy następną przybliżoną wartość y2 w punkcie N2.
Stabilizujemy wartości y(x) w punktach x0,x1,...,xn - jest to metoda Eulera - metoda stycznych.
Źródła błędów podczas rozwiązywania - błąd metody i błąd zaokrągleń.
II. Aproksymacja krzywej nie prostą lecz łukiem paraboli.
Wykorzystywane są 2 właściwości (słuszne dla paraboli)
1. Styczna do łuku M0M1 w punkcie p0 odciętej będącej średnią arytmetyczną odciętych punktów M0 i M1 jest równoległa do odcinka M0M1.
Zmodyfikowana metoda Eulera
Gdyby znany był punkt P o odciętej (x0+x1)/2 to wystarczyłoby obliczyć styczną w P i poprowadzić równoległą M0M1 (M1 punkt przecięcia równoległy z prostą x=x0+h.
Punkt P aproksymujemy P` - współczynnik kierunkowy
P`={x`=x0+h/2 y`=y0+h/2∙p0} p0=f`(x0,y0); x`,y` - nowe punkty
tg kąta nachylenia stycznej oraz odcinka M0M1
Współrzędne punktu M1 {x1=x0+h y1=y0+h∙p`}
Formuły te można zapisać:
k1=h∙f(x0,y0) k2=h∙f(x0+h/2,y0+k1/2)
y1=y0+k2, potem wyznacza się współrzędne M2 (x0+2∙h) korzystając z M1 itd.
yi+1=yi+h∙f(xi+1/2∙h,yi+1/2∙h∙f(xi,yi)
Metoda Rungego-Kutty
Szukamy współczynników: a,b,..., ၡ,ß,ၸ,.. oraz liczb R1,R2,.. takich aby wartość y określona przez ciąg równań była możliwie blisko dokładnej wartości
k1=hთf(x0,y0); k2=hთf(x0+aთh,y0+ၡთk1)
k3=hთf(x0 + bთh, y0+ßთk1+ၸთk2) itd.
y1=y0+R1თk1+…+Rnთkn+…
Formuły drugiego rzędu:
k1=hთf(x0,y0) k2=hთf(x0+aთh,y0+ၡთk1)
y1=y0+R1k1+R2k2
To przybliżenie i przybliżenie wzorem Taylora powinno różnić się jak najmniej.
Wyprowadzenie: R1,R2,ၡ,a
y(x) spełnia y`(x)=f(x,y(x)), zróżniczkujmy względem x y``(x)=f`x+y`თf`y
Obszerniejszy material na temat równań różniczkowych mozna znalesc tutaj