خوارزمية طريقة التنصيف مع أمثلة

ما هي طريقة التنصيف؟

تُعدّ طريقة التنصيف إحدى أهمّ التقنيات العددية لإيجاد جذر المعادلات متعددة الحدود أو المعادلات المتسامية. وتعتمد هذه الطريقة على تحديد الفترة التي تحتوي على الجذر، ثمّ تقسيم هذه الفترة إلى نصفين في كلّ تكرار حتى يتمّ تحديد موقع الجذر ضمن هامش خطأ مقبول. وبسبب هذا التحديد، تُعرف طريقة التنصيف أيضاً باسم طريقة التحديد.

نظراً لأن آلية عملها تشبه البحث الثنائي، تُعرف طريقة التنصيف أيضاً باسم طريقة البحث الثنائي، أو طريقة التنصيف، أو طريقة التقسيم الثنائي. وهي تستند إلى أساس نظري متين: نظرية القيمة المتوسطة، التي تضمن أن الدالة المتصلة التي تغير إشارتها على فترة ما يجب أن تعبر الصفر في مكان ما داخل تلك الفترة.

بعد وضع التعريف الأساسي، دعونا نستكشف لماذا يعد إيجاد جذور المعادلات أمراً مهماً وكيف تتناسب طريقة التنصيف مع تلك الصورة الأوسع.

إيجاد جذور المعادلات

في هذا النقاش، سنركز فقط على المعادلات ذات المتغير المستقل الواحد. قد تكون هذه المعادلات خطية أو غير خطية. تصف المعادلات الخطية تمثيل الخط المستقيم بيانيًا، بينما تصف المعادلات غير الخطية المنحنيات والأشكال الأكثر تعقيدًا.

جذر المعادلة هو قيمة المتغير المستقل التي تحقق المعادلة. على سبيل المثال، جذر المعادلة f(x) = 4 – x² القيمة 0 تساوي 2، لأن f(2) = 4 – 2² = 0.

لنفترض أن f(x) دالة حقيقية متصلة. وفقًا لنظرية القيمة المتوسطة، فإن المعادلة f(x) = 0 لها جذر واحد على الأقل بين a و b عندما يكون f(a)f(b) < 0. بعبارة أخرى، للدالة f(x) جذر، "c"، يقع في مكان ما بين a و b.

تستغل طريقة التنصيف خاصية تغيير الإشارة هذه تحديدًا. يوضح القسم التالي كيف تبدو هذه الفكرة بيانيًا.

التمثيل البياني لطريقة التنصيف

يوضح الرسم البياني التالي آلية عمل طريقة التنصيف. من الرسم البياني، نلاحظ أن الجذر الحقيقي للمعادلة مُحدد باللون الأحمر.

يمكن تلخيص الإجراء على النحو التالي:

• نختار أولاً تخمينين أوليين، أ₁ وب₁، والتي من أجلها f(a)₁)و(ب₁) < 0. وفقًا لنظرية القيمة المتوسطة، يجب أن يقع الجذر في [a₁، ب₁].
• ثم نحسب نقطة المنتصف لـ₁ وب₁، وهو ب₂تم تقليص الفترة الأولية الآن إلى [أ₁، ب₂] لأن و(أ₁)و(ب₂) <0.
• وبالمثل، يتم تقسيم الفاصل الزمني إلى النصف مرارًا وتكرارًا حتى يتم العثور على حل تقريبي ضمن التفاوت المطلوب.

بعد أن أصبح الحدس الهندسي واضحاً، يمكننا الآن صياغة الإجراء كخوارزمية خطوة بخطوة.

خوارزمية طريقة التنصيف

فيما يلي خطوات تطبيق خوارزمية طريقة التنصيف لإيجاد جذر المعادلة f(x) = 0.

الخطوة 1) اختر التخمينات الأولية a و b ومعدل التسامح e.

الخطوة 2) إذا كانت f(a)f(b) ≥ 0، فإن الجذر لا يقع في هذه الفترة. في هذه الحالة، لا يوجد حل ضمن [a, b].

الخطوة 3) أوجد نقطة المنتصف، ج = (أ + ب)/2.

(أ) إذا كانت قيمة الدالة عند نقطة المنتصف f(c) = 0، فإن c هو الجذر. انتقل إلى الخطوة 5.
(ii) إذا كانت f(a)f(c) < 0، فإن الجذر يقع بين a و c. ثم اجعل a = a، b = c.
(iii) وإلا، فضع a = c، b = b.

