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

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

يُعدّ إيجاد جذور كثيرات الحدود مشكلةً عريقةً دُرست على نطاق واسع عبر التاريخ، وقد أثّرت بشكلٍ كبير على تطوّر الرياضيات. وهي تتضمن تحديد إما تقريبًا عدديًا أو صيغةً مغلقةً لجذور كثيرة حدود أحادية المتغير، أي تحديد حلول تقريبية أو حلول بصيغة مغلقة لـ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}}إما أن تكون أعدادًا حقيقية أو أعدادًا مركبة .

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

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

ملخص

الصيغ المغلقة

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

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

الخوارزميات العددية

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

تاريخ

الصيغ المغلقة

أدرك السومريون، ثم البابليون، مشكلة إيجاد جذور كثيرات الحدود. ومنذ ذلك الحين، استمر البحث عن صيغ مغلقة لمعادلات كثيرات الحدود لآلاف السنين.

المعادلات التربيعية

تمكن البابليون والمصريون من حل معادلات تربيعية محددة في الألفية الثانية قبل الميلاد، وتتوافق حلولهم بشكل أساسي مع الصيغة التربيعية. [ 2 ]

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

المكعبات والرباعية

حدث أول اختراق في صيغة مغلقة لكثيرات الحدود من الدرجة الثانية أو أعلى في إيطاليا. ففي أوائل القرن السادس عشر، وجد عالم الرياضيات الإيطالي سكيبيوني ديل فيرو صيغة مغلقة للمعادلات التكعيبية من الشكل التالي:x3+مx=ن{\displaystyle x^{3}+mx=n}، أينم،ن{\displaystyle m,n}هي أعداد غير سالبة. وفي وقت لاحق، اكتشف نيكولو تارتاليا أيضًا طرقًا لحل مثل هذه المعادلات التكعيبية، وقام جيرولامو كاردانو بتلخيص ونشر عملهم في كتابه "آرس ماجنا" عام 1545.

في هذه الأثناء، اكتشف لودوفيكو فيراري ، تلميذ كاردانو، الصيغة المغلقة للمعادلات الرباعية في عام 1540. ويستند حله إلى الصيغة المغلقة للمعادلات التكعيبية، وبالتالي كان عليه الانتظار حتى يتم نشر الصيغة التكعيبية.

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

عدم قابلية حل المعادلات الخماسية

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

مع ذلك، لاحظ لاغرانج عيوب هذه الحجج في بحثه المنشور عام ١٧٧١ بعنوان "تأملات في النظرية الجبرية للمعادلات" ، حيث حلل سبب عدم جدوى الطرق المستخدمة لحل المعادلات التكعيبية والرباعية في حل المعادلات الخماسية. وتعتمد حجته على دراسة تبديل جذور المعادلات متعددة الحدود. ومع ذلك، ظل لاغرانج يعتقد بوجود صيغة مغلقة في جذور المعادلات الخماسية. ويبدو أن غاوس كان أول عالم رياضيات بارز يشك في عدم إمكانية حل المعادلات الخماسية، كما ذكر في أطروحته للدكتوراه عام ١٧٩٩.

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

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

حل عام باستخدام التوافقية

في عام 2025، قدم نورمان ويلدبرجر ودين روبين حلاً عاماً لأي درجة، يتضمن متسلسلة قوى رسمية . المعادلة1-x+أ2x2+أ3x3+أ4x4+...{\displaystyle 1-x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+...}يوجد حل

x=∑م2،م3،...≥0(2م2+3م3+4م4+...)!(1+م2+2م3+...)!م2!م3!...أ2م2أ3م3...{\displaystyle x=\sum _{m_{2},m_{3},...\geq 0}{{\frac {(2m_{2}+3m_{3}+4m_{4}+...)!}{(1+m_{2}+2m_{3}+...)!m_{2}!m_{3}!...}}a_{2}^{m_{2}}a_{3}^{m_{3}}...}}

هذا تعميم لحل المعادلات التربيعية باستخدام أعداد كاتالانجن{\displaystyle C_{n}}، والتي من أجلها يختزل إلىx=∑ن≥0جنتن{\displaystyle x=\sum _{n\geq 0}C_{n}t^{n}}أما بالنسبة للخماسي، فهذا يرتبط ارتباطًا وثيقًا بسلسلة أيزنشتاين . [ 4 ]

الأساليب العددية

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

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

