روش دو بخشی — به زبان ساده (+ دانلود فیلم آموزش گام به گام)

۵۳۳۵ بازدید
آخرین به‌روزرسانی: ۱۷ اردیبهشت ۱۴۰۲
زمان مطالعه: ۴۲ دقیقه
روش دو بخشی — به زبان ساده (+ دانلود فیلم آموزش گام به گام)

ساده‌ترین الگوریتم یافتن ریشه معادلات روش دو بخشی یا تنصیف (Bisection Method) است. این الگوریتم را می‌توان بر هر تابع پیوسته $$ f ( x ) $$ در بازه $$ [a,b] $$ اعمال کرد که علامت مقدار تابع $$ f ( x ) $$ از $$ a $$ تا $$ b$$ تغییر می‌کند. فرایند روش دو بخشی ساده است: بازه به دو قسمت تقسیم می‌کنیم و یک جواب باید در یک زیربازه وجود داشته باشد که در آن، علامت $$ f(x)$$ تغییر می‌کند. روند مذکور را تکرار می‌کنیم.

محتوای این مطلب جهت یادگیری بهتر و سریع‌تر آن، در انتهای متن به صورت ویدیویی نیز ارائه شده است.

الگوریتم روش دو بخشی

فرایند روش دو بخشی به صورت زیر است:

  1. بازه شروع $$ [a_0,b_0] $$ را انتخاب کنید، به گونه‌ای که $$ f(a_0)f(b_0) < 0 $$.
  2. نقطه میانی $$ f(m_0) $$ که $$ m_0 = (a_0+b_0)/2 $$ را محاسبه کنید.

  1. زیربازه $$ [a_1,b_1] $$ را تعیین کنید:
    1. اگر $$ f(a_0)f(m_0) < 0 $$، آنگاه $$ [a_1,b_1] $$ به عنوان بازه بعدی در نظر گرفته می‌شود که در آن، $$ a_1=a_0 $$ و $$ b_1=m_0 $$.
    2. اگر $$ f(b_0)f(m_0) < 0 $$، آنگاه $$ [a_1,b_1] $$ به عنوان بازه بعدی در نظر گرفته می‌شود که در آن، $$ a_1=m_0 $$ و $$ b_1=b_0 $$.
  2. مراحل ۲ و ۳ را تا زمانی که طول بازه $$ [a_N,b_N] $$ به یک مقدار از پیش تعیین شده برسد، تکرار کنید.
  3. نقطه میانی $$ m_N=(a_N+b_N)/2 $$ را محاسبه کنید.

طبق قضیه مقدار میانی، یک جواب برای معادله $$ f(x)=0 $$ در بازه $$ [a,b] $$ تضمین شده است که $$ f ( x)$$ در بازه $$ [a,b] $$ پیوسته بوده و $$ f(a)f(b) < 0 $$. به عبارت دیگر، علامت تابع در بازه مذکور تغییر کرده و در نتیجه، باید در نقطه (یا نقاطی) درون بازه برابر با صفر شود.

خطای مطلق روش دو بخشی

روش دو بخشی (عموماً) رویکردی برای به دست آوردن جواب دقیق معادله $$ f ( x ) = 0 $$ به دست نمی‌دهد. البته، می‌توانیم مقدار خطای مطلق را در تقریب تخمین بزنیم.

قضیه

فرض کنید $$ f ( x) $$ تابعی پیوسته در بازه $$ [a,b] $$ باشد به گونه‌ای که $$ f(a)f(b) < 0 $$. اگر بعد از $$N$$ تکرار روش دو بخشی، $$ x _ N $$ نقطه میانی در $$ N$$اُمین زیربازه $$ [a_N,b_N] $$ باشد:

$$ \large x_N = \frac{a_N + b_N}{2} $$

آنگاه جواب دقیق $$ x_{\mathrm{true}} $$ معادله $$ f(x)=0 $$ در زیربازه $$ [a_N,b_N] $$ وجود خواهد داشت و مقدار خطای مطلق برابر است با:

$$ \large \left| \ x _ { \text {true} } - x _ N \, \right | \leq \frac { b - a } { 2 ^ { N + 1 } } $$

می‌توانیم محدوده خطا را برای مشاهده حداقل تکرار لازم برای تضمین کمتر بودن خطای مطلق از مقدار از پیش تعیین شده $$ \epsilon $$ بازنویسی کنیم:

