طريقة رب الأسرة

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

سُميت هذه الطرق نسبةً إلى عالم الرياضيات الأمريكي ألستون سكوت هاوسهولدر . الحالة d = 1 تُقابل طريقة نيوتن ؛ والحالة d = 2 تُقابل طريقة هالي .

طريقة هاوسهولدر هي خوارزمية عددية لحل المعادلة f ( x ) = 0. في هذه الحالة، يجب أن تكون الدالة f دالة لمتغير حقيقي واحد. تتكون الطريقة ^{[ 1 ]} من سلسلة من التكرارات.

$${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$$

بدءاً من تخمين أولي x ₀ ، حيث يشير الرقم العلوي بين قوسين إلى عدد مرات اشتقاق الدالة .

إذا كانت f دالة قابلة للتفاضل بشكل مستمر من d + 1 مرة ، وكان a صفرًا لـ f ولكن ليس صفرًا لمشتقتها، فإن التكرارات x _n في جوار a تحقق ما يلي:

$${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{d+1},}$$ بالنسبة للبعض${\displaystyle K>0.}$

هذا يعني أن التكرارات تتقارب إلى الصفر إذا كانت القيمة الأولية قريبة بما فيه الكفاية، وأن التقارب من الرتبة d + 1 أو أفضل. علاوة على ذلك، عندما تكون القيمة قريبة بما فيه الكفاية من a ، فإنه عادةً ما يكون الحال${\displaystyle x_{n+1}-a\approx C(x_{n}-a)^{d+1}}$بالنسبة للبعض${\displaystyle C\neq 0}$. بخاصة،

• إذا كان d فرديًا و C > 0 فإن التقارب إلى a سيكون من قيم أكبر من a ؛
• إذا كان d فرديًا و C < 0 فإن التقارب إلى a سيكون من قيم أقل من a ؛
• إذا كان d زوجيًا و C > 0، فإن التقارب إلى a سيكون من الجانب الذي يبدأ منه؛ و
• إذا كان d زوجيًا و C < 0 فإن التقارب إلى a سيتبادل الجانبين.

على الرغم من رتبة تقاربها، لا تُستخدم هذه الطرق على نطاق واسع عندما يكون d ≥ 3 لأن الزيادة في الدقة لا تتناسب مع زيادة الجهد المبذول. يُعبّر مؤشر أوستروفسكي عن انخفاض الخطأ في عدد تقييمات الدالة بدلاً من عدد التكرارات. ^{[ 2 ]}

• بالنسبة لكثيرات الحدود، يتطلب حساب المشتقات الأولى من f عند x = _n باستخدام طريقة هورنر جهدًا مقداره d + 1 عملية حساب لكثيرات الحدود. وبما أن n ( d + 1) عملية حساب على مدى n تكرارًا تعطي أس خطأ مقداره ( d + 1) ⁿ ، فإن أس عملية حساب واحدة للدالة هو${\displaystyle {\sqrt[{d+1}]{d+1}}}$، عدديًا 1.4142 ، 1.4422 ، 1.4142 ، 1.3797 لقيم d = 1، 2، 3، 4 ، ثم تنخفض بعد ذلك. وفقًا لهذا المعيار، فإن حالة d = 2 ( طريقة هالي ) هي القيمة المثلى لـ d .
• بالنسبة للدوال العامة، يتطلب حساب المشتقة باستخدام حساب تايلور للتفاضل التلقائي ما يعادل ( d + 1)( d + 2)/2 من عمليات حساب الدالة. وبالتالي، فإن عملية حساب واحدة للدالة تقلل الخطأ بمقدار أُسّي قدره${\displaystyle {\sqrt[{\frac {(d+1)(d+2)}{2}}]{d+1}}}$، وهو${\displaystyle {\sqrt[{3}]{2}}\approx 1.2599}$بالنسبة لطريقة نيوتن،${\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}$بالنسبة لطريقة هالي، والانحدار نحو 1 أو التقارب الخطي بالنسبة للطرق ذات الرتبة الأعلى.

طريقة هاوسهولدر من الدرجة الأولى هي ببساطة طريقة نيوتن ، وذلك لأن: $${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}$$

بالنسبة لطريقة هاوسهولدر من الرتبة الثانية، نحصل على طريقة هالي ، وذلك لأن المتطابقات $${\displaystyle \textstyle (1/f)'(x)=-{\frac {f'(x)}{f(x)^{2}}}\ }$$ و $${\displaystyle \textstyle \ (1/f)''(x)=-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}}}}$$ ينتج عنه $${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}}$$ في السطر الأخير،${\displaystyle h_{n}=-{\tfrac {f(x_{n})}{f'(x_{n})}}}$هو تحديث لتكرار نيوتن عند النقطة${\displaystyle x_{n}}$تمت إضافة هذا السطر لتوضيح أين يكمن الاختلاف عن طريقة نيوتن البسيطة.

تُستنتج طريقة الرتبة الثالثة من متطابقة المشتقة من الرتبة الثالثة لـ 1/ f$${\displaystyle \textstyle (1/f)'''(x)=-{\frac {f'''(x)}{f(x)^{2}}}+6{\frac {f'(x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}}$$ وله الصيغة $${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}$$ وهكذا دواليك.

كانت أول مشكلة حلها نيوتن باستخدام طريقة نيوتن-رافسون-سيمبسون هي معادلة متعددة الحدود${\displaystyle y^{3}-2y-5=0}$لاحظ أنه ينبغي أن يكون هناك حل قريب من 2. باستبدال y = x + 2 ، تتحول المعادلة إلى $${\displaystyle 0=f(x)=-1+10x+6x^{2}+x^{3}}$$تبدأ متسلسلة تايلور للدالة المقلوبة بـ $${\displaystyle {\begin{array}{rl}1/f(x)=&-1-10\,x-106\,x^{2}-1121\,x^{3}-11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385\,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{array}}}$$ تُحسب نتيجة تطبيق طرق هاوسهولدر من مختلف الرتب عند x = 0 أيضًا بقسمة المعاملات المتجاورة لسلسلة القوى الأخيرة . بالنسبة للرتب الأولى، نحصل على القيم التالية بعد خطوة تكرار واحدة فقط: على سبيل المثال، في حالة الرتبة الثالثة، ${\displaystyle x_{1}=0.0+106/1121=0.09455842997324}$.

كما هو واضح، يوجد أكثر بقليل من d منازل عشرية صحيحة لكل رتبة d. أول مائة رقم من الحل الصحيح هي 0.09455 14815 42326 59148 23865 40579 30296 38573 06105 62823 91803 04128 52904 53121 89983 48366 71462 67281 77715 77578 .

لنحسب${\displaystyle x_{2},x_{3},x_{4}}$قيم لبعض الرتب الدنيا،

$${\displaystyle f=-1+10x+6x^{2}+x^{3}}$$$${\displaystyle f^{\prime }=10+12x+3x^{2}}$$$${\displaystyle f^{\prime \prime }=12+6x}$$$${\displaystyle f^{\prime \prime \prime }=6}$$

وباستخدام العلاقات التالية،

الطلب الأول؛${\displaystyle x_{i+1}=x_{i}-f(x_{i})/f^{\prime }(x_{i})}$

الدرجة الثانية؛${\displaystyle x_{i+1}=x_{i}-2ff^{\prime }/(2{f^{\prime }}^{2}-ff^{\prime \prime })}$

الدرجة الثالثة؛${\displaystyle x_{i+1}=x_{i}-(6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime })/(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}$

يبدأ الاشتقاق الدقيق لطرق هاوسهولدر من تقريب باديه من الرتبة d + 1 للدالة، حيث يتم اختيار التقريب ذي البسط الخطي . وبمجرد تحقيق ذلك، ينتج التحديث للتقريب التالي من حساب الصفر الوحيد للبسط.

يأخذ تقريب باديه الشكل التالي: $${\displaystyle f(x+h)={\frac {a_{0}+h}{b_{0}+b_{1}h+\cdots +b_{d-1}h^{d-1}}}+O(h^{d+1}).}$$ للدالة الكسرية صفر عند${\displaystyle h=-a_{0}}$.

كما أن متعددة حدود تايلور من الدرجة d لها d + 1 معاملًا تعتمد على الدالة f ، فإن تقريب باديه له أيضًا d + 1 معاملًا تعتمد على f ومشتقاتها. وبشكل أدق، في أي تقريب باديه، يجب أن يكون مجموع درجتي كثيرتي حدود البسط والمقام مساويًا لرتبة التقريب. لذلك،${\displaystyle b_{d}=0}$يجب أن يصمد.

يمكن تحديد تقريب باديه انطلاقًا من متعددة حدود تايلور للدالة f باستخدام خوارزمية إقليدس . مع ذلك، فإن البدء من متعددة حدود تايلور لـ 1/ f أقصر ويؤدي مباشرةً إلى الصيغة المعطاة. $${\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f)'(x)h+\cdots +(1/f)^{(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac {h^{d}}{d!}}+O(h^{d+1})}$$ يجب أن يكون مساوياً لمعكوس الدالة الكسرية المطلوبة، نحصل عليه بعد الضرب في${\displaystyle a_{0}+h}$في السلطة${\displaystyle h^{d}}$المعادلة $${\displaystyle 0=b_{d}=a_{0}(1/f)^{(d)}(x){\frac {1}{d!}}+(1/f)^{(d-1)}(x){\frac {1}{(d-1)!}}}$$.

الآن، حل المعادلة الأخيرة لإيجاد الصفر${\displaystyle h=-a_{0}}$ينتج عن البسط ما يلي: $${\displaystyle {\begin{aligned}h&=-a_{0}={\frac {{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\&=d\,{\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{aligned}}}$$.

وهذا يستلزم صيغة التكرار $${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$$.

إن تطبيق طريقة هاوسهولدر على الدالة الحقيقية f ( x ) هو نفسه تطبيق طريقة نيوتن. $${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$$ لإيجاد أصفار الدالة: $${\displaystyle g(x)=\left|(1/f)^{(d-1)}\right|^{-1/d}\,,}$$ حيث نقوم بحساب المشتقة من الرتبة ( d - 1) ورفعها إلى قوة -1/ d . على وجه الخصوص، d = 1 تعطي طريقة نيوتن دون تعديل، و d = 2 تعطي طريقة هالي.

يمكن كتابة طريقة هاوسهولدر من الرتبة d على شكل مجموع متداخل من الحدود التي تغير تدريجياً طريقة هاوسهولدر من الرتبة ( k − 1) إلى الرتبة k : $${\displaystyle x_{n+1}=x_{n}+{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}+\sum _{k=2}^{d}\left(k\;{\frac {\left(1/f\right)^{(k-1)}(x_{n})}{\left(1/f\right)^{(k)}(x_{n})}}-(k-1)\;{\frac {\left(1/f\right)^{(k-2)}(x_{n})}{\left(1/f\right)^{(k-1)}(x_{n})}}\right)}$$

في الحد${\displaystyle d\rightarrow \infty }$، يمثل الطرف الأيمن من هذه المعادلة المتسلسلة الناتجة عن نظرية لاغرانج العكسية . وبموجب شروط هذه النظرية، تكون القيمة المحسوبة _x1 هي القيمة المطلوبة للجذر تمامًا عندماتُختار القيمة الابتدائية x0 قريبة منها بدرجة كافية _.

• سيباه، باسكال؛ غوردون، كزافييه (2001). "طريقة نيوتن والتكرارات من الرتبة العليا" . تم الاسترجاع في 5 نوفمبر 2025 .ملاحظة : استخدم نسخة PostScript من هذا الرابط؛ نسخة الموقع الإلكتروني غير مُجمّعة بشكل صحيح.
• وايسشتاين، إريك دبليو. "طريقة هاوسهولدر" . ماث وورلد .