W1/2
str 1
Rozwi zywanie równa nieliniowych
Niech f b dzie funkcj okre lon na przedziale [a,b]. Zadaniem jest
znalezienie takiego α z tego przedziału, e f (α) = 0. Oczywi cie takich
warto ci α mo e by wiele. Numerycznie, takie zadanie, rozwi zuje si
zwykle metodami iteracyjnymi, tj. tworzymy ci g kolejnych przybli e
xk , który zbiega do rozwi zania α. Z grupy tych metod zostan
omówione metody :
metoda bisekcji (połowienia)
metoda siecznych
metoda stycznych (Newtona)
Bardzo wa n rol , w metodach iteracynych, odgrywa wykładnik zbie no ci
metody. Jest to najwi ksza liczba p ( p ≥ 1 ) taka, e
ek+ 1 ≤ C ⋅ ( ek
)p
gdzie ek = α - xk , natomiast C jest stał nieujemn zale n zwykle od
funkcji f ( lub jej pochodnych ). Ci g ( xk ) jest tym szybciej zbie ny do
pierwiastka α im wi kszy jest wykładnik zbie no ci i im mniejsza jest stała
C, przy czym p odgrywa tutaj istotniejsz rol .
Je eli
−s
ek ≤ 10
to
− ps
ek+ 1 ≤ C ⋅ 10
Je eli metoda iteracyjna jest zbie na, to w przypadku p = 1 mówimy o
zbie no ci liniowej, natomiast dla p 1 o zbie no ci ponadliniowej.
Liczb α nazywamy m-krotnym pierwiastkiem równania f (x) = 0 , gdy
m
f ( x) = ( x − α ) ⋅ g( x) ,
przy czym g( α ) ≠ 0.
Mówimy, e α jest pierwiastkiem pojedy czym, je eli m = 1;
- wielokrotnym, je eli m 1.
Zało ymy, e f jest funkcj ci gł w przedziale [a,b] oraz f ( a) ⋅ f ( b ) 0
i f (x1) f ''(x1) 0
zapewniamy zbie no metody.
Wtedy zbie no do zera pojedy czego jest z
wykładnikiem
p=
a wi c jest to zbie no
1+
ponadliniowa.
2
5
( p ≅ 1.62 ),
(3)
f ( xk+ 1) ≤ ε
lub (2) i (3).
W1/2
str 3
Metoda stycznych
Zało ymy, e f jest funkcj klasy C 1 ( [a,b] )
Opis metody
(a) wybieramy punkt startowy x0 przedziału, w którym poszukujemy
pierwiastka,
(b) kolejne przybli enia xk+1 , k = 0,1,2,.... obliczamy ze wzoru
xk+ 1 = xk −
f ( xk)
f1(x) = d f ( x)
dx
f1( xk)
Stosujemy te same warunki ko czenia iteracji jak w metodzie siecznych.
Ilustacja działania metody stycznych.
(a, f(a)) styczna ma równanie
Uwaga. Poprowadzona z punktu
y - f(a) = f ' (a) (x -a)
Metoda stycznych, podobnie jak metoda siecznych, nie zawsze jest zbie na.
Je eli jednak
(1) f jest funkcj klasy C 2 ( [a,b] ) ,
(2) f ( a) ⋅ f ( b ) 0
zapewniamy zbie no tej metody.
Wtedy zbie no do zera pojedy czego jest z
wykładnikiem
p=2
a wi c jest to zbie no ponadliniowa i najszybsza w porównaniu z
przedstawionymi wcze niej metodami.
(*)
__________________________________________________________
Efektywno
metod
Miar zakresu oblicze potrzebnych do wyznaczenia pierwiastka z zadan
dokładno ci jest wska nik efektywno ci metody
1
E=p
K
gdzie p jest wykładnikiem zbie no ci metody, a K jest kosztem jednej iteracji.
Im E jest mniejsze, tym metoda jest mniej efektywna.
Koszt jednej iteracji zale y głównie od tego ile razy w jednym kroku nale y
obliczy warto funkcji f i ewentualnie jej pochodnych. Przyjmuj c, e koszt
obliczania funkcji f jest równy 1, a koszt obliczania pochodnej w stosunku do
funkcji jest równy K1, dla przedstawionych metod mamy
str 4
W1/2
a) bisekcji : E = 1 ; p = 1, K = 1,
b) siecznych : E =
1+
5
2
≅ 1.62 ; p =
1+
5
, Κ = 1,
2
1
c) stycznych : E = 2
1+ K1
; p = 2, K = 1 + K
1
Z omówionych trzech metod najni szy wska nik efektywno ci ma metoda bisekcji
(zbie no tylko liniowa). Porównanie dwóch pozostałych metod zale y od kosztu
obliczania pochodnej w stosunku do kosztu obliczania funkcji. Dla
1
K1 r - metoda siecznych.
_________________________________________________________
(*)
Normy wektorów
W wielu zastosowaniach fizyki i matematyki, szczególnie przy przeprowadzaniu oblicze
numerycznych, wygodnie jest wprowadzi pewne poj cie, analogiczne do znanej z geometrii
analitycznej długo ci wektora, a mianowicie normy wektora..
W przestrzeni Rn , której elementami s wektory x = [ x1, x2, ... ,xn]T, mo na wprowadzi wiele norm
wektorów, przy czym w obliczeniach numerycznych najcz ciej s stosowane nast puj ce normy
|| x ||1 = |x1| + |x2| + .... +|xn|
norma "Manhattan"
|| x ||2 = ( |x1|2 + |x2|2 + .... +|xn|2 ) 1/2 norma druga
|| x ||oo = max{ |x1| , |x2| , .... , |xn| } norma niesko czono
Rozwi zywanie układów równa nieliniowych
Rozwa amy układ n równa liniowych z n niewiadomymi x1, .... ,xn
f i ( x1, .... ,xn ) = 0 , i = 1,2, ... , n
który mo na zapisa w postaci wektorowej
F(x)=0
gdzie x = ( x1, .... ,xn ) oraz F ( x ) = [ f 1 ( x ), f 2 ( x ), ... , f n ( x ) ]T
Podobnie, jak w przypadku równa skalarnych , układ taki rozwi zujemy metodami
iteracyjnymi tworz c ci g kolejnych przybli e wektorowych
x (k) = ( x1(k), .... ,xn(k) )
zbie nych do wektora rozwi za
W1/2
α = (α1, ... , αn ).
... zobacz całą notatkę
Komentarze użytkowników (0)