روش های تصویری عمومی برای مسائل بزرگ- قسمت ۱۱

روش های تصویری عمومی برای مسائل بزرگ- قسمت ۱۱

اکتبر 20, 2020 Off By مدیر سایت

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

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