طريقة التدرج المترافق

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 162 صور
الموسوعة الحرة
مقارنة بين تقارب خوارزمية التدرج الهبوطي مع حجم الخطوة الأمثل (باللون الأخضر) وخوارزمية المتجه المرافق (باللون الأحمر) لتقليل دالة تربيعية مرتبطة بنظام خطي معين. يتقارب التدرج المرافق، بافتراض دقة الحساب، في عدد خطوات لا يتجاوز n ، حيث n هو حجم مصفوفة النظام (هنا n  =  2).

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

يمكن استخدام طريقة التدرج المترافق لحل مسائل التحسين غير المقيدة ، مثل تقليل الطاقة . تُنسب هذه الطريقة عادةً إلى ماغنوس هيستينز وإدوارد ستيفل ، [ 1 ] [ 2 ] اللذين برمجاها على جهاز Z4 ، [ 3 ] وأجريا عليها أبحاثًا مستفيضة. [ 4 ] [ 5 ]

تُقدّم طريقة التدرج المترافق الثنائي تعميمًا للمصفوفات غير المتناظرة. وتسعى طرق التدرج المترافق غير الخطية المختلفة إلى إيجاد القيم الدنيا لمسائل التحسين غير الخطية.

وصف المشكلة التي تعالجها التدرجات المترافقة

لنفترض أننا نريد حل نظام المعادلات الخطية

أx=ب{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }

بالنسبة للمتجهx{\displaystyle \mathbf {x} }، حيث المعروفن×ن{\displaystyle n\times n}مصفوفةأ{\displaystyle \mathbf {A} }متناظر (أي ،أتي=أ{\displaystyle \mathbf {A} ^{\mathsf {T}}=\mathbf {A} }), موجب التحديد (أيxتيأx>0{\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {Ax} >0}لجميع المتجهات غير الصفريةx{\displaystyle \mathbf {x} }فيRن{\displaystyle \mathbb {R} ^{n}}وحقيقي ، وب{\displaystyle \mathbf {b} }معروف أيضًا. نرمز إلى الحل الوحيد لهذا النظام بـx*{\displaystyle \mathbf {x} _{*}}.

الاشتقاق كطريقة مباشرة

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

نقول إن متجهين غير صفريينu{\displaystyle \mathbf {u} }وv{\displaystyle \mathbf {v} }مترافقة (بالنسبة إلىأ{\displaystyle \mathbf {A} }) لو

uتيأv=0.{\displaystyle \mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =0.}

منذأ{\displaystyle \mathbf {A} }إذا كانت متناظرة وموجبة التحديد، فإن الطرف الأيسر يُعرّف ضربًا داخليًا

uتيأv=⟨u،v⟩أ:=⟨أu،v⟩=⟨u،أتيv⟩=⟨u،أv⟩.{\displaystyle \mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =\langle \mathbf {u} ,\mathbf {v} \rangle _{\mathbf {A} }:=\langle \mathbf {A} \mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} ^{\mathsf {T}}\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} \mathbf {v} \rangle .}

يكون المتجهان مترافقين إذا وفقط إذا كانا متعامدين بالنسبة لهذا الجداء الداخلي. والترافق علاقة متناظرة: إذاu{\displaystyle \mathbf {u} }هو مرافق لـv{\displaystyle \mathbf {v} }، ثمv{\displaystyle \mathbf {v} }هو مرافق لـu{\displaystyle \mathbf {u} }لنفترض أن

P={ص1،...،صن}{\displaystyle P=\{\mathbf {p} _{1},\dots ,\mathbf {p} _{n}\}}

هي مجموعة منن{\displaystyle n}المتجهات المترافقة فيما بينها بالنسبة إلىأ{\displaystyle \mathbf {A} }، أيصأناتيأصج=0{\displaystyle \mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0}للجميعأنا≠ج{\displaystyle i\neq j}. ثمP{\displaystyle P}يشكل أساسًا لـRن{\displaystyle \mathbb {R} ^{n}}ويمكننا التعبير عن الحلx*{\displaystyle \mathbf {x} _{*}}لأx=ب{\displaystyle \mathbf {Ax} =\mathbf {b} }على هذا الأساس:

x*=∑أنا=1نαأناصأنا⇒أx*=∑أنا=1نαأناأصأنا.//

حل المسألة بضربها من اليسارأx=ب{\displaystyle \mathbf {Ax} =\mathbf {b} }مع المتجهصكتي{\displaystyle \mathbf {p} _{k}^{\mathsf {T}}}العائد

صكتيب=صكتيأx*=∑أنا=1نαأناصكتيأصأنا=∑أنا=1نαأنا⟨صك،صأنا⟩أ=αك⟨صك،صك⟩أ{\displaystyle \mathbf {p} _{k}^{\mathsf {T}}\mathbf {b} =\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _ {k} ^ {\mathsf {T}}\mathbf {A} \mathbf {p} _{i}=\sum _{i=1}^{n}\alpha _{i}\left\langle \mathbf {p} _{k},\mathbf {p} _{i}\right\rangle _{\mathbf {A} }=\alpha _{k}\left\langle \mathbf {ص} _{ك},\mathbf {ص} _ {ك}\يمين\rangle _{\mathbf {A} }}

وهكذا

αك=⟨صك،ب⟩⟨صك،صك⟩أ.{\displaystyle \alpha _{k}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\langle \mathbf {p} _{k},\mathbf {p} _{k}\rangle _{\mathbf {A} }}}.}

وهذا يعطي الطريقة التالية [ 4 ] لحل المعادلةأx=ب{\displaystyle \mathbf {Ax} =\mathbf {b} }: ابحث عن سلسلة منن{\displaystyle n}الاتجاهات المترافقة، ثم احسب المعاملاتαك{\displaystyle \alpha _{k}}.

كطريقة تكرارية

إذا اخترنا المتجهات المترافقةصك{\displaystyle \mathbf {p} _{k}}بعناية، قد لا نحتاج إلى جميعها للحصول على تقريب جيد للحلx*{\displaystyle \mathbf {x} _{*}}لذا، نريد اعتبار طريقة التدرج المترافق طريقة تكرارية. وهذا يسمح لنا أيضًا بحل الأنظمة تقريبًا حيثن{\displaystyle n}حجمها كبير لدرجة أن الطريقة المباشرة ستستغرق وقتاً طويلاً جداً.

نرمز إلى التخمين الأولي لـx*{\displaystyle \mathbf {x} _{*}}بواسطةx0{\displaystyle \mathbf {x} _{0}}(يمكننا أن نفترض دون فقدان للعمومية أنx0=0{\displaystyle \mathbf {x} _{0}=\mathbf {0} }وإلا فضع في اعتبارك النظامأz=ب-أx0{\displaystyle \mathbf {Az} =\mathbf {b} -\mathbf {Ax} _{0}}بدلاً من ذلك). بدءاً منx0{\displaystyle \mathbf {x} _{0}}نبحث عن الحل، وفي كل تكرار نحتاج إلى مقياس يخبرنا ما إذا كنا أقرب إلى الحل.x*{\displaystyle \mathbf {x} _{*}}(وهو أمر غير معروف لنا). ينبع هذا المقياس من حقيقة أن الحلx*{\displaystyle \mathbf {x} _{*}}وهي أيضًا القيمة الصغرى الوحيدة للدالة التربيعية التالية

و(x)=12xتيأx-xتيب،x∈Rن.{\displaystyle f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {A} \mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {b} ,\qquad \mathbf {x} \in \mathbb {R} ^{n}\,.}

يتضح وجود قيمة صغرى فريدة من نوعها لأن مصفوفة هيسيان للمشتقات الثانية متناظرة وموجبة التحديد.

