Metoda Newtona-Raphsona metoda rozwiązywania układu równań nieliniowych 1
Dany jest układ n równań algebraicznych, z których co najmniej jedno jest równaniem nieliniowym
f x x L x
1 (
,
,
,
1
2
n ) = 0
f x x L x
2 (
,
,
,
1
2
n )
= 0
− f x x L x
gdzie
n (
− − − − − − −
,
,
,
1
2
n )
− − −
= 0
f (⋅): n
L
L
R ∋ x =
→
x ∈ R
=
i
( x , x , , x
f
i
n
1
2
n )
i (
)
,
,
1 ,
2
, ,
Funkcje f (·) są funkcjami dwukrotnie róŜniczkowalnymi W zapisie wektorowym:
f ( x) = 0
gdzie
n
x = R
i
f ( )
n
⋅ : R ∋ x → y = f ( x) n
∈R
2
Rozwiązanie składa się z dwóch etapów:
- linearyzacji,
- rozwiązywania układu równań liniowych.
n
Dla kaŜdej z funkcji
f
:
wykonujemy rozwinięcie w otoczeniu i (⋅) R
∋ x → R
zadanego punktu
x
,
,L
=
,
zgodnie ze wzorem Taylora
0
( x x
x
,
1 0
2, 0
n, 0 ) T
( )
( )
( )
( )
f
L
L
=
+
i ( x , x ,
, x
f x
x
x
1
2
n )
i (
,
,
,
,
1 0
2, 0
n, 0 )
( )
( )
( )
f
∂
∂
i
+
⋅(
f
x − x
i
+
⋅ x − x
L
+ +
1
,
1 0 )
( 2 2, 0 )
( )
( )
x
∂
x
∂
1 x= x(
x=
0 )
2
x(0)
f
∂ i
+
⋅( x − x
+ R
i
L
=
n
n
n, 0 )
( )
,
,
1 ,
2
, .
x
i
∂ n x= x(0) 3
Składnik R jest resztą zawierającą czynniki ( x − x 2 ,
,
1 ,
2 L
=
,
j
j , 0 )
i
( )
j
n
Niech J f ( x) oznacza macierz Jacobiego funkcji f (·), wyznaczoną w punkcie x
∂ f 1( x) ∂ f 1( x)
∂ f 1( x)
L
∂ x 1
∂ x 2
∂ xn
∂ f 2 ( x) ∂ f 2 ( x)
∂ f 2( x)
L
def
x
x
x
J
1
2
f ( x )
∂
∂
∂
=
n
M
M
M
M
∂ f
f
f
n ( x )
∂ n( x)
∂ n ( x)
L
∂ x 1
∂ x 2
∂ xn
4
Rozwinięcie w szereg Taylora moŜna przedstawić w zapisie wektorowym
f
x
x
x
x
1 (
) f 1( 0 )
∂ f 1( )
∂ f 1( )
( )
L
x 1 − x ,1(0) R
1
x
x
f x
x
2 (
)
f 2 ( 0 )
∂ 1
∂
( )
n
x 2 − x 2,(0) R2
=
+ M
M
⋅
+
M
M
M
M
∂
f x
f x
n (
)
∂ n( )
L
f x
f x
x
x
R
n (
) n( 0 )
( )
∂ x 1
∂ x
n − n,(0) n
n
W uproszczonym zapisie
f ( x) = f ( x 0 )+ J f ( x 0 )⋅( x − x
+ R x, x
0 )
( 0 )
( )
( )
( )
( )
gdzie
( x −
=
−
,
−
, L
x
,
−
0 )
( x x x x
x
x
1
,
1 0
2
2, 0
n
n, 0 ) T
( )
( )
( )
( )
5
R ( x, x
≅
0 )
( )
0
Funkcje f (·)
f ( x) ≅ f ( x
+ J x
f
⋅ x − x
0 )
( 0 ) (
0 )
( )
( )
( )
Pierwsze przybliŜenie moŜna obliczyć przyjmując, Ŝe
f ( x
J
x
x
x
0 )+
f (
0 )⋅ (
− 0 )
( )
( )
( ) = 0
x(1)
x − x
= − J - 1 x
f
⋅ f x
0
( 0 ) ( 0 )
a po przekształceniu
( )
( )
( )
(det J f ( x ≠
0 )
0)
przy załoŜeniu, Ŝe
( )
x
-
1 = x
− J 1 x
f
⋅ f x
0
( 0 ) ( 0 )
mamy
( )
( )
( )
( )
6
x(
pierwszego przybliŜenia zostaje uznany za wystarczająco 1)
dobre przybliŜenie rozwiązania układu równań, jeŜeli:
f ( x
x
x
1 −
0
<
1 )
( )
< δ
( )
( )
ε
gdzie: δ i ε są zadanymi liczbami dodatnimi określającymi wymaganą dokładność wyznaczania pierwiastka JeŜeli spełniony jest jeden z ww. warunków kończymy obliczenia, jeŜeli nie, to liczymy dalej
Rozwijamy funkcje f (·) w szereg Taylora w otoczeniu punktu x(1) 7
+ J x
f
⋅ x − x
1 )
( 1 ) (
1 )
Otrzymujemy
( )
( )
( )
( )
Jak poprzednio przyjmujemy
f ( x
J
x
x
x
1 )+
f (
1 )⋅ (
− 1 )
( )
( )
( ) = 0
Przy załoŜeniu, Ŝe macierz J
jest nieosobliwa, mamy
f ( x 1 )
( )
-1
x − x
= − J x
f
⋅ f x
1
( 1 ) ( 1 )
( )
( )
( )
i następnie
-1
x
= x − J x
f
⋅ f x
2
1
( 1 ) ( 1 )
( )
( )
( )
( )
Akceptujemy rozwiązanie, jeŜeli
f ( x
x(
x
2) −
(1) < ε
2 )
( ) < δ
JeŜeli nie, to kontynuujemy obliczenia 8
Wzór rekurencyjny dla algorytmu Newtona-Raphsona naleŜy zapisać jako: n
x(
R
0)
∈
,
1
-
x
x
J
x
f x
k +1 =
k
− f ( k )⋅ ( k )
( )
( )
( )
( ) ,
k =
L
,
1
,
0
,
2
Zwykle w czasie obliczeń stosuje się wygodniejszy algorytm: n
x(
R
0)
∈
,
J
x
x
x
f x
f (
k )⋅ (
k +1 −
k ) = −
( k )
( )
( )
( )
( ) ,
k =
L
,
1
,
0
,
2
9
f ( x
x
x
k +1 −
k
<
k +1 )
( ) < δ
( )
( )
ε
Wektor
x( k 1+)
jest przybliŜonym rozwiązaniem układu równań Macierz Jacobiego trzeba wyznaczać w kaŜdym kolejnym kroku k + 1 iteracji Algorytm uproszczony – macierz Jacobiego jest wyznaczana co pewną liczbę kroków.
10
2
2
x + y − 2 = 0
2 x + y − 3 = 0
11