نظرية ستورم

في الرياضيات ، تُعرف متتالية ستورم لكثير الحدود أحادي المتغير p بأنها متتالية من كثيرات الحدود المرتبطة بـ p ومشتقتها، وذلك باستخدام صيغة معدلة من خوارزمية إقليدس لكثيرات الحدود . تُعبّر نظرية ستورم عن عدد الجذور الحقيقية المختلفة لـ p الواقعة في فترة معينة بدلالة عدد تغيرات إشارات قيم متتالية ستورم عند حدود تلك الفترة. عند تطبيقها على فترة جميع الأعداد الحقيقية، تُعطي هذه النظرية العدد الإجمالي للجذور الحقيقية لـ p . ^{[ 1 ]}

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

في الحسابات على الأعداد الحقيقية ، تُعدّ نظرية ستورم أقل كفاءة من الطرق الأخرى القائمة على قاعدة ديكارت للإشارات . ومع ذلك، فهي تعمل على كل حقل مغلق حقيقي ، وبالتالي تظل أساسية للدراسة النظرية للتعقيد الحسابي لقابلية الحسم وإزالة المُكمِّمات في نظرية الأعداد الحقيقية من الرتبة الأولى.

سميت متتالية ستورم ونظرية ستورم نسبة إلى جاك شارل فرانسوا ستورم ، الذي اكتشف النظرية في عام 1829. ^{[ 2 ]}

سلسلة ستورم أو متتالية ستورم لكثير الحدود أحادي المتغير P ( x ) ذي المعاملات الحقيقية هي متتالية من كثيرات الحدود${\displaystyle P_{0},P_{1},\ldots ,}$بحيث

${\displaystyle {\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1},P_{i}),\end{aligned}}}$

لـ i ≥ 1 ، حيث P' هي مشتقة P ، و${\displaystyle \operatorname {rem} (P_{i-1},P_{i})}$هو الجزء المتبقي من التقسيم الإقليدي لـ${\displaystyle P_{i-1}}$بواسطة${\displaystyle P_{i}.}$طول متتالية ستورم هو على الأكثر درجة P.

عدد تغيرات الإشارة عند ξ لمتتالية ستورم لـ P هو عدد تغيرات الإشارة (مع تجاهل الأصفار) في متتالية الأعداد الحقيقية

