مُهيئ مسبق

بدلاً من حل النظام الخطي الأصلي${\displaystyle Ax=b}$ل${\displaystyle x}$، يمكن للمرء أن ينظر في النظام المُهيأ مسبقًا بشكل صحيح$${\displaystyle AP^{-1}(Px)=b}$$ وحل $${\displaystyle AP^{-1}y=b}$$ ل${\displaystyle y}$و $${\displaystyle Px=y}$$ ل${\displaystyle x}$.

أو بدلاً من ذلك، يمكن حل النظام المُهيأ مسبقًا من اليسار$${\displaystyle P^{-1}(Ax-b)=0.}$$

يعطي كلا النظامين نفس الحل الذي يقدمه النظام الأصلي طالما أن مصفوفة التكييف المسبق${\displaystyle P}$غير منفرد . التكييف المسبق الأيسر أكثر تقليدية.

النظام المُهيأ مسبقًا ذو الجانبين$${\displaystyle QAP^{-1}(Px)=Qb}$$ قد يكون ذلك مفيدًا، على سبيل المثال، للحفاظ على تناظر المصفوفة: إذا كانت المصفوفة الأصلية${\displaystyle A}$هي حقيقية متناظرة ومُهيئات مسبقة حقيقية${\displaystyle Q}$و${\displaystyle P}$مُرضٍ ${\displaystyle Q^{T}=P^{-1}}$ثم المصفوفة المُهيأة${\displaystyle QAP^{-1}}$وهي متناظرة أيضًا. يُعدّ التكييف المسبق ثنائي الجانب شائعًا في القياس القطري حيث تكون المُكيِّفات المسبقة${\displaystyle Q}$و${\displaystyle P}$تكون العناصر قطرية ويتم تطبيق التحجيم على كل من أعمدة وصفوف المصفوفة الأصلية${\displaystyle A}$على سبيل المثال، من أجل تقليل النطاق الديناميكي لعناصر المصفوفة.

الهدف من التكييف المسبق هو تقليل رقم الحالة ، على سبيل المثال، لمصفوفة النظام المُكيَّف مسبقًا من اليسار أو اليمين${\displaystyle P^{-1}A}$أو${\displaystyle AP^{-1}}$. تعمل أرقام الحالة الصغيرة على تحسين التقارب السريع للحلول التكرارية وتحسين استقرار الحل فيما يتعلق بالاضطرابات في مصفوفة النظام والجانب الأيمن، على سبيل المثال، السماح بتكميم أكثر صرامة لإدخالات المصفوفة باستخدام دقة حاسوبية أقل .

المصفوفة المُهيأة مسبقًا${\displaystyle P^{-1}A}$أو${\displaystyle AP^{-1}}$نادرًا ما يتم تشكيلها بشكل صريح. فقط عملية تطبيق المُهيئ المسبق تحل المشكلة. ${\displaystyle P^{-1}}$قد يلزم حساب متجه معين.

عادةً ما يكون هناك مفاضلة في اختيار${\displaystyle P}$بما أن المشغل${\displaystyle P^{-1}}$يجب تطبيقها في كل خطوة من خطوات حل المعادلات الخطية التكراري، وينبغي أن يكون لتطبيقها تكلفة صغيرة (وقت حسابي). ${\displaystyle P^{-1}}$وبالتالي، فإن أرخص جهاز تهيئة مسبقة سيكون${\displaystyle P=I}$.منذ ذلك الحين${\displaystyle P^{-1}=I.}$من الواضح أن هذا يؤدي إلى النظام الخطي الأصلي، ولا يقوم المُهيئ المسبق بأي شيء. وعلى النقيض من ذلك، فإن الخيار ${\displaystyle P=A}$أعطِ${\displaystyle P^{-1}A=AP^{-1}=I,}$والتي تتمتع برقم شرط مثالي يساوي 1، مما يتطلب تكرارًا واحدًا للتقارب؛ ومع ذلك في هذه الحالة${\displaystyle P^{-1}=A^{-1},}$وتطبيق المُهيئ المسبق لا يقل صعوبة عن حل النظام الأصلي. لذلك يختار المرء ${\displaystyle P}$ كحل وسط بين هذين النقيضين، في محاولة لتحقيق الحد الأدنى من التكرارات الخطية مع الحفاظ على العامل ${\displaystyle P^{-1}}$ بأبسط شكل ممكن. فيما يلي بعض الأمثلة على أساليب التكييف المسبق النموذجية.

طرق التكرار المُهيأة لـ${\displaystyle Ax-b=0}$وهي، في معظم الحالات، مكافئة رياضياً للطرق التكرارية القياسية المطبقة على النظام المُهيأ مسبقاً${\displaystyle P^{-1}(Ax-b)=0.}$على سبيل المثال، التكرار القياسي لريتشاردسون لحل${\displaystyle Ax-b=0}$يكون $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

