در این مطلب، روش نوشتن برنامه پیدا کردن ریشه های تابع با روش دو بخشی بیان و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ پی» (PHP) انجام شده است. تابع f(x)‎ روی عدد ممیز شناور x و همچنین، دو عدد a و b داده شده است؛ به طوری که f(a)*f(b) < 0‎ و f(x)‎ در [a, b] پیوسته است. در اینجا، f(x)‎ نشانگر یک معادله جبری یا غیر جبری است. هدف، پیدا کردن ریشه در بازه [a, b] (یا پیدا کردن مقداری از x به طوری است که f(x) = 0) است. مثال زیر،‌ به درک بهتر این مطلب کمک می‌کند.

ورودی: تابعی از x، مثلا x3 – x2 + 2 و دو مقدار a = -200 و b = 300 به گونه‌ای که f(a)*f(b) < 0 و f(a)‎ و f(b)‎ علامت‌های مخالف هم دارند.

خروجی: The value of root is : -1.0025 (یا هر مقدار ممکن دیگری با انحراف پذیرفته شده از ریشه).

ممکن است این پرسش برای برخی از افراد مطرح شود که توابع جبری و غیر جبری چه هستند؟ توابع جبری، توابعی محسوب می‌شوند که می‌توان آن‌ها را به صورت چند جمله‌ایی‌هایی مانند f(x) = a1x3 + a2x2 +‎ ….. + e نشان داد که در آن‌ها، aa1, a2, …‎ ثابت‌ها و x یک متغیر است. به عنوان مثال‌هایی از توابع غیر جبری، می‌توان به توابعی به صورت f(x) = sin(x)*x – 3 یا f(x) = ex + x2 یا f(x) = ln(x) + x ….‎ اشاره کرد.

روش دو بخشی چیست؟

این روش که آن را روش «تنصیف»، «نصف شدن فاصله» (Interval Halving Method) یا «دو بخشی» (Bisection Method) نیز می‌نامند، یک روش «جستجوی دودویی» (Binary Search Method) یا روش دوگانگی (Dichotomy Method) است. از این روش برای پیدا کردن ریشه یک معادله در بازه داده شده استفاده می‌شود. در واقع روش دو بخشی برای پیدا کردن مقدار x برای f(x) = 0 مورد استفاده قرار می‌گیرد.

این روش بر اساس «قضیه مقدار میانی» (The Intermediate Value Theorem) است. قضیه مقدار میانی بیان می‌کند که اگر f(x) ‎ یک تابع پیوسته باشد و دو عدد حقیقی a و b به طوری که f(a)*f(b) 0 و f(b) < 0 وجود داشته باشند، تضمین می‌شود که حداقل یک ریشه بین آن‌ها وجود داشته باشد.

فرضیات

  • f(x)‎ یک تابع پیوسته در بازه [a, b] است.
  • f(a) * f(b) < 0

گام‌ها

  1. هدف پیدا کردن نقطه میانی c= (a + b)/2 است.
  2. اگر f(c) == 0، بنابراین c ریشه و پاسخ مسئله است.
  3. در غیر این صورت، f(c) != 0
    1. اگر مقدار f(a)*f(c) < 0، بنابراین ریشه بین a و c خواهد بود. بنابراین، برای a و c نیز تکرار می‌شود.
    2. در غیر این صورت، اگر f(b)*f(c) < 0، ریشه بین b و c قرار دارد. بنابراین تکرار برای b و c انجام می‌شود.
    3. در غیر این صورت، تابع داده شده هیچ یک از مفروضات را دنبال نمی‌کند.
    4. از آنجا که ریشه ممکن است یک عدد ممیز شناور باشد، گام‌های بالا تا هنگامی که تفاوت بین a و b کمتر از یک مقدار (یک مقدار بسیار کوچک) باشد، تکرار می‌شوند.

در ادامه، پیاده‌سازی گام‌های بالا در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در ++C

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در جاوا

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در پایتون

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در #C

برنامه پیدا کردن ریشه های تابع با روش دو بخشی در PHP

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

مزایا و معایب روش دوبخشی

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

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

^^

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

بر اساس رای 2 نفر

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

نظر شما چیست؟

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