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

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

تُعرَّف الطريقة التكرارية بواسطة $${\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k}),\quad k\geq 0}$$ وبالنسبة لنظام خطي معين${\displaystyle A\mathbf {x} =\mathbf {b} }$مع الحل الدقيق${\displaystyle \mathbf {x} ^{*}}$الخطأ بواسطة ​$${\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*},\quad k\geq 0.}$$ تُسمى الطريقة التكرارية خطية إذا وُجدت مصفوفة${\displaystyle C\in \mathbb {R} ^{n\times n}}$بحيث $${\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall k\geq 0}$$ وتُسمى هذه المصفوفة مصفوفة التكرار . وهي طريقة تكرارية بمصفوفة تكرار مُعطاة.${\displaystyle C}$يُطلق عليها اسم متقاربة إذا تحقق ما يلي $${\displaystyle \lim _{k\to \infty }C^{k}=0.}$$

تنص نظرية مهمة على أنه بالنسبة لطريقة تكرارية معينة ومصفوفة التكرار الخاصة بها${\displaystyle C}$يكون متقاربًا إذا وفقط إذا كان نصف قطره الطيفي${\displaystyle \rho (C)}$ أصغر من واحد، أي $${\displaystyle \rho (C)<1.}$$

تعتمد الطرق التكرارية الأساسية على تقسيم المصفوفة${\displaystyle A}$داخل $${\displaystyle A=M-N}$$ وهنا المصفوفة${\displaystyle M}$ينبغي أن تكون قابلة للعكس بسهولة . تُعرَّف الطرق التكرارية الآن على النحو التالي: $${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+\mathbf {b} ,\quad k\geq 0,}$$ أو، على نحو مماثل، $${\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}+M^{-1}\left(\mathbf {b} -A\mathbf {x} ^{k}\right),\quad k\geq 0.}$$ ومن هذا يستنتج أن مصفوفة التكرار تُعطى بواسطة $${\displaystyle C=I-M^{-1}A=M^{-1}N.}$$

تستخدم الأمثلة الأساسية للطرق التكرارية الثابتة تقسيم المصفوفة${\displaystyle A}$مثل $${\displaystyle A=D+L+U\,,\quad D:=\operatorname {diag} ((a_{ii})_{i})}$$ أين${\displaystyle D}$هو الجزء القطري فقط من${\displaystyle A}$، و${\displaystyle L}$هو الجزء السفلي المثلثي الصارم من${\displaystyle A}$. على التوالى،${\displaystyle U}$هو الجزء العلوي المثلثي الدقيق من${\displaystyle A}$.

• طريقة ريتشاردسون :$${\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$$
• طريقة جاكوبي :$${\displaystyle M:=D}$$
• طريقة جاكوبي المخمدة :$${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$$
• طريقة جاوس-سيدل :$${\displaystyle M:=D+L}$$
• طريقة الاسترخاء المتتالي المفرط (SOR):$${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$$
• الاسترخاء المتتالي المتناظر (SSOR):$${\displaystyle M:={\frac {1}{\omega \left(2-\omega \right)}}\left(D+\omega L\right)D^{-1}\left(D+\omega U\right)\quad (\omega \not \in \{0,2\})}$$

تُسمى الطرق التكرارية الثابتة الخطية أيضًا طرق الاسترخاء .

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