ح(و(x))=أ،{\displaystyle \mathbf {H} (f(\mathbf {x} ))=\mathbf {A} \,,}

وأنّ أداة التصغير (استخدام)دو(x)=0{\displaystyle Df(\mathbf {x} )=0}) يحل المسألة الأولية ويستنتج من مشتقته الأولى

∇و(x)=أx-ب.{\displaystyle \nabla f(\mathbf {x} )=\mathbf {A} \mathbf {x} -\mathbf {b} \,.}

يشير هذا إلى أخذ متجه الأساس الأولص0{\displaystyle \mathbf {p} _{0}}أن يكون معكوس تدرجو{\displaystyle f}فيx=x0{\displaystyle \mathbf {x} =\mathbf {x} _{0}}تدرجو{\displaystyle f}يساويأx-ب{\displaystyle \mathbf {Ax} -\mathbf {b} }بدءاً من تخمين أوليx0{\displaystyle \mathbf {x} _{0}}وهذا يعني أننا نأخذص0=ب-أx0{\displaystyle \mathbf {p} _{0}=\mathbf {b} -\mathbf {Ax} _{0}}ستكون المتجهات الأخرى في الأساس مترافقة مع التدرج، ومن هنا جاء اسم طريقة التدرج المترافق . لاحظ أنص0{\displaystyle \mathbf {p} _{0}}وهو أيضًا الباقي الناتج عن هذه الخطوة الأولية من الخوارزمية.

يتركرك{\displaystyle \mathbf {r} _{k}}ليكن الباقي عندك{\displaystyle k}الخطوة رقم:

رك=ب-أxك.{\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}.}

كما لوحظ أعلاه،رك{\displaystyle \mathbf {r} _{k}}هو التدرج السالب لـو{\displaystyle f}فيxك{\displaystyle \mathbf {x} _{k}}لذا، تتطلب طريقة التدرج الهبوطي التحرك في الاتجاه rk . ومع ذلك، نصر هنا على أن الاتجاهاتصك{\displaystyle \mathbf {p} _{k}}يجب أن تكون مترافقة. إحدى الطرق العملية لفرض ذلك هي اشتراط بناء اتجاه البحث التالي من الباقي الحالي وجميع اتجاهات البحث السابقة. يُعد قيد الترافق قيدًا من نوع التعامد المعياري، وبالتالي يمكن اعتبار الخوارزمية مثالًا على تعامد غرام-شميدت . وهذا يُعطي التعبير التالي:

صك=رك-∑أنا<كركتيأصأناصأناتيأصأناصأنا// {A} \mathbf {p} _{i}}}\mathbf {p} _{i}}

(انظر الصورة في أعلى المقال لمعرفة تأثير قيد الاقتران على التقارب). باتباع هذا النهج، يُعطى الموقع الأمثل التالي بواسطة

xك+1=xك+αكصك{\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}

مع

αك=صكتي(ب-أxك)صكتيأصك=صكتيركصكتيأصك،{\displaystyle \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {p} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}},}

حيث تستنتج المساواة الأخيرة من تعريفرك{\displaystyle \mathbf {r} _{k}}. التعبير عنαك{\displaystyle \alpha _{k}}يمكن اشتقاق ذلك إذا استبدلنا تعبير x k +1 في f وقمنا بتقليله بالنسبة إلىαك{\displaystyle \alpha _{k}}

و(xك+1)=و(xك+αكصك)=:ز(αك)ز′(αك)=!0⇒αك=صكتي(ب-أxك)صكتيأصك.{\displaystyle {\begin{aligned}f(\mathbf {x} _{k+1})&=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})=:g(\alpha _{k})\\g'(\alpha _{k})&{\overset {!}{=}}0\quad \Rightarrow \quad \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}\,.\end{aligned}}}

الخوارزمية الناتجة

تُقدّم الخوارزمية المذكورة أعلاه أبسط شرح لطريقة التدرج المترافق. ظاهريًا، تتطلب الخوارزمية كما هي مُوضّحة تخزين جميع اتجاهات البحث السابقة ومتجهات البقايا، بالإضافة إلى العديد من عمليات ضرب المصفوفات بالمتجهات، وبالتالي قد تكون مُكلفة حسابيًا. مع ذلك، يُظهر تحليل أدقّ للخوارزمية [ 6 ] : صفحة 558 أنرأنا{\displaystyle \mathbf {r} _{i}}متعامد معرج{\displaystyle \mathbf {r} _{j}}، أيرأناتيرج=0{\displaystyle \mathbf {r} _{i}^{\mathsf {T}}\mathbf {r} _{j}=0}، لأنا≠ج{\displaystyle i\neq j}. وصأنا{\displaystyle \mathbf {p} _{i}}يكونأ{\displaystyle \mathbf {A} }-متعامد معصج{\displaystyle \mathbf {p} _{j}}، أيصأناتيأصج=0{\displaystyle \mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0}، لأنا≠ج{\displaystyle i\neq j}ويمكن اعتبار ذلك أنه مع تقدم الخوارزمية،صأنا{\displaystyle \mathbf {p} _{i}}ورأنا{\displaystyle \mathbf {r} _{i}}تمتد على نفس فضاء كريلوف الفرعي ، حيثرأنا{\displaystyle \mathbf {r} _{i}}تشكل الأساس المتعامد بالنسبة للجداء الداخلي القياسي، وصأنا{\displaystyle \mathbf {p} _{i}}تشكل الأساس المتعامد بالنسبة للجداء الداخلي الناتج عنأ{\displaystyle \mathbf {A} }. لذلك،xك{\displaystyle \mathbf {x} _{k}}يمكن اعتبارها إسقاطًا لـx{\displaystyle \mathbf {x} }في فضاء كريلوف الفرعي.

أي، إذا بدأت طريقة CG بـx0=0{\displaystyle \mathbf {x} _{0}=0}ثم [ 7 ]xك=أرزمأنانy∈Rن{(x*-y)⊤أ(x*-y):y∈فترة⁡{ب،أب،...،أك-1ب}}{\displaystyle x_{k}=\mathrm {argmin} _{y\in \mathbb {R} ^{n}}{\left\{(x_{*}-y)^{\top }A(x_{*}-y):y\in \operatorname {span} \left\{b,Ab,\ldots ,A^{k-1}b\right\}\right\}}}أينx*{\displaystyle x_{*}}الحل هوأx=ب{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }.

فيما يلي شرح مفصل للخوارزمية المستخدمة في حل المسألةأx=ب{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }أينأ{\displaystyle \mathbf {A} }هي مصفوفة حقيقية، متناظرة، موجبة التحديد. متجه الإدخالx0{\displaystyle \mathbf {x} _{0}}يمكن أن يكون حلاً أولياً تقريبياً أو0{\displaystyle \mathbf {0} }إنها صيغة مختلفة للإجراء المحدد المذكور أعلاه.

ر0:=ب-أx0لو ر0 إذا كانت صغيرة بما يكفي، فقم بالعودة x0 ونتيجة لذلكص0:=ر0ك:=0يكررαك:=ركتيركصكتيأصكxك+1:=xك+αكصكرك+1:=رك-αكأصكلو رك+1 إذا كانت صغيرة بما يكفي، فقم بالخروج من الحلقةβك:=رك+1تيرك+1ركتيركصك+1:=رك+1+βكصكك:=ك+1نهاية التكراريعود xك+1 ونتيجة لذلك{\displaystyle {\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&{\hbox{if }}\mathbf {r} _{0}{\text{ is sufficiently small, then return }}\mathbf {x} _{0}{\text{ as the result}}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{repeat}}\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad {\hbox{if }}\mathbf {r} _{k+1}{\text{ is sufficiently small, then exit loop}}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad k:=k+1\\&{\text{end repeat}}\\&{\text{return }}\mathbf {x} _{k+1}{\text{ as the result}}\end{aligned}}}

