ابعاد ماتریس، ماتریس خیلی بزرگ را به ماتریسی متشابه تبدیل می­ کند که زوج­های ویژه آن نزدیک به ماتریس اولیه است. لذا در این پایان نامه با معرفی روش­هایی که از مفهوم و خواص زیرفضاها استفاده می­ کنند و همچنین با استفاده ازخاصیت شروع مجدد ضمنی، الگوریتم آرنولدی با شروع مجدد را تعریف می­کنیم. برای بدست آوردن زوج­های ویژه ماتریس­های بزرگ، روش آرنولدی سراسری ^[۲]پیشنهاد می­ شود که برای ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است. لذا با معرفی طرح شروع مجدد سعی بر حل این مشکل داریم. در فصل اول تعاریفی از ماتریس­ها و زیرفضاها آورده می شود سپس در فصل دوم، مروری بر روش­های زیرفضای کرایلف نموده و همچنین طرح شروع مجدد ضمنی معرفی می­ شود. در فصل سوم، توضیح مختصری از فرآیندهای آرنولدی سراسری ، الگوریتم­های 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ضرب داخلی