أسلوب لاغير

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

سميت هذه الطريقة تكريماً لعالم الرياضيات الفرنسي إدموند لاغير .

خوارزمية طريقة لاغير لإيجاد جذر واحد لكثير الحدود p ( x ) من الدرجة n هي:

• اختر قيمة أولية x ₀
• بالنسبة لـ k = 0، 1، 2، ...
  • لو${\displaystyle p(x_{k})}$صغير جدًا، اخرج من الحلقة
  • احسب${\displaystyle G={\frac {p'(x_{k})}{p(x_{k})}}}$
  • احسب${\displaystyle H=G^{2}-{\frac {p''(x_{k})}{p(x_{k})}}}$
  • احسب${\displaystyle a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2})}}}}}$، حيث يتم اختيار الإشارة لإعطاء المقام ذي القيمة المطلقة الأكبر، لتجنب الإلغاء الكارثي .
  • تعيين${\displaystyle x_{k+1}=x_{k}-a}$
• كرر العملية حتى تصبح قيمة a صغيرة بما يكفي أو حتى يتم الوصول إلى الحد الأقصى لعدد التكرارات.

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

تنص النظرية الأساسية للجبر على أن كل متعددة حدود من الدرجة n${\displaystyle p}$يمكن كتابتها بالشكل التالي

${\displaystyle p(x)=C\left(x-x_{1}\right)\left(x-x_{2}\right)\cdots \left(x-x_{n}\right),}$

لهذا السبب.${\displaystyle x_{1},\ x_{2},\ \ldots ,\ x_{n},}$هي جذور كثيرة الحدود. إذا أخذنا اللوغاريتم الطبيعي لكلا الطرفين، فسنجد أن

${\displaystyle \ln {\bigl |}p(x){\bigr |}=\ln {\bigl |}C{\bigr |}+\ln {\bigl |}x-x_{1}{\bigr |}+\ln {\bigl |}x-x_{2}{\bigr |}+\cdots +\ln {\bigl |}x-x_{n}{\bigr |}.}$

نرمز إلى المشتقة اللوغاريتمية بـ

$\begin{aligned}G&=\frac{\operatorname{d}}{\operatorname{d}x}\ln{\Bigl|}p(x)\Bigr|}=\frac{1}{x-x_{1}}}+\frac{1}{x-x_{2}}}+\cdots+\frac{1}{x-x_{n}}}\\&=\frac{p'(x)}{\bigl|}p(x)\bigr|}}},\end{aligned}}}$

والمشتقة الثانية المنفية بواسطة

$\begin{aligned}\H&=-\frac{\operatorname{d}^2}{\operatorname{d}x^2}\ln{\Bigl|}p(x)\Bigr|}=\frac{1}{(x-x_1)^2}}}+\frac{1}{(x-x_2)^2}}}+\cdots+\frac{1}{(x-x_n)^2}}}\\&=-\frac{p''(x)}{\bigl|}p(x)\bigr|}}}+\left(\frac{p'(x)}{p(x)}}\right)^2\cdot\\operatorname{sgn}\!{\Bigl(}p(x)\Bigr)}.\end{aligned}}}$

ثم نقوم بما يسميه أكتون (1970) "مجموعة من الافتراضات الجذرية"، وهي أن الجذر الذي نبحث عنه، على سبيل المثال،${\displaystyle x_{1}}$مسافة قصيرة،${\displaystyle a,}$بعيدًا عن تخميننا${\displaystyle x,}$أما الجذور الأخرى فتتجمع معاً، على مسافة أبعد.${\displaystyle b.}$إذا رمزنا لهذه المسافات بـ

${\displaystyle a\equiv x-x_{1}}$

و

${\displaystyle b\approx x-x_{2}\approx x-x_{3}\approx \cdots \approx x-x_{n},}$

أو تحديداً،

${\displaystyle b\equiv \operatorname {harmonic\ mean} {\Bigl \{}x-x_{2},\ x-x_{3},\ \ldots \ x-x_{n}{\Bigr \}}}$

ثم معادلتنا لـ${\displaystyle \ G\ }$يمكن كتابتها على النحو التالي

${\displaystyle G={\frac {1}{a}}+{\frac {n-1}{b}}}$

والتعبير عن${\displaystyle H}$يصبح

${\displaystyle H={\frac {1}{a^{2}}}+{\frac {n-1}{b^{2}}}.}$

حل هذه المعادلات لـ${\displaystyle a,}$وجدنا أن

${\displaystyle a={\frac {n}{G\pm {\sqrt {{\bigl (}n-1{\bigr )}{\bigl (}nH-G^{2}{\bigr )}}}}},}$

في هذه الحالة، يتم اختيار الجذر التربيعي للعدد (الذي قد يكون مركباً) لإنتاج أكبر قيمة مطلقة للمقام وجعله${\displaystyle \ a\ }$أصغر ما يمكن؛ أو بعبارة أخرى، يُحقق ما يلي:

${\displaystyle \operatorname {\mathcal {R_{e}}} {\biggl \{}{\overline {G}}{\sqrt {\left(n-1\right)\left(nH-G^{2}\right)}}{\biggr \}}>0,}$

أين${\displaystyle {\mathcal {R_{e}}}}$يرمز إلى الجزء الحقيقي من العدد المركب، و${\displaystyle {\overline {G}}}$هو المرافق المعقد لـ${\displaystyle G;}$أو

${\displaystyle a={\frac {p(x)}{p'(x)}}\cdot {\Biggl \{}{\frac {1}{n}}+{\frac {n-1}{n}}{\sqrt {1-{\frac {n}{n-1}}{\frac {p(x)\ p''(x)}{p'(x)^{2}}}}}{\Biggr \}}^{-1},}$

حيث يتم اختيار الجذر التربيعي لعدد مركب بحيث يكون له جزء حقيقي غير سالب.

بالنسبة للقيم الصغيرة لـ${\displaystyle p(x)}$تختلف هذه الصيغة عن إزاحة طريقة هالي من الدرجة الثالثة بخطأ قدره${\displaystyle \operatorname {\mathcal {O}} {\bigl \{}(p(x))^{3}{\bigr \}},}$لذا فإن التقارب بالقرب من الجذر سيكون تكعيبياً أيضاً.

إذا كان x جذرًا بسيطًا لكثير الحدود${\displaystyle p(x),}$ثم تتقارب طريقة لاغير بشكل تكعيبي كلما كانت القيمة الأولية للتخمين،${\displaystyle x^{(0)},}$قريب بما فيه الكفاية من الجذر${\displaystyle x_{1}.}$من ناحية أخرى، عندما${\displaystyle x_{1}}$إن التقارب متعدد الجذور هو مجرد خطي، مع عقوبة حساب قيم متعددة الحدود ومشتقاتها الأولى والثانية في كل مرحلة من مراحل التكرار.

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

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

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