روش دوبخشی

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

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

داده‌های مسئله عبارتند از (f(x به عنوان تابع ورودی و بازه [a,b] که در آن به دنبال ریشه تابع هستیم.

شروط استفاده

دو محدودیت اصلی برای به‌کارگیری از این روش وجود دارد:

• در بازه [a,b] داده شده، ریشه وجود داشته باشد.
• ریشه ذکر شده در بازه فوق یکتا باشد.

اگر بخواهیم محدودیت‌های گفته شده را به زبان ریاضی بیان کنیم، اینگونه خواهد بود:

1. مقدار تابع در x=a و x=b هم علامت نباشند، به عبارتی f(a).f(b) < 0.
2. با توجه به قضیه مقدار میانی و شروط ۱ و ۲ حتماً X در بازه [a,b] وجود دارد که f(X) = ۰ باشد.
3. در هیچ‌یک از نقاط بازه [a,b] مشتق تابع (f(x برابر صفر نباشد.

مراحل الگوریتم

1. محاسبه مقدار c - نقطه وسط بازه [a,b] - یا به عبارتی a+b) = c)½.
2. محاسبه مقدار تابع در f(c) ,c.
3. اگر c به قدر کافی به ریشه نزدیک بود (مقدار |(f(c)| به اندازه کافی به صفر نزدیک بود)، محاسبات را متوقف می‌کنیم.
4. در غیر این صورت اگر (f(c هم علامت (f(a بود c را جایگزین a می‌کنیم، در غیر این صورت (یعنی اگر(f(c هم علامت (f(b بود) c را جایگزین b می‌کنیم. در این حالت مطمئنیم ریشه در بازه جدید وجود خواهد داشت و دوباره به مرحله ۱ برمی‌گردیم.

پیاده‌سازی کامپیوتری الگوریتم

پیاده‌سازی الگوریتم دوبخشی به صورت شبه کد قابل مشاهده است:

INPUT: Function f,
       endpoint values a, b,
       tolerance TOL,
       maximum iterations NMAX
CONDITIONS: a < b,
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x) = 0 by less than TOL

N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
  c ← (a + b)/2 # new midpoint
  If f(c) = 0 or (b – a)/2 < TOL then # solution found
    Output(c)
    Stop
  EndIf
  N ← N + 1 # increment step counter
  If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded

می‌خواهیم ریشه چندجمله ای روبرو را با استفاده از روش دوبخشی تقریب بزنیم:

ابتدا باید a و b را به عنوان بازه جوری معین کنیم تا (f(a و (f(b هم علامت نباشند. برای مثال بالا اعداد ۱ و ۲ مناسب خواهند بود چرا که:

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

نقاطی که در این تابع مشتق صفر دارند تقریبا برابر برابر 0.7 و 0.7- است که در بازه مورد نظر با نیستند. پس با اطمینان میتوانیم از روش دوبخشی در این مثال برای یافتن ریشه استفاده کنیم.

مرحله اول تقریب را با یافتن c انجام می‌دهیم: ${\displaystyle a_1=1}$

حال زمان محاسبه مقدار تابع در نقطه c است:

به دلیل منفی بودن مقدار تابع، c را جایگزین a می‌کنیم تا مقادیر تابع در حدود بازه جدید نیز هم علامت نباشند.

در نتیجه b همان مقدار قبلی را خواهد داشت ولی a مقدار جدید ۱٫۵ را خواهد گرفت.

با تکرار این روش خواهیم دید فاصله بازه a و b تدریج کم و کم‌تر می‌شود و به ریشه واقعی تابع نزدیک تر می‌شویم. این اتفاق در جدول زیر قابل مشاهده است.

مراحل تقریب می‌تواند تا زمان لازم ادامه پیدا کنند، در این مثال تا مرحله پانزدهم ادامه یافته‌است.

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

در واقع اگر c را ریشه اصلی در نظر بگیریم و c_{n را تقریب بدست آمده از روش برای ریشه در مرحله n ام بدانیم، خواهیم داشت:}

درجه همگرایی خطی باعث می‌شود که روش دوبخشی الگوریتم نسبتاً کندی در پیدا کردن ریشه باشد.

یکی از مهم­ترین مزایای این روش، همگرایی همیشگی است. در هر مرحله از پیمایش و اجرای الگوریتم حتما خطا کمتر خواهد شد و مسائلی مانند واگرایی یا گیرافتادن الگوریتم در حلقه برای این روش وجود ندارد.

از معایب روش دوبخشی می­توان به کند بودن روش و همچنین عدم توانایی الگوریتم در پیدا کردن بیش از یک ریشه در یک بازه معین اشاره کرد. در صورت وجود چنین مسئله ای باید از روش های دیگر پیدا کردن ریشه توابع استفاده کرد.

با وجود اینکه اطلاعات چندانی درباره تاریخچه دقیق پیدایش این روش در دست نیست، اما می­توان گفت که اندکی بعد از بیان قضیه مقدار میانی مطرح شده است. قضیه مقدار میانی برای اولین بار توسط بولزانو در سال 1817 طرح گردید. می­توان حدس زد یکی از ابزار های لازم برای اثبات کامل قضیه مقدار میانی، کارکرد روش دوبخشی بوده است.

• الگوریتم جست و جوی دودویی
• روش نیوتون-رافسون
• روش نابجایی