طريقة دوراند-كيرنر

في التحليل العددي ، تُعدّ طريقة فايرشتراس ، أو طريقة دوراند-كيرنر ، التي اكتشفها كارل فايرشتراس عام 1891 وأعاد اكتشافها بشكل مستقل دوراند عام 1960 وكيرنر عام 1966، خوارزمية لإيجاد جذور المعادلات متعددة الحدود . ^{[ 1 ]} بعبارة أخرى، يمكن استخدام هذه الطريقة لحل المعادلة f(x) = 0 عدديًا ، حيث f دالة متعددة الحدود معطاة ، ويمكن اعتبارها مُعدّلة بحيث يكون معاملها الرئيسي 1. 

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

لنفترض أن متعددة الحدود f معرفة بـ

${\displaystyle f(x)=x^{4}+ax^{3}+bx^{2}+cx+d}$

لكل x . الأرقام المعروفة a و b و c و d هي المعاملات .

لتكن الأعداد (التي قد تكون مركبة) P و Q و R و S جذور هذه المعادلة f .

${\displaystyle f(x)=(xP)(xQ)(xR)(xS)}$

لكل قيمة x . يمكن عزل القيمة P من هذه المعادلة:

${\displaystyle P=x-{\frac {f(x)}{(xQ)(xR)(xS)}}.}$

لذا إذا تم استخدامها كتكرار نقطة ثابتة

${\displaystyle x_{1}:=x_{0}-{\frac {f(x_{0})}{(x_{0}-Q)(x_{0}-R)(x_{0}-S)}},}$

تتميز هذه الطريقة باستقرارها القوي، حيث أن كل نقطة ابتدائية x₀ ≠ Q أو R أو S _تُعطي بعد تكرار واحد الجذر P = x₁ . علاوة على ذلك، إذا استُبدلت الأصفار Q و R و S بتقريبات q ≈ Q و r ≈ R و s ≈ S ، بحيث لا تساوي q و r و s _قيمة P ، فإن P تظل نقطة ثابتة في تكرار النقطة الثابتة المضطرب.

${\displaystyle x_{k+1}:=x_{k}-{\frac {f(x_{k})}{(x_{k}-q)(x_{k}-r)(x_{k}-s)}},}$

منذ

${\displaystyle P-{\frac {f(P)}{(Pq)(Pr)(Ps)}}=P-0=P.}$

لاحظ أن المقام لا يزال مختلفًا عن الصفر. هذه العملية التكرارية ذات النقطة الثابتة هي عملية انكماش لـ x حول النقطة P.

يكمن مفتاح الطريقة الآن في دمج التكرار ذي النقطة الثابتة لـ P مع تكرارات مماثلة لـ Q و R و S في تكرار متزامن لجميع الجذور.

تهيئة p و q و r و s :

p ₀  := (0.4 + 0.9 i ) ⁰ ,

q ₀  := (0.4 + 0.9 i ) ¹ ,

r ₀  := (0.4 + 0.9 i ) ² ,

s ₀  := (0.4 + 0.9 i ) ³ .

لا يوجد شيء مميز في اختيار 0.4  +  0.9 i باستثناء أنه ليس عددًا حقيقيًا ولا جذرًا للوحدة .

قم بإجراء عمليات الاستبدال لـ n = 1، 2، 3، ...:

${\displaystyle p_{n}=p_{n-1}-{\frac {f(p_{n-1})}{(p_{n-1}-q_{n-1})(p_{n-1}-r_{n-1})(p_{n-1}-s_{n-1})}},}$

${\displaystyle q_{n}=q_{n-1}-{\frac {f(q_{n-1})}{(q_{n-1}-p_{n})(q_{n-1}-r_{n-1})(q_{n-1}-s_{n-1})}},}$

${\displaystyle r_{n}=r_{n-1}-{\frac {f(r_{n-1})}{(r_{n-1}-p_{n})(r_{n-1}-q_{n})(r_{n-1}-s_{n-1})}},}$

${\displaystyle s_{n}=s_{n-1}-{\frac {f(s_{n-1})}{(s_{n-1}-p_{n})(s_{n-1}-q_{n})(s_{n-1}-r_{n})}}.}$

كرر العملية حتى تتوقف الأرقام p و q و r و s عن التغير بشكل أساسي بالنسبة للدقة المطلوبة. عندها تصبح قيمها P و Q و R و S مرتبةً وفقًا للدقة المختارة. وبذلك تكون المشكلة قد حُلت.

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

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

