Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 1

Właściwości metod iteracyjnych

iteratio=powtarzanie (procesu numerycznego w celu ulepszenia
wcześniejszych wyników)=kolejne przybliżanie
metoda iteracji prostej:
x=F(x)
równanie iteracji

)

x

(

F

x

i

i

=

+1

dostateczny warunek zbieżności:

1

<

)

x

(

'

F

szybkość zbieżności tym większa im mniejszy

)

x

(

'

F

Def.:
Niech x

i

będzie ciągiem kolejnych przybliżeń zbieżnej metody iteracyjnej:

a

x

lim

i

i

=

∞

→

. Jeżeli istnieje liczba

1

≥

p

taka, że

1

1

0

1

=

<

≠

=

−

−

+

∞

→

p

gdy

C

,

C

a

x

a

x

lim

p

i

i

i

to mówimy, że metoda jest rzędu p w punkcie a. Liczba C jest nazywana
stałą asymptotyczną błędu.

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 2

Jeżeli z jedną iteracją związany jest koszt K to

K

p

E

1

=

nazywamy

wskaźnikiem efektywności metody.

Tw.
Jeżeli równaniem iteracji jest

)

x

(

x

i

i

Φ

=

+1

i dla k=1,..,p-1

0

=

Φ

)

a

(

)

k

(

,

to metoda jest rzędu p.
dow.

1

2

1

2

+

+

−

+

Φ

−

+

+

+

Φ

−

+

Φ

−

+

Φ

=

Φ

=

p

i

)

p

(

p

i

i

i

i

i

)

a

x

(

(

O

!

p

)

a

(

)

a

x

(

!

)

a

(

'

'

)

a

x

(

)

a

(

'

)

a

x

(

)

a

(

)

x

(

x

L

!

p

)

a

(

)

a

x

(

a

x

lim

)

p

(

p

i

i

i

Φ

=

−

−

+

∞

→

1

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 3

Metody iteracyjne rozwiązywania równań nieliniowych

Szukamy rzeczywistego pierwiastka równania

0

=

)

x

(

f

. Jeżeli jest nim

ξ

, a

i

x

jest przybliżeniem

ξ

(

i

x

leży w otoczeniu

ξ

), to

L

+

−

+

−

+

−

+

=

=

=

)

x

(

f

!

)

x

(

)

x

(

'

'

f

!

)

x

(

)

x

(

'

f

)

x

(

)

x

(

f

)

(

f

i

)

(

i

i

i

i

i

i

3

3

2

3

2

0

ξ

ξ

ξ

ξ

zaniedbując wyrazy rzędy większego niż

ν

otrzymujemy równanie do

wyznaczenia kolejnego przybliżenia

1

+

i

x

Dla

1

=

ν

(metoda Newtona-Raphsona stopnia I):

)

x

(

'

f

)

x

x

(

)

x

(

f

i

i

i

i

−

+

=

+1

0

)

x

(

'

f

)

x

(

f

x

x

i

i

i

i

−

=

+1

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 4

Dla

2

=

ν

(metoda Newtona-Raphsona stopnia II):

)

x

(

'

'

f

!

)

x

x

(

)

x

(

'

f

)

x

x

(

)

x

(

f

i

i

i

i

i

i

i

2

0

2

1

1

−

+

−

+

=

+

+

)

x

(

'

'

f

)

x

(

'

'

f

)

x

(

'

f

)

x

(

'

f

)

x

(

'

f

x

x

i

i

i

i

i

i

i

2

2

1

−

±

−

=

+

Zbieżność lokalna!
Rząd zbieżności metody N-R I dla jednokrotnego zera (

0

≠

)

(

'

f

ξ

):

)

x

(

'

f

)

x

(

f

x

)

x

(

),

x

(

x

i

i

−

=

Φ

Φ

=

+1

0

1

2

=













+

−

=

Φ

=

ξ

ξ

x

)

x

(

'

f

)

x

(

'

'

f

)

x

(

f

)

x

(

'

f

)

x

(

'

f

)

(

'

, czyli p=2

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 5

Rząd zbieżności metody N-R I dla m-krotnego zera
(

0

≠

−

=

)

(

g

),

x

(

g

)

x

(

)

x

(

f

m

ξ

ξ

):

),

x

(

'

g

)

x

(

)

x

(

g

)

x

(

m

)

x

(

'

f

m

m

1

1

−

−

−

+

−

=

ξ

ξ

,

)

x

(

'

g

)

x

(

)

x

(

g

)

x

(

m

)

x

(

g

)

x

(

x

)

x

(

m

m

m

1

1

−

−

−

+

−

−

−

=

Φ

ξ

ξ

ξ

m

)

(

'

1

1

−

=

Φ

ξ

, czyli p=1

m

C

1

1

−

=

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 6

Metoda siecznych

)

x

(

f

)

x

(

f

x

)

x

(

f

x

)

x

(

f

)

x

(

f

)

x

(

f

)

x

x

)(

x

(

f

x

)

x

(

'

f

)

x

(

f

x

x

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

1

1

1

1

1

1

−

−

−

−

−

+

−

−

=

−

−

−

≈

−

=

p=1.618..
Regula falsi
dane

0

<

)

a

(

f

)

x

(

f

,

a

,

x

i

i

i

i

obliczamy

,

)

a

(

f

)

x

(

f

)

a

(

f

x

)

x

(

f

a

i

i

i

i

i

i

i

−

−

=

µ

wybieramy

0

1

1

>

⇐







=

=

+

+

)

(

f

)

x

(

f

a

a

x

i

i

i

i

i

i

µ

µ

0

1

1

<

⇐







=

=

+

+

)

(

f

)

x

(

f

x

a

x

i

i

i

i

i

i

µ

µ

p=1

Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 6

W6 - 7

Układy równań nieliniowych

[

]

























⋅

⋅

⋅

=

⋅

=

=

=

=

)

(

f

)

(

f

)

(

f

)

(

F

,

x

,

,

x

,

x

X

,

)

X

(

F

n

,...,

i

,

)

x

,

,

x

,

x

(

f

n

T

n

n

i

M

L

L

2

1

2

1

2

1

0

1

0

Dla

1

=

ν

(metoda Newtona-Raphsona stopnia I):

)

X

X

)(

X

(

'

F

)

X

(

F

i

i

i

i

−

+

=

+1

0









































∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

=

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

X

F

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

(

'

1

2

1

1

1

1

2

2

1

2

1

1

2

1

1

2

1

1

1

1

1

L

L

L

L

M

M

M

M

L

L

L

L

L

L

L

L