جدول (۵-۲) عملکرد الگوریتم آرنولدی سراسری پایه برای ماتریس تصادفی

در شکل (۳-۱) رفتار همگرایی مسئله برای و s=2 به تصویر کشیده شده است.
شکل(۳-۱)عملکرد الگوریتم سراسری آرنولدی در فضای
بر اساس فرایند آرنولدی سراسری، جیبلو الگوریتم FOM سراسری[۱۶] و الگوریتم GMRES سراسری را برای حل سیستم خطی با طرف راست چندگانه و حل عددی مسائل معادلات ماتریس پیشنهاد داد.
اگر به عنوان مثال سیستم خطی گانه با طرف راست داشته باشیم بصورت مختصر الگوریتم FOM GL-و الگوریتم GMRES GL- را توضیح می­دهیم.
فرض کنید در الگوریتم FOM GL-، را حدس اولیه برای راه حل از معادله­ و را بصورت باقیمانده تعریف کنیم. بعد از تکرار از الگوریتم FOM GL-، در هر مرحله تصحیح شده و از زیرفضای کرایلف استخراج می­ شود به طوری که باقیمانده آن در هر مرحله برابر
است و در صدق می­ کند و جواب سیستم خطی برابر است بطوریکه که است.
در الگوریتم GMRES GL-، صحت به وسیله­ شرط مینیمال کردن باقیمانده بطوریکه که ، تعیین می­ شود.
نشان داده می­ شود جواب مسئله­ کمترین مربع است:
جزئیات این دو روش آرنولدی در [۱۶] ذکر شده است.
لازم به ذکر است که اگر باشد، فرایند آرنولدی سراسری به فرایند آرنولدی استاندارد کاهش می­یابد همچنین روش­های FOM GL-و GMRES GL- به روش­های استاندارد FOM و GMRES تبدیل می­ شود.
در ادامه فصل به بررسی الگوریتم سراسری آرنولدی و آرنولدی بلوکی برای حل مسئله­ مقدارویژه­ می­پردازیم.
۳-۴ روش آرنولدی سراسری برای حل مسئله ­ی مقدارویژه
اولین گام استنتاج روش آرنولدی سراسری برای مسئله­ مقدارویژه ساده است ولی بنیادی­ترین نکته این است که باید زیرفضای کرایلف ماتریس از را بصورت یک زیرفضای کرایلف بلوکی استاندارد از که با یک بردار شروع بلوکی آغاز می­ شود، تفسیر کرد.
هر عضو پایه که از یک زیرفضای کرایلف ماتریس به طور معمول بردار است و هر عضو از آن بردار به وسیله­ یک ماتریس جایگزین می­ شود. می­توان زیرفضای کرایلف ماتریس را به زیرفضای کرایلف استانداردی که نیاز داریم، تغییر دهیم.
فرض کنید زیرفضای بلوکی دارای رتبه ستونی کامل باشد آنگاه الگوریتم(۱) یک پایه از زیرفضای کرایلف بلوکی در را تولید می­ کند. هرچند باید به یاد داشته باشیم که این پایه به صورت معمول متعامد نیست. اگر بخواهیم به صورت ریاضی تفسیر کنیم هنگامی که به صورت زیرفضای کرایلف بلوکی باشد ممکن است از اصل تصویری متعامد استاندارد برای حل مقادیر­ویژه استفاده کنیم در این حالت
دو طرف را در ضرب می­کنیم و داریم:
ماتریس تصویری از روی زیرفضا به وسیله­ ستون­هایی از گسترش می­یابند. بطوریکه مقادیرویژه به صورت که همان مقدار ریتز از در این زیرفضا و به صورت غیرنرمال بردار ریتز آن برابر است. در واقع بردارهای­ ویژه از ماتریس تصویری که به مقدارهای­ویژه اختصاص داده شده است.
اگر بخواهیم به صورت ریاضی توضیح دهیم، هنگامی که فرایند آرنولدی بلوکی استاندارد یک پایه متعامد از را تولید کند مقدار ریتز و بردار ریتز یکسانی را استخراج می­ کند هرچند به صورت عددی به نتیجه­ دلخواه نمی­رسیم، زیرا اولا ممکن است ستون متغیر باشد و ثابت نماند و نزدیک به وابسته خطی باشد. به همین دلیل تقریبا نامنفرد است؛ دوما روش آرنولدی بلوکی استاندارد برای های یکسان بسیار پرهزینه است در واقع قسمتی از هزینه مرحله آرنولدی سراسری این است که نیاز به عملیات ممیز شناور برای تشکیل و معکوس آن دارد در حالی که هزینه­ های فرآیندهای آرنولدی بلوکی ماتریس به وسیله­ ضرب­های برداری بیش از عملیات ممیز شناور است؛ (با فرض اینکه هیچ متعامد سازی استفاده نشده است).
می­توان گفت هزینه­ فرایند آرنولدی بلوکی استاندارد برای های یکسان بیشتر از فرایند آرنولدی بلوکی است بنابراین نمی­تواند فرایند کاربردی باشد. لذا فرایند دیگری را پیشنهاد می­کنیم.
تعریف ۳-۱۰ : تعریف می­کنیم . آنگاه هر مقدارویژه از یک مقدارویژه گانه است. فرض می­کنیم یک ماتریس قطری­پذیر باشد تعریف می­کنیم و ماتریس بردارویژه
آنگاه داریم:
در واقع تجزیه­ی مقدارویژه انجام می­ شود. بردار ویژه متناظر از که به اختصاص داده­اند را می­گیریم که فرم آن به شکل زیر است:
که احتمال وجود عناصر ناصفر آن در موقعیت­های، است.
فرایند آرنولدی سراسری روی ماتریس با ماتریس شروع کاملا وابسته به فرایند آرنولدی استاندارد روی ماتریس با بردار اولیه شروع است. ادامه­ نتایج به آسانی در [۲۴] قابل توجیه است که در واقع اولین گام برای پیشنهاد و درک روش آرنولدی سراسری برای مسائل­ویژه است.
قضیه۳-۲: اگر و طبق تعاریف بالا باشند آنگاه قالب یک پایه­ متعامد از زیرفضای کرایلف معمول است که توسط ماتریس و بردار شروع تولید می­ شود؛ تعریف می­کنیم:
آنگاه در ادامه طبق فرایند آرنولدی استاندارد داریم:
هنگامی که متعامد باشند قضیه۳-۲ نشان می­دهد که یک ماتریس تصویری متعامد از روی زیرفضای است.
و بطوریکه ،جفت­ویژه از با . مقدارویژه­های ، مقادیر ریتز از نسبت به زیرفضای و بردارهای ریتز متناظر با آن
می­باشند. پس به راحتی می­توان از جفت­های ریتز برای تقریب جفت­های ویژه استفاده کرد. نرم باقیمانده نیز به صورت زیر محاسبه می­ شود:
تا وقتی که همگرایی رخ ندهد الگوریتم را تکرار می­کنیم.
هرچند این وضعیت دقیق است ولی نمی­ توان آن را به سادگی برای هایی که از نظر اندازه بسیار بزرگتر از اند و همچنین کلیه­ مقادیرویژه آنها حداقل گانه باشند، انجام داد.
باید توجه داشته باشیم از یک طرف هر مقدارویژه از یک مقدارویژه گانه از است از طرف دیگر مقادیرویژه از همواره ساده هستند اگر آن قطری­پذیر باشد. فرض کنید قطری­پذیر باشد روش آرنولدی استاندارد در صورتی که فقط دارای مقادیرویژه ساده باشد، کارا است[۱۹,۲۰,۲۱,۲۶,۲۷]. بنابراین هنگامی­که جفت­های ریتز که در بالا ذکر شد همگرا باشد، می­توان یک تقریب ساده از جفت­های ویژه گانه از داشته باشیم.
حال می­توان روش آرنولدی سراسری را پیشنهاد کرد تا به طور مستقیم روی کار کند، نسبت به اینکه روی ماتریس خیلی بزرگتر ) اجرا شود. زیرفضای کرایلف بلوکی را می­توان به سادگی به جمع مستقیم بردار یکه زیرفضای کرایلف تجزیه کرد که توسط بردارهای شروع تولید می­ شود.
یادآوری می­ شود که فرض کردیم ستون­های به صورت مستقل خطی هستند. به طور مثال در زبان MATLAB ستون­هایی از را به صورت نمایش می­دهیم که فرمی از یک پایه است. تا وقتی کهبطوریکه مستقل خطی فرض شده باشد می­توان زیرفضای کرایلف بعدی داشت. اکنون از که برای تقریبی از برخی مقادیرویژه از استفاده می­کنیم که مقدار F-ریتز نامیده می­شوند و مربوط به زیرفضای کرایلف ماتریس هستند؛ با این حال می­توان بردارهای جدید تایی را به صورت زیر محاسبه کرد:
که بردارهای F-ریتز، خوانده می­شوند و مربوط به زیرفضای کرایلف است. برای هر ، بردارهای F-ریتز متناظر به صورت داریم.
حال اگر فرض کنیم به همگرایی رسیدیم پس سه حالت ممکن است رخ دهد:
اگر ساده باشد بردار F-ریتز باید تقریبا موازی باشد تا بتوانند یکسانی تقریب بزنند.
اگر چندگانه باشد هرکدام از بردار F-ریتز ، تقریب خوبی برای بردارویژه هستند.
اگر به چندگانگی توجه نکنیم و مکان­ویژه اختصاص داده شده در تعیین نشود به راحتی می­توان از برخی بردارهای F-ریتز برای تقریب بردارویژه به جای محاسبه­ی کلیه­ آنها استفاده کرد.
تعریف می­کنیم:
پس و به راحتی می­توان بازبینی کرد که راه­حل معادله­ زیر است:
جفت­های را جفت­های F-ریتز از می­خوانند که مربوط به زیرفضای کرایلف ماتریس است.
می­توان تحقیق کردکه چگونه یک مقدار F-ریتز و بردار F-ریتز، یک مقدارویژه و مکان بردارویژه از را به وسیله­ رجوع به جفت ریتز استاندارد از روی زیرفضای تقریب می­زند.
قضیه۳-۳: عبارات زیر برقرار هستند