پیاده سازی روش نیوتون رافسون | راهنمای کاربردی

۱۹۷۹ بازدید
آخرین به‌روزرسانی: ۲۴ خرداد ۱۴۰۲
زمان مطالعه: ۶ دقیقه

در این مطلب، پیاده سازی روش نیوتون رافسون در زبان‌های برنامه‌نویسی گوناگون همراه با ارائه کدهای کامل، انجام شده است.

پیاده سازی روش نیوتون رافسون

تابع f(x)‎ روی یک نقطه ممیز شناور x و یک حدس اولیه برای ریشه آن داده شده است. هدف پیدا کردن ریشه تابع در بازه است. در اینجا، f(x)‎ نشانگر یک معادله جبری یا غیر جبری است. برای سادگی بیشتر، فرض می‌شود که مشتق تابع نیز به عنوان ورودی داده شده است.

مثال زیر به درک بهتر این مسئله کمک شایان توجهی می‌کند.

Input: A function of x (for example x3 – x2 + 2),
       derivative function of x (3x2 – 2x for above example)
       and an initial guess x0 = -20
Output: The value of root is : -1.00
        OR any other value close to root.

در ادامه، روش نیوتون رافسون با «روش دو بخشی» (Bisection Method) و «روش نابجایی» (The Method Of False Position) مقایسه شده است.

  • در روش‌های دوبخشی و نابجایی، یک بازه داده می‌شد. در اینجا، تنها یک حدس اولیه از مقدار ریشه ارائه می‌شود.
  • همگرا شدن در دو روش مذکور، تضمین شده است؛ اما روش نیوتون رافسون ممکن است در برخی از حالات همگرا نشود.
  • روش نیوتون رافسون نیازمند مشتق است. این در حالی است که مشتق‌گیری از برخی توابع، بسیار دشوار و یا غیر ممکن است.
  • در بسیاری از مسائل، روش نیوتون رافسون سریع‌تر از دو روش دیگر بیان شده، همگرا می‌شود.
  • روش نیوتون رافسون می‌تواند ریشه‌های تکرار شده را تشخیص دهد، زیرا صراحتاً به دنبال تغییرات در علامت f(x)‎ نیست.

فرمول

با شروع از حدس اولیه x1، روش نیوتون رافسون از رابطه زیر برای پیدا کردن مقدار بعدی x، یعنی xn+1 از مقدار پیشین xn استفاده می‌کند.

پیاده سازی روش نیوتون رافسون -- راهنمای کاربردی

الگوریتم

ورودی: مقدار اولیه x، تابع func(x)‎، مشتق تابع derivFunc(x)‎

خروجی: ریشه تابع Func()‎

  1. محاسبه مقادیر func(x)‎ و derivFunc(x)‎ برای مقدار اولیه x
  2. محاسبه h: h = func(x) / derivFunc(x)‎
  3. تا هنگامی که h، بزرگ‌تر از خطای پذیرفته ε است
    1. h = func(x) / derivFunc(x)‎
    2. x = x – h

در ادامه، پیاده‌سازی روش نیوتون رافسون در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

پیاده سازی روش نیوتون رافسون در ++C

// C++ program for implementation of Newton Raphson Method for 
// solving equations 
#include<bits/stdc++.h> 
#define EPSILON 0.001 
using namespace std; 
  
// An example function whose solution is determined using 
// Bisection Method. The function is x^3 - x^2  + 2 
double func(double x) 
{ 
    return x*x*x - x*x + 2; 
} 
  
// Derivative of the above function which is 3*x^x - 2*x 
double derivFunc(double x) 
{ 
    return 3*x*x - 2*x; 
} 
  
// Function to find the root 
void newtonRaphson(double x) 
{ 
    double h = func(x) / derivFunc(x); 
    while (abs(h) >= EPSILON) 
    { 
        h = func(x)/derivFunc(x); 
   
        // x(i+1) = x(i) - f(x) / f'(x)   
        x = x - h; 
    } 
  
    cout << "The value of the root is : " << x; 
} 
  
