1.1 Wyjaśnić pojęcia związane z błędem:

• liczba przybliżona a jest to liczba różniąca się nieznacznie od dokładnej liczby A i zastępująca ja w obliczeniach

• błąd bezwzględny Da liczby przybliżonej a nazywamy wartość bezwzględną różnicy między wartością dokładną A a wartością przybliżoną a Da= | A-a |

• błąd względny da liczby przybliżonej a nazywamy stosunek błędu bezwzględnego do modułu liczby A. da=Da/|a|

l .2 Wyprowadzić wzory na błąd bezwzględny i błąd względny wartości funkcji jednej i wielu zmiennych.

"Niech oszacowanie Dx będzie małe i niech i |e| <=Dx. Dla funkcji f określonej na przedziale [x-Dx,x+Dx] o wartościach rzeczywistych, klasy C^¥ mamy:

Ponieważ w porównaniu do pierwszego, pozostałe składniki powyższego rozwinięcia są małe, więc

Tak więc dla dostatecznie małego Dx, dobrymi przybliżeniami dla oszacowań błędu bezwzględnego i błędu względnego wartości funkcji są odpowiednio wielkości

Przeprowadzając analogiczne rozumowanie błąd bezwzględny i względny dla funkcji wielu zmiennych definiujemy w następujący sposób

1.6 Co to jest: wskaźnik uwarunkowania zadania numerycznego -jest mnożnikiem, zależnym zwykle od danych zadania, określającym zmianę zaburzeń względnych danych (w sensie wartości bezwzględnych Iub norm tych zaburzeń). Oznaczany jest przez cond lub cond(x)

Podać ten wskaźnik dla zadania obliczania wartości funkcji jedej zmiennej y=f(x)

2. Rozwiązywanie układów równań liniowych.

2.1 Co to jest: wskaźnik uwarunkowania zadania numerycznego - jest mnożnikiem, zależnym zwykle od danych zadania, określającym zmianę zaburzeń względnych danych (w sensie wartości bezwzględnych lub norm tych zaburzeń). Oznaczany jest przez cond lub cond(x) Podać ten wskaźnik dla zadania rozwiązywania układów równań liniowych.

cond(A)=||A|| ||A^-1||

3. Rozwiązywanie równań nieliniowych i ich układów.

3.1 Na czym polegają metody iteracyjne rozwiązywania rozważanego obecnie zadania numerycznego (dla przypadku skalarnego). Zdefiniować wykładnik zbieżności takich metod. Podać ten wykładnik dla metody: siecznych, stycznych, bisekcji.

Metody iteracyjne polegają na tworzeniu ciągu kolejnych przybliżeń x_k, który zbiega do rozwiązania a.

Wykładnik zbieżności metod-jest to największa liczba p (p³1), że | e_k+1 | £ C*( | e_k | )^p, gdzie e_k=a-x_k, zaś C jest stałą nieujemną zależną zazwyczaj od funkcji f (lub jej pochodnych). Wykładnik zbieżności dla metody:

• Siecznych: p=(l+Ö5 )/2 (p»1.62) - zbieżność ponadliniowa

• Stycznych: p=2 - zbieżność ponadliniowa

• Bisekcii: p=l - metoda jest wtedy zbieżna liniowo

3.2 Dla równania skalarnego, omówić metodę

• siecznych - opis metody:

a)wybieramy dwa punkty startowe x₀ i x₁ z przedziału, w którym poszukujemy pierwiastka,

b)kolejne przybliżenia x_k+1, k=0,1,2,.. obliczamy ze wzoru: x_k+1=x_k-f(x_k)×{[(x_k-x_k-1)]/[f(x_k)-f(x_k-1)]}.

Warunki kończenia iteracji: l) ½ x_k+1-x_k½£e, 2) ½ x_k+1-x_k½£e×½x_k+1½, 3) ½f(x_k+1)½£e.

Zapewniamy zbieżność metody gdy:

1) f jest funkcją klasy C² ([a,b])

2) f(a)*f(b)<0,

3) f'i f" nie zmieniają znaku w [a,b], wówczas zbieżność jest z wykładnikiem p= (1+Ö5)/2

• stycznych - opis metody:

a)wybieramy punkt startowy x_o z przedziału, w którym poszukujemy pierwiastka,

b)kolejne przybliżenia x_k+i, k=0,l,2,„ obliczamy ze wzoru: x_k+1=x_k-[f(x_k)/f1(_­x_k)]

f(x)=d/dxf(x)

