پیاده سازی روش نیوتون رافسون | راهنمای کاربردی
در این مطلب، پیاده سازی روش نیوتون رافسون در زبانهای برنامهنویسی گوناگون همراه با ارائه کدهای کامل، انجام شده است.
پیاده سازی روش نیوتون رافسون
تابع 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()
- محاسبه مقادیر func(x) و derivFunc(x) برای مقدار اولیه x
- محاسبه h: h = func(x) / derivFunc(x)
- تا هنگامی که h، بزرگتر از خطای پذیرفته ε است
- h = func(x) / derivFunc(x)
- 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) برای ریشه دوم از روش نیوتون رافسون مشتق شده است.