طريقة الاتجاه المتناوب الضمنية

تُعدّ طريقة ADI عملية تكرارية من خطوتين تقوم بتحديث مساحات الأعمدة والصفوف بالتناوب لحل تقريبي لـ${\displaystyle AX-XB=C}$تتكون دورة واحدة من دورات ADI من الخطوات التالية: ^{[ 7 ]}

1. أوجد قيمة${\displaystyle X^{(j+1/2)}}$، أين${\displaystyle \left(A-\beta _{j+1}I\right)X^{(j+1/2)}=X^{(j)}\left(B-\beta _{j+1}I\right)+C.}$

2. أوجد قيمة${\displaystyle X^{(j+1)}}$، أين ${\displaystyle X^{(j+1)}\left(B-\alpha _{j+1}I\right)=\left(A-\alpha _{j+1}I\right)X^{(j+1/2)}-C}$.

الأرقام${\displaystyle (\alpha _{j+1},\beta _{j+1})}$تُسمى هذه المعاملات بمعاملات الإزاحة، ويعتمد التقارب بشكل كبير على اختيار هذه المعاملات. ^{[ 8 ] [ 9 ]} لإجراء${\displaystyle K}$تكرارات ADI، تخمين أولي${\displaystyle X^{(0)}}$مطلوب، وكذلك${\displaystyle K}$معلمات التحويل،${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$.

لو${\displaystyle A\in \mathbb {C} ^{m\times m}}$و ${\displaystyle B\in \mathbb {C} ^{n\times n}}$، ثم${\displaystyle AX-XB=C}$يمكن حلها مباشرة في${\displaystyle {\mathcal {O}}(م^{3}+n^{3})}$باستخدام طريقة بارتلز-ستيوارت . ^{[ 10 ]} لذلك، لا يكون استخدام ADI مفيدًا إلا عند ضرب المصفوفة في المتجه وحل المعادلات الخطية التي تتضمن${\displaystyle A}$و${\displaystyle B}$يمكن تطبيقها بتكلفة زهيدة.

المعادلة${\displaystyle AX-XB=C}$يوجد حل فريد إذا وفقط إذا${\displaystyle \sigma (A)\cap \sigma (B)=\emptyset }$، أين${\displaystyle \sigma (M)}$هو طيف​${\displaystyle M}$^{[ 1 ]} ومع ذلك ، فإن طريقة ADI تعمل بشكل جيد للغاية عندما${\displaystyle \sigma (A)}$و${\displaystyle \sigma (B)}$متباعدة بشكل جيد، و${\displaystyle A}$و${\displaystyle B}$هي مصفوفات طبيعية . تتحقق هذه الافتراضات، على سبيل المثال، بواسطة معادلة ليابونوف${\displaystyle AX+XA^{*}=C}$متى${\displaystyle A}$هي موجبة تمامًا . في ظل هذه الافتراضات، تُعرف معلمات الإزاحة شبه المثلى لعدة خيارات من${\displaystyle A}$و${\displaystyle B}$^{[ 8 ] [ 9 ]} بالإضافة إلى ذلك ، يمكن حساب حدود الخطأ المسبقة، مما يلغي الحاجة إلى مراقبة الخطأ المتبقي في التنفيذ.

لا يزال من الممكن تطبيق طريقة ADI حتى في حال عدم استيفاء الافتراضات المذكورة أعلاه. قد يؤثر استخدام معلمات إزاحة دون المستوى الأمثل سلبًا على التقارب، ^{[ 1 ]} كما يتأثر التقارب أيضًا بعدم انتظام التوزيع الطبيعي لـ${\displaystyle A}$أو${\displaystyle B}$(وأحيانًا يكون ذلك مفيدًا). ^{​​[ 11 ]} لوحظ أن طرق فضاء كريلوف الجزئي ، مثل طريقة فضاء كريلوف الجزئي العقلاني، ^{[ 12 ] تتقارب عادةً بشكل أسرع من طريقة ADI في هذا السياق، [ 1 ] [ 3 ]} وقد أدى ذلك إلى تطوير طرق هجينة تجمع بين ADI والإسقاط. ^{[ 3 ]}

إن مشكلة إيجاد معلمات إزاحة جيدة ليست بالمشكلة البسيطة. ويمكن فهم هذه المشكلة من خلال دراسة معادلة خطأ ADI. بعد ذلك${\displaystyle K}$في عدد التكرارات، يُعطى الخطأ بواسطة

${\displaystyle XX^{(K)}=\prod _{j=1}^{K}{\frac {(A-\alpha _{j}I)}{(A-\beta _{j}I)}}\left(XX^{(0)}\right)\prod _{j=1}^{K}{\frac {(B-\beta _{j}I)}{(B-\alpha _{j}I)}}.}$

اختيار${\displaystyle X^{(0)}=0}$ينتج عن ذلك الحد التالي للخطأ النسبي:

$\displaystyle \frac \left\|XX^{(K)}\right\|_{2}}{\|X\|_{2}}\leq \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2},\quad r_{K}(M)=\prod _{j=1}^{K}{\frac \(M-\alpha _{j}I)}{(M-\beta _{j}I)}}.}$