يتم تطبيقه على النظام المُهيأ مسبقًا${\displaystyle P^{-1}(Ax-b)=0,}$يتحول إلى طريقة مشروطة مسبقًا $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

من أمثلة الطرق التكرارية المُهيأة الشائعة للأنظمة الخطية: طريقة التدرج المترافق المُهيأة ، وطريقة التدرج المترافق الثنائي ، وطريقة الباقي الأدنى المعممة . تتطلب الطرق التكرارية، التي تستخدم الضرب القياسي لحساب المعاملات التكرارية، تغييرات مقابلة في الضرب القياسي بالإضافة إلى الاستبدال.${\displaystyle P^{-1}(Ax-b)=0}$ل${\displaystyle Ax-b=0.}$

بالنسبة للمصفوفة المتناظرة الموجبة المحددة${\displaystyle A}$المُهيئ المسبق${\displaystyle P}$يُختار عادةً ليكون متماثلاً وموجباً أيضاً. المؤثر المُهيأ مسبقاً${\displaystyle P^{-1}A}$وبالتالي، تكون متماثلة وموجبة تمامًا، ولكن بالنسبة إلى${\displaystyle P}$الضرب القياسي القائم على أساس . في هذه الحالة، يتمثل التأثير المطلوب عند تطبيق مُهيئ مسبق في جعل الشكل التربيعي للمؤثر المُهيأ مسبقًا${\displaystyle P^{-1}A}$فيما يتعلق بـ${\displaystyle P}$يجب أن يكون حاصل الضرب القياسي القائم على أساس كروي تقريبًا. ^{[ 1 ]}

يدل على${\displaystyle T=P^{-1}}$نؤكد أن التكييف المسبق يُنفذ عمليًا عن طريق ضرب متجه ما${\displaystyle r}$بواسطة${\displaystyle T}$أي حساب الناتج${\displaystyle Tr.}$في العديد من التطبيقات،${\displaystyle T}$لا يتم تقديمها كمصفوفة، بل كمؤثر${\displaystyle T(r)}$التأثير على المتجه${\displaystyle r}$لكن بعض مُهيئات الأسطح الشائعة تتغير مع${\displaystyle r}$والاعتماد على${\displaystyle r}$قد لا تكون خطية. تتضمن الأمثلة النموذجية استخدام طرق تكرارية غير خطية ، مثل طريقة التدرج المترافق ، كجزء من بناء المُهيئ. قد تكون هذه المُهيئات فعالة للغاية عمليًا، إلا أن سلوكها يصعب التنبؤ به نظريًا.

من الحالات الخاصة المثيرة للاهتمام للتهيئة المتغيرة التهيئة العشوائية، مثل التهيئة متعددة الشبكات على شبكات خشنة عشوائية. ^{[ 2 ]} عند استخدامها في طرق التدرج الهبوطي ، يمكن اعتبار التهيئة العشوائية تطبيقًا للتدرج الهبوطي العشوائي ، ويمكن أن تؤدي إلى تقارب أسرع مقارنةً بالتهيئة الثابتة، لأنها تكسر نمط "الزقزاق" التقاربي للتدرج الهبوطي .

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

• التدرج المترافق المُهيأ مسبقًا – math-linux.com
• قوالب لحل الأنظمة الخطية: لبنات بناء الطرق التكرارية

قياسًا على الأنظمة الخطية، بالنسبة لمسألة القيم الذاتية${\displaystyle Ax=\lambda x}$قد يميل المرء إلى استبدال المصفوفة${\displaystyle A}$باستخدام المصفوفة${\displaystyle P^{-1}A}$باستخدام مُهيئ مسبق${\displaystyle P}$ومع ذلك، فإن هذا لا يكون منطقيًا إلا إذا كانت المتجهات الذاتية الباحثة لـ ${\displaystyle A}$و${\displaystyle P^{-1}A}$وهي متماثلة. وينطبق هذا على التحويلات الطيفية.

التحويل الطيفي الأكثر شيوعًا هو ما يسمى بتحويل الإزاحة والانعكاس ، حيث بالنسبة لكمية قياسية معينة${\displaystyle \alpha }$، والتي تسمى الإزاحة ، مشكلة القيمة الذاتية الأصلية${\displaystyle Ax=\lambda x}$يتم استبدالها بمشكلة الإزاحة والعكس${\displaystyle (A-\alpha I)^{-1}x=\mu x}$تُحفظ المتجهات الذاتية، ويمكن حل مسألة الإزاحة والعكس باستخدام خوارزمية تكرارية، مثل تكرار القوة . ينتج عن ذلك تكرار العكس ، الذي يتقارب عادةً إلى المتجه الذاتي المقابل للقيمة الذاتية الأقرب إلى الإزاحة.${\displaystyle \alpha }$. إن تكرار حاصل قسمة رايلي هو طريقة إزاحة وعكس مع إزاحة متغيرة.