هذه هي الخوارزمية الأكثر استخدامًا. نفس الصيغة لـβك{\displaystyle \beta _{k}}كما يستخدم أيضًا في طريقة التدرج المترافق غير الخطي لفليتشر-ريفز .

إعادة التشغيل

نلاحظ أنx1{\displaystyle \mathbf {x} _{1}}يتم حسابها بواسطة طريقة التدرج الهبوطي المطبقة علىx0{\displaystyle \mathbf {x} _{0}}. جلسةβك=0{\displaystyle \beta _{k}=0}سيؤدي ذلك بالمثل إلىxك+1{\displaystyle \mathbf {x} _{k+1}}تم حسابها بواسطة طريقة التدرج الهبوطي منxك{\displaystyle \mathbf {x} _{k}}أي، يمكن استخدامها كطريقة بسيطة لإعادة تشغيل تكرارات التدرج المترافق. [ 4 ] قد تؤدي عمليات إعادة التشغيل إلى إبطاء التقارب، ولكنها قد تحسن الاستقرار إذا ساءت طريقة التدرج المترافق، على سبيل المثال، بسبب خطأ التقريب .

حساب البواقي الصريح

الصيغxك+1:=xك+αكصك{\displaystyle \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}ورك:=ب-أxك{\displaystyle \mathbf {r} _{k}:=\mathbf {b} -\mathbf {Ax} _{k}}، وكلاهما صحيح في الحساب الدقيق، مما يجعل الصيغرك+1:=رك-αكأصك{\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}ورك+1:=ب-أxك+1{\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}متكافئان رياضياً. يُستخدم الأول في الخوارزمية لتجنب عملية ضرب إضافية بـأ{\displaystyle \mathbf {A} }بما أن المتجهأصك{\displaystyle \mathbf {Ap} _{k}}تم حسابها بالفعل لتقييمαك{\displaystyle \alpha _{k}}قد يكون الخيار الأخير أكثر دقة، حيث يحل محل الحساب الصريح.رك+1:=ب-أxك+1{\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}بالنسبة للطريقة الضمنية عن طريق التكرار الخاضع لتراكم أخطاء التقريب ، وبالتالي يوصى بها للتقييم العرضي. [ 8 ]

يُستخدم معيار الباقي عادةً كمعيار للتوقف. معيار الباقي الصريحرك+1:=ب-أxك+1{\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}يوفر مستوىً مضمونًا من الدقة في العمليات الحسابية الدقيقة وفي وجود أخطاء التقريب ، حيث يتوقف التقارب بشكل طبيعي. في المقابل، فإن الباقي الضمنيرك+1:=رك-αكأصك{\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}من المعروف أن السعة تستمر في الانخفاض إلى ما دون مستوى أخطاء التقريب ، وبالتالي لا يمكن استخدامها لتحديد ركود التقارب.

حساب ألفا وبيتا

في الخوارزمية،αك{\displaystyle \alpha _{k}}يتم اختيارها بحيثرك+1{\displaystyle \mathbf {r} _{k+1}}متعامد معرك{\displaystyle \mathbf {r} _{k}}يتم تبسيط المقام من

αك=ركتيركركتيأصك=ركتيركصكتيأصك{\displaystyle \alpha _{k}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}}

منذرك+1=صك+1-βكصك{\displaystyle \mathbf {r} _{k+1}=\mathbf {p} _{k+1}-\mathbf {\beta } _{k}\mathbf {p} _{k}}. الβك{\displaystyle \beta _{k}}يتم اختيارها بحيثصك+1{\displaystyle \mathbf {p} _{k+1}}هو مرافق لـصك{\displaystyle \mathbf {p} _{k}}. بدءًا،βك{\displaystyle \beta _{k}}يكون

βك=-رك+1تيأصكصكتيأصك{\displaystyle \beta _{k}=-{\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}}

استخدام

رك+1=رك-αكأصك{\displaystyle \mathbf {r} _{k+1}=\mathbf {r} _{k}-\alpha _{k}\mathbf {A} \mathbf {p} _{k}}

وبالمثل

أصك=1αك(رك-رك+1)،{\displaystyle \mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}(\mathbf {r} _{k}-\mathbf {r} _{k+1}),}

بسطβك{\displaystyle \beta _{k}}تمت إعادة كتابتها على النحو التالي

رك+1تيأصك=1αكرك+1تي(رك-رك+1)=-1αكرك+1تيرك+1{\displaystyle \mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})=-{\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}

لأنرك+1{\displaystyle \mathbf {r} _{k+1}}ورك{\displaystyle \mathbf {r} _{k}}هي متعامدة بحكم تصميمها. يُعاد كتابة المقام على النحو التالي

صكتيأصك=(رك+βك-1صك-1)تيأصك=1αكركتي(رك-رك+1)=1αكركتيرك{\displaystyle \mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}=(\mathbf {r} _{k}+\beta _{k-1}\mathbf {p} _{k-1})^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}

باستخدام ذلك، يتم تحديد اتجاهات البحثصك{\displaystyle \mathbf {p} _{k}}تكون مترافقة، ومرة ​​أخرى، تكون البواقي متعامدة. وهذا يعطيβ{\displaystyle \beta }في الخوارزمية بعد الإلغاءαك{\displaystyle \alpha _{k}}.

مثال على الكود بلغة جوليا (لغة برمجة)

باستخدام الجبر الخطي""" x = conjugate_gradient(A, b, x0 = zero(b); atol=length(b)*eps(norm(b))أعد حل المعادلة `A * x = b` باستخدام طريقة التدرج المترافق.يجب أن تكون `A` مصفوفة موجبة محددة أو عامل خطي آخر.`x0` هو التخمين الأولي للحل (الافتراضي هو متجه الصفر).يمثل `atol` التسامح المطلق في مقدار الباقي `b - A * x`للتقارب (الافتراضي هو إبسيلون الآلة).تُرجع الدالة متجه الحل التقريبي `x`."""دالة conjugate_gradient (A , b :: AbstractVector , x0 :: AbstractVector = zero ( b ); atol = length ( b ) * eps ( norm ( b )))x = copy ( x0 ) # تهيئة الحلr = b - A * x0 # الباقي الأوليp = نسخة ( r ) # اتجاه البحث الأوليr²old = r ' * r # المعيار التربيعي للباقيk = 0بينما r²old > atol ^ 2 # كرر حتى التقاربAp = A * p # اتجاه البحثα = r²old / ( p ' * Ap ) # حجم الخطوة@. x += α * p # حل التحديث# تحديث القيمة المتبقية:إذا كان ( k + 1 ) % 16 يساوي صفرًا # كل 16 تكرارًا، أعد حساب الباقي من البدايةr .= b .- A * x # لتجنب تراكم الأخطاء العدديةآخر@. r -= α * Ap # استخدم صيغة التحديث التي توفر عملية ضرب مصفوفة في متجه واحدةنهايةr²new = r ' * r@. p = r + ( r²new / r²old ) * p # تحديث اتجاه البحثr²old = r²new # تحديث معيار مربع البواقيk += 1نهايةإرجاع xنهاية

مثال على الكود في MATLAB

