نظام المعادلات متعددة الحدود

المعادلة المثلثية هي معادلة g = 0 حيث g دالة مثلثية . يمكن تحويل هذه المعادلة إلى نظام متعدد الحدود عن طريق فك دوال الجيب وجيب التمام فيها (باستخدام صيغ المجموع والفرق )، واستبدال sin( x ) و cos( x ) بمتغيرين جديدين s و c ^، وإضافة المعادلة الجديدة s² + c² - ¹ = 0 .

على سبيل المثال، بسبب الهوية

${\displaystyle \cos(3x)=4\cos ^{3}(x)-3\cos(x),}$

حل المعادلة

${\displaystyle \sin ^{3}(x)+\cos(3x)=0}$

يكافئ حل نظام كثير الحدود

${\displaystyle {\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}}$

لكل حل ( c ₀ , s ₀ ) لهذا النظام، يوجد حل وحيد x للمعادلة بحيث يكون 0 ≤ x < 2 π .

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

عند حل نظام على حقل منتهٍ k يحتوي على q عنصرًا، يكون الاهتمام الأساسي منصبًا على الحلول في k . وبما أن عناصر k هي بالضبط حلول المعادلة x ^q – x = 0 ، فإنه يكفي، لتقييد الحلول في k ، إضافة المعادلة x _i ^q – x _i = 0 لكل متغير x _i . 

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

على سبيل المثال، إذا كان النظام يحتوي على${\displaystyle {\sqrt {2}}}$، يتم الحصول على نظام على الأعداد النسبية عن طريق جمع المعادلة r ₂ ² – 2 = 0 واستبدالها${\displaystyle {\sqrt {2}}}$بواسطة r ₂ في المعادلات الأخرى.

في حالة الحقل المنتهي، يسمح نفس التحويل دائمًا بافتراض أن الحقل k له رتبة أولية.

الطريقة المعتادة لتمثيل الحلول هي من خلال سلاسل منتظمة صفرية الأبعاد. تتكون هذه السلسلة من متتالية من كثيرات _{الحدود f₁} ( x₁ ) , f₂ ( x₁ , _x₂ ) , ... , fₙ ( _x₁ , ... _, xₙ ) _بحيث ، لكل i بحيث ₁ ≤ i ≤ _n

• f _i عبارة عن متعدد الحدود في x ₁ ، ... ، x _i فقط ، والذي له درجة d _i > 0 في x _i ؛
• معامل x _i ^{d _i} في f _i هو متعدد الحدود في x ₁ ، ... ، x _{i −1} والذي ليس له أي جذر مشترك مع f ₁ ، ... ، f _{i − 1} .

ترتبط بسلسلة منتظمة كهذه منظومة معادلات مثلثة

${\displaystyle {\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}}$

تُستخلص حلول هذا النظام بحل المعادلة الأولى أحادية المتغير، ثم تعويض الحلول في المعادلات الأخرى، ثم حل المعادلة الثانية التي أصبحت الآن أحادية المتغير، وهكذا. ويشير تعريف السلاسل المنتظمة إلى أن المعادلة أحادية المتغير المُستنتجة من _fᵢ لها الدرجة dᵢ _، وبالتالي فإن للنظام d₁ ... dₙ _حلاً ، بشرط عدم وجود جذر متعدد في عملية الحل هذه ( _{النظرية} الأساسية في الجبر ).

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

${\displaystyle {\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}}$

هناك العديد من الخوارزميات لحساب التحلل المثلثي لنظام متعدد الحدود عشوائي (ليس بالضرورة صفري الأبعاد) ^{[ 4 ]} إلى سلاسل منتظمة (أو أنظمة شبه جبرية منتظمة ).

