PRZYBLIĩONE METODY

ROZWIĄZYWANIA

RÓWNAē

Metody kolejnych przybliĪeĔ

3

Metody kolejnych przybliĪeĔ

Twierdzenie . (Bolzano – Cauchy’ego)

JeĪeli funkcja

F(x)

jest ciągáa w przedziale domkniĊtym

[a,b]

i

F(a)⋅F(b) < 0

, to miĊdzy punktami

a

i

b

znajduje siĊ

co najmniej jeden pierwiastek równania

F(x) = 0

.

Twierdzenie 2.

JeĪeli w przedziale

[a, b]

speánione są zaáoĪenia twierdzenia .

i dodatkowo

sgn F

′(x) = const

dla

x∈[a,b]

, to przedziaá ten

jest przedziaáem izolacji pierwiastka równania

F(x) = 0

.

4

Metody kolejnych przybliĪeĔ

Przebieg funkcji miĊdzy punktami

a

i

b

5

Metody kolejnych przybliĪeĔ

Przykáad

Sprawdziü czy podany przedziaá jest przedziaáem izolacji
jednego pierwiastka równania

F(x) = 0

.

3

2

( )

3

2

5

F x

x

x

x

= −

−

+

[ , ] [1, 2]

a b =

6

Metody kolejnych przybliĪeĔ

( )

(1)

F a

F

=

3

2

1

3 1

2 1 5

= − ⋅ − ⋅ +

1

=

( )

(2)

F b

F

=

3

2

2

3 2

2 2 5

= − ⋅ − ⋅ +

3

= −

PoniewaĪ:

(1)

(2)

0

F

F

⋅

<

to wiadomo, Īe pomiĊdzy punktami a i b znajduje siĊ co
najmniej jeden pierwiastek równania

F(x) = 0

.

7

Metody kolejnych przybliĪeĔ

d ( )

( )

d

F x

F x

x

′

=

2

3

6

2

x

x

=

−

−

( )

(1)

F a

F

′

′

=

2

3 1

6 1 2

= ⋅ − ⋅ −

5

= −

( )

(2)

F b

F

′

′

=

2

3 2

6 2 2

= ⋅ − ⋅ −

2

= −

PoniewaĪ:

sgn

( )

const

dla

[ , ]

F x

x

a b

′

=

∈

czyli funkcja ma staáy znak w przedziale

[a,b],

to przedziaá

[a, b]

jest przedziaáem izolacji jednego pierwiastka

równania

F(x) = 0

.

Metoda bisekcji

9

Metoda bisekcji

Niech

[a,b]

bĊdzie przedziaáem izolacji pierwiastka równania

F(x) = 0

.

Jako pierwsze dwa wyrazy ciągu przybliĪeĔ przyjmuje siĊ:

1

2

x

a x

b

=

=

Kolejne przybliĪenia wynikają ze wzoru:

1

,

[1,(

2)],

2

2

i

k

i

x

x

x

k

i

i

−

+

=

∈

−

>

10

Metoda bisekcji

k

dobierane jest tak, aby:

1

i

i

i

k

x

x

x

x

−

−

≈

−

1

(

) ( )

0

i

i

F x

F x

−

<

11

Metoda bisekcji

12

Metoda bisekcji

PoniewaĪ kolejne przybliĪenia znajdują siĊ kaĪdorazowo w
przedziaáach izolacji, oraz

1

1

i

i

i

i

x

x

x

x

+

−

− < −

Metoda jest zbieĪna

13

Metoda bisekcji

Zaleta metody: prostota

Wada metody: wolna zbieĪnoĞü procesu iteracyjnego

14

Metoda bisekcji

Algorytm

1

x

a

=

2

x

b

=

1

2

1

1

1

1

2

1, 2,...,

2

( )

( )

0

i

m

x

x

x

y F x
y

F x

y y

x

x

x

x

=

­

°

+

° =

°

° =

®

° =

°

⋅ >

=

°

°

=

¯

jeĪeli

to

w przeciwnym wypadku

15

Metoda bisekcji

Przykáad

Dla funkcji i przedziaáu izolacji z poprzedniego przykáadu
obliczyü metodą bisekcji pierwiastek równania

F(x) = 0

z

dokáadnoĞcią

ε.

3

2

( )

3

2

5

F x

x

x

x

= −

−

+

[ , ] [1, 2]

a b =

0.1

ε =

( )

i

F x < ε

1

2

1

2

x

a

x

b

= =

= =

16

Metoda bisekcji

. iteracja

1

2

2

x

x

x

+

=

1 2

1.5

2

+

=

=

( )

(1.5)

y F x

F

=

=

1.375

= −

1

1

( )

(1)

y

F x

F

=

=

1

=

( )

F x > ε

1

1.375

y y

⋅ = −

0

<

2

1.5

x

x

= =

1

2

1

2

x

x

=

=

17

Metoda bisekcji

2. iteracja

1

2

2

x

x

x

+

=

1 1.5

1.25

2

+

=

=

( )

(1.25)

y F x

F

=

=

0.234

= −

1

1

