1. Zadanie numeryczne, uwarunkowanie zadania numerycznego; wskaźnik uwarunkowania, przykłady:

Zadanie numeryczne: ϕ : D⊂Rⁿ → R^m

d (wektor danych = [d₁…d_n]), ~d(zaburzenie) ∈ D

ω (wektor wyników) ∈ R^m (∈ϕ(d))

Algorytm - A(d) ≠ ϕ(d) (może być zaokrąglenie)

Wskaźnik uwarunkowania: cond(d)<1 dobrze uw.

Dla funkcji :

2. Sposoby reprezentacji liczb w maszynie cyfrowej, arytmetyka zmiennopozycyjna fl, własności ar. fl:

x=s*2^c*m, s∈{±1}, c∈Ζ, m-mantysa m∈[½, 1),

m=Σe_-i2^-i, e_-1=1, e_-1∈{0,1}

m_t=Σe_-t2^-t +e_-(t+1)2^-t - praw. zaokr.

|x-rd(x)|=2^c|m-m_t|≤½2^c-t

rd(x)=x(1+δ), | δ|≤2^-t

fl(a□b)=rd(a□b), fl₂=t:=2l (Algorytm Gilla-Mǖlera: sumow. z uwzględ. popraw.)

3. Algorytm metody numerycznej, numeryczne stabilności algorytmu, błąd algorytm. num. stabilnego, przykłady:

Algorytm jest numerycznie stabilny ⇔ ∃K (niezal. od arytmet. i cond(d)), że ∀d∈D ∃~d ||d-~d|| ≤ k2^-t||d|| oraz fl(A(d)) = ϕ(~d)

Błąd algorytmu: ||fl(A(d))- ϕ(d)|| = ||ϕ(~d)- ϕ(d)|| ≤ cond(d)
||ϕ(d)|| ≤ Kcond(d)2^-t||ϕ(d)||

≤ K cond(d)2^-t

4. Normy wektorów i macierzy oraz ich własności:

Wektorów: Normy Höldera: ||x||_p=lim_p∞||x||_p=
p ≥1; euklidesowa: pε{1;2}; ||x||₂=
||x||_∞=max_i|x_i|

||x||_∞ ≤ ||x||₂ ≤ ||x||₁ ≤ √(n)||x||₂; ||x||₁ ≤ n||x||_∞; ||x||₂ ≤ √(n)||x||_∞

Macierzy: Euklidesowa (Shuma): ||A||_E=
; Indukowana: ||A||_p=

||A||₁=max_j ∑_i|a_ij| kolumnowa; ||A||₂=max_λεSp√λ spektralna; ||A||_∞max_i ∑_j|a_ij|; ||Ax||_*≤||A||_^ ||x||_* zg.z norm.w.

Własności: ||A^H||₂=||A||₂; ||A^HA||₂=||A||₂²; ||A||₂² ≤ ||A||₁ ||A||_∞; ||AB||_p ≤ ||A||_p ||B||_p

A unitarna: ||A||₂=1; ||AB||_E = ||B||_E;

||BA||_E = ||B||_E; W hermit: ||A||₂ = max_λ|λ|

5. Macierze L^(k) i macierze permutacji, ich własności i zastosowanie:

Macierz PεR^nxm nazywamy macierzą permutacji, jeżeli ∀_i ∑_j p_ij=1 oraz ∀_j ∑_i p_ij=1; p_ijε{0,1}

Własności: P^T=P^-1 (ortogon); det(P)=sgnσ; P^TA -przest. wierszy; AP -przest. kol.; P_kl= P_kl^T= P_kl^-1

Własności L^(k): det L^(k)=1; (L^(k))^-1-bez minusów; L⁽¹⁾ L⁽²⁾… L^(k)-trójkątna diag(A)=1, -l_ij; Niech a=[a₁…a_n]^T l_ik=a_i/a_k;

6. Zadanie rozwiązywania układów równań liniowych, wskaźnik uwarunkowania, rozwiązywanie układów z macierzami trójkątnymi:

~A=A+δA (macierz zaburzeń) ~b=b+δb (wekt. zab)

~x=x+δx - zaburzenie wyniku; cond(A) wskaź. uw.

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

