Ćwiczenie7 JK, Politechnika Lubelska, Studia, sem III, pen, METODY NUMERYCZNE
[ Pobierz całość w formacie PDF ]
Laboratorium metod numerycznych, RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych
nieliniowych: metodĢ bisekcji, regula falsi, siecznych, Newtona- Raphsona.
RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych nieliniowych
Pierwiastki rwnania
nieliniowego f(x)=0 na ogþ nie dajĢ wyrazię siħ za pomocĢ wzoru analitycznego, dlatego duŇe znaczenie
majĢ metody przybliŇonego rozwiĢzywania rwnaı. SĢ to
metody kolejnych
przybliŇeı pierwiastka
,
czyli
metody iteracyjne
. Oznacza to, Ňe startujĢc od jednego lub kilku przybliŇeı poczĢtkowych
pierwiastka konstruuje siħ ciĢg x
0
, x
1
, x
2
, ÈzbieŇny do tego pierwiastka.
W metodach tych zadanie znalezienia pierwiastkw uwaŇamy za wykonane, jeĻli potrafimy okreĻlię je z
ŇĢdanĢ dokþadnoĻciĢ i podaę oszacowanie bþħdu. NaleŇy pamiħtaę, Ňe wiħkszoĻę metod przybliŇonego
rozwiĢzywania rwnaı moŇna stosowaę jedynie wtedy, gdy znany jest przedziaþ, w ktrym znajduje siħ
pojedynczy pierwiastek
(przedziaþ izolacji).
Metoda bisekcji
Dane jest rwnanie: f(x)=0, przy czym o funkcji f(x) zakþadamy, Ňe jest ciĢgþa w przedziale
domkniħtym <a, b>, wewnĢtrz ktrego znajduje siħ dokþadnie jeden pierwiastek i na ktrego koıcach
wartoĻci funkcji f(x) majĢ przeciwne znaki, tzn. f(a)f(b)<0. Zadanie polega na znalezieniu przybliŇonej
wartoĻci pierwiastka rwnania f(x)=0. W tym celu dzielimy przedziaþ <a, b> na poþowy punktem
x
1
=(a+b)/2. JeŇeli f(x
1
)=0, to x
1
jest szukanym pierwiastkiem.
JeĻli zaĻ
xf
to z otrzymanych dwch przedziaþw <a, x
1
> i <x
1
, b> wybieramy ten, na
koıcach ktrego funkcja f(x) ma przeciwne znaki. Z kolei ten przedziaþ dzielimy na poþowy, ponownie
badamy wartoĻę funkcji f(x) w punkcie x
2
, znaki funkcji f(x) po pewnej liczbie krokw albo otrzymany
pierwiastek dokþadny f(x
n
)=0, albo ciĢg przedziaþw takich, Ňe f(x
i
)ßf(x
i+1
)<0, przy czym x
i
oraz x
i+1
sĢ
odpowiednio poczĢtkiem i koıcem i-tego przedziaþu, a jego dþugoĻę wynosi:
(
1
)
0
1
( )
(1).
x
-
+
x
=
b
-
a
i
i
1
i
2
Lewe koıce przedziaþw tworzĢ ciĢg niemalejĢcy i ograniczony z gry, a prawe koıce ciĢg nierosnĢcy i
ograniczony z doþu, wiħc z rwnania (1) wynika, Ňe istnieje ich wsplna granica ŋ.
Ze wzglħdu na stosowanĢ metodħ obliczeniowĢ, ten sposb znajdowania pierwiastkw nazywamy
metodĢ bisekcji
(takŇe
metodĢ poþowienia
lub
metodĢ rwnego podziaþu
.
Przykþad 1
. MetodĢ bisekcji znaleŅę rzeczywisty pierwiastek rwnania
+
xx
. ýatwo sprawdzię, Ňe
pierwiastek ten znajduje siħ w przedziale <0, 1>. Mamy f(0)=-1 oraz f(1)=1. Pochodna
0
3
-
1
=
0
xf
jest w przedziale <0, 1> dodatnia, wiħc jest to przedziaþ izolacji pierwiastka. Wyniki
obliczeı kolejnych przybliŇeı szukanego pierwiastka umieszczone sĢ w tabeli 1.
'
2
(
)
=
x
3
+
1
=
Tabela 1. Wyniki obliczeı dla przykþadu 1
i x
i
f(x
i
) i x
i
f(x
i
)
0,0 -1,0 4 0,6875 0,0124511
1,0 1,0 5 0,65625 -0,0611268
1 0,5 -0,375 6 0,671875 -0,0248299
2 0,75 0,171875 È È È
3 0,625 -0,1308593
PodstawowĢ zaletĢ bisekcji oprcz jej duŇej prostoty jest pewnoĻę, Ňe w kaŇdej kolejnej iteracji szukany
pierwiastek leŇy miħdzy dwiema wartoĻciami zmiennej x, dla ktrych funkcja f(x) zmienia znak.
Wielokrotne powtarzanie obliczeı doprowadzię musi zatem do uzyskania wyniku z ŇĢdanĢ dokþadnoĻciĢ.
Metoda regula falsi
Nazwa metody pochodzi od þaciıskich sþw:
regula
Î linia i
falsus
Î faþszywy. Jest to zatem metoda
faþszywego zaþoŇenia liniowoĻci funkcji. Zakþadamy, Ňe w rozpatrywanym przedziale <a, b> rwnanie
f(x)=0 ma dokþadnie jeden pierwiastek pojedynczy, i Ňe f(a) f(b)<0. Ponadto niech f(x) bħdzie w
przedziale <a, b> funkcjĢ klasy C
2
i niech jej pierwsza i druga pochodna majĢ staþy znak w tym
przedziale. Z zaþoŇeı tych wynika, Ňe wykres funkcji y=f(x) moŇe mieę jednĢ z czterech postaci
Laboratorium metod numerycznych, RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych
nieliniowych: metodĢ bisekcji, regula falsi, siecznych, Newtona- Raphsona.
przedstawionych ma rysunkach (1-4):
Wykres funkcji
f
(
x
) w przedziale <
a, b
> w zaleŇnoĻci od znaku
pierwszej
i
drugiej
pochodnej
funkcji
f
(
x
)
f
(
x
)
f x
f x
>
>
( )
( )
0
0
f x
f x
( )
( )
>
0
0
<
0
x
0
x
a
b
a
b
f
(
x
)
f x
f x
<
<
( )
( )
0
0
( )
f x
f x
<
0
0
f
(
x
)
( )
>
x
0
0
x
b
a
b
a
Rys. 1-4: Wykres funkcji
f
(
x
) w przedziale <
a, b
> w zaleŇnoĻci od znaku pierwszej i drugiej
pochodnej funkcji
Rozpatrzmy przypadek, gdy w przedziale <a, b> pochodne f(x) i fÑ(x) sĢ dodatnie (rys. 2- dla pozostaþych
przypadkw rozumowanie jest analogiczne). Przez punkty A(a, f(a)) i B(b, f(b)) prowadzimy ciħciwħ o
rwnaniu:
f
(
a
)
-
f
(
b
)
y
-
f
(
a
)
=
(
x
-
a
)
b
-
a
OdciħtĢ x
1
punktu, w ktrym ciħciwa AB
przecina oĻ 0x, przyjmuje siħ jako pierwsze
przybliŇenie szukanego pierwiastka rwnania
f(x)=0. StĢd
f
(
a
)
(
)
.JeŇeli
x
=
a
-
b
-
a
)
1
f
(
b
)
-
f
(
a
)
f(x
1
)=0, to oczywiĻcie x
1
jest szukanym
pierwiastkiem ŋ i zadanie jest zakoıczone.
ZaþŇmy, Ňe
xf
. JeŇeli przybliŇenie x1 nie
jest wystarczajĢco dokþadne, to przez punkt C(x
1
,
f(x
1
)) oraz przez ten z punktw A, B, ktrego
rzħdna ma przeciwny znak niŇ f(x
1
), prowadzimy
nastħpnĢ ciħciwħ (rys.2). Odciħta x
2
punktu, w
ktrym ta ciħciwa przetnie oĻ 0x, da nam drugie
przybliŇenie pierwiastka ŋ. Dla uproszczenia
rozumowania przyjħliĻmy, Ňe fÓ(x)>0 oraz
fÑ(x)>0 w przedziale <a, b>, co oznacza, Ňe
funkcja y=f(x) jest wypukþa i w kolejnych
przybliŇeniach punkt B pozostaje nieruchomy.
(
1
)
0
Laboratorium metod numerycznych, RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych
nieliniowych: metodĢ bisekcji, regula falsi, siecznych, Newtona- Raphsona.
(Dla funkcji f(x) takiej, Ňe fÓ(x)>0 i fÑ(x)<0 w przedziale <a, b>, nieruchomy byþby ten punkt A). JeŇeli
przybliŇenie x
2
jest nadal niewystarczajĢce, to przez punkty B i D(x
2,
f(x
2
)) prowadzimy trzeciĢ ciħciwħ,
co daje nam trzecie przybliŇenie x
3
itd. W ten sposb otrzymujemy kolejne wyrazy ciĢgu przybliŇeı
pierwiastka, x
1
, x
2
, x
3
, È, x
n
okreĻlonego wzorem rekurencyjnym:
f
(
x
)
(2)
k
x
=
a
,
x
=
x
-
(
b
-
x
),
k
=
1
2
,...,
n
0
k
+
1
k
k
f
(
b
)
-
f
(
x
)
k
MoŇna wykazaę, Ňe przy przyjħtych zaþoŇeniach ciĢg ten jest rosnĢcy i ograniczony, a wiħc zbieŇny, i Ňe
jego granicĢ jest szukany pierwiastek ŋ. (jeĻli nieruchomy jest punkt B, to kolejne wyrazy ciĢgu
przybliŇeı sĢ mniejsze od ŋ oraz f(x
k
)<0 dla kaŇdego k).PrzechodzĢc do granicy dla nŗ¯ z rwnoĻci (2)
otrzymujemy:
f
(
g
)
, przy czym
g
=
g
-
(
b
-
g
)
f
(
b
)
-
f
(
g
)
StĢd f(g)=0, a przy zaþoŇeniu istnienia tylko jednego pierwiastka w przedziale <a, b> mamy gŞŋ.
BþĢd bezwzglħdny przybliŇenia x
n
moŇna oszacowaę znajĢc dwa kolejne przybliŇenia x
n-1
i x
n
oraz
korzystajĢc z twierdzenia LagrangeÓa o przyrostach:
W niewielkim otoczeniu pierwiastka ŋ moŇna
przyjĢę, Ňe:
Przykþad 2.
MetodĢ regula falsi znaleŅę rzeczywisty pierwiastek
rwnania:
3x-cosx-1=0
BadajĢc funkcjħ wystħpujĢcĢ w rwnaniu moŇemy
stwierdzię, Ňe w przedziale <0,25,0,75> ma ona
dokþadnie jedno miejsce zerowe (w badanym przedziale
f(x)>0 oraz fÓ(x)>0). Kolejne jego przybliŇenia
obliczone wg wzoru (2) znajdujĢ sie w tabeli 2.
x
i
f(x
i
)
a=0,25 -1,218912
b=0,75 0,518311
x
1
=0,600819 -0,022416
x
2
=0,607003 -0,000352
x
3
=0,607100 -0,000006
x
4
=0,607101 -0,000002
x
5
=0,607101
Metoda regula falsi jest zbieŇna dla dowolnej funkcji w przedziale <a, b> (oczywiĻcie f(a)f(b)<0), jeŇeli
tylko pierwsza pochodna tej funkcji jest ograniczona i rŇna od zera w otoczeniu pierwiastka. JeŇeli
druga pochodna nie zmienia znaku w rozpatrywanym przedziale, to ten koniec przedziaþu, w ktrym
fÑ(x)f(x)>0, jest staþym punktem iteracji - wszystkie ciħciwy przechodzĢ przez ten punkt.
WadĢ tej metody
jest jej stosunkowo powolna zbieŇnoĻę.
Laboratorium metod numerycznych, RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych
nieliniowych: metodĢ bisekcji, regula falsi, siecznych, Newtona- Raphsona.
Metoda siecznych
Metodħ regula falsi moŇna znacznie ulepszyę, jeŇeli zrezygnuje siħ z ŇĢdania, aby w punktach
wytyczajĢcych kolejnĢ ciħciwħ funkcja f(x) miaþa rŇne znaki, natomiast do wyznaczenia (n+1) Î szego
przybliŇenia wykorzysta siħ punkty x
n
oraz x
n-1
. Wzr (2) przyjmuje wwczas postaę:
(3)
Metoda (3) nosi nazwħ
metody siecznych
. Jej zbieŇnoĻę jest znacznie szybsza niŇ metody regula falsi.
Niestety, zdarzajĢ siħ przypadki, gdy moŇe nie byę zbieŇna, np. poczĢtkowe przybliŇenia nie leŇĢ
dostatecznie blisko pierwiastka. W metodzie tej istotne znaczenie ma maksymalna graniczna dokþadnoĻę
wynikajĢca z przyjħtej arytmetyki. Gdy bowiem rŇnica x
n+1
-x
n
jest tego samego rzħdu, co oszacowanie
bþħdu, jakim jest obarczona, nastħpne przybliŇenie moŇe juŇ byę caþkowicie bþħdne.
NaleŇy za dodatkowe kryterium przerywania iteracji przyjmowaę wartoĻci
xf
tak, aby tworzyþy one
ciĢg malejĢcy ( w koıcowej fazie obliczeı). Iteracja powinna byę przerwana, jeŇeli rŇnica miħdzy
kolejnymi przybliŇeniami zamiast maleę zaczyna szybko wzrastaę. W takim wypadku zalecane jest
przeprowadzenie powtrnej lokalizacji pierwiastka (zawħŇajĢc poczĢtkowy przedziaþ jego izolacji).
(
n
)
Przykþad 3.
StosujĢc
metodħ siecznych
znaleŅę w przedziale <1, 2> pierwiastek rwnania
x
3
+x
2
-3x-3=0
Funkcja wystħpujĢca w rwnaniu ma w przedziale <1,2> dokþadnie jeden pierwiastek.
Kolejne przybliŇenia tego pierwiastka obliczmy zgodnie ze wzorem (3). Wyniki sĢ zapisane w tabeli 2.
i x
i
f(x
i
)
0 1
-4
1 2
3
2 1,57142
-1,36449
3 1,70540
-0,24784
4 1,73513
0,02920
5 1,73199
0,000576
6 1,73193
Metoda Newtona - Raphsona
Metoda
Newtona- Raphsona
, zwana takŇe
metodĢ Newtona
lub
metodĢ stycznych
, naleŇy do metod
iteracyjnych. Do zadania jednowymiarowego, tzn. jednego rwnania, w metodzie tej dla znalezienia
nastħpnego punktu iteracji korzysta siħ tylko z jednego punktu startowego x
0
. JeĻli wartoĻę dla x=x
0
jest
rŇna od zera, to w punkcie o wspþrzħdnych (x
0
, f(x
0
)) prowadzi siħ stycznĢ do wykresu funkcji.
Rys. Interpretacja geometryczna metody Newtona- Raphsona.
Laboratorium metod numerycznych, RozwiĢzywanie rwnaı i ukþadw rwnaı algebraicznych
nieliniowych: metodĢ bisekcji, regula falsi, siecznych, Newtona- Raphsona.
Pierwsze przybliŇenie x
1
pierwiastka stanowi punkt przeciħcia tej stycznej z osiĢ 0x. Nastħpnie z punktu o
wspþrzħdnych (x
1
, f(x
1
)) prowadzi siħ kolejnĢ stycznĢ. Punkt przeciħcia tej stycznej z osiĢ 0x jest drugim
przybliŇeniem pierwiastka x
2
. w ten sposb otrzymuje siħ kolejne wyrazy ciĢgu przybliŇeı x
1
, x
2
, x
3
, È .
Wzr rekurencyjny opisujĢcy obliczanie tych wyrazw ma postaę:
x
k+1
=x
k
+h
k
,
k=0,1,È
(4)
f
(
x
)
k
h
k
-
=
,
f
'
(
x
)
Obliczenia koıczy siħ, gdy:
eps
=
+1
przy czym eps oznacza zadanĢ z gry dokþadnoĻę i jest oszacowaniem bþħdu f(x
n
)/fÓ(x
n
).
Wybr punktu startowego x0 jest bardzo istotny i moŇe decydowaę o zbieŇnoĻci ciĢgu kolejnych
przybliŇeı.
k
k
k
h
x
-
x
<
Przykþad 4.
Zbadaę zbieŇnoĻę rozwiĢzania
rwnania y=e
-x
+x
2
-2 metodĢ Newtona od
wyboru punktu startowego x
0
. Wykres
funkcji przedstawiono obok.
Badana funkcja ma dwa rzeczywiste
pierwiastki x1>0 oraz x2<0. Wyniki obliczeı
tych pierwiastkw z rŇnĢ dokþadnoĻciĢ i dla
rŇnych punktw startowych (niekiedy
bardzo odlegþych od szukanych pierwiastkw
zebrano w tabeli.
x
0
-1,0
10
100
dokþadnoĻę 0,001
0,000001 0,001
0,000001 0,001
0,000001
liczba
iteracji
4
5
6
7
10
11
1,3159
-0.635
-0,635
5,1
5,1
50,1
50,1
-0,534
-0,543
2,74
2,74
25,02
25,02
-0,537
-0,537
1,71
1,71
12,5
12,5
-0,537
-0,5373
1,36
1,369
6,35
6,35
-0,5372
1,31
1,317
3,33
3,33
1,3159
1,3169
1,95
1,95
1,3159
1,43
1,43
1,32
1,32
1,315
1,315
1,3159
1,3159
1,315973
Z tabeli wynika, Ňe osiĢgniħcie dokþadnoĻci tysiĢc razy wiħkszej wymaga tylko jednego kroku wiħcej.
WartoĻę kolejnego przybliŇenia najbardziej zmienia siħ w pierwszych iteracjach. Wybr punktu
startowego ma takŇe znaczenie Î np. dla x
0
=-1 potrzeba 4 iteracji, zaĻ 11 dla x
0
=100.
W wyniku przeprowadzonych obliczeı stwierdzono, Ňe wartoĻę pochodnej fÓ(x) poczĢwszy od drugiej
iteracji zmienia siħ nieznacznie.
Z wyraŇenia na h
k
wynika, ze pochodnĢ fÓ(x) moŇna obliczaę z takĢ dokþadnoĻciĢ wzglħdnĢ, z jakĢ
oblicza siħ f(x). MoŇna wiħc nie wyznaczaę fÓ(x) w kaŇdej iteracji. Znacznie przyspiesza to proces
iteracyjny (szczeglnie dla rwnaı nieliniowych), nie wpþywajĢc znaczĢco na jego zbieŇnoĻę.
Uproszczone wzory przyjmujĢ postaę (4).
[ Pobierz całość w formacie PDF ]