Metody Numeryczne, Matematyka Finansowa, rok II semestr letni 2012/2013

Wykład 10: Równania nieliniowe, część 1

Będziemy zajmowali się rozwiązywaniem równań postaci f ( x) = 0 dla danej funkcji ciągłej f : [ a, b] → R. Większość metod można stosować jedynie wtedy, gdy znany jest przedział

izolacji pierwiastka, czyli taki, w którym znajduje się pojedynczy pierwiastek równania.

Lokalizacja pierwiastków może odbywać się z wykorzystaniem wykresu funkcji f , albo po przekształceniu równania do postaci ϕ( x) = ψ( x), gdzie wykresy funkcji są prostsze do wyko-nania.

Przykład 1

1

Można też użyć tablicowania funkcji, tzn. można zlokalizować przedział [ a, b], w którym f ( a) · f ( b) < 0. Na mocy twierdzenia Darboux, dla funkcji ciągłej, wewnątrz tego przedziału istnieje co najmniej jeden pierwiastek równania f ( x) = 0.

Kolejnym etapem obliczania przybliżonego pierwiastków jest uściślenie pierwiastków przybliżonych, tj. określenie tych pierwiastków z żądaną dokładnością.

Metoda bisekcji (inaczej: połowienia przedziału lub równego podziału) Niech dana będzie funkcja y = f ( x) określona, ciągła i monotoniczna w przedziale [ a, b] i niech f ( a) · f ( b) < 0. W przedziale tym istnieje jeden pierwiastek równania f ( x) = 0. Aby znaleźć przybliżoną wartość pierwiastka, dzielimy przedział [ a, b] na połowę punktem x 0 = a+ b.

2

Jeśli f ( x 0) = 0, to x 0 jest szukanym pierwiastkiem, jeśli zaś f( x 0) 6= 0, to z otrzymanych dwóch przedziałów [ a, x 0] i [ x 0 , b] wybieramy ten, na końcach którego funkcja ma przeciwne znaki -

czyli ten, w którym leży szukany pierwiastek. Z kolei ten przedział - nazwijmy go [ a 1 , b 1] dzielimy na połowę, ponownie badamy wartość funkcji f w punkcie x 1 = a 1+ b 1 i znaki funkcji na 2

końcach otrzymanych przedziałów, itd.

W wyniku takiego postępowania po pewnej liczbie kroków albo otrzymamy pierwiastek do-kładny f ( xn) = 0, albo ciąg przedziałów takich, że f ( an) · f ( bn) < 0, przy czym an oraz bn są odpowiednio początkiem i końcem n-tego przedziału:

[ a, b] = [ a 0 , b 0] ⊃ [ a 1 , b 1] ⊃ [ a 2 , b 2] ⊃ . . . ⊃ [ an, bn] ⊃ [ an+1 ,bn+1] ⊃ . . .

gdzie

a 0 ¬ a 1 ¬ a 2 ¬ . . . ¬ b 0

b 0 ­ b 1 ­ b 2 ­ . . . ­ a 0

oraz

b

b

n− 1 − an− 1

n − an =

,

n ­ 0

2

Ciąg ( an) jako niemalejący i ograniczony z góry jest zbieżny. Podobnie zbieżny jest ciąg ( bn).

Ponieważ

b

b

0 − a 0

n − an =

,

n ­ 0 ,

2 n

zatem

b

lim ( b

0 − a 0

n − an) = lim

= 0 .

n→∞

n→∞

2 n

Niech

ξ := lim an = lim bn.

n→∞

n→∞

Przejście do granicy w nierówności f ( an) · f ( bn) < 0 daje ( f ( ξ))2 ¬ 0, czyli f ( ξ) = 0.

Jeśli obliczenia przerywamy po znalezieniu przedziału [ an, bn], to pierwiastek równania na pewno się w nim znajduje. Najlepszym przybliżeniem tego pierwiastka jest środek przedziału a

x

n + bn

n =

,

2

a błąd tego przybliżenia szacujemy następująco

b

b

|ξ − x

n − an

0 − a 0

n| ¬

=

.

(1)

2

2 n+1

Uwaga 1 Metodą połowienia można znaleźć tylko jeden pierwiastek równania f ( x) = 0.

2

Przykład 2 Wyznaczyć z dokładnością do ε = 1 · 10 − 2 pierwiastek równania x 3 + x − 5 = 0.

2

3

Metoda regula falsi

Przyjmijmy, że w rozpatrywanym przedziale [ a, b] równanie f ( x) = 0 ma dokładnie jeden (jednokrotny) pierwiastek i f ( a) · f ( b) < 0. Ponadto niech f ∈ C 2([ a, b]) i niech jej pierwsza i druga pochodna mają stały znak na tym przedziale.1 Wobec tych założeń wykres funkcji y = f ( x) może być tylko jednym z czterech rodzajów: Rozpatrzymy przypadek, gdy na przedziale [ a, b] pochodna rzędu pierwszego i drugiego jest dodatnia. Dla pozostałych przypadków rozumowanie jest analogiczne.

Przez punkty A( a, f ( a)) i B( b, f ( b)) prowadzimy prostą o równaniu f ( b) − f ( a)

y − f ( a) =

( x − a) .

b − a

1Założenia te są potrzebne do oszacowania błędu i umożliwiają ustalenie stałego punktu iteracji.

4

Odciętą x 1 taką, że y 1 = 0 (prosta AB przecina oś 0X) przyjmujemy za pierwsze przybliżenie szukanego pierwiastka ξ równania f ( x) = 0. Stąd f ( a)

x 1 = a −

( b − a)

f ( b) − f ( a)

Jeżeli f ( x 1) = 0, to oczywiście x 1 jest szukanym pierwiastkiem. Załóżmy jednak, że tak nie jest.

Przez punkt C( x 1 , f( x 1)) oraz przez ten z punktów A i B, którego rzędna ma przeciwny znak niż f ( x 1), prowadzimy następną prostą. Odcięta x 2 punktu, w którym ta prosta przetnie oś 0X

daje nam drugie przybliżenie szukanego pierwiastka, itd. W ten sposób otrzymujemy kolejne wyrazy ciągu przybliżeń pierwiastka określonego wzorem rekurencyjnym: x 0 = a

f ( x

x

n)

n+1 = xn −

( b − x

f ( b) − f ( x

n) ,

n = 0 , 1 , 2 , . . .

n)

Punktem nieruchomym jest B.

Dla przypadku: f ′( x) < 0 i f ′′( x) > 0 dla x ∈ [ a, b], w kolejnych przybliżeniach punkt A pozostaje nieruchomy i otrzymujemy ciąg:

x 0 = b

f ( x

x

n)

n+1 = xn −

( x

f ( x

n − a) ,

n = 0 , 1 , 2 , . . .

n) − f ( a)

Dla oszacowania błędu przybliżenia można wykorzystać wzór, który otrzymujemy z twierdzenia o wartości średniej:

f ( xn+1) = ( xn+1 − ξ) f ′( c) , gdzie c leży między xn+1 i ξ.

Stąd

f ( x

|f ( x

|ξ − x

n+1)

n+1) |

n+1 | =

¬

f ′( c)

m

1

przy czym m 1 = inf |f′( x) |.

x∈[ a,b]

Uwaga 2 Metoda regula falsi jest zbieżna dla dowolnej funkcji ciągłej na przedziale [ a, b] (o ile oczywiście f ( a) · f ( b) < 0), jeżeli f ′ jest ograniczona i różna od zera w otoczeniu pierwiastka.

Uwaga 3 Nieruchomy jest ten koniec przedziału [ a, b] dla którego f · f ′′ > 0.

5