ابعاد ماتریس، ماتریس خیلی بزرگ را به ماتریسی متشابه تبدیل می کند که زوجهای ویژه آن نزدیک به ماتریس اولیه است. لذا در این پایان نامه با معرفی روشهایی که از مفهوم و خواص زیرفضاها استفاده می کنند و همچنین با استفاده ازخاصیت شروع مجدد ضمنی، الگوریتم آرنولدی با شروع مجدد را تعریف میکنیم. برای بدست آوردن زوجهای ویژه ماتریسهای بزرگ، روش آرنولدی سراسری [۲]پیشنهاد می شود که برای ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است. لذا با معرفی طرح شروع مجدد سعی بر حل این مشکل داریم. در فصل اول تعاریفی از ماتریسها و زیرفضاها آورده می شود سپس در فصل دوم، مروری بر روشهای زیرفضای کرایلف نموده و همچنین طرح شروع مجدد ضمنی معرفی می شود. در فصل سوم، توضیح مختصری از فرآیندهای آرنولدی سراسری ، الگوریتمهای FOM سراسری و GMRES سراسری داریم. در قسمت بعد از این فصل روش آرنولدی سراسری برای مسائل ویژه نامتقارن بزرگ پیشنهاد می شود سپس راه حل بدست آوردن زوجهای ویژه برای ماتریس با ابعاد بزرگ توضیح داده می شود و همچنین چگونگی استفاده از روش آرنولدی سراسری برای حل مسائل ویژه چندگانه بیان می شود. استفاده از طرح شروع مجدد، برای هنگامیکه این روش زوجهای ویژه تقریبی را برای ابعاد بالا بدست نیاورد، ضروری است. لذا در این پایان نامه الگوریتم آرنولدی سراسری با شروع مجدد تعریف می شود. در بخش بعد روش شروع مجدد ضمنی، به الگوریتم سراسری با شروع مجدد ضمنی با مقادیر F-ریتز ناخواسته پیشرفت داده می شود. در پایان الگوریتم آرنولدی سراسری با شروع مجدد ضمنی، با انتقالهای پیشنهادشده دقیق همراه می شود. در فصل آخر مثالهای عددی و میزان کارایی الگوریتمها گزارش داده میشوند.
فصل اول
تعاریف
و
مفاهیم پایه
فصل ۱ تعاریف و مفاهیم پایه
در این فصل، به بیان و یادآوری بعضی تعاریف و مفاهیمی که در فصول بعد مورد استفاده قرار میگیرند، پرداخته میشوند.
۱-۱ تعریف تعامد مجموعه
یک مجموعه از بردارهای در ، متعامد یکه است اگر برای هر داشته باشیم : و به ازای هر i ، باشد .
۱-۲ انواع ماتریس ها
ماتریس هرمیتی
ماتریس مربعی هرمیتی است هرگاه ( را ترانهادهی مزدوج ماتریس مینامیم) .
ماتریس جایگشتی
ماتریس مربعی غیرصفر را ماتریس جایگشتی گوییم هرگاه تنها عنصر غیرصفر در هر سطر و ستون آن یک باشد و بقیه عناصر، همگی صفر باشند. بنابراین، اگر یک جایگشت از باشد آنگاه
ماتریس هسنبرگی
ماتریس مربعی را بالاهسنبرگی گوییم اگر برای هر داشته باشیم.
درمقابل، پایین هسنبرگی است اگر برای هر داشته باشیم.
ماتریس مثبت معین
ماتریس متقارن مثبت معین است هرگاه برای هر بردار غیرصفر داشته باشیم .
ماتریس نرمال
ماتریس مربعی نرمال است اگر باشد.
ماتریس متعامد
ماتریس را یک ماتریس متعامد گویند، هرگاه
خواص ماتریس متعامد:
معکوس یک ماتریس متعامد برابر ترانهاده آن میباشد، یعنی:
حاصل ضرب دو ماتریس متعامد نیز یک ماتریس متعامد میباشد.
ماتریس بلوکی
تعریف : فرض کنید یک ماتریس دلخواه باشد، در اینصورت یک ماتریس بلوکی نامیده می شود هرگاه، هریک از درایه هایش یک ماتریس باشد. با فرض اینکه نیز یک ماتریس بلوکی باشد و
، جمع و ضرب آنها به شکل
تعریف می شود. یک ماتریس قطری بلوکی یک ماتریس بلوکی است که هریک از بلوکهای قطری آن یک ماتریس مربعی بوده و دیگر عناصرش صفر باشند.
۱-۳ چند جملهای مشخصه، بردارویژه ، مقدارویژه
اگر یک ماتریس باشد آنگاه چندجملهای چندجملهای مشخصه نامیده می شود. صفرهای چندجملهای مشخصه، مقادیر ویژهی ماتریس نامیده می شود. مقدار ویژه است اگر و فقط اگر یک بردار ناصفر وجود داشته باشد به طوری که . بردار را بردار ویژه(بردار ویژه راست) می گوییم. مجموعه تمام مقادیر ویژهی ماتریس را طیف ماتریس نامیده و با نشان می دهند و نیز شعاع طیفی ماتریس را با نشان داده که عبارت است از :
در ادامه به تعریف چندجملهای مونیک و چندجملهای مینیمال میپردازیم.
چند جملهای مونیک
چندجملهای که ضریب بزرگترین درجه آن برابر یک است چندجملهای مونیک نامیده می شود. مثلاً
چندجملهای مینیمال
چندجملهای مونیک با کمترین درجه که ماتریس آن را برابر ماتریس صفر کند چندجملهای مینیمال ماتریس نامیده می شود.
محاسبهی چندجملهای مینیمال
فصل را با معرفی نرم ماتریس ادامه میدهیم.
۱-۴ نرمهای یک ماتریس
اگر ماتریس باشد آنگاه نرم ماتریس با همراه با خواص زیر تعریف می شود.
و است اگر و فقط اگر .
برای هر اسکالر c : .
به ازای هر دو ماتریس و داریم: .
حال به تعریف چند نرم شناخته شده میپردازیم.
نرم خطی (نرم یک)
,
نرم بینهایت (ماکسیمم)
نرم بینهایت ماتریس با نمایش داده و بصورت زیر تعریف می شود:
نرم فروبنیوس
نرم فروبنیوس ماتریس را با نمایش داده و بصورت زیر تعریف می شود:
در ادامه به تعریف دو نوع تجزیه یک ماتریس میپردازیم.
۱-۵ تجزیه و
الف- فرض کنید یک ماتریس باشد، آنگاه یک ماتریس متعامد و یک ماتریس بالا مثلثی وجود دارد به طوری که ، که در آن ماتریس به فرم میباشد و ها هریک ماتریس هاوسهولدر میباشند.
ب- فرض کنید یک ماتریس باشد، تجزیه ماتریس عبارت است از تبدیل ماتریس ضرایب به حاصل ضرب دو ماتریس و ، که در آن یک ماتریس پایین مثلثی و یک ماتریس بالامثلثی واحد است (یک ماتریس بالامثلثی که همه عناصر روی قطر اصلی آن یک هستند).
۱-۶ فضاهای ضرب داخلی
الف: یک ضرب داخلی روی زیر فضای برداری عبارت است از یک تابع حقیقی که به هر زوج از بردارهای و عدد حقیقی را اختصاص میدهد بطوریکه برای بردارهای و اسکالر چهار اصل زیر برقرار باشد:
به ازای هر ؛
اگر و فقط اگر
به ازای هر داشته باشیم:
به ازای هر و داشته باشیم: .
یک فضای برداری همراه با یک ضرب داخلی را یک فضای ضرب داخلی مینامند.
ب: دو بردار از یک فضای ضرب داخلی متعامد نامیده می شود، هرگاه
ج: یک مجموعه از بردارها مانند را متعامد گویند، هرگاه
د: مجموعه U را متعامد یکه گویند، هرگاه متعامد باشد و نرم هر بردار متعلق به برابر یک باشد، یعنی
و: مجموعه همه ترکیبات خطی یک مجموعه از بردارهای یک زیر فضای برداری است که مجموعه همه ترکیبات خطی متناهی نامیده می شود و به صورت زیر نمایش داده می شود:
ه: فرض کنید ، در اینصورت فضای برد و پوچ ماتریس به ترتیب به صورت زیر تعریف می شود:
بنا به تعریف هرگاه ماتریس نامنفرد باشد، آنگاه . اما اگر منفرد باشد، در اینصورت، لذا صفر یک مقدار ویژه ماتریس میباشد، حال اگر بردارهای ویژه نظیر صفر را به دست آوریم اعضای خواهند بود.
۱-۶-۱ زیر فضای کرایلف
یک زیرفضای کرایلف از بعد کمتر یا مساوی متناظر با ماتریس و بردار بصورت زیر تعریف می شود:
هر بردار بصورت نوشته می شود، که در آن یک چندجمله ای از درجه کمتر یا مساوی است.
در ادامه الگوریتم متعامدسازی گراماشمیت را بطور مختصر شرح میدهیم.
۷-۱ الگوریتم متعامدسازی گرام اشمیت
مجموعه از بردارهای مستقل خطی را در نظر بگیرید. با بهره گرفتن از الگوریتم متعامدسازی گرام اشمیت میتوان این مجموعه را به مجموعه ای متعامد یکه تبدیل کرد.
۱-۷-۱ الگوریتم گرام اشمیت
ورودی الگوریتم: مجموعهای از بردارهای مستقل
خروجی الگوریتم: مجموعه ای بردارهای متعامد یکه
قرار دهید: ؛ اگر پایان روند، در غیر اینصورت .
به ازاء و مقادیر زیر را بدست آورید.
هرگاه ، پایان روند، در غیر این صورت .
الگوریتم فوق روند گرام اشمیت استاندارد نامیده می شود. الگوریتم مشابهی وجود دارد که از لحاظ ریاضی معادل با روند گرام اشمیت استاندارد است، ولی خصوصیات عددی بهتری دارد که آن را روند گرام اشمیت اصلاح شده مینامندکه در ادامه بطور مختصر توضیح داده می شود.
۱-۷-۲ الگوریتم گرام اشمیت اصلاح شده
قرار دهید: ؛ اگر پایان روند، در غیر اینصورت .
به ازاء مقادیر زیر را بدست آورید.
به ازای مقادیر زیر را بدست آورید:
,
هرگاه ؛ پایان روند، در غیر اینصورت .
در این فصل تعاریف لازم که در پایان نامه استفاده می شود بیان شد. در مورد تجزیهی و توضیح مختصری داده شد، هم چنین فضاهای ضرب داخلی به ویژه زیرفضای کرایلف معرفی شد و در آخر فصل الگوریتم متعامدسازی گرام اشمیت که برای تبدیل مجموعههای بردارهای مستقل به مجموعه بردارهای یکه استفاده می شود بیان شد. درادامه به معرفی روشهای زیرفضای کرایلف برای حل مسائل مقدارویژه میپردازیم.
فصل ۲
روشهای زیر فضای کرایلف
برای حل
مسائل مقدار ویژه
فصل ۲ روشهای زیر فضای کرایلف برای حل مسائل مقدار ویژه
۲-۱ مقدمه
از جمله روشهای مهم برای محاسبه مقادیر ویژه و بردارهای ویژه ماتریسهای بزرگ، روشهای تصویری متعامد و متمایل است. در این فصل دستهای از مهمترین روشهای تعیین مقادیر ویژه ماتریسهای بزرگ بر اساس این روشها بررسی می شود.
۲ـ۲ زیرفضای کرایلف
قضیه ۲ـ۱: زیرفضای کرایلف از بعد است اگر و فقط اگر درجه چندجملهای مینیمال در رابطه با ماتریس بزرگتر از باشد .
اثبات: بردارهای تشکیل یک پایه برای زیرفضای کرایلف می دهند اگر و فقط اگر برای هر سطر , ترکیب خطی ناصفر باشد و این شرط معادل با این است که چندجملهای از درجه کمتر یا مساوی ، برای وجود ندارد، و این اثبات را کامل می کند.
تعدادی از روشهای زیرفضای کرایلف عبارتند از:
۱ـ روش آرنولدی
۲ـ روش هرمیتی لنگزوس
۳ـ روش ناهرمیتی لنگزوس
هر یک از روشهای فوق را به صورت بلوکی نیز میتوان بهکار برد که در این صورت این روشها را روشهای بلوکی زیرفضای کرایلف مینامند. روشهای آرنولدی و لنگزوس روشهای تصویری متعامد هستند، در حالی که روش ناهرمیتی لنگزوس روش تصویری متمایل است.
۲ـ۳ فرایند آرنولدی
فرایند آرنولدی، روش تصویری متعامد روی زیرفضای کرایلف است. این روش برای به دست آوردن مقادیر ویژه تقریبی ماتریسهای تنک و حل دستگاههای خطی بزرگ به وجود آمده است که بر مبنای ساختن یک زیرفضا که زیرفضای کرایلف نامیده می شود، استوار است.
انتخاب بردار اولیه در این روش بسیار مهم است. لذا روشهای مختلفی برای انتخاب این بردارها وجود دارد.
۲-۳-۱ الگوریتم آرنولدی
۱ـ بردار اولیه با نرم یک و بعد از زیرفضای کرایلف را انتخاب کنید.
۲ـ به ازاء مقادیر ویژه زیر را محاسبه کنید:
معیار توقف الگوریتم زمانی است که بردار صفر شود، در این الگوریتم درایههای ماتریس هسنبرگ و بردارهای ماتریس متعامد را به وجود میآورند. در ادامه جزئیات مهمی از الگوریتم ارائه شده است.
مزایای روش آرنولدی
۱ـ در بسیاری از مسائل کاربردی هنگام برخورد با مسئله تعیین مقادیر ویژه یک ماتریس بزرگ، نیاز به تعیین تمام مقادیر ویژه آن نیست، بلکه معمولاً در این گونه مسائل محاسبه مقدار ویژه از تمام مقدار ویژه ماتریس بزرگ کفایت می کند.
۲ـ روش آرنولدی این امکان را فراهم میسازد تا دقیقا به تعداد مورد نیاز مقادیر ویژه را محاسبه نمائیم.
در ادامه چند خاصیت مهم الگوریتم آرنولدی بررسی می شود.
قضیه۲ـ۲: بردارهای پایهای متعامد برای زیرفضایکرایلف زیر تشکیل می دهند.
اثبات: بردارهای با توجه به ساختارشان متعامد هستند؛ از طرف دیگر با استقراء روی نشان میدهیم که هر بردار به صورت میباشد که در آن یک چندجملهای از درجه است. اگر باشد، با قراردادن داریم: ، فرض کنید مطلب فوق برای تمام اعداد صحیح کمتر یا مساوی برقرار باشد، در این صورت داریم:
که نشان میدهد بردار به صورت بسط داده می شود.
قضیه ۲ـ۳ : فرض کنید ماتریس متعامد با ستونهای و یک ماتریس هسنبرگ باشد. که درایههای غیرصفر آن توسط الگوریتم آرنولدی تولید شده است، در این صورت روابط زیر برقرار است:
اثبات: با توجه به روابط و در الگوریتم آرنولدی تساوی زیر به دست می آید.
و این تساوی، رابطه (۲-۳) را اثبات می کند. رابطه (۲-۴) از ضرب ماتریس در دو طرف رابطه (۲-۳) و با توجه به متعامد بودن بردارهای به دست می آید.
این وضعیت در شکل (۴ـ۱) نشان داده شده است. با توجه به شکل، اثر ماتریس روی ماتریس متعامد ، ماتریس به علاوه یک ماتریس با رتبه یک را میدهد.
.
شکل (۴ـ۱) رفتار الگوریتم آرنولدی در فرایند متعامدسازی
نکته: فرض کنیدها مقادیر ویژه ماتریس تولید شده توسط روند آرنولدی باشد، در این صورت تخمینی از بردارهای ریتز متناظر با مقادیر ویژه عبارتند از که در آن بردارویژه متناظر با از ماتریس هسنبرگ است. قضیه زیر ثابت می کند که بردارهای ریتز متناظر با مقادیر ویژه را میتوان به عنوان تقریبی از بردارهای ویژه ماتریس متناظر با مقادیر ویژه بهکار برد.
قضیه ۲ـ۴: فرض کنید بردار ویژه متناظر با مقدار ویژه از ماتریس هسنبرگ باشد و یک تخمین بردار ریتز یعنی باشد، در این صورت داریم:
از این رو
اثبات: با ضرب بردار در دو طرف رابطه داریم:
بنابراین
تذکر: هر چند الگوریتم آرنولدی می تواند تا مرتبه اجرا گردد، در این صورت ماتریس هسنبرگ تولید خواهد شد که تمام مقادیر ویژه ماتریس اولیه را دارا میباشد؛ ولی باید توجه داشت که در این الگوریتم افزایش تعداد اعمال را بسیار زیاد می کند و لذا زمان اجرای محاسبات افزایش یافته و دقت تشابه و متعامدسازی نیز کاهش مییابد.
۲-۳-۲ الگوریتم آرنولدی اصلاح شده گرام اشمیت
الگوریتم آرنولدی بر اساس روند متعامدسازی گرام اشمیت پایهریزی شده است و همانگونه که در فصل اول بیان شد الگوریتم گرام اشمیت اصلاحشده از لحاظ ریاضی معادل الگوریتم گرام اشمیت استاندارد است؛ ولی از لحاظ عددی پایدارتر است. همین موضوع در مورد الگوریتم آرنولدی نیز برقرار است؛ بنابراین اساس الگوریتم آرنولدی روی آن پایهریزی می شود.
الگوریتم این روش به صورت زیر ارائه می شود.
الگوریتم آرنولدی اصلاح شده گرام اشمیت
۱ـ بردار اولیه با نرم یک و بعد از زیرفضای کرایلف را انتخاب کنید.
۲ـ به ازاء مقادیر زیر را محاسبه کنید:
در حساب دقیق ریاضی الگوریتم فوق با الگوریتم قبلی آرنولدی تفاوتی ندارد و تعداد اعمال هر دو یکسان است؛ اما شکل و طراحی الگوریتم باعث شده تا از نقطه نظر عددی خواص بهتری داشته باشد. در جدول (۲ـ۱) دیده می شود که این الگوریتم با الگوریتم آرنولدی استاندارد از لحاظ ریاضی کاملاً معادل است.
| Arnoldi-MGS | Arnoldi-GS | Method |
| Flops | ||
| Storage |
جدول (۲ـ۱): تعداد اعمال روشهای آرنولدی و آرنولدی اصلاحشده
مثال ۲ـ۱: فرض کنید یک ماتریس نواری به صورت زیر باشد.
جدول زیر عملکرد الگوریتم آرنولدی را برای ماتریس فوق به ازای تا نشان میدهد. بردار اولیه دلخواه را به صورت در نظر میگیریم. در این جدول نرم جهت نمایش میزان دقت الگوریتم درج گردیده است. همانگونه که دیده می شود؛ با افزایش دقت تشابهسازی نیز کاهش مییابد.
|
مدت زمان اجرای الگوریتم (بر حسب ثانیه) |
نرم بردار مانده | |
| ۲ | ||
| ۳ | ||
| ۶ | ||
| ۸ | ||
| ۱۰ | ||
| ۱۲ | ||
| ۱۴ | ||
| ۱۶ | ||
| ۱۸ | ||
| ۲۰ |
جدول (۲ـ۲) عملکرد الگوریتم آرنولدی برای ماتریس به ازای های مختلف
مثال ۲ـ۲ : ماتریس نامتقارن با درایههای تصادفی بین صفر و یک را به صورت زیر در نظر بگیرید. برنامه مربوط به الگوریتم آرنولدی را به ازای جهت یافتن ماتریس متعامد و ماتریس هسنبرگ اجرا میکنیم.
بعد از اجرای برنامه مربوط به الگوریتم آرنولدی به ازای ماتریس متعامد و ماتریس بالا هسنبرگی به صورت زیر به دست می آید. بردار اولیه دلخواه را به صورت (۱,۱,…,۱) در نظر میگیریم.
بررسی خطا
ماتریس که در رابطه (۲-۳) به آن اشاره شد؛ ماتریسی با مرتبه یک و با فرمول زیر به دست می آید.
ستون آخر ماتریس فوق در واقع بردار است که با ضرب این بردار در بردار ماتریس بدست می آید. همانگونه که ملاحظه می شود؛ الگوریتم آرنولدی ماتریس دلخواه را با یک ماتریس بالا هسنبرگی متشابه میسازد. لذا مقادیر ویژه این ماتریس هسنبرگی تقریباً همان مقادیر ویژه ماتریس هستند.
۲ـ۴ روش هرمیتی لنگزوس
روش هرمیتی لنگزوس به عنوان روش آرنولدی ساده شده برای ماتریسهای هرمیتی به کار میرود. اصل روش همان روش تصویری روی زیرفضای کرایلف میباشد.
قضیه زیر نشان میدهد که اگر روش آرنولدی را برای ماتریسهای هرمیتی به کار ببریم؛ چگونه به فرمهای سادهتری از ماتریسها دست خواهیم یافت.
قضیه ۲ـ۵ : فرض کنید روش آرنولدی برای ماتریس هرمیتی به کار برده شده باشد، آنگاه ضرایب تولید شده توسط الگوریتم حقیقی هستند؛ به طوری که:
به عبارت دیگر ماتریس به دست آمده از روند آرنولدی برای ماتریس هرمیتی ، حقیقی، متقارن و سه قطری است.
اثبات: با توجه به اینکه ماتریس یک ماتریس هرمیتی و بنا به ساختارش هسنبرگی است؛ بنابراین ماتریس یک ماتریس سه قطری است. به علاوه اسکالر بنا به تعریف حقیقی است و اسکالر با توجه به اینکه ماتریس هرمیتی میباشد، حقیقی است. از این رو، ماتریس هسنبرگ ، حقیقی، متقارن و سه قطری است.
این ماتریس را به صورت زیر نمایش میدهیم:
برای نمایش سادهتر الگوریتم لنگزوس قرار میدهیم:
بنابراین با تغییرات مختصری در الگوریتم آرنولدی، الگوریتم لنگزوس به صورت زیر به دست می آید.
۲-۴-۱ الگوریتم لنگزوس
۱ـ بردار اولیه با نرم یک و بعد از زیرفضای کرایلف را انتخاب کنید و قرار دهید:
۲ـ به ازاء مقادیر زیر را به دست آورید:
لذا زمانی که ماتریس متقارن یا هرمیتی باشد؛ الگوریتم لنگزوس این ماتریس را با ماتریس سه قطری و متقارن، تشابهسازی مینماید و برای ماتریس تنها نیاز به ذخیره سه بردار است.
مثال ۲-۳ : فرض کنید یک ماتریس متقارن به صورت زیر باشد. برنامه مربوط به الگوریتم لنگزوس را به ازای جهت یافتن ماتریس متعامد و ماتریس هسنبرگ اجرا میکنیم.
بردار اولیه دلخواه را به صورت (۱,۱,…,۱) در نظر میگیریم، که در آن عدد یک به تعداد ۱۲ بار تکرار شده است. بعد از اجرای برنامه مربوط به الگوریتم لنگزوس به ازای ماتریس سه قطری و متقارن به صورت زیر به دست می آید. این ماتریس با ماتریس اولیه متشابه است و مقادیر ویژه آن با ماتریس اولیه تقریباً برابر است.
و ماتریس متعامد به صورت زیر به دست می آید.
مقدار خطای تعامدسازی روش است.
۲ـ۵ روش ناهرمیتی لنگزوس
این روش در واقع تعمیم روش لنگزوس برای حالتی که ماتریس اولیه ناهرمیتی است؛ به کار میرود. این ایده توسط لنگزوس بیان شد و تفاوت اصلی آن با الگوریتم آرنولدی این است که به جای ساخت یک پایه متعامد برای زیرفضای کرایلف یک زوج پایه دو متعامد برای دو زیرفضای و ساخته می شود که در آن
و
الگوریتم این روش به صورت زیر ارائه می شود.
۲-۵-۱ الگوریتم ناهرمیتی لنگزوس
۱ـ دو بردار, به طوری که را انتخاب کنید و قرار دهید:
۲ـ به ازاء مقادیر زیر را به دست آورید:
خاطرنشان میکنیم که بینهایت راه برای انتخاب اسکالرهای و وجود دارد و انتخاب این مقادیر برای آن است که ، این دو پارامتر به عنوان ضریب مقیاس برای دو بردار و هستند.
زمانی که ماتریس متقارن باشد، آنگاه ها مثبت و حقیقی خواهند بود وها را برابر قرار میدهیم. الگوریتم فوق، ماتریسرا با یک ماتریس سه قطری تشابهسازی می کند، این ماتریس به صورت زیر است:
در این الگوریتم تا وقتیها متعلق به زیرفضای باشند، ها نیز متعلق به زیرفضای خواهند بود. در حقیقت قضیه زیر برای الگوریتم برقرار است.
قضیه ۲ـ۶ : اگر الگوریتم فوق قبل از مرحله ام متوقف نشود، آنگاه بردارهای برای
و برای تشکیل یک معادله می دهند، به عبارت دیگر
به علاوه بردارهای و به ترتیب پایهای برای زیرفضاهای
و میباشند، و روابط زیر برای الگوریتم برقرار است:
که در آن و ماتریسهای هستند که ستونهای آنها به ترتیب و است. [۳۰]
مثال ۲ـ۴ : ماتریس نامتقارن را به صورت زیر در نظر بگیرید.
برنامه الگوریتم ناهرمیتی لنگزوس را به ازاء برای این ماتریس، جهت بررسی قضیه ۲-۴ به کار میبریم.
الف ـ الگوریتم ناهرمیتی لنگزوس، ماتریس را با یک ماتریس سه قطری تشابهسازی می کند، این ماتریس به صورت زیر است:
ب ـ ماتریس در رابطه به صورت زیر محاسبه میگردد.
ستون آخر ماتریس در واقع همان بردار است.
ج ـ هر چند ماتریسهای و متعامد نیستند؛ ولی رابطه بین آنها برقرار است.
۲-۵-۲ نحوه محاسبه مقادیر ویژه و بردارهای ویژه در روش ناهرمیتی لنگزوس
مقادیر ویژه ماتریس سه قطری با هر یک از روشهای ذکرشده به دست می آید، فرض کنید این مقادیر باشند و بردارهای ویژه متناظر با این مقادیر …, باشند. مشابه با روش آرنولدی بردارهای ریتز عبارتند از: . این بردارها تقریبی از بردارهای ویژه ماتریس متناظر با مقادیر ویژه هستند.
به علاوه اگر یک بردار ویژه چپ ماتریس سه قطری متناظر با مقدار ویژه باشد، یعنی
در این صورت بردار ، یک بردار ویژه ماتریس متناظر با مقدار ویژه است.
لازم به ذکر است روش ناهرمیتی لنگزوس بر خلاف روش آرنولدی و هرمیتی لنگزوس یک روش تصویری متعامد نیست. یک روش تصویری متمایل محسوب می شود. به علاوه ماتریسهای و به دست آمده از الگوریتم ناهرمیتی لنگزوس متعامد نیستند؛ ولی رابطه بین آنها برقرار است.
نتیجه: ماتریس دلخواه مفروض است، در این فصل دو روش آرنولدی و روش ناهرمیتی لنگزوس برای ماتریس دلخواه مورد بحث قرار داده شد. در روش اول یک پایه متعامد برای زیرفضای کرایلف تولید می شود؛ در صورتی که در روش دوم، دو پایه متعامد تولید می شود. روش آرنولدی به خاطر خواص تعامدش برای ماتریسهای نرمال بهتر عمل می کند. از طرف دیگر روش ناهرمیتی لنگزوس تقریبهایی از دو بردار ویژه راست و چپ را تولید می کند که برای برخی کاربردها مفید است.
۲-۶ الگوریتم آرنولدی با شروع مجدد
تعداد مراحل تکرار در الگوریتم آرنولدی می تواند زیاد باشد، این تعداد قابل پیش بینی نیست و به خاصیت ماتریس بستگی دارد. تعداد تکرار بالا مستلزم حافظه کافی برای ذخیرهی بردارهای آرنولدی است که این بسیار هزینهبر است. به همین دلیل الگوریتم آرنولدی با شروع مجدد ضمنی(IRA) هزینهها را وسیله محدود کردن بعد زیرفضای جستجوکاهش میدهد. این بدان معنی است که تکرار بعد از یک تعداد مرحله متوقف می شود(این تعداد بزرگتر از تعداد مقادیرویژه خواسته شده است). در واقع بعد زیرفضای جستجو بدون اینکه ساختار زیرفضای کرایلف از بین برود، کاهش مییابد.
الگوریتم آرنولدی با شروع مجدد ضمنی اولین بار توسط سورنسون[۳۳] پیشنهاد شد. الگوریتم لنگزوس با شروع مجدد ضمنی مشابه با الگوریتم آرنولدی با شروع مجدد بیان شده است با این تفاوت که برای ماتریسهای متقارن کاربرد دارد. این الگوریتم همراه با الگوریتم لنگزوس با شروع مجدد ضمنی در بستهی نرمافزاری ARPACK ارائه شد. پایه این الگوریتمها برای یافتن مقادیرویژه ماتریس اسپارس در متلب است.
۲-۶ -۱ الگوریتم تکرار آرنولدی - مرحله
ورودی الگوریتم : ماتریس و ماتریس شروع
خروجی الگوریتم: ماتریس هسنبرگی (مقادیرویژه آن تقریبا با مقادیربرابر است) و خطا
در این الگوریتم، با الگوریتم آرنولدی تکرار می شود. مشاهده می شود چگونه بعد زیر فضای جستجو بدون از بین رفتن اطلاعات مربوط به بردارهای ویژه کاهش مییابند.
مرحله در الگوریتم فوق الذکر الگوریتم متعامدسازی گرام اشمیت را بیان می کند که بصورت زیر است:
بصورت قرارداد در نظر میگیریم. هرچند متعامدسازی گرام اشمیت کلاسیک سریعتر است ولی به دقیقی متعامدسازی گرام اشمیت اصلاح شده نمی باشد برای همین اکثر مواقع کاملا بزرگ است. بنابراین متعامدسازی برای بدست آوردن تعامد مطلوب تکرار می شود.
اصلاحات ممکن مرحله که مربوط به تکرار دوم است بصورت زیر است:
همچنین داریم:
از طرفی
برای همین داریم:
تعداد تکرارهای بالاتر ممکن است ولی به ندرت لازم است.
بعد از اجرای الگوریتم ۲-۶ -۱، نسبت آرنولدی به صورت زیر است:
که بوسیلهی موارد زیر قابل دسترس است:
اگر باشد آنگاه روی ماتریس پایا است بدین معنی است که
در واقع موقعیتی مناسب است که
به همین دلیل مقادیر ریتز و بردارهای ریتز، مقادیرویژه و بردارهای ویژه از هستند.
میتوان امیدوار بود که کوچک است آنگاه
آنگاه روی ماتریس پایا است، که با متفاوت است و انحراف آن به وسیله است که مقدار آن برابر است. میتوان گفت در شرایط مناسب مقادیرویژه از تقریب خوبی برای مقادیرویژه از هستند.
در ادامه بررسی میکنیم چگونه میتوان یک یافت در صورتی که کوچک باشد.
۲-۷ شروع مجدد ضمنی
ابتدا از تکرار آرنولدی شروع میکنیم
۲-۷ -۱ الگوریتم مرحله ضمنی بروی ماتریس
این الگوریتم پس از فراخوانی الگوریتم ۲-۶-۱ بدست می آید.
مرحله ضمنی بطوریکه بر روی ماتریس با انتقال را بکار میگیریم.
تعریف میکنیم . در واقع ضرب تا از ماتریسهای هسنبرگ یکانی است بطوریکه شامل زیر قطر ناصفر زیر قطر اصلی است.
همچنین تعریف میکنیم
آنگاه از الگوریتم ۲-۶-۱ بدست میآوریم:
یا
همانطور که بیان شد دارای مقدار غیر صفر زیر قطر اصلی است. ساختار سطر آخر بصورت زیر است:
تعداد صفرها و تعداد عناصر غیرصفر برابر است و است. حال اگر ستون از ستون در عبارت را در نظر نگیریم داریم:
در ادامه کلیه نتایجی که تا اینجا کسب نمودیم در الگوریتم ۲-۷-۲ بکار میبریم.
میتوان گفت یک مرحله با انتقال ها بردار را به یک چندگانگی از تبدیل می کند. در واقع این اصلاح ساده از تکرار آرنولدی عبارت زیر را میدهد:
۲-۷-۲ الگوریتم شروع مجدد ضمنی آرنولدی(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-ریتز برای تقریب بردار ویژه به جای اینکه همه آنها را محاسبه نمود، استفاده کرد.
اگر تعداد را بنامیم :
الف) هرگاه باشد آنگاه هریک از بردار F-ریتز به صورت وابسته خطی عددی میباشد، از هرکدام از عددها چندگانگی را تشخیص میدهیم.
ب) هرگاه باشد آنگاه هریک از بردار F-ریتز به صورت مستقل خطی میباشد.
پس حداقل گانه میباشد. آنگاه الگوریتم آرنولدی سراسری را با یک جدید مستقل از قبلی اجرا نموده و بردارهایF-ریتز همگرای جدید را محاسبه میکنیم و آنها را به مقادیر قبلی
اضافه میکنیم. اگر به صورت وابسته خطی عددی باشد آنگاه رتبه[۱۰]ماتریس برابر می شود درغیر اینصورت ادامه میدهیم. قضیه و آزمایش عددی نشان میدهد که این فرایند مقدارویژه چندگانه و مکان آن را تا وقتی که شرط مقدارویژه خواسته شده کوچکتر از معکوس نرم باقیمانده باشد، بدست می آورد.
روش آرنولدی سراسری در حافظه بسیار پرهزینه است و هزینه محاسبات با اضافه شدن افزایش مییابد. بنابراین برای کاهش این هزینهها، شروع مجدد هنگامیکه به تقریبی از مقدارویژه برای بالاترین مقدار نرسیده است، لازم است. عملیات شروع مجدد ابتدا توسط کاروش[۱۱] [۲۲] بیان شده است سپس طرح شروع مجدد به وسیله تعداد زیادی از پژوهشگران مورد تحقیق قرار گرفت. بهخصوص پایگه[۱۲] [۱۰]، کولوم [۱۳]و دونات[۱۴] [۱۰] ، گلوب[۱۵] و آندروود[۱۶][۱۲] ، سد[۱۷][۲۷,۲۸] و چاتلین[۱۸] و هو[۱۹][۶]که همگی آنها طرح، شروع مجدد ضمنی بودند. پس از طی چندین سال مشهورترین طرح شروع مجدد توسط سورنسون[۲۰] [۳۳] ارائه شد که ترکیبی از تکرار انتقال ضمنی با فرایند آرنولدی میباشد. همچنین انتقالهای دقیق در [۳۳] بیان شده است.
در ادامه این پایان نامه الگوریتم شروع مجدد را با فرایند آرنولدی سراسری ادامه میدهیم و الگوریتم ضمنی شروع مجدد آرنولدی سراسری[۲۱] با مقادیر F-ریتز ناخواسته، توسط انتقال پیاده سازی میکنیم.
نکاتی که در این پایان نامه باید در نظر داشت :
یک ماتریس قطری پذیر بزرگ است.
مقدارویژه و بردارویژه متناظر با آن میباشد.
نرم طیفی یک ماتریس و نرم-۲ بردار است.
نرم فریبنیوس یک ماتریس میباشد و
حرف بالای ماتریس به معنای ترانهاده مزدوج آن ماتریس میشد
ماتریس واحد است
بردارهای ویژه و تقریب آنها با طول واحد نرمالسازی میشوند.
۳-۳ فرایند آرنولدی سراسری ، FOM سراسری و GMRES سراسری
تعریف ۳-۲ : فرض کنید را فضای خطی فشرده از ماتریس مثلثی باشد. برای دو ماتریس و در ، -Fضرب داخلی را بصورت زیرتعریف میکنیم:
که به معنی اثر [۲۲]ماتریس مربعی میباشد.
تعریف ۳- ۳ : هنگامیکه و ، F-متعامد باشند آنگاه -Fضرب داخلی آن برابر صفر میباشد و بصورت زیر تعریف می شود:
تعریف ۳-۴ : برای هر ماتریس اولیه ، زیرفضای کرایلف ماتریس تعریف می شود و بصورت زیر است:
که زیرمجموعه است.
در واقع اگر یعنی، به ازای یک اسکالر ،
اگر و با تعریف یک عمل خطی که:
آنگاه داریم:
که یعنی ضرب داخلی از فضای بردار مختلط میباشد.
تعریف ۳-۵ : را ضرب کرونکر[۲۳] ماتریس و نشان میدهیم، که خواص اساسی آن عبارتند از: (خاصیتهای پایه در [۱۱] ذکر شده است)
اگر ، آنگاه داریم:
هر مقدارویژه ، از ،یک مقدارویژه گانه از است.
در ادامه به توضیح الگوریتم آرنولدی سراسری میپردازیم. اساس این الگوریتم بر فرایند گرام اشمیت اصلاح شده است، که یک پایه -Fمتعامد ، از زیرفضای کرایلف ماتریس را میسازدکه برای که دلتای کرونکر است.
در ادامه الگوریتم آرنولدی سراسری و قضایای مربوط به آن را شرح میدهیم.
۳-۳-۱ الگوریتم آرنولدی سراسری ( الگوریتم ۱) [۱۶,۲۴]
ورودی الگوریتم : ماتریس و ماتریس شروع
خروجی الگوریتم: ماتریس هسنبرگی (مقادیرویژه آن تقریبا با مقادیربرابر است) و ماتریس نتیجه
این فرایند به ضرب ماتریس در بردار به علاوهی عملیات ممیز شناور نیاز دارد.
اگر را به صورت ،همچنین و را دو ماتریس هسنبرگی و در نظر بگیریم که عناصر غیرصفر آن توسط الگوریتم (۱) تعریف نمائیم. آنگاه :
که در آن ، امین پایه به صورت زیر است.
قضیه۳-۱: [۱۶] اگر ، و را طبق تعاریف بالا داشته باشیم، آنگاه یک پایه -Fمتعامد از زیرفضای کرایلف ماتریس و داریم:
( ،ماتریس صفر است و )
مثال ۳-۱: فرض کنید باشد یک ماتریس تصادفی بصورت زیر باشد.
ماتریس شروع را نیز بصورت زیر تعریف میکنیم:
ماتریس را با بردار شروع به عنوان ورودی به الگوریتم سراسری آرنولدی میدهیم سپس در اولین مرحله ماتریس بدست می آید.
| iter Residual norms |
| جدول (۵-۲) عملکرد الگوریتم آرنولدی سراسری پایه برای ماتریس تصادفی |
در شکل (۳-۱) رفتار همگرایی مسئله برای و 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-ریتز، یک مقدارویژه و مکان بردارویژه از را به وسیله رجوع به جفت ریتز استاندارد از روی زیرفضای تقریب میزند.
قضیه۳-۳: عبارات زیر برقرار هستند
اثبات عبارت :
آنگاه نتیجه میگیریم:
و برای اثبات عبارت تنها باید توجه کنیم که:
آنگاه عبارت نیز اثبات گردید.
فرمولهای
و
نشان می دهند نرم فروبنیوس باقیمانده جفت F-ریتز دقیقا با نرم-۲ باقیمانده جفت ریتز برابر است که توسط روش آرنولدی استاندارد روی ماتریس در سر تا سر زیرفضای تشکیل شده است.
لازم به ذکر است از عبارت
میتوان برای پایان حلقه و همچنین تست کردن همگرایی روش آرنولدی سراسری بدون محاسبهی استفاده کرد.
طی روش آرنولدی استاندارد روی ماتریس در سرتاسر زیرفضای بردارهای ریتز را داریم:
طبق فرض اینکه پس است. برای همین غیرنرمال هستند و نرم آنها همواره کمتر از یک است. تا وقتی که هیچیک از پایه های نامتعامد خاص نباشند، عموما باید در سایز مقایسه شوند.
به طور مثال اگر داشته باشیم بنابراین داریم:
با ترکیب موارد بالا و اثبات قضیه ۳-۳ داریم:
طرف چپ رابطه بالا نرم باقیمانده از جفت F-ریتز نرمال است و طرف راست آن فقط نرم باقیمانده از است که یک تقریب جفتویژه از است. رابطه (۲۰) و (۲۱) نشان میدهد که اگر روش آرنولدی استاندارد برای همگرایی بکار رود، همه بردار F-ریتز ، تقریب خوبی برای بردارهای ویژه از که به مقدارویژه اختصاص دارند، هستند. به همین دلیل روش آرنولدی سراسری خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد و برای یکسان باقیماندهی قیاسپذیری را بدست می آورد. میتوان برای درک بهتر به منابع[۱۹,۲۰,۲۱,۲۶,۲۷] مراجعه کرد.
۳-۴-۱ الگوریتم آرنولدی سراسری با شروع مجدد[۲۴]( الگوریتم ۲)
ورودی الگوریتم : ماتریس و ماتریس شروع
خروجی الگوریتم: ماتریس هسنبرگی (مقادیرویژه آن تقریبا با مقادیربرابر است) و ماتریس نتیجه
فرض کنیم برای که جفتهای ویژه خواسته شده از و خطای خواسته شده . یک ماتریس به نام و ماتریس را به بطویکه به عنوان ماتریس شروع میگیریم.
- به ازای زیرشاخهی زیر را تکرار میکنیم تا وقتی که همگرا شود
الف) پایه F-متعامد، را به وسیله الگوریتم(۱) بدست میآوریم.
ب) جفت ویژه را توسط ماتریس هسنبرگ نتیجه محاسبه میکنیم و از استفاده میکنیم تا مقادیرویژه خواسته شده را تقریب زده شود.
ج) به ازای قرار میدهیم: .
د) همگرایی جفتهای تقریبی ویژه بررسی میکنیم.
ه)اگر کلیه نتیجهها کمتر از بود آنگاه به مرحله ۳ میرویم.
نکتهای که باید در نظر داشت این است که اگر باشد روش آرنولدی سراسری همان روش آرنولدی پایه استاندارد است.
۳-۵ مسائل مقادیرویژه چندگانه
همانطور که قبلا گفتیم با فرض اینکه قطریپذیر باشد اگر قطریپذیر باشد، مقادیر F-ریتز همواره ساده است، حتی اگر دارای مقادیرویژه چندگانه باشد. به همین دلیل اگر تنها دارای مقادیرویژه ساده داشته باشد، روش آرنولدی سراسری برای این مسئله کار میدهد. در نتیجه وقتی خواسته شده چندگانه باشد، این روش به خودی خود نمیتواند چندگانگی را تشخیص دهد و همچنین مکانویژه اختصاص داده شده به آن مقدارویژه را محاسبه کند. تحلیل نظری که میتوان از [۲۱] نتیجه گرفت این است که چگونه روش آرنولدی سراسری برای حل مسائل مقدارویژه چندگانه می تواند موفق باشد.
همواره فرض میکنیم یک ماتریس قطریپذیر و دارای مقادیرویژه مجزا تایی است و چندگانگی با بطوریکه نشان داده می شود.
فرض کنید عنوان فضایویژه که به اختصاص دارد و ستونهایی از
به صورت یک پایه از که به ازای .
ماتریس شروع با اندازه به صورت است آنگاه به ازای هر ، بدست می آید که بصورت یکتا بسط پیدا می کند :
تعریف میکنیم:
هنگامیکه باشد واضح است رتبهی ناقص سطری دارد. فرض کنید ماتریس برای رتبهی کامل سطری دارد. میتوان فوقالذکر را بصورت زیر نوشت:
به طوریکه دارای بردارهای ویژه با طول یک که به اختصاص دارد.
طبق فرض روی که ، را همچنین یک پایه از میباشد و برای ، باید وابستهی خطی به به ازای باشد و متعلق به فضای تولید شده توسط است. به عبارت دیگر تعریف میکنیم :
و
آنگاه برای ، رتبهی ستونی کامل دارد درصورتیکه برای دارای رتبهی ناقص ستونی است و کوچکترین مقدارتکین آن نیز برابر صفر است. در ادامه مبحث فرض میکنیم نرمال باشد و همچنین فرض میکنیم که ستونهایی از برای قویاً مستقل خطی است که این بدین معناست که کوچکترین مقدارتکین از کوچک نیست و برای خوش وضع است. این فرض برای یک پایه از درنظر گرفته می شود و بصورت تصادفی تولید می شود.
قضیهی زیر قادر به تعیین مقدار عددی به وسیله روش آرنولدی سراسری است.
قضیه۳-۴: فرض میکنیم شعاعهای طیفی هستندکه به اختصاص داده میشوند و تعریف میکنیم ماتریس
و آنگاه
ازآنجائیکه عدد شرطی است و قبلا در عبارت تعریف شده است. و کوچکترین مقادیرتکین از ماتریسهای و هستند. به این ترتیب داریم :
بطور دقیق، اگر ، آنگاه
رابطه درستی در شرط نرم باقیمانده را تخمین میزند؛ از آنجائیکه به صورت عدد شرطی عمل می کند و شرایطی از را اندازه میگیرد.
اگر یکی از و بزرگ باشد و یا تفکیک از تخمین و دیگر مقادیرویژه دقیق خیلی کوچک باشند، بد وضع است. در عبارت میتوان دید که اگر قیاسپذیر با و یا بزرگتر از باشد آنگاه ممکن است کوچک نباشد.
براساس این قضیه میتوان تصمیم گرفت که اگر به ازای به صورت تخمینی از رتبه ناقص ستونی در عبارت باشد و بدینسان چندگانگی قابل تعیین است و میتوان یک پایه تقریبی را بدست آورد. به عبارت دیگر تخمینی از رتبه ناقص ستونی برای است و دارای رتبهی ستونی کامل برای است. برای همین به ازای برای کوچک نیست.
میتوان گفت را اینگونه در نظر میگیریم:
فرض میکنیم . آنگاه اگر کمترین عدد طبیعی باشد بطوریکه
با یک مقدار ثابت معنادار که کوچکتر از است، بصورت یک گانه و برابر است. در واقع در عمل، یک ثابت شناخته نشده است که میتوان آن را کمتر از در نظر گرفت مثلا یا کوچکتر، که بدین معنی است که به ازای بطور کامل به صورت بدوضع است ؛ حال اگر باشد میتوان گفت برابر یا است. بنابراین اگر قیاسپذیر یا بزرگتر از و معتبر باشد این فرایند ممکن است برای تشخیص موفق نباشد.
در عمل، داده شده است، یک ماتریس تصادفی ، تعریف شده در عبارت که شرط رتبهی ماتریس بر آن برقرار است، را میسازیم.
با ، اگر مقدارویژه عددی گانه را محاسبه کنیم آنگاه مقدارویژه آن حداقل گانه است به همین دلیل در مواردی که باشد، تشخیص به طور قطع قابل حل نمی باشد. ادامه نتایج بدست آمده از مقالات [۲۰,۲۱] به روشنی غلبه بر این مشکل را نشان میدهد.
در ابتدا یک ماتریس شروع تصادفی با ستونهای انتخاب میکنیم. اگر یک مقدارویژه گانه یافتیم آنگاه میتوان الگوریتم۳-۴-۱ را با یک ماتریس اولیه شروع جدید با ستونهای به کار گرفت که به صورت تصادفی انتخاب می شود. حال میتوان یک مقدارویژه چندگانه را محاسبه کرد که از نظر عددی با مقدار محاسبهشده با برابر است. سپس میتوان رتبهی ماتریس را تعیین کرد که شامل بردارهای F-ریتز همگرا با مقادیرF-ریتز همگرا چندگانه عددی است.
نکته قابل توجه این است هنگامی که مسئله مقدارویژه از ماتریس در شرایط بدوضع نباشد؛ اگر برخی مقادیرتکین از این ماتریس با مرتبهی یکسان به صورت ماکزیمم نرمهای باقیمانده از این جفتهای داخلی همگرا باشد آنگاه از نظر عددی آنها را صفر در نظر میگیریم.
اگر رتبهی عددی ماتریس کمتر از باشد، آنگاه چندگانگی این مقدارویژه، رتبهی چنین ماتریسی است. در غیراینصورت الگوریتم (۲) ، با شرط را تکرار میکنیم و تا وقتی که رتبهی عددی ماتریس که شامل این به بردارهای F-ریتز که با شروع میشوند، همگرا شوند که همانطور که انتظار میرود این مقدار کمتر از است. پس میتوان گفت چندگانگی مقدارویژه () قابل تشخیص و برابر با رتبهی عددی ماتریس است.
بطور خلاصه یک الگوریتم آرنولدی سراسری برای مسئله مقدارویژه چندگانه را ارائه می شود.
۳-۵-۱ الگوریتم آرنولدی سراسری برای مسائل مقدارویژه چندگانه
ورودی الگوریتم : ماتریس و ماتریس شروع و
خروجی الگوریتم: ماتریس هسنبرگی (مقادیرویژه آن تقریبا با مقادیربرابر است) و مقدار
مجموعه و و و خطا راتعیین می کنیم.
ماتریس شروع ، بطوریکه راانتخاب می کنیم.
به ازای زیرشاخهی الف، ب، ج و د را تکرار میکنیم تا وقتی که همگرا شود.
الف) پایه F-متعامد، را به وسیله الگوریتم(۱) بدست میآوریم.
ب) جفت ویژه را توسط ماتریس هسنبرگ نتیجه محاسبه میکنیم و از استفاده میکنیم تا مقادیرویژه خواسته شده را تقریب زده شود.
ج)همگرایی جفتهای ویژه را بررسی می کنیم.
د)اگر کلیه نتیجهها کمتر از بود آنگاه به مرحله ۴ می رویم.
- به ازای کلیه و مجموعه و تعداد ستونها
الف) رتبهی عددی از برای کلیه را محاسبه می کنیم.
ب) اگر باشد، و را از حذف می کنیم.
ج) در غیر اینصورت، و قرار می دهیم و به مرحله ۲ می رویم.
در این فصل روشهای آرنولدی سراسری، FOM سراسری و GMRES سراسری معرفی شد ، توضیحاتی از الگوریتم آرنولدی سراسری برای مقادیرویژه چندگانه داده شد و همچنین قضایای مربوطه بیان شد. مثال عددی که به عنوان ورودی به الگوریتم آرنولدی سراسری پیاده سازی شده در نرمافزار متلب داده شد و نتایج و نمودار بدست آمده، گزارش داده شد. در فصل بعد فرایند آرنولدی سراسری با شروع مجدد ضمنی همراه با الگوریتمها بیان می شود.
فصل چهارم
فرایند آرنولدی سراسری
با
شروع مجدد ضمنی
فصل۴ فرایند آرنولدی سراسری با شروع مجدد ضمنی
۴-۱ مقدمه
الگوریتم آرنولدی سراسری پایه، هنگامی که زیاد می شود الگوریتم پرهزینه و غیرعملی می شود، زیرا با افزایش میزان حافظه اضافی و هزینه محاسبات بالا میرود برای همین باید محدود شود که زیاد نشود. برای اینکه الگوریتم کارا باشد، شروع مجدد ضروری است. همانطور که قبلا بیان شد تکنیک شروع مجدد ضمنی توسط سورنسون[۲۵] [۳۳] بیان شد که الگوریتمی مشهور و موفق است. حال نشان میدهیم چگونه آن را به فرایند آرنولدی سراسری گسترش دهیم و به الگوریتم آرنولدی با شروع مجدد ضمنی (IRGA) برسیم. همچنین میتوان مشابه با الگوریتم آرنولدی با شروع مجدد ضمنی از تعداد F-ریتز ناخواسته با انتقال استفاده کرد که به اسم انتقالهای دقیق نیز نامیده میشودو الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) با انتقالهای دقیق را نتیجه گرفت.
۴-۲ الگوریتم آرنولدی سراسری باشروع مجدد ضمنی
اگر را یک عددصحیح ثابت در نظر بگیریم که تعداد جفتهای خواستهشده از است و مراحل برابر است. مرحله فرایند آرنولدی سراسری بصورت زیر است:
همچنین میتوان تکرار انتقال داده شده را برای تجزیه بکار گیریم. را یک انتقال در نظر میگیریم و
اگر در تجزیه ، ماتریس متعامد و ماتریس بالامثلثی داشته باشیم آنگاه
و
بنابراین بدست میآوریم
دراینصورت داریم
کابرد پی در پی انتقالهای ضمنی نتیجه میدهد
از آنجائیکه
که هر یک ماتریس متعامد که به انتقال اختصاص دارد.
حال تفکیک میکنیم :
همچنین نکتهای که باید توجه داشت این است که
پس در نتیجه بدست میآوریم:
ستون اول از دو طرف را برابر میکنیم و بدست میآوریم:
از آنجائیکه
.
نکتهای که باید در نظر داشت این است که
و
پس داریم:
یک فرایند آرنولدی سراسری مرحله ای جدید با به روزشده شروع می شود برای همین نیاز به شروع مجدد و گسترش آن به یک مرحله ای نیست.
نکتهی قابل توجه این است که مشابه با الگوریتم آرنولدی با شروع مجدد ضمنی[۲۶](IRA) [33] میتوان از تعداد F-ریتز ناخواسته با انتقال استفاده کرد که به اسم انتقالهای دقیق نیز نامیده می شود.
حال در ادامه الگوریتم IRGA[27] با انتقالهای دقیق شرح داده می شود.
۴-۲-۱ الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) با انتقالهای دقیق
جفتهای ویژه داده شده است و همچنین و را انتخاب میکنیم و را برابر قرار میدهیم و را برابر به عنوان یک ماتریس شروع قرار میدهیم.
فرایند آرنولدی سراسری مرحله ای را اجرا میکنیم و را بدست میآوریم.
جفتهای ویژه از را حساب میکنیم از بین آنها جفت ویژه از را به عنوان تقریبی از مقادیرویژه خواسته شده و تعداد مقدارویژه ناخواسته را به عنوان انتقالها میگیریم.
شروع مجدد ضمنی با کاربرد انتقال انجام میدهیم، الگوریتم آرنولدی سراسری را به روز میکنیم و نتیجه میدهد
همگرایی را تست میکنیم اگر به نتیجه رسیده باشیم توقف میکنیم در غیراینصورت به مرحله ۲ میرویم و فرایند آرنولدی سراسری را ادامه میدهیم.
۴-۲-۲ الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) برای مسائل مقدارویژه چندگانه
جفتهای ویژه داده شده است و همچنین و را انتخاب میکنیم و را برابر قرار میدهیم . مجموعه ، ، و را تعریف میکنیم.
را برابر به عنوان یک ماتریس شروع قرار میدهیم.
فرایند آرنولدی سراسری مرحله ای را اجرا میکنیم و را بدست میآوریم.
جفتهای ویژه از ماتریس را محاسبه میکنیم و به عنوان تقریبی از مقادیرویژه خواسته شده انتخاب میکنیم و به تعداد ، ناخواسته ، را به عنوان انتقالها در نظر میگیریم.
شروع مجدد ضمنی با انتقالهای بکار میبریم و الگوریتم آرنولدی سراسری را به روز می کند و نتیجه میدهد.
همگرایی را تست میکنیم اگر به نتیجه رسیده باشیم به مرحله ۷ میرویم در غیراینصورت به مرحله ۳ میرویم و فرایند آرنولدی سراسری را از مرحله به بالا بسط میدهیم.
. به ازای کلیه و مجموعه و تعداد ستونها:
الف) رتبهی عددی از برای کلیه را محاسبه می کنیم.
ب) اگر باشد، و را از حذف می کنیم.
ج) در غیر اینصورت، و قرار می دهیم و به مرحله ۲ می رویم.
قابل ذکر است که اگر یک ماتریس متقارن حقیقی باشد آنگاه الگوریتم ۴-۱-۱ با ساده کردن فرایند آرنولدی سراسری به عنوان فرایند لنگزوس سراسری متقارن کار می کند.
در این فصل الگوریتم آرنولدی سراسری با شروع مجدد ضمنی و همچنین الگوریتم آرنولدی سراسری با شروع مجدد ضمنی برای مسئله مقدارویژه چندگانه معرفی شد. در فصل بعد نتایج عددی حاصل از اجرای برنامه ها توسط نرمافزار متلب برای ماتریسهای بزرگ غیرهرمیتی بیان می شود.
فصل پنجم
نتایج عددی
فصل ۵ نتایج عددی
۵- ۱ مقدمه
در این فصل روشهای بیان شده در قالب مثالهای عددی با بهره گرفتن از نرمافزار متلب مورد بررسی قرار میگیرد. در این مثالها از ماتریسهای بزرگ و همچنین شناخته شده نیز استفاده می شود و نتایج عملکرد هر روش به صورت نمودار نشان داده می شود.
برای روشن ساختن کارایی الگوریتمها مثالهای عددی میآوریم همچنین برای میزان بهرهوری و اعتبار IRGA مثالهایی آمده است.
تمامی این مثالها روی کامپیوتری با نرمافزاری MATLAB 7.1 اجرا شده و نتیجه میدهد. اگر نرم باقیمانده وابسته
با تعیین کردن اگر رابطه همگرایی بالا برقرار باشد آنگاه قابل قبول است. طبق تحلیل قبلی فرض میکردیم که
که برای کوچک، مسائل ویژه چندگانه کاملا در شرایط وخیمی قرار میگیرند.
در مثالها به صورت تصادفی بدست می آید، همچنین iter تکرار برنامه در نظر گرفته می شود و Residual norms را نرم باقیمانده وابسته در نظر میگیریم.
۵-۲ بررسی روش آرنولدی سراسری پایه
مثال ۵-۲-۱: این آزمایش روی مجموعه ای از ماتریسهای آزمایشی از جمله ماتریس که به فرم زیر است اجرا می شود
اگر فرد باشد دارای مقدار صفر در قطر اصلی و مقادیرویژه مشخص و تکین است. مقادیرویژه مثبت و منفی ، ، ،…، (۱ یا ۰) هستند.
ماتریس به ازای را به عنوان ورودی به الگوریتم آرنولدی سراسری پایه میدهیم و سپس توسط تابع آرنولدی سراسری که در کدنویسی متلب به شکل زیر است:
به ازای ، ماتریس متعامد و ماتریس بدست می آید.
جدول (۵-۱) نتایج بدست آمده را نشان میدهد همچنین شکل (۵-۱) منحنی همگرایی برای را نشان میدهد. نشان میدهیم این الگوریتم تقریبا
| iter Residual norms |
جدول (۵-۱) عملکرد الگوریتم آرنولدی سراسری پایه برای ماتریس به ازای های مختلف
شکل (۵-۱) ماتریس با
شکل (۵-۲) ماتریس با
مثال ۵-۲-۲: این آزمایش را روی ماتریس نامتقارن bcsstk11 ازمجموعه Matrix Market انجام میدهیم. معیار توقف برنامه هنگامی است که نرمهای باقیمانده از تقریب جفتهای ویژه کمتر از یا تعداد تکرارها به ۸۰ برسد.
| iter Residual norms |
جدول (۵-۲) عملکرد الگوریتم آرنولدی سراسری پایه برای ماتریس bcsstk11 به ازای های مختلف
شکل (۵-۳) ماتریسbcsstk11 با
شکل (۵-۴) ماتریسbcsstk11 با
۵-۳ بررسی روش آرنولدی سراسری برای مسائل مقدارویژه چندگانه
مثال ۵-۳-۱:این آزمایش را روی ماتریس نامتقارن dw8192 [۳] انجام میدهیم معیار توقف برنامه هنگامی است که نرمهای باقیمانده از تقریب جفتهای ویژه کمتر از باشد. نشان میدهیم این الگوریتم کاملا به iter مربوط است. همچنین میتوان از جدول مشاهده کرد که به ازای های بزرگتر همگرایی الگوریتم برای مقادیرویژه سریعتر اتفاق میافتد این مسئله به وضوح در نمودار مشخص است.
| iter Residual norms |
جدول (۵-۳) عملکرد الگوریتم آرنولدی سراسری پایه برای ماتریس dw8192
شکل (۵-۵) ماتریسdw8192 برای
۵-۴ بررسی روش آرنولدی سراسری با شروع مجدد ضمنی برای مسائل غیرهرمیتی بزرگ
مثال ۵-۴-۱: این آزمایش روی مجموعه ای از ماتریسهای آزمایشی از جمله ماتریس که به فرم زیر است اجرا می شود
اگر فرد باشد دارای مقدار صفر در قطر اصلی و مقادیرویژه مشخص و تکین است. مقادیرویژه مثبت و منفی ، ، ،…، (۱ یا ۰) هستند. مسئله مقدارویژه برای وقتیکه n=2000 در شرایط وخیمی قرار میگیرد، عدد شرط از بردارویژه ماتریس محاسبه می شود و برابر است. هرچند کوچکترین عدد شرطی طیفی از یک مقدارویژه مجزا بیشتر از است. بنابراین میتوان انتظار داشت محاسبهی بزرگترین جفتهای ویژه با بهره گرفتن از الگوریتمهای آرنولدی بسیار مشکل است.
الگوریتم ۴-۱-۱ را روی ماتریس اجرا میکنیم و زمان توقف برنامه هنگامی است که نرمهای باقیمانده از تقریب جفتهای ویژه کمتر از باشد. در واقع میخواهیم ۴ تا از بزرگترین مقادیرویژه که شامل ۱۹۹۹، ۱۹۹۷، ۱۹۹۵، ۱۹۹۳ را محاسبه کنیم. شروع مجدد یکسانی برای تعیین درستی به ازای های مختلف دارد. این توجیهای است که الگوریتم آرنولدی سراسری سرعت همگرایی یکسانی دارد هم چنان که الگوریتم آرنولدی استاندارد مثلا برای سرعت همگرایی یکسان دارد این مسئله کاملا به iter مربوط است. هم چنین میتوان از جدول مشاهده کرد که به ازای های بزرگتر تعداد شروع مجدد کمتر استفاده می شود و همگرایی الگوریتم برای مقادیرویژه سریعتر اتفاق میافتد.
جدول (۵-۴) عملکرد الگوریتم آرنولدی سراسری با شروع مجدد ضمنی برای ماتریس به ازای های مختلف
شکل (۵-۶) ماتریس با
مثال ۵-۴-۲: این آزمایش را روی ماتریس نامتقارن dw8192 [۳] انجام میدهیم معیار توقف مانند مثال قبل است. در واقع ۴ تا از بزرگترین مقادیرویژه از نظر بزرگی را محاسبه میکنیم
این مقادیرویژه نزدیک بهم ولی از نظر عددی مجزا هستند. به همین دلیل این مسئله ممکن است برای انواع الگوریتمهای آرنولدی آسان نباشد. جدول (۵ـ۲) نتایج را گزارش میدهد همانطور که میبینیم الگوریتم پیشنهاد شده این مسئله را بصورت مفید و موثر حل می کند. شکل (۵ـ۲) منحنی همگرایی برای نمایش میدهد. از طرف دیگر مشاهدات یکسان با مثال قبل میبینیم.
جدول (۵ـ۵) عملکرد الگوریتم آرنولدی سراسری با شروع مجدد ضمنی برای ماتریس dw8192 به ازای های مختلف
شکل (۵ـ۷) ماتریس dw8192
مثال ۵-۴-۳: حال الگوریتم را روی ماتریس نامتقارن حقیقی بهنام OLM1000 [۳] آزمایش میکنیم. معیار توقف همانی است که در دو مثال قبل استفاده میکردیم. میخواهیم ۴ تا از بزرگترین مقادیرویژه از نظر بزرگی را محاسبه میکنیم
این مقادیرویژه نزدیک بهم ولی از نظر عددی مجزا هستند( مانند مثال ۵-۳-۱ ) به همین دلیل این مسئله ممکن است برای انواع الگوریتمهای پیشنهاد شده آسان نباشد. جدول (۵ـ۳) نتایج بدست آمده را گزارش میدهد همچنین شکل (۵-۳) منحنی همگرایی را برای نمایش میدهد با توجه به جدول و نمودارها میتوان نتیجه گرفت این الگوریتم این مسئله را بصورت مفید و موثر حل می کند. این نتایج مشابه نتایج بدست آمده از مثال ۵-۳-۱ است.
جدول (۵ـ۶) عملکرد الگوریتم آرنولدی سراسری با شروع مجدد ضمنی برای ماتریس OLM1000 به ازای های مختلف
شکل (۵-۸) ماتریس OLM1000 با
مثال ۵-۴-۴: در این مثال معادله
روی یک فضای مربعی با شرط مرزی درنظرگرفته می شود. را برابر یک میگیریم. ماتریس سه بعدی بلوکی حاصل عبارت است از:
و از آنجا که یک ماتریس سهبعدی است و
و تعداد نقاط شبکه روی هر طرف مربع است. را میتوان برای های بزرگ بصورت در نظر گرفت. مقادیرویژه و بهم نزدیک هستند و با افزایش نزدیکتر نیز میشوند.
الگوریتم ۴-۱-۱ را روی ماتریس آزمایش میکنیم و بوسیلهی بدست می آید. ۴ مقادیرویژه با بزرگترین قسمت های حقیقی را در نظر میگیریم و معیار توقف را مانند مثالهای قبل این قسمت در نظر میگیریم. اولیه را بصورت تصادفی انتخاب میکنیم و مقادیرویژه را محاسبه میکنیم:
جدول (۵ـ۴) نتایج بدست آمده را نشان میدهد. همچنین شکل (۵-۴) منحنی همگرایی به ازای را نمایش میدهد.
جدول (۵ـ۷) عملکرد الگوریتم آرنولدی سراسری با شروع مجدد ضمنی برای ماتریس به ازای های مختلف
شکل (۵-۹) ماتریس با
۵-۵ نتیجه گیری
در این پایان نامه با معرفی روشهایی که از مفهوم و خواص زیرفضا استفاده می کنند سعی بر حل مسائل مقدارویژه ماتریسهای بزرگ داشتیم که این نوع روشها جزء روشهای تکراری تصویری هستند. خاصیت روشهای تکراری تصویری این است که ساختار ماتریس بزرگ را حفظ می کنند. یکی از این نوع روشها، روش آرنولدی سراسری بود، که با توجه به نتایج بدست آمده دریافتیم که خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد و مقادیرویژه مجزای ماتریس بزرگ همان مقادیرویژه ماتریس اصلی است. سپس برای اینکه مسئله مقادیرویژه چندگانه را حل کنیم روش آرنولدی سراسری برای حل مسائل مقدارویژهی چندگانه را بیان کردیم که در کاربرد کارا و قابل اطمینان است.
این روشها برای بدست آوردن زوجهای ویژه ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است لذا برای حل این مشکل خاصیت شروع مجدد را معرفی کردیم. در ادامه روش آرنولدی سراسری با شروع مجدد ضمنی بیان شد و با توجه به نتایج عددی حاصل از آزمایش چند نوع از ماتریسهای بزرگ دریافتیم که الگوریتم آرنولدی سراسری سرعت همگرایی یکسانی نسبت به الگوریتم آرنولدی استاندارد دارد ولی شروع مجدد مقادیر ریتز را سریعتر به مقادیرویژه همگرا می کند پس میتوان گفت روش آرنولدی سراسری با شروع مجدد ضمنی برای حل مسائل مقدارویژه ماتریسهای بزرگ کارا و قابل اعتماد است.
در آخر روش آرنولدی سراسری با شروع مجدد ضمنی با مقادیر ریتز ناخواسته را پیشنهاد کردیم که با بهره گرفتن از روش آرنولدی سراسری و این الگوریتم میتوان مسائل ویژه چندگانه را حل کرد و همچنین چندگانگی مقادیرویژه و مکانهای ویژه را تشخیص داد.
پیوست A
واژه نامه انگلیسی به فارسی
تقریب………………………………………………………………………………………………………………………………..Approximation
جواب تقریبی………………………………………………………………………………………………… Approximation solution
پایه…………………………………………………………………………………………………………………………………………………………..Basis
ماتریس مشخصه…………………………………………………………………………………………………Characteristic Matrix
ضریب……………………………………………………………………………………………………………………………………………Coefficient
مختلط……………………………………………………………………………………………………………………………………………….Complex
مولفه……………………………………………………………………………………………………………………………………………Component
محاسبه……………………………………………………………………………………………………………………………………..computation
ثابت…………………………………………………………………………………………………………………………………………………..Constant
همگرائی………………………………………………………………………………………………………………………………….Convergence
متناظر…………………………………………………………………………………………………………………………………Corresponding
تجزیه…………………………………………………………………………………………………………………………………..Decomposition
کاهش………………………………………………………………………………………………………………………………………………Deflation
وابسته……………………………………………………………………………………………………………………………………………Dependent
قابل قطری شدن…………………………………………………………………………………………………………….. Diagonalizable
قطری غالب……………………………………………………………………………………………………………Diagonally dominant
بعد…………………………………………………………………………………………………………………………………………………Dimension
روش مستقیم……………………………………………………………………………………………………………………… Direct method
خواسته شده……………………………………………………………………………………………………………………………………….Desired
مجزا…………………………………………………………………………………………………………………………………………………….Distinct
توزیع………………………………………………………………………………………………………………………………………….Distribution
فضای ویژه…………………………………………………………………………………………………………………………………. Eigenspace
مقدارویژه……………………………………………………………………………………………………………………………………..Eigenvalue
بردارویژه…………………………………………………………………………………………………………………………………….Eigenvector
درایه…………………………………………………………………………………………………………………………………………………………Entry
معادل……………………………………………………………………………………………………………………………………………Equivalent
صریح، روشن……………………………………………………………………………………………………………………………………….Explicit
خارجی……………………………………………………………………………………………………………………………………………….External
فاکتورگیری…………………………………………………………………………………………………………………………..Factorization
تعمیم یافته………………………………………………………………………………………………………………………………..Generalized
تولیدکردن………………………………………………………………………………………………………………………………………..Generate
سراسری………………………………………………………………………………………………………………………………………………..Global
بزرگترین……………………………………………………………………………………………………………………………………………Greatest
هرمیتی…………………………………………………………………………………………………………………………………………..Hermitian
ضمنی………………………………………………………………………………………………………………………………………………….Implicit
بردار مستقل……………………………………………………………………………………………………………….Independent vector
ضرب داخلی…………………………………………………………………………………………………………………………..Inner-product
اولیه……………………………………………………………………………………………………………………………………………………….Initial
بازه………………………………………………………………………………………………………………………………………………………Interval
بررسی کردن………………………………………………………………………………………………………………………………Investigate
تکرار…………………………………………………………………………………………………………………………………………………..Iteration
مستقل خطی…………………………………………………………………………………………………………..Linear independent
چندگانه………………………………………………………………………………………………………………………………..
|
[جمعه 1400-07-30] [ 07:43:00 ب.ظ ]
|