دالة x = conjugate_gradient ( A, b, x0, tol )% إرجاع حل المعادلة `A * x = b` باستخدام طريقة التدرج المترافق.تذكير: يجب أن تكون المصفوفة A متناظرة وموجبة التحديد.إذا كان عدد الهامش أقل من 4tol = eps ;نهايةr = b - A * x0 ;p = r ;rsold = r ' * r ;x = x0 ;طالما أن الجذر التربيعي ( rsold ) > tolAp = A * p ;alpha = rsold / ( p ' * Ap );x = x + alpha * p ;r = r - alpha * Ap ;rsnew = r ' * r ;p = r + ( rsnew / rsold ) * p ;rsold = rsnew ;نهايةنهاية

مثال عددي

لنعتبر النظام الخطي Ax = b المعطى بالعلاقة التالية

أx=[4113][x1x2]=[12]،{\displaystyle \mathbf {A} \mathbf {x} ={\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}1\\2\end{bmatrix}},}

سنقوم بتنفيذ خطوتين من طريقة التدرج المترافق بدءًا من التخمين الأولي

x0=[21]{\displaystyle \mathbf {x} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}}

من أجل إيجاد حل تقريبي للنظام.

حل

للعلم، الحل الدقيق هو

x=[111711]≈[0.09090.6364]{\displaystyle \mathbf {x} ={\begin{bmatrix}{\frac {1}{11}}\\\\{\frac {7}{11}}\end{bmatrix}}\approx {\begin{bmatrix}0.0909\\\\0.6364\end{bmatrix}}}

تتمثل خطوتنا الأولى في حساب متجه الباقي r₀ المرتبط بـ x₀ . يُحسب هذا الباقي من الصيغة r₀ = b - Ax₀ ، وفي حالتنا يساوي

ر0=[12]-[4113][21]=[-8-3]=ص0.{\displaystyle \mathbf {r} _{0}={\begin{bmatrix}1\\2\end{bmatrix}}-{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}2\\1\end{bmatrix}}={\begin{bmatrix}-8\\-3\end{bmatrix}}=\mathbf {p} _{0}.}

بما أن هذه هي التكرار الأول، فسوف نستخدم متجه البقايا r 0 كاتجاه البحث الأولي p 0 ؛ ستتغير طريقة اختيار p k في التكرارات اللاحقة.

نحسب الآن القيمة العددية α 0 باستخدام العلاقة

α0=ر0تير0ص0تيأص0=[-8-3][-8-3][-8-3][4113][-8-3]=73331≈0.2205{\displaystyle \alpha _{0}={\frac {\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}{\mathbf {p} _{0}^{\mathsf {T}}\mathbf {Ap} _{0}}}={\frac {{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}={\frac {73}{331}}\approx 0.2205}

يمكننا الآن حساب x 1 باستخدام الصيغة

x1=x0+α0ص0=[21]+73331[-8-3]≈[0.23560.3384].{\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\alpha _{0}\mathbf {p} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}+{\frac {73}{331}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}.}

تُنهي هذه النتيجة التكرار الأول، وهي عبارة عن حل تقريبي "مُحسَّن" للنظام، x1 . يمكننا الآن الانتقال إلى حساب متجه الباقي التالي r1 باستخدام الصيغة .

ر1=ر0-α0أص0=[-8-3]-73331[4113][-8-3]≈[-0.28100.7492].{\displaystyle \mathbf {r} _{1}=\mathbf {r} _{0}-\alpha _{0}\mathbf {A} \mathbf {p} _{0}={\begin{bmatrix}-8\\-3\end{bmatrix}}-{\frac {73}{331}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}.}

تتمثل خطوتنا التالية في هذه العملية في حساب القيمة العددية β 0 التي سيتم استخدامها في النهاية لتحديد اتجاه البحث التالي p 1 .

β0=ر1تير1ر0تير0≈[-0.28100.7492][-0.28100.7492][-8-3][-8-3]=0.0088.{\displaystyle \beta _{0}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}=0.0088.}

الآن، باستخدام هذا العدد القياسي β 0 ، يمكننا حساب اتجاه البحث التالي p 1 باستخدام العلاقة

ص1=ر1+β0ص0≈[-0.28100.7492]+0.0088[-8-3]=[-0.35110.7229].{\displaystyle \mathbf {p} _{1}=\mathbf {r} _{1}+\beta _{0}\mathbf {p} _{0}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}+0.0088{\begin{bmatrix}-8\\-3\end{bmatrix}}={\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}.}

نقوم الآن بحساب القيمة العددية α 1 باستخدام القيمة p 1 التي حصلنا عليها حديثًا باستخدام نفس الطريقة المستخدمة لحساب α 0 .

α1=ر1تير1ص1تيأص1≈[-0.28100.7492][-0.28100.7492][-0.35110.7229][4113][-0.35110.7229]=0.4122.{\displaystyle \alpha _{1}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {p} _{1}^{\mathsf {T}}\mathbf {Ap} _{1}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-0.3511&0.7229\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}}}=0.4122.}

وأخيراً، نجد x 2 باستخدام نفس الطريقة المستخدمة لإيجاد x 1 .

x2=x1+α1ص1≈[0.23560.3384]+0.4122[-0.35110.7229]=[0.09090.6364].{\displaystyle \mathbf {x} _{2}=\mathbf {x} _{1}+\alpha _{1}\mathbf {p} _{1}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}+0.4122{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}={\begin{bmatrix}0.0909\\0.6364\end{bmatrix}}.}

النتيجة، x 2 ، هي تقريب "أفضل" لحل النظام من x 1 و x 0. لو تم استخدام الحساب الدقيق في هذا المثال بدلاً من الدقة المحدودة، لكان من الممكن نظرياً الوصول إلى الحل الدقيق بعد n = 2 تكرار ( حيث n هي رتبة النظام).

خاصية الإنهاء المحدود

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

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

ولتوضيح ذلك، انظر إلى النظام التالي:

أ=[3-2-24]،ب=[11]{\displaystyle A={\begin{bmatrix}3&-2\\-2&4\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}1\\1\end{bmatrix}}}

نبدأ من تخمين أوليx0=[12]{\displaystyle \mathbf {x} _{0}={\begin{bmatrix}1\\2\end{bmatrix}}}. منذأ{\displaystyle A}إذا كانت المصفوفة متناظرة وموجبة التحديد، وكان النظام ثنائي الأبعاد، فيجب أن تجد طريقة التدرج المترافق الحل الدقيق في خطوتين على الأكثر. يوضح كود MATLAB التالي هذا السلوك:

A = [ 3 , - 2 ; - 2 , 4 ]; x_true = [ 1 ; 1 ]; b = A * x_true ;x = [ 1 ; 2 ]; % التخمين الأولي r = b - A * x ; p = r ;لـ k = 1 : 2 Ap = A * p ; alpha = ( r ' * r ) / ( p ' * Ap ); x = x + alpha * p ; r_new = r - alpha * Ap ; beta = ( r_new ' * r_new ) / ( r ' * r ); p = r_new + beta * p ; r = r_new ; نهايةعرض ( 'الحل الدقيق:' ); عرض ( x );

تؤكد النتائج أن الطريقة تصل إلى[11]{\displaystyle {\begin{bmatrix}1\\1\end{bmatrix}}}بعد دورتين، يتوافق ذلك مع التوقع النظري. يوضح هذا المثال كيف تتصرف طريقة التدرج المترافق كطريقة مباشرة في ظل ظروف مثالية.

تطبيق على الأنظمة المتفرقة

تتمتع خاصية الإنهاء المحدود أيضًا بآثار عملية في حل الأنظمة المتفرقة الكبيرة، والتي تظهر بشكل متكرر في التطبيقات العلمية والهندسية. على سبيل المثال، تجزئة معادلة لابلاس ثنائية الأبعاد∇2u=0{\displaystyle \nabla ^{2}u=0}يؤدي استخدام الفروق المحدودة على شبكة منتظمة إلى نظام خطي متفرقأx=ب{\displaystyle A\mathbf {x} =\mathbf {b} }، أينأ{\displaystyle A}متناظرة وموجبة التحديد.