يوجد أيضًا خوارزمية خاصة بالحالة الصفرية الأبعاد، وهي منافسة للخوارزميات المباشرة في هذه الحالة. وتتمثل هذه الخوارزمية في حساب أساس غروبنر للترتيب المعجمي العكسي المتدرج (grevlex) أولًا ، ثم استنتاج أساس غروبنر المعجمي باستخدام خوارزمية FGLM ^{[ 5 ] ، وأخيرًا تطبيق خوارزمية Lextriangular [ 6 ]} .

يُعدّ هذا التمثيل للحلول مناسبًا تمامًا للمعاملات في حقل منتهٍ. مع ذلك، بالنسبة للمعاملات النسبية، يجب مراعاة جانبين:

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

تم حل المشكلة الأولى بواسطة داهان وشوست: ^{[ 7 ] [ 8 ]} من بين مجموعات السلاسل المنتظمة التي تمثل مجموعة معينة من الحلول، توجد مجموعة تكون فيها المعاملات محدودة بشكل صريح بدلالة حجم نظام الإدخال، مع حد شبه مثالي. هذه المجموعة، المسماة بالتفكيك المتساوي الإسقاط ، تعتمد فقط على اختيار الإحداثيات. وهذا يسمح باستخدام الطرق المعيارية لحساب التفكيك المتساوي الإسقاط بكفاءة. ^{[ 9 ]}

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

التمثيل النسبي أحادي المتغير أو RUR هو تمثيل لحلول نظام متعدد الحدود ذي بُعد صفري على الأعداد النسبية، وقد قدمه ف. روييه. ^{[ 10 ]}

يتكون RUR لنظام ذي أبعاد صفرية من تركيبة خطية x ₀ من المتغيرات، تسمى متغير الفصل ، ونظام من المعادلات ^{[ 11 ].}

${\displaystyle {\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}}$

حيث h عبارة عن متعدد حدود أحادي المتغير في x 0 _من الدرجة D و g ₀ ، ... ، g _n هي متعددات حدود أحادية المتغير في x ₀ من الدرجة أقل من D.

بالنظر إلى نظام متعدد الحدود ذي بُعد صفري على الأعداد النسبية، فإن RUR له الخصائص التالية.

• جميع التراكيب الخطية للمتغيرات باستثناء عدد محدود منها هي متغيرات فصل.
• عند اختيار المتغير الفاصل، يكون RUR موجودًا وفريدًا. على وجه الخصوص، يتم تعريف h و g _i بشكل مستقل عن أي خوارزمية لحسابهما.
• حلول النظام تتوافق بشكل فردي مع جذور h وتعدد كل جذر من جذور h يساوي تعدد الحل المقابل.
• يتم الحصول على حلول النظام عن طريق استبدال جذور h في المعادلات الأخرى.
• إذا لم يكن للدالة h أي جذر مضاعف، فإن g ₀ هي مشتقة الدالة h .

على سبيل المثال، بالنسبة للنظام المذكور في القسم السابق، يُعد كل تركيب خطي للمتغير، باستثناء مضاعفات x و y و x + y ، متغيرًا فاصلًا. إذا اخترنا t = x – y / 2 كمتغير فاصل ، فإن RUR هو

${\displaystyle {\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}}$

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

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

