خوارزمية البحث عن الجذر

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 19 صور
الموسوعة الحرة

في التحليل العددي ، تُعرف خوارزمية إيجاد الجذور بأنها خوارزمية لإيجاد أصفار الدوال المتصلة ، والتي تُسمى أيضًا "الجذور" . يُعرَّف صفر الدالة f بأنه العدد x الذي يحقق f ( x ) = 0. ولأن أصفار الدوال، عمومًا، لا يمكن حسابها بدقة أو التعبير عنها بصيغة مغلقة ، فإن خوارزميات إيجاد الجذور تُقدم تقريبات لهذه الأصفار. بالنسبة للدوال من الأعداد الحقيقية إلى الأعداد الحقيقية، أو من الأعداد المركبة إلى الأعداد المركبة، تُعبَّر هذه التقريبات إما كأعداد عشرية بدون حدود للخطأ، أو كقيم عشرية مع حدود للخطأ. تُكافئ التقريبات ذات حدود الخطأ فترات عزل صغيرة للجذور الحقيقية، أو أقراصًا للجذور المركبة. [ 1 ]

إن حل المعادلة f ( x ) = g ( x ) يُعادل إيجاد جذور الدالة h ( x ) = f ( x ) - g ( x ) . لذا، يمكن استخدام خوارزميات إيجاد الجذور لحل أي معادلة لدوال متصلة. مع ذلك، لا تضمن معظم خوارزميات إيجاد الجذور إيجاد جميع جذور الدالة، وإذا لم تجد الخوارزمية أي جذر، فهذا لا يعني بالضرورة عدم وجود جذر.

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

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

أساليب التحديد

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

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

أبسط خوارزمية لإيجاد الجذور هي طريقة التنصيف . لنفترض أن f دالة متصلة، ونعرف الفترة [ a , b ] بحيث يكون لـ f ( a ) و f ( b ) إشارتان متعاكستان (بين قوسين). ولنفترض أن c = ( a + b )/2 هو منتصف الفترة (نقطة المنتصف أو النقطة التي تنصف الفترة). عندئذٍ، إما أن يكون لـ f ( a ) و f ( c ) ، أو لـ f ( c ) و f ( b ) إشارتان متعاكستان، وبذلك نكون قد قسمنا طول الفترة على اثنين. على الرغم من أن طريقة التنصيف قوية، إلا أنها لا تزيد الدقة إلا بمقدار بت واحد فقط في كل تكرار. لذلك، فإن عدد عمليات تقييم الدالة المطلوبة لإيجاد جذر تقريبي من نوع ε هوسجل2⁡ب-أε{\displaystyle \log _{2}{\frac {ba}{\varepsilon }}}. أما الطرق الأخرى، في ظل الظروف المناسبة، فيمكنها تحقيق الدقة بشكل أسرع.

موقف كاذب ( regula falsi )

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

ج=أو(ب)-بو(أ)و(ب)-و(أ).{\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}

طريقة الوضع الخاطئ مشابهة لطريقة القاطع ، إلا أنها، بدلاً من الاحتفاظ بآخر نقطتين، تحرص على الاحتفاظ بنقطة واحدة على كل جانب من الجذر. قد تكون طريقة الوضع الخاطئ أسرع من طريقة التنصيف، ولن تتباعد أبدًا مثل طريقة القاطع. مع ذلك، قد تفشل في التقارب في بعض التطبيقات البسيطة بسبب أخطاء التقريب التي قد تؤدي إلى إشارة خاطئة للدالة f ( c ) . عادةً ما يحدث هذا إذا كانت مشتقة f كبيرة في جوار الجذر.

الاستيفاء

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

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

الأساليب التكرارية

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

طريقة نيوتن (والطرق المماثلة القائمة على المشتقات)

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

طريقة القاطع

باستبدال المشتقة في طريقة نيوتن بفرق محدود ، نحصل على طريقة القاطع . لا تتطلب هذه الطريقة حساب المشتقة (ولا حتى وجودها)، ولكن ثمن ذلك هو بطء التقارب (رتبة التقارب هي النسبة الذهبية ، أي ما يقارب 1.62 [ 2 ] ). تُعد طريقة برودن تعميمًا لطريقة القاطع في الأبعاد الأعلى .

طريقة ستيفنسن

إذا استخدمنا ملاءمة متعددة الحدود لإزالة الجزء التربيعي من الفرق المحدود المستخدم في طريقة القاطع، بحيث يقترب بشكل أفضل من المشتقة، فإننا نحصل على طريقة ستيفنسن ، التي لها تقارب تربيعي، وسلوكها (الجيد والسيئ) هو نفسه بشكل أساسي طريقة نيوتن ولكنها لا تتطلب مشتقة.

طريقة التكرار ذات النقطة الثابتة

