برنامه پیدا کردن ریشه های تابع با روش دو بخشی — راهنمای کاربردی

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

در این مطلب، روش نوشتن برنامه پیدا کردن ریشه های تابع با روش دو بخشی بیان و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ پی» (PHP) انجام شده است. تابع f(x)‎ روی عدد ممیز شناور x و همچنین، دو عدد a و b داده شده است؛ به طوری که f(a)*f(b) < 0‎ و f(x)‎ در [a, b] پیوسته است. در اینجا، f(x)‎ نشانگر یک معادله جبری یا غیر جبری است. هدف، پیدا کردن ریشه در بازه [a, b] (یا پیدا کردن مقداری از x به طوری است که f(x) = 0) است. مثال زیر،‌ به درک بهتر این مطلب کمک می‌کند.

997696

ورودی: تابعی از x، مثلا x3 - x2 + 2 و دو مقدار a = -200 و b = 300 به گونه‌ای که f(a)*f(b) < 0 و f(a)‎ و f(b)‎ علامت‌های مخالف هم دارند.

خروجی: The value of root is : -1.0025 (یا هر مقدار ممکن دیگری با انحراف پذیرفته شده از ریشه).

ممکن است این پرسش برای برخی از افراد مطرح شود که توابع جبری و غیر جبری چه هستند؟ توابع جبری، توابعی محسوب می‌شوند که می‌توان آن‌ها را به صورت چند جمله‌ایی‌هایی مانند f(x) = a1x3 + a2x2 +‎ ….. + e نشان داد که در آن‌ها، aa1, a2, …‎ ثابت‌ها و x یک متغیر است. به عنوان مثال‌هایی از توابع غیر جبری، می‌توان به توابعی به صورت f(x) = sin(x)*x – 3 یا f(x) = ex + x2 یا f(x) = ln(x) + x ….‎ اشاره کرد.

روش دو بخشی چیست؟

این روش که آن را روش «تنصیف»، «نصف شدن فاصله» (Interval Halving Method) یا «دو بخشی» (Bisection Method) نیز می‌نامند، یک روش «جستجوی دودویی» (Binary Search Method) یا روش دوگانگی (Dichotomy Method) است. از این روش برای پیدا کردن ریشه یک معادله در بازه داده شده استفاده می‌شود. در واقع روش دو بخشی برای پیدا کردن مقدار x برای f(x) = 0 مورد استفاده قرار می‌گیرد.

این روش بر اساس «قضیه مقدار میانی» (The Intermediate Value Theorem) است. قضیه مقدار میانی بیان می‌کند که اگر f(x) ‎ یک تابع پیوسته باشد و دو عدد حقیقی a و b به طوری که f(a)*f(b) 0 و f(b) < 0 وجود داشته باشند، تضمین می‌شود که حداقل یک ریشه بین آن‌ها وجود داشته باشد.

فرضیات

  • f(x)‎ یک تابع پیوسته در بازه [a, b] است.
  • f(a) * f(b) < 0

گام‌ها

  1. هدف پیدا کردن نقطه میانی c= (a + b)/2 است.
  2. اگر f(c) == 0، بنابراین c ریشه و پاسخ مسئله است.
  3. در غیر این صورت، f(c) != 0
    1. اگر مقدار f(a)*f(c) < 0، بنابراین ریشه بین a و c خواهد بود. بنابراین، برای a و c نیز تکرار می‌شود.
    2. در غیر این صورت، اگر f(b)*f(c) < 0، ریشه بین b و c قرار دارد. بنابراین تکرار برای b و c انجام می‌شود.
    3. در غیر این صورت، تابع داده شده هیچ یک از مفروضات را دنبال نمی‌کند.
    4. از آنجا که ریشه ممکن است یک عدد ممیز شناور باشد، گام‌های بالا تا هنگامی که تفاوت بین a و b کمتر از یک مقدار (یک مقدار بسیار کوچک) باشد، تکرار می‌شوند.

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

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در ++C

1// C++ program for implementation of Bisection Method for 
2// solving equations 
3#include<bits/stdc++.h> 
4using namespace std; 
5#define EPSILON 0.01 
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// Prints root of func(x) with error of EPSILON 
15void bisection(double a, double b) 
16{ 
17    if (func(a) * func(b) >= 0) 
18    { 
19        cout << "You have not assumed right a and b\n"; 
20        return; 
21    } 
22  
23    double c = a; 
24    while ((b-a) >= EPSILON) 
25    { 
26        // Find middle point 
27        c = (a+b)/2; 
28  
29        // Check if middle point is root 
30        if (func(c) == 0.0) 
31            break; 
32  
33        // Decide the side to repeat the steps 
34        else if (func(c)*func(a) < 0) 
35            b = c; 
36        else
37            a = c; 
38    } 
39    cout << "The value of root is : " << c; 
40} 
41  
42// Driver program to test above function 
43int main() 
44{ 
45    // Initial values assumed 
46    double a =-200, b = 300; 
47    bisection(a, b); 
48    return 0; 
49}

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در جاوا