// Driver program to test above 
int main() 
{ 
    double x0 = -20; // Initial values assumed 
    newtonRaphson(x0); 
    return 0; 
} 

پیاده سازی روش نیوتون رافسون در جاوا

// Java program for implementation of  
// Newton Raphson Method for solving  
// equations 
class GFG { 
      
    static final double EPSILON = 0.001; 
      
    // An example function whose solution 
    // is determined using Bisection Method. 
    // The function is x^3 - x^2 + 2 
    static double func(double x) 
    { 
        return x * x * x - x * x + 2; 
    } 
      
    // Derivative of the above function  
    // which is 3*x^x - 2*x 
    static double derivFunc(double x) 
    { 
        return 3 * x * x - 2 * x; 
    } 
      
    // Function to find the root 
    static void newtonRaphson(double x) 
    { 
        double h = func(x) / derivFunc(x); 
        while (Math.abs(h) >= EPSILON) 
        { 
            h = func(x) / derivFunc(x); 
      
            // x(i+1) = x(i) - f(x) / f'(x)  
            x = x - h; 
        } 
      
        System.out.print("The value of the"
                + " root is : " 
                + Math.round(x * 100.0) / 100.0); 
    } 
      
    // Driver code 
    public static void main (String[] args) 
    { 
          
        // Initial values assumed 
        double x0 = -20;  
        newtonRaphson(x0); 
    } 
} 
  
// This code is contributed by Anant Agarwal. 

پیاده سازی روش نیوتون رافسون در پایتون

# Python3 code for implementation of Newton 
# Raphson Method for solving equations 
  
# An example function whose solution  
# is determined using Bisection Method.  
# The function is x^3 - x^2 + 2 
def func( x ): 
    return x * x * x - x * x + 2
  
# Derivative of the above function  
# which is 3*x^x - 2*x 
def derivFunc( x ): 
    return 3 * x * x - 2 * x 
  
# Function to find the root 
def newtonRaphson( x ): 
    h = func(x) / derivFunc(x) 
    while abs(h) >= 0.0001: 
        h = func(x)/derivFunc(x) 
          
        # x(i+1) = x(i) - f(x) / f'(x) 
        x = x - h 
      
    print("The value of the root is : ", 
                             "%.4f"% x) 
  
# Driver program to test above 
x0 = -20 # Initial values assumed 
newtonRaphson(x0) 
  
# This code is contributed by "Sharad_Bhardwaj" 

پیاده سازی روش نیوتون رافسون در #C

// C# program for implementation of  
// Newton Raphson Method for solving  
// equations 
using System; 
class GFG { 
      
    static double EPSILON = 0.001; 
      
    // An example function whose solution 
    // is determined using Bisection Method. 
    // The function is x^3 - x^2 + 2 
    static double func(double x) 
    { 
        return x * x * x - x * x + 2; 
    } 
      
    // Derivative of the above function  
    // which is 3*x^x - 2*x 
    static double derivFunc(double x) 
    { 
        return 3 * x * x - 2 * x; 
    } 
      
    // Function to find the root 
    static void newtonRaphson(double x) 
    { 
        double h = func(x) / derivFunc(x); 
        while (Math.Abs(h) >= EPSILON) 
        { 
            h = func(x) / derivFunc(x); 
      
            // x(i+1) = x(i) - f(x) / f'(x)  
            x = x - h; 
        } 
      
        Console.Write("The value of the"
                    + " root is : "
                    + Math.Round(x * 100.0) / 100.0); 
    } 
      
    // Driver code 
    public static void Main () 
    { 
          
        // Initial values assumed 
        double x0 = -20;  
        newtonRaphson(x0); 
    } 
} 
  
// This code is contributed by nitin mittal 

پیاده سازی روش نیوتون رافسون در PHP

<?php 
// PHP program for implementation  
// of Newton Raphson Method for  
// solving equations 
$EPSILON = 0.001; 
  
