روشهای ایستای تکراری و ریلکسیشن
روشهای ایستای تکراری یک سیستم خطی را با تقسیم ماتریس و اعمال مکرر یک قانون بهروزرسانی ثابت حل میکنند؛ روشهای کلاسیک ژاکوبی، گاوس-سایدل و ریلکسیشن بیش از حد متوالی نمونههای اساسی این روشها هستند.
Definition
یک روش ایستای تکراری روشی است که بهروزرسانی آن در هر مرحله از یک ماتریس تکرار یکسان استفاده میکند، که از تقسیم ماتریس ضرایب به یک بخش با قابلیت معکوسپذیری آسان و یک باقیمانده مشتق شده است؛ همگرایی توسط شعاع طیفی ماتریس تکرار حاصل تعیین میشود.
Scope
این موضوع چارچوب تقسیم ماتریس، تکرارهای ژاکوبی و گاوس-سایدل، ریلکسیشن بیش از حد متوالی و انتخاب پارامتر بهینه ریلکسیشن، معیار شعاع طیفی برای همگرایی، و نقشی که این تکرارهای ساده امروزه به عنوان هموارساز در روشهای چندشبکهای و به عنوان پیششرطکننده ایفا میکنند را پوشش میدهد.
Core questions
- چگونه تقسیم ماتریس منجر به یک تکرار نقطه ثابت برای سیستم خطی میشود؟
- روشهای ژاکوبی و گاوس-سایدل چه تفاوتی دارند و چرا گاوس-سایدل معمولاً سریعتر است؟
- چگونه ریلکسیشن بیش از حد همگرایی را تسریع میکند و چگونه پارامتر بهینه انتخاب میشود؟
- تحت چه شرایطی بر روی ماتریس، این تکرارها همگرا میشوند؟
Key theories
- تقسیم ماتریس و معیار شعاع طیفی
- نوشتن ماتریس به صورت یک بخش با قابلیت معکوسپذیری آسان منهای یک باقیمانده، یک تکرار ایستا را تعریف میکند که خطای آن در هر مرحله در یک ماتریس تکرار ضرب میشود؛ تکرار برای هر حدس اولیه همگرا میشود اگر و تنها اگر شعاع طیفی آن ماتریس تکرار کمتر از یک باشد.
- ریلکسیشن بیش از حد متوالی
- با فراتر رفتن از اصلاح گاوس-سایدل با یک عامل ریلکسیشن، ریلکسیشن بیش از حد متوالی میتواند شعاع طیفی را به شدت کاهش دهد؛ برای برخی ماتریسهای ساختاریافته، یک پارامتر ریلکسیشن بهینه به صورت تحلیلی شناخته شده است و منجر به افزایش چشمگیر سرعت میشود.
Mechanisms
روش ژاکوبی هر مجهول را به طور همزمان با استفاده از مقادیر تنها از پیمایش قبلی بهروزرسانی میکند، که معادل تقسیم کردن از روی قطر است. گاوس-سایدل از جدیدترین مقادیر بهروزرسانی شده در همان پیمایش استفاده میکند، که معادل تقسیم کردن از روی بخش پایینمثلثی است و معمولاً سریعتر همگرا میشود. ریلکسیشن بیش از حد متوالی یک میانگین وزنی از مقدار قدیمی و بهروزرسانی گاوس-سایدل را تشکیل میدهد که توسط یک پارامتر ریلکسیشن کنترل میشود؛ انتخاب این پارامتر بزرگتر از یک، همگرایی را برای ماتریسهای مناسب تسریع میکند. همگرایی برای هر سه روش برای دستههایی مانند ماتریسهای کاملاً قطری غالب یا متقارن مثبت-معین تضمین شده است و با شعاع طیفی ماتریس تکرار کمیسازی میشود.
Clinical relevance
اگرچه معمولاً برای اینکه به عنوان حلکنندههای مستقل برای سیستمهای بزرگ رقابتی باشند، بسیار کند هستند، اما روشهای ایستای تکراری همچنان به عنوان هموارساز در قلب روشهای چندشبکهای، به عنوان پیششرطکنندههای ساده برای روشهای کریلوف، و به عنوان بلوکهای ساختمانی با قابلیت موازیسازی آسان اهمیت دارند؛ به ویژه گاوس-سایدل و ژاکوبی وزنی در حلکنندههای چندسطحی مدرن بسیار رایج هستند.
History
تکرارهای ژاکوبی و گاوس-سایدل به قرن نوزدهم بازمیگردند، در حالی که ریلکسیشن بیش از حد متوالی و نظریه همگرایی دقیق آن توسط دیوید یانگ و ریچارد وارگا در دهه 1950 توسعه یافتند؛ اگرچه بعدها توسط روشهای کریلوف و چندشبکهای به عنوان حلکنندههای اصلی تحتالشعاع قرار گرفتند، اما این تکرارها به عنوان اجزای ضروری طرحهای چندسطحی و پیششرطکننده احیا شدند.
Key figures
- Carl Friedrich Gauss
- Philipp Ludwig von Seidel
- David M. Young
- Richard S. Varga
Related topics
Seminal works
- saad2003
- varga2000
Frequently asked questions
- چرا گاوس-سایدل معمولاً سریعتر از ژاکوبی است؟
- گاوس-سایدل بلافاصله از مقادیر بهروزرسانی شده در همان پیمایش استفاده میکند، بنابراین اطلاعات سریعتر از طریق مجهولات منتشر میشود و معمولاً تعداد تکرارها را در مقایسه با ژاکوبی که فقط از مقادیر پیمایش قبلی استفاده میکند، نصف میکند.
- اگر این روشها کند هستند، چرا هنوز مورد مطالعه قرار میگیرند؟
- آنها هموارسازهای عالی و پیششرطکنندههای سادهای هستند. در روشهای چندشبکهای، چند پیمایش گاوس-سایدل یا ژاکوبی وزنی به طور کارآمد خطای نوسانی را حذف میکنند، که دقیقاً همان نقشی است که روشهای چندشبکهای به آن نیاز دارند، بنابراین این تکرارهای کلاسیک به عنوان اجزای حلکنندههای مدرن سریع به حیات خود ادامه میدهند.