طريقة غريف

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

ليكن p ( x ) متعدد حدود من الدرجة n

${\displaystyle p(x)=(x-x_{1})\cdots (x-x_{n}).}$

ثم

${\displaystyle p(-x)=(-1)^{n}(x+x_{1})\cdots (x+x_{n}).}$

ليكن q ( x ) متعددة الحدود التي لها مربعات${\displaystyle x_{1}^{2},\cdots ,x_{n}^{2}}$كجذورها،

${\displaystyle q(x)=\left(x-x_{1}^{2}\right)\cdots \left(x-x_{n}^{2}\right).}$

ثم يمكننا أن نكتب:

$\begin{aligned}q(x^{2})&=\left(x^{2}-x_{1}^{2}\right)\cdots \left(x^{2}-x_{n}^{2}\right)\\&=(x-x_{1})(x+x_{1})\cdots (x-x_{n})(x+x_{n})\\&=\left\{(x-x_{1})\cdots (x-x_{n})\right\}\times \left\{(x+x_{1})\cdots (x+x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}(-x-x_{1})\cdots (-x-x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}p(-x)\right\}\\&=(-1)^{n}p(x)p(-x)\end{aligned}}}$

يمكن الآن حساب q ( x ) من خلال العمليات الجبرية على معاملات متعددة الحدود p ( x ) فقط. ليكن:

${\displaystyle {\begin{aligned}p(x)&=x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}\\q(x)&=x^{n}+b_{1}x^{n-1}+\cdots +b_{n-1}x+b_{n}\end{aligned}}}$

ثم ترتبط المعاملات بالعلاقة التالية

${\displaystyle b_{k}=(-1)^{k}a_{k}^{2}+2\sum _{j=0}^{k-1}(-1)^{j}\,a_{j}a_{2k-j},\qquad a_{0}=b_{0}=1.}$

لاحظ غريف أنه إذا قام المرء بفصل p ( x ) إلى أجزائه الفردية والزوجية:

${\displaystyle p(x)=p_{e}\left(x^{2}\right)+xp_{o}\left(x^{2}\right),}$

عندئذٍ نحصل على تعبير جبري مبسط لـ q ( x ) :

${\displaystyle q(x)=(-1)^{n}\left(p_{e}(x)^{2}-xp_{o}(x)^{2}\right).}$

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

يؤدي تكرار هذه العملية عدة مرات إلى فصل الجذور وفقًا لقيمها المطلقة. ويؤدي تكرارها k مرة إلى الحصول على متعددة حدود من الدرجة n .

${\displaystyle q^{k}(y)=y^{n}+{a^{k}}_{1}\,y^{n-1}+\cdots +{a^{k}}_{n-1}\,y+{a^{k}}_{n}\,}$

بجذور

${\displaystyle y_{1}=x_{1}^{2^{k}},\,y_{2}=x_{2}^{2^{k}},\,\dots ,\,y_{n}=x_{n}^{2^{k}}.}$

إذا تم فصل مقادير جذور كثيرة الحدود الأصلية بعامل ما${\displaystyle \rho >1}$، إنه،${\displaystyle |x_{k}|\geq \rho |x_{k+1}|}$ثم يتم فصل جذور التكرار رقم k بواسطة عامل نمو سريع

${\displaystyle \rho ^{2^{k}}\geq 1+2^{k}(\rho -1)}$.

ثم يتم استخدام علاقات فيتا

${\displaystyle {\begin{aligned}a_{\;1}^{k}&=-(y_{1}+y_{2}+\cdots +y_{n})\\a_{\;2}^{k}&=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n}\\&\;\vdots \\a_{\;n}^{k}&=(-1)^{n}(y_{1}y_{2}\cdots y_{n}).\end{aligned}}}$

إذا كانت الجذور${\displaystyle x_{1},\dots ,x_{n}}$مفصولة بشكل كافٍ، لنقل بمعامل${\displaystyle \rho >1}$،${\displaystyle |x_{m}|\geq \rho |x_{m+1}|}$ثم القوى المتكررة${\displaystyle y_{1},y_{2},...,y_{n}}$يتم فصل الجذور بواسطة العامل${\displaystyle \rho ^{2^{k}}}$والتي سرعان ما تصبح كبيرة جداً.

يمكن بعد ذلك تقريب معاملات متعددة الحدود المتكررة بواسطة حدها الرئيسي،

${\displaystyle a_{\;1}^{k}\approx -y_{1}}$

${\displaystyle a_{\;2}^{k}\approx y_{1}y_{2}}$وهكذا دواليك،

يعني

${\displaystyle y_{1}\approx -a_{\;1}^{k},\;y_{2}\approx -a_{\;2}^{k}/a_{\;1}^{k},\;\dots \;y_{n}\approx -a_{\;n}^{k}/a_{\;n-1}^{k}.}$

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

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