$$ \large \begin {align}
\frac { b - a } { 2 ^ { N + 1 } } & < \epsilon \\
\frac { b - a } { \epsilon } & < 2 ^ { N + 1 } \\
\ln \left ( \frac { b - a } { \epsilon } \right ) & < ( N + 1 ) \ln ( 2 ) \\
\frac { \ln \left ( \frac { b - a } { \epsilon } \right ) } { \ln ( 2 ) } - 1 & < N
\end {align} $$

پیاده‌سازی در پایتون

تابعی می‌نویسیم و نام آن را "bisection" قرار می‌دهیم. این تابع چهار ورودی "b" ،"a" ،"f" و "N" دارد و خروجی آن، حل معادله $$ f ( x ) =0 $$ با $$N$$ بار تکرار روش دو بخشی است. اگر در هر نقطه از تکرار داشته باشیم: $$ f(a_n)f(b_n) \geq 0 $$ (به دلیل بازه اولیه نامناسب یا گرد کردن خطا در محاسبات)، آنگاه در خروجی برنامه، عبارت "Bisection method fails." چاپ می‌شود و خروجی "None" خواهد بود.

برنامه پایتون مربوط به تابع مذکور به صورت زیر است.

1def bisection(f,a,b,N):
2    '''Approximate solution of f(x)=0 on interval [a,b] by bisection method.
3
4    Parameters
5    ----------
6    f : function
7        The function for which we are trying to approximate a solution f(x)=0.
8    a,b : numbers
9        The interval in which to search for a solution. The function returns
10        None if f(a)*f(b) >= 0 since a solution is not guaranteed.
11    N : (positive) integer
12        The number of iterations to implement.
13
14    Returns
15    -------
16    x_N : number
17        The midpoint of the Nth interval computed by the bisection method. The
18        initial interval [a_0,b_0] is given by [a,b]. If f(m_n) == 0 for some
19        midpoint m_n = (a_n + b_n)/2, then the function returns this solution.
20        If all signs of values f(a_n), f(b_n) and f(m_n) are the same at any
21        iteration, the bisection method fails and return None.
22
23    Examples
24    --------
25    >>> f = lambda x: x**2 - x - 1
26    >>> bisection(f,1,2,25)
27    1.618033990263939
28    >>> f = lambda x: (2*x - 1)*(x - 3)
29    >>> bisection(f,0,1,10)
30    0.5
31    '''
32    if f(a)*f(b) >= 0:
33        print("Bisection method fails.")
34        return None
35    a_n = a
36    b_n = b
37    for n in range(1,N+1):
38        m_n = (a_n + b_n)/2
39        f_m_n = f(m_n)
40        if f(a_n)*f_m_n < 0:
41            a_n = a_n
42            b_n = m_n
43        elif f(b_n)*f_m_n < 0:
44            a_n = m_n
45            b_n = b_n
46        elif f_m_n == 0:
47            print("Found exact solution.")
48            return m_n
49        else:
50            print("Bisection method fails.")
51            return None
52    return (a_n + b_n)/2

برای مثال، پارامترهای ورودی تابع را $$ f(x)=x^2 - x - 1 $$ و $$ N=25 $$ تکرار در بازه $$ [1,2] $$ در نظر می‌گیریم و می‌خواهیم نسبت طلایی را تقریب بزنیم:

$$ \large \phi = \frac { 1 + \sqrt { 5 } } { 2 } $$

نسبت طلایی $$ \phi $$، ریشه چندجمله‌ای درجه دوم $$ x^2 - x - 1 = 0 $$ است.

1f = lambda x: x**2 - x - 1
2approx_phi = bisection(f,1,2,25)
3print(approx_phi)
1.618033990263939

همچنین تضمین می‌شود که مقدار خطای مطلق کمتر از $$ (2 - 1)/(2^{26}) $$ باشد:

1error_bound = 2**(-26)
2print(error_bound)
1.4901161193847656e-08

بررسی می‌کنیم که مقدار خطای مطلق کمتر از محدوده خطا باشد:‌

1abs( (1 + 5**0.5)/2 - approx_phi) < error_bound
True

پیاده‌سازی در متلب

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

برای مثال، کد متلب روش دو بخشی برای یافتن ریشه $$p(x)=x^3-x-2$$ در بازه $$[0,2]$$ به صورت زیر است:

