Numeryczne obliczanie pochodnej

Pochodną można obliczyć na trzy sposoby:

przednia:

x

x

i

x

i+1

pierwsza pochodna w punkcie x

i

jest:

 



  

i

1

i

i

1

i

i

x

x

x

f

x

f

x

f













ocena błędu O(h

i

), gdzie h

i

=x

i+1

-x

i

Pochodna centralna:

x

x

i

x

i+1

x

i-1

y

f

i-1

f

i

f

i+1

f

i-1

Ψ

0

(x)

f

i

Ψ

1

(x)

f

i+1

Ψ

2

(x)

W

2

(x)= f

i-1

Ψ

0

(x)+ f

i

Ψ

1

(x)+ f

i+1

Ψ

2

(x)

gdzie

 













  











 













i

1

i

1

i

1

i

i

1

i

2

1

i

i

1

i

i

1

i

1

i

1

1

i

1

i

i

1

i

1

i

i

0

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x





























































Dla skrócenia zapisu oznaczamy:

h

i-1

=x

i

-x

i-1

h

i

=x

i+1

-x

i

i mamy:

 





















  















  









i

1

i

i

i

1

i

2

i

1

i

1

i

1

i

i

1

i

1

i

1

i

1

i

1

i

1

i

1

i

i

1

i

i

i

1

i

1

i

1

i

i

0

h

h

h

x

x

x

x

x

h

h

x

x

x

x

h

h

x

x

x

x

x

h

h

h

x

x

x

x

x

x

x

x

h

x

x

x

x

x



















































































Obliczając pochodne mamy:

 









 

 









i

1

i

i

i

1

i

i

1

i

i

i

1

i

2

i

1

i

1

i

1

i

i

1

i

1

i

1

i

1

i

1

i

1

i

1

i

i

i

1

i

1

i

1

i

i

0

h

h

h

x

x

x

2

h

h

h

x

x

x

x

x

h

h

x

x

x

2

h

h

x

x

x

x

x

h

h

h

x

x

x

2

h

h

h

x

x

x

x

x





























































































Obliczamy pochodną centralną w punkcie x=x

i

:

 













 

  







i

1

i

i

1

i

i

1

i

i

1

i

i

i

2

i

1

i

i

1

i

i

1

i

1

i

1

i

i

i

1

i

1

i

1

i

i

i

1

i

1

i

1

i

i

i

1

i

1

i

1

i

i

i

i

i

0

h

h

h

h

h

h

h

x

x

x

h

h

h

h

h

h

x

x

x

2

x

h

h

h

h

h

h

h

x

x

h

h

h

x

x

x

x

x























































































Podstawiając mamy obliczoną pierwszą pochodną centralną:









i

1

i

i

1

i

1

i

i

1

i

1

i

i

i

i

1

i

1

i

i

1

i

x

x

h

h

h

h

f

h

h

h

h

f

h

h

h

h

f

dx

df

i

































W przypadku równomiernie rozłożonych punktów, czyli h

i-1

=h

i

=h,

to

 

2

1

i

1

i

x

x

h

O

h

2

f

f

dx

df

i













Trzeci sposób obliczenia jest nazywany pochodną wsteczną:

x

x

i

x

i-1

 

1

i

i

1

i

i

i

x

x

f

f

x

f













Dokładność obliczeń jest rzędu O(h

i-1

).

Przykład: Pochodna funkcji: f(x) = sin(x)

Przyjęto krok jednakowy h=0.1

0

1.57

3.14

4.71

6.28

1

0.5

0

0.5

1

f x

( )

pf x

( )

cf x

( )

tf x

( )

x

Przednia pochodna:

 





 

h

x

sin

h

x

sin

x

pf







Centralna pochodna:

 



 



h

2

h

x

f

h

x

f

x

cf









Wsteczna pochodna:

 

  



h

h

x

f

x

f

x

tf







Błąd oceniano według zależności:

dla przedniej: ep(x)=pf(x)-cos(x)
dla centralnej: ec(x)=cf(x)-cos(x)
dla wstecznej: et(x)=tf(x)-cos(x)

0

1.57

3.14

4.71

6.28

0.05

0.025

0

0.025

0.05

ep x

( )

ec x

( )

et x

( )

x

0

1.57

3.14

4.71

6.28

0.002

0.001

0

0.001