تُعدّ طريقة غريف الأنسب لكثيرات الحدود ذات الجذور الحقيقية البسيطة، مع إمكانية تكييفها لكثيرات الحدود ذات الجذور والمعاملات المركبة، والجذور ذات التعددية الأعلى. على سبيل المثال، لوحظ ^{[ 2 ]} أنه بالنسبة لجذر${\displaystyle x_{\ell +1}=x_{\ell +2}=\dots =x_{\ell +d}}$مع التعددية d ، الكسور

${\displaystyle \left|{\frac {(a_{\;\ell +i}^{m-1})^{2}}{a_{\;\ell +i}^{m}}}\right|}$يميل إلى${\displaystyle {\binom {d}{i}}}$

ل${\displaystyle i=0,1,\dots ,d}$وهذا يسمح بتقدير بنية التعددية لمجموعة الجذور.

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

تستبدل هذه الطريقة الأعداد بمتسلسلات قوى مقطوعة من الدرجة الأولى، والمعروفة أيضًا بالأعداد الثنائية . ويتم ذلك رمزياً بإدخال "كمية جبرية متناهية الصغر".${\displaystyle \varepsilon }$مع الخاصية المميزة${\displaystyle \varepsilon ^{2}=0}$ثم متعددة الحدود ${\displaystyle p(x+\varepsilon )=p(x)+\varepsilon \,p'(x)}$له جذور${\displaystyle x_{m}-\varepsilon }$، مع قوى

${\displaystyle (x_{m}-\varepsilon )^{2^{k}}=x_{m}^{2^{k}}-\varepsilon \,{2^{k}}\,x_{m}^{2^{k}-1}=y_{m}+\varepsilon \,{\dot {y}}_{m}.}$

وبالتالي قيمة${\displaystyle x_{m}}$يمكن الحصول عليها بسهولة ككسر${\displaystyle x_{m}=-{\tfrac {2^{k}\,y_{m}}{{\dot {y}}_{m}}}.}$

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

يمكن تغيير نطاق كل متعددة حدود في المجال والمدى بحيث يكون المعامل الأول والأخير في متعددة الحدود الناتجة مساويًا للواحد. إذا كان حجم المعاملات الداخلية محدودًا بـ M ، فإن حجم المعاملات الداخلية بعد مرحلة واحدة من تكرار غريف يكون محدودًا بـ${\displaystyle nM^{2}}$بعد k مرحلة، يحصل المرء على الحد${\displaystyle n^{2^{k}-1}M^{2^{k}}}$بالنسبة للمعاملات الداخلية.

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

${\displaystyle c=\alpha \,e^{-2^{k}\,r},}$

أين${\displaystyle \alpha ={\frac {c}{|c|}}}$هو عدد مركب طوله وحدة واحدة و${\displaystyle r=-2^{-k}\log |c|}$هو أمر إيجابي حقيقي. فصل السلطة${\displaystyle 2^{k}}$يؤدي إدخال الأس إلى اختزال القيمة المطلقة لـ c إلى الجذر الثنائي المقابل. ولأن هذا يحافظ على مقدار (تمثيل) المعاملات الأولية، فقد سُميت هذه العملية بإعادة التطبيع.

عملية ضرب عددين من هذا النوع عملية مباشرة، بينما تتم عملية الجمع بعد التحليل إلى عوامل.${\displaystyle c_{3}=c_{1}+c_{2}=|c_{1}|\cdot \left(\alpha _{1}+\alpha _{2}{\tfrac {|c_{2}|}{|c_{1}|}}\right)}$، أين${\displaystyle c_{1}}$يتم اختيار العدد الأكبر من بين العددين، أي${\displaystyle r_{1}<r_{2}}$. هكذا

${\displaystyle \alpha _{3}={\tfrac {s}{|s|}}}$و${\displaystyle r_{3}=r_{1}+2^{-k}\,\log {|s|}}$مع${\displaystyle s=\alpha _{1}+\alpha _{2}\,e^{2^{k}(r_{1}-r_{2})}.}$

المعاملات${\displaystyle a_{0},a_{1},\dots ,a_{n}}$يتم تمثيل المرحلة النهائية k من تكرار غريف، لقيمة كبيرة معقولة لـ k ، بأزواج${\displaystyle (\alpha _{m},r_{m})}$،${\displaystyle m=0,\dots ,n}$من خلال تحديد زوايا الغلاف المحدب لمجموعة النقاط${\displaystyle \{(m,r_{m}):\;m=0,\dots ,n\}}$يمكن تحديد تعدد جذور متعددة الحدود. وبدمج إعادة التطبيع هذه مع تكرار المماس، يمكن استخراج جذور متعددة الحدود الأصلية مباشرةً من المعاملات الموجودة عند زوايا الغلاف.

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

• وايسستين، إريك دبليو. “طريقة غريفي” . عالم الرياضيات .
• مالاجوفيتش، جريجوريو. زوبيلي، خورخي ب. (2001). “تكرار Tangent Graeffe”. الرياضيات الرقمية . 89 (4): 749-782 . سيتيسيركس 10.1.1.44.3611 . دوى : 10.1007/s002110100278 . S2CID 100025 .