أين${\displaystyle \|\cdot \|_{2}}$هو معيار المشغل . المجموعة المثالية لمعاملات الإزاحة${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$تُعرّف الدالة الكسرية${\displaystyle r_{K}}$ذلك يقلل الكمية$\displaystyle \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}}$. لو${\displaystyle A}$و${\displaystyle B}$هي مصفوفات طبيعية ولها تحليلات ذاتية${\displaystyle A=V_{A}\Lambda _{A}V_{A}^{*}}$و${\displaystyle B=V_{B}\Lambda _{B}V_{B}^{*}}$، ثم

${\displaystyle \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}=\|r_{K}(\Lambda _{A})\|_{2}\|r_{K}(\Lambda _{B})^{-1}\|_{2}}$.

في العديد من التطبيقات،${\displaystyle A}$و${\displaystyle B}$هي مصفوفات كبيرة جدًا ومتفرقة، و${\displaystyle C}$يمكن اعتبارها عاملاً${\displaystyle C=C_{1}C_{2}^{*}}$، أين${\displaystyle C_{1}\in \mathbb {C} ^{m\times r},C_{2}\in \mathbb {C} ^{n\times r}}$، مع${\displaystyle r=1,2}$[ ^{1 ] في مثل هذا} السياق، قد لا يكون من الممكن تخزين المصفوفة الكثيفة المحتملة${\displaystyle X}$بشكل صريح. يمكن استخدام أحد أنواع مؤشر ADI، والذي يُسمى مؤشر ADI المُعامل، ^{[ 3 ] [ 2 ]} لحساب${\displaystyle ZY^{*}}$، أين${\displaystyle X\approx ZY^{*}}$تعتمد فعالية مؤشر ADI المُعامل على ما إذا${\displaystyle X}$يمكن تقريبها جيدًا بمصفوفة منخفضة الرتبة. ومن المعروف أن هذا صحيح في ظل افتراضات مختلفة حول${\displaystyle A}$و${\displaystyle B}$[ ^{11 ] [ 9 ]​}

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

لنفترض معادلة الانتشار الخطي في بعدين،

${\displaystyle {\partial u \over \partial t}=\left({\partial ^{2}u \over \partial x^{2}}+{\partial ^{2}u \over \partial y^{2}}\right)=(u_{xx}+u_{yy})}$

تُنتج طريقة كرانك-نيكلسون الضمنية معادلة الفروق المحدودة التالية:

${\displaystyle {u_{ij}^{n+1}-u_{ij}^{n} \over \Delta t}={1 \over 2(\Delta x)^{2}}\left(\delta _{x}^{2}+\delta _{y}^{2}\right)\left(u_{ij}^{n+1}+u_{ij}^{n}\right)}$

أين:

${\displaystyle \Delta x=\Delta y}$

و${\displaystyle \delta _{p}^{2}}$يمثل عامل الفرق الثاني المركزي للإحداثي p

${\displaystyle \delta _{p}^{2}u_{ij}=u_{ij+e_{p}}-2u_{ij}+u_{ij-e_{p}}}$