باستخدام5×5{\displaystyle 5\times 5}تُنتج الشبكة الداخلية25×25{\displaystyle 25\times 25}النظام، ومصفوفة المعاملاتأ{\displaystyle A}يحتوي على نمط استنسل خماسي النقاط. كل صف منأ{\displaystyle A}تحتوي على خمسة عناصر غير صفرية على الأكثر، تُمثل النقطة المركزية وجيرانها المباشرين. على سبيل المثال، قد تبدو المصفوفة الناتجة عن هذه الشبكة كما يلي:

أ=[4-10⋯-10⋯-14-1⋯00⋯0-14-100⋯⋮⋮⋱⋱⋱⋮-10⋯-14-1⋯00⋯0-14⋯⋮⋮⋯⋯⋯⋱]{\displaystyle A={\begin{bmatrix}4&-1&0&\cdots &-1&0&\cdots \\-1&4&-1&\cdots &0&0&\cdots \\0&-1&4&-1&0&0&\cdots \\\vdots &\vdots &\ddots &\ddots &\ddots &\vdots \\-1&0&\cdots &-1&4&-1&\cdots \\0&0&\cdots &0&-1&4&\cdots \\\vdots &\vdots &\cdots &\cdots &\cdots &\ddots \end{bmatrix}}}

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

خصائص التقارب

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

باعتبارها طريقة تكرارية ، تعمل طريقة التدرج المترافق بشكل رتيب (في معيار الطاقة) على تحسين التقريبات.xك{\displaystyle \mathbf {x} _{k}}قد تصل هذه الطريقة إلى الحل الدقيق، وقد تحقق التفاوت المطلوب بعد عدد قليل نسبيًا من التكرارات (مقارنة بحجم المشكلة). ويكون التحسن عادةً خطيًا، وتتحدد سرعته برقم الحالة.κ(أ){\displaystyle \kappa (A)}مصفوفة النظامأ{\displaystyle A}الأكبرκ(أ){\displaystyle \kappa (A)}أي أن التحسن يكون أبطأ. [ 9 ]

لكن تظهر حالة مثيرة للاهتمام عندما تكون القيم الذاتية متباعدة لوغاريتميًا لمصفوفة متناظرة كبيرة. على سبيل المثال، لنفترضأ=سؤالدسؤالتي{\displaystyle A=QDQ^{T}}أينسؤال{\displaystyle Q}هي مصفوفة متعامدة عشوائية ود{\displaystyle D}هي مصفوفة قطرية ذات قيم ذاتية تتراوح منλن=1{\displaystyle \lambda _{n}=1}لλ1=106{\displaystyle \lambda _{1}=10^{6}}، متباعدة لوغاريتميًا. على الرغم من خاصية الإنهاء المحدود لـ CGM، حيث يجب نظريًا الوصول إلى الحل الدقيق في أكثر منن{\displaystyle n}مع تقدم الخطوات، قد تُظهر الطريقة ركودًا في التقارب. في مثل هذه الحالة، حتى بعد عدد أكبر بكثير من التكرارات - على سبيل المثال، عشرة أضعاف حجم المصفوفة - قد ينخفض ​​الخطأ بشكل طفيف فقط (على سبيل المثال، إلى10-5{\displaystyle 10^{-5}}علاوة على ذلك، قد يتذبذب الخطأ التكراري بشكل كبير، مما يجعله غير موثوق به كشرط للتوقف. ولا يُعزى ضعف التقارب هذا إلى رقم الشرط وحده (على سبيل المثال،κ2(أ)=106{\displaystyle \kappa _{2}(A)=10^{6}})، بل يعتمد الأداء على توزيع القيم الذاتية نفسه. فعندما تكون القيم الذاتية متباعدة بشكل أكثر انتظامًا أو موزعة عشوائيًا، تختفي عادةً مشكلات التقارب هذه، مما يُبرز أن أداء CGM لا يعتمد فقط علىκ(أ){\displaystyle \kappa (A)}ولكن أيضًا حول كيفية توزيع القيم الذاتية. [ 10 ]

لوκ(أ){\displaystyle \kappa (A)}عندما يكون النظام كبيرًا، تُستخدم عملية التكييف المسبق عادةً لاستبدال النظام الأصليأx-ب=0{\displaystyle \mathbf {Ax} -\mathbf {b} =0}معم-1(أx-ب)=0{\displaystyle \mathbf {M} ^{-1}(\mathbf {Ax} -\mathbf {b} )=0}بحيثκ(م-1أ){\displaystyle \kappa (\mathbf {M} ^{-1}\mathbf {A} )}أصغر منκ(أ){\displaystyle \kappa (\mathbf {A} )}انظر أدناه.

نظرية التقارب

عرّف مجموعة جزئية من كثيرات الحدود على النحو التالي:

Πك*:={ ص∈Πك : ص(0)=1 }،{\displaystyle \Pi _{k}^{*}:=\left\lbrace \ p\in \Pi _{k}\ :\ p(0)=1\ \right\rbrace \,,}

أينΠك{\displaystyle \Pi _{k}}هي مجموعة كثيرات الحدود ذات الدرجة القصوىك{\displaystyle k}.

يترك(xك)ك{\displaystyle \left(\mathbf {x} _{k}\right)_{k}}لتكن التقريبات التكرارية للحل الدقيقx*{\displaystyle \mathbf {x} _{*}}وحدد الأخطاء على النحو التالي:هـك:=xك-x*{\displaystyle \mathbf {e} _{k}:=\mathbf {x} _{k}-\mathbf {x} _{*}}الآن، يمكن تقريب معدل التقارب على النحو التالي [ 4 ] [ 11 ]

‖هـك‖أ=مينص∈Πك*‖ص(أ)هـ0‖أ≤مينص∈Πك*الأعلىλ∈σ(أ)|ص(λ)| ‖هـ0‖أ≤2(κ(أ)-1κ(أ)+1)ك ‖هـ0‖أ≤2خبرة⁡(-2كκ(أ)) ‖هـ0‖أ،{\displaystyle {\begin{aligned}\left\|\mathbf {e} _{k}\right\|_{\mathbf {A} }&=\min _{p\in \Pi _{k}^{*}}\left\|p(\mathbf {A} )\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq \min _{p\in \Pi _{k}^{*}}\,\max _{\lambda \in \sigma (\mathbf {A} )}|p(\lambda )|\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq 2\left({\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\right)^{k}\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq 2\exp \left({\frac {-2k}{\sqrt {\kappa (\mathbf {A} )}}}\right)\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\,,\end{aligned}}}

أينσ(أ){\displaystyle \sigma (\mathbf {A} )}يشير إلى الطيف ، وκ(أ){\displaystyle \kappa (\mathbf {A} )}يشير إلى رقم الحالة .

هذا يدل علىك=12κ(أ)سجل⁡(‖هـ0‖أε-1){\displaystyle k={\tfrac {1}{2}}{\sqrt {\kappa (\mathbf {A} )}}\log \left(\left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\varepsilon ^{-1}\right)}تكفي التكرارات لتقليل الخطأ إلى2ε{\displaystyle 2\varepsilon }لأيε>0{\displaystyle \varepsilon >0}.

لاحظ، الحد المهم عندماκ(أ){\displaystyle \kappa (\mathbf {A} )}يميل إلى∞{\displaystyle \infty }

κ(أ)-1κ(أ)+1≈1-2κ(أ)لκ(أ)≫1.{\displaystyle {\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\approx 1-{\frac {2}{\sqrt {\kappa (\mathbf {A} )}}}\quad {\text{for}}\quad \kappa (\mathbf {A} )\gg 1\,.}

يُظهر هذا الحد معدل تقارب أسرع مقارنةً بالطرق التكرارية لجاكوبي أو جاوس-سيدل التي تتناسب مع≈1-2κ(أ){\displaystyle \approx 1-{\frac {2}{\kappa (\mathbf {A} )}}}.

لا يُفترض وجود خطأ تقريب في نظرية التقارب، ولكن حد التقارب يكون صالحًا بشكل عام في الممارسة العملية كما تم شرحه نظريًا [ 5 ] بواسطة آن جرينباوم .

التقارب العملي

إذا تم تهيئة النموذج عشوائيًا، فإن المرحلة الأولى من التكرارات غالبًا ما تكون الأسرع، حيث يتم التخلص من الخطأ داخل فضاء كريلوف الفرعي الذي يعكس في البداية رقم حالة فعال أصغر. أما المرحلة الثانية من التقارب، فعادةً ما تكون محددة جيدًا بواسطة حد التقارب النظري.κ(أ){\textstyle {\sqrt {\kappa (\mathbf {A} )}}}لكنها قد تكون فوق الخطية، اعتمادًا على توزيع طيف المصفوفةأ{\displaystyle A}والتوزيع الطيفي للخطأ. [ 5 ] في المرحلة الأخيرة، يتم الوصول إلى أدنى دقة ممكنة، ويتوقف التقارب أو قد تبدأ الطريقة بالتباعد. في تطبيقات الحوسبة العلمية النموذجية بصيغة الفاصلة العائمة ذات الدقة المزدوجة للمصفوفات ذات الأحجام الكبيرة، تستخدم طريقة التدرج المترافق معيار توقف بتفاوت ينهي التكرارات خلال المرحلة الأولى أو الثانية.

طريقة التدرج المترافق المُهيأ مسبقًا

في معظم الحالات، يكون التكييف المسبق ضروريًا لضمان التقارب السريع لطريقة التدرج المترافق. إذام-1{\displaystyle \mathbf {M} ^{-1}}هي متماثلة موجبة التحديد وم-1أ{\displaystyle \mathbf {M} ^{-1}\mathbf {A} }يتمتع برقم حالة أفضل منأ،{\displaystyle \mathbf {A} ,}يمكن استخدام طريقة التدرج المترافق المُهيأ مسبقًا. وهي تأخذ الشكل التالي: [ 12 ]

ر0:=ب-أx0{\displaystyle \mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}}
يحل:مz0:=ر0{\displaystyle {\textrm {Solve:}}\mathbf {M} \mathbf {z} _{0}:=\mathbf {r} _{0}}
ص0:=z0{\displaystyle \mathbf {p} _{0}:=\mathbf {z} _{0}}
ك:=0{\displaystyle k:=0\,}
يكرر
αك:=ركتيzكصكتيأصك{\displaystyle \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}}
xك+1:=xك+αكصك{\displaystyle \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}
رك+1:=رك-αكأصك{\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}
إذا كانت قيمة r k +1 صغيرة بما يكفي ، فاخرج من الحلقة .
Soلvهـ مzك+1:=رك+1{\displaystyle \mathrm {Solve} \ \mathbf {M} \mathbf {z} _{k+1}:=\mathbf {r} _{k+1}}
βك:=رك+1تيzك+1ركتيzك{\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}
صك+1:=zك+1+βكصك{\displaystyle \mathbf {p} _{k+1}:=\mathbf {z} _{k+1}+\beta _{k}\mathbf {p} _{k}}
ك:=ك+1{\displaystyle k:=k+1\,}
نهاية التكرار
والنتيجة هي x k +1

الصيغة المذكورة أعلاه تعادل تطبيق طريقة التدرج المترافق المنتظم على النظام المهيأ مسبقًا [ 13 ]

هـ-1أ(هـ-1)تيx^=هـ-1ب{\displaystyle \mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}\mathbf {\hat {x}} =\mathbf {E} ^{-1}\mathbf {b} }

