الاسترخاء المفرط المتتالي

في الجبر الخطي العددي ، تُعدّ طريقة الاسترخاء المتتالي ( SOR ) شكلاً مُعدّلاً من طريقة جاوس-سيدل لحلّ نظام المعادلات الخطية ، مما يُؤدي إلى تقارب أسرع. ويمكن استخدام طريقة مماثلة لأي عملية تكرارية بطيئة التقارب .

طُوِّرت هذه الطريقة في آنٍ واحد من قِبَل ديفيد إم. يونغ الابن وستانلي ب. فرانكل عام ١٩٥٠ بهدف حلّ الأنظمة الخطية تلقائيًا على الحواسيب الرقمية. وقد استُخدمت طرق الاسترخاء المفرط قبل عمل يونغ وفرانكل، ومن أمثلتها طريقة لويس فراي ريتشاردسون ، والطرق التي طوّرها آر. في. ساوثويل . إلا أن هذه الطرق صُمِّمت للحساب بواسطة حاسبات بشرية ، ما يتطلب خبرةً لضمان التقارب نحو الحل، الأمر الذي جعلها غير قابلة للتطبيق في برمجة الحواسيب الرقمية. وقد نُوقشت هذه الجوانب في أطروحة ديفيد إم. يونغ الابن ^{[ ١ ].}

بفرض وجود نظام مربع من n معادلة خطية مع مجهول x :

$${\displaystyle A\mathbf {x} =\mathbf {b} }$$

أين:

$${\displaystyle {\begin{aligned}&A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\\[1ex]&\mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.\end{aligned}}}$$

ثم يمكن تحليل A إلى مكون قطري D ، ومكونين مثلثيين سفليين وعلويين L و U :