( )

(1)

y

F x

F

=

=

1

=

( )

F x > ε

1

0.234

y y

⋅ = −

0

<

2

1.25

x

x

= =

1

2

1

1.5

x

x

=

=

18

Metoda bisekcji

3. iteracja

1

2

2

x

x

x

+

=

1 1.25

1.125

2

+

=

=

( )

(1.125)

y F x

F

=

=

0.376

=

1

1

( )

(1)

y

F x

F

=

=

1

=

( )

F x > ε

1

0.376

y y

⋅ =

0

>

1

1.125

x

x

= =

1

2

1

1.25

x

x

=

=

19

Metoda bisekcji

4. iteracja

1

2

2

x

x

x

+

=

1.125 1.25

1.1875

2

+

=

=

( )

(1.1875)

y F x

F

=

=

0.069

=

( )

F x < ε

1

2

1.125

1.25

x

x

=

=

Pierwiastek:

1.1875

x

=

Metoda ciĊciw

21

Metoda ciĊciw

Rozwiązanie równania

F(x) = 0

jest przybliĪone ciągiem miejsc

zerowych ciĊciw poprowadzonych miĊdzy punktami
stanowiącymi koĔce kolejnych przedziaáów izolacji.

22

Metoda ciĊciw

23

Metoda ciĊciw

Równanie ciĊciw, moĪna zapisaü w postaci:

1

1

1

1

(

)

(

)

(

)

i

i

k

i

k

i

y F x

x x

F x

F x

x

x

−

−

−

−

−

−

=

−

−

x

k

– drugi kraniec przedziaáu izolacji

[x

i−1

,x

k

]

Czyli pierwszą ciĊciwĊ prowadzimy miedzy punktami:

( , ( ))

( , ( ))

a F a

b F b

24

Metoda ciĊciw

Dla

y = 0

:

1

1

1

1

(

)

(

)

(

)

k

i

i

i

i

k

i

x

x

x

x

F x

F x

F x

−

−

−

−

−

=

−

−

∗∗∗∗

25

Metoda ciĊciw

ZaáoĪenie:

W przedziale

[a,b]

, lub w kolejnym przedziale izolacji znak

drugiej pochodnej funkcji

F(x)

nie zmienia siĊ.

Wyrazy ciągu

∗∗∗∗

dają przybliĪenie pierwiastka

z niedomiarem lub nadmiarem.

26

Metoda ciĊciw

PrzybliĪenie z niedomiarem:

( )

0

( )

0

F x

F x

′

′′

>

>

lub

( )

0

( )

0

F x

F x

′

′′

<

<

wtedy:

*

1

2

...

i

i

i

x

x

x

x

+

+

<

<

< <

27

Metoda ciĊciw

PrzybliĪenie z nadmiarem:

( )

0

( )

0

F x

F x

′

′′

>

<

lub

( )

0

( )

0

F x

F x

′

′′

<

>

wtedy:

*

1

2

...

i

i

i

x

x

x

x

+

+

>

>

> >

Przy czym dwie sąsiednie wartoĞci ciągu przybliĪeĔ związane

są wzorem

∗∗∗∗

28

Metoda ciĊciw

Oszacowanie pierwiastka z niedomiarem

( )

0

( )

0

F x

F x

′

<

′′

<

( )

0

( )

0

F x

F x

′

>

′′

>

29

Metoda ciĊciw

Oszacowanie pierwiastka z nadmiarem

( )

0

( )

0

F x

F x

′

>

′′

<

( )

0

( )

0

F x

F x

′

<

′′

>

30

Metoda ciĊciw

Ciąg

{x

i

}

jest monotoniczny i ograniczony, posiada wiĊc granicĊ:

lim

i

i

x

g

→∞

=

czyli:

lim{ }

i

i

x

→∞

( )

(

)

( )

k

k

x

g

g F g

F x

F g

−

= −

−

g

=

stąd wynika:

( )

0

F g =

*

g x

=

co dowodzi zbieĪnoĞci metody.

31

Metoda ciĊciw

x

k

– punkt staáy pĊku ciĊciw

[ , ],

x

a b

∈

( )

( )

0

F x F x

′

′′

⋅

>

k

x

b

=

[ , ],

x

a b

∈

( )

( )

0

F x F x

′

′′

⋅

<

k

x

a

=

Lewy lub prawy kraniec przedziaáu

[a,b]

, czyli

x

k

= a

lub

x

k

= b

.

32

Metoda ciĊciw

Przykáad

Dla funkcji i przedziaáu izolacji z poprzedniego przykáadu
obliczyü metodą ciĊciw pierwiastek równania

F(x) = 0

z

dokáadnoĞcią

ε.

3

2

( )

3

2

5

F x

x

x

x

= −

−

+

[ , ] [1, 2]

a b =

0.1

ε =

2

( )

3

6

2

F x

x

x

′

=

−

−

( )

6

6

F x

x

′′

=

−

33

Metoda ciĊciw

OkreĞlenie punktu pĊku ciĊciw

x

k

:

2

a b

z

+

=

1 2