أين

هـهـتي=م،x^=هـتيx.{\displaystyle \mathbf {EE} ^{\mathsf {T}}=\mathbf {M} ,\qquad \mathbf {\hat {x}} =\mathbf {E} ^{\mathsf {T}}\mathbf {x} .}

يجب استخدام تحليل تشوليسكي للمُهيئ للحفاظ على تناظر النظام (وإيجابيته المحددة). ومع ذلك، لا يلزم حساب هذا التحليل، ويكفي معرفةم-1{\displaystyle \mathbf {M} ^{-1}}يمكن إثبات ذلكهـ-1أ(هـ-1)تي{\displaystyle \mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}}له نفس الطيف مثلم-1أ{\displaystyle \mathbf {M} ^{-1}\mathbf {A} }.

مصفوفة التكييف المسبقم{\displaystyle \mathbf {M} }يجب أن تكون الدالة متناظرة وموجبة التحديد وثابتة، أي لا يمكن أن تتغير من تكرار لآخر. إذا تم انتهاك أي من هذه الافتراضات المتعلقة بالمُهيئ، فقد يصبح سلوك طريقة التدرج المترافق المُهيأ غير قابل للتنبؤ.

ومن الأمثلة على المعالج المسبق الشائع الاستخدام تحليل تشوليسكي غير الكامل . [ 14 ]

استخدام المُهيئ المسبق عملياً

من المهم أن نضع في اعتبارنا أننا لا نريد عكس المصفوفةم{\displaystyle \mathbf {M} }بشكل صريح من أجل الحصول علىم-1{\displaystyle \mathbf {M} ^{-1}}للاستخدام في العملية، منذ عملية القلبم{\displaystyle \mathbf {M} }سيستغرق ذلك وقتًا/موارد حاسوبية أكثر من حل خوارزمية التدرج المترافق نفسها. على سبيل المثال، لنفترض أننا نستخدم مُهيئًا مسبقًا ناتجًا عن تحليل تشوليسكي غير الكامل. المصفوفة الناتجة هي مصفوفة مثلثية سفلية.ل{\displaystyle \mathbf {L} }ومصفوفة المُهيئ المسبق هي:

م=للتي{\displaystyle \mathbf {M} =\mathbf {LL} ^{\mathsf {T}}}

ثم علينا أن نحل:

مz=ر{\displaystyle \mathbf {Mz} =\mathbf {r} }

z=م-1ر{\displaystyle \mathbf {z} =\mathbf {M} ^{-1}\mathbf {r} }

لكن:

م-1=(ل-1)تيل-1{\displaystyle \mathbf {M} ^{-1}=(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {L} ^{-1}}

ثم:

z=(ل-1)تيل-1ر{\displaystyle \mathbf {z} =(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {L} ^{-1}\mathbf {r} }

لنأخذ متجهًا وسيطًاأ{\displaystyle \mathbf {a} }:

أ=ل-1ر{\displaystyle \mathbf {a} =\mathbf {L} ^{-1}\mathbf {r} }

ر=لأ{\displaystyle \mathbf {r} =\mathbf {L} \mathbf {a} }

منذر{\displaystyle \mathbf {r} }ول{\displaystyle \mathbf {L} }ومعروف، ول{\displaystyle \mathbf {L} }هي مثلثية سفلية، حلها لـأ{\displaystyle \mathbf {a} }يُعدّ هذا الأمر سهلاً وغير مكلف حسابياً باستخدام الاستبدال الأمامي . ثم نستبدلأ{\displaystyle \mathbf {a} }في المعادلة الأصلية:

z=(ل-1)تيأ{\displaystyle \mathbf {z} =(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {a} }

أ=لتيz{\displaystyle \mathbf {a} =\mathbf {L} ^{\mathsf {T}}\mathbf {z} }

منذأ{\displaystyle \mathbf {a} }ولتي{\displaystyle \mathbf {L} ^{\mathsf {T}}}معروفة، ولتي{\displaystyle \mathbf {L} ^{\mathsf {T}}}هي مثلثية علوية، حلها لـz{\displaystyle \mathbf {z} }يُعدّ الأمر سهلاً وغير مكلف حسابياً باستخدام الاستبدال العكسي .

باستخدام هذه الطريقة، لا حاجة إلى قلبم{\displaystyle \mathbf {M} }أول{\displaystyle \mathbf {L} }بشكل صريح على الإطلاق، وما زلنا نحصلz{\displaystyle \mathbf {z} }.

طريقة التدرج المترافق المرن المُهيأ مسبقًا

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

βك:=رك+1تي(zك+1-zك)ركتيzك{\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\left(\mathbf {z} _{k+1}-\mathbf {z} _{k}\right)}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}

بدلاً من صيغة فليتشر-ريفز

βك:=رك+1تيzك+1ركتيzك{\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}

قد يُحسّن هذا بشكلٍ كبيرٍ التقارب في هذه الحالة. [ 15 ] يُمكن تسمية هذا الإصدار من طريقة التدرج المترافق المُهيأ مسبقًا [ 16 ] بالمرن ، لأنه يسمح بتهيئة مُتغيرة. كما ثبت [ 17 ] أن الإصدار المرن قوي حتى لو لم تكن المُهيئات مُتماثلة موجبة التحديد (SPD).

يتطلب تطبيق النسخة المرنة تخزين متجه إضافي. بالنسبة لمُهيئ SPD ثابت،رك+1تيzك=0،{\displaystyle \mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k}=0,}لذا فإن كلا الصيغتين لـ β k متكافئتان في الحساب الدقيق، أي بدون خطأ التقريب .

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

مقابل طريقة الانحدار الأسرع الأمثل محليًا

في كلتا طريقتي التدرج المترافق الأصلية والمُهيأة، يكفي فقط ضبط βك:=0{\displaystyle \beta _{k}:=0}لتحقيق الأمثلية المحلية، تُستخدم طرق البحث الخطي والانحدار الأسرع . مع هذا الاستبدال، تكون المتجهات p دائمًا هي نفسها المتجهات z ، لذا لا حاجة لتخزين المتجهات p . وبالتالي، تكون كل تكرارات طرق الانحدار الأسرع أقل تكلفةً مقارنةً بطرق التدرج المترافق. مع ذلك، تتقارب الأخيرة بشكل أسرع، إلا في حال استخدام مُهيئ مُتغير (بشكل كبير) و/أو غير مُهيئ SPD، كما ذُكر أعلاه.

طريقة التدرج المترافق كوحدة تحكم تغذية راجعة مثلى للمكامل المزدوج

يمكن أيضًا اشتقاق طريقة التدرج المترافق باستخدام نظرية التحكم الأمثل . [ 19 ] في هذا النهج، تُعتبر طريقة التدرج المترافق وحدة تحكم تغذية راجعة مثالية .u=ك(x،v):=-γأ∇و(x)-γبv{\displaystyle u=k(x,v):=-\gamma _{a}\nabla f(x)-\gamma _{b}v}بالنسبة لنظام التكامل المزدوج ،x˙=v،v˙=u{\displaystyle {\dot {x}}=v,\quad {\dot {v}}=u}الكمياتγأ{\displaystyle \gamma _{a}}وγب{\displaystyle \gamma _{b}}هي مكاسب تغذية راجعة متغيرة. [ 19 ]

التدرج المترافق على المعادلات العادية

يمكن تطبيق طريقة التدرج المترافق على أي مصفوفة من الرتبة n × m بتطبيقها على المعادلات العادية A T A ومتجه الطرف الأيمن A T b ، لأن A T A مصفوفة متناظرة موجبة شبه محددة لأي A. والنتيجة هي التدرج المترافق على المعادلات العادية ( CGN أو CGNR ).

A T Ax = A T b

باعتبارها طريقة تكرارية، لا تتطلب هذه الطريقة تكوين المصفوفة A T A بشكل صريح في الذاكرة، بل يكفي إجراء عمليات ضرب المصفوفة في المتجه، وضرب منقول المصفوفة في المتجه. لذا، تُعدّ طريقة CGNR مفيدةً بشكل خاص عندما تكون A مصفوفة متفرقة، نظرًا لكفاءة هذه العمليات العالية. مع ذلك، يتمثل عيب تكوين المعادلات العادية في أن رقم الشرط κ( A T A ) يساوي κ² ( A ) ، وبالتالي قد يكون معدل تقارب CGNR بطيئًا، وقد تتأثر جودة الحل التقريبي بأخطاء التقريب. غالبًا ما يكون إيجاد مُهيئ جيد جزءًا مهمًا من استخدام طريقة CGNR.

تم اقتراح العديد من الخوارزميات (مثل CGLS وLSQR). يُزعم أن خوارزمية LSQR تتمتع بأفضل استقرار عددي عندما تكون المصفوفة A سيئة التكييف، أي عندما يكون لها رقم حالة كبير .

طريقة التدرج المترافق للمصفوفات الهرميتية المعقدة

يمكن توسيع طريقة التدرج المترافق مع تعديل بسيط لحل نظام المعادلات الخطية، بمعلومية المصفوفة A ذات القيم المركبة والمتجه b.أx=ب{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }بالنسبة للمتجه ذي القيم المركبة x، حيث A مصفوفة هيرميتية (أي A' = A) وموجبة التحديد ، ويرمز الرمز ' إلى منقولة المرافق . التعديل البسيط هو استبدال منقولة المرافق بمنقولة المصفوفة الحقيقية في كل مكان.

المزايا والعيوب

تم تلخيص مزايا وعيوب طرق التدرج المترافق في محاضرات نيميروفسكي وبنتال [ 20 ] : القسم 7.3

مثال مرضي

هذا المثال مأخوذ من [ 21 ] ليكنت∈(0،1){\textstyle t\in (0,1)}، وتحديددبليو=[تتت1+تتت1+تتت⋱⋱⋱تت1+ت]،ب=[10⋮0]{\displaystyle W={\begin{bmatrix}t&{\sqrt {t}}&&&&\\{\sqrt {t}}&1+t&{\sqrt {t}}&&&\\&{\sqrt {t}}&1+t&{\sqrt {t}}&&\\&&{\sqrt {t}}&\ddots &\ddots &\\&&&\ddots &&\\&&&&&{\sqrt {t}}\\&&&&{\sqrt {t}}&1+t\end{bmatrix}},\quad b={\begin{bmatrix}1\\0\\\vdots \\0\end{bmatrix}}}منذدبليو{\displaystyle W}إذا كانت قابلة للعكس، فإنه يوجد حل وحيد لهادبليوx=ب{\textstyle Wx=b}حلّها باستخدام خوارزمية التدرج المترافق يعطينا تقاربًا سيئًا إلى حد ما:‖ب-دبليوxك‖2=(1/ت)ك،‖ب-دبليوxن‖2=0{\displaystyle \|b-Wx_{k}\|^{2}=(1/t)^{k},\quad \|b-Wx_{n}\|^{2}=0}بعبارة أخرى، خلال عملية التدرج المترافق، ينمو الخطأ بشكل أسي، حتى يصبح فجأة صفراً عند إيجاد الحل الفريد.

انظر أيضاً

مراجع

  1. ↑ هيستينز، ماغنوس ر .؛ ستيفل، إدوارد (ديسمبر 1952). "طرق التدرجات المترافقة لحل الأنظمة الخطية" (ملف PDF) . مجلة البحوث التابعة للمكتب الوطني للمعايير . 49 (6): 409. doi : 10.6028/jres.049.044 .
  2. ↑ سترايتر، ت. أ. (1971). حول توسيع فئة ديفيدون-برودن من طرق تقليل شبه نيوتن من الرتبة الأولى إلى فضاء هيلبرت لانهائي الأبعاد مع تطبيقات على مسائل التحكم الأمثل (أطروحة دكتوراه). جامعة ولاية كارولينا الشمالية. hdl : 2060/19710026200 – عبر خادم التقارير الفنية التابع لناسا.
  3. ^ سبايسر ، أمبروس (2004). "Konrad Zuse und die ERMETH: Ein weltweiter Architektur-Vergleich" [ كونراد زوسي وإيرميث: مقارنة عالمية بين البنى المعمارية ] . في Hellige، هانز ديتر (محرر). جيش المعلوماتية. Visionen، Paradigmen، Leitmotive (باللغة الألمانية). برلين: سبرينغر. ص. 185. ردمك  3-540-00217-0.
  4. 1 2 3 4 بولياك، بوريس (1987). مقدمة في التحسين .
  5. 1 2 3 غرينباوم، آن (1997). الطرق التكرارية لحل الأنظمة الخطية . doi : 10.1137/1.9781611970937 . ISBN 978-0-89871-396-1.
  6. ↑ بوتيف، زدرافكو إي.؛ كروس، ديرك ب.؛ تايمر، توماس (2025). علم البيانات والتعلم الآلي: الأساليب الرياضية والإحصائية ( الطبعة الثانية). بوكا راتون؛ لندن: مطبعة سي آر سي. الصفحات 558-559 . ISBN   978-1-032-48868-4.
  7. ↑ باكيت، إليوت؛ تروغدون، توماس (مارس 2023). "شمولية خوارزميات التدرج المترافق وMINRES على مصفوفات التغاير العيني" . مجلة الاتصالات في الرياضيات البحتة والتطبيقية . 76 (5): 1085-1136 . arXiv : 2007.00640 . doi : 10.1002/cpa.22081 . ISSN 0010-3640 . 
  8. ↑ شيوشوك، جوناثان ر (1994). مقدمة لطريقة التدرج المترافق بدون ألم مبرح (PDF) .
  9. ↑ سعد، يوسف (2003). الطرق التكرارية للأنظمة الخطية المتفرقة ( الطبعة الثانية ). فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية. ص 195. ISBN   978-0-89871-534-7.
  10. ↑ هولمز، م. (2023). مقدمة في الحوسبة العلمية وتحليل البيانات، الطبعة الثانية . سبرينغر. ISBN 978-3-031-22429-4.
  11. ↑ هاك بوش، و. (21-06-2016). الحل التكراري لأنظمة المعادلات المتفرقة الكبيرة ( الطبعة الثانية). سويسرا: سبرينغر. ISBN  978-3-319-28483-5. OCLC 952572240 . 
  12. ↑ باريت، ريتشارد؛ بيري، مايكل؛ تشان، توني ف.؛ ديميل، جيمس؛ دوناتو، جون؛ دونغارا، جاك؛ إيخوت، فيكتور؛ بوزو، رولدان؛ رومين، تشارلز؛ فان دير فورست، هينك. قوالب لحل الأنظمة الخطية: لبنات بناء الطرق التكرارية (ملف PDF) (الطبعة الثانية ). فيلادلفيا، بنسلفانيا: SIAM. ص 13. تاريخ الاسترجاع : 31 مارس 2020 .  
  13. ↑ غولوب، جين هـ.؛ فان لون، تشارلز ف. (2013). حسابات المصفوفات ( الطبعة الرابعة). مطبعة جامعة جونز هوبكنز. القسم 11.5.2. ISBN  978-1-4214-0794-4.
  14. ↑ كونكوس، ب.؛ غولوب، ج.هـ؛ موران، ج. (1985). "التكييف المسبق الكتلي لطريقة التدرج المترافق" . مجلة SIAM للحوسبة العلمية والإحصائية . 6 (1): 220-252 . doi : 10.1137/0906018 .
  15. ↑ غولوب، جين هـ.؛ يي، تشيانغ (1999). "طريقة التدرج المترافق المُهيأة غير الدقيقة مع التكرار الداخلي والخارجي". مجلة SIAM للحوسبة العلمية . 21 (4): 1305. CiteSeerX 10.1.1.56.1755 . doi : 10.1137/S1064827597323415 . 
  16. ↑ نوتاي، إيفان (2000). "التدرجات المترافقة المرنة". مجلة SIAM للحوسبة العلمية . 22 (4): 1444-1460 . CiteSeerX 10.1.1.35.7473 . doi : 10.1137/S1064827599362314 . 
  17. ↑ بووميستر، هنريكوس؛ دوغيرتي، أندرو؛ كنيازيف، أندرو ف. (2015). "التكييف المسبق غير المتناظر لطرق التدرج المترافق والانحدار الأشد 1" . وقائع علوم الحاسوب . 51 : 276-285 . arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 . S2CID 51978658 . 
  18. ↑ كنيازيف، أندرو ف.؛ لاشوك، إيليا (2008). "طرق الانحدار الأسرع والتدرج المترافق مع التكييف المسبق المتغير". مجلة SIAM لتحليل المصفوفات وتطبيقاتها . 29 (4): 1267. arXiv : math/0605767 . doi : 10.1137/060675290 . S2CID 17614913 . 
  19. 1 2 روس، آي إم ، "نظرية التحكم الأمثل للتحسين المتسارع"، arXiv : 1902.09004 ، 2019.
  20. ↑ نيميروفسكي وبن-تال (2023). "التحسين الثالث: التحسين المحدب" (PDF) .
  21. ↑ بينينجتون، فابيان بيدريجوسا، كورتني باكيت، توم تروغدون، جيفري. "دليل تعليمي حول نظرية المصفوفات العشوائية والتعلم الآلي" . random-matrix-learning.github.io . تاريخ الاسترجاع: 5 ديسمبر 2023 .{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

للمزيد من القراءة

  • أتكينسون، كينديل أ. (1988). "القسم 8.9". مقدمة في التحليل العددي (  الطبعة الثانية). جون وايلي وأولاده. ISBN 978-0-471-50023-0.
  • أفرييل، موردخاي (2003). البرمجة غير الخطية: التحليل والأساليب . دار نشر دوفر. ISBN 978-0-486-43227-4.
  • جولوب، جين هـ.؛ فان لون، تشارلز ف. (2013). "الفصل 11". حسابات المصفوفات (  الطبعة الرابعة). مطبعة جامعة جونز هوبكنز. ISBN 978-1-4214-0794-4.
  • سعد، يوسف (1 أبريل 2003). "الفصل 6" . الطرق التكرارية للأنظمة الخطية المتفرقة (  الطبعة الثانية). SIAM. ISBN 978-0-89871-534-7.
  • جيرار موران: "الكشف عن الأخطاء الصامتة وتصحيحها في خوارزمية التدرج المترافق"، الخوارزميات العددية، المجلد 92 (2023)، الصفحات  869-891. الرابط: https://doi.org/10.1007/s11075-022-01380-1
  • موران، جيرارد؛ تيشي، بيتر (2024). تقدير معيار الخطأ في خوارزمية التدرج المترافق . سيام. ISBN 978-1-61197-785-1.