روش دو بخشی — به زبان ساده (+ دانلود فیلم آموزش گام به گام)
سادهترین الگوریتم یافتن ریشه معادلات روش دو بخشی یا تنصیف (Bisection Method) است. این الگوریتم را میتوان بر هر تابع پیوسته $$ f ( x ) $$ در بازه $$ [a,b] $$ اعمال کرد که علامت مقدار تابع $$ f ( x ) $$ از $$ a $$ تا $$ b$$ تغییر میکند. فرایند روش دو بخشی ساده است: بازه به دو قسمت تقسیم میکنیم و یک جواب باید در یک زیربازه وجود داشته باشد که در آن، علامت $$ f(x)$$ تغییر میکند. روند مذکور را تکرار میکنیم.
الگوریتم روش دو بخشی
فرایند روش دو بخشی به صورت زیر است:
- بازه شروع $$ [a_0,b_0] $$ را انتخاب کنید، به گونهای که $$ f(a_0)f(b_0) < 0 $$.
- نقطه میانی $$ f(m_0) $$ که $$ m_0 = (a_0+b_0)/2 $$ را محاسبه کنید.
- زیربازه $$ [a_1,b_1] $$ را تعیین کنید:
- اگر $$ f(a_0)f(m_0) < 0 $$، آنگاه $$ [a_1,b_1] $$ به عنوان بازه بعدی در نظر گرفته میشود که در آن، $$ a_1=a_0 $$ و $$ b_1=m_0 $$.
- اگر $$ f(b_0)f(m_0) < 0 $$، آنگاه $$ [a_1,b_1] $$ به عنوان بازه بعدی در نظر گرفته میشود که در آن، $$ a_1=m_0 $$ و $$ b_1=b_0 $$.
- مراحل ۲ و ۳ را تا زمانی که طول بازه $$ [a_N,b_N] $$ به یک مقدار از پیش تعیین شده برسد، تکرار کنید.
- نقطه میانی $$ 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
اگر این مطلب برایتان مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- روش نیوتن — به زبان ساده
- دستگاه معادلات خطی — به زبان ساده
- جذر یا محاسبه ریشه دوم عدد — به زبان ساده
^^
سلام ببخشید کسی میتونه معادلات درجه سوم را در پایتون حل کنید؟
عالی بود.ممنون
سلام.
سپاس از همراهیتان با مجله فرادرس.
سالم و سربلند باشید.