علاوة على ذلك، يمكن تحليل متعددة الحدود أحادية المتغير h ( x₀ ₎ للمعادلة RUR، مما يُعطي معادلة RUR لكل عامل غير قابل للاختزال. وهذا يُوفر التحليل الأولي للمثالي المُعطى (أي التحليل الأساسي لجذر المثالي). عمليًا، يُنتج هذا مخرجات بمعاملات أصغر بكثير، خاصةً في حالة الأنظمة ذات التعددية العالية.

على عكس التفكيكات المثلثية والتفكيكات متساوية الإسقاط، فإن RUR غير معرف في بُعد موجب.

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

ومع ذلك، هناك طريقتان تستحقان الذكر هنا.

• يمكن استخدام طريقة نيوتن إذا كان عدد المعادلات مساويًا لعدد المتغيرات. لا تُمكّن هذه الطريقة من إيجاد جميع الحلول، ولا من إثبات عدم وجود حل. لكنها سريعة جدًا عند البدء من نقطة قريبة من الحل. لذا، فهي أداة أساسية لطريقة الاستمرار بالتماثل الموصوفة أدناه.
• نادرًا ما تُستخدم تقنيات التحسين لحل أنظمة المعادلات متعددة الحدود، لكنها نجحت، في حوالي عام 1970، في إثبات أن نظامًا من 81 معادلة تربيعية في 56 متغيرًا ليس نظامًا غير متسق. ^{[ 12 ]} وباستخدام الطرق الأخرى المعروفة، لا يزال هذا الأمر خارج نطاق إمكانيات التكنولوجيا الحديثة، حتى عام 2022.تعتمد هذه الطريقة ببساطة على تقليل مجموع مربعات المعادلات. إذا وُجد الصفر كقيمة صغرى محلية، فهذا يعني أنه حلٌّ. تُجدي هذه الطريقة نفعًا مع الأنظمة ذات القيم المُفرطة، ولكنها تُخرج معلومات فارغة إذا كانت جميع القيم الصغرى المحلية المُكتشفة موجبة.

هذه طريقة شبه عددية تفترض أن عدد المعادلات يساوي عدد المتغيرات. هذه الطريقة قديمة نسبياً، لكنها شهدت تحسينات كبيرة في العقود الأخيرة. ^{[ 13 ]}

تنقسم هذه الطريقة إلى ثلاث خطوات. أولاً، يتم حساب حد أعلى لعدد الحلول. يجب أن يكون هذا الحد دقيقًا قدر الإمكان. لذلك، يتم حسابه باستخدام أربع طرق مختلفة على الأقل، ويتم اختيار أفضل قيمة، ولتكن${\displaystyle N}$، يتم الاحتفاظ به.

في الخطوة الثانية، النظام${\displaystyle g_{1}=0,\,\ldots ,\,g_{n}=0}$يتم توليد معادلات متعددة الحدود التي تحتوي بالضبط على${\displaystyle N}$حلول يسهل حسابها. هذا النظام الجديد لديه نفس العدد${\displaystyle n}$من المتغيرات ونفس العدد${\displaystyle n}$من المعادلات ونفس البنية العامة للنظام المراد حله،${\displaystyle f_{1}=0,\,\ldots ,\,f_{n}=0}$.

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

${\displaystyle (1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0}$.

تتمثل عملية الاستمرار بالتماثل في تشويه المعلمة${\displaystyle t}$من 0 إلى 1، ثم اتبع${\displaystyle N}$الحلول أثناء هذا التشوه. وهذا يعطي الحلول المطلوبة لـ${\displaystyle t=1}$يعني ما يلي أنه إذا${\displaystyle t_{1}<t_{2}}$، الحلول لـ${\displaystyle t=t_{2}}$يتم استنتاجها من حلول لـ${\displaystyle t=t_{1}}$باستخدام طريقة نيوتن. تكمن الصعوبة هنا في اختيار قيمة مناسبة لـ${\displaystyle t_{2}-t_{1}:}$إذا كانت قيمة كبيرة جدًا، فقد يكون تقارب نيوتن بطيئًا، بل وقد ينتقل من مسار حل إلى آخر. أما إذا كانت صغيرة جدًا، فإن عدد الخطوات يبطئ من سرعة الطريقة.

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

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

• تقوم طريقة Aberth ، المطبقة في MPSolve، بحساب جميع الجذور المركبة بأي دقة.
• خوارزمية أوسبنسكي لكولينز وأكريتاس، ^{[ 14 ]} التي حسّنها رويلييه وزيمرمان ^{[ 15 ]} والمبنية على قاعدة ديكارت للإشارات . تحسب هذه الخوارزمية الجذور الحقيقية، المعزولة في فترات ذات عرض صغير اختياري. وهي مُطبقة في برنامج مابل (الدالتان fsolve و RootFinding[Isolate] ).