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

۳۵۴۶ بازدید
آخرین به‌روزرسانی: ۲۴ خرداد ۱۴۰۲
زمان مطالعه: ۶ دقیقه
پیاده سازی روش نیوتون رافسون | راهنمای کاربردی

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

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

تابع 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

1// C++ program for implementation of Newton Raphson Method for 
2// solving equations 
3#include<bits/stdc++.h> 
4#define EPSILON 0.001 
5using namespace std; 
6  
7// An example function whose solution is determined using 
8// Bisection Method. The function is x^3 - x^2  + 2 
9double func(double x) 
10{ 
11    return x*x*x - x*x + 2; 
12} 
13  
14// Derivative of the above function which is 3*x^x - 2*x 
15double derivFunc(double x) 
16{ 
17    return 3*x*x - 2*x; 
18} 
19  
20// Function to find the root 
21void newtonRaphson(double x) 
22{ 
23    double h = func(x) / derivFunc(x); 
24    while (abs(h) >= EPSILON) 
25    { 
26        h = func(x)/derivFunc(x); 
27   
28        // x(i+1) = x(i) - f(x) / f'(x)   
29        x = x - h; 
30    } 
31  
32    cout << "The value of the root is : " << x; 
33} 
34  
35// Driver program to test above 
36int main() 
37{ 
38    double x0 = -20; // Initial values assumed 
39    newtonRaphson(x0); 
40    return 0; 
41} 

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

1// Java program for implementation of  
2// Newton Raphson Method for solving  
3// equations 
4class GFG { 
5      
6    static final double EPSILON = 0.001; 
7      
8    // An example function whose solution 
9    // is determined using Bisection Method. 
10    // The function is x^3 - x^2 + 2 
11    static double func(double x) 
12    { 
13        return x * x * x - x * x + 2; 
14    } 
15      
16    // Derivative of the above function  
17    // which is 3*x^x - 2*x 
18    static double derivFunc(double x) 
19    { 
20        return 3 * x * x - 2 * x; 
21    } 
22      
23    // Function to find the root 
24    static void newtonRaphson(double x) 
25    { 
26        double h = func(x) / derivFunc(x); 
27        while (Math.abs(h) >= EPSILON) 
28        { 
29            h = func(x) / derivFunc(x); 
30      
31            // x(i+1) = x(i) - f(x) / f'(x)  
32            x = x - h; 
33        } 
34      
35        System.out.print("The value of the"
36                + " root is : " 
37                + Math.round(x * 100.0) / 100.0); 
38    } 
39      
40    // Driver code 
41    public static void main (String[] args) 
42    { 
43          
44        // Initial values assumed 
45        double x0 = -20;  
46        newtonRaphson(x0); 
47    } 
48} 
49  
50// This code is contributed by Anant Agarwal. 

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

1# Python3 code for implementation of Newton 
2# Raphson Method for solving equations 
3  
4# An example function whose solution  
5# is determined using Bisection Method.  
6# The function is x^3 - x^2 + 2 
7def func( x ): 
8    return x * x * x - x * x + 2
9  
10# Derivative of the above function  
11# which is 3*x^x - 2*x 
12def derivFunc( x ): 
13    return 3 * x * x - 2 * x 
14  
15# Function to find the root 
16def newtonRaphson( x ): 
17    h = func(x) / derivFunc(x) 
18    while abs(h) >= 0.0001: 
19        h = func(x)/derivFunc(x) 
20          
21        # x(i+1) = x(i) - f(x) / f'(x) 
22        x = x - h 
23      
24    print("The value of the root is : ", 
25                             "%.4f"% x) 
26  
27# Driver program to test above 
28x0 = -20 # Initial values assumed 
29newtonRaphson(x0) 
30  
31# This code is contributed by "Sharad_Bhardwaj" 

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

1// C# program for implementation of  
2// Newton Raphson Method for solving  
3// equations 
4using System; 
5class GFG { 
6      
7    static double EPSILON = 0.001; 
8      
9    // An example function whose solution 
10    // is determined using Bisection Method. 
11    // The function is x^3 - x^2 + 2 
12    static double func(double x) 
13    { 
14        return x * x * x - x * x + 2; 
15    } 
16      
17    // Derivative of the above function  
18    // which is 3*x^x - 2*x 
19    static double derivFunc(double x) 
20    { 
21        return 3 * x * x - 2 * x; 
22    } 
23      
24    // Function to find the root 
25    static void newtonRaphson(double x) 
26    { 
27        double h = func(x) / derivFunc(x); 
28        while (Math.Abs(h) >= EPSILON) 
29        { 
30            h = func(x) / derivFunc(x); 
31      
32            // x(i+1) = x(i) - f(x) / f'(x)  
33            x = x - h; 
34        } 
35      
36        Console.Write("The value of the"
37                    + " root is : "
38                    + Math.Round(x * 100.0) / 100.0); 
39    } 
40      
41    // Driver code 
42    public static void Main () 
43    { 
44          
45        // Initial values assumed 
46        double x0 = -20;  
47        newtonRaphson(x0); 
48    } 
49} 
50  
51// This code is contributed by nitin mittal 

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

1<?php 
2// PHP program for implementation  
3// of Newton Raphson Method for  
4// solving equations 
5$EPSILON = 0.001; 
6  
7// An example function whose  
8// solution is determined  
9// using Bisection Method.  
10// The function is x^3 - x^2 + 2 
11function func($x) 
12{ 
13    return $x * $x * $x -  
14           $x * $x + 2; 
15} 
16  
17// Derivative of the above 
18// function which is 3*x^x - 2*x 
19function derivFunc($x) 
20{ 
21    return 3 * $x * 
22               $x - 2 * $x; 
23} 
24  
25// Function to  
26// find the root 
27function newtonRaphson($x) 
28{ 
29    global $EPSILON; 
30    $h = func($x) / derivFunc($x); 
31    while (abs($h) >= $EPSILON) 
32    { 
33        $h = func($x) / derivFunc($x); 
34  
35        // x(i+1) = x(i) -  
36        // f(x) / f'(x)  
37        $x = $x - $h; 
38    } 
39  
40    echo "The value of the ".  
41           "root is : " , $x; 
42} 
43  
44// Driver Code 
45$x0 = -20; // Initial values assumed 
46newtonRaphson($x0); 
47  
48// This code is contributed by ajit 
49?>

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

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
نظر شما چیست؟

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