طُوِّرت أقدم طرق التقريب التكراري لإيجاد الجذور لحساب الجذور التربيعية. في كتاب "ميتريكا " لهيرون الإسكندري (القرن الأول والثاني الميلادي)، حُسبت القيم التقريبية للجذور التربيعية من خلال التحسين التكراري لتقدير أولي. [ 5 ] وقدّم جمشيد الكاشي نسخة معممة من هذه الطريقة لحسابن{\displaystyle n}الجذر النوني . وقد تم العثور على طريقة مماثلة أيضًا في منشور هنري بريجز Trigonometria Britannica في عام 1633. كما طور فرانسيسكوس فييتا طريقة تقريبية مطابقة تقريبًا لطريقة نيوتن.

قام نيوتن بتعميم هذه الطريقة لحساب جذور كثيرات الحدود العشوائية في كتابه "De analysi per aequationes numero terminorum infinitas" (الذي كُتب عام 1669 ونُشر عام 1711)، والمعروف الآن باسم طريقة نيوتن . وفي عام 1690، نشر جوزيف رافسون نسخة مُحسّنة من طريقة نيوتن، مُقدّماً إياها بصيغة أقرب إلى النسخة الحديثة المُستخدمة اليوم. [ 6 ]

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

طرق عزل الجذر الحقيقي

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

تم تقديم أول خوارزمية كاملة لعزل الجذور الحقيقية بواسطة جاك شارل فرانسوا ستورم في عام 1829، والمعروفة باسم نظرية ستورم .

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

الطرق الميكانيكية

قبل اختراع الحواسيب الإلكترونية، كان الناس يستخدمون الحواسيب الميكانيكية لأتمتة مسائل حل جذور كثيرات الحدود. في عام ١٧٥٨، اقترح العالم المجري يا. أ. دي سيغنر تصميمًا لآلة حل الجذور في بحثه، تعمل عن طريق رسم بيان كثير الحدود على مستوى ثنائي الأبعاد، ثم إيجاد الجذور كنقاط تقاطع هذا الرسم مع المحور السيني. وفي عام ١٧٧٠، بحث عالم الرياضيات الإنجليزي جاك راونينغ إمكانية رسم بيان كثيرات الحدود باستخدام الحركات الموضعية. [ ١٠ ]

في عام 1845، اقترح عالم الرياضيات الإنجليزي فرانسيس باشفورث استخدام الطرق المثلثية لتبسيط مسألة إيجاد الجذور. بالنظر إلى متعددة الحدودأ0+أ1x+...+أنxن=0{\displaystyle a_{0}+a_{1}x+...+a_{n}x^{n}=0}، بديلx=كوس⁡ت{\displaystyle x=\cos t}. منذكوسن⁡ت{\displaystyle \cos ^{n}t}يمكن كتابتها كتركيبة خطية منكوس⁡كت،ك∈Z{\displaystyle \cos kt,k\in \mathbb {Z} }(انظر متعددات حدود تشيبيشيف )، يمكن إعادة صياغة متعددة الحدود بالشكل التالي

ب0+ب1كوس⁡ت+ب2كوس⁡(2ت)+...+بنكوس⁡(نت){\displaystyle b_{0}+b_{1}\cos t+b_{2}\cos(2t)+...+b_{n}\cos(nt)}

يمكن رسم هذه المنحنيات بواسطة محلل توافقي (يُعرف أيضًا باسم أجهزة التنبؤ بالمد والجزر). [ 11 ] بنى اللورد كلفن أول محلل توافقي عام 1872، بينما تصور باشفورث مثل هذا الجهاز في بحثه قبل ذلك بـ 27 عامًا. [ 12 ]

قام المهندس والرياضي الإسباني ليوناردو توريس كيفيدو ببناء عدة آلات لحل الجذور الحقيقية والمركبة لكثيرات الحدود بين عامي 1893 و1900. تستخدم آلته خوارزمية لوغاريتمية، وتحتوي على مكون ميكانيكي يُسمى مبدأ اللانهاية.سجل⁡(أ+ب){\displaystyle \log(a+b)}منسجل⁡أ،سجل⁡ب{\displaystyle \log a,\log b}بدقة عالية. وهذا يسمح له بتحقيق دقة عالية في إيجاد جذور كثيرات الحدود: حيث تحسب الآلة جذور كثيرات الحدود من الدرجة 8 بدقة تبلغ10-3{\displaystyle 10^{-3}}[ 13 ]​

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

إيجاد جذر واحد