0.002

ec x

( )

x

O(h)

O(h

2

)

krok h=0.001

0

1.57

3.14

4.71

6.28

1

0.5

0

0.5

1

f x

( )

pf x

( )

cf x

( )

tf x

( )

x

ocena błędu dla h=0.001:

0

1.57

3.14

4.71

6.28

510

4

2.510

4

0

2.510

4

510

4

ep x

( )

ec x

( )

et x

( )

x

0

1.57

3.14

4.71

6.28

210

7

110

7

0

110

7

210

7

ec x

( )

x

O(h)

O(h

2

)

Obliczenie pochodnej funkcji: f(x)=sin(ωx)
pochodna obliczona dokładnie: f’(x)=ωcos(ωx)
krok obliczeń: h=0.1/f
przyjęto f=50Hz

0

0.005

0.01

0.015

0.02

400

200

0

200

400

f x

( )

pf x

( )

cf x

( )

tf x

( )

x

0

0.005

0.01

0.015

0.02

100

50

0

50

100

ep x

( )

ec x

( )

et x

( )

x

0

0.005

0.01

0.015

0.02

40

20

0

20

40

ec x

( )

x

h=0.001/f

0

0.005

0.01

0.015

0.02

400

200

0

200

400

f x

( )

pf x

( )

cf x

( )

tf x

( )

x

błąd przy h=0.001/f

0

0.005

0.01

0.015

0.02

1

0.5

0

0.5

1

ep x

( )

ec x

( )

et x

( )

x

0

0.005

0.01

0.015

0.02

0.004

0.002

0

0.002

0.004

ec x

( )

x

Wpływ długości kroku na wyniki obliczeń

0

1.57

3.14

4.71

6.28

1



10

6

5



10

7

0

5



10

7

1



10

6

pf x

( ) dpf x

( )



x

h=10

-6

0

1.57

3.14

4.71

6.28

1



10

7

5



10

8

0

5



10

8

1



10

7

pf x

( ) dpf x

( )



x

h=10

-7

0

1.57

3.14

4.71

6.28

2



10

8

1



10

8

0

1



10

8

2



10

8

pf x

( ) dpf x

( )



x

h=10

-8

0

1.57

3.14

4.71

6.28

2



10

6

1



10

6

0

1



10

6

2



10

6

pf x

( ) dpf x

( )



x

h=10

-10

Wzory dla pochodnych do 4-go rzędu przy równoodległych

punktach. Odległość między punktami wynosi h.

Pochodna wsteczna obliczana z dokładnością O(h).















































































































i

1

i

2

i

3

i

4

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

1

4

6

4

1

1

3

3

1

0

1

2

1

0

0

1

1

0

0

0

f

h

f

h

f

h

f

h

Pochodna wsteczna obliczana z dokładnością O(h

2

)

























































































































i

1

i

2

i

3

i

4

i

5

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

f

3

14

26

24

11

2

5

18

24

14

3

0

2

5

4

1

0

0

3

4

1

0

0

0

f

h

f

h

2

f

h

f

h

2

Pochodna centralna, błąd O(h

2

):















































































































2

i

1

i

i

1

i

2

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

1

4

6

4

1

1

2

0

2

1

0

1

2

1

0

0

1

0

1

0

f

h

f

h

2

f

h

f

h

2

Pochodna centralna z dokładnością O(h

4

)











































































































































3

i

2

i

1

i

i

1

i

2

i

3

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

f

f

1

12

39

56

39

12

1

1

8

13

0

13

8

1

0

1

16

30

16

1

0

0

1

8

0

8

1

0

f

h

6

f

h

8

f

h

12

f

h

12

Pochodna przednia z dokładnością O(h)















































































































4

i

3

i

2

i

1

i

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

1

4

6

4

1

0

1

3

3

1

0

0

1

2

1

0

0

0

1

1

f

h

f

h

f

h

f

h

Przednia z dokładnością O(h

2

)



























































































































5

i

4

i

3

i

2

i

1

i

i

IV

i

4

i

3

i

2

i

f

f

f

f

f

f

11

11

24

26

14

3

0

3

14

24

18

5

0

0

1

4

5

2

0

0

0

1

4

3

f

h

f

h

2

f

h

f

h

2

Aproksymacja

Dążenie do minimalizacji normy.

