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

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

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

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

توجد العديد من أنواع خوارزميات الشبكات المتعددة، ولكن السمة المشتركة بينها هي اعتمادها على تسلسل هرمي من التجزئات (الشبكات). وتتمثل الخطوات المهمة فيما يلي: ^{[ 5 ] [ 6 ]}

• التنعيم – تقليل الأخطاء عالية التردد، على سبيل المثال باستخدام بضع تكرارات من طريقة جاوس-سيدل .
• حساب الباقي - حساب الخطأ المتبقي بعد عملية (عمليات) التنعيم.
• التقييد – تقليل دقة الخطأ المتبقي إلى شبكة أكثر خشونة.
• الاستيفاء أو التمديد - استيفاء تصحيح محسوب على شبكة أكثر خشونة إلى شبكة أكثر دقة.
• التصحيح – إضافة حل الشبكة الخشنة المطولة إلى الشبكة الدقيقة.

تتوفر العديد من طرق الشبكة المتعددة، وتختلف هذه الطرق في المفاضلة بين سرعة حل التكرار الواحد ومعدل التقارب معه. الأنواع الرئيسية الثلاثة هي: دورة V، ودورة F، ودورة W. وتختلف هذه الطرق في نوع وعدد دورات الحبيبات الخشنة التي تُنفذ في كل تكرار دقيق. تُنفذ خوارزمية دورة V واحدة للحبيبات الخشنة. أما دورة F فتُنفذ دورة V للحبيبات الخشنة متبوعة بدورة F للحبيبات الخشنة، بينما تُنفذ دورة W دورتين للحبيبات الخشنة في كل تكرار. بالنسبة لمسألة ثنائية الأبعاد منفصلة ، ​​تستغرق دورة F وقتًا أطول بنسبة 83% من دورة V، بينما تستغرق دورة W وقتًا أطول بنسبة 125%. إذا طُبِّقت المسألة في مجال ثلاثي الأبعاد، فإن تكرار دورة F ودورة W يستغرقان وقتًا أطول بنسبة 64% و75% على التوالي من تكرار دورة V، مع إهمال التكاليف الإضافية . عادةً، تُحقق دورة W تقاربًا مشابهًا لدورة F. مع ذلك، في مسائل الحمل الحراري والانتشار ذات أعداد بيكلي العالية ، قد تُظهر دورة W تفوقًا في معدل التقارب لكل تكرار على دورة F. تتنوع خيارات عوامل التنعيم بشكل كبير، إذ تشمل طرق فضاء كريلوف الجزئي ، ويمكن تهيئتها مسبقًا .

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

دالة phi = V_Cycle ( phi,f,h ) % شبكة متعددة الدورات V المتكررة لحل معادلة بواسون (∇² phi = f) على شبكة منتظمة بمسافة h% التنعيم المسبق phi = التنعيم ( phi , f , h );% حساب الأخطاء المتبقية r = residual ( phi , f , h );% Restriction rhs = restriction ( r );eps = zeros ( size ( rhs ));% إيقاف التكرار عند أصغر حجم للشبكة، وإلا استمرار التكرار إذا تم الوصول إلى أصغر حجم للشبكة eps = coarse_level_solve ( eps , rhs , 2 * h ); else eps = V_Cycle ( eps , rhs , 2 * h ); end% الإطالة والتصحيح φ = φ + الإطالة ( eps );% بعد التنعيم phi = smoothing ( phi , f , h ); end