يمكن أيضًا اختيار القيم الأولية لـ p و q و r و s بإجراء آخر، حتى بشكل عشوائي، ولكن بطريقة تضمن

• إنها تقع داخل دائرة ليست كبيرة جدًا تحتوي أيضًا على جذور الدالة f ( x )، على سبيل المثال الدائرة المحيطة بنقطة الأصل بنصف قطر${\displaystyle 1+\max {\big (}|a|,|b|,|c|,|d|{\big )}}$، (حيث 1، a ، b ، c ، d هي معاملات f ( x ))

وذلك

• إنهم ليسوا قريبين جداً من بعضهم البعض،

وهو ما قد يصبح مصدر قلق متزايد مع ازدياد درجة متعددة الحدود.

إذا كانت المعاملات حقيقية وكان لكثير الحدود درجة فردية، فلا بد أن يكون له جذر حقيقي واحد على الأقل. لإيجاد هذا الجذر، استخدم قيمة حقيقية لـ p₀ كقيمة ابتدائية، واجعل q₀ و r₀ ، وهكذا _، أزواجًا مركبة _{مترافقة .} عندئذٍ ، ستحافظ عملية التكرار على هذه الخصائص؛ أي أن pₙ سيكون دائمًا حقيقيًا، و qₙ و rₙ _، وهكذا _، ستكون دائمًا مترافقة. بهذه الطريقة، سيتقارب pₙ إلى جذر حقيقي P. بدلاً _{من ذلك، اجعل جميع} القيم الابتدائية حقيقية؛ وستبقى كذلك.

هذا المثال مأخوذ من مرجع جاكوبي (1992). المعادلة التي تم حلها هي: س³ ^- 3 س² + 3 س - 5 = 0. في التكرارات الأربعة الأولى، تتحرك ^قيم p و q و r بشكل عشوائي ظاهريًا، ولكن بعد ذلك يتم تحديد الجذور بدقة تصل إلى منزلة عشرية واحدة. بعد التكرار الخامس، نحصل على أربع منازل عشرية صحيحة، ويؤكد التكرار السادس اللاحق ثبات الجذور المحسوبة. هذا السلوك العام مميز لهذه الطريقة. لاحظ أيضًا أنه في هذا المثال، تُستخدم الجذور فور حسابها في كل تكرار. بعبارة أخرى، يعتمد حساب كل عمود ثانٍ على قيمة الأعمدة المحسوبة السابقة.

لا.	ص	q	ر
0	+1.0000 + 0.0000i	+0.4000 + 0.9000i	− 0.6500 + 0.7200i
1	+1.3608 + 2.0222i	− 0.3658 + 2.4838i	− 2.3858 − 0.0284i
2	+2.6597 + 2.7137i	+0.5977 + 0.8225i	- 0.6320 - 1.6716i
3	+2.2704 + 0.3880i	+0.1312 + 1.3128i	+0.2821 − 1.5015i
4	+2.5428 − 0.0153i	+0.2044 + 1.3716i	+0.2056 − 1.3721i
5	+2.5874 + 0.0000i	+0.2063 + 1.3747i	+0.2063 − 1.3747i
6	+2.5874 + 0.0000i	+0.2063 + 1.3747i	+0.2063 − 1.3747i

لاحظ أن المعادلة لها جذر حقيقي واحد وزوج واحد من الجذور المركبة المترافقة، وأن مجموع الجذور هو  3.

لكل مجموعة من n من الأعداد المركبة، يوجد متعدد حدود أحادي واحد فقط من الدرجة n يحتوي على هذه الأعداد كجذور له (مع الحفاظ على التكرارات). يُعطى متعدد الحدود هذا بضرب جميع العوامل الخطية المناظرة، أي

${\displaystyle g_{\vec {z}}(X)=(X-z_{1})\cdots (X-z_{n}).}$

تحتوي هذه المعادلة متعددة الحدود على معاملات تعتمد على الأصفار المحددة،

${\displaystyle g_{\vec {z}}(X)=X^{n}+g_{n-1}({\vec {z}})X^{n-1}+\cdots +g_{0}({\vec {z}}).}$

تُعتبر هذه المعاملات، حتى الإشارة، كثيرات الحدود المتناظرة الأولية${\displaystyle \alpha _{1}({\vec {z}}),\dots ,\alpha _{n}({\vec {z}})}$من الدرجات 1، ...، ن .