Warunki kończenia iteracji są takie same jak w metodzie siecznych.

Zapewniamy zbieżność metody gdy:

l ) f jest funkcją klasy C

2) f(a)*f(b)<0,

3) f'i f" nie zmieniają znaku w [a,b], to przyjmując x_o takie, że f(x_o)f"(x_o)>0; zbieżność jest z wykładnikiem p=2

• bisekcji - opis metody:

a)dzielimy przedział [a,b] na połowę punktem x₁==(a+b)/2,

b)jeżeli f(x₁)=0, to x₁ jest pierwiastkiem i metodę kończymy,

c)jeżeli f(x₁)¹0 to wybieramy ten z podprzedziałów [a,x₁] lub [x₁,b], w którym funkcja zmienia znak.

W tej metodzie z góry można określić liczbę iteracji potrzebną do uzyskania dokładności e

Metoda ta jest liniowo zbieżna gdy wykładnik p=l i stała C=0,5.

3.3 Podać założenia dotyczące funkcji f, przedziału [a,b], punktów (punktu) startowych, zapewniające zbieżność do pierwiastka ciągu generowanego przez metodę:

• siecznych - f jest funkcją klasy C²[a,b]), f(a)*f(b)<0, na przedziale [a,b] f' i f "nie zmieniają znaku, punkty startowe x_o i x₁ wybieramy z przedziału w którym poszukujemy pierwiastka, przyjmując je tak by f(x_o)-f "(x_o)>0 i f(x₁)'-f"(x₁)>0

• stycznych - f jest funkcją klasy C²[a,b]), f(a)*f(b)<0, na przedziale [a,b] f' i f "nie zmieniają znaku, punkt startowy x_o wybieramy z przedziału w którym poszukujemy pierwiastka, przyjmujemy je takie by f(x_o)*f "( x_o)>0

• bisekcji - f jest funkcją ciągłą na przedziale [a,b], oraz f(a)*f(b)<0 (f zmienia znak w [a,b]), przedział [a,b] dzielimy na połowę punktem x₁=(a+b)/2, jeżeli f(x₁)=0 to x₁ jest szukanym pierwiastkiem, jeżeli f(x₁)=/0 wybieramy ten z podprzedziałów [a,x₁] lub [x₁,b] gdzie funkcja zmienia znak

4 Interpolacja,

4.1 Sformułować zadanie interpolacyjne Lagrange’a.

Zadanie interpolacyjne Lagrange'a polega na znalezieniu wielomianu L_n, stopnia nie wyższego niż n spełniającego warunki interpolacji L_n(x_i)=f(x_i) dla i=0,l,..,n. Wielomian L_n nazywamy wielomianem interpolacyjnym Lagrange’a funkcji f opartym na węzłach x₀,x₁,...,x_n.

4.2 Sformułować i udowodnić twierdzenie o jednoznaczności rozwiązania zadania interpolacyjnego Lagrange'a.

Zadanie interpolacyjne Lagrange'a polega na znalezieniu wielomianu L_n, stopnia nie wyższego niż n spełniającego warunki interpolacji L_n(x_i)=f(x_i) dla i=0,l,..,n.

Zadanie interpolacyjne Lagrange' a ma jednoznaczne rozwiązanie.

Dowód: Szukany wielomian zapiszemy w postaci:

** Zadanie interpolacji L_n(x_j)=y_i dla i=0,l,..,n prowadzi do układu n+1 równań liniowych Va=y z

Macierz Vandermonde'ajest macierzą nieosobliwą dla układu różnych węzłów. Zatem układ Va=y ma dokładnie jedno rozwiązanie. Istnieje wielomian postaci ** i jest on wyznaczony jednoznacznie.

4.4 Zdefiniować iloraz różnicowy 1-go rzędu, 2-go rzędu i ogólnie k-go rzędu.

Wyznaczyć tablicę ilorazów różnicowych dla funkcji f określonej następująco: np. f(0)=1, f(1)=3, f(3)=2.

Ilorazami różnicowymi I rzędu nazywamy wyrażenia.

f_0,1=(y₁-y_o)/x₁-x_o,.. .f_n-l,n=(y_n-y_n-l)/x_n-x_n-l

Ilorazami różnicowymi II rzędu nazywamy wyrażenia.

f_0,1,2=(f_l,2-f_0,l)/x₂-x₀,...f_n-2,n-l,n=(f_n-l,n-f_n-2,n-l)/x_n-x_n-2

