ساده‌ترین الگوریتم یافتن ریشه معادلات روش دو بخشی یا تنصیف (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 $$ را محاسبه کنید.
  3. زیربازه $$ [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 $$.
  4. مراحل ۲ و ۳ را تا زمانی که طول بازه $$ [a_N,b_N] $$ به یک مقدار از پیش تعیین شده برسد، تکرار کنید.
  5. نقطه میانی $$ 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” خواهد بود.

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

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

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

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

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

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

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

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

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

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

نتیجه:

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

^^

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

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

دانلود ویدیو

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

دانلود ویدیو

سید سراج حمیدی دانش‌آموخته مهندسی برق است و به ریاضیات و زبان و ادبیات فارسی علاقه دارد. او آموزش‌های مهندسی برق، ریاضیات و ادبیات مجله فرادرس را می‌نویسد.

بر اساس رای 19 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

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