1// Java program for implementation of Bisection Method  
2// for solving equations 
3class GFG{ 
4    static final float EPSILON = (float)0.01; 
5  
6    // An example function whose solution is determined using 
7    // Bisection Method. The function is x^3 - x^2  + 2 
8    static double func(double x) 
9    { 
10        return x*x*x - x*x + 2; 
11    } 
12  
13    // Prints root of func(x) with error of EPSILON 
14    static void bisection(double a, double b) 
15    { 
16        if (func(a) * func(b) >= 0) 
17        { 
18            System.out.println("You have not assumed"
19                        + " right a and b"); 
20            return; 
21        } 
22  
23        double c = a; 
24        while ((b-a) >= EPSILON) 
25        { 
26            // Find middle point 
27            c = (a+b)/2; 
28  
29            // Check if middle point is root 
30            if (func(c) == 0.0) 
31                break; 
32  
33            // Decide the side to repeat the steps 
34            else if (func(c)*func(a) < 0) 
35                b = c; 
36            else
37                a = c; 
38        } 
39                //prints value of c upto 4 decimal places 
40        System.out.printf("The value of root is : %.4f"
41                        ,c); 
42    } 
43  
44    // Driver program to test above function 
45    public static void main(String[] args) 
46    { 
47        // Initial values assumed 
48        double a =-200, b = 300; 
49        bisection(a, b); 
50    } 
51    // This code is contributed by Nirmal Patel 
52}

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در پایتون

1# Python program for implementation 
2# of Bisection Method for 
3# solving equations 
4  
5   
6# An example function whose 
7# solution is determined using 
8# Bisection Method. 
9# The function is x^3 - x^2  + 2 
10def func(x): 
11    return x*x*x - x*x + 2
12   
13# Prints root of func(x) 
14# with error of EPSILON 
15def bisection(a,b): 
16  
17    if (func(a) * func(b) >= 0): 
18        print("You have not assumed right a and b\n") 
19        return
20   
21    c = a 
22    while ((b-a) >= 0.01): 
23  
24        # Find middle point 
25        c = (a+b)/2
26   
27        # Check if middle point is root 
28        if (func(c) == 0.0): 
29            break
30   
31        # Decide the side to repeat the steps 
32        if (func(c)*func(a) < 0): 
33            b = c 
34        else: 
35            a = c 
36              
37    print("The value of root is : ","%.4f"%c) 
38      
39# Driver code 
40# Initial values assumed 
41a =-200
42b = 300
43bisection(a, b) 
44  
45# This code is contributed 
46# by Anant Agarwal.

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در #C

1// C# program for implementation  
2// of Bisection Method for  
3// solving equations 
4using System; 
5  
6class GFG 
7{ 
8static float EPSILON = (float)0.01; 
9  
10// An example function whose  
11// solution is determined using 
12// Bisection Method. The function 
13// is x^3 - x^2 + 2 
14static double func(double x) 
15{ 
16    return x * x * x -  
17           x * x + 2; 
18} 
19  
20// Prints root of func(x)  
21// with error of EPSILON 
22static void bisection(double a,  
23                      double b) 
24{ 
25    if (func(a) * func(b) >= 0) 
26    { 
27        Console.WriteLine("You have not assumed" +  
28                                " right a and b"); 
29        return; 
30    } 
31  
32    double c = a; 
33    while ((b - a) >= EPSILON) 
34    { 
35        // Find middle point 
36        c = (a + b) / 2; 
37  
38        // Check if middle  
39        // point is root 
40        if (func(c) == 0.0) 
41            break; 
42  
43        // Decide the side  
44        // to repeat the steps 
45        else if (func(c) * func(a) < 0) 
46            b = c; 
47        else
48            a = c; 
49    } 
50      
51    // prints value of c  
52    // upto 4 decimal places 
53    Console.WriteLine("The value of " +  
54                      "root is : "+ c); 
55} 
56  
57// Driver Code 
58static public void Main () 
59{ 
60    // Initial values assumed 
61    double a = -200, b = 300; 
62    bisection(a, b); 
63} 
64} 
65  
66// This code is contributed by ajit 

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در PHP

1<?php 
2// PHP program for implementation  
3// of Bisection Method for solving 
4// equations 
5$EPSILON = 0.01; 
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// Prints root of func(x) 
18// with error of EPSILON 
19function bisection($a, $b) 
20{ 
21    global $EPSILON; 
22    if (func($a) *  
23        func($b) >= 0) 
24    { 
25        echo "You have not assumed " .  
26                 "right a and b","\n"; 
27        return; 
28    } 
29  
30    $c = $a; 
31    while (($b - $a) >= $EPSILON) 
32    { 
33        // Find middle point 
34        $c = ($a + $b) / 2; 
35  
36        // Check if middle  
37        // point is root 
38        if (func($c) == 0.0) 
39            break; 
40  
41        // Decide the side to 
42        // repeat the steps 
43        else if (func($c) * func($a) < 0) 
44            $b = $c; 
45        else
46            $a = $c; 
47    } 
48    echo "The value of root is : " , $c; 
49} 
50  
51// Driver Code 
52  
53// Initial values assumed 
54$a =-200; 
55$b = 300; 
56bisection($a, $b); 
57  
58// This code is contributed by ajit 
59?>

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

The value of root is : -1.0025

پیچیدگی زمانی این روش بستگی به مقادیر مفروض و خود تابع دارد.

مزایا و معایب روش دوبخشی

مزیت روش دوبخشی در آن است که این روش تضمین می‌کند که همگرا شود. عیب اصلی این روش آن است که نمی‌تواند چندین ریشه را پیدا کند. به طور کلی، روش دو بخشی برای به دست آوردن یک تخمین خام از راهکار، مورد استفاده قرار می‌گیرد. روش‌هایی که سریع‌تر همگرا می‌شوند، برای پیدا کردن جواب‌ها مورد استفاده قرار می‌گیرند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

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