Rozwiązywanie równań algebraicznych

f(x)=0

Metoda bisekcji

Przykład:

0

1

x

4

x

3







x

-1 0 -0.5

-0.25

-0.125

-

0.187

5

f(x

)

-4 1

-

1.12

5

-

0.0156

25

0.498

045

0.243

08

x

-

0.2187

5

-

0.2343

75

-

0.24218

75

-

0.246093

75

f(x

)

0.1145

32

0.0496

254

0.01704

45

0.000721

037

x

-

0.24804
69

-

0.246582
03

-

0.246337
9

-

0.24621
58

f(x) -

0.00744
91

-
0.001320
98

-
0.000299
93

0.00021
057

Zaleta metody: Jeżeli pierwiastek istnieje, to go znajdziemy.

Wada metody: Duża liczba obliczeń

Regula falsi.

Założenia:

a) funkcja ma w przedziale [a,b] tylko jeden pierwiastek
i zachodzi f(a)f(b)<0,
b) jest funkcja jest klasy C

2

[a,b], pierwsza i druga pochodna

nie zmieniają znaku na przedziale [a,b].

Funkcja spełniająca powyższe założenia musi mieć w otoczeniu

miejsca zerowego jeden z następujących przebiegów:

f(a)

a

b

f(b)

x

y

f(a)

a

b

f(b)

x

y

f(a)

a

b

f(b)

x

y

f(a)

a

b

f(b)

x

y

Przebieg obliczeń metodą regula falsi:

x

y

a

b

f(a)

f(b)

x

1

f(x

1

)

x

2

analitycznie: ustalamy koniec z
warunku f(x

1

)f(a)<0 lub f(x

1

)f(b)<0

Prowadzimy prostą:

   

   

a

f

b

f

a

f

x

f

a

b

a

x











   

   

a

f

b

f

a

f

x

f

a

b

a

x











ale f(x

1

)=0 stąd

 

   

a

f

b

f

a

f

a

b

a

x

1











lub

     

a

f

a

f

b

f

a

b

a

x

1









Dla n-tej iteracji mamy b=x

n-1

i podstawiając mamy:



    

a

f

a

f

x

f

a

x

a

x

1

n

1

n

n













Ocena błędu dla dostatecznie małego przedziału [x

n-1

,x

n

]

można przyjąć jako:

)

x

(

f

)

x

(

f

)

x

(

f

x

x

x

x

n

1

n

n

1

n

n

n

d













Metoda regula falsi jest zbieżna dowolnej funkcji ciągłej
na przedziale [a,b].
Poszukiwanie pierwiastka zostaje zakończone jeżeli:







 1

n

n

x

x

Metoda jest wolno zbieżna.

Przykład:

0

1

x

4

x

3







x

-1 0 -0.2

-

0.23664

12

-

0.244233

54

f(x

)

-4 1 0.19

2

0.04013

427

0.008497

292

     

 

   

2

.

0

x

4

4

1

1

0

1

x

a

f

a

f

b

f

a

b

a

x

1

1

1





























Ponieważ f(-1)=-4, a f(x

1

)=0.192,

więc stałym punktem będzie x=-1

x

-

0.245835

632

-

0.246174

92

-

0.246246

829

f(x

)

0.001800

359

0.000381

603

0.000080

891

x

-

0.2462620

72

f(x

)

0.0000171

47

w metodzie bisekcji potrzebowaliśmy

14 kroków

ocena błędu:

)

x

(

f

)

x

(

f

)

x

(

f

x

x

x

x

n

1

n

n

1

n

n

n

d













)

x

(

f

)

x

(

f

)

x

(

f

x

x

x

x

n

1

n

n

1

n

n

n

d













ocena błędu:





6

d

10

1

.

4

246262072

.

0

x











Metoda siecznych

Przepis:

)

x

(

f

)

x

(

f

)

x