${\displaystyle P_{0}(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots .}$

يُشار إلى هذا العدد من تغيرات الإشارة هنا بـ V ( ξ ) .

تنص نظرية ستورم على أنه إذا كانت P متعددة حدود خالية من المربعات ، فإن عدد الجذور الحقيقية المختلفة لـ P في الفترة نصف المفتوحة ( a , b ] هو V ( a ) - V ( b ) (حيث a و b عددان حقيقيان بحيث a < b ). ^{[ 1 ]}

تُعمَّم هذه النظرية على فترات غير محدودة بتعريف إشارة كثيرة الحدود عند +∞ على أنها إشارة معاملها الرئيسي (أي معامل الحد ذي أعلى درجة). أما عند –∞، فتكون إشارة كثيرة الحدود هي إشارة معاملها الرئيسي لكثيرة الحدود ذات الدرجة الزوجية، والعكس صحيح لكثيرة الحدود ذات الدرجة الفردية.

في حالة كثير الحدود غير الخالي من المربعات، إذا لم يكن a أو b جذرًا متعددًا لـ p ، فإن V ( a ) − V ( b ) هو عدد الجذور الحقيقية المختلفة لـ P.

برهان النظرية هو كما يلي: عندما تزداد قيمة x من a إلى b ، فقد تمر بصفر ما.${\displaystyle P_{i}}$( i > 0 )؛ عندما يحدث هذا، يكون عدد تغيرات الإشارة لـ${\displaystyle (P_{i-1},P_{i},P_{i+1})}$لا يتغير. عندما يمر x بجذر من${\displaystyle P_{0}=P,}$عدد الاختلافات في الإشارة لـ${\displaystyle (P_{0},P_{1})}$تتناقص من 1 إلى 0. هذه هي القيم الوحيدة لـ x التي قد تتغير فيها بعض الإشارات.

لنفترض أننا نريد إيجاد عدد الجذور في نطاق معين لكثير الحدود${\displaystyle p(x)=x^{4}+x^{3}-x-1}$. لذا

${\displaystyle {\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1\end{aligned}}}$

باقي قسمة p0 على p1 في _الفضاء الإقليدي _هو${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$وبضربها في -1 نحصل على

${\displaystyle p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}}$.

ثم بقسمة _p1 على p2 وضرب الباقي في -1 ، نحصل _على

${\displaystyle p_{3}(x)=-32x-64}$.

بقسمة p2 _على p3 وضرب الباقي في -1 ، نحصل _على

${\displaystyle p_{4}(x)=-{\tfrac {3}{16}}}$.

وبما أن هذا ثابت، فإن هذا ينهي حساب متتالية ستورم.

لإيجاد عدد الجذور الحقيقية لـ${\displaystyle p_{0}}$يجب تقييم متواليات إشارات هذه كثيرات الحدود عند −∞ و ∞ ، وهي على التوالي (+, −, +, +, −) و (+, +, +, −, −) .

${\displaystyle V(-\infty ) -V(+\infty )=3-1=2,}$

حيث يشير V إلى عدد تغيرات الإشارة في المتتالية، مما يدل على أن p له جذران حقيقيان.

يمكن التحقق من ذلك بملاحظة أن p ( x ) يمكن تحليلها إلى ( x² ^- 1)( x² + x + 1) ، حيث يمتلك العامل الأول الجذرين -1 و 1 ، بينما لا يمتلك العامل الثاني ^أي جذور حقيقية. وتنتج هذه النتيجة الأخيرة من الصيغة التربيعية ، وكذلك من نظرية ستورم، التي تُعطي متتاليات الإشارات (+, -, -) عند -∞ و (+, +, -) عند +∞ .

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

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

${\displaystyle P_{0},P_{1},\dots ,P_{m}}$

بحيث

• تتناقص الدرجات بعد الدرجة الأولى:${\displaystyle \deg P_{i}<\deg P_{i-1}}$for i = 2, ..., m ;
• ${\displaystyle P_{m}}$ليس لها جذر حقيقي أو ليس لها تغيرات في الإشارة بالقرب من جذورها الحقيقية.
• إذا كان P _i ( ξ ) = 0 لـ 0 < i < m و ξ عدد حقيقي، فإن P _{i −1} ( ξ ) P _{i + 1} ( ξ ) < 0 .

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

عند حساب متتالية ستورم الأصلية باستخدام القسمة الإقليدية، قد يحدث أن يصادف المرء متعددة حدود لها عامل لا يكون سالباً أبداً، مثل${\displaystyle x^{2}}$أو${\displaystyle x^{2}+1}$في هذه الحالة، إذا استمر الحساب باستبدال متعددة الحدود بناتج قسمتها على العامل غير السالب، نحصل على متتالية ستورم المعممة، والتي يمكن استخدامها أيضًا لحساب عدد الجذور الحقيقية، لأن برهان نظرية ستورم لا يزال ساريًا (بسبب الشرط الثالث). قد يُبسط هذا الحساب أحيانًا، على الرغم من صعوبة إيجاد عوامل غير سالبة كهذه عمومًا، باستثناء القوى الزوجية لـ x .

في الجبر الحاسوبي ، تكون معاملات كثيرات الحدود التي يتم النظر فيها صحيحة، أو يمكن تحويلها لتصبح ذات معاملات صحيحة. تحتوي متتالية ستورم لكثيرة حدود ذات معاملات صحيحة عمومًا على كثيرات حدود معاملاتها ليست صحيحة (انظر المثال أعلاه).

لتجنب العمليات الحسابية على الأعداد النسبية ، تتمثل إحدى الطرق الشائعة في استبدال القسمة الإقليدية بالقسمة الزائفة لحساب القواسم المشتركة الكبرى لكثيرات الحدود . وهذا يعني استبدال متتالية الباقي في خوارزمية القسمة الإقليدية بمتتالية باقي زائفة، وهي متتالية${\displaystyle p_{0},\ldots ,p_{k}}$كثيرات الحدود التي تحتوي على ثوابت${\displaystyle a_{i}}$و${\displaystyle b_{i}}$بحيث${\displaystyle b_{i}p_{i+1}}$هو الجزء المتبقي من التقسيم الإقليدي لـ${\displaystyle a_{i}p_{i-1}}$بواسطة${\displaystyle p_{i}.}$(تُحدد الأنواع المختلفة من متواليات الباقي الزائفة من خلال اختيار${\displaystyle a_{i}}$و${\displaystyle b_{i};}$عادة،${\displaystyle a_{i}}$تم اختيارها لعدم إدخال المقامات أثناء القسمة الإقليدية، و${\displaystyle b_{i}}$(وهو قاسم مشترك لمعاملات الباقي الناتج؛ انظر إلى متتالية الباقي الزائف لمزيد من التفاصيل.)

على سبيل المثال، تُعتبر متتالية الباقي في خوارزمية إقليدس متتالية باقي زائفة مع${\displaystyle a_{i}=b_{i}=1}$لكل i ، وتكون متتالية ستورم لكثير الحدود متتالية شبه باقية مع${\displaystyle a_{i}=1}$و${\displaystyle b_{i}=-1}$لكل i .

تم تصميم العديد من متواليات الباقي الزائف لحساب القواسم المشتركة الكبرى لكثيرات الحدود ذات المعاملات الصحيحة دون إدخال المقامات (انظر متوالية الباقي الزائف ). ويمكن تحويلها جميعًا إلى متواليات ستورم معممة عن طريق اختيار إشارة${\displaystyle b_{i}}$أن يكون عكس علامة${\displaystyle a_{i}.}$وهذا يسمح باستخدام نظرية ستورم مع متواليات الباقي الزائفة.

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

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

يُعدّ عزل الجذور مفيدًا أيضًا في العمليات الحسابية مع الأعداد الجبرية . وللعمليات الحسابية مع الأعداد الجبرية، تتمثل إحدى الطرق الشائعة في تمثيلها كزوج من متعددة الحدود التي يكون العدد الجبري جذرًا لها، وفترة عزل. على سبيل المثال${\displaystyle {\sqrt {2}}}$يمكن تمثيلها بشكل لا لبس فيه بواسطة${\displaystyle (x^{2}-2,[0,2]).}$

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

لعزل الجذور الحقيقية، يبدأ المرء من فترة زمنية${\displaystyle (a,b]}$تحتوي على جميع الجذور الحقيقية، أو الجذور ذات الأهمية (غالبًا، وخاصة في المسائل الفيزيائية، تكون الجذور الموجبة فقط هي المهمة)، ويتم حسابها${\displaystyle V(a)}$و${\displaystyle V(b).}$لتحديد هذه الفترة الابتدائية، يمكن استخدام حدود على حجم الجذور (انظر خصائص جذور كثيرات الحدود §  حدود على جذور كثيرات الحدود (المركبة) ). ثم، يتم تقسيم هذه الفترة إلى قسمين، باختيار قيمة c في منتصفها.${\displaystyle (a,b].}$حساب${\displaystyle V(c)}$يُحدد عدد الجذور الحقيقية في${\displaystyle (a,c]}$و${\displaystyle (c,b],}$ويمكن تكرار العملية نفسها على كل فترة فرعية. عند مصادفة فترة لا تحتوي على أي جذر، يمكن استبعادها من قائمة الفترات المراد دراستها. وعند مصادفة فترة تحتوي على جذر واحد فقط، يمكن التوقف عن قسمتها، لأنها فترة عزل. وتتوقف العملية في النهاية عندما لا يتبقى سوى فترات العزل.

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

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

ليكن P ( x ) و Q ( x ) كثيرتي حدود بمعاملات حقيقية بحيث لا يوجد لـ P و Q جذر مشترك، ولا يوجد لـ P جذور متعددة. بعبارة أخرى، P و P'Q كثيرتا حدود أوليان فيما بينهما . لا يؤثر هذا القيد فعليًا على عمومية ما يلي، إذ تسمح حسابات القاسم المشترك الأكبر (GCD) باختزال الحالة العامة إلى هذه الحالة، وتكون تكلفة حساب متتالية ستورم مساوية لتكلفة حساب القاسم المشترك الأكبر.

لنفترض أن W ( a ) يرمز إلى عدد تغيرات الإشارة عند النقطة a لمتتالية ستورم المعممة التي تبدأ من P و P'Q . إذا كان a < b عددين حقيقيين، فإن W ( a ) - W ( b ) هو عدد جذور P في الفترة${\displaystyle (a,b]}$بحيث يكون Q ( a ) > 0 مطروحًا منه عدد الجذور في نفس الفترة التي يكون فيها Q ( a ) < 0. وبدمج هذا مع العدد الإجمالي لجذور P في نفس الفترة، كما هو موضح في نظرية ستورم، نحصل على عدد جذور P التي يكون فيها Q ( a ) > 0 وعدد جذور P التي يكون فيها Q ( a ) < 0. ^{[ 1 ]}

• باسو، سوغاتا؛ بولاك، ريتشارد ؛ روي، ماري فرانسواز (2006). "القسم 2.2.2". خوارزميات في الهندسة الجبرية الحقيقية (  الطبعة الثانية). سبرينغر . الصفحات 52-57 . ISBN  978-3-540-33098-1.
• شتورم، جاك تشارلز فرانسوا (1829). "ذاكرة حول دقة المعادلات الرقمية". نشرة العلوم دي Férussac . 11 : 419 - 425.
• سيلفستر، ج. ج. (1853). "حول نظرية العلاقات الاقترانية بين دالتين تكامليتين كسريتين، تتضمن تطبيقًا على نظرية دوال ستورم، ونظرية أكبر مقياس جبري مشترك" . معاملات الجمعية الملكية بلندن ، 143 : 407-548 . doi : 10.1098/rstl.1853.0018 . JSTOR 108572 . 
• توماس، جوزيف ميلر (1941). " نظرية ستورم للجذور المتعددة". مجلة الرياضيات الوطنية . 15 (8): 391-394 . doi : 10.2307/3028551 . JSTOR 3028551. MR 0005945 .  
• هايندل، لي إي. (1971). "خوارزميات حسابية للأعداد الصحيحة لتحديد الأصفار الحقيقية لكثيرات الحدود". وقائع ندوة ACM الثانية حول المعالجة الرمزية والجبرية - SYMSAC '71 . ص  415. doi : 10.1145/800204.806312 . MR 0300434. S2CID 9971778 .  
• دي مورا، ليوناردو؛ باسْمور، غرانت أولني (2013). "الحساب في الامتدادات الحقيقية المغلقة المتناهية الصغر والمتسامية للأعداد النسبية" . الاستدلال الآلي - CADE-24 . سلسلة محاضرات في علوم الحاسوب. المجلد  7898. الصفحات 178-192 . doi : 10.1007/978-3-642-38574-2_12 . ISBN  978-3-642-38573-5. S2CID 9308312 . 
• بانتون، دون ب.؛ فيرديني، ويليام أ. (1981). "برنامج فورتران لتطبيق نظرية ستورم في حساب معدلات العائد الداخلي". مجلة التحليل الكمي المالي ، 16 (3): 381-388 . doi : 10.2307/2330245 . JSTOR 2330245. S2CID 154334522 .  
• أكريتاس، ألكيفيديس ج . (1982). "تأملات في زوج من النظريات لبودان وفورييه". مجلة الرياضيات 55 (5): 292-298 . doi : 10.2307/2690097 . JSTOR 2690097. MR 0678195 .  
• بيدرسن، بول (1991). "نظرية ستورم متعددة المتغيرات". في: ماتسون، هارولد ف.؛ مورا، تيو؛ راو، تي آر إن (محررون). الجبر التطبيقي، والخوارزميات الجبرية، ورموز تصحيح الأخطاء، الندوة الدولية التاسعة، AAECC-9، نيو أورليانز، لويزيانا، الولايات المتحدة الأمريكية، 7-11 أكتوبر 1991، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  539. برلين: سبرينغر. الصفحات 318-332 . doi : 10.1007/3-540-54522-0_120 . ISBN  978-3-540-54522-4MR 1229329​​ 
• ياب، تشي (2000). المشكلات الأساسية في الجبر الخوارزمي . مطبعة جامعة أكسفورد . ISBN 0-19-512516-9.
• رحمن، كيو آي؛ شميسر، جي. (2002). النظرية التحليلية لكثيرات الحدود . سلسلة دراسات الجمعية الرياضية بلندن. سلسلة جديدة. المجلد  26. أكسفورد: مطبعة جامعة أكسفورد . ISBN 0-19-853493-0. Zbl 1072.30006 . 
• باومول، ويليام. الديناميات الاقتصادية ، الفصل 12، القسم 3، "المعلومات النوعية عن الجذور الحقيقية"
• DG Hook و PR McAree، "استخدام متواليات ستورم لتحديد الجذور الحقيقية لمعادلات كثير الحدود" في Graphic Gems I (تحرير A. Glassner)، Academic Press، ص  416 - 422، 1990.