1.5

2

+

=

=

( )

(1.5)

F z

F

′

′

=

4.25

= −

( )

(1.5)

F z

F

′′

′′

=

6

=

( )

( )

0

F z F z

′

′′

⋅

<

1

k

x

a

= =

1

2

x

b

= =

(

) 1

k

F x =

1

( )

3

F x = −

34

Metoda ciĊciw

1

2

1

1

1

( )

(

)

( )

k

k

x

x

x

x

F x

F x

F x

−

= −

−

1.25

=

2

( )

(1.25)

F x

F

=

0.234

= −

( )

F x > ε

. iteracja

35

Metoda ciĊciw

2

3

2

2

2

( )

(

)

( )

k

k

x

x

x

x

F x

F x

F x

−

= −

−

1.202

=

3

( )

(1.202)

F x

F

=

0.0017576

= −

( )

F x < ε

2. iteracja

Pierwiastek:

1.202

x =

Metoda stycznych

(Newtona)

37

Metoda stycznych

Rozwiązanie równania

F(x) = 0

w przedziale

[a,b]

jest

przybliĪone ciągiem miejsc zerowych stycznych do
funkcji

F(x)

.

38

Metoda stycznych

39

Metoda stycznych

Równanie stycznej w punkcie

x

i−1

:

1

1

1

(

)

(

)(

)

i

i

i

y F x

F x

x x

−

−

−

′

−

=

−

Dla

y = 0

:

1

1

1

(

)

,

1

(

)

i

i

i

i

F x

x

x

i

F x

−

−

−

=

−

>

′

40

Metoda stycznych

Wybór pierwszego przybliĪenia

x

1

= a

lub

x

1

= b

:

( )

( )

0

F x F x

′

′′

⋅

>

1

x

b

=

( )

( )

0

F x F x

′

′′

⋅

<

1

x

a

=

 JeĪeli druga pochodna w przedziale izolacji nie ma staáego

znaku, to proces iteracyjny moĪe byü rozbieĪny

41

Metoda stycznych

Wybór pierwszego przybliĪenia w metodzie stycznych

( )

0

( )

0

F x

F x

′

>

′′

<

( )

0

( )

0

F x

F x

′

<

′′

>

42

Metoda stycznych

Wybór pierwszego przybliĪenia w metodzie stycznych c. d.

( )

0

( )

0

F x

F x

′

>

′′

>

( )

0

( )

0

F x

F x

′

<

′′

<

43

Metoda stycznych

Przykáad

Dla funkcji i przedziaáu izolacji z poprzedniego przykáadu
obliczyü metodą stycznych pierwiastek równania

F(x) = 0

z dokáadnoĞcią

ε.

3

2

( )

3

2

5

F x

x

x

x

= −

−

+

[ , ] [1, 2]

a b =

0.1

ε =

2

( )

3

6

2

F x

x

x

′

=

−

−

( )

6

6

F x

x

′′

=

−

44

Metoda stycznych

2

a b

z

+

=

1 2

1.5

2

+

=

=

( )

( )

0

F z F z

′

′′

⋅

<

1

1

x

a

= =

1

( ) 1

F x =

1

( )

5

F x

′

= −

45

Metoda stycznych

1

2

1

1

( )

( )

F x

x

x

F x

= −

′

1.2

=

2

( )

0.008

F x =

. iteracja

( )

F x < ε

MoĪna przerwaü obliczenia!

2

( )

4.88

F x

′

= −

46

Metoda stycznych

2

3

2

2

( )

( )

F x

x

x

F x

= −

′

1.202

=

3

( )

0.00176

F x = −

2. iteracja

( )

F x < ε

Metoda stycznych

- inny wariant

48

Metoda stycznych – inny wariant

49

Metoda stycznych – inny wariant

1

1

1

1

1

(

)

,

lub

,

1

( )

i

i

i

F x

x

x

x

a

x

b i

F x

−

−

=

−

=

=

>

′

50

Metoda stycznych – inny wariant

Przykáad

Dla funkcji i przedziaáu izolacji z poprzedniego przykáadu
obliczyü metodą stycznych pierwiastek równania

F(x) = 0

z dokáadnoĞcią

ε.

3

2

( )

3

2

5

F x

x

x

x

= −

−

+

[ , ] [1, 2]

a b =

0.1

ε =

2

( )

3

6

2

F x

x

x

′

=

−

−

( )

6

6

F x

x

′′

=

−

51

Metoda stycznych – inny wariant

2

a b

z

+

=

1 2

1.5

2

+

=

=

( )

( )

0

F z F z

′

′′

⋅

<

1

1

x

a

= =

1

( ) 1

F x =

1

( )

5

F x

′

= −

52

Metoda stycznych – inny wariant

1

2

1

1

( )

( )

F x

x

x

F x

= −

′

1.2

=

2

( )

0.008

F x =

. iteracja

( )

F x < ε

MoĪna przerwaü obliczenia!

2

3

2

1

( )

( )

F x

x

x

F x

= −

′

1.202

=

3

( )

0.0001935

F x =

2. iteracja