(

f

x

x

x

x

n

1

n

n

1

n

n

n

1

n















Przykład:

0

1

x

4

x

3







x

-1 0 -0.2

-

0.2475247

52

-

0.2462564

39

f(x) -4 1

0.19

2

-

0.0052644

81

0.0000407

03

w regula falsi potrzeba 8 kroków

x

-

0.246266

17

f(x

)

0.907E-8

w 6-tym kroku

Koniecznie trzeba obliczać f(x

n

) i jeżeli zaczyna narastać

należy zawęzić przedział i powtórzyć obliczenia.

Niebezpieczeństwo znalezienia fałszywego pierwiastka.

Metoda szybsza niż reguła falsi.

a

b

x

1

Pierwsza iteracja musi startować

z punktów spełniających warunek:

f(a)f(b)<0

Metoda Newtona - Raphsona

Niech  małe w mamy:



  

 

 

2

x

f

x

f

x

f

x

f

2



















Pomijając małe drugiego rzędu 

2

mamy, że f(x+)=0,

jeżeli

 

 

x

f

x

f









Graficznie:

x

y

x

n



n

 

n

n

x

f

tg







Równanie prostej stycznej
w punkcie x

n

jest:

  

  

n

n

n

x

f

x

x

x

f

y









x

n+1

Prosta:

  

  

n

n

n

x

f

x

x

x

f

y









przechodzi przez zero, czyli y=0, w punkcie x

n+1

i mamy:

 

 

n

n

n

1

n

x

f

x

f

x

x









Przykład:

0

1

x

4

x

3







 

x 0

-0.25 -

0.246268

657

-
0.2462661

72

f(x

)

1 -

0.0156
25

-
0.000010
39

-0.2E-10

W 3 krokach dokładność osiągana w metodzie siecznych

w 5 krokach

W obliczeniach numerycznych pochodną najczęściej oblicza się
numerycznie:

Metoda Newtona – Raphsona jest zbieżna kwadratowo, tzn.

 

 

i

i

2
i

1

i

x

f

2

x

f















  

  

h

x

f

h

x

f

x

f

i

i

i









„Pechowe” przypadki:

x

f(x)

x

0

x

1

x

2

rozbieżna

Zmniejszyć przedział

[x

d

,x

0

]

x

d

cykl

x

f(x)

x

1

=x

3

=...

x

2

=x

4

=...

x

d

Budując procedurę należy się zabezpieczyć przed taką możliwością.

Wystartować z punktu x

1

znajdującego się bliżej x

d

Pierwiastki wielokrotne:

 

 

0

x

f

i

0

x

f

d

d







Przy pierwiastkach wielokrotnych badać funkcję:

)

x

(

f

)

x

(

f

)

x

(

g





Pierwiastki zespolone

Przykład

0

4

x

x

2

3







5

3

1

1

3

5

200

140

80

20

40

100

f x

( )

0

x

Szukamy zespolonych pierwiastków metodą Newtona - Raphsona

n

2
n

2
n

3
n

n

1

n

x

2

x

3

4

x

x

x

x













Jako punkt startowy musimy wybrać liczbę zespoloną:

x

0

=i

gdzie

1

i





i

2309

.

1

8462

.

0

x

e

6056

.

3

e

1623

.

3

i

i

2

3

i

3

i

x

1

69

.

213

i

43

.

198

i

1



























x

2

=-0.50605+1.21289i

x

3

=-0.49471+1.32934i

x

4

=-0.50119+1.32409i

x

5

=-0.500059+1.322855i

x

6

=-0.5+1.32275i

błąd=-0.00083198+0.00043738i

x

d

=-0.5+1.322288i

Układy równań nieliniowych

Dany jest układ równań:













0

x

,...,

x

,

x

f

..........

..........

..........

0

x

,...,

x

,

x

f

0

x

,...,

x

,

x

f

n

2

1

n

n

2

1

2

n

2

1

1







Dla skrócenia zapisu wprowadzamy oznaczenia:





 

X

f

x

,...,

x

,

x

f

k

n

2

1

k



oraz



































)

x

,...,

x

,

x

(

f

.

.

)

x

,...,

x

,

x

(

f

)

x

,...,

x

,

x

(

f

)

X

