Mrtoda Newtona - Raphsona wyznaczania miejsca zerowego wielomianu

[janusz55]

Metoda Newtona-Raphsona jest jedną z najczęściej stosowanych technik iteracyjnych do rozwiązywania równań głównie nieliniowych.

Metoda wykorzystuje styczną do krzywej.

Znajdujemy pierwsze przybliżenie \( x_{1} \) określone przez punkt, w którym linia styczna do funkcji \( f \) w punkcie \( (x_{0}, f(x_{0})) \) przecina oś \( Ox.\)

Wartość \( x_{1} \) jest znacznie bliższa pierwiastkowi \( \alpha \) niż pierwotna wartość \( x_{0}.\)

Jeśli \( x_{n+1} \) oznacza wartość uzyskaną w kolejnych iteracjach, to jest to punkt prostej stycznej do \( f \) w punkcie o współrzędnych \((x_{n}, f(x_{n)}),\)

Równanie iteracyjne wiążące kolejne wartości \( x_{n+1} \) i \( x_{n} \) ma postać:

\( x_{n+1} = x_{n} -\frac{f(x_{n})}{f'(x_{n})} , \ \ n\geq 0, \ \ f'(x_{n})\neq 0.\)

Można wykazać, że metoda ta jest zbieżna z wykładnikiem zbieżności rzędu \( p = 2 \) i jej błąd w \( (n+1) \) iteracji wynosi

\( e_{n+1} = -e^2_{n}\cdot \frac{f^{''}(\xi_{n})}{ 2f'(x_{n})}, \ \ \xi_{n} \in (x_{n}, \ \ \alpha).\)

Metoda Newtona - Raphsona w programie MATLAB

Kod: Zaznacz cały

function newton(f,df,x0,tol,n)
% Metoda Newtona rozwiązywania równania nieliniowego f(x)=0.
iter=0;
u=feval(f,x0);
v=feval(df,x0);
err=abs(u/v);
disp('______________________________________________')
disp(' iter x f(x) df(x) |xn+1-xn| ')
disp('______________________________________________')
fprintf('%2.0f %12.6f %12.6f %12.6f\n', iter, x0, u, v)
while (err>tol)&(iter<=n)&(v~=0)
x1=x0-u/v;
err=abs(x1-x0);
x0=x1;
u=feval(f,x0);
v=feval(df,x0);
iter=iter+1;
fprintf('%2.0f %12.6f %12.6f %12.6f %12.6f\n',iter,x0,u,v,err)
end
if (v==0)
disp('dzielenie przez zero')
end
if (iter>n)
disp(' Metoda nie jest zbieżna')
end

function f = f1(x)
f= x.^3 -6*x.^2 +12*x -26; 

function f = df1(x)
f = 3*x.^2 -12*x + 12;

Wyniki

Kod: Zaznacz cały

>> newton('f1','df1',3,10^(-4),40)
_________________________________________________________
 iter     x          f(x)        df(x)       |xn+1- xn| 
_________________________________________________________
 0     3.000000   -17.000000     3.000000
 1     8.666667   278.296296   133.333333     5.666667
 2     6.579444    78.036956    62.913934     2.087222
 3     5.339068    19.228525    33.448127     1.240376
 4     4.764192     3.120523    22.922274     0.574876
 5     4.628057     0.151161    20.720053     0.136135
 6     4.620762     0.000419    20.605176     0.007295
 7     4.620741     0.000000    20.604856     0.000020

[janusz55]

Jeśli za punkt początkowy przyjmiemy \( (x_{0}, 0) = (5, 0), \) to miejsce zerowe wielomianu otrzymamy już w czterech iteracjach

Kod: Zaznacz cały

newton('f1','df1',5,10^(-4),40)
_______________________________________________________
 iter     x             f(x)      df(x)       |xn+1-xn| 
_______________________________________________________
 0     5.000000     9.000000    27.000000
 1     4.666667     0.962963    21.333333     0.333333
 2     4.621528     0.016208    20.617224     0.045139
 3     4.620742     0.000005    20.604860     0.000786
 4     4.620741     0.000000    20.604856     0.000000
 

[janusz55]

Jeśli za punkt początkowy przyjmiemy \( (x_{0}, 0) = (5, 0), \) to miejsce zerowe wielomianu otrzymamy już w czterech iteracjach

Kod: Zaznacz cały

newton('f1','df1',5,10^(-4),40)
_______________________________________________________
 iter     x             f(x)      df(x)       |xn+1-xn| 
_______________________________________________________
 0     5.000000     9.000000    27.000000
 1     4.666667     0.962963    21.333333     0.333333
 2     4.621528     0.016208    20.617224     0.045139
 3     4.620742     0.000005    20.604860     0.000786
 4     4.620741     0.000000    20.604856     0.000000
 

[janusz55]

Metoda Newtona-Raphsona jest jedną z najczęściej stosowanych technik iteracyjnych do rozwiązywania równań głównie nieliniowych.

Metoda wykorzystuje styczną do krzywej.

Znajdujemy pierwsze przybliżenie \( x_{1} \) określone przez punkt, w którym linia styczna do funkcji \( f \) w punkcie \( (x_{0}, f(x_{0})) \) przecina oś \( Ox.\)

Wartość \( x_{1} \) jest znacznie bliższa pierwiastkowi \( \alpha \) niż pierwotna wartość \( x_{0}.\)

Jeśli \( x_{n+1} \) oznacza wartość uzyskaną w kolejnych iteracjach, to jest to punkt prostej stycznej do \( f \) w punkcie o współrzędnych \((x_{n}, f(x_{n)}),\)

Równanie iteracyjne wiążące kolejne wartości \( x_{n+1} \) i \( x_{n} \) ma postać:

\( x_{n+1} = x_{n} -\frac{f(x_{n})}{f'(x_{n})} , \ \ n\geq 0, \ \ f'(x_{n})\neq 0.\)

Można wykazać, że metoda ta jest zbieżna z wykładnikiem zbieżności rzędu \( p = 2 \) i jej błąd w \( (n+1) \) iteracji wynosi

\( e_{n+1} = -e^2_{n}\cdot \frac{f^{''}(\xi_{n})}{ 2f'(x_{n})}, \ \ \xi_{n} \in (x_{n}, \ \ \alpha).\)

Metoda Newtona - Raphsona w programie MATLAB

Kod: Zaznacz cały

function newton(f,df,x0,tol,n)
% Metoda Newtona rozwiązywania równania nieliniowego f(x)=0.
iter=0;
u=feval(f,x0);
v=feval(df,x0);
err=abs(u/v);
disp('______________________________________________')
disp(' iter x f(x) df(x) |xn+1-xn| ')
disp('______________________________________________')
fprintf('%2.0f %12.6f %12.6f %12.6f\n', iter, x0, u, v)
while (err>tol)&(iter<=n)&(v~=0)
x1=x0-u/v;
err=abs(x1-x0);
x0=x1;
u=feval(f,x0);
v=feval(df,x0);
iter=iter+1;
fprintf('%2.0f %12.6f %12.6f %12.6f %12.6f\n',iter,x0,u,v,err)
end
if (v==0)
disp('dzielenie przez zero')
end
if (iter>n)
disp(' Metoda nie jest zbieżna')
end

function f = f1(x)
f= x.^3 -6*x.^2 +12*x -26; 

function f = df1(x)
f = 3*x.^2 -12*x + 12;

Wyniki

Kod: Zaznacz cały

>> newton('f1','df1',3,10^(-4),40)
_________________________________________________________
 iter     x          f(x)        df(x)       |xn+1- xn| 
_________________________________________________________
 0     3.000000   -17.000000     3.000000
 1     8.666667   278.296296   133.333333     5.666667
 2     6.579444    78.036956    62.913934     2.087222
 3     5.339068    19.228525    33.448127     1.240376
 4     4.764192     3.120523    22.922274     0.574876
 5     4.628057     0.151161    20.720053     0.136135
 6     4.620762     0.000419    20.605176     0.007295
 7     4.620741     0.000000    20.604856     0.000020