$${\displaystyle A=D+L+U,}$$ أين $${\displaystyle D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\quad L={\begin{bmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.}$$

يمكن إعادة كتابة نظام المعادلات الخطية على النحو التالي:

$${\displaystyle \left(D+\omega L\right)\mathbf {x} =\omega \mathbf {b} -\left[\omega U+\left(\omega -1\right)D\right]\mathbf {x} }$$

بالنسبة لثابت ω > 1، يسمى عامل الاسترخاء .

طريقة الاسترخاء المتتالي هي تقنية تكرارية تحل الطرف الأيسر من هذه المعادلة لإيجاد قيمة x ، باستخدام القيمة السابقة لـ x في الطرف الأيمن. ويمكن كتابة ذلك تحليليًا على النحو التالي:

$${\displaystyle {\begin{aligned}\mathbf {x} ^{(k+1)}&=\left(D+\omega L\right)^{-1}\left(\omega \mathbf {b} -\left[\omega U+\left(\omega -1\right)D\right]\mathbf {x} ^{(k)}\right)\\&=L_{\omega }\mathbf {x} ^{(k)}+\mathbf {c} ,\end{aligned}}}$$

أين${\displaystyle \mathbf {x} ^{(k)}}$هي التقريب أو التكرار رقم k لـ${\displaystyle \mathbf {x} }$و${\displaystyle \mathbf {x} ^{(k+1)}}$هي التكرار التالي أو k + 1 من${\displaystyle \mathbf {x} }$ومع ذلك، من خلال الاستفادة من الشكل المثلثي لـ ( D + ωL ) ، يمكن حساب عناصر x ^{( k + 1) بالتتابع باستخدام} التعويض الأمامي :

$${\displaystyle x_{i}^{(k+1)}=\left(1-\omega \right)x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}$$

ويمكن كتابة ذلك مرة أخرى تحليليًا في شكل مصفوفة-متجه دون الحاجة إلى عكس المصفوفة${\displaystyle (D+\omega L)}$: ^{[ 2 ]}

$${\displaystyle \mathbf {x} ^{(k+1)}=\left(1-\omega \right)\mathbf {x} ^{(k)}+\omega D^{-1}\left(\mathbf {b} -L\mathbf {x} ^{(k+1)}-U\mathbf {x} ^{(k)}\right).}$$

إن اختيار عامل الاسترخاء ω ليس بالأمر السهل بالضرورة، ويعتمد على خصائص مصفوفة المعاملات . في عام 1947، أثبت أوستروفسكي أنه إذا${\displaystyle A}$إذا كانت متناظرة وموجبة التحديد${\displaystyle \rho (L_{\omega })<1}$ل${\displaystyle 0<\omega <2}$وبالتالي، يتبع ذلك تقارب عملية التكرار، لكننا نهتم بشكل عام بالتقارب الأسرع بدلاً من مجرد التقارب.

بما أنه يمكن استبدال العناصر أثناء حسابها في هذه الخوارزمية، فلا حاجة إلا لمتجه تخزين واحد، ويتم الاستغناء عن فهرسة المتجهات. وتتلخص الخوارزمية فيما يلي:

المدخلات: A ، b ، ω المخرجات:${\displaystyle \phi }$ اختر تخمينًا أوليًا${\displaystyle \phi }$للوصول إلى الحل، كرر العملية حتى التقارب. من أجل i من 1 إلى n ، اجعل σ تساوي 0. من أجل j من 1 إلى n ، إذا كان j ≠ i ، فاجعل σ تساوي 0.${\displaystyle \sigma +a_{ij}\phi _{j}}$end if end ( j -loop) تعيين${\displaystyle \phi _{i}}$ل${\displaystyle (1-\omega )\phi _{i}+\omega \,(b_{i}-\sigma )/a_{ii}}$نهاية ( حلقة i ) تحقق مما إذا تم الوصول إلى التقارب النهاية (تكرار)

ملحوظة

${\displaystyle (1-\omega )\phi _{i}+{\frac {\omega }{a_{ii}}}(b_{i}-\sigma )}$ويمكن كتابتها أيضاً${\displaystyle \phi _{i}+\omega \left({\frac {b_{i}-\sigma }{a_{ii}}}-\phi _{i}\right)}$وبالتالي توفير عملية ضرب واحدة في كل تكرار للحلقة الخارجية for .

لدينا النظام الخطي

$${\displaystyle {\begin{aligned}4x_{1}-x_{2}-6x_{3}+0x_{4}&=2,\\-5x_{1}-4x_{2}+10x_{3}+8x_{4}&=21,\\0x_{1}+9x_{2}+4x_{3}-2x_{4}&=-12,\\1x_{1}+0x_{2}-7x_{3}+5x_{4}&=-6.\end{aligned}}}$$

لحل المعادلات، نختار عامل استرخاء${\displaystyle \omega =0.5}$ومتجه تخمين أولي${\displaystyle \phi =(0,0,0,0)}$وفقًا لخوارزمية الاسترخاء المتتالي، يتم الحصول على الجدول التالي، الذي يمثل تكرارًا نموذجيًا مع التقريبات، والذي من الناحية المثالية، ولكن ليس بالضرورة، يجد الحل الدقيق، (3، -2 ، 2، 1) ، في 38 خطوة.

التكرار	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$
0 1	0.25	-2.78125​	1.6289062	0.5152344
0 2	1.2490234	-2.2448974​	1.9687712	0.9108547
0 3	2.070478	-1.6696789​	1.5904881	0.76172125
...	...	...	...	...
37	2.9999998	- 2.0	2.0	1.0
38	3.0	- 2.0	2.0	1.0

فيما يلي تطبيق بسيط للخوارزمية بلغة Common Lisp .

;; اضبط تنسيق الفاصلة العائمة الافتراضي على "long-float" لضمان التشغيل الصحيح على نطاق أوسع من الأرقام. ( setf *read-default-float-format* 'long-float )( defparameter +MAXIMUM-NUMBER-OF-ITERATIONS+ 100 "عدد التكرارات التي يجب أن تتوقف الخوارزمية عن  العمل بعدها، بغض النظر عن حلها الحالي.  قد يوفر عدد أكبر من التكرارات نتيجة أكثر دقة، ولكنه يفرض  متطلبات أداء أعلى." )( declaim ( type ( integer 0 * ) +MAXIMUM-NUMBER-OF-ITERATIONS+ ))( defun get-errors ( computed-solution exact-solution ) "لكل عنصر من عناصر متجه الحل المحسوب، تسترجع هذه الدالة  خطأه بالنسبة لمتجه الحل الدقيق المتوقع، وتعيد  متجهًا من قيم الخطأ.  ---  على الرغم من أنه يجب أن يكون كلا متجهي الإدخال متساويين في الحجم، إلا أنه  لا يتم التحقق من هذا الشرط، ويحدد أقصر متجه من المتجهين  عدد عناصر متجه الإخراج.  ---  الصيغة المعتمدة هي التالية:  let resultVectorSize = min(computedSolution.length, exactSolution.length)  let resultVector = new vector of resultVectorSize  For i from 0 to (resultVectorSize - 1)  resultVector[i] = exactSolution[i] - computedSolution[i]  Return resultVector" ( declare ( type ( vector number * ) computed-solution )) ( declare ( type ( vector number * ) exact-solution )) ( map ' ( vector number * ) #' - exact-solution computed-solution ))( defun is-convergent ( errors &key ( error-tolerance 0.001 )) "يتحقق هذا من الوصول إلى التقارب بالنسبة  لمتجه الأخطاء (ERRORS) الذي يسجل التباين بين متجه الحل المحسوب  ومتجه الحل الدقيق.  ---  يتحقق التقارب إذا وفقط إذا كان كل  مكون من مكونات الخطأ المطلق أقل من أو يساوي قيمة تحمل الخطأ (ERRORS-TOLERANCE)، أي:  لكل e في متجه الأخطاء (ERRORS)، يكون الشرط: abs(e) <= errorTolerance." ( declare ( type ( vector number * ) errors )) ( declare ( type number error-tolerance )) ( flet (( error-is-acceptable ( error ) ( declare ( type number error )) ( <= ( abs error ) error-tolerance ))) ( every #' error-is-acceptable errors )))( defun make-zero-vector ( size ) "ينشئ ويعيد متجهًا بحجم SIZE مع تعيين جميع عناصره إلى 0." ( declare ( type ( integer 0 * ) size )) ( make-array size :initial-element 0.0 :element-type 'number '))( defun successive-over-relaxation ( A b omega &key ( phi ( make-zero-vector ( length b ))) ( convergence-check #' ( lambda ( iteration phi ) ( declare ( ignore phi )) ( >= iteration +MAXIMUM-NUMBER-OF-ITERATIONS+ )))) "تُنفذ هذه الدالة طريقة الاسترخاء المتتالي (SOR)، المُطبقة على  المعادلات الخطية المُحددة بواسطة المصفوفة A ومتجه الطرف الأيمن  B، باستخدام عامل الاسترخاء أوميغا، وتُعيد  متجه الحل المحسوب.  --- تتمثل  الخطوة الأولى في الخوارزمية، وهي اختيار قيمة ابتدائية PHI،  في مُعامل الكلمة المفتاحية الاختياري PHI، والذي يكون افتراضيًا  متجهًا صفريًا بنفس بنية B. في حال توفيره،  سيتم تعديل هذا المتجه بشكل جذري. على أي حال،  يُمثل متجه PHI قيمة نتيجة الدالة.  ---  يتم تنفيذ شرط الإنهاء بواسطة CONVERGENCE-CHECK،  وهو مُسند اختياري  lambda(iteration phi) => دالة منطقية معممة  تُرجع T، مما يدل على الإنهاء الفوري عند الوصول إلى  التقارب، أو NIL، مما يدل على استمرار العملية في غير ذلك. في  تكوينها الافتراضي، تلتزم دالة CONVERGENCE-CHECK ببساطة  بوصول التكرار إلى "+MAXIMUM-NUMBER-OF-ITERATIONS+"،  متجاهلةً دقة المتجه PHI. ( declare ( type ( array number ( * * )) A )) ( declare ( type ( vector number * ) b )) ( declare ( type number omega )) ( declare ( type ( vector number * ) phi )) ( declare ( type ( function (( integer 1 * ) ( vector number * )) * ) convergence-check )) ( let (( n( array-dimension A 0 ))) ( declare ( type ( integer 0 * ) n )) ( loop for iteration from 1 by 1 do ( loop for i from 0 below n by 1 do ( let (( rho 0 )) ( declare ( type number rho )) ( loop for j from 0 below n by 1 do ( when ( /= j i ) ( let (( a[ij] ( aref A i j )) ( phi[j] ( aref phi j ))) ( incf rho ( * a[ij] phi[j] ))))) ( setf ( aref phi i ) ( + ( * ( - 1 omega ) ( aref phi i )) ( * ( / omega ( aref A i i )) ( - ( aref b i ) rho )))))) ( format T "~&~d. solution = ~a" iteration phi ) ;; تحقق من الوصول إلى التقارب. ( when ( funcall convergence-check iteration phi ) ( return )))) ( the ( vector number * ) phi ));; استدعاء الدالة باستخدام المعاملات النموذجية. ( let (( A ( make-array ( list 4 4 ) :initial-contents ' (( 4 -1 -6 0 ) ( -5 -4 10 8 ) ( 0 9 4 -2 ) ( 1 0 -7 5 )))) ( b ( vector 2 21 -12 -6 )) ( omega 0.5 ) ( exact-solution ( vector 3 -2 2 1 ))) ( successive-over-relaxation A b omega :convergence-check #' ( lambda ( iteration phi ) ( declare ( type ( integer 0 * ) iteration )) ( declare ( type ( vector number * ) phi )) ( let (( errors ( get-errors phi exact-solution ))) ( declare ( type ( vector number * ) errors )) ( format T "~&~d. errors = ~a" iteration errors ) ( or ( is-convergent errors :error-tolerance 0.0 ) ( >= iteration +الحد الأقصى لعدد التكرارات+ ))))))

تطبيق بسيط بلغة بايثون للرمز الزائف المذكور أعلاه.

استورد مكتبة NumPy باسم np، واستورد مكتبة scipy باسم linalg.def sor_solver ( A , b , omega , initial_guess , convergence_criteria ): """  هذا تطبيق للشيفرة الزائفة المذكورة في مقالة ويكيبيديا.  الوسائط:  A: مصفوفة NumPy من الرتبة n×n.  b: متجه NumPy ذو n بُعد.  omega: عامل الاسترخاء.  initial_guess: تخمين الحل الأولي الذي يبدأ به المُحلِّل.  convergence_criteria: أقصى تباين مقبول لاعتبار الحل الحالي مناسبًا.  القيمة المرجعة:  phi: متجه الحل ذو البُعد n.  """ step = 0 phi = initial_guess [:] residual = linalg . norm ( A @ phi - b ) # الباقي الأولي while residual > convergence_criteria : for i in range ( A . shape [ 0 ]): sigma = 0 for j in range ( A . shape [ 1 ]): if j != i : sigma += A [ i , j ] * phi [ j ] phi [ i ] = ( 1 - omega ) * phi [ i ] + ( omega / A [ i , i ]) * ( b [ i ] - sigma ) residual = linalg . norm ( A @ phi - b ) step += 1 print ( "الخطوة {} الباقي: {:10.6g} " . format ( step , residual )) return phi# مثال توضيحي يُحاكي المثال الوارد في مقالة ويكيبيديا residual_convergence = 1e-8 omega = 0.5 # عامل الاسترخاءA = np.array ( [ [ 4 , -1 , -6 , 0 ] , [ -5 , -4 , 10 , 8 ] , [ 0 , 9 , 4 , -2 ] , [ 1 , 0 , -7 , 5 ] ] )​b = np.array ( [ 2 , 21 , -12 , -6 ] )​​initial_guess = np.zeros ( 4 )​​phi = sor_solver ( A , b , omega , initial_guess , residual_convergence ) print ( phi )

النسخة الخاصة بالمصفوفات المتناظرة A ، والتي

$${\displaystyle U=L^{T},\,}$$

يُشار إليه باسم الاسترخاء المتتالي المتناظر ، أو ( SSOR )، حيث

$${\displaystyle P=\left({\frac {D}{\omega }}+L\right){\frac {\omega }{2-\omega }}D^{-1}\left({\frac {D}{\omega }}+U\right),}$$

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

$${\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}-\gamma ^{k}P^{-1}\left(A\mathbf {x} ^{k}-\mathbf {b} \right),\ k\geq 0.}$$

يُنسب الفضل في تطوير طريقتي SOR و SSOR إلى ديفيد إم. يونغ جونيور.

يمكن استخدام أسلوب مماثل لأي طريقة تكرارية. إذا كان التكرار الأصلي على الشكل التالي

$${\displaystyle x_{n+1}=f(x_{n})}$$

ثم سيستخدم الإصدار المعدل

$${\displaystyle x_{n+1}^{\mathrm {SOR} }=(1-\omega )x_{n}^{\mathrm {SOR} }+\omega f(x_{n}^{\mathrm {SOR} }).}$$

مع ذلك، فإن الصيغة المذكورة أعلاه، والمستخدمة لحل أنظمة المعادلات الخطية، ليست حالة خاصة من هذه الصيغة إذا اعتُبر x متجهًا كاملًا. إذا استُخدمت هذه الصيغة بدلًا من ذلك، فستبدو معادلة حساب المتجه التالي كما يلي:

$${\displaystyle \mathbf {x} ^{(k+1)}=\left(1-\omega \right)\mathbf {x} ^{(k)}+\omega L_{*}^{-1}\left(\mathbf {b} -U\mathbf {x} ^{(k)}\right),}$$

أين${\displaystyle L_{*}=L+D}$قيم${\displaystyle \omega >1}$تُستخدم هذه القيم لتسريع تقارب عملية بطيئة التقارب، بينما تُستخدم قيم أخرى${\displaystyle \omega <1}$تُستخدم غالبًا للمساعدة في إرساء تقارب عملية تكرارية متباعدة أو تسريع تقارب عملية متجاوزة .

توجد طرق متنوعة لضبط معلمات الاسترخاء بشكل تكيفي${\displaystyle \omega }$بناءً على السلوك الملحوظ لعملية التقارب. عادةً ما تساعد هذه الطرق في الوصول إلى تقارب فائق الخطية لبعض المسائل، لكنها تفشل في مسائل أخرى.

• طريقة جاكوبي
• انتشار الاعتقاد الغاوسي
• تقسيم المصفوفة

• تتضمن هذه المقالة نصًا من المقالة Successive_over-relaxation_method_-_SOR الموجودة على CFD-Wiki والتي تخضع لرخصة GFDL .

• أبراهام بيرمان، روبرت ج. بليمونز ، المصفوفات غير السالبة في العلوم الرياضية ، 1994، SIAM. ISBN 0-89871-321-8.
• بلاك، نويل ومور، شيرلي. "طريقة الاسترخاء المتتالي" . عالم الرياضيات .
• أ. هادجيديموس، الاسترخاء المتتالي المفرط (SOR) والأساليب ذات الصلة ، مجلة الرياضيات الحسابية والتطبيقية 123 (2000)، 177-199.
• يوسف سعد ، الطرق التكرارية للأنظمة الخطية المتفرقة ، الطبعة الأولى، PWS، 1996.
• نسخة Netlib من "Templates for the Solution of Linear Systems" من تأليف باريت وآخرون.
• ريتشارد إس. فارغا 2002 تحليل المصفوفات التكراري ، الطبعة الثانية (من طبعة برنتيس هول لعام 1962)، سبرينغر-فيرلاغ.
• ديفيد إم. يونغ الابن، الحل التكراري للأنظمة الخطية الكبيرة ، دار النشر الأكاديمية، 1971. (أعيد طبعه بواسطة دوفر، 2003)

• وحدة طريقة SOR
• برنامج لحل أنظمة المعادلات الخطية ثلاثية الأقطار يعتمد على SOR، مكتوب بلغة C++