مع${\displaystyle e_{p}=(1,0)}$أو${\displaystyle (0,1)}$ل${\displaystyle p=x}$أو${\displaystyle y}$على التوالي (و${\displaystyle ij}$اختصار لنقاط الشبكة${\displaystyle (i,j)}$).

بعد إجراء تحليل الاستقرار ، يمكن إثبات أن هذه الطريقة ستكون مستقرة لأي${\displaystyle \Delta t}$.

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

تعتمد فكرة طريقة ADI على تقسيم معادلات الفروق المحدودة إلى قسمين، أحدهما مع أخذ المشتقة x ضمنيًا والآخر مع أخذ المشتقة y ضمنيًا.

${\displaystyle {u_{ij}^{n+1/2}-u_{ij}^{n} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n}\right) \over \Delta x^{2}}}$

${\displaystyle {u_{ij}^{n+1}-u_{ij}^{n+1/2} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n+1}\right) \over \Delta y^{2}}}$

إن نظام المعادلات المعني متناظر وثلاثي الأقطار (مُقسّم إلى نطاق بعرض نطاق 3)، ويتم حله عادةً باستخدام خوارزمية المصفوفة ثلاثية الأقطار .

يمكن إثبات أن هذه الطريقة مستقرة بشكل مطلق ومن الدرجة الثانية في الزمان والمكان. ^{[ 20 ]} توجد طرق ADI أكثر دقة، مثل طرق دوغلاس، ^{[ 21 ]} أو طريقة عامل f ^{[ 22 ]} التي يمكن استخدامها لثلاثة أبعاد أو أكثر.

يمكن تعميم استخدام طريقة ADI كخوارزمية لتقسيم المؤثرات . أي أنه يمكننا النظر في معادلات التطور العامة.

${\displaystyle {\dot {u}}=F_{1}u+F_{2}u,}$

أين${\displaystyle F_{1}}$و${\displaystyle F_{2}}$هي مؤثرات (ربما غير خطية) معرفة على فضاء باناخ . ^{[ 23 ] [ 24 ]} في مثال الانتشار أعلاه لدينا${\displaystyle F_{1}={\partial ^{2} \over \partial x^{2}}}$و${\displaystyle F_{2}={\partial ^{2} \over \partial y^{2}}}$.

من الممكن تبسيط طريقة ADI التقليدية إلى طريقة ADI الأساسية، التي تحتوي فقط على عوامل متشابهة في الطرف الأيسر، بينما تخلو من العوامل في الطرف الأيمن. يمكن اعتبار هذا المخطط الأساسي لطريقة ADI، ^{[ 25 ] [ 26 ]} حيث لا توجد عوامل إضافية (يتم تقليلها) في الطرف الأيمن، على عكس معظم الطرق الضمنية التقليدية التي تتكون عادةً من عوامل في كلا طرفي المعادلات. تؤدي طريقة ADI الأساسية إلى معادلات تحديث أبسط وأكثر إيجازًا وكفاءة دون التأثير سلبًا على دقة طريقة ADI التقليدية.

يمكن تبسيط العديد من الطرق الضمنية الكلاسيكية، مثل طريقة بيسمان-راشفورد، وطريقة دوغلاس-غون، وطريقة دياكونوف، وطريقة بيم-وارمينغ، وطريقة كرانك-نيكلسون، وغيرها، إلى مخططات ضمنية أساسية ذات أطراف يمنى خالية من المؤثرات. ^{[ 26 ]} في صيغها الأساسية، ترتبط طريقة FADI ذات الدقة الزمنية من الدرجة الثانية ارتباطًا وثيقًا بطريقة FLOD الأساسية أحادية البعد محليًا، والتي يمكن تطويرها إلى دقة زمنية من الدرجة الثانية، كما هو الحال في معادلات ماكسويل ثلاثية الأبعاد ^{[ 27 ] [ 28 ]} في الكهرومغناطيسية الحاسوبية . بالنسبة لمعادلات التوصيل الحراري والانتشار ثنائية وثلاثية الأبعاد، يمكن تطبيق كل من طريقتي FADI وFLOD بطريقة أبسط وأكثر كفاءة واستقرارًا مقارنةً بالطرق التقليدية. ^{[ 29 ] [ 30 ]}