(

F

n

2

1

n

n

2

1

2

n

2

1

1

i równanie zapisujemy krótko:

 

0

X

F



Metoda iteracji prostej

Równanie:

 

0

X

F



zapisujemy w postaci:

 

X

G

X 

i procedura iteracji prostej ma postać:





1

n

n

X

G

X





Stosowana szczególnie w przypadkach jeżeli mamy dobre

przybliżenie początkowe. Sytuacja taka występuje np. w

przypadku małej zmiany parametrów równania.

Przykład:

1

y

2

x

1

y

x

2

2

2

2









którego rozwiązaniem jest: x

1

=1; y

1

=0 oraz x

2

=-1; y

2

=0

Szukamy rozwiązania układu po małej zmianie parametrów:

1

y

01

.

2

x

95

.

0

y

x

2

2

2

2









mamy schemat iteracyjny:

01

.

2

x

1

y

y

95

.

0

x

2

1

n

n

2

1

n

n













Jako startowy punkt wybieramy: x

0

=1; y

0

=0 i mamy:

n 0

1

2

3

4

x

n

1 0.974

68

0.9746

8

0.961

834

0.9618

34

y

n

0

0

0.1577

18

0.157

718

0.1930

06

n

5

6

7

8

x

n

0.955

379

0.9553

79

0.9521

509

0.95215

1

y

n

0.193

006

0.2083

47

0.2083

47

0.21557

36

n

9

10

11

12

x

n

0.9505

409

0.95054

1

0.9497

389

0.94973

9

y

n

0.2155

734

0.21907

994

0.2190

797

0.22080

36

Z przedstawionych obliczeń widać, że metoda jest wolno

zbieżna i dlatego stosowana tylko w przypadkach, gdy

znamy bardzo dobrze zerowe przybliżenie. Zastosowanie

w równaniach różniczkowych.

Metoda Newtona - Raphsona

Rozwijamy funkcję f

k

(X) w szereg Taylora w otoczeniu

punktu X

i

:

0

)

x

x

(

x

f

...

)

x

x

(

x

f

)

X

(

f

...

..........

..........

..........

..........

..........

..........

..........

..........

0

)

x

x

(

x

f

...

)

x

x

(

x

f

)

X

(

f

.........

..........

..........

..........

..........

..........

..........

..........

0

)

x

x

(

x

f

...

)

x

x

(

x

f

)

X

(

f

i

,

n

n

X

X

n

n

i

,

1

1

X

X

1

n

i

n

i

,

n

n

X

X

n

k

i

,

1

1

X

X

1

k

i

k

i

,

n

n

X

X

n

1

i

,

1

1

X

X

1

1

i

1

i

i

i

i

i

i









































































Dla uproszczenia zapisu wprowadzamy macierz Jacobiego
zdefiniowaną następująco:

i

X

X

n

n

2

n

1

n

n

2

2

2

1

2

n

1

2

1

1

1

i

x

f

.

.

x

f

x

f

.

.

.

.

.

.

.

.

.

.

x

f

.

.

x

f

x

f

x

f

.

.

x

f

x

f

)

X