Ilorazami różnicowymi k-tego rzędu nazywamy wyrażenia

f_i,j+1,..,i+k=(f_i+1,..,i+k-f_i,..,i+k-1)/x_i+k-x_i

4.6 Podać definicję funkcji sklejanej stopnia trzeciego.

Funkcją sklejaną stopnia 3 na przedziale <a,b> nazywamy funkcję, która:

a)jest wielomianem stopnia 3 na każdym przedziale <x_i,x_i+1>,

b)jest klasy C² na <a,b>

4.7 Sformułować zadanie interpolacji przy pomocy funkcji sklejanych stopnia trzeciego. Czym są dodatkowe warunki ?

Funkcję f(x) określoną na przedziale [a,b] nazywamy funkcją sklejaną stopnia trzeciego, jeżeli

• f(x) jest wielomianem stopnia co najwyżej trzeciego na każdym podprzedziale (x_i,x_i+1),i=0,l,..n-l

• f(x) jest funkcją klasy C²[a,b].

Punkty x_i są węzłami funkcji sklejanej.

Interpolacyjna funkcja sklejana stopnia trzeciego zależy od dwóch parametrów, wobec czego nakładane są najczęściej na węzłach krańcowych a i b dwa dodatkowe warunki. Mogą mieć one postać: f’(a+0)=a i f’(b-0)=b , a,b-ustalone liczby rzeczywiste. Jeżeli funkcja f ma pochodne w punktach a i b oraz znane są ich wartości, to można je przyjąć jako liczby występujących po prawych stronach powyższych warunków. Jeżeli zaś znane są tylko wartości funkcji f w węzłach to mogą to być przybliżenia pochodnych.

5. Aproksymacja średmokwadratowa dyskretna.

5.1 Sformułować zadanie aproksymacji średniokwadratowej dyskretnej.

Rozważyć przypadki aproksymacji typu wielomianowego i trygonometrycznego.

• Aproksymacja średniookwadratowa dyskretna: j = (j _o,j _i,..,j _m)®układ m+l funkcji

określonych na (a,b)

