طريقة نيوتن شبه
طريقة شبه نيوتنهي طريقة تحسين تعتمد على طريقة نيوتن، وتستخدم بشكل أساسي لحل مشاكل القيمة الصفرية والعظمى والدنيا للمعادلات غير الخطية أو الدوال المستمرة.
عندما تكون مصفوفة جاكوبي في طريقة نيوتن أو هيسيان عندما يكون من الصعب أو حتى من المستحيل حساب المصفوفة، يأتي دور طريقة شبه نيوتن. وهي واحدة من أكثر الطرق فعالية لحل مشاكل التحسين غير الخطية. تم اقتراح طريقة شبه نيوتن لأول مرة من قبل الولايات المتحدة. أرجون فيزيائي في المختبر الوطني دبليو سي دي فيدون في 20 قرن 50 العصر المقترح.
فكرة طريقة شبه نيوتن
طريقة نيوتن تحل هيسيان عند حساب المصفوفة، يجب حساب المصفوفة العكسية أولاً، مما سيؤدي إلى انخفاض الكفاءة، ولكن طريقة شبه نيوتن تستخدم مصفوفة محددة موجبة لتقريب هيسيان يتم الحصول على المصفوفة العكسية للمصفوفة، وبالتالي تقليل تعقيد الخوارزمية وتحسين الكفاءة.
خوارزميات شبه نيوتن الشائعة
- خوارزمية DFP (ديفيدون-فليتشر-باول)
في خوارزمية DFP، نختار تقريبًا لـ، على افتراض أن المصفوفة في كل تكرار تتكون من زائد حدين إضافيين، وهما
في،
و
هي المصفوفة غير المحددة. لكن
لصنع
بإرضاء شرط شبه نيوتن، يمكنناوإرضاء
مرغوب فيه
يمكن الحصول على المصفوفةصيغة التكرار
يمكن إثبات أنه إذا كانت المصفوفة الأولية
إذا كانت موجبة محددة، فإن كل مصفوفة في العملية التكرارية
كلهم إيجابيون.
- خوارزمية BFGS (Broyden-Fletcher-Goldfard-Shano)
DFP هوتقريب معكوس مصفوفة هيسيان
، بينما في خوارزمية BFGS،
التقريب إلى مصفوفة هيسيان
، الشرط شبه نيوتن المقابل
افترض أنه في كل تكرار المصفوفة
يكونمع مصطلحين إضافيين، وهما
في،وهي المصفوفة غير المحددة. لكن
لصنعبإرضاء شرط شبه نيوتن، يمكنناوإرضاء
مرغوب فيه
يمكن الحصول على المصفوفةصيغة التكرار
يمكن إثبات أنه إذا كانت المصفوفة الأولية
إذا كانت موجبة محددة، فإن كل مصفوفة في العملية التكراريةكلهم إيجابيون.
- خوارزمية من نوع برويدن (خوارزمية برويدن)
يمكننا الحصول على مصفوفة خوارزمية BFGSالصيغة التكرارية لخوارزمية BFGS هيصيغة التكرار لـ .
يتذكر
بتطبيق صيغة شيرمان-موريسون مرتين، نحصل على
يُطلق عليه اسم خوارزمية BFGS.صيغة التكرار لـ .
صيغة شيرمان-موريسون: افترض
هي مصفوفة عكسية من الدرجة n،
هو متجه ذو أبعاد n، و
وهي أيضًا مصفوفة قابلة للعكس، إذًا:
دع الصيغة التكرارية التي تم الحصول عليها بواسطة خوارزمية DFP تكونتم تسجيله كـ
وفقًا للصيغة التكرارية لخوارزمية BFGSما تحصل عليهيُشار إليه على أنه، بما أن كليهما يُلبي شرط شبه نيوتن، فإن التركيبة الخطية للاثنين
كما أنه يلبي شرط شبه نيوتن وهو محدد إيجابي. في،
. يُطلق على هذا النوع من الخوارزميات اسم خوارزمية نوع برويدن.