تُعدّ التحويلات الطيفية خاصة بمسائل القيم الذاتية، ولا يوجد لها نظائر في الأنظمة الخطية. وهي تتطلب حسابًا عدديًا دقيقًا للتحويل المعني، وهو ما يُشكّل العائق الرئيسي في المسائل الكبيرة.

لإقامة صلة وثيقة بالأنظمة الخطية، لنفترض أن القيمة الذاتية المستهدفة${\displaystyle \lambda _{\star }}$إذا كانت القيمة معروفة (تقريبًا)، فيمكن حساب المتجه الذاتي المقابل من النظام الخطي المتجانس.${\displaystyle (A-\lambda _{\star }I)x=0}$باستخدام مفهوم التكييف المسبق الأيسر للأنظمة الخطية، نحصل على${\displaystyle T(A-\lambda _{\star }I)x=0}$، أين ${\displaystyle T}$هو المُهيئ المسبق، والذي يمكننا محاولة حله باستخدام تكرار ريتشاردسون

$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{\star }I)\mathbf {x} _{n},\ n\geq 0.}$$

• نماذج لحل مسائل القيم الذاتية الجبرية: دليل عملي

على سبيل المثال، لإيجاد قيمة صغرى محلية لدالة ذات قيم حقيقية${\displaystyle F(\mathbf {x} )}$باستخدام خوارزمية التدرج الهبوطي ، يتم اتخاذ خطوات تتناسب عكسيًا مع التدرج .${\displaystyle -\nabla F(\mathbf {a} )}$ (أو التدرج التقريبي) للدالة عند النقطة الحالية: $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

يتم تطبيق المُهيئ المسبق على التدرج: $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

يمكن اعتبار التكييف المسبق هنا بمثابة تغيير في هندسة فضاء المتجهات بهدف جعل مجموعات المستوى تبدو كدوائر. ^{[ 5 ]} في هذه الحالة، يتجه التدرج المُكيَّف مسبقًا نحو نقطة القيم القصوى كما هو موضح في الشكل، مما يُسرِّع عملية التقارب.

الحد الأدنى للدالة التربيعية $${\displaystyle F(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} ,}$$ أين${\displaystyle \mathbf {x} }$و${\displaystyle \mathbf {b} }$هي متجهات عمودية حقيقية و${\displaystyle A}$هي مصفوفة حقيقية متناظرة موجبة التحديد ، وهي بالضبط حل المعادلة الخطية${\displaystyle A\mathbf {x} =\mathbf {b} }$. منذ${\displaystyle \nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$، طريقة التدرج المشروط لتقليل ${\displaystyle F(\mathbf {x} )}$يكون $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

هذه هي عملية التكرار المسبق لريتشاردسون لحل نظام المعادلات الخطية .

الحد الأدنى لنسبة رايلي$${\displaystyle \rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},}$$ أين${\displaystyle \mathbf {x} }$هو متجه عمودي حقيقي غير صفري و${\displaystyle A}$هي مصفوفة حقيقية متناظرة موجبة التحديد ، و هي أصغر قيمة ذاتية لـ${\displaystyle A}$بينما القيمة الصغرى هي المتجه الذاتي المقابل . بما أن${\displaystyle \nabla \rho (\mathbf {x} )}$يتناسب مع${\displaystyle A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x} }$، طريقة التدرج المشروط لتقليل ${\displaystyle \rho (\mathbf {x} )}$يكون $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.}$$

هذا نظير لتكرار ريتشاردسون المشروط مسبقًا لحل مسائل القيم الذاتية.

في كثير من الحالات، قد يكون من المفيد تغيير المُهيئ المسبق في بعض خطوات الخوارزمية التكرارية أو حتى في كل خطوة منها ، وذلك لاستيعاب تغير شكل مجموعات المستويات، كما هو الحال في $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P_{n}^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

مع ذلك، ينبغي الأخذ في الاعتبار أن بناء مُهيئ فعال غالبًا ما يكون مكلفًا حسابيًا. ويمكن أن تتجاوز التكلفة المتزايدة لتحديث المُهيئ بسهولة الأثر الإيجابي للتقارب الأسرع.${\displaystyle P_{n}^{-1}=H_{n}}$، وهو تقريب BFGS لمصفوفة هيسيان العكسية ، ويشار إلى هذه الطريقة باسم طريقة شبه نيوتن .