funkcja przybliżająca F_m(x)=S^m_j=0a_j-j_j(x); współczynnik a_j dobieramy tak by wyrazenie: H(a_o,a₁,..,a_m)=Sⁿ_i=0(y_iF_m(x_i)² miało najmniejszą wartość. Wartości współczynników wyznaczamy z warunków zerowania się pochodnych (d/da_k)H=-2Sⁿ_i=0(y_i-F­_m(x_i))j_k(x_i)=0 k=0,1,...,m otrzymujemy m+1 równań liniowych z niewiadomymi a_o,a₁,..,a_m

• Aproksymacja wielomianowa - Funkcje j_j są wielomianami stopnia (j=0,l ,2,..m) kiedy F_m jest wielomianem stopnia co najwyżej m, wtedy funkcję optymalną F_m nazywamy m-tym wielomianem optymalnym.

• Aproksymacja trygonometryczna - Do aproksymacji stosujemy wielomiany trygonometryczne (j =(1, sin(x), cos(x), sin(2x),...,sin(kx), cos(kx)) 2k<=n wtedy:

F_2k+1(x)=a₀+S^k_j=1(a_jcos(j×k)+b_jsin(j×x))

rozważamy odcinek (0,2P) na zbiorze równoodległych punktów: x_i=(2P*i)/(n+1) i=0,l,..,n macierz Gramma jest diagonalna a_o=l /(n+1)Sⁿ_i=0y_i a_j=2/(n+1)Sⁿ_i=0y_icos(jx_i) bj=2/(n+1)Sⁿ_i=0y_isin(jx_i) j=1,..,k

5.4 Omówić problem uwarunkowania zadania rozwiązywania układu równań normalnych.

H(a_o,a₁,..,a_m)-odchylenie średniokwadratowe, należy tak dobrać współczynniki "a_j" by odchylenie średniokwadratowe było jak najmniejsze.

Błąd średniokwadratowy: d=Ö[1/(n+1)Sⁿ_i=0(y_i-F(x_i))²].

Gdy m=n rząd macierzy M jest równy n+1 to n-ta funkcja optymalna jest funkcją interpolującą funkcji f opartą na węzłach x, wtedy H=0 d=0.

W przypadku (j_j=x^j już dla niedużych m (m>5) układ jest równań normalnych, jest źle lub bardzo źle uwarunkowany (jednomiany); liczbę funkcji przybliżających=(m+l) ustalamy wyznaczając kolejne funkcje optymalne i kwadrat średniego błędu: (dm)²=Hm/n-m

Hm-odchylenie średniokwadratowe dla m-tej funkcji optymalnej Fm;

obliczenia prowadzi się aż (dm)² maleje w sposób istotny, wartość po której (dm)² już znacznie nie maleje wyznaczają układ funkcji przybliżających j_o, j₁,.., j_m

6. Całkowanie numeryczne.

6.1 Co to jest kwadratura ? Omówić rolę funkcji wagowej p.

Do przybliżonego obliczenia całki I(f) stosujemy wzory, zwane kwadraturami, w postaci:

przy czym współczynniki A_k nie zależą od funkcji f. Oczywiście x_i¹x_j dla i¹j. Współczynniki A_k i punkty x_k nazywamy odpowiednio współczynnikami i węzłami kwadratury S. Jeżeli funkcja f ma osobliwości utrudniające dobre przybliżenie to f(x)=F(x)*p(x) gdzie F(x) jest funkcją która może dobrze przybliżyć a p(x) ma wszelkie osobliwości funkcji podcałkowej utrudniające przybliżenie

6.2 Podać definicję rzędu kwadratury.

Mówimy, że kwadratura S jest rzędu r(r³ l), jeżeli: I(W)=S(W) dla wszystkich wielomianów

W stopnia mniejszego niż r, istnieje wielomian W stopnia r taki, że I(W)¹S(W). Jedynym ze sposobów otrzymywania kwadratur S jest zastąpienie w całce I funkcji f funkcją interpolującą F. Wtedy:

gdzie funkcja interpolująca F jest np. interpolacyjnym wielomianem czy interpolacyjną funkcją sklejaną dla funkcji f. Jeżeli F jest wielomianem interpolacyjnym, to S nazywamy kwadraturą interpolacyjną.

6.3 Omówić prosty i złożony wzór trapezów.

Niech F=L_n będzie wielomianem interpolacyjnym Lagrange'a

Wtedy

Jeżeli funkcję f zastąpimy wielomianem interpolacyjnym L opartym na węzłach a i b, to otrzymamy kwadraturę trapezów

Geometrycznie dla f³0, przybliżamy pole między wykresem f i osią Ox polem trapezu o podstawach f(a) i f(b). Złożony wzór trapezów przy podziale przedziału [a,b] na n podprzedziałów o tej samej długości h=(b-a)/n jest postaci

6.4 Omówić prosty i złożony wzór parabol.

Prosty: S(f)=(b-a)/6*(f(a)+f(b)+4f(a+b)/2)

aby osiągnąć lepszą dokładność można zwiększać liczbę węzłów n lub dzielić przedział na mniejsze części Złożony: dzielimy przedział całkowania <a,b> na m równych części o długości (b-a)/n=h , „n" musi być parzyste S(f)=h/2*[f(a)+f(b)+2S^n-1_i=1f(a+ih)+4S^n-1_i=1f(a+ih+h/2)]

6.5 Omówić błąd złożonego wzoru trapezów i złożonego wzoru parabol.

Błąd trapezów: E(f)=-[(b-a)³/12m²]*f⁽²⁾ (x1) Błąd parabol: E(f)=-[(b-a)⁵/2880m⁴]*f⁽⁴⁾ (x2)

x1,x2 -> pewne punkty z przedziału (a,b); pochodna f⁽²⁾(x) oraz f⁽⁴⁾(x) jest ciągła na <a,b>

6.6 Omówić 2 - punktowa prosta i złożona kwadraturę Gaussa-Legendre’a.

Dla przedziału <-1,1> całkowania: S(f)=f(x_o)+f(x₁) gdzie x0=-1/sqrt(3); x1=1/sqrt(3); dla dowolnego przedziału całkowania <a,b> ® liniowa zmiana zmiennej całkowania

t=[(a+b)/2]+[(b-a)/2]*x prosta ò^b_af(t)=[(b-a)/2]ò¹_-1g(x)dx g(x)=f{[(a+b)/2]+[(b-a)/2]*x} S(f)=(b-a)/2*[f((a+b)/2+(b-a)/2-x_o)+f((a+b)/2+(b-a)/2*x₁)] złożona: dla równomiernego podziału przedziału całkowania na części (m) gdzie h=(b-a)/m S(f)=h/2S^m-l_i=0[f(a+ih+ht_o)+f(a+ih+ht₁] t_o=(1+x_o)/2 t1=(l+x₁)/2

7. Rozwiązywanie zasadnień początkowych dla równań różniczkowych zwyczajnych.

7.1 Omówić jawną metodę Eulera.

Według tej metody y_i+1=y_i+hf(x_i,y_i), i=0,1,2,..,n-1 przy czym y_o=y_a

Metoda ta ma prostą interpretację geometryczną, oznaczamy punkty M_i=M_i(x_i,y_i), odcinek M_iM_i+1 ma w punkcie M_i zgodny z kierunkiem stycznej do rozwiązania, które przechodzi przez ten punkt, wielkość T_i, jest błędem metody który powstał przy przejściu od x_i do x_i+1, e_o=0, e₁=T_o zakłada się również że rozwiązanie dokładne y=y(x) jest klasy C²([a,b]). Rozwiązanie to spełnia równanie y(x_i+l)=y(x_i)+hf(x_i,y(x_i))+(1/2)h²y⁽²⁾ (x_i), x_i<x_i<x_i+1 stąd otrzymujemy: T_i=(1/2)h²y⁽²⁾ (x_i) WYKRES

Metoda niejawna eulera

yi +1 = yi +h f (xi +1 + yi+ 1) i = 0, 1 , 2 , ..... ,

Jeżeli znamy już yi , to i-tą spośród powyższych równości można traktować

jako równanie z niewiadomą yi+1 . Zatem wyznaczenie yi+1 wymaga rozwiązania

równania (na ogół nieliniowego). Zakładamy, że równanie to dla dostatecznie

małych h ma dokładnie jedno rozwiązanie.

Rząd metody

Największą liczbę całkowitą p taką, że dla dostatecznie małych h zachodzi

nierówność

|ei (h)|<=c h^p dla każdego i = 0,1, ... ,n(h) , gdzie c jest stałą niezależną od h, nazywamy

rzędem metody.

Pojęcie zbieżności metody dyskretnej jest podstawowym pojęciem teorii

metod rozwiązywania zagadnień (1).

Niech y = y(x) będzie rozwiązaniem (dokładnym) zagadnienia i niech yi = yi(h)

oznacza przybliżone rozwiązanie tego zagadnienia w punktach

xi = xi(h), i = 1, 2, ... , n = n(h)

otrzymane pewną metodą dyskretną.

Oznaczymy przez

ei = ei(h) = y(xi) - yi(h)

b³ąd przybliSenia odpowiadający punktowi xi.

Idea zbieSności metody dyskretnej jest następująca: im bardziej gęsty jest podzia³

odcinka [x0 , b] węz³ami, tym mniejsze są błędy ei odpowiadające tym punktom.

Powiemy, że metoda jest zbieżna, jeżeli b³ędy te zbiegają do zera, gdy h maleje do zera.

3.5 Czy można stosować metodę np. stycznych, gdy f(x) = e^x – x – 1 i punkt startowy x₀ = 1

5.3 Przyjmując, że G=M^TM jest macierzą Grama, podać postać macierzy M., gdy np. a) 2,x,x²,2^x są funkcjami bazowymi, b) aproksymacji dokonujemy na zbiorze {-1,0,2,3}.

1.2? Podać definicję normy macierzy A i definicję współczynnika uwarunkowania macierzy.

W przestrzeni Rⁿ, której elementami są macierze stosowane są normy:

- n kolumnowa norma pierwsza

maksymalna suma modułów w kolumnie

- n wierszowa, n nieskończona

- n spektralna, norma druga

gdzie r(B)=max{½A½:def(B-A_i)=0} jest promieniem spektralnym macierzy

Wskaźnik uwarunkowania – 1.6

1.4? Sformułować zagadnienie aproksymacji funkcji f(x) (metodą najmniejszych kwadratów)

Niech f=(f₀, f₁,... ,f_n) będzie układem (m+1) f.określonych na przedziale [a,b]. Zakładamy, że rząd macierzy M=m+1

Będziemy rozważać zadanie aproksymacji linowej polegającej na przybliżeniu funkcji f kombinacjami linowymi funkcji f_j­ (j=0,1,..,n) F_n(x)=S^m_j=0a_jf_j(x) a_j dobieramy tak aby wyrażenie H(a₀,a₁,...,a_m) = Sⁿ_i=0(y_i-F(x_i))² było jak najbliżej węzłów tzn min H

Funkcję F_m, dla której H osiąga minimum nazywamy m-tą funkcją optymalną. Liczymy dH/da_k­=0 k=0,1,...,m

F(x) = a₀+a₁x+…+a_mx^m