// An example function whose  
// solution is determined  
// using Bisection Method.  
// The function is x^3 - x^2 + 2 
function func($x) 
{ 
    return $x * $x * $x -  
           $x * $x + 2; 
} 
  
// Derivative of the above 
// function which is 3*x^x - 2*x 
function derivFunc($x) 
{ 
    return 3 * $x * 
               $x - 2 * $x; 
} 
  
// Function to  
// find the root 
function newtonRaphson($x) 
{ 
    global $EPSILON; 
    $h = func($x) / derivFunc($x); 
    while (abs($h) >= $EPSILON) 
    { 
        $h = func($x) / derivFunc($x); 
  
        // x(i+1) = x(i) -  
        // f(x) / f'(x)  
        $x = $x - $h; 
    } 
  
    echo "The value of the ".  
           "root is : " , $x; 
} 
  
// Driver Code 
$x0 = -20; // Initial values assumed 
newtonRaphson($x0); 
  
// This code is contributed by ajit 
?>

خروجی قطعه کدهای بالا به صورت زیر است.

The value of root is : -1.00

روش کار برنامه‌های ارائه شده در بالا

ایده کلی آن است که یک خط مماس بر f(x)‎ در نقطه x1 ترسیم شود. نقطه‌ای که خط مماس از محور x عبور می‌کند، باید تخمین بهتری از ریشه نسبت به x1 ارائه کند. این نقطه، x2 نامیده می‌شود.

f(x2)‎ محاسبه و یک خط مماس در x2 ترسیم می‌شود.

پیاده سازی روش نیوتون رافسون -- راهنمای کاربردی

می‌دانیم که شیب خط از (x1, f(x1))‎ به (x2, 0) برابر با f'(x1))‎ است و در آن، f’‎ نشانگر مشتق f است.

f'(x1) = (0 - f(x1)) / (x2 - x1) 

f'(x1) *  (x2 - x1) =  - f(x1)

x2 =  x1 - f(x1) / f'(x1)

با پیدا کردن این نقطه x2، حرکت به سمت نزدیک‌تر به ریشه، انجام می‌شود. گام بالا باید تا جایی ادامه پیدا کند که به ریشه بسیار نزدیک باشیم یا آن را پیدا کنیم. به طور کلی، داریم:

xn+1 =  xn - f(xn) / f'(xn)

این روش را می‌توان با استفاده از سری تیلور نیز توضیح داد. فرض می‌شود که x1 حدس اولیه است. می‌توان x2 را به صورت زیر نوشت.

xn+1 = xn + h ------- (1)

در اینجا، h یک مقدار کوچک است که می‌تواند مثبت یا منفی باشد. مطابق با سری تیلور داریم:

ƒ(x)‎ که تا بی‌نهایت مشتق‌پذیر است را می‌توان به صورت زیر نوشت.

f(xn+1) = f(xn + h) = f(xn) + h*f'(xn) + ((h*h)/2!)*(f''(xn)) + ...

با توجه به اینکه هدف پیدا کردن ریشه است، داریم f(xn+1) = 0.

f(xn) + h*f'(xn) + ((h*h)/2!)*(f''(xn)) + ... = 0

اکنون، با توجه به اینکه h کوچک است، h*h بسیار کوچک خواهد بود. بنابراین، اگر عبارت‌های مرتبه بالاتر نادیده گرفته شوند، داریم:

f(xn) + h*f'(xn) = 0

با جایگزینی مقدار h = xn+1 - xn از معادله ۱، داریم:

f(xn) + (xn+1 - xn)*f'(xn) = 0

xn+1 = xn - f(xn) / f'(xn)

نکته:

  • معمولا از این روش برای بهبود نتایج به دست آمده توسط روش دوبخشی یا روش نابجایی، استفاده می‌شود.
  • «روش بابلی» (Babylonian Method) برای ریشه دوم از روش نیوتون رافسون مشتق شده است.
بر اساس رای ۸ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *