1

Wybrane metody przybliżonego

wyznaczania rozwiązań (pierwiastków)

równań algebraicznych

w postaci f (x)

Wykład czwarty

EiT, sem. 2, 2014/2015

2





f

jest funkcją rzeczywistą zmiennej rzeczywistej x,



 

R

R









x

f

x

f :

.

f(x) = 0

Rozwiązanie składa się z dwóch etapów:

- wyboru przedziału izolacji; przedziału, w którym funkcja ciągła, na końcach tego

przedziału ma różne znaki, czyli f(a)∙f(b) < 0,

- zastosowania algorytmu iteracyjnego do wyszukiwania właściwego rozwiązania.

Metody szukania przedziału [a, b]:

- tabelka,

- oszacowanie przedziału, w którym

f

1

(x) = f

2

(x)

3

Warunki gwarantujące znalezienie pierwiastka:

1. różne znaki funkcji na końcach przedziału

   

0





b

f

a

f

,

2. ciągłość funkcji w przedziale [a, b],
3. istnienie pierwszej pochodnej, pochodna nie zmienia znaku w całym przedziale,

funkcja jest gładka i monotoniczna,

4. druga pochodna ma stały znak w całym przedziale, tj. nie ma punktów przegięcia,

przebieg funkcji albo wklęsły, albo wypukły.

4

Zakończenie procesu poszukiwania rozwiązania:

-







)

k

(

x

(

f

1

, δ - zależy od poszukiwanej wartości,

- zbieżność iteracji, czyli

,

x

x

)

k

(

)

k

(









1

ε - zależy od poszukiwanej wartości,

- iteracja trwa zbyt długo, warunek k > k

max

, koniec obliczeń,

- wartości

,

x

(

f

x

(

f

)

k

(

)

k

(





1

nieprawidłowy algorytm.

Wybór wartości

.

x

)

( 0

Metody: bisekcji, regula falsi, siecznych, stycznych, iteracji prostej.

5

Metoda bisekcji

– metoda połowienia

Zakłada się, że występująca w równaniu (1) funkcja





f jest ciągła na zadanym przedziale

 

b

a, i spełnia w punktach krańcowych warunek

f (x) = 0

(1)

   

0





b

f

a

f

Należy znaleźć przedział

 

b

a,

Ustalić liczby ε, δ (większe od błędu zaokrąglenia
wynikającego ze skończonej precyzji zapisu liczb w komputerze)

6

Przebieg obliczeń

Ustalamy, że

)

(

)

(

b

b

,

a

a

0

0





 

2

0

0

0

)

(

)

(

b

a

x





Sprawdzamy, czy

,

)

x

(

f

)

(





0

jeżeli TAK, to

)

(

x

0

jest rozwiązaniem

*

x

x

)

(



0

pierwsza iteracja

7

jeżeli NIE, to sprawdzamy,
czy przedział [a,

)

(

x

0

] spełnia warunek

 

 

0

0





)

(

x

f

a

f

,

jeżeli TAK, to

)

(

)

(

)

(

b

x

,

a

a

1

0

1





jeżeli NIE, to

)

(

)

(

)

(

b

b

,

a

x

1

1

0





Następnie

2

1

1

1

)

(

)

(

)

(

b

a

x





Sprawdzamy, czy

,

)

x

(

f

)

(





1

druga

iteracja

8

jeżeli TAK, to

)

(

x

1

jest rozwiązaniem

*

x

x

)

(



1

jeżeli NIE, to sprawdzamy, czy przedział [

)

(

a

1

,

)

(

x

1

]

spełnia warunek

   

0

1

1





)

(

)

(

x

f

a

f

,

jeżeli TAK, to

)

(

)

(

)

(

)

(

b

x

,

a

a

2

1

2

1





jeżeli NIE, to

)

(

)

(

)

(

)

(

b

b

,

a

x

2

1

2

1





Następnie

2

2

2

2

)

(

)

(

)

(

b

a

x





trzecia iteracja

9

Sprawdzamy, czy

,

)

x

(

f

)

(





2

jeżeli TAK, to

)

(

x

2

jest rozwiązaniem

*

x

x

)

(



2

.

Jeżeli nie, to sprawdzamy …. itd.

Algorytm

2

)

k

(

)

k

(

)

k

(

b

a

x





gdzie k = 0, 1, 2, 3, …..

Zakończenie obliczeń





)

x

(

f

)

k

(

wtedy

*

x

x

)

k

(



10

a

b

f(x)

x

f(a)

f(b)

x

(0)

a

(1)

b

(1)

a

(0)

b

(0)

 

2

)

0

(

)

0

(

0

b

a

x





,

)

x

(

f

)

(





0

*

x

x

)

(



0

2

1

1

1

)

(

)

(

)

(

b

a

x





,

)

x

(

f

)

(





1

*

x

x

)

(



1

x

(1)

a

(2)

b

(2)

x

(2)

Ilustracja graficzna

│f (x

(2)

)│ < δ

x

(2)

= x

*

11

Karta następstw

START

CZYTAJ: a, b,

δ f (x) = 0

k = 0

x (k) = (a+b)/2

│f (x (k) )│<δ

TAK

x

*

= x (k)

STOP

NIE

f (a)

·f (x (k)) < 0

NIE

a = x (k)

TAK

b = x (k)

k = k + 1

12

Regula falsi

13

Metoda: regula falsi

Zakłada się, że występująca w równaniu (1) funkcja





f jest ciągła na zadanym przedziale

 

b

a, i spełnia w punktach krańcowych warunek

f (x) = 0

(1)

   

0





b

f

a

f

Należy znaleźć przedział

 

b

a,

Ustalić liczby ε, δ (większe od błędu zaokrąglenia
wynikającego ze skończonej precyzji zapisu liczb w komputerze)

14

Przebieg obliczeń

Wyznaczamy punkt przecięcia prostej przechodzącej przez punkty

a, f (a) i b, f (b) z osią x

)

a

(

f

)

b

(

f

)

a

b

(

)

b

(

f

b

x

)

(











1

Jeżeli

a

x

b

x

to

)

b

(

f

)

x

(

f

)

(

)

p

(

)

(









0

1

0

Jeżeli NIE, to

b

x

a

x

)

(

)

p

(





0

Sprawdzamy, czy

,

)

x

(

f

)

(





1

Jeżeli TAK, to

)

(

x

1

jest rozwiązaniem

*

x

x

)

(



1

a

b

x

(1)

f(x)

x

15

Jeżeli NIE, to

)

x

(

f

)

x

(

f

)

x

x

(

)

x

(

f

x

x

)

k

(

)

p

(

)

k

(

)

p

(

)

k

(

)

k

(

)

k

(













1

k = 1, 2, 3 ,…

Koniec obliczeń, gdy







)

x

(

f

)

k

(

1

wtedy

*

x

x

)

k

(





1

16

f(x)

x

f(b)

f(a)

a

b

0

Ilustracja graficzna

x

(1)

17

Ilustracja graficzna

f(x)

x

f(b)

f(a)

a

b

0

x

(1)

f (x

(1)

)

·f (b) < 0 x

(0)

= a x

(p)

= b

x

(p)

│f(x

(1)

)

│ < δ

TAK

koniec obliczeń x

(1)

= x

*

NIE

liczymy dalej

x

(0)

18

Ilustracja graficzna

f(x)

x

f(b)

f(a)

a

b

0

x

(1)

f (x

(1)

)

·f (b) < 0 x

(p)

= b x

(0)

= a

x

(p)

x

(2)

x

(0)