1clc;
2clear;
3close all;
4format long
5%% example 1
6 f = @(x) x^3-x-2;
7 a = 0 ;
8 b = 2 ;
9
10N = 20 ;
11for i = 1:N
12    x = (a+b)/2;
13    if f(a)*f(x) < 0
14        b = x ;
15    end
16    if f(b)*f(x) < 0
17        a = x ;
18    end
19    STR = ['n = ', num2str(i), ', x = ' ,num2str(x), ', f(x) = ' ,num2str(f(x))];
20    disp(STR)
21    
22end

خروجی این حاصل از اجرای کد بالا به صورت زیر خواهد بود:

n = 1, x = 1, f(x) = -2
n = 2, x = 1.5, f(x) = -0.125
n = 3, x = 1.75, f(x) = 1.6094
n = 4, x = 1.625, f(x) = 0.66602
n = 5, x = 1.5625, f(x) = 0.2522
n = 6, x = 1.5313, f(x) = 0.059113
n = 7, x = 1.5156, f(x) = -0.034054
n = 8, x = 1.5234, f(x) = 0.01225
n = 9, x = 1.5195, f(x) = -0.010971
n = 10, x = 1.5215, f(x) = 0.00062218
n = 11, x = 1.5205, f(x) = -0.0051789
n = 12, x = 1.521, f(x) = -0.0022794
n = 13, x = 1.5212, f(x) = -0.00082891
n = 14, x = 1.5214, f(x) = -0.00010343
n = 15, x = 1.5214, f(x) = 0.00025935
n = 16, x = 1.5214, f(x) = 7.7956e-05
n = 17, x = 1.5214, f(x) = -1.2739e-05
n = 18, x = 1.5214, f(x) = 3.2608e-05
n = 19, x = 1.5214, f(x) = 9.9343e-06
n = 20, x = 1.5214, f(x) = -1.4026e-06

به طور مشابه، کد زیر و نتیجه آن مربوط به روش دو بخشی برای یافتن ریشه معادله $$ f ( x ) =0.2\cosh (x) + \cos ( x ) - 3 $$ در بازه $$[0,6]$$ است:

1clc;
2clear;
3close all;
4format long
5
6%%% example 2
7f = @(x) 0.2*cosh(x)+cos(x)-3;
8a = 0 ;
9b = 6 ;
10
11N = 20 ;
12for i = 1:N
13    x = (a+b)/2;
14    if f(a)*f(x) < 0
15        b = x ;
16    end
17    if f(b)*f(x) < 0
18        a = x ;
19    end
20    STR = ['n = ', num2str(i), ', x = ' ,num2str(x), ', f(x) = ' ,num2str(f(x))];
21    disp(STR)
22    
23end

نتیجه:

n = 1, x = 3, f(x) = -1.9765
n = 2, x = 4.5, f(x) = 5.792
n = 3, x = 3.75, f(x) = 0.4339
n = 4, x = 3.375, f(x) = -1.047
n = 5, x = 3.5625, f(x) = -0.38476
n = 6, x = 3.6563, f(x) = 0.0037101
n = 7, x = 3.6094, f(x) = -0.19557
n = 8, x = 3.6328, f(x) = -0.097211
n = 9, x = 3.6445, f(x) = -0.047073
n = 10, x = 3.6504, f(x) = -0.021763
n = 11, x = 3.6533, f(x) = -0.0090467
n = 12, x = 3.6548, f(x) = -0.0026734
n = 13, x = 3.6555, f(x) = 0.00051706
n = 14, x = 3.6552, f(x) = -0.0010785
n = 15, x = 3.6553, f(x) = -0.0002808
n = 16, x = 3.6554, f(x) = 0.00011811
n = 17, x = 3.6554, f(x) = -8.1348e-05
n = 18, x = 3.6554, f(x) = 1.838e-05
n = 19, x = 3.6554, f(x) = -3.1484e-05
n = 20, x = 3.6554, f(x) = -6.5521e-06

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

^^

فیلم‌ های آموزش روش دو بخشی — به زبان ساده (+ دانلود فیلم آموزش گام به گام)

فیلم آموزشی روش دو بخشی

دانلود ویدیو

فیلم آموزشی حل مثال از روش دو بخشی در متلب

دانلود ویدیو
بر اساس رای ۳۵ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Mathematical Python
۳ دیدگاه برای «روش دو بخشی — به زبان ساده (+ دانلود فیلم آموزش گام به گام)»

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

عالی بود.ممنون

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

نظر شما چیست؟

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