طريقة برودن

في طريقة القاطع ، نستبدل المشتقة الأولى f ′ عند x _n بتقريب الفروق المحدودة :

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},}$

ويتبع ذلك أسلوب مشابه لطريقة نيوتن :

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}}$

حيث n هو مؤشر التكرار.

لنفترض نظامًا من k معادلات غير خطية في${\displaystyle k}$مجهولون

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

حيث f دالة متجهة القيم للمتجه x

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

بالنسبة لمثل هذه المسائل، يقدم برودن صيغة معدلة من طريقة نيوتن أحادية البعد، حيث يستبدل المشتقة بمصفوفة جاكوبية تقريبية J. يتم تحديد مصفوفة جاكوبية التقريبية بشكل تكراري بناءً على معادلة القاطع ، وهي تقريب باستخدام الفروق المحدودة:

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1})،}$

حيث n هو مؤشر التكرار. ولتوضيح الأمر، عرّف

${\displaystyle \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},}$

لذا يمكن إعادة صياغة ما سبق على النحو التالي

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

تكون المعادلة أعلاه غير محددة عندما تكون قيمة k أكبر من واحد. اقترح برودن استخدام أحدث تقدير لمصفوفة جاكوبي، J _{n −1} ، ثم تحسينها من خلال اشتراط أن يكون الشكل الجديد حلاً لأحدث معادلة قاطع، وأن يكون هناك تعديل طفيف على J _{n −1} .

$// \mathbf {x} _{n}^{\mathrm {T} }.}$

هذا يقلل من معيار فروبينيوس

${\displaystyle \|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.}$

ثم يقوم المرء بتحديث المتغيرات باستخدام جاكوبيان التقريبي، وهو ما يسمى نهج شبه نيوتن.

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).}$

لو${\displaystyle \alpha =1}$هذه هي خطوة نيوتن الكاملة؛ وعادةً ما تُستخدم طريقة البحث الخطي أو طريقة منطقة الثقة للتحكم${\displaystyle \alpha }$يمكن اعتبار مصفوفة جاكوبي الأولية مصفوفة قطرية ذات عناصر تساوي 1، على الرغم من أن الأكثر شيوعًا هو تغيير مقياسها بناءً على الخطوة الأولى. ^{[ 3 ]} كما اقترح برودن استخدام صيغة شيرمان-موريسون ^{[ 4 ]} لتحديث معكوس مصفوفة جاكوبي التقريبية مباشرةً.

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _ {n} ^ {\mathrm {T}}\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

تُعرف هذه الطريقة الأولى باسم "طريقة برودن الجيدة".

يمكن اشتقاق تقنية مماثلة باستخدام تعديل مختلف قليلاً على J _{n −1} . وهذا ينتج عنه طريقة ثانية، تُعرف باسم "طريقة برودن السيئة":

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _ {n}\|^{2}}}\دلتا \mathbf {f} _{n}^{\mathrm {T} }.}$

هذا يقلل من معيار فروبينيوس مختلف

${\displaystyle \|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.}$

في ورقته البحثية الأصلية، لم يتمكن برودن من تطبيق الطريقة السيئة بنجاح، ولكن توجد حالات تنجح فيها ^{[ 5 ]} ، وقد طُرحت عدة تفسيرات لذلك. ^{[ 6 ] [ 7 ]} وقد اقتُرحت العديد من مخططات شبه نيوتن الأخرى في مجال التحسين، مثل BFGS ، حيث يُبحث عن قيمة عظمى أو صغرى من خلال إيجاد أصفار المشتقات الأولى (أصفار التدرج في أبعاد متعددة). يُطلق على مصفوفة جاكوبي للتدرج اسم مصفوفة هيسيان ، وهي متناظرة، مما يُضيف قيودًا إضافية على تقريبها.