Twierdzenia:

||A^-1 δA||<1 => det(~A)≠0

||A^-1 δA||≤ε<1 =>

||I||=||AA^-1||≤||A|| ||A^-1||=cond(A) => cond_p(A) ≥ 1 A^T=A^-1 (ortogon.) => ||A||₂=1 i ||A^-1||=1 - zad. dobrze uw.; A=A^T => ||A||₂=max_λ|λ| i ||A^-1||=1/min_λ|λ| => cond₂(A)=||A||₂ / ||A^-1||

Macierz Hilberta:
-źle uwarunkowana

Mać. trójkątne:

diag(A)≠0

num.stab<=> K≈n

1. górna

2. dolna

koszt:

(*) 0+1+…+(n-1); (+) 0+1+…+(n-1); =½ n(n-1)

7. Metoda el. Gaussa rozw. układów równań liniowych, rozkład LU, częściowy i pełny wybór elem. głównego

Gauss: l_i1=a_i1 / a₁₁ Koszt: (*) n³/3; (+) n³/3

Rozkład LU . 2 układy z mać trójkątną, koszt (2 ½ n²)

Doolittle'a −

Crouta −
Cholesky'ego −

U=A⁽ⁿ⁾=L^(n-1)A^(n-1)L^(n-1)…L⁽¹⁾

Wybór elementu głównego (częściowy)
Zamieniamy także kol. mać. b

Wybór elementu głównego (pełny)

Rozkład trójkątny z wyb. część. A=P_1,p1(L⁽¹⁾)^-1 P_2,p2(L⁽²⁾)^-1 … P_(n-1),p(n-1) (L^(n-1))^-1 U

Rozkład trójkątny z wyb. pełnym A^(k+1)=L^(k)P_k,pk A^(k) P_k,qk (zamiana i kolumn i wierszy)

Macierz diagonalnie silnie dominująca:

8. Metoda eliminacji Gaussa rozwiązywania ukł. równ. dla mać. 3diag i pasmowych

A=LU, gdzie L: diag(L)=1 i w dół β₂… oraz U: diag(U)=α₁ i w bok c₁… α₁=1; β_i=b_i / α_1-i; α_i=a_i - β_ic_i-1

(a₁ a_n b_i c_i) ≠ 0 oraz |a_i|≥|b_i|+|c_i| przy czym przynajmniej 1 z tych nierówności jest ostra to układ Ax=f ma jednoznaczne rozw. i jest numerycznie stabilny.

k:=1…n-1 //szerokość w=p+q+1

p₁=min(p+q,n-k); q₁=min(q,n-k); //wybór el. głównego i zam wierszy

r: max =|a_ik^(k)|=max_k<i<k+q1|a_ik^(k)|

max=0 => STOP

zamień a_rj^(k) ⇔ a_kj^(k) j=k…k+p1 b_r^(k) ⇔ b_k^(k)

for i=k+1…k+q₁ //eliminacja

l=a_ik^(k) / a_kk^(k)

a_ij^(k+1)=a_ij^(k) - la_kj^(k) j=k+1…k+p₁

b_i^(k+1)=b_i^(k) - lb_k^(k)

k=n…1

p₁=min(p+q,n-k) x_k = (b_k^(k)-∑_j=k+1…k+p1a_kj^(k)x_j) / a_kk^(k)

Koszt nqw [(*)(+)]

9. 
   Metoda Banachiewicza (dla macierzy rzecz. i symetrycznych i dodatnio określonych) rozwiązywania układów równań liniowych, rozkład A=LL^T

Własności: A=A^T>0 =>: ∃α>0 (a_xx) ≥α||x||₂²; det(a)>0; Sp(A)⊂R₊

Tw.

Tw. Sylwestra A=A^T => A>0 wszystkie minory główne są dodatnie

dla j=1…n:
koszt n³/6

10. Odwracanie macierzy i obliczanie wyznaczników

A=LU lub A=LL^T lub A=QR to A^-1 = U^-1L^-1 = L^-1TL^-1 = R^-1Q^-1 = R^-1D^-1Q^T

u_ii≠0≠l_ii, W=U^-1, S=L^-1

i:=1…n