الخطوة 4) إذا كان الخطأ المطلق أعلى من معدل التسامح، أي (ب - أ) > هـ، فارجع إلى الخطوة 3.

الخطوة 5) عرض c كالجذر التقريبي.

لنلقِ نظرة على مثال عملي لخوارزمية طريقة التنصيف. سنجد جذر الدالة المتصلة التالية باستخدام صيغة طريقة التنصيف.

و (س) = س³ - س² + 2

مثال على طريقة التقسيم

الخطوة 1) لنفترض،

         أ = -10،
         ب = 10، و
         e = 1% أو 0.01.

الخطوة 2) الآن، سوف نتحقق مما إذا كان f(a)f(b) >= 0 أم لا.

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + = 2 902
         و(أ)و(ب) = و(-10)و(10) = (-1098)(902) < 0

وبالتالي، فإن جذر الدالة المذكورة أعلاه يقع في الفترة [-10، 10].

الخطوة 3) بعد ذلك، يتم حساب نقطة المنتصف ج.

الآن يجب التحقق من الشروط التالية:

(i) هل f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2، وهو لا يساوي 0.

(ii) هل f(a)f(c) < 0:
         f(c)f(a) = 2 * (-1098) < 0

تم استيفاء الشرط. في التكرار التالي، ستكون القيم كالتالي:

         أ = أ = -10
         ب = ج = 0

الخطوة 4) بما أن (ب - أ) = (0 - (-10)) = 10 > 0.01، تُكرر العملية. يوضح الجدول أدناه التكرارات التالية.

الخطوة 5) في التكرار الحادي عشر، يصبح الشرط الوارد في الخطوة الرابعة غير صحيح. وبالتالي، فإن الجذر التقريبي لهذه المعادلة هو -1.00586.

بعد الانتهاء من المثال العددي، يقدم القسم التالي المخطط المنطقي الذي يوضح تدفق التحكم الكامل.

طريقة التنصيف المخطط المنطقي

يلخص المخطط الانسيابي أدناه منطق اتخاذ القرار لطريقة التنصيف، بما في ذلك فحص الأقواس، وتحديث نقطة المنتصف، واختبار التسامح.

مستعار-Code

يعكس الكود الزائف أدناه الخوارزمية ويعمل كنموذج أولي لتنفيذ طريقة التنصيف في أي لغة برمجة.

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

مثال على طريقة التقسيم في C/C++

C/ التاليC++ يطبق البرنامج طريقة التنصيف لإيجاد جذر المعادلة f(x) = x³ - س² + 2 ضمن الفترة [-10، 10].

الإدخال:

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

الإخراج:

The root is :-1.00586

مثال على طريقة التنصيف في Python

استخدم Python ينتج الإصدار أدناه نفس الجذر التقريبي باستخدام نفس المنطق، مما يجعله مثالياً للتجربة السريعة والتعليم.

الإدخال:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

الإخراج:

The root is :  -1.0059

مزايا وقيود طريقة التنصيف

كغيرها من الأساليب العددية، تتميز طريقة التنصيف بمزايا واضحة وبعض العيوب العملية. يلخص الجدول أدناه أهم هذه المزايا والعيوب.

تطبيقات طريقة التنصيف

تُستخدم طريقة التنصيف في العديد من سيناريوهات الحوسبة العملية والحديثة حيث تكون هناك حاجة إلى خطوة قوية لإيجاد الجذر.

• محاكاة هندسية: حل المعادلات غير الخطية التي تظهر في انتقال الحرارة، وديناميكا الموائع، والتحليل الهيكلي.
• النماذج المالية: حساب العوائد، ومعدلات العائد الداخلي، ونقاط التعادل حيث لا توجد حلول مغلقة.
• التعلم الآلي والذكاء الاصطناعي: تحديد العتبات، ومعايرة النماذج، وضبط المعلمات الفائقة داخل الحلول العددية المدعومة بالذكاء الاصطناعي.
• الرسومات الحاسوبية: تحديد نقاط تقاطع الأشعة مع الأسطح وقيم المعلمات على طول المنحنيات.
• الأنظمة المضمنة: جذور تقريبية في وحدات التحكم ذات الموارد المحدودة حيث تكون البساطة والقدرة على التنبؤ أكثر قيمة من السرعة.

الأسئلة الشائعة