الطريقة الأكثر استخدامًا لحساب جذر أي دالة قابلة للتفاضلو{\displaystyle f} هي طريقة نيوتن ، التي يتم فيها وضع تخمين أوليx0{\displaystyle x_{0}}يتم تحسينها بشكل متكرر. في كل تكرار، يكون الخط المماس لـو{\displaystyle f}فيxن{\displaystyle x_{n}}يُستخدم كتقريب خطي لـو{\displaystyle f}ويُستخدم جذرها كتخمين لاحقxن+1{\displaystyle x_{n+1}}:

xن+1=xن-و(xن)و′(xن)،{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},}

بشكل عام، قيمةxن{\displaystyle x_{n}}ستتقارب إلى جذر منو{\displaystyle f}.

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

على الرغم من أن معدل تقارب طريقة نيوتن يكون عادةً تربيعيًا ، إلا أنه قد يتقارب ببطء شديد أو حتى لا يتقارب على الإطلاق. وبشكل خاص، إذا لم يكن لكثير الحدود جذر حقيقي، وx0{\displaystyle x_{0}}إذا تم اختيار عدد حقيقي، فلن تتقارب طريقة نيوتن. مع ذلك، إذا كان لكثير الحدود جذر حقيقي أكبر من الجذر الحقيقي الأكبر لمشتقته، فإن طريقة نيوتن تتقارب تربيعيًا إلى هذا الجذر الأكبر.x0{\displaystyle x_{0}}أكبر من هذا الجذر الأكبر (توجد طرق سهلة لحساب الحد الأعلى للجذور، انظر خصائص جذور كثيرات الحدود ). هذه هي نقطة البداية لطريقة هورنر لحساب الجذور.

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

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

إيجاد جميع الجذور المركبة

طرق تستخدم الحساب بالأعداد المركبة

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

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

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

طرق تستخدم الجبر الخطي

لعلّ أكثر الطرق موثوقيةً لإيجاد جميع جذور متعددة الحدود هي إيجاد القيم الذاتية للمصفوفة المرافقة لمتعددة الحدود أحادية الحد، والتي تتطابق مع جذور متعددة الحدود. توجد العديد من الخوارزميات لحساب القيم الذاتية للمصفوفات. تستخدم الطريقة القياسية لإيجاد جميع جذور متعددة الحدود في MATLAB خوارزمية فرانسيس QR لحساب القيم الذاتية للمصفوفة المرافقة المناظرة لمتعددة الحدود. [ 14 ]

باستخدام البنية المتفرقة للمصفوفة المرافقة، تُعطي بعض طرق التكرار الخاصة بخوارزمية QR جميع الجذور المركبة في عملية حسابية من رتبة O(n^2) وتخزين من رتبة O(n). [ 15 ] [ 16 ]

