Nyuton üsulu

Nyuton üsulu (həmçinin Nyuton-Rafson üsulu) — riyazi analizdə İsaak Nyuton və Cozef Rafsonun adına adlandırılmış, real dəyərə malik funksiyaların köklərinin ardıcıl olaraq daha yaxşı həllini tapmaq üsulu. Bu, kökün tapılması alqoritmlərindən biridir.

Nyuton üsulunun bir dəyişənlə tətbiqi aşağıdakı kimidir:

Bu üsul x dəyişəni olan f funksiyası, həmin funksiyanın f ′ törəməsi və f funksiyasının kökü kimi ilkin x₀ fərziyyəsi ilə başlayır. Əgər bu funksiya formulanın törəməsindəki fərziyyələri qane edirsə və ilkin fərz edilən həll yaxındırsa, o zaman x₁ daha yaxşı təxmini həll tapmaq üçün

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,.$

istifadə edilir.

Həndəsi olaraq, (x₁, 0), (x₀, f (x₀))-də f funksiyasının x oxu ilə kəsişməsidir

Bu proses daha dəqiq həll tapılana kimi aşağıdakı kimi davam etdirilir:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,$

Təsviri

İkinci tərtib törəmənin köməyi ilə minimumun axtarılması üsullarına iki tərtibli üsullar deyilir. Bu üsullarda funksiyanın Teylor sırasına ayrılışında kvadratik hissədən istifadə edilir. Nyuton üsulu da məhz ikinci tərtib üsullara, yəni minimallaşdırılan funksiyanın ikinci tərtib törəmələrindən istifadə edilən üsullara aiddir. Bu üsulda da məqsəd funksiyanın Teylor ayrılışının kvadratik hissəsindən istifadə etməkdir. Teylor ayrılışının kvadratik hissəsi funksiyanı bu ayrılışın xətti hissəsinə nisbətən daha dəqiq approksimasiya etdiyindən gözləmək olar ki, ikinci tərtib üsullar birinci tərtib üsullara nisbətən daha sürətlə yığılır. Tətbiqi məsələlərin həlli göstərir ki, Nyuton üsulu çox sürətlə yığılır.

Nümunə

Ədədin kvadrat kökünün tapılması məsələsinə baxaq. Nyuton üsulu kvadrat kökün tapılması üsullarından biridir.

Məsələn, əgər 612-nin kökünü tapmaq istəyiriksə, o zaman bu məsələ belə yazıla bilər

$x^{2}=612$

Nyuton üsulu ilə funksiyanın yazılışı belədir

$f(x)=x^{2}-612$

və onun törəməsi

$f'(x)=2x.\,$

İlkin fərziyyə kimi 10 ədədini götürsək, Nyuton üsulu ilə hesablama ardıcıllığı belə olacaq

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}$

burada düzgün onluq kəsr ədədlərinin altından xətt çəkilib. Bir neçə təkrarlamadan sonra nəticənin dəqiqliyi də artır.

Proqramlaşdırılması

Python

''' funksiyanın test edilməsi

def f(x):
    return x**2 - 17

def f1(x):
    return 2*x

'''

def newtons_method(x0, f, f1, e):
    #f1 - törəmə
    x0 = float(x0)
    while True:
        x1 = x0 - (f(x0) / f1(x0))
        if abs(x1 - x0) < e:
            return x1
        x0 = x1

PHP

<?php
// PHP 5.4
function newtons_method(
	$a = -1, $b = 1, 
	$f = function($x) {
	
		return pow($x, 4) - 1;
	
	},
	$derivative_f = function($x) {

		return 4 * pow($x, 3);
	
	}, $eps = 1E-3) {

        $xa = $a;
        $xb = $b;

        $iteration = 0;

        while (abs($xb) > $eps) {

            $p1 = $f($xa);
            $q1 = $derivative_f($xa);
            $xa -= $p1 / $q1;
            $xb = $p1;
            ++$iteration;

        }

        return $xa;

}

Octave

function res = nt()
eps = 1e-7;
x0_1 = [-0.5,0.5];
max_iter = 500;
xopt = new(@resh, eps, max_iter);   
xopt
endfunction
function a = new(f, eps, max_iter)
x=-1;
p0=1;
i=0;
 while (abs(p0)>=eps)
[p1,q1]=f(x);
 x=x-p1/q1;
p0=p1;
 i=i+1;
 end
 i
 a=x;
endfunction
function[p,q]= resh(x)   % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1;
   p=-25*x.^4+16*x.^3-36*x.^2+22*x-2;
   q=-100*x.^3+48*x.^2-72*x+22;
endfunction

С

#include <stdio.h>
#include <math.h>

#define eps 0.000001
double fx(double x) { return x*x-17;} // hesablanan funksiya
double dfx(double x) { return 2*x;} // törəmə funksiya

typedef double(*function)(double x); // tapşırıq tipi function

double solve(function fx, function dfx, double x0) {
  double x1  = x0 - fx(x0)/dfx(x0); // birinci approksimasiya
  while (fabs(x1-x0)>eps) { // 0.000001 dəqiqliyinə çatana kimi
    x0 = x1;
    x1 = x1 - fx(x1)/dfx(x1); // növbəti approksimasiya
  }
  return x1;
}

int main () {
  printf("%f\n",solve(fx,dfx,4)); // ekrana verilməsi
  return 0;
}

C++

typedef double (*function)(double x);

double TangentsMethod(function f, function df, double xn, double eps) {
   double x1  = xn - f(xn)/df(xn);
   double x0 = xn;
   while(abs(x0-x1) > eps) {
      x0 = x1;
      x1 = x1 - f(x1)/df(x1);
   }
   return x1;
}

//İlkin appoksimasiya seçimi
xn = MyFunction(A)*My2Derivative(A) > 0 ? B : A;

double MyFunction(double x) { return (pow(x, 5) - x - 0.2); } //Sizin funksiya
double MyDerivative(double x) { return (5*pow(x, 4) - 1); } //Birinci dərəcəli törəmə
double My2Derivative(double x) { return (20*pow(x, 3)); } //İkinci dərəcəli törəmə

//Funksiyanın çağrılması nümunəsi
double x = TangentsMethod(MyFunction, MyDerivative, xn, 0.1)

Xarici keçidlər

• Weisstein, Eric W. Newton's Method (ing.) Wolfram MathWorld saytında.
• Newton's method, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Roots of Equations, Course notes.