ابعاد ماتریس، ماتریس خیلی بزرگ را به ماتریسی متشابه تبدیل می کند که زوجهای ویژه آن نزدیک به ماتریس اولیه است. لذا در این پایان نامه با معرفی روشهایی که از مفهوم و خواص زیرفضاها استفاده می کنند و همچنین با استفاده ازخاصیت شروع مجدد ضمنی، الگوریتم آرنولدی با شروع مجدد را تعریف میکنیم. برای بدست آوردن زوجهای ویژه ماتریسهای بزرگ، روش آرنولدی سراسری [۲]پیشنهاد می شود که برای ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است. لذا با معرفی طرح شروع مجدد سعی بر حل این مشکل داریم. در فصل اول تعاریفی از ماتریسها و زیرفضاها آورده می شود سپس در فصل دوم، مروری بر روشهای زیرفضای کرایلف نموده و همچنین طرح شروع مجدد ضمنی معرفی می شود. در فصل سوم، توضیح مختصری از فرآیندهای آرنولدی سراسری ، الگوریتمهای FOM سراسری و GMRES سراسری داریم. در قسمت بعد از این فصل روش آرنولدی سراسری برای مسائل ویژه نامتقارن بزرگ پیشنهاد می شود سپس راه حل بدست آوردن زوجهای ویژه برای ماتریس با ابعاد بزرگ توضیح داده می شود و همچنین چگونگی استفاده از روش آرنولدی سراسری برای حل مسائل ویژه چندگانه بیان می شود. استفاده از طرح شروع مجدد، برای هنگامیکه این روش زوجهای ویژه تقریبی را برای ابعاد بالا بدست نیاورد، ضروری است. لذا در این پایان نامه الگوریتم آرنولدی سراسری با شروع مجدد تعریف می شود. در بخش بعد روش شروع مجدد ضمنی، به الگوریتم سراسری با شروع مجدد ضمنی با مقادیر F-ریتز ناخواسته پیشرفت داده می شود. در پایان الگوریتم آرنولدی سراسری با شروع مجدد ضمنی، با انتقالهای پیشنهادشده دقیق همراه می شود. در فصل آخر مثالهای عددی و میزان کارایی الگوریتمها گزارش داده میشوند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
فصل اول
تعاریف
و
مفاهیم پایه
فصل ۱ تعاریف و مفاهیم پایه
در این فصل، به بیان و یادآوری بعضی تعاریف و مفاهیمی که در فصول بعد مورد استفاده قرار میگیرند، پرداخته میشوند.
۱-۱ تعریف تعامد مجموعه
یک مجموعه از بردارهای در ، متعامد یکه است اگر برای هر داشته باشیم : و به ازای هر 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ضرب داخلی
