همانطور که بیان شد دارای مقدار غیر صفر زیر قطر اصلی است. ساختار سطر آخر بصورت زیر است:
تعداد صفرها و تعداد عناصر غیرصفر برابر است و است. حال اگر ستون از ستون در عبارت را در نظر نگیریم داریم:
در ادامه کلیه نتایجی که تا اینجا کسب نمودیم در الگوریتم ۲-۷-۲ بکار میبریم.
میتوان گفت یک مرحله با انتقال ها بردار را به یک چندگانگی از تبدیل می کند. در واقع این اصلاح ساده از تکرار آرنولدی عبارت زیر را میدهد:
۲-۷-۲ الگوریتم شروع مجدد ضمنی آرنولدی(IRA)
ورودی الگوریتم : ماتریس و ماتریس شروع
خروجی الگوریتم: ماتریس هسنبرگی و ماتریس ، و ماتریس نتیجه
اولین ستونها در عبارت بدست آمده زیر را میسنجیم
و نتیجه میگیریم. اگر کلیه مرحله را در نظر بگیریم داریم:
اگر یک مقدارویژه از باشد آنگاه اجزائی از در این مسیر را با بردار ویژه متناظر با آن حذف می کند در واقع اگر نزدیک به یک مقدارویژه از باشد آنگاه تنها دارای جزءهای کوچک بردارهای ویژه متناظر با نزدیکترین مقادیرویژه در این مسیر است. انتخاب دشوار است زیرا همچنان ممکن است در اجرای الگوریتم ۲-۷-۱مقادیر ریتز ناخواسته یکسان بازیابی شوند.
بررسی معیار همگرایی
تعریف میکنیم بطوریکه و آنگاه داریم:
در این فصل روشهای زیرفضای کرایلف که شامل روش آرنولدی، روش هرمیتی لنگزوس و روش ناهرمیتی لنگزوس بود، توضیح داده شد و قضایای کاربردی مربوط به این الگوریتمها نیز بیان شد. مثالهایی برای درک سادهتر این الگوریتمها نیز بیان گردید. در آخر فصل الگوریتم آرنولدی با شروع مجدد معرفی شد. در ادامه روش آرنولدی سراسری برای حل مقدارویژه ماتریسهای بزرگ بیان می شود.
فصل ۳
روش آرنولدی سراسری
برای مسئله
مقدارویژه ماتریس غیرهرمیتی بزرگ
با کاربردهای ویژه
و
مقدارویژه چندگانه
فصل ۳ روش آرنولدی سراسری برای مسئله مقدارویژه ماتریس غیرهرمیتی بزرگ
روشهای تصویری سراسری برای حل عددی مسائل معادلات ماتریسهای بزرگ استفاده می شود، اما هنوز راهی برای حل مسائل مقدارویژه بزرگ شناخته نشده است. در این پایان نامه روش آرنولدی سراسری برای حل مسائل مقدارویژه بزرگ بیان می شود. این روش جفتهای F-ریتز[۳] که برای تقریب جفت ویژه وجود دارند را محاسبه می کند.
روش آرنولدی سراسری خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد و مقادیرویژه مجزای ماتریس بزرگ همان مقادیرویژه ماتریس اصلی هستند.
به عنوان یک کاربرد، فرض کنید یک ماتریس قطری پذیر باشد؛ نشان داده می شود روش آرنولدی سراسری می تواند مسئله مقدارویژه چندگانه را حل کند.
۳- ۱ مقدمه
جیبلو[۴]، مسادی[۵] و سادوک[۶] روش تصویری سراسری [۱۶] را برای حل معادلات ماتریسی پیشنهاد کردند. یک جزء اصلی از روشهای سراسری استفاده از ضرب اسکالر فروبنیوس است. در واقع روش “سراسری” یک الگوریتم با ضرب F-داخلی را شرح میدهد. نشان داده می شود فرایند آرنولدی سراسری یک پایه متعامد از زیرفضای کرایلف یک ماتریس را تولید می کند و اساس آن از روشهای سراسری FOM و سراسری GMRES مشتق میشوند[۱۳,۱۴,۳۰]. برخی دیگر از پژوهشگران روشهای عمومی دیگری مانند نگارشهای CG ، SCG ، CR و CMRH پیشنهاد کردند.
در طی چندین سال گذشته، روش عمومی عددی، به صورت گسترده، برای حل سیستم خطی با طرف راست چندگانه و معادله ماتریس استفاده میشد. به عنوان مثال معادله ریکاتی[۷] و معادله سیلوستر[۸] [۴,۱۷,۱۸,۲۴,۳۱]را میتوان نام برد.
این روشها از دسته روشهای تصویری عمومی روی زیرفضای کرایلف ماتریس هستند.
تحلیل همگرایی روی الگوریتم GMRES سراسری در [۵] مورد بررسی قرار گرفت.
الگوریتمهای زیرفضای کرایلف به طور مفصل در فصل دوم شرح داده شده اند. هنگامیکه الگوریتمهای زیرفضای کرایلف برای حل مسائل ذکرشده بالا کاربرد داشته باشند بسیار کارآمد میشوند، کاربردهای دیگر از زیرفضای کرایلف سراسری در مدل کاهشی به خصوص سیستمهای MIMO که در [۷,۸,۹,۱۵] بیان شد؛ هرچند هیچ روش تصویری سراسری برای حل مسئله مقدارویژه ماتریس بزرگ پیشنهاد نشده است اما آیا روش تصویری سراسری می تواند یک روش پیشنهادی برای حل مسئله مقدارویژه باشد؟
برای مسئله مقدارویژه ماتریس غیرهرمیتی بزرگ، یک کلاس بزرگ از روشها، روشهای تصویری متعامد است که شامل روش آرنولدی مشهور میباشد[۱,۲۶,۲۹,۳۴].
یادآوری مینماییم که روش آرنولدی از فرایند آرنولدی برای ساختن یک پایه متعامد از زیرفضای کرایلف که با یک بردار شروع می شود، استفاده می کند و جفتهای F-ریتز[۹] را محاسبه می کند که تقریبی برای برخی مقادیرویژه از ماتریس بزرگ میباشد.
فرض میکنیم یک ماتریس قطری پذیر باشد، هرچند مشخص شده است که روش آرنولدی خود به تنهایی نمیتواند چندگانگی مقدارویژه از مقادیرویژه خواسته شده و همچنین مکان مقادیرویژه را تشخیص دهد[۱۹,۲۰,۲۱] . برای غلبه بر این مشکل روش آرنولدی بلوکی پیشنهاد می شود[۲,۲۰,۲۳]که ابتدا از فرایند آرنولدی بلوکی برای ساخت پایه متعامد از زیرفضای کرایلف استفاده می شود که به وسیله یک مجموعه بردار، جفتهای ریتز از زیرفضای کرایلف بلوکی استخراج می شود که تقریبی از مقادیرویژه خواسته شده میباشد.
در این فصل مبنای کار، یک فرایند آرنولدی سراسری است که با یک ماتریس اولیه شروع می شود و نشان داده می شود چگونه روش آرنولدی سراسری برای مسئله مقدارویژه نامتقارن بزرگ نتیجه میدهد؛ لذا یک چهارچوب عمومی از روش تصویری سراسری برای مسئله مقدارویژه پیشنهاد می شود که روش تصویری F-متعامد نامگذاری می شود. این روش جفتهای F-ریتز را برای تقریب زدن برخی جفت مقادیر ویژه محاسبه می کند .
تفاوت بنیادی با روش تصویری معمول در این است که هماکنون بردار F-ریتز داریم که به هر مقدار
F-ریتز اختصاص داده شده است که هرکدام از اینها به عنوان تقریبی از بردارویژه استفاده می شود. در واقع میتوان یک بردار F-ریتز را برای استفاده از هر مقدار F-ریتز انتخاب نمود. با هر مقدارویژه از در یک زیرفضای کرایلف کاملا وابسته به یک مجموعه تایی و جفتهای F-ریتز حداقل دقیقا برابر جفتهای ریتز های معمولی هستند به همین دلیل است که روش آرنولدی سراسری خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد.
با فرض اینکه یک ماتریس قطری پذیر باشد نشان میدهیم که روش آرنولدی سراسری می تواند چند گانگی مقدارویژه خواسته شده را با مکان تطابقی آن تشخیص دهد. برای گویا بودن مسئله روی روش سراسری بیشتر تاکید میکنیم.
۳-۲ تعاریف پایه مربوط به فرایند آرنولدی سراسری
فرایند آرنولدی سراسری، پایه -Fمتعامد از زیرفضای کرایلف ماتریس را به وسیله ماتریس اولیه و نرم یک فریبنیوس تولید می کند. در واقع
=
یک ماتریس است.
تعریف ۳-۱ : اگر پایه را بردار مستقل خطی تفسیر کنیم، این زیرفضای کرایلف ماتریس می تواند به صورت یک زیرفضای کرایلف بلوکی معمولی با قطرهای باشد که با یک بردار بلوکی اولیه آغاز می شود. به همین دلیل میتوانیم آن را به جمع مستقیم بردار یکه با قطر از زیرفضای کرایلف تجزیه کنیم.
به وسیله اصل تصویری -Fمتعامد ، میتوانیم مقدارویژه تقریب بزنیم:
که مقدار F-ریتز مربوط به زیرفضای کرایلف ماتریس خوانده میشوند. برای هر مقدار F-ریتز ، میتوانیم یک بردارویژه تقریبی، از هر بردار یکه زیرفضای کرایلف بدست آوریم.
فرض کنید مقدار F-ریتز و بردارهای F-ریتز ، متناظر با آن همگرا هستند، پس میتوان گفت تقریب خوبی از مقادیرویژه هستند.
اگر مقدارویژه خواسته شده ساده باشد، بردار F-ریتز به صورت وابسته خطی عددی میباشد. اگر چندگانگی مقادیرویژه خواسته شده اهمیت نداشته باشد میتوان به طور ساده از هریک از بردار F-ریتز برای تقریب بردار ویژه به جای اینکه همه آنها را محاسبه نمود، استفاده کرد.
اگر تعداد را بنامیم :