(

J





















































































i w postaci macierzowej możemy krótko zapisać układ równań:

   

0

X

X

J

X

F

i

i

i







gdzie oznaczono:

i

1

i

i

X

X

X









i rozwiązując symbolicznie mamy:

   

i

i

1

i

1

i

X

F

X

J

X

X









Przykład

B x

4

y

4







0.0221347267



1.7154013895

10

3













B x

3

y

3







0.4054281364

0.0757925914

















y

3

1.6034305983





x

3

2.547524882



B x

2

y

2







2.0774058055
0.4332616428















y

2

1.2783983143





x

2

2.6115212513



B x

1

y

1







1.0181697533

0.2113862264

















y

1

0.6296790316





x

1

0.8775588736





Nowa wartość startowa

x

n

y

n













x

n 1



y

n 1















J x

n 1



y

n 1









1



(

)

B x

n 1



y

n 1















n

1 10





y

0

1



x

0

1



B x y



(

)

f1 x y



(

)

f2 x y



(

)















J x y



(

)

pf1xx y



(

)

pf2xx y



(

)

pf1yx y



(

)

pf2yx y



(

)















pf2yx y



(

)

1

x y



sinx

( ) siny

( )







pf2xx y



(

)

cosx

( ) cos y

( )



1

x y







pf1yx y



(

)

expx y



(

) sin5 x



(

)



siny

( )





pf1xx y



(

)

expx y



(

) sin5 x



(

) 5 cos5 x



(

)





(

)





f2 x y



(

)

cos y

( ) sinx

( )



ln x y











f1 x y



(

)

expx y



(

) sin5 x



(

)



cos y

( )





B x

10

y

10







7.6327832943

10

16





1.0061396161

10

16















y

10

1.5326556001





x

10

2.5104053429



B x

7

y

7







7.6327832943

10

16





1.0061396161

10

16















y

7

1.5326556001





x

7

2.5104053429



B x

6

y

6







1.429500962



10

11





2.5677376891



10

13















y

6

1.5326556001





x

6

2.5104053429



B x

5

y

5







6.4971110534



10

6





3.05616917610

6















y

5

1.5326533005





x

5

2.5104046859



B x

4

y

4







0.0221347267



1.7154013895

10

3



















y

4

1.5304688912





x

4

2.5085770863



B x

3

y

3







0.4054281364

0.0757925914

















y

3

1.6034305983





x

3

2.547524882



B x

2

y

2







2.0774058055
0.4332616428















y

2

1.2783983143





x

2

2.6115212513



B x

1

y

1







1.0181697533

0.2113862264

















y

1

0.6296790316





x

1

0.8775588736





B v

6

w

6







2.8284190988



10

4





4.0146896267



10

6















w

6

1.0538411892



v

6

0.0359317811





B v

5

w

5







3.082730668



10

3





6.399377386710

6















w

5

1.0541200235



v

5

0.0361162013





B v

4

w

4







0.0321949207



9.5125042042



10

4



















w

4

1.0561052291



v

4

0.038130869





B v

3

w

3







0.2812551155



0.0206871382















w

3

1.097928869



v

3

0.0523869108





B v

2

w

2







1.4623634971

0.0241516982

















w

2

0.8706086893



v

2

0.0653226558



B v

1

w

1







1.251877214



0.5666309304

















w

1

0.9185509088



v

1

0.2566102428





v

n

w

n













v

n 1



w

n 1















PJ v

n 1



w

n 1





h







1



(

)

B v

n 1



w

n 1



























w

0

0.1



v

0

0.1



h

0.1



PJ x y

 h



(

)

f1 x h



y



(

) f1 x y



(

)



h

f2 x h



y



(

) f2 x y



(

)



h

f1 x y h





(

) f1 x y



(

)



h

f2 x y h





(

) f2 x y



(

)



h























Obliczenia przy numerycznie liczonej pochodnej

h=0.1

B v

10

w

10







2.0727367989



10

8





1.9211454649



10

10















w

10

1.0538173605



v

10

0.0359127014





B v

7

w

7







2.6276351633



10

5





1.6937433446



10

7















w

7

1.053819747



v

7

0.0359144545





B v

6

w

6







2.8284190988



10

4





4.0146896267



10

6















w

6

1.0538411892



v

6

0.0359317811





B v

5

w

5







3.082730668



10

3





6.3993773867

10

6















w

5

1.0541200235



v

5

0.0361162013





B v

4

w

4







0.0321949207



9.5125042042



10

4



















w

4

1.0561052291



v

4

0.038130869





B v

3

w

3







0.2812551155



0.0206871382















w

3

1.097928869



v

3

0.0523869108





B v

2

w

2







1.4623634971

0.0241516982

















w

2

0.8706086893



v

2

0.0653226558



B v

1

w

1







1.251877214



0.5666309304

















w

1

0.9185509088



v

1

0.2566102428





v

n

w

n













v

n 1



w

n 1















PJ v

n 1



w

n 1





h







1



(

)

B v

n 1



w

n 1

