w_ii=1/u_ii s_ii=1/l_ii

w_ij= (∑_k=i…j-1w_iku_ik)/u_jj j:=i+1…n

s_ij=-(∑_k=j…i-1l_iks_kj)/l_ii j=1…i-1

detA = detLdetU = ∏l_iiu_ii = ∏l_ii² = detQdetR = ±∏√(|d_i|) r_ii

11. Metoda iteracji prostej rzwiązywania układów równań liniowych, ogólny warunek zbieżności, sposoby przejścia z układu Ax=b do x=Bx+c

ρ(B)=max_λ|λ| =(dla dow mać.) lim_k^k√||B^k||₂ - promień spektralny macierzy B

x^(k+1)=Bx^(k)+c; x^(k)x*; ciąg x^(k)jest zbieżny przy dowolnym x⁽⁰⁾ jeżeli ρ(B) <1 (im mniej tym szybciej)

x^(k+1)- x* = B(x^(k)-x*) =…= B^k+1(x⁽⁰⁾-x*) => x^(k)-x* = B^k(x⁽⁰⁾-x*) => ||x^(k)-x*||₂ ≤ ||B^k||₂ ||x⁽⁰⁾-x*||₂ ||B^k||₂≈[ρ(B)]^k

Metoda Richardsona:

Ax=B pAx=pB (p≠0) x=x-pAx+pb x=(I-pA)x + pb = B_R + C_R

