روش دوبخشی کیست؟ توضیح بده.
روش دوبخشی یا تصنیف، یکی از روش‌های مهم مطرح شده در محاسبات عددی برای یافتن ریشه یک تابع پیوسته‌ است که می‌دانیم در دو نقطه مقدار آن دارای علامت مختلف است. تکرار این روش بر روی تابع‌هایی با ویژگی ذکر شده در صورتی که در حدود بازه، هم علامت نباشند ما را به ریشه می‌رساند.به‌طور دقیقتر ابتدا مقدار تابع در میانه بازه داده شده محاسبه می‌شود، سپس از بین دو بازه ایجاد شده، بازه ای انتخاب می‌شود که مقدار تابع در ابتدا و انتهای بازهٔ جدید هم علامت نباشند.در این صورت به علت پیوستگی تابع اطمینان داریم ریشه در این بازه خواهد بود. حال برای این بازهٔ منتخب دوباره الگوریتم را تکرار می‌کنیم و به ریشه نزدیکتر می‌شویم.ویژگی.این روش در محاسبات عددی از ساده‌ترین روش‌های پیدا کردن ریشه تابع است. محاسبات ساده ای دارد و نیاز به محاسبات دشوار مشتق و انتگرال ندارد. از طرفی در کنار سادگی، این روش کند است و نسبت به بقیه روش‌های پیشنهادی برای پیدا کردن ریشه یک تابع، دیرتر به جواب می‌رسد.روش دوبخشی که بعضاً روش تصنیف نیز خوانده می‌شود، شباهت‌هایی به الگوریتم جستجوی دودویی در علوم کامپیوتر دارد.جزئیات الگوریتم.داده‌های مسئله عبارتند از (f(x به عنوان تابع ورودی و بازه [a,b] که در آن به دنبال ریشه تابع هستیم.شروط استفاده.دو محدودیت اصلی برای به‌کارگیری از این روش وجود دارد:اگر بخواهیم محدودیت‌های گفته شده را به زبان ریاضی بیان کنیم، اینگونه خواهد بود:پیاده‌سازی کامپیوتری الگوریتم.پیاده‌سازی الگوریتم دوبخشی به صورت شبه کد قابل مشاهده است:INPUT: Function f, endpoint values a, b, tolerance TOL, maximum iterations NMAXCONDITIONS: a &lt; b, either f(a) &lt; 0 and f(b) &gt; 0 or f(a) &gt; 0 and f(b) &lt; 0OUTPUT: value which differs from a root of f(x) = 0 by less than TOLN ← 1While N ≤ NMAX # limit iterations to prevent infinite loop c ← (a + b)/2 # new midpoint If f(c) = 0 or (b – a)/2 &lt; 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 intervalEndWhileOutput("Method failed.") # max number of steps exceededبررسی یک مثال: پیدا کردن ریشه یک چند جمله ای.می‌خواهیم ریشه چندجمله ای روبرو را با استفاده از روش دوبخشی تقریب بزنیم: ابتدا باید a و b را به عنوان بازه جوری معین کنیم تا (f(a و (f(b هم علامت نباشند. برای مثال بالا اعداد ۱ و ۲ مناسب خواهند بود چرا که:در نظر داریم به علت پیوستگی تابع چند جمله ای شرط دوم استفاده از روش برقرار خواهد بود.برای بررسی شرط سوم باید از تابع مشتق بگیریم و اطمینان داشته باشیم در بازه مورد نظر مشتق تابع در هیچ نقطه ای صفر نیست.مرحله اول تقریب را با یافتن c انجام می‌دهیم: formula_6 , formula_7 , formula_8.حال زمان محاسبه مقدار تابع در نقطه c است: به دلیل منفی بودن مقدار تابع، c را جایگزین a می‌کنیم تا مقادیر تابع در حدود بازه جدید نیز هم علامت نباشند.در نتیجه b همان مقدار قبلی را خواهد داشت ولی a مقدار جدید ۱٫۵ را خواهد گرفت.با تکرار این روش خواهیم دید فاصله بازه a و b تدریج کم و کم‌تر می‌شود و به ریشه واقعی تابع نزدیک تر می‌شویم. این اتفاق در جدول زیر قابل مشاهده است.مراحل تقریب می‌تواند تا زمان لازم ادامه پیدا کنند، در این مثال تا مرحله پانزدهم ادامه یافته‌است.بررسی خطا.با انجام هر مرحله از این تقریب، بازه اعداد، که مطمئن هستیم ریشه در این بازه قرار دارد، نصف می‌شود. به همین دلیل درجه همگرایی این روش خطی است.در واقع اگر c را ریشه اصلی در نظر بگیریم و درجه همگرایی خطی باعث می‌شود که روش دوبخشی الگوریتم نسبتاً کندی در پیدا کردن ریشه باشد.مزایا و معایب.یکی از مهم­ترین مزایای این روش، همگرایی همیشگی است. در هر مرحله از پیمایش و اجرای الگوریتم حتما خطا کمتر خواهد شد و مسائلی مانند واگرایی یا گیرافتادن الگوریتم در حلقه برای این روش وجود ندارد.از معایب روش دوبخشی می­توان به کند بودن روش و همچنین عدم توانایی الگوریتم در پیدا کردن بیش از یک ریشه در یک بازه معین اشاره کرد. در صورت وجود چنین مسئله ای باید از روش های دیگر پیدا کردن ریشه توابع استفاده کرد.تاریخچه.با وجود اینکه اطلاعات چندانی درباره تاریخچه دقیق پیدایش این روش در دست نیست، اما می­توان گفت که اندکی بعد از بیان قضیه مقدار میانی مطرح شده است. قضیه مقدار میانی برای اولین بار توسط بولزانو در سال 1817 طرح گردید. می­توان حدس زد یکی از ابزار های لازم برای اثبات کامل قضیه مقدار میانی، کارکرد روش دوبخشی بوده است.