Przykłady stosowanych norm:

 

 

 

 

b

,

a

l

i

przestrzen

w

)

)]

x

(

f

[

(

f

b

,

a

L

i

przestrzen

w

dx

)

x

(

f

)

x

(

w

f

b

,

a

L

i

przestrzen

w

dx

)

x

(

f

f

b

,

a

C

i

przestrzen

w

)

x

(

f

sup

f

N
2

N

0

i

2

1

2

i

w

2,

2

1

2

b

a

w

,

2

2

2

1

2

b

a

2

0

]

b

,

a

[

x











































Zadanie aproksymacji polega na minimalizacji normy:

)

x

(

g

)

x

(

F



Niech







K

0

n

n

n

)

x

(

h

a

)

x

(

g

i dane są wartości funkcji :

i

i

F

)

x

(

F



w punktach i=0,2,...P.
Niech będzie zastosowana norma z wagą:















 

P

0

i

2

K

0

n

i

n

n

i

i

)

x

(

h

a

F

w

i szukamy minimum sumy ze względu na współczynniki a

n

.

Przykład:

x

0

0.2

0.5

0.6

1

y

0.1

0.2

0.4

0.45

0.4

2

2

1

0

x

a

x

a

a

)

x

(

g







Przyjmujemy wielomian aproksymujący w postaci:

przyjmując funkcję wagową równą jedności otrzymujemy:







 







2

2

1

0

2

2

1

0

2

2

1

0

2

2

1

0

2

0

2

1

0

a

a

a

4

.

0

36

.

0

a

6

.

0

a

a

45

.

0

25

.

0

a

5

.

0

a

a

4

.

0

04

.

0

a

2

.

0

a

a

2

.

0

)

a

1

.

0

(

)

a

,

a

,

a

(

d









































Szukamy ekstremum funkcji d(a

0

,a

1

,a

2

) i przyrównując do zera

pierwsze pochodne względem a

0

, a

1

i a

2

otrzymujemy:

67

.

0

a

1937

.

1

a

349

.

1

a

65

.

1

a

d

91

.

0

a

2365

.

1

a

65

.

1

a

3

.

2

a

d

55

.

1

a

65

.

1

a

3

.

2

a

5

a

d

3

1

0

2

2

1

0

1

2

1

0

0





































Rozwiązanie powyższych równań ma postać:

151

.

0

a

493

.

0

a

204

.

0

a

0

1

2









Interpolacja z wagą















 







2

2

1

0

2

2

1

0

2

2

1

0

2

2

1

0

2

0

2

1

0

w

a

a

a

4

.

0

5

.

0

a

36

.

0

a

6

.

0

a

45

.

0

a

25

.

0

a

5

.

0

a

4

.

0

a

04

.

0

a

2

.

0

a

2

.

0

5

.

0

a

1

.

0

25

.

0

a

,

a

,

a

d









































Po obliczeniu ekstremum mamy: a

0

=0.319

a

1

=0.158

a

2

=-0.041

Wielomian aproksymujący jest:

 

2

w

x

041

.

0

x

158

.

0

319

.

0

x

W







x

0

0.2

0.5

0.6

1

y

0.1

0.2

0.4

0.45

0.4

y

ap

0.151 0.241

4

0.346

5

0.373

3

0.44

1

x

0.5

0

0.2

0.1

0.2

0.4

y

y

y

ap

Aproksymacja za pomocą funkcji wykładniczej

Wyniki badań eksperymentalnych aproksymujemy funkcją:

 





b

ax

exp

A

x

y





x

x

0

x

1

x

2

… x

k

… x

N

y(x) y

0

y

1

y

2

… y

k

… y

N

x

y

x

0

x

1

x

k

x

N

y

0

y

1

y

k

y

N

Przyjmujemy

b=-ax

0

i A=y

0

otrzymujemy zadanie aproksymacyjne:

t

t

0

=0 t

1

=

x

1

-

x

0

t

2

=x

2

-

x

0

… t

k

=

x

k

-

x

0

… t

N

=x

N

-

x

0

z(t) z

0

=1 z

1

=y

1

/y

0

z

2

=y

2

/

y

0

… z

k

=y

k

/

y

0

…

z

N

=

y

N

/y

0

Mamy następujące zadanie:

 

 

at

exp

t

z



Obliczamy logarytm naturalny rzędnych:

t

t

0

t

1

t

2

…

t

k

…

t

N

w(t)=ln[z

(t)]

0 ln(z

1

)

ln(z

2

)

… ln(z

k

) … ln(z

N

)

at

)

t

(

w

ap



i mamy zadanie aproksymacyjne:

 





min

at

w

a

f

N

0

k

2

k

k











Po obliczeniu pochodnej otrzymujemy równanie:





0

t

at

w

2

da

df

N

k

0

k

k

k

k















którego rozwiązanie jest:











N

1

k

2

k

N

1

k

k

k

t

t

w

a

i otrzymujemy:

 









0

0

x

x

a

exp

y

x

y





Wielomiany trygonometryczne











n

1

k

k

k

0

n

)

kx

sin

b

kx

cos

a

(

2

a

)

x

(

F

aproksymacja funkcji okresowej na dyskretnym równoodległym
zbiorze punktów:

i=0,1,2,..., 2L-1

L

i

x

i





ciągły:

L

n

)

jx

sin

b

jx

cos

a

(

a

2

1

)

x

(

y

n

1

j

i

i

0

n













a współczynniki wyznacza się z równania:













1

L

2

0

i

2

i

n

i

)

x

(

y

)

x

(

f

Różniczkując względem a

k

otrzymujemy następujące równania

dla wyznaczania współczynników:





0

kx

cos

jx

sin

b

jx

cos

a

2

a

)

x

(

f

i

1

L

2

0

i

n

1

j

i

j

i

j

0

i



























0

kx

sin

jx

cos

0

=

k

=

j

dla

2L

0

k

=

j

dla

L

k

j

dla

0

kx

cos

jx

cos

1

L

2

0

l

l

l

1

L

2

0

i

i

i





























Mamy tożsamości:

Na mocy powyższych tożsamości mamy:

L

n

,...,

1

,

0

j

L

lj

cos

)

x

(

F

L

1

a

1

L

2

0

l

l

j















Podobnie wyznaczamy współczynniki b

j

z równania:





0

kx

sin

jx

sin

b

jx

cos

a

2

a

)

x

(

F

l

1

L

2

0

l

n

1

j

l

j

l

j

0

l



























korzystając z tożsamości:

















k

=

j

dla

L

k

j

dla

0

kx

sin

jx

sin

1

L

2

0

l

l

l

otrzymujemy:

L

n

,...,

1

,

0

j

L

jl

sin

)

x

(

F

L

1

b

1

L

2

0

i

l

j















Szereg zespolony.

Dana jest funkcja określona przez podanie jej wartości f

n

w punktach:

N

n

2

x

n





gdzie n=0,1,2,...,N-1. Aproksymujemy funkcję wielomianem
trygonometrycznym postaci:

1

i

gdzie

)

ikx

exp(

c

)

x

(

w

1

N

0

k

k













Otrzymujemy N równań dla wyznaczenia współczynników c

k

:











1

N

0

k

n

k

n

n

)

ikx

exp(

c

f

)

x

(

w

Rozwiązanie ostatniego układu równań czyli współczynniki c

k

są określane równaniami:











1

N

0

n

n

n

p

)

ipx

exp(

f

N

1

c

Idea szybkie transformaty Fouriera tzw. FFT

Fast Fourier Transform

Ponieważ

N

n

2

x

n





więc

























N

pn

2

i

exp

ipx

exp

n

Oznaczmy:



















N

i

2

epx

w

Zauważmy, że

Re

Im

w=w

N+1

N

2

w

p

=w

p+N

Każda całkowita potęga w leży na okręgu jednostkowym
i co więcej jeżeli wykładnik p potęgi w

p

jest większy od N

to punkty się nakrywają. Na tym spostrzeżeniu bazuje FFT.

Piszemy:









1

N

0

n

n

pn

p

f

w

N

1

c

Możemy zapisać w postaci macierzowej:

Oznaczając:

1

N

,...,

1

,

0

n

dla

N

f

g

n

n







 

 

 

n

pn

p

g

w

c 

gdzie

 





































2

1

N

1

N

0

1

N

1

0

0

0

0

pn

w

w

w

.

.

.

w

w

w

w

w

w

w









Ponieważ w

0

=1 więc nie będziemy pisać zerowej kolumny i wiersza.

Dalej mamy związki:



















N

i

2

epx

w





 

k

k

N

w

k

N

i

2

exp

k

N

i

2

exp

N

N

i

2

exp

k

N

N

i

2

exp

w

















 













 



































czyli

 

k

k

N

w

w







a więc wiersze i kolumny: 1 i N-1
2 i N-2
..............
k i N-k
..............
N/2-1 i N/2+1 dla N parzystych
(N-1)2 i (N+1)/2 dla N nieparzystych

są sprzężone

.

W praktyce najczęściej stosowane N=2

M

.

Jeżeli liczba węzłów interpolacyjnych mniejsza od 2

M

,

to uzupełniamy zerami.

N=8

w

w

2

w

3

w

4

=-

1

(w

*

)

3

(w

*

)

2

w

*

w

2

w

4

w

6

w

8

=1 (w

*

)

6

(w

*

)

4

(w

*

)

2

w

3

w

6

w

9

w

12

=

-1

(w

*

)

9

(w

*

)

6

(w

*

)

3

w

4

w

8

w

12

w

16

=

1

(w

*

)

12

(w

*

)

8

(w

*

)

4

w

5

w

10

w

15

w

20

=

-1

(w

*

)

15

(w

*

)

10

(w

*

)

5

w

6

w

12

w

18

w

24

=

1

(w

*

)

18

(w

*

)

12

(w

*

)

6

w

7

w

14

w

21

w

28

=

-1

(w

*

)

21

(w

*

)

14

(w

*

)

7



















8

i

2

epx

w











 



8

i

2

epx

w

*

lub inaczej

a b c

-

1

c

*

b

*

a

*

b -

1

b

*

1 b -1 b

*

c b

*

a

-

1

a

*

b c

*

-1 1 -1 1 -1 1 -1

c

*

b a

*

-

1

a b

*

c

b

*

-

1

b 1 b

*

-1 b

a

*

b

*

c

*

-

1

c

b a

















































7

6

5

4

3

2

1

0

f

f

f

f

f

f

f

f

dla otrzymania tablicy mnożników wystarczy obliczyć połowę

pierwszego wiersza!!!

np. a=a

r

+ia

i

oraz a

*

=a

r

-ia

i

czyli np.

af

1

+a

*

f

7

=a

r

(f

1

+f

7

)+ia

i

(f

1

-f

7

)

i podobnie dla innych

operacji.

Wykorzystanie przedstawionych uproszczeń pozwala w stosunku

do zwykłego algorytmu zawierającego N

2

działań zespolonych

zmniejszyć ich liczbę dla N=2

M

do 2NM

1

2

3

4

5

6

0

1200

2400

3600

4800

6000

2

2 m



m2

m 1





m

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.1875

f(x) -4 1

-

1.125

-

0.01562

5

0.4980

45

0.2430

8

x

-

0.21875

-

0.23437

5

-

0.242187

5

-

0.24609375

f(x

)

0.11453

2

0.04962

54

0.017044

5

0.00072103

7

x

-

0.248046
9

-

0.2465820
3

-

0.2463379

-

0.246215
8

f(x) -

0.007449
1

-

0.0013209
8

-

0.0002999
3

0.000210

57

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.236641

2

-

0.24423354

f(x) -4 1 0.19

2

0.040134

27

0.00849729

2

     

 

   

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.24583563

2

-

0.2461749

2

-

0.24624682

9

f(x) 0.00180035

9

0.0003816

03

0.00008089

1

x

-

0.24626207

2

f(x) 0.00001714

7

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.24752475

2

-

0.24625643

9

f(x) -4

1 0.192

-

0.00526448

1

0.00004070

3

w regula falsi potrzeba 8 kroków

x

-

0.2462661

7

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.24626865

7

-
0.24626617

2

f(x) 1 -

0.01562

5

-
0.00001039

-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.9746

8

0.97468

0.9618

34

0.96183

4

y

n

0

0

0.15771

8

0.1577

18

0.19300

6

n

5

6

7

8

x

n

0.9553

79

0.95537

9

0.95215

09

0.952151

y

n

0.1930

06

0.20834

7

0.20834

7

0.215573

6

n

9

10

11

12

x

n

0.95054

09

0.950541 0.949738

9

0.949739

y

n

0.21557

34

0.2190799

4

0.219079

7

0.220803

6

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

