من حيث المبدأ، يمكن استخدام أي خوارزمية للقيم الذاتية لإيجاد جذور متعددة الحدود. مع ذلك، ولأسباب تتعلق بالكفاءة، يُفضل استخدام الطرق التي تستغل بنية المصفوفة، أي التي يمكن تنفيذها بصيغة لا تعتمد على المصفوفات. من بين هذه الطرق طريقة القوة ، التي يُعد تطبيقها على منقولة المصفوفة المرافقة طريقة برنولي الكلاسيكية لإيجاد الجذر ذي القيمة المطلقة الأكبر. أما طريقة القوة العكسية مع الإزاحات، التي تجد أصغر جذر أولًا، فهي التي تُحرك متغير ( cpoly ) لخوارزمية جينكينز-تراوب وتمنحها استقرارها العددي. إضافةً إلى ذلك، تتميز هذه الطريقة بتقارب سريع من الرتبة .1+φ≈2.6{\displaystyle 1+\varphi \approx 2.6}(أينφ{\displaystyle \varphi }( النسبة الذهبية ) حتى في وجود جذور متجمعة. يأتي هذا التقارب السريع بتكلفة ثلاث عمليات تقييم متعددة الحدود لكل خطوة، مما ينتج عنه متبقي من O (| f ( x )| 2+3 φ ) ، أي تقارب أبطأ من التقارب بثلاث خطوات في طريقة نيوتن.

قيود الطرق التكرارية لإيجاد جميع الجذور

أقدم طريقة لإيجاد جميع الجذور هي البدء بإيجاد جذر واحد. عند إيجاد الجذر r ، يمكن حذفه من كثيرة الحدود بقسمة ذات الحدين x – r . تحتوي كثيرة الحدود الناتجة على الجذور المتبقية، والتي يمكن إيجادها بتكرار هذه العملية. هذه الفكرة، على الرغم من شيوعها في الاشتقاقات النظرية، لا تُجدي نفعًا في الحسابات العددية بسبب ظاهرة عدم الاستقرار العددي : تُظهر كثيرة حدود ويلكنسون أن تعديلًا طفيفًا جدًا في أحد المعاملات قد يُغير بشكل كبير ليس فقط قيمة الجذور، بل طبيعتها أيضًا (حقيقية أو مركبة). كذلك، حتى مع تقريب جيد، عند تقييم كثيرة حدود عند جذر تقريبي، قد نحصل على نتيجة قريبة جدًا من الصفر. على سبيل المثال، إذا كانت لكثيرة حدود من الدرجة 20 (درجة كثيرة حدود ويلكنسون) جذر قريب من 10، فقد تكون مشتقة كثيرة الحدود عند هذا الجذر من رتبة1020؛{\displaystyle 10^{20};}وهذا يعني أن خطأً من10-10{\displaystyle 10^{-10}}قد ينتج عن قيمة الجذر قيمة لكثير الحدود عند الجذر التقريبي تكون من رتبة1010.{\displaystyle 10^{10}.}

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

إن إيجاد الجذور الحقيقية لكثير الحدود ذي المعاملات الحقيقية هو مشكلة حظيت باهتمام كبير منذ بداية القرن التاسع عشر، ولا تزال مجالًا نشطًا للبحث.

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

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

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

تم تطبيق هذه الخوارزميات وهي متاحة في برنامج Mathematica (طريقة الكسور المستمرة) وبرنامج Maple (طريقة التنصيف)، بالإضافة إلى أنظمة الجبر الحاسوبي الرئيسية الأخرى ( SageMath و PARI/GP ). ويمكن لكلا التطبيقين إيجاد الجذور الحقيقية لكثيرات الحدود من الدرجة الأعلى من 1000 بشكل روتيني.

إيجاد الجذور في نطاق محدود

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

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

تستخدم خوارزمية Lehmer–Schur اختبار Schur–Cohn للدوائر؛ ويستخدم أحد المتغيرات، خوارزمية Wilf's global bisection، حساب عدد اللفات للمناطق المستطيلة في المستوى المركب.

تستخدم طريقة تقسيم الدائرة تحويلات متعددة الحدود القائمة على تحويل فورييه السريع (FFT) لإيجاد عوامل ذات درجة عالية تُقابل مجموعات من الجذور. ويتم تعظيم دقة التحليل باستخدام تكرار من نوع نيوتن. تُعد هذه الطريقة مفيدة لإيجاد جذور كثيرات الحدود ذات الدرجة العالية بدقة متناهية؛ إذ تتميز بتعقيد شبه مثالي في هذا السياق.

إيجاد الجذور المركبة في أزواج

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

يُعدّ الشكل الحقيقي لخوارزمية جينكينز-تراوب تحسينًا لهذه الطريقة.

كثيرات الحدود ذات المعاملات النسبية

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

التحليل الخالي من المربعات لكثير الحدود p هو تحليلص=ص1ص22⋯صكك{\displaystyle p=p_{1}p_{2}^{2}\cdots p_{k}^{k}}حيث كلصأنا{\displaystyle p_{i}}إما أن يكون 1 أو متعدد الحدود بدون جذور متعددة، واثنين مختلفينصأنا{\displaystyle p_{i}}ليس لديهم أي أصل مشترك.

تُعد خوارزمية يون طريقة فعالة لحساب هذا التحليل .

انظر أيضاً

مراجع

  1. ↑ بان، فيكتور ي. (يناير 1997). "حل المعادلات متعددة الحدود: بعض التاريخ والتقدم الحديث" . مجلة SIAM Review . 39 (2): 187-220 . doi : 10.1137/S0036144595288554 . ISSN 0036-1445 . 
  2. ↑ بيريمان، أ. إي. (1956). "المعادلة التربيعية البابلية" . المجلة الرياضية . 40 (333): 185-192 . doi : 10.2307/3608807 . ISSN 0025-5572 . JSTOR 3608807 .  
  3. ↑ براون، جيم (2000). "أبيل وعدم قابلية حل المعادلة الخماسية" (PDF) .
  4. ↑ وايلدبرغر، ن. ج.؛ روبين، د. (8 أبريل 2025). "حل متسلسلة هايبر-كاتالان لمعادلات متعددة الحدود، والجيود" . المجلة الرياضية الأمريكية الشهرية . 132 (5): 383-402 . doi : 10.1080/00029890.2025.2460966 .
  5. ↑ فاولر، ديفيد؛ روبسون، إليانور (نوفمبر 1998). "تقريبات الجذر التربيعي في الرياضيات البابلية القديمة: YBC 7289 في سياقها" . Historia Mathematica . 25 (4): 366–378 . doi : 10.1006/hmat.1998.2209 .
  6. ↑ كاجوري، فلوريان (1911-02-01). "ملاحظة تاريخية حول طريقة نيوتن-رافسون للتقريب" . المجلة الرياضية الأمريكية الشهرية . 18 (2): 29-32 . doi : 10.1080/00029890.1911.11997596 . ISSN 0002-9890 . 
  7. ^ أكريتاس، الكيفياديس ج.؛ دانيلوبولوس، ستيليانوس د. (1978/11/01). "حول نظرية السيد فنسنت المنسية" . تاريخ الرياضيات . 5 (4): 427-435 . دوى : 10.1016 / 0315-0860(78)90211-2 . ISSN 0315-0860 . 
  8. ↑ أوسبنسكي، جيه في (جيمس فيكتور) (1948). نظرية المعادلات. -- . أرشيف الإنترنت. نيويورك : شركة ماكجرو هيل للنشر . 
  9. ↑ روييه، فابريس؛ زيمرمان، بول (يناير 2004). "عزل فعال للجذور الحقيقية لكثيرات الحدود" . مجلة الرياضيات الحسابية والتطبيقية . 162 (1): 33-50 . doi : 10.1016/j.cam.2003.08.015 .
  10. ↑ Frame, JS (1945). "آلات لحل المعادلات الجبرية" . رياضيات الحساب . 1 (9): 337-353 . doi : 10.1090/S0025-5718-1945-0011196-2 . ISSN 0025-5718 . 
  11. ↑ باشفورث، فرانسيس؛ الجمعية البريطانية، كامبريدج، 1845 (1892). طبعة مُعاد طباعتها من "وصف لآلة لإيجاد الجذور العددية للمعادلات ورسم مجموعة متنوعة من المنحنيات المفيدة". أُرسلت إلى الجمعية البريطانية، 1845. مع ملحق يحتوي على مقتطفات من أوراق بحثية تتعلق باختراع جهاز التنبؤ بالمد والجزر . كامبريدج.{{cite book}}: صيانة CS1: موقع الناشر مفقود ( رابط ) صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط ) صيانة CS1: أسماء رقمية: قائمة المؤلفين ( رابط )
  12. ↑ باركر (2011) ، ص 37.
  13. ↑ توماس، فيديريكو (1 أغسطس/آب 2008). "عرض موجز عن المغزل اللانهائي لليوناردو توريس" . نظرية الآليات والآلات . 43 (8): 1055-1063 . doi : 10.1016/j.mechmachtheory.2007.07.003 . hdl : 10261/30460 . ISSN 0094-114X . 
  14. ↑ "جذور كثيرات الحدود - جذور MATLAB" . ماث ووركس . 2021-03-01 . تم الاسترجاع في 2021-09-20 .
  15. ↑ جاريد ل. أورينتز، توماس ماخ، راف فاندبريل وديفيد س. واتكينز: "حساب سريع ومستقر عكسيًا لجذور كثيرات الحدود"، مجلة SIAM لتحليل المصفوفات وتطبيقاتها، المجلد 36، العدد 3 (2015).
  16. ↑ جاريد ل. أورينتز، توماس ماخ، ليوناردو روبول، راف فاندبريل وديفيد س. واتكينز: "الحساب السريع والمستقر العكسي لجذور كثيرات الحدود، الجزء الثاني: تحليل الخطأ العكسي؛ المصفوفة المصاحبة والقلم المصاحب"، مجلة SIAM لتحليل المصفوفات وتطبيقاتها، المجلد 39، العدد 3 (2018).
  17. ↑ نغوين، هوي؛ نغوين، أوان؛ فو، فان (2016). "حول عدد الجذور الحقيقية لكثيرات الحدود العشوائية" . مجلة الاتصالات في الرياضيات المعاصرة . 18 (4): 1550052. arXiv : 1402.4628 . doi : 10.1142/S0219199715500522 . ISSN 0219-1997 .