دالة phi = F_Cycle ( phi,f,h ) % شبكة متعددة الدورات F المتكررة لحل معادلة بواسون (∇² phi = f) على شبكة منتظمة بمسافة h% التنعيم المسبق phi = التنعيم ( phi , f , h );% حساب الأخطاء المتبقية r = residual ( phi , f , h );% Restriction rhs = restriction ( r );eps = zeros ( size ( rhs ));% إيقاف التكرار عند أصغر حجم للشبكة، وإلا استمرار التكرار إذا تم الوصول إلى أصغر حجم للشبكة eps = coarse_level_solve ( eps , rhs , 2 * h ); else eps = F_Cycle ( eps , rhs , 2 * h ); end% الإطالة والتصحيح φ = φ + الإطالة ( eps );% إعادة تنعيم phi = التنعيم ( phi , f , h );% حساب الأخطاء المتبقية r = residual ( phi , f , h );% Restriction rhs = restriction ( r );% إيقاف التكرار عند أصغر حجم للشبكة، وإلا استمرار التكرار إذا تم الوصول إلى أصغر حجم للشبكة eps = coarse_level_solve ( eps , rhs , 2 * h ); else eps = V_Cycle ( eps , rhs , 2 * h ); end% الإطالة والتصحيح φ = φ + الإطالة ( eps );% بعد التنعيم phi = smoothing ( phi , f , h ); end

دالة phi = W_cycle ( phi,f,h ) % شبكة متعددة الدورات W المتكررة لحل معادلة بواسون (∇² phi = f) على شبكة منتظمة بمسافة h% التنعيم المسبق phi = التنعيم ( phi , f , h );% حساب الأخطاء المتبقية r = residual ( phi , f , h );% Restriction rhs = restriction ( r );eps = zeros ( size ( rhs ));% إيقاف التكرار عند أصغر حجم للشبكة، وإلا استمرار التكرار إذا تم الوصول إلى أصغر حجم للشبكة eps = coarse_level_solve ( eps , rhs , 2 * h ); else eps = W_cycle ( eps , rhs , 2 * h ); end% الإطالة والتصحيح φ = φ + الإطالة ( eps );% إعادة تنعيم phi = التنعيم ( phi , f , h );% حساب الأخطاء المتبقية r = residual ( phi , f , h );% Restriction rhs = restriction ( r );% إيقاف التكرار عند أصغر حجم للشبكة، وإلا استمرار التكرار إذا تم الوصول إلى أصغر حجم للشبكة eps = coarse_level_solve ( eps , rhs , 2 * h ); else eps = W_cycle ( eps , rhs , 2 * h ); end% الإطالة والتصحيح φ = φ + الإطالة ( eps );% بعد التنعيم phi = smoothing ( phi , f , h ); end

يتميز هذا النهج عن غيره من الطرق بأنه يتناسب خطيًا مع عدد العقد المنفصلة المستخدمة. بعبارة أخرى، يمكنه حل هذه المسائل بدقة معينة في عدد من العمليات يتناسب مع عدد المجاهيل.

لنفترض أن لدينا معادلة تفاضلية يمكن حلها تقريبًا (بدقة معينة) على شبكة${\displaystyle i}$بكثافة نقاط شبكية معينة${\displaystyle N_{i}}$افترض كذلك أن الحل على أي شبكة${\displaystyle N_{i}}$يمكن الحصول عليها ببذل جهد معين${\displaystyle W_{i}=\rho KN_{i}}$من حل على شبكة أكثر خشونة${\displaystyle i+1}$. هنا،${\displaystyle \rho =N_{i+1}/N_{i}<1}$تمثل هذه النسبة عدد نقاط الشبكة على الشبكات "المجاورة"، ويُفترض أنها ثابتة في جميع مستويات التسلسل الهرمي للشبكة، و${\displaystyle K}$يمثل بعض الثوابت نموذجًا لجهد حساب النتيجة لنقطة شبكية واحدة.

ثم يتم الحصول على علاقة التكرار التالية لجهد الحصول على الحل على الشبكة${\displaystyle k}$: $${\displaystyle W_{k}=W_{k+1}+\rho KN_{k}}$$

وعلى وجه الخصوص، نجد ذلك لأدق شبكة${\displaystyle N_{1}}$الذي - التي $${\displaystyle W_{1}=W_{2}+\rho KN_{1}}$$ بدمج هذين التعبيرين (وباستخدام${\displaystyle N_{k}=\rho ^{k-1}N_{1}}$) يعطي $${\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}$$

باستخدام المتسلسلة الهندسية ، نجد بعد ذلك (لعدد محدود)${\displaystyle n}$) $${\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}$$

أي أنه يمكن الحصول على حل في${\displaystyle O(N)}$الوقت. تجدر الإشارة إلى وجود استثناء واحد لهذه القاعدة.${\displaystyle O(N)}$أي استخدام شبكة متعددة الدورات W في مسألة أحادية البعد؛ سيؤدي ذلك إلى${\displaystyle O(N\log N)}$تعقيد.

يمكن استخدام طريقة الشبكة المتعددة ذات التسامح المخفّض عمدًا كمعالج مسبق فعال لحل تكراري خارجي، على سبيل المثال، ^{[ 7 ].} ولا يزال من الممكن الحصول على الحل في${\displaystyle O(N)}$يُستخدم هذا الأسلوب أيضًا في حالة استخدام طريقة الشبكة المتعددة كحلّ. ويُستخدم التكييف المسبق للشبكة المتعددة عمليًا حتى في الأنظمة الخطية، عادةً بدورة واحدة لكل تكرار، كما هو الحال في برنامج Hypre . وتتجلى ميزته الرئيسية مقارنةً بحلّ الشبكة المتعددة البحت بوضوح في المسائل غير الخطية، مثل مسائل القيم الذاتية .

إذا كانت مصفوفة المعادلة الأصلية أو مسألة القيم الذاتية متماثلة موجبة التحديد (SPD)، يُصمم المُهيئ عادةً ليكون كذلك، بحيث يمكن استخدام طرق التدرج المترافق (CG) التكرارية القياسية. قد تُعقّد قيود SPD المفروضة هذه عملية بناء المُهيئ، كأن تتطلب تنعيمًا مُنسقًا قبل وبعد المعالجة. مع ذلك، فقد ثبت ^{[ 8 ]} أن طرق الانحدار الأسرع المُهيأة وطرق CG المرنة للأنظمة الخطية SPD، وطريقة LOBPCG لمسائل القيم الذاتية المتماثلة، تتمتع بالمتانة حتى لو لم يكن المُهيئ SPD.

وُصِفَ مُهيئ BPX لأول مرة في أطروحة الدكتوراه لـ Xu ^{[ 9 ]} ونُشِرَ لاحقًا في Bramble-Pasciak-Xu ^{[ 10 ].} وهو أحد النهجين الرئيسيين للشبكات المتعددة (والآخر هو خوارزمية الشبكات المتعددة الكلاسيكية مثل V-cycle) لحل الأنظمة الجبرية واسعة النطاق الناتجة عن تجزئة النماذج في العلوم والهندسة الموصوفة بمعادلات تفاضلية جزئية. وبالنظر إلى إطار تصحيح الفضاء الجزئي ^{[ 11 ]} ، يُعد مُهيئ BPX طريقةً متوازيةً لتصحيح الفضاء الجزئي، بينما تُعد V-cycle الكلاسيكية طريقةً متتابعةً لتصحيح الفضاء الجزئي. ومن المعروف أن مُهيئ BPX أكثر توازيًا بطبيعته، وفي بعض التطبيقات أكثر قوةً من طريقة V-cycle الكلاسيكية للشبكات المتعددة. وقد استُخدِمت هذه الطريقة على نطاق واسع من قِبَل الباحثين والممارسين منذ عام 1990.

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

تعتمد مجموعة أخرى من طرق التحليل متعدد الدقة على الموجات الصغيرة . ويمكن دمج هذه الطرق مع طرق الشبكة المتعددة. ^{[ 15 ] [ 16 ]} على سبيل المثال، يتمثل أحد استخدامات الموجات الصغيرة في إعادة صياغة منهج العناصر المحدودة باستخدام طريقة متعددة المستويات. ^{[ 17 ]}

تُظهر الشبكة المتعددة التكيفية تحسينًا تكيفيًا للشبكة ، أي أنها تُعدّل الشبكة أثناء سير الحساب، بطريقة تعتمد على الحساب نفسه. ^{[ 18 ]} وتتلخص الفكرة في زيادة دقة الشبكة فقط في مناطق الحل التي تتطلب ذلك.

تشمل التوسعات المهمة عمليًا لطرق الشبكات المتعددة تقنيات لا تستخدم المعادلات التفاضلية الجزئية أو خلفية المسائل الهندسية لبناء التسلسل الهرمي متعدد المستويات. ^{[ 19 ]} تبني طرق الشبكات المتعددة الجبرية (AMG) تسلسلها الهرمي من المؤثرات مباشرةً من مصفوفة النظام. في طرق الشبكات المتعددة الجبرية التقليدية، تكون مستويات التسلسل الهرمي مجرد مجموعات فرعية من المجاهيل دون أي تفسير هندسي. (بشكل أعم، يمكن أن تكون مجاهيل الشبكة الخشنة تركيبات خطية محددة من مجاهيل الشبكة الدقيقة). وبالتالي، تصبح طرق الشبكات المتعددة الجبرية حلولًا مغلقة لبعض فئات المصفوفات المتفرقة . تُعتبر طرق الشبكات المتعددة الجبرية مفيدة بشكل أساسي عندما يصعب تطبيق الشبكات المتعددة الهندسية، ^{[ 20 ]} ولكنها تُستخدم غالبًا ببساطة لأنها تتجنب البرمجة اللازمة لتنفيذ شبكة متعددة حقيقية. في حين أن طرق الشبكات المتعددة الجبرية التقليدية طُوّرت أولًا، إلا أن هناك طريقة جبرية ذات صلة تُعرف باسم التجميع المُنعّم (SA).

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

تم اعتماد طرق الشبكة المتعددة أيضًا لحل مسائل القيمة الابتدائية . ^{[ 22 ]} ومن بين الطرق ذات الأهمية الخاصة هنا طرق الشبكة المتعددة المتوازية زمنيًا: ^{[ 23 ]} على عكس طرق رونج-كوتا الكلاسيكية أو الطرق الخطية متعددة الخطوات ، فإنها توفر التزامن في الاتجاه الزمني. ويمكن أيضًا إعادة صياغة طريقة التكامل المتوازية زمنيًا المعروفة باسم Parareal كشبكة متعددة المستويات ثنائية المستوى زمنيًا.

تظهر المسائل شبه المنفردة في عدد من التطبيقات الفيزيائية والهندسية الهامة. ومن الأمثلة البسيطة، ولكن المهمة، على المسائل شبه المنفردة صياغة الإزاحة في المرونة الخطية للمواد شبه غير القابلة للانضغاط. عادةً، تتلخص المشكلة الرئيسية لحل هذه الأنظمة شبه المنفردة في معالجة المؤثر شبه المنفرد المعطى بواسطة${\displaystyle A+\varepsilon M}$بشكل قوي فيما يتعلق بالمعامل الموجب، ولكن الصغير${\displaystyle \varepsilon }$. هنا${\displaystyle A}$هو مؤثر شبه محدد متناظر ذو فضاء صفري كبير ، بينما${\displaystyle M}$هو مؤثر متماثل موجب التحديد . وقد بُذلت جهودٌ حثيثة لتصميم طريقة متعددة الشبكات قوية وسريعة لمثل هذه المسائل شبه المنفردة. وقُدِّم دليلٌ عام كمبدأ تصميم لتحقيق معدل تقارب مستقل عن المعاملات (مثل حجم الشبكة والمعاملات الفيزيائية كنسبة بواسون التي تظهر في المؤثر شبه المنفرد) لطريقة الشبكة المتعددة المطبقة على هذه الأنظمة شبه المنفردة، ^{[ 24 ]} أي أنه في كل شبكة، يجب إنشاء تجزئة مكانية يُطبَّق عليها التنعيم، بحيث يُضمَّن الفضاء الصفري للجزء المنفرد من المؤثر شبه المنفرد في مجموع الفضاءات الصفرية المحلية، وتقاطع الفضاء الصفري مع الفضاءات المحلية الناتجة عن التجزئة المكانية.

• روابط لعروض AMG التقديمية