روش دوقلوهای متقارن (Francis' Double Shift QR)، در ریاضیات (Mathematics)

انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :

روش دوقلوهای متقارن (Francis' Double Shift QR) :

توضیح ساده: روش دوقلوهای متقارن (یا روش QR با دو تغییر مکان) یک نسخه پیشرفته از الگوریتم QR است که توسط جان فرانسیس در دهه ۱۹۶۰ توسعه یافت. این روش برای محاسبه مقادیر ویژه ماتریس های نامتقارن (و متقارن) به کار می رود و با استفاده از دو تغییر مکان همزمان (اغلب به صورت مختلط مزدوج)، امکان کار با مقادیر ویژه مختلط را بدون استفاده از اعداد مختلط فراهم می کند. این الگوریتم پایه و اساس روش های مدرن محاسبه مقادیر ویژه است.

شرح گام به گام: ایده اصلی: به جای یک تغییر مکان، دو تغییر مکان (که ممکن است مختلط باشند) به طور همزمان اعمال می شوند. این کار باعث می شود اگر ماتریس دارای مقادیر ویژه مختلط مزدوج باشد، الگوریتم با اعداد حقیقی کار کند و همگرایی سریع تری داشته باشد. مراحل کلی:

۱. ماتریس A را به شکل بالاهسنبرگ (Hessenberg) کاهش دهید.

۲. یک جفت تغییر مکان (μ₁, μ₂) انتخاب کنید (اغلب مقادیر ویژه گوشه پایین-راست ۲×۲ ماتریس).

۳. یک مرحله QR مضاعف (Double QR step) را اعمال کنید که معادل دو مرحله QR با تغییر مکان های μ₁ و μ₂ است، اما به صورت ترکیبی.

۴. این کار باعث می شود ماتریس به شکل بالاهسنبرگ باقی بماند و به تدریج به شکل بالامثلثی (شبه قطری) همگرا شود.

۵. پس از همگرایی، بلوک های ۱×۱ و ۲×۲ روی قطر ظاهر می شوند که به ترتیب مقادیر ویژه حقیقی و مختلط را نشان می دهند.

اهمیت: قبل از روش فرانسیس، الگوریتم QR برای ماتریس های با مقادیر ویژه مختلط مشکل داشت. روش دوقلوهای متقارن این مشکل را حل کرد و امکان محاسبه کارآمد همه مقادیر ویژه ماتریس های حقیقی را فراهم آورد. این روش هنوز هم هسته اصلی الگوریتم های محاسبه مقادیر ویژه در MATLAB و LAPACK است.

مزایا: بسیار پایدار، کارآمد، قادر به محاسبه همه مقادیر ویژه (حقیقی و مختلط) ماتریس های حقیقی با محاسبات حقیقی.

معایب: پیاده سازی پیچیده، نیاز به درک عمیق جبر خطی عددی دارد.

کاربردها: استانداردترین روش در نرم افزارهای عددی برای محاسبه مقادیر ویژه ماتریس های متراکم.

نکته: جان فرانسیس این روش را در سن ۲۴ سالگی توسعه داد و سال ها بعد جایزه معتبری دریافت کرد.