Metody Numeryczne

Z metod numerycznych (wykład) jest egzamin. Od 4ry w górę zwolnienie.

Literatura:
- ‘Praktyczne metody analicy numerycznej’; Jean Legras
= BEST: ‘Elementy metod numerycznych’; Stanisław Wojciech; Politechnika Łódzka Filia w Bielsku Białej, Bielsko-Biała 1998
- ‘Metody Numeryczne’, Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski


Błędy
Jeżeli dane wejściowe obarczone są błędem, to automatycznie dane wyjściowe też będą (Należy dobrać odpowiednią dokładność danych wejściowych).

Błędy:
- Zaokrąglenia – błedy operacji arytmetycznych
- Obcięcia - popęniane przy zastąpieniu procesu nieskończonego procesem skończonym.

Algorytm jest numerycznie stabilny jeśli zwiększając dokładność obliczeń można zwiększyć dokładność otrzymanego rozwiązania.

a → wektor wejściowy
W = W(a) → wektor wyściowy

Uwarunkowanie zadania: Jak bardzo wektor wyjściowy W(a + δa) różni się od W(a). Zależy od rodzaju zadania.

Rozwiązywanie równania liniowego z jedną niewiadomą.
1) f(x) = 0; x = ?

Przedział izolacji – taki przedział, w którym funkcja ma tylko jeden pierwiastek.

Metoda iteracji prostej (kolejnych przybliżeń):

Równanie 1) przekształcamy do takiego:
x = g(x), gdzie: g – f → ciągła

Metoda polega na utworzeniu ciągu (x0 → zadana z góry wartość początkowa):
x1 = g(x0)
x2 = g(x1)
x3 = g(x2)
x4 = g(x3)
...
xn = g(xn-1)

Zakładamy, że ciąg x0, x1, x2, x0, …, xn jest zbieżny do x*, gdy n→∞, to xn → x*. Wtedy g(xn-1) → g(x*). Z zależności:
lim n→∞ { xn = g(xn-1) }
x* = g(x*)

Oznacza to, że x* spełnia równanie 2), a więc też równanie 1).
f(x*) = 0

[P]
x2 = c; (c > 0)
x2 – c = 0
f(x) = x2 – c
f(x) = 0
x = ½ * (x + c/x) = g(x) → jest ciągła na przedziale (0; ∞)

Warunek wystarczający (w skrócie ww) zbieżności:
Niech x*, x0, x1, x2, …, xn, należy E; E – przedział

Załóżmy, że istnieje liczba k>- taka, że dla każdej pary xi, sj є do E zachodzi nierówność:
|g(xi) - g(xj)| ≤ K * |xi – xj|

Jeżeli K < 1, to ciąg (xn)n є N jest zbieżny (do x*).

Jeśli g jest różniczkowalna w zbiorze E i dla wszystkich x należy E |g’(x)| < 1, to (xn)nєN jest zbieżny (do x*) → (tu: K = maxxєN |g’(x)|)
R1 → gdy pochodna mniejsza niż 1
R2 → gdy pochodna większan niż 1

Metoda linearyzacji (stycznych, Newtona)
f(x) = 0; rozwiązania szukamy w przedziale <a; b> (w tak zwanym przedziale izolacji).

Startujemy z punktu x0 tego przedziału, w którym f(x0) ma taki sam znak jak f’’(x0) → funkcja jest tam wypukła (zwykle x0 jest końcem przedziału).
	R3
Zakładamy, że f’ i f’’ w <a; b> nie zmieniają znaku oraz
f(a) * f(b) < 0

x0 – wartość początkowa przybliżenia pierwiastka (rozwiązania równania 1))

niech x1 = x0 + h; dla przybliżenia x1 równanie 1) ma postać:
f(x1) = 0; czyli f(x0 + h) = 0
Jeżeli funkcja ma pierwszą i drugą pochodną, to ze wzoru Taylora (dla n = 2):
f(x0 + h) = f(x0) + f’(x0)/1! * h + 1/2! * f’’(x0 + Θ * h) * h2
gdzie 0 < Θ < 1
Opuszczamy wyraz z drugą pochodną
f(x0 + h) ≈ f(x0) + h * f’(x0)
Linearyzujemy (wzór na funkcję zastępujemy wzorem na styczną)
f(xo) + h * f’(x0) ≈ 0 → tak chcemy (traktujemy to jako równość)
h ≈ -f(x0)/f’(x0)
x1 ≈ x0 + h = x0 – f(x0)/f’(x0)
xn+1 = xn – f(xn)/f’(xn) → następne przybliżenie rozwiązania obliczamy z poprzedniego tym wzorem (Newtona)

[P]
x2 – c = 0; c > 0; x = sqrt(c)
f(x) = x2 – c
f’(x) = 2 * x
f(x)/f’(x) = (x2 – c)/(2 * x) = ½ * (x – c/x)
xn+1 = xn – ½ * (xn – c/xn) = ½ * xn + ½ * c/xn = ½ * (xn + c/xn) → wzór Herona