پیش‌شرطی‌سازی

پیش‌شرطی‌سازی یک سیستم خطی را به یک سیستم معادل با طیف مطلوب‌تر تبدیل می‌کند، به طوری که یک حل‌کننده تکراری در گام‌های بسیار کمتری همگرا می‌شود؛ این اغلب مهم‌ترین عامل در عملکرد حل‌کننده‌های بزرگ و تنک (sparse) است.

Definition

پیش‌شرطی‌کننده ماتریسی است که به صورت ضمنی یا صریح بر یک سیستم خطی اعمال می‌شود و ماتریس ضرایب یا معکوس آن را تقریب می‌زند تا سیستم پیش‌شرطی‌شده دارای ویژگی‌های طیفی باشد که منجر به همگرایی بسیار سریع‌تر یک روش تکراری می‌شود.

Scope

این موضوع ایده یک معکوس تقریبی را پوشش می‌دهد که مقادیر ویژه را خوشه‌بندی می‌کند یا عدد شرطی را کاهش می‌دهد، خانواده‌های اصلی پیش‌شرطی‌کننده‌ها — قطری و بلوک قطری، تجزیه LU و چولسکی ناقص، معکوس‌های تقریبی تنک، و پیش‌شرطی‌کننده‌های تجزیه دامنه و چندشبکه‌ای — و موازنه بین اثربخشی یک پیش‌شرطی‌کننده و هزینه ساخت و اعمال آن را بررسی می‌کند.

Core questions

• چگونه یک پیش‌شرطی‌کننده طیف یک سیستم را تغییر می‌دهد تا همگرایی تکراری را تسریع کند؟
• چه چیزی یک پیش‌شرطی‌کننده خوب را می‌سازد، با موازنه کیفیت تقریب در برابر هزینه ساخت و اعمال؟
• تجزیه‌های ناقص و معکوس‌های تقریبی تنک چگونه ساخته می‌شوند؟
• چه زمانی از روش‌های چندشبکه‌ای یا تجزیه دامنه به عنوان پیش‌شرطی‌کننده به جای حل‌کننده‌های مستقل استفاده می‌شود؟

Key theories

تبدیل طیفی

اعمال یک پیش‌شرطی‌کننده که معکوس ماتریس را تقریب می‌زند، یک عملگر پیش‌شرطی‌شده را به دست می‌دهد که مقادیر ویژه آن خوشه‌بندی شده‌اند یا عدد شرطی آن کاهش یافته است؛ از آنجا که همگرایی کریلوف به طیف بستگی دارد، این می‌تواند تعداد تکرارها را به میزان قابل توجهی کاهش دهد.

پیش‌شرطی‌کننده‌های تجزیه ناقص

تجزیه‌های LU ناقص و چولسکی ناقص، عوامل مثلثی تقریبی را محاسبه می‌کنند در حالی که پرشدگی (fill-in) فراتر از یک الگوی تنکی یا آستانه انتخابی را کنار می‌گذارند و یک پیش‌شرطی‌کننده ارزان تولید می‌کنند که بخش زیادی از عملکرد ماتریس را به خود اختصاص می‌دهد.

Mechanisms

یک پیش‌شرطی‌کننده M به گونه‌ای انتخاب می‌شود که حل سیستم‌ها با M ارزان باشد و عملگر پیش‌شرطی‌شده به ماتریس همانی نزدیک باشد و مقادیر ویژه آن را خوشه‌بندی کند. پیش‌شرطی‌سازی قطری (ژاکوبی) صرفاً مقیاس‌بندی مجدد می‌کند؛ تجزیه‌های LU یا چولسکی ناقص با حذف ورودی‌های کوچک یا خارج از الگو در طول حذف، عوامل مثلثی تنک تقریبی می‌سازند؛ معکوس‌های تقریبی تنک مستقیماً یک M تنک را می‌سازند که معکوس را تقریب می‌زند به طوری که فقط ضرب ماتریس-بردار مورد نیاز است. پیش‌شرطی‌کننده‌های قدرتمندتر در هر تکرار یک چرخه چندشبکه‌ای یا یک حل تجزیه دامنه را اعمال می‌کنند. در هر مورد، پیش‌شرطی‌کننده در هر مرحله از یک روش کریلوف اعمال می‌شود و طراحی آن بین میزان تقریب معکوس و هزینه تشکیل و اعمال آن تعادل برقرار می‌کند.

Clinical relevance

پیش‌شرطی‌سازی برای حل سیستم‌های بزرگ و بدشرط ناشی از گسسته‌سازی PDE و بهینه‌سازی در مقیاس بزرگ تعیین‌کننده است؛ پیش‌شرطی‌کننده مناسب می‌تواند یک تکرار را که راکد می‌ماند به تکراری تبدیل کند که در چند گام همگرا می‌شود، و انتخاب و تنظیم پیش‌شرطی‌کننده‌ها یک نگرانی عملی مرکزی در نرم‌افزارهای علوم و مهندسی محاسباتی است.

History

پیش‌شرطی‌سازی همراه با روش‌های کریلوف از دهه 1970 به بعد رشد کرد، با تجزیه‌های ناقص که توسط Meijerink و van der Vorst در سال 1977 معرفی شد و مجموعه‌ای گسترده از پیش‌شرطی‌کننده‌های جبری و چندسطحی که از آن زمان توسعه یافته‌اند؛ اکنون اغلب مهم‌تر از انتخاب خود روش کریلوف برای عملکرد حل‌کننده شناخته می‌شود.

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

چه چیزی یک پیش‌شرطی‌کننده را خوب می‌کند؟

یک پیش‌شرطی‌کننده خوب، معکوس ماتریس را به دقت تقریب می‌زند تا سیستم پیش‌شرطی‌شده برای روش تکراری آسان باشد، در عین حال ساخت و اعمال آن ارزان است. هنر در موازنه این اهداف متضاد است: یک پیش‌شرطی‌کننده دقیق‌تر در هر مرحله هزینه بیشتری دارد اما به گام‌های کمتری نیاز دارد.

آیا می‌توان از یک حل‌کننده به عنوان پیش‌شرطی‌کننده استفاده کرد؟

بله. یک چرخه واحد از چندشبکه یا یک حل تجزیه دامنه اغلب به عنوان یک پیش‌شرطی‌کننده در داخل یک روش کریلوف استفاده می‌شود، که استحکام تکرار کریلوف را با کاهش سریع خطا در حل‌کننده داخلی ترکیب می‌کند.