A=A^T>0 to ρ(B_R) = max_Sp(BR)|μ| = max_Sp(A)|1-pλ| = max((|1-pλ_min|, |1-pλ_max|) => pε(0, 2/λ_max); p_opt=2/(λ_min+λ_max)

i dla dużych cond(A) wolna zbieżność

x_i^(k+1) = x_i^(k) + p(b_i-∑_ja_ijx_j^(k)), k=0…n

redukowalna: ∃P: P^TAP=
silnie/słabo dominująca: |a_ii|≥∑_i≠j|a_ij|; sil.: wszystkie >, sł.: przyn. 1;

12. Metody Jakobiego i Seidla j/w

Jakobi:

A=L+D+U =

▲+ \ +▼,

A_ii≠0; …

Dx = -(L+u)x + b x= -D^-1(L+U)x+ D^-1b = B_Jx + C_J

x_i^(k+1) = (b_i - ∑_j≠ia_ijx_j^(k))/a_ii i=1…n; k=0…;

zbieżna: A silnie dom., A słabo dom. i niereduk.

Gauss - Seidl:

x = -(L+D)^-1Ux + (L+D)^-1b = B_GSx + C_GS

x_i^(k+1) = x_i^(k) +

+ (b_i - ∑_j<i-1a_ijx_j^(k+1) - ∑_i-1<j<n+1a_ijx_j^(k))/a_ii

zbieżna: słabo dom. i niereduk., A=A^T>0

13. Metoda SOR j/w

w=1GS

B_w = (d+wL)^-1((1-w)D-wU); C_w = w(D+wL)^-1b

x_i^(k+1) = x_i^(k) + w(b_i - ∑_j<i-1a_ijx_j^(k+1) - ∑_i-1<j<n+1a_ijx_j^(k))/a_ii

zbieżna: A=A^T>0 to ∀wε(0,2) ρ(B_w)≥|w-1|

14. Porównanie metod iteracji prostej dla układów równań liniowych z macierzą symetryczną i dodatnio określoną oraz posiadającą własność A

A ma własność A jeżeli istnieje P: P^TAP=
, gdzie D1, D2 macierze diagonalne

Tw. Jeżeli A=L+I+U A=A^T>0 i nie ma własności A to

1. ρ(B_J)=ρ(B_R)|_{p opt}
   

2. ρ(B_GS)=ρ²(B_J)

3. 
   

w_b jest optymalne

Więc λ_max≠λ_min => 0 < ρ(B_{w opt}) < ρ(B_GS) < ρ(B_R)|_{p opt} <1

ρ(B_R)|_{p opt} = ρ(B_J) =

ρ(B_{w opt}) = w_opt-1 =

Tw. Gerszgorina; Sp(A) ⊂ ∪K_i(a_ii, r_ii) = ∑_j≠i|a_ij|

15. Zadanie interpolacji wielomianowej funkcji jednej zmiennej, błąd interpolacji, wielomian interpolacyjny Lagrange'a:

Zadanie: Danych jest n+1 węzów
i klasa funkcji G, szukamy takiego
aby

Jednoznaczność:
posiada conajw. n+1 pierw

Błąd: |Π(x)| = |(x-x₀)… (x-x_n)| ≤ ¼n!hⁿ⁺¹; h=max_i(x_i-x_i-1);

Tw. f∈Cⁿ⁺¹[a,b] => ∀x∈[a,b] ∃ξ∈[a,b] że R(x) = f(x) - w(x) =
R(x) = |f(x) - w(x)| ≤ …

Lagrange:

16. Zadanie interpolacji wielomianowej funkcji jednej zmiennej, błąd interpolacji, wielomian interpolacyjny Newtona:

f_i=f(x_i); f_ij=(f_i-f_j)/(x_i-x_j);

f_i…i+k = (f_i…i+k-1 - f_i+1…i+k) / (x_i - x_i+k)

węzły równoodległe: x_i=a+ih; h=|a-b|/n

17. Zadanie interpolacji wielomianowej funkcji jednej zmiennej, optymalny wybór węzłów - węzły Czybyszewa

Chcemy aby zminimalizować max_x|Π(x)|

x= ½[(b-a)t+(a+b)], t∈[-1;1];

wzór rekur.

Wtedy |R(x)|≤
Jak interpolujemy |x| albo 1/(1+25x²) to efekt Rungego

18. Zadanie interpolacji wielomianowej funkcji jednej zmiennej, klasyczna interpolacja Hermita:

∑_im_i:=n+1, m=max(m_i) (wyrównujemy również pochodną) w^j(x_i)=f^(j)(x_i), j=0…m_i-1; Dla m=2 klasyczna, m=1 Lagrange

Błąd klasycznej: R(x) = Π(x) (f⁽²ⁿ⁺²⁾(ξ)) / (2n+2)!; Π(x)=(x-x₀)^m0…(x-x_n)^mk=(x-x₀)²…(x-x_n)²

Klasyczna: 0…n węzłów, W_2n+1;

ϕ_i:=[1-2(x-x_i)l`<sub>i</sub>(x<sub>i</sub>)]l<sup>2</sup><sub>i(x)</sub> ϕ<sub>i</sub>(x<sub>k</sub>) = ψ`_i(x_k)=δik

ψ_i:=(x-x_i)l²_i(x) ϕ`_i(x_k) = ψ_i(x_k)=0

W(x)=∑f(x_i)ϕ(x) + ∑f`(x_i)ψ(x)

19. Sposoby numerycznego różniczkowania

f^(j)(x) ≈ w^(j)(x); Tw: f∈Cⁿ⁺¹[a,b] to max|f^(j)(x) - w^(j)(x)|≤

1. f^'(x)≈(f(x+h)-f(x))/h

2. f^'(x)≈(f(x)-f(x-h))/h r(x)=f`(x)-[f'(x)h + ½ f''(ζ)h²]/h = ½hf''(ζ)

3. f^'(x)≈(f(x+h)-f(x-h)) / 2h

4. f^'(x)≈(f(x+h)-2f(x)+f(x-h)) / h²

20. Całkowanie funkcji jednej zmiennej - formuły proste Newtona - Cotesa (prostokątów, trapezów, Simpsona)

S(f) = ∑A_if(x_i) A_i-współcz. form.; r(f)=I(f)-S(f)

NC: x_i=a+ih; h=(b-a)/n; S(f) = ∫_a^bw(x)dx

n		nazwa	wzór
	reszta kwadratury	kwadratury
0	Dla n≥1	prostokątów	(b-a)f(x0) = hf(x0)
1	(12)	trapezów	(b-a)[f(a)+f(b)]/2
2	(2880)	Simpsona	(b-a)… [f(a)+4f(x1)+f(b)]/6
3	(6480)	3/8	(b-a)… …[f(a)+3f(x1)+3f(x2)+f(b)]/8

21. Całkowanie funkcji jednej zmiennej - formuły złożone Newtona - Cotesa (prostokątów, trapezów, Simpsona)

I(f) = ∫_a^bf(x)dx = ∑∫_xi-1^xif(x)dx ≈ ∑S_i(f) = S(f)

r(f) = ∑r_i(f)

Prostokąt: S(f) = h∑f(x_i⁽⁰⁾)

x_i⁽⁰⁾=(x_i-1+x_i)/2 - p.środk. |r(f)|=∑(f⁽²⁾(ξ_i) h³) / 24

mm₂ ≤ ∑f⁽²⁾(ξ_i) ≤ M₂m => min_x(f²(x)) ≤ (∑f⁽²⁾(ξ_i)) / m ≤ max_x(f²(x)) => r(f) = (f⁽²⁾(ξ) h²)(b-a) / 24

|r(f)| ≤ M₂h²(b-a) / 24

Trapez : S(f) = ½h[f(a) + f(b) + 2∑f(a+ih)]

Simpson: S(f) = h[f(a) + f(b) + 2∑f(a+ih) + 4∑f(a+ih-h/2)]/6

22. Rozwiązywanie równań nieliniowych, wykładnik zbieżności, sposoby lokalizacji pierwiastków:

f[a,b]R, szukamy f(x*)=0

- tablicowanie (wykres) - f(a)f(b)<0 => ∃x* oraz f'(x) ma stały znak to ∃! - graficznie f(x)=f₁(x) - f₂(x)

Met. int. jest rzędu p (p≥1) jeżeli istnieje A>0, że ciąg x^(k) określony tą metodą spełnia nierówność: |x^(k+1)-x*| ≤ A|x^(k)-x*|^p {dobre: A małe, p duże}

p=1 zbieżność liniowa |x^(k+1)-x*| ≤ A|x^(k)-x*| ≤ |x^(k+1)-x*| ≤ A²|x^(k-1)-x*| ≤…≤ A^k+1|x⁽⁰⁾-x*|; A<1 - war. zbież.

p>1 zbieżność ponadliń. |x^(k+1)-x*| ≤ (A^1/(p-1)|x⁽⁰⁾-x*|)^pk-1|x⁽⁰⁾-x*|; A^1/(p-1)|x⁽⁰⁾-x*|<1 - war. zbież.

23. Metody rozwiązywania skalarnych równań nieliniowych, ich własności i porównanie:

Nazwa	p/A	założenia	zbieżność	wzór
bisekcja	1 A=½	ciągła [a,b]	bezwrunk.	x^1= ½(a+b); f(x^i)f(a)<0 to [a,x^i] k-ty: (b-a) /2^k<ε
styczne	2 A=M2/2m1	kl.C^2[a,b]	warunk.	x^(k+1) = x^(k) - f(x^k)/f^1(x^k)
sieczne	½(1+√5)≈1,6 A=(M2/2m1)^p	kl.C^2[a,b]	warunk.	x^(k+1) = x^(k)- [f(x^k) / (f(x^k) - f(x^k-1)] (x^k-x^k-1)
regulafalsi	1	kl. C[a,b]		miejsce przecięcia odcinka ab, itd.
Steffensena	2			x^k+1 = x^k - f^2(x^k) / [f(x^k+f(x^k)) - f(x^k)]
Halleya	3			x^k+1 = x^k - [f(x^k) f^1(x^k)] / [f^1(x^k)- ½f(x^k) f^2(x^k)]
it. prostej	1		M1<1	x^k+1 = g(x^k)

24. Metoda stycznych poszukiwania pierwiastków równania skalarnego, wykładnik zbieżności i warunki zbieżności metody:

x⁰∈[a,b] =



f¹(x₀) = tgα = f(x⁰)/(x⁰-x¹)

Zbieżność globalna dla dowolnego
- jeżeli

• 
  ;
  ;

• 
  .

• 
  

Kryteria STOPU:
|x* - x^k|<|f(x^k)|/m₁

25. Metoda iteracji prostej rozwiązywania układu równań nieliniowych, wykładnik zbieżności i warunki zbieżności:

x⁰-przyliżenie początkowe; x^k+1 = g(x^k)

Tw1: D - zbiór domknięty => warunek Lipschitza, ponadto x*∈D to: ∃!x*; ||x^k-x*||0; ||x^k+1-x*||≤L||x^k-x*||; ||x^k-x*|| ≤ (L^k/(1-L))||x¹-x⁰||

!!!D-zb. wypukły g(x')-g(x'')=g'(ξ)(x'-x''); g'(x) - mać. Jakobiego {δg_i/δx_j}_i,j=1ⁿ; ||g(x')-g(x'')||=||g'(ξ)|| ||(x'-x'')|| (n.mać. zg. z n.w) wystarczy żeby L=sup_x||g'(x)||<1

Tw2: D-domk. i L, ∃x*, x⁰∈S={x: ||x-x*|| ≤ r} to x^kεS i spełniona teza Tw1

26. Metoda Newtona rozwiązywania układu równań nieliniowych, wykładnik zbieżności i warunki zbieżności:

x^k+1=x^k - [f¹(x^k)]^-1f(x^k);

Niech D-wypukły i f-różniczkowalne, oraz ∃x*, det(f¹(x*))≠0, L, x⁰∈S to: Met. poprawnie określona; ||x^k+1-x*|| ≤ q||x^k-x*||; ||x^k+1-x*||0; ||x^k+1-x*|| ≤ (q/r)||x^k-x*||²

Warunki STOPU: podobne jak it. pr. oraz ||x^k+1-x*|| ≤ q||x^k-x*|| ≤… ≤q^k+1r ≤ε

27. Metody rozwiązywania równań skalarnych posiadających zera wielokrotne:

f(x)=(x-x*)^mg(x)≠0; f^m(x*)=0; => p=1!!!

Alg1: F(x)=f(x)/f¹(x) {x* - zero 1-krotne F};


styczne:
p=2 (m zgadujemy )

28. Metody poszukiwania zer wielomianów:

1 zero: Newton/styczne (w pewnym otoczeniu zbieżna, p=2), sieczne, Laguerre: x^k+1=
znak, żeby |x^k+1-x^k| było mniejsze, H(x)=[(n-1)(f¹(x))]² - nf(x)f²(x), jak zbieżne to p=3; Jak n rzeczywisty z n zer to zawsze zbiega do najbliższego zera.

Schemat Hornera dla f, f', f''

a_n= b_n= c_n= d_n; b/c/d_i = b/c/d_i+1x + a/b/c, i=n-1…0/1/2

f(x)=b₀ f'(x)=c₁ f''(x)=2d₂, koszt 3n[(*)(+)]

Wyznaczanie kilku zer: deflacja czynnikiem liniowym: x*, f(x)=(x-x*)Q(x), Q(x)=∑q_j+1x^j

Alg1: q_n+1=0; q_j=a_j+q_j+1x*; j=n…1

Alg2: q₀=0; q_j+1=(q_j-a_j)/x*; j=0…n-1, chyba że x*=0

Maehly: f(x)=(x-x₁)…(x-x_n), a_n=1; x₁ z Newtona; f₁(x)= (x-x₂)…(x-x_n), x₂ z Newtona dla f₁… ; f¹₁(x)/f₁(x) = (f¹(x)/f(x))(x^k+1/x-x₁); Trzeba uważać, żeby x_i⁽⁰⁾≠x_j

Bairstow: a_n=1, a_jεR, f(x)=Π^n/2(x²-p_jx-r_j)(x-a); m(x,p,r)=x²-px-r; f(x)=m(x,p,r)Q(x,p,r)+q₁(p,r)x+q₀(p,r).

q_i obliczamy dzieląc f przez m


to samo dla r


Podstawić i


29. Interpolacja trygonometryczna:

[0,2π] x_k=2kπ/(n+1)

t_n(x)= ½a₀ + ∑[a_j cos(jx) + kj sin(jx)] + v ½a_m+1 cos[(m+1)x], gdzie dla n -parz m=n/2, v=0; dla n-niep m=(n-1)/2, v=1

Tw. dla funkcji określonej na [0,2π] ∃!x* Ponadto a_j=2/(n+1) ∑f(x_k)cos(jx_k); b_j=2/(n+1) ∑f(x_k)sin(jx_k)

dla dowolnego [a,b] => v=b-a (okres)

























---