موضوع مقاله: روش دوبخشی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش دوبخشی | مقدمه: روش دوبخشی یا تصنیف، یکی از روش‌های مهم مطرح شده در محاسبات عددی برای یافتن ریشه یک تابع پیوسته‌ است که می‌دانیم در دو نقطه مقدار آن دارای علامت مختلف است. | ## بخش 1: روش دوبخشی | تکرار این روش بر روی تابع‌هایی با ویژگی ذکر شده در صورتی که در حدود بازه، هم علامت نباشند ما را به ریشه می‌رساند. به‌طور دقیقتر ابتدا مقدار تابع در میانه بازه داده شده محاسبه می‌شود، سپس از بین دو بازه ایجاد شده، بازه ای انتخاب می‌شود که مقدار تابع در ابتدا و انتهای بازهٔ جدید هم علامت نباشند. حال برای این بازهٔ منتخب دوباره الگوریتم را تکرار می‌کنیم و به ریشه نزدیکتر می‌شویم. از طرفی در کنار سادگی، این روش کند است و نسبت به بقیه روش‌های پیشنهادی برای پیدا کردن ریشه یک تابع، دیرتر به جواب می‌رسد. روش دوبخشی که بعضاً روش تصنیف نیز خوانده می‌شود، شباهت‌هایی به الگوریتم جستجوی دودویی در علوم کامپیوتر دارد. جزئیات الگوریتم داده‌های مسئله عبارتند از (f(x به عنوان تابع ورودی و بازه [a,b] که در آن به دنبال ریشه تابع هستیم. شروط استفاده دو محدودیت اصلی برای به‌کارگیری از این روش وجود دارد: در بازه [a,b] داده شده، ریشه وجود داشته باشد. اگر بخواهیم محدودیت‌های گفته شده را به زبان ریاضی بیان کنیم، اینگونه خواهد بود: مقدار تابع در x=a و x=b هم علامت نباشند، به عبارتی f(a).f(b) < 0. | ## بخش 2: روش دوبخشی | با توجه به قضیه مقدار میانی و شروط ۱ و ۲ حتماً X در بازه [a,b] وجود دارد که f(X) = ۰ باشد. در هیچ‌یک از نقاط بازه [a,b] مشتق تابع (f(x برابر صفر نباشد.کتاب محاسبات عددی تألیف نیکوکار و درویشی بخش 2.3.1 مراحل الگوریتم محاسبه مقدار c - نقطه وسط بازه [a,b] - یا به عبارتی a+b) = c)½. اگر c به قدر کافی به ریشه نزدیک بود (مقدار |(f(c)| به اندازه کافی به صفر نزدیک بود)، محاسبات را متوقف می‌کنیم. در این حالت مطمئنیم ریشه در بازه جدید وجود خواهد داشت و دوباره به مرحله ۱ برمی‌گردیم. پیاده‌سازی کامپیوتری الگوریتم پیاده‌سازی الگوریتم دوبخشی به صورت شبه کد قابل مشاهده است:. برای مثال بالا اعداد ۱ و ۲ مناسب خواهند بود چرا که: در نظر داریم به علت پیوستگی تابع چند جمله ای شرط دوم استفاده از روش برقرار خواهد بود. برای بررسی شرط سوم باید از تابع مشتق بگیریم و اطمینان داشته باشیم در بازه مورد نظر مشتق تابع در هیچ نقطه ای صفر نیست. نقاطی که در این تابع مشتق صفر دارند تقریبا برابر برابر 0.7 و 0.7- است که در بازه مورد نظر با نیستند. | ## بخش 3: روش دوبخشی | حال زمان محاسبه مقدار تابع در نقطه c است: به دلیل منفی بودن مقدار تابع، c را جایگزین a می‌کنیم تا مقادیر تابع در حدود بازه جدید نیز هم علامت نباشند. با تکرار این روش خواهیم دید فاصله بازه a و b تدریج کم و کم‌تر می‌شود و به ریشه واقعی تابع نزدیک تر می‌شویم. شماره مرحله۱۱۲۱٫۵۰٫۱۲۵−۲۱٫۵۲۱٫۷۵۱٫۶۰۹۳۷۵۰۳۱٫۵۱٫۷۵۱٫۶۲۵۰٫۶۶۶۰۱۵۶۴۱٫۵۱٫۶۲۵۱٫۵۶۲۵۰٫۲۵۲۱۹۷۳۵۱٫۵۱٫۵۶۲۵۱٫۵۳۱۲۵۰۰۰٫۰۵۹۱۱۲۵۶۱٫۵۱٫۵۳۱۲۵۰۰۱٫۵۱۵۶۲۵۰۰٫۰۳۴۰۵۳۸−۷۱٫۵۱۵۶۲۵۰۱٫۵۳۱۲۵۰۰۱٫۵۲۳۴۳۷۵۰٫۰۱۲۲۵۰۴۸۱٫۵۱۵۶۲۵۰۱٫۵۲۳۴۳۷۵۱٫۵۱۹۵۳۱۳۰٫۰۱۰۹۷۱۲−۹۱٫۵۱۹۵۳۱۳۱٫۵۲۳۴۳۷۵۱٫۵۲۱۴۸۴۴۰٫۰۰۰۶۲۲۲۱۰۱٫۵۱۹۵۳۱۳۱٫۵۲۱۴۸۴۴۱٫۵۲۰۵۰۷۸۰٫۰۰۵۱۷۸۹−۱۱۱٫۵۲۰۵۰۷۸۱٫۵۲۱۴۸۴۴۱٫۵۲۰۹۹۶۱۰٫۰۰۲۲۷۹۴−۱۲۱٫۵۲۰۹۹۶۱۱٫۵۲۱۴۸۴۴۱٫۵۲۱۲۴۰۲۰٫۰۰۰۸۲۸۹−۱۳۱٫۵۲۱۲۴۰۲۱٫۵۲۱۴۸۴۴۱٫۵۲۱۳۶۲۳۰٫۰۰۰۱۰۳۴−۱۴۱٫۵۲۱۳۶۲۳۱٫۵۲۱۴۸۴۴۱٫۵۲۱۴۲۳۳۰٫۰۰۰۲۵۹۴۱۵۱٫۵۲۱۳۶۲۳۱٫۵۲۱۴۲۳۳۱٫۵۲۱۳۹۲۸۰٫۰۰۰۰۷۸۰ مراحل تقریب می‌تواند تا زمان لازم ادامه پیدا کنند، در این مثال تا مرحله پانزدهم ادامه یافته‌است. بررسی خطا با انجام هر مرحله از این تقریب، بازه اعداد، که مطمئن هستیم ریشه در این بازه قرار دارد، نصف می‌شود. در هر مرحله از پیمایش و اجرای الگوریتم حتما خطا کمتر خواهد شد و مسائلی مانند واگرایی یا گیرافتادن الگوریتم در حلقه برای این روش وجود ندارد. از معایب روش دوبخشی می­توان به کند بودن روش و همچنین عدم توانایی الگوریتم در پیدا کردن بیش از یک ریشه در یک بازه معین اشاره کرد. در صورت وجود چنین مسئله ای باید از روش های دیگر پیدا کردن ریشه توابع استفاده کرد. تاریخچه با وجود اینکه اطلاعات چندانی درباره تاریخچه دقیق پیدایش این روش در دست نیست، اما می­توان گفت که اندکی بعد از بیان قضیه مقدار میانی مطرح شده است. | ## جمع‌بندی | می­توان حدس زد یکی از ابزار های لازم برای اثبات کامل قضیه مقدار میانی، کارکرد روش دوبخشی بوده است.