يمكننا استخدام طريقة التكرار بنقطة ثابتة لإيجاد جذر الدالة. بفرض دالة معينةو(x){\displaystyle f(x)}والتي قمنا بتعيينها إلى الصفر لإيجاد الجذر (و(x)=0{\displaystyle f(x)=0})، نعيد كتابة المعادلة بدلالةx{\displaystyle x}لهذا السبب.و(x)=0{\displaystyle f(x)=0}يصبحx=ز(x){\displaystyle x=g(x)}(ملاحظة، غالبًا ما يكون هناك العديد)ز(x){\displaystyle g(x)}وظائف لكلو(x)=0{\displaystyle f(x)=0}الدالة). بعد ذلك، نعيد تسمية كل جانب من المعادلة على النحو التالي:xن+1=ز(xن){\displaystyle x_{n+1}=g(x_{n})}حتى نتمكن من إجراء التكرار. بعد ذلك، نختار قيمة لـx1{\displaystyle x_{1}}ونُجري التكرار حتى يتقارب نحو جذر الدالة. إذا تقارب التكرار، فسيتقارب إلى جذر. ولن يتقارب التكرار إلا إذا|ز′(رooت)|<1{\displaystyle |g'(root)|<1}.

كمثال على التحويلو(x)=0{\displaystyle f(x)=0}لx=ز(x){\displaystyle x=g(x)}إذا تم إعطاء الدالةو(x)=x2+x-1{\displaystyle f(x)=x^{2}+x-1}، سنعيد كتابتها كإحدى المعادلات التالية.

xن+1=(1/xن)-1{\displaystyle x_{n+1}=(1/x_{n})-1}،
xن+1=1/(xن+1){\displaystyle x_{n+1}=1/(x_{n}+1)}،
xن+1=1-xن2{\displaystyle x_{n+1}=1-x_{n}^{2}}،
xن+1=xن2+2xن-1{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}، أو
xن+1=±1-xن{\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}.

الاستيفاء العكسي

يمكن تجنب ظهور القيم المركبة في طرق الاستيفاء عن طريق استيفاء معكوس الدالة f ، مما ينتج عنه طريقة الاستيفاء التربيعي العكسي . مرة أخرى، يكون التقارب أسرع تقاربًا من طريقة القاطع، لكن الاستيفاء التربيعي العكسي غالبًا ما يكون أداؤه ضعيفًا عندما لا تكون القيم المتكررة قريبة من الجذر.

مزيج من الأساليب

طريقة برنت

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

طريقة ميدرز

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

جذور كثيرات الحدود

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

أ0+أ1x+أ2x2+⋯+أنxن=0{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}

أينأأنا{\displaystyle a_{i}}إما أن تكون أعدادًا حقيقية أو أعدادًا مركبة .

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

على الرغم من أهميتها التاريخية، فإن إيجاد جذور كثيرات الحدود ذات الدرجة الأعلى لم يعد يلعب دورًا محوريًا في الرياضيات والرياضيات الحاسوبية، باستثناء واحد رئيسي في الجبر الحاسوبي . [ 3 ]

إيجاد الجذور في الأبعاد العليا

تم تعميم طريقة التنصيف لتشمل أبعادًا أعلى؛ وتُسمى هذه الطرق بطرق التنصيف المعممة . [ 4 ] [ 5 ] في كل تكرار، يُقسّم المجال إلى جزأين، وتُقرر الخوارزمية - بناءً على عدد قليل من تقييمات الدالة - أيًّا من هذين الجزأين يجب أن يحتوي على جذر. في بُعد واحد، يكون معيار القرار هو أن تكون للدالة إشارات متعاكسة. يكمن التحدي الرئيسي في توسيع نطاق هذه الطريقة لتشمل أبعادًا متعددة في إيجاد معيار يُمكن حسابه بسهولة ويضمن وجود جذر.

تُعطي نظرية بوانكاريه -ميراندا معيارًا لوجود جذر في مستطيل، ولكن من الصعب التحقق منها لأنها تتطلب تقييم الدالة على كامل حدود المستطيل.

يُقدّم معيار آخر من خلال نظرية كرونكر [ 6 ] . تنص هذه النظرية على أنه إذا كانت الدرجة الطوبولوجية للدالة f على مستطيل غير صفرية، فإن المستطيل يجب أن يحتوي على جذر واحد على الأقل للدالة f . يُشكّل هذا المعيار أساسًا للعديد من طرق إيجاد الجذور، مثل طرق ستينجر [ 7 ] وكيرفوت [ 8 ] . مع ذلك، قد تستغرق عملية حساب الدرجة الطوبولوجية وقتًا طويلاً.

يعتمد معيار ثالث على متعدد السطوح المميز . يُستخدم هذا المعيار في طريقة تُسمى التنصيف المميز. [ 4 ] : ​​19 - لا تتطلب هذه الطريقة حساب الدرجة الطوبولوجية، بل تتطلب فقط حساب إشارات قيم الدوال. عدد التقييمات المطلوبة هو على الأقلسجل2⁡(د/ϵ){\displaystyle \log _{2}(D/\epsilon )}حيث D هو طول أطول ضلع في متعدد السطوح المميز. [ 9 ] : 11، اللمة 4.7. لاحظ أن فراهاتيس وإيوردانيديس [ 9 ] يثبتان حدًا أدنى لعدد التقييمات، وليس حدًا أعلى.

تستخدم طريقة رابعة نظرية القيمة المتوسطة على العناصر البسيطة. [ 10 ] ومرة ​​أخرى، لم يتم تحديد حد أعلى لعدد الاستعلامات.

انظر أيضاً

طريقة برودن  – طريقة شبه نيوتن لإيجاد الجذور في حالة المتغيرات المتعددة

مراجع

  1. ↑ بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "الفصل 9. إيجاد الجذور ومجموعات المعادلات غير الخطية" . وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8.
  2. ↑ شانسون، جيفري ر. (3 أكتوبر 2024). "رتبة التقارب" . ليبرتيكستس ماثيماتيكس . تم الاسترجاع في 3 أكتوبر 2024 .
  3. ↑ بان، فيكتور ي. (يناير 1997). "حل المعادلات متعددة الحدود: بعض التاريخ والتقدم الحديث" . مجلة SIAM Review . 39 (2): 187-220 . doi : 10.1137/S0036144595288554 . ISSN 0036-1445 . 
  4. 1 2 مورين، ب.؛ فراهاتيس، م.ن.؛ ياكوبسون، ج.س. (2002-06-01). "حول تعقيد عزل الجذور الحقيقية وحساب الدرجة الطوبولوجية بيقين" . مجلة التعقيد . 18 (2): 612-640 . doi : 10.1006/jcom.2001.0636 . ISSN 0885-064X . 
  5. ↑ فراهاتيس، مايكل ن. (2020). "تعميمات لنظرية القيمة المتوسطة لتقريب النقاط الثابتة وأصفار الدوال المتصلة" . في: سيرجييف، ياروسلاف د.؛ كفاسوف، ديمتري إي. (محرران). الحسابات العددية: النظرية والخوارزميات . سلسلة محاضرات في علوم الحاسوب. المجلد 11974. تشام: دار نشر سبرينغر الدولية. الصفحات 223-238 . doi : 10.1007/978-3-030-40616-5_17 . ISBN   978-3-030-40616-5. S2CID 211160947 . 
  6. ↑ أورتيغا، جيمس م.؛ راينبولدت، فيرنر س. (2000). الحل التكراري للمعادلات غير الخطية في عدة متغيرات . جمعية الرياضيات الصناعية والتطبيقية. ISBN 978-0-89871-461-6.
  7. ↑ ستينجر، فرانك (1975-03-01). "حساب الدرجة الطوبولوجية لتطبيق في Rn". الرياضيات العددية . 25 (1): 23-38 . doi : 10.1007/BF01419526 . ISSN 0945-3245 . S2CID 122196773 .  
  8. ↑ كيرفوت، بيكر (1979-06-01). "طريقة فعّالة لحساب درجة التشعب لطريقة التنصيف المعممة". الرياضيات العددية . 32 (2): 109-127 . doi : 10.1007/BF01404868 . ISSN 0029-599X . S2CID 122058552 .  
  9. 1 2 فراهاتيس، إم إن؛ إيوردانيديس، كي آي (1986-03-01). "طريقة عامة سريعة للتنصيف لحل أنظمة المعادلات غير الخطية". الرياضيات العددية . 49 (2): 123-138 . doi : 10.1007/BF01389620 . ISSN 0945-3245 . S2CID 121771945 .  
  10. ↑ فراهاتيس، مايكل ن. (2020-04-15). "نظرية القيمة المتوسطة للمُجَسَّمات لتقريب النقاط الثابتة والأصفار باستخدام المُجَسَّمات" . الطوبولوجيا وتطبيقاتها . 275 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641 . S2CID 213249321 .  

للمزيد من القراءة

  • فيكتور ياكوفليفيتش بان: "حل معادلة متعددة الحدود: بعض التاريخ والتقدم الأخير"، مجلة SIAM، المجلد 39، العدد 2، الصفحات 187-220 (يونيو 1997).
  • جون مايكل ماكنامي: الطرق العددية لجذور كثيرات الحدود - الجزء الأول ، إلسيفير، ISBN 978-0-444-52729-5 (2007).
  • جون مايكل ماكنامي وفيكتور ياكوفليفيتش بان: الطرق العددية لجذور كثيرات الحدود - الجزء الثاني ، إلسيفير، ISBN 978-0-444-52730-1 (2013).