لإيجاد جميع جذور متعددة الحدود المعطاة${\displaystyle f(X)=X^{n}+c_{n-1}X^{n-1}+\cdots +c_{0}}$مع متجه المعاملات${\displaystyle (c_{n-1},\dots ,c_{0})}$أصبح إيجاد متجه حل لنظام فيتا الآن مكافئًا لإيجاد متجه حل لنظام فيتا.

${\displaystyle {\begin{matrix}c_{0}&=&g_{0}({\vec {z}})&=&(-1)^{n}\alpha _{n}({\vec {z}})&=&(-1)^{n}z_{1}\cdots z_{n}\\c_{1}&=&g_{1}({\vec {z}})&=&(-1)^{n-1}\alpha _{n-1}({\vec {z}})\\&\vdots &\\c_{n-1}&=&g_{n-1}({\vec {z}})&=&-\alpha _{1}({\vec {z}})&=&-(z_{1}+z_{2}+\cdots +z_{n}).\end{matrix}}}$

تُستنتج طريقة دوراند-كيرنر من تطبيق طريقة نيوتن متعددة الأبعاد على هذا النظام. ومن الأسهل جبريًا التعامل مع متطابقات المعاملات هذه باعتبارها متطابقات كثيرات الحدود المقابلة.${\displaystyle g_{\vec {z}}(X)=f(X)}$في طريقة نيوتن، ينظر المرء، بمعلومية متجه ابتدائي معين${\displaystyle {\vec {z}}}$، لمتجه الزيادة${\displaystyle {\vec {w}}}$بحيث${\displaystyle g_{{\vec {z}}+{\vec {w}}}(X)=f(X)}$يتحقق ذلك حتى الحدود من الرتبة الثانية وما فوق في الزيادة. ولذلك يتم حل المتطابقة

${\displaystyle f(X)-g_{\vec {z}}(X)=\sum _{k=1}^{n}{\frac {\partial g_{\vec {z}}(X)}{\partial z_{k}}}w_{k}=-\sum _{k=1}^{n}w_{k}\prod _{j\neq k}(X-z_{j}).}$

إذا كانت الأرقام${\displaystyle z_{1},\dots ,z_{n}}$إذا كانت كثيرات الحدود مختلفة مثنى مثنى، فإنها تشكل أساسًا للفضاء ذي الأبعاد n${\displaystyle \mathbb {C} [X]_{n-1}}$من كثيرات الحدود ذات الدرجة القصوى n − 1. وبالتالي حل  ${\displaystyle {\vec {w}}}$توجد معادلة الزيادة في هذه الحالة. إحداثيات الزيادة${\displaystyle {\vec {w}}}$يتم الحصول عليها ببساطة عن طريق تقييم معادلة الزيادة

${\displaystyle -\sum _{k=1}^{n}w_{k}\prod _{j\neq k}(X-z_{j})=f(X)-\prod _{j=1}^{n}(X-z_{j})}$

عند النقاط${\displaystyle X=z_{k}}$مما ينتج عنه

${\displaystyle -w_{k}\prod _{j\neq k}(z_{k}-z_{j})=-w_{k}g_{\vec {z}}'(z_{k})=f(z_{k})}$، إنه${\displaystyle w_{k}=-{\frac {f(z_{k})}{\prod _{j\neq k}(z_{k}-z_{j})}}.}$

في حلقة القسمة (الجبر) لفئات البواقي modulo ƒ ( X )، يُعرّف الضرب في X تشاكلاً داخلياً تكون أصفار ƒ ( X ) هي قيمه الذاتية ذات التعددية المناظرة. باختيار أساس، يُمثَّل عامل الضرب بمصفوفة معاملاته A ، وهي المصفوفة المرافقة لـ ƒ ( X ) لهذا الأساس.

بما أن كل متعددة حدود يمكن اختزالها بتردد ƒ ( X ) إلى متعددة حدود من الدرجة n − 1 أو أقل، يمكن تعريف فضاء فئات البواقي بأنه فضاء متعددات الحدود من الدرجة n − 1. ويمكن أخذ أساس خاص بالمسألة من استيفاء لاغرانج كمجموعة من n متعددة الحدود    

${\displaystyle b_{k}(X)=\prod _{1\leq j\leq n,\;j\neq k}(X-z_{j}),\quad k=1,\dots ,n,}$

أين${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$هي أعداد مركبة مختلفة مثنى مثنى. لاحظ أن دوال النواة لاستيفاء لاغرانج هي${\displaystyle L_{k}(X)={\frac {b_{k}(X)}{b_{k}(z_{k})}}}$.

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

${\displaystyle X\cdot b_{k}(X)\mod f(X)=X\cdot b_{k}(X)-f(X)}$	${\displaystyle =\sum _{j=1}^{n}{\Big (}z_{j}\cdot b_{k}(z_{j})-f(z_{j}){\Big )}\cdot {\frac {b_{j}(X)}{b_{j}(z_{j})}}}$
	${\displaystyle =z_{k}\cdot b_{k}(X)+\sum _{j=1}^{n}w_{j}\cdot b_{j}(X)}$،

أين${\displaystyle w_{j}=-{\frac {f(z_{j})}{b_{j}(z_{j})}}}$إليكم آخر التحديثات المتعلقة بشارع فايرشتراس.

وبالتالي فإن المصفوفة المصاحبة لـ ƒ ( X ) هي

${\displaystyle A=\mathrm {diag} (z_{1},\dots ,z_{n})+{\begin{pmatrix}1\\\vdots \\1\end{pmatrix}}\cdot \left(w_{1},\dots ,w_{n}\right).}$

من حالة المصفوفة المنقولة لنظرية دائرة غيرشغورين، يتبين أن جميع القيم الذاتية لـ A ، أي جميع جذور ƒ ( X )، تقع ضمن اتحاد الأقراص${\displaystyle D(a_{k,k},r_{k})}$بنصف قطر${\displaystyle r_{k}=\sum _{j\neq k}{\big |}a_{j,k}{\big |}}$.

هنا يمتلك المرء${\displaystyle a_{k,k}=z_{k}+w_{k}}$لذا فإن المراكز هي التكرارات التالية لتكرار فايرشتراس، وأنصاف الأقطار${\displaystyle r_{k}=(n-1)\left|w_{k}\right|}$التي هي مضاعفات لتحديثات فايرشتراس. إذا كانت جذور ƒ ( X ) معزولة جيدًا (بالنسبة للدقة الحسابية) والنقاط${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$إذا كانت هذه القيم قريبة بما يكفي من هذه الجذور، فستصبح جميع الأقراص منفصلة، ​​بحيث يحتوي كل قرص على صفر واحد فقط. وستكون نقاط منتصف الدوائر أقرب إلى الأصفار.

كل مصفوفة مترافقة${\displaystyle TAT^{-1}}$المصفوفة A هي أيضًا مصفوفة مصاحبة لـ ƒ ( X ). اختيار T كمصفوفة قطرية لا يؤثر على بنية A. الجذر القريب من${\displaystyle z_{k}}$يحتوي على أي دائرة معزولة مركزها${\displaystyle z_{k}}$بغض النظر عن T. اختيار المصفوفة القطرية المثلى T لكل مؤشر يؤدي إلى تقديرات أفضل (انظر المرجع Petkovic et al. 1995).

يشير الارتباط بين متسلسلة تايلور وطريقة نيوتن إلى أن المسافة من${\displaystyle z_{k}+w_{k}}$إلى الجذر المقابل يكون من رتبة${\displaystyle O{\big (}|w_{k}|^{2}{\big )}}$إذا كان الجذر معزولًا جيدًا عن الجذور المجاورة وكان التقريب قريبًا بما فيه الكفاية من الجذر، فإن طريقة نيوتن تتقارب تربيعيًا بعد أن يصبح التقريب قريبًا ؛ أي أن الخطأ يتضاعف تربيعيًا مع كل خطوة (مما يقلل الخطأ بشكل كبير عندما يصبح أقل من 1). أما في حالة طريقة دوراند-كيرنر، فيكون التقارب تربيعيًا إذا كان المتجه${\displaystyle {\vec {z}}=(z_{1},\dots ,z_{n})}$يقترب من تبديل ما لمتجه جذور الدالة f .

للوصول إلى استنتاج التقارب الخطي، توجد نتيجة أكثر تحديدًا (انظر المرجع Petkovic et al. 1995). إذا كان المتجه الأولي${\displaystyle {\vec {z}}}$وناقل تحديثات فايرشتراسه${\displaystyle {\vec {w}}=(w_{1},\dots ,w_{n})}$يحقق عدم المساواة

${\displaystyle \max _{1\leq k\leq n}|w_{k}|\leq {\frac {1}{5n}}\min _{1\leq j<k\leq n}|z_{k}-z_{j}|,}$

إذن، ينطبق هذا التباين أيضًا على جميع التكرارات، وجميع أقراص التضمين.${\displaystyle D{\big (}z_{k}+w_{k},(n-1)|w_{k}|{\big )}}$تكون منفصلة، ​​ويتحقق التقارب الخطي بمعامل انكماش قدره 1/2. علاوة على ذلك، يمكن في هذه الحالة اختيار أقراص التضمين على النحو التالي:

${\displaystyle D\left(z_{k}+w_{k},{\tfrac {1}{4}}|w_{k}|\right),\quad k=1,\dots ,n,}$

يحتوي كل منها على صفر واحد بالضبط للدالة f .

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

• ويرشتراس، كارل (1891). "لا يوجد أي وقت مضى، يمكن أن يكون هناك سبب منطقي لوظيفة واحدة من أفضل المنتجات التي يمكن أن تكون منتجًا خطيًا من وظائف التصميم" . Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin . مؤرشفة من الأصلي بتاريخ 2013-11-02 . تم الاسترجاع 2013/10/31 .
• دوراند، إي. (1960). “المعادلات من النوع F ( x )  =  0: جذور متعددة الحدود”. في ماسون؛ وآخرون  . (محرران). الحلول الرقمية للمعادلات الجبرية . المجلد.  1.
• كيرنر، إيمو أو. (1966). "Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen". الرياضيات الرقمية . 8 (3): 290-294 . دوى : 10.1007 / BF02162564 . S2CID 115307022 . 
• بريشيتش، ماريكا (1980). "نظرية تقارب لطريقة التحديد المتزامن لجميع أصفار متعددة الحدود" (ملف PDF) . منشورات المعهد الرياضي . السلسلة الجديدة. 28 (42): 158-168 .
• بيتكوفيتش، إم إس، كارستنسن، سي، وتراجكوفيتش، إم (1995). "صيغة فايرشتراس وطرق إيجاد الأصفار". الرياضيات العددية . 69 (3): 353-372 . CiteSeerX 10.1.1.53.7516 . doi : 10.1007/s002110050097 . S2CID 18594004 .  {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
• بو جاكوبي، Nulpunkter for polynomier ، CAE-nyt (دورية لـ Dansk CAE Gruppe [مجموعة CAE الدنماركية])، 1988.
• أغنيث كنودسن، Numeriske Metoder (ملاحظات المحاضرة)، Københavns Teknikum.
• بو جاكوبي، Numerisk løsning af ligninger ، Bygningsstatiske meddelelser (نشرته الجمعية الدنماركية للعلوم والهندسة الإنشائية) المجلد 63 رقم. 3-4، 1992، ص  83-105.
• جوردون، كزافييه (1996). Combinatoire، الخوارزمية وهندسة متعددات الحدود . باريس: مدرسة البوليتكنيك. مؤرشفة من الأصلي بتاريخ 28-10-2006 . تم الاسترجاع 2006-08-22 .
• فيكتور بان (مايو 2002): إيجاد جذور كثيرات الحدود أحادية المتغير بدقة حسابية أقل ومعدلات تقارب أعلى . تقرير فني، جامعة مدينة نيويورك
• نيومير، أرنولد (2003). "تضمين مجموعات أصفار كثيرات الحدود" . مجلة الرياضيات الحسابية والتطبيقية . 156 (2): 389-401 . Bibcode : 2003JCoAM.156..389N . doi : 10.1016/S0377-0427(03)00380-7 .
• جان فيرشيلد، طريقة فايرشتراس (المعروفة أيضًا باسم طريقة دوراند-كيرنر) ، 2003.
• بيرنهارد رينكه، ديرك شلايشر، ومايكل ستول، " مكتشف جذور Weierstrass ليس متقاربًا بشكل عام "، 2020
  • بيرنهارد رينكه، ديرك شلايشر ومايكل ستول: "إن أداة البحث عن الجذر Weierstrass-Durand-Kerner ليست متقاربة بشكل عام"، Math. شركات. المجلد 92 (2023)، الصفحات 839-866. دوي: https://doi.org/10.1090/mcom/3783 .

• Ada Generic_Roots باستخدام طريقة دوراند-كيرنر (أرشيف) - تطبيق مفتوح المصدر بلغة Ada
• جذور كثيرات الحدود — تطبيق مفتوح المصدر بلغة جافا
• استخراج الجذور من كثيرات الحدود  : طريقة دوراند-كيرنر — يتضمنعرضًا توضيحيًا باستخدام تطبيق جافا صغير