روش دوبخشی

از ویکی‌پدیا، دانشنامهٔ آزاد
چند مرحله از اعمال روش دوبخشی اعمال شده بر بازهٔ [a1;b1]. نقطه قرمز بزرگ ریشه تابع است.

روش دوبخشی (به انگلیسی: Bisection method) یا تصنیف، یکی از روش‌های مهم مطرح شده در محاسبات عددی برای یافتن ریشه یک تابع پیوسته‌ است که می‌دانیم در دو نقطه مقدار آن دارای علامت مختلف است. تکرار این روش بر روی تابع‌هایی با ویژگی ذکر شده در صورتی که در حدود بازه، هم علامت نباشند ما را به ریشه می‌رساند.[۱]

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

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

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

ویژگی

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

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

جزئیات الگوریتم

داده‌های مسئله عبارتند از (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 انجام می‌دهیم: , , .


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

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

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

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

شماره مرحله
۱ ۱ ۲ ۱٫۵ ۰٫۱۲۵−
۲ ۱٫۵ ۲ ۱٫۷۵ ۱٫۶۰۹۳۷۵۰
۳ ۱٫۵ ۱٫۷۵ ۱٫۶۲۵ ۰٫۶۶۶۰۱۵۶
۴ ۱٫۵ ۱٫۶۲۵ ۱٫۵۶۲۵ ۰٫۲۵۲۱۹۷۳
۵ ۱٫۵ ۱٫۵۶۲۵ ۱٫۵۳۱۲۵۰۰ ۰٫۰۵۹۱۱۲۵
۶ ۱٫۵ ۱٫۵۳۱۲۵۰۰ ۱٫۵۱۵۶۲۵۰ ۰٫۰۳۴۰۵۳۸−
۷ ۱٫۵۱۵۶۲۵۰ ۱٫۵۳۱۲۵۰۰ ۱٫۵۲۳۴۳۷۵ ۰٫۰۱۲۲۵۰۴
۸ ۱٫۵۱۵۶۲۵۰ ۱٫۵۲۳۴۳۷۵ ۱٫۵۱۹۵۳۱۳ ۰٫۰۱۰۹۷۱۲−
۹ ۱٫۵۱۹۵۳۱۳ ۱٫۵۲۳۴۳۷۵ ۱٫۵۲۱۴۸۴۴ ۰٫۰۰۰۶۲۲۲
۱۰ ۱٫۵۱۹۵۳۱۳ ۱٫۵۲۱۴۸۴۴ ۱٫۵۲۰۵۰۷۸ ۰٫۰۰۵۱۷۸۹−
۱۱ ۱٫۵۲۰۵۰۷۸ ۱٫۵۲۱۴۸۴۴ ۱٫۵۲۰۹۹۶۱ ۰٫۰۰۲۲۷۹۴−
۱۲ ۱٫۵۲۰۹۹۶۱ ۱٫۵۲۱۴۸۴۴ ۱٫۵۲۱۲۴۰۲ ۰٫۰۰۰۸۲۸۹−
۱۳ ۱٫۵۲۱۲۴۰۲ ۱٫۵۲۱۴۸۴۴ ۱٫۵۲۱۳۶۲۳ ۰٫۰۰۰۱۰۳۴−
۱۴ ۱٫۵۲۱۳۶۲۳ ۱٫۵۲۱۴۸۴۴ ۱٫۵۲۱۴۲۳۳ ۰٫۰۰۰۲۵۹۴
۱۵ ۱٫۵۲۱۳۶۲۳ ۱٫۵۲۱۴۲۳۳ ۱٫۵۲۱۳۹۲۸ ۰٫۰۰۰۰۷۸۰

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

بررسی خطا

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

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

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

مزایا و معایب

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

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

تاریخچه

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

جستارهای وابسته

منابع

  1. «Bisection Method». دریافت‌شده در ۱۷ مه ۲۰۱۹.
  2. کتاب محاسبات عددی تألیف نیکوکار و درویشی بخش 2.3.1
  3. Burden & Faires 1985, p. 29. This version recomputes the function values at each iteration rather than carrying them to the next iterations.
  4. Burden & Faires 1985, p. 31, Theorem 2.1
  5. https://sites.google.com/site/knowyourrootsmaxima/introduction/bisectionmethod