بخشی از مقاله
چکیده
روشهای تکراری تودرتو برای حل دستگاه معادلات خطی مورد بررسی قرار میگیرند. این روشها به صورت تکرار داخلی / خارجی است که تکرار خارجی آن براساس روشهای شکافی هستند، که در هر تکرار برای حل دستگاه معادلات خطی از روشهای زیر فضای کریلف استفاده میکند. خواص همگرایی روشهای ارئه شده مورد بررسی قرار میگیرد. انتخابهای ممکن از تکرار مراحل داخلی با جزئیات مورد بحث قرار میگیرند و مثالهای عددی از تفاضلات گسستهسازی محدود معادلات دیفرانسیل با مشتقات جزئی مرتبهی دوم برای بررسی مؤثرتر استفاده میشود و قدرتمندی یک طرح جدیدروی روش مانده مینیمال تعمیم یافته.1
واژه های کلیدی
دستگاه معادلات خطی، تکرار داخلی/خارجی، روش گرادیان مزدوج
مقدمه
یکی از اساسیترین و مفیدترین مسألههای محاسباتی، حل دستگاه معادلات خطی است که A ماتریس داده شده، b یک بردار مفروض و x بردار مجهول است. چنین دستگاههایی کاربردهای فراوانی درگرافیک کامپیوتری، دانش ماشینی، محاسبات علمی و بسیاری از شاخههای مهندسی دارند. روش شکافی تو در تو گرادیان مزدوج2 برای حل دستگاه معادلات خطی - - 1 ارائه میگردد. روش شکافی تو در تو گرادیان مزدوج در واقع یک روش تکراری داخلی / خارجی با تکرار شکافی منحصر بفرد به عنوان تکرار خارجی آن، و با تکرار روشگرادیان مزدوج[1] 3 به عنوان تکرار درونی آن میباشد. فرض میکنیم ماتریس ضرایب A یک ماتریس نامنفرد کلی باشد که دارای شکاف A=B-C است همچنین B یک ماتریس معین متقارن است، در این صورت با استفاده از روشهای تکراری شکافی، دستگاه معادلات خطی - 1 - را حل کرده و در هر تکرار، دستگاه معادلات خطی با ماتریس ضرایب Bرا به صورت نادقیق با استفاده از روش گرادیان مزدوج حل میکنیم.
برقراری روش شکافی تو در تو گرادیان مزدوج
با در نظر گرفتن تنها رفتار عددی، روش گرادیان مزدوج در تمامی جنبهها برتر از روش مانده مینیمال تعمیم یافته میباشد. متأسفانه، روش گرادیان مزدوج تنها برای دستگاههای معین مثبت متقارن از معادلات خطی امکانپذیر است و ممکن است برای تولید یک دنباله تکراری همگرا با شکست مواجه شود، حتی زمانی که ماتریس ضرایب فقط کمی نامتقارن باشد. به هر حال، در حالتی که ماتریس ضرایب Aتقریباً معین مثبت متقارن است، در بعضی موارد، از روش گرادیان مزدوج به جای روش مانده مینیمال تعمیم یافته برای حل دستگاه معادلات خطی استفاده میکنیم. فرض کنیم A دارای شکاف A=B-C باشد همچنین B یک ماتریس غیر منحصر بفرد باشد و فرض کنیم که این شکاف شرایط زیر را ارضا کند:
الف - B یک ماتریس معین مثبت متقارن است.
ب - شعاع طیفی ماتریس - - کمتر از یک باشد یعنی پس دستگاه معادلات خطی - 1 - معادل با معادله نقطه ثابت Bx=Cx+b میباشد.
را به عنوان بردار شروع در نظر میگیریم، فرض کنیم که تقریبی از به جواب از دستگاه معادلا ت خطی - 1 - را محاسبه کردهایم سپس تقریب بعدی ممکن است به صورت دقیق و یا یک جواب نادقیق از دستگاه معادلات خطی تعریف شده باشد. حل دستگاه معادلات خطیدقیقاً توسط یک روش مستقیم مانند روش حذفی گاوس- سایدل [ 4] بدست میآید. برای این دسته از روشها، ما تئوریهای همگرایی را تنها برای یک دسته محدود از ماتریسها بیان میکنیم و رفتار عددی این ماتریسها به دلیل وابستگی قوی آنها بر انتخاب شکافهای داخلی و همچنین معیارهای توقف از تکرارهای داخلی کاملاً واضح نیست. از یک روش جدید برای بدست آوردن میتوان به حل دستگاه معادلات خطی - 2 - توسط روش تکراری گرادیان مزدوج اشاره کرد.
ممکن است خواص بهتر نظری و سرعت همگرایی سریعتر روش مانده مینیمال تعمیم یافته به دلیل ویژگی های خاص از روش گرادیان مزدوج باشد. به ویژه زمانی که ماتریس ضرایب A دارای غالب معین مثبت متقارن جزئی B است. ما به نتیجه روش جدید به عنوان یک روش شکافی تو در تو گرادیان مزدوج اشاره میکنیم. در روش شکافی تو در تو گرادیان مزدوج بردار سمت راست یعنی b ورودی است، تکرار اولیه، اعمال ماتریس A و B را روی یک بردار محاسبه میکند، تحمل توقف ، و بزرگترین تعداد مجاز از تکرار مراحل ، به ترتیب تکرارهای خارجی و داخلی میباشند. با در نظر گرفتن هزینهها، ما تنها نیاز به ذخیره چهار بردار داریم. قابل ملاحظه است که این روند تنها با استفاده از دو جفت دو جمله، و در نتیجه تنها نیاز به نگهداری تعداد کمی از بردارها در حافظه است.
هر تکرار داخلی به یک ضرب ماتریس در بردار، دو حاصل ضرب داخلی و سه عملکرد به شکل u+ نیاز دارد. که در آن u،v بردار هستند و اسکالر میباشد، هر تکرار خارجی به یک ضرب اضافی ماتریس در بردار، یک عملکرد به شکل u-v یک ضرب داخلی و یک عمل ریشه دوم برای اعداد حقیقی نیاز دارد. اگر فرض کنیم که اعداد غیر صفر ازi امین ردیف ازماتریس A ، باشد و ماتریس شکافی B حداقل الگوی ماتریس تُنُک A را حفظ میکند، سپس هر تکرار داخلی روش گرادیان مزدوج نیازمند میباشد. فرض کنید که امین تکرار خارجی به مرحله از تکرار روش گرادیان مزدوج برای رسیدن به معیار توقف، نیاز داشته باشد پس مقدار هر تکرار خارجی به صورت میباشد. به ویژه اگر و پس هر تکرار خارجی در روش شکافی تو در تو گرادیان مزدوج به صورت زیر میباشد: ملاحظه میکنیم که روش شکافی تو در تو گرادیان مزدوج میتواند به عنوان یک روش استاندارد داخلی / خارجی دیده شود.
تحلیل همگرایی
لم زیر نرخ همگرایی روش گرادیان مزدوج را شرح میدهد. لم. [3] فرض کنید B یک ماتریس معین مثبت متقارن باشد و فرض کنید دستگاه معادلات خطی Bx=b توسط روش گرادیان مزدوج حل شود. اگر بردار شروع، ، امین تکرار و جواب دقیقی از دستگاه معادلات خطی فوق باشد، پس براساس لم بالا میتوانیم قضیهی زیر را در مورد خواص همگرایی روش شکافی تو در تو گرادیان مزدوج بیان کنیم. قضیه. فرض کنید A یک ماتریس نامتقارن و نامنفرد باشد هچنین شکاف A=B-C همگرا و معین مثبت متقارن باشد. فرض کنیم که روش شکافی تو در تو گرادیان مزدوج با حدس اولیه شروع و یک دنباله تکرار شونده باشد که تقریب ام به جواب از دستگاه معادلات خطی - - 1 است که از حل دستگاه معادلات خطی - - 2 با مرحله از تکرارهای روش گرادیان مزدوج بدست آمده است
پس برای کاهش بیشتر تعداد پیششرطهای k - B - و برای بهبود عملکرد روش شکافی تو در تو گرادیان مزدوج میتوانیم پیششرط دستگاه معادلات خطی - 2 - را توسط یک ماتریس معین مثبت متقارن M پیش شرط گذاری کنیم که نزدیک به ماتریس B است و ممکن است توسط فاکتور [1] IC یا تکرار -SSORمانند[1,2] بدست آیند. در این حالت، مقدار ویژه ماتریس در نزدیکی یک خوشه خواهد بود و توسط قضیهی گفته شده در قبل روش شکافی تو در تو گرادیان مزدوج که تکرار روش گرادیان مزدوج پیششرط سازی شده را از دستگاه معادلات خطی - x= - اعمال میکند. در امین تکرار خارجی به طور قابل توجهای نرخ همگرایی سریعی خواهیم داشتکه به این روش، روش پیششرط سازی شکافی تودرتو گرادیان مزدوج4 گفته میشود.
نتایج عددی
- N است که دستگاه معادلات خطی نامتقارن تنک - 1 - با ماتریس ضرایب - - A=diag را در نظر میگیریم که یک ماتریس سه قطری بلوکی N است و - k,k-1 - ، - k,k - و - k,k+1 - به ترتیب عناصر بلوک میباشند. در اینجا - T=diagیک ماتریس سه قطری - k,k-1 - ، - k,k - و - - k,k+1 به ترتیب عناصر سمت راست ماتریس b=A است که درآن.ورودی ماتریس A به صورت زیر است:
