چکیدهروشهای سراسری تصویری برای حل عددی مسائل معادلات ماتریسهای بزرگ استفاده میشود، اما هنوز راهی برای حل مسائل بزرگ مقدارویژه شناخته نشده است. در این پایاننامه روش آرنولدی سراسری برای حل مسائل بزرگ مقدارویژه بیان میشود. این روش جفتهای F-ریتز[1] که برای تقریب جفت ویژه وجود دارند را محاسبه میکند.روش آرنولدی سراسری خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد و مقادیرویژه مجزای ماتریس بزرگ همان مقادیرویژه ماتریس اصلی هستند.در کاربرد؛ فرض کنید یک ماتریس قطری پذیر باشد؛ نشان داده میشود روش آرنولدی سراسری میتواند مسئله مقدارویژه چندگانه را حل کند همچنین الگوریتم آرنولدی سراسری با شروع مجدد ضمنی همراه با انتقالهای F پیشنهاد شده را گسترش میدهیم. که این الگوریتم برای حل مسائل جفت ویژه چندگانه استفاده میشود. آزمایشهای عددی نشان میدهد که این الگوریتم برای مسائل ویژه کارا است. فهرست مطالبمقدمه. 1فصل 1 تعاریف و مفاهیم پایه. 31-1 تعریف تعامد مجموعه. 31-2 انواع ماتریس ها. 31-3 چند جملهای مشخصه،بردارویژه ،مقدارویژه. 51-4 نرمهای یک ماتریس. 61-5 تجزیه و .. 71-6 فضاهای ضرب داخلی. 71-6-1 زیر فضای کرایلف. 87-1 الگوریتم متعامدسازی گرام اشمیت. 91-7-1 الگوریتم گرام اشمیت. 91-7-2 الگوریتم گرام اشمیت اصلاح شده. 9فصل 2روشهای زیر فضای کرایلف برای حل مسائل مقدار ویژه. 122-1 مقدمه. 122ـ2 زیرفضای کرایلف. 122ـ3 فرآیند آرنولدی. 132-3-1 الگوریتم آرنولدی. 132-3-2 الگوریتم آرنولدی اصلاح شده گرام اشمیت. 162ـ4 روش هرمیتی لنگزوس. 202-4-1 الگوریتم لنگزوس. 212ـ5 روش ناهرمیتی لنگزوس. 222-5-1 الگوریتم ناهرمیتی لنگزوس. 232-5-2 نحوه محاسبه مقادیر ویژه و بردارهای ویژه در روش ناهرمیتی لنگزوس. 262-6 الگوریتم آرنولدی با شروع مجدد. 262-6 -1 الگوریتم تکرار آرنولدی - مرحله. 272-7 شروع مجدد ضمنی. 292-7 -1 الگوریتم مراحل ضمنی بروی ماتریس ... 292-7-2 الگوریتم شروع مجدد ضمنی آرنولدی(IRA). 31فصل 3 روش آرنولدی سراسری برای مسئله مقدارویژه ماتریس غیرهرمیتی بزرگ. 343- 1 مقدمه. 343-2 تعاریف پایه مربوط به فرآیند آرنولدی سراسری. 363-3 فرآیند آرنولدی سراسری ، FOM سراسری و GMRES سراسری. 383-4 روش آرنولدی سراسری برای حل مسئلهی مقدارویژه. 443-4-1 الگوریتم آرنولدی سراسری با شروع مجدد(الگوریتم2) 513-5 مسائل مقادیرویژه چندگانه. 523-5-1 الگوریتم آرنولدی سراسری برای مسائل مقدارویژه چندگانه 56فصل4 فرآیند آرنولدی سراسری باشروع مجدد ضمنی. 594-1 مقدمه. 594-2 الگوریتم آرنولدی سراسری باشروع مجدد ضمنی. 594-2-1 الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) با انتقالهای دقیق. 624-2-2 الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) برای مسائل مقدارویژه چندگانه. 62فصل 5 نتایج عددی. 655- 1 مقدمه. 655-2 بررسی روش آرنولدی سراسری پایه. 665-3 بررسی روش آرنولدی سراسری برای مسائل مقدارویژه چندگانه 695-4 بررسی روش آرنولدی سراسری با شروع مجدد ضمنی برای مسائل غیرهرمیتی بزرگ. 705-5 نتیجه گیری. 77واژه نامه انگلیسی به فارسی. 78واژه نامه فارسی به انگلیسی. 82منابع و مآخذ. 86 مقدمهاز مسائل مهمی که همواره در جبرخطی مورد بحث است مبحث مقادیرویژه و بردارهای ویژه است. تاکنون روشهای عددی زیادی برای پیداکردن آنها ابداع شده است، اما همگی آنها پاسخگوی نیاز علوم مختلف نیستند. به طور مثال، در شیمی کوانتوم برای پیدا کردن انرژی مولکولی احتیاج به پیدا کردن زوجهای ویژه ماتریسهای با مرتبه بالا میباشد، که روشهای متداول عملا بیاستفاده هستند، علاوه بر آن از آنجا که حل مسائل مقدارویژه ماتریسهای بزرگ با استفاده از روشهای مستقیم، حافظه و محاسبات زیادی لازم دارند و ساختار ماتریس را حفظ نمیکنند. لذا برای ماتریسهای بزرگ مناسب نیستند، در حالی که روشهای تصویری تکراری ساختار ماتریس را حفظ میکنند. بدین صورت که با کوچک کردن ابعاد ماتریس، ماتریس خیلی بزرگ را به ماتریسی متشابه تبدیل میکند که زوجهای ویژه آن نزدیک به ماتریس اولیه است. لذا در این پایاننامه با معرفی روشهایی که از مفهوم و خواص زیرفضاها استفاده میکنند و همچنین با استفاده ازخاصیت شروع مجدد ضمنی، الگوریتم آرنولدی با شروع مجدد را تعریف میکنیم. برای بدست آوردن زوجهای ویژه ماتریسهای بزرگ، روش آرنولدی سراسری [2]پیشنهاد میشود که برای ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است. لذا با معرفی طرح شروع مجدد سعی بر حل این مشکل داریم. در فصل اول تعاریفی از ماتریسها و زیرفضاها آورده می شود سپس در فصل دوم، مروری بر روشهای زیرفضای کرایلف نموده و همچنین طرح شروع مجدد ضمنی معرفی میشود. در فصل سوم، توضیح مختصری از فرآیندهای آرنولدی سراسری ، الگوریتمهای FOM سراسری و GMRES سراسری داریم. در قسمت بعد از این فصل روش آرنولدی سراسری برای مسائل ویژه نامتقارن بزرگ پیشنهاد میشود سپس راه حل بدست آوردن زوجهای ویژه برای ماتریس با ابعاد بزرگ توضیح داده میشود و همچنین چگونگی استفاده از روش آرنولدی سراسری برای حل مسائل ویژه چندگانه بیان میشود. استفاده از طرح شروع مجدد، برای هنگامیکه این روش زوجهای ویژه تقریبی را برای ابعاد بالا بدست نیاورد، ضروری است. لذا در این پایاننامه الگوریتم آرنولدی سراسری با شروع مجدد تعریف میشود. در بخش بعد روش شروع مجدد ضمنی، به الگوریتم سراسری با شروع مجدد ضمنی با مقادیر F-ریتز ناخواسته پیشرفت داده میشود. در پایان الگوریتم آرنولدی سراسری با شروع مجدد ضمنی، با انتقالهای پیشنهادشدهی دقیق همراه میشود. در فصل آخر مثالهای عددی و میزان کارایی الگوریتمها گزارش داده میشوند. فصل اول تعاریف ومفاهیم پایهدر این فصل، به بیان و یادآوری بعضی تعاریف و مفاهیمی که در فصول بعد مورد استفاده قرار میگیرند، پرداخته میشوند.یک مجموعه از بردارهای در ، متعامد یکه است اگر برای هر داشته باشیم : و به ازای هر i ، باشد .ماتریس هرمیتیماتریس مربعی هرمیتی است هرگاه ( را ترانهادهی مزدوج ماتریس مینامیم) .ماتریس جایگشتی ماتریس مربعی غیرصفر را ماتریس جایگشتی گوییم هرگاه تنها عنصر غیرصفر در هر سطر و ستون آن یک باشد و بقیه عناصر، همگی صفر باشند. بنابراین، اگر یک جایگشت از باشد آنگاهماتریس هسنبرگی ماتریس مربعی را بالاهسنبرگی گوییم اگر برای هر داشته باشیم. درمقابل، پایین هسنبرگی است اگر برای هر داشته باشیم.ماتریس مثبت معینماتریس متقارن مثبت معین است هرگاه برای هر بردار غیرصفر داشته باشیم .ماتریس نرمال ماتریس مربعی نرمال است اگر باشد.ماتریس متعامدماتریس را یک ماتریس متعامد گویند، هرگاهخواص ماتریس متعامد: ماتریس بلوکیتعریف : فرض کنید یک ماتریس دلخواه باشد، در اینصورت یک ماتریس بلوکی نامیده میشود هرگاه، هریک از درایه هایش یک ماتریس باشد.با فرض اینکه نیز یک ماتریس بلوکی باشد و، جمع و ضرب آنها به شکل تعریف میشود.یک ماتریس قطری بلوکی یک ماتریس بلوکی است که هریک از بلوکهای قطری آن یک ماتریس مربعی بوده و دیگر عناصرش صفر باشند.اگر یک ماتریس باشد آنگاه چندجملهای چندجملهای مشخصه نامیده میشود.صفرهای چندجملهای مشخصه،مقادیر ویژهی ماتریس نامیده میشود. مقدار ویژه است اگر و فقط اگر یک بردار ناصفر وجود داشته باشد به طوری که . بردار را بردار ویژه(بردار ویژه راست) می گوییم. مجموعهی تمام مقادیر ویژهی ماتریس را طیف ماتریس نامیده و با نشان میدهند و نیز شعاع طیفی ماتریس را با نشان داده که عبارت است از : در ادامه به تعریف چندجملهای مونیک و چندجملهای مینیمال میپردازیم.چند جملهای مونیکچندجملهای که ضریب بزرگترین درجه آن برابر یک است چندجملهای مونیک نامیده میشود. مثلاًچندجملهای مینیمالچندجملهای مونیک با کمترین درجه که ماتریس آن را برابر ماتریس صفر کند چندجملهای مینیمال ماتریس نامیده میشود. محاسبهی چندجملهای مینیمال فصل را با معرفی نرم ماتریس ادامه میدهیم.اگر ماتریس باشد آنگاه نرم ماتریس با همراه با خواص زیر تعریف میشود.حال به تعریف چند نرم شناخته شده میپردازیم.نرم خطی (نرم یک),نرم بینهایت (ماکسیمم)نرم بینهایت ماتریس با نمایش داده و بصورت زیر تعریف میشود:نرم فروبنیوسنرم فروبنیوس ماتریس را با نمایش داده و بصورت زیر تعریف میشود: در ادامه به تعریف دو نوع تجزیه یک ماتریس میپردازیم.الف- فرض کنید یک ماتریس باشد، آنگاه یک ماتریس متعامد و یک ماتریس بالا مثلثی وجود دارد به طوری که ، که در آن ماتریس به فرم میباشد و ها هریک ماتریس هاوسهولدر میباشند.ب- فرض کنید یک ماتریس باشد، تجزیه ماتریس عبارت است از تبدیل ماتریس ضرایب به حاصل ضرب دو ماتریس و ، که در آن یک ماتریس پایین مثلثی و یک ماتریس بالامثلثی واحد است (یک ماتریس بالامثلثی که همه عناصر روی قطر اصلی آن یک هستند).
روش های تصویری عمومی برای مسائل بزرگ مقدارویژه غیر هرمیتی WORD
چکیدهروشهای سراسری تصویری برای حل عددی مسائل معادلات ماتریسهای بزرگ استفاده میشود، اما هنوز راهی برای حل مسائل بزرگ مقدارویژه شناخته نشده است. در این پایاننامه روش آرنولدی سراسری برای حل مسائل بزرگ مقدارویژه بیان میشود. این روش جفتهای F-ریتز[1] که برای تقریب جفت ویژه وجود دارند را محاسبه میکند.روش آرنولدی سراسری خاصیت همگرایی را از روش آرنولدی استاندارد به ارث میبرد و مقادیرویژه مجزای ماتریس بزرگ همان مقادیرویژه ماتریس اصلی هستند.در کاربرد؛ فرض کنید یک ماتریس قطری پذیر باشد؛ نشان داده میشود روش آرنولدی سراسری میتواند مسئله مقدارویژه چندگانه را حل کند همچنین الگوریتم آرنولدی سراسری با شروع مجدد ضمنی همراه با انتقالهای F پیشنهاد شده را گسترش میدهیم. که این الگوریتم برای حل مسائل جفت ویژه چندگانه استفاده میشود. آزمایشهای عددی نشان میدهد که این الگوریتم برای مسائل ویژه کارا است. فهرست مطالبمقدمه. 1فصل 1 تعاریف و مفاهیم پایه. 31-1 تعریف تعامد مجموعه. 31-2 انواع ماتریس ها. 31-3 چند جملهای مشخصه،بردارویژه ،مقدارویژه. 51-4 نرمهای یک ماتریس. 61-5 تجزیه و .. 71-6 فضاهای ضرب داخلی. 71-6-1 زیر فضای کرایلف. 87-1 الگوریتم متعامدسازی گرام اشمیت. 91-7-1 الگوریتم گرام اشمیت. 91-7-2 الگوریتم گرام اشمیت اصلاح شده. 9فصل 2روشهای زیر فضای کرایلف برای حل مسائل مقدار ویژه. 122-1 مقدمه. 122ـ2 زیرفضای کرایلف. 122ـ3 فرآیند آرنولدی. 132-3-1 الگوریتم آرنولدی. 132-3-2 الگوریتم آرنولدی اصلاح شده گرام اشمیت. 162ـ4 روش هرمیتی لنگزوس. 202-4-1 الگوریتم لنگزوس. 212ـ5 روش ناهرمیتی لنگزوس. 222-5-1 الگوریتم ناهرمیتی لنگزوس. 232-5-2 نحوه محاسبه مقادیر ویژه و بردارهای ویژه در روش ناهرمیتی لنگزوس. 262-6 الگوریتم آرنولدی با شروع مجدد. 262-6 -1 الگوریتم تکرار آرنولدی - مرحله. 272-7 شروع مجدد ضمنی. 292-7 -1 الگوریتم مراحل ضمنی بروی ماتریس ... 292-7-2 الگوریتم شروع مجدد ضمنی آرنولدی(IRA). 31فصل 3 روش آرنولدی سراسری برای مسئله مقدارویژه ماتریس غیرهرمیتی بزرگ. 343- 1 مقدمه. 343-2 تعاریف پایه مربوط به فرآیند آرنولدی سراسری. 363-3 فرآیند آرنولدی سراسری ، FOM سراسری و GMRES سراسری. 383-4 روش آرنولدی سراسری برای حل مسئلهی مقدارویژه. 443-4-1 الگوریتم آرنولدی سراسری با شروع مجدد(الگوریتم2) 513-5 مسائل مقادیرویژه چندگانه. 523-5-1 الگوریتم آرنولدی سراسری برای مسائل مقدارویژه چندگانه 56فصل4 فرآیند آرنولدی سراسری باشروع مجدد ضمنی. 594-1 مقدمه. 594-2 الگوریتم آرنولدی سراسری باشروع مجدد ضمنی. 594-2-1 الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) با انتقالهای دقیق. 624-2-2 الگوریتم آرنولدی سراسری با شروع مجدد ضمنی(IRGA) برای مسائل مقدارویژه چندگانه. 62فصل 5 نتایج عددی. 655- 1 مقدمه. 655-2 بررسی روش آرنولدی سراسری پایه. 665-3 بررسی روش آرنولدی سراسری برای مسائل مقدارویژه چندگانه 695-4 بررسی روش آرنولدی سراسری با شروع مجدد ضمنی برای مسائل غیرهرمیتی بزرگ. 705-5 نتیجه گیری. 77واژه نامه انگلیسی به فارسی. 78واژه نامه فارسی به انگلیسی. 82منابع و مآخذ. 86 مقدمهاز مسائل مهمی که همواره در جبرخطی مورد بحث است مبحث مقادیرویژه و بردارهای ویژه است. تاکنون روشهای عددی زیادی برای پیداکردن آنها ابداع شده است، اما همگی آنها پاسخگوی نیاز علوم مختلف نیستند. به طور مثال، در شیمی کوانتوم برای پیدا کردن انرژی مولکولی احتیاج به پیدا کردن زوجهای ویژه ماتریسهای با مرتبه بالا میباشد، که روشهای متداول عملا بیاستفاده هستند، علاوه بر آن از آنجا که حل مسائل مقدارویژه ماتریسهای بزرگ با استفاده از روشهای مستقیم، حافظه و محاسبات زیادی لازم دارند و ساختار ماتریس را حفظ نمیکنند. لذا برای ماتریسهای بزرگ مناسب نیستند، در حالی که روشهای تصویری تکراری ساختار ماتریس را حفظ میکنند. بدین صورت که با کوچک کردن ابعاد ماتریس، ماتریس خیلی بزرگ را به ماتریسی متشابه تبدیل میکند که زوجهای ویژه آن نزدیک به ماتریس اولیه است. لذا در این پایاننامه با معرفی روشهایی که از مفهوم و خواص زیرفضاها استفاده میکنند و همچنین با استفاده ازخاصیت شروع مجدد ضمنی، الگوریتم آرنولدی با شروع مجدد را تعریف میکنیم. برای بدست آوردن زوجهای ویژه ماتریسهای بزرگ، روش آرنولدی سراسری [2]پیشنهاد میشود که برای ماتریس با ابعاد بالا روشی پرهزینه در حافظه و محاسبات است. لذا با معرفی طرح شروع مجدد سعی بر حل این مشکل داریم. در فصل اول تعاریفی از ماتریسها و زیرفضاها آورده می شود سپس در فصل دوم، مروری بر روشهای زیرفضای کرایلف نموده و همچنین طرح شروع مجدد ضمنی معرفی میشود. در فصل سوم، توضیح مختصری از فرآیندهای آرنولدی سراسری ، الگوریتمهای FOM سراسری و GMRES سراسری داریم. در قسمت بعد از این فصل روش آرنولدی سراسری برای مسائل ویژه نامتقارن بزرگ پیشنهاد میشود سپس راه حل بدست آوردن زوجهای ویژه برای ماتریس با ابعاد بزرگ توضیح داده میشود و همچنین چگونگی استفاده از روش آرنولدی سراسری برای حل مسائل ویژه چندگانه بیان میشود. استفاده از طرح شروع مجدد، برای هنگامیکه این روش زوجهای ویژه تقریبی را برای ابعاد بالا بدست نیاورد، ضروری است. لذا در این پایاننامه الگوریتم آرنولدی سراسری با شروع مجدد تعریف میشود. در بخش بعد روش شروع مجدد ضمنی، به الگوریتم سراسری با شروع مجدد ضمنی با مقادیر F-ریتز ناخواسته پیشرفت داده میشود. در پایان الگوریتم آرنولدی سراسری با شروع مجدد ضمنی، با انتقالهای پیشنهادشدهی دقیق همراه میشود. در فصل آخر مثالهای عددی و میزان کارایی الگوریتمها گزارش داده میشوند. فصل اول تعاریف ومفاهیم پایهدر این فصل، به بیان و یادآوری بعضی تعاریف و مفاهیمی که در فصول بعد مورد استفاده قرار میگیرند، پرداخته میشوند.یک مجموعه از بردارهای در ، متعامد یکه است اگر برای هر داشته باشیم : و به ازای هر i ، باشد .ماتریس هرمیتیماتریس مربعی هرمیتی است هرگاه ( را ترانهادهی مزدوج ماتریس مینامیم) .ماتریس جایگشتی ماتریس مربعی غیرصفر را ماتریس جایگشتی گوییم هرگاه تنها عنصر غیرصفر در هر سطر و ستون آن یک باشد و بقیه عناصر، همگی صفر باشند. بنابراین، اگر یک جایگشت از باشد آنگاهماتریس هسنبرگی ماتریس مربعی را بالاهسنبرگی گوییم اگر برای هر داشته باشیم. درمقابل، پایین هسنبرگی است اگر برای هر داشته باشیم.ماتریس مثبت معینماتریس متقارن مثبت معین است هرگاه برای هر بردار غیرصفر داشته باشیم .ماتریس نرمال ماتریس مربعی نرمال است اگر باشد.ماتریس متعامدماتریس را یک ماتریس متعامد گویند، هرگاهخواص ماتریس متعامد: ماتریس بلوکیتعریف : فرض کنید یک ماتریس دلخواه باشد، در اینصورت یک ماتریس بلوکی نامیده میشود هرگاه، هریک از درایه هایش یک ماتریس باشد.با فرض اینکه نیز یک ماتریس بلوکی باشد و، جمع و ضرب آنها به شکل تعریف میشود.یک ماتریس قطری بلوکی یک ماتریس بلوکی است که هریک از بلوکهای قطری آن یک ماتریس مربعی بوده و دیگر عناصرش صفر باشند.اگر یک ماتریس باشد آنگاه چندجملهای چندجملهای مشخصه نامیده میشود.صفرهای چندجملهای مشخصه،مقادیر ویژهی ماتریس نامیده میشود. مقدار ویژه است اگر و فقط اگر یک بردار ناصفر وجود داشته باشد به طوری که . بردار را بردار ویژه(بردار ویژه راست) می گوییم. مجموعهی تمام مقادیر ویژهی ماتریس را طیف ماتریس نامیده و با نشان میدهند و نیز شعاع طیفی ماتریس را با نشان داده که عبارت است از : در ادامه به تعریف چندجملهای مونیک و چندجملهای مینیمال میپردازیم.چند جملهای مونیکچندجملهای که ضریب بزرگترین درجه آن برابر یک است چندجملهای مونیک نامیده میشود. مثلاًچندجملهای مینیمالچندجملهای مونیک با کمترین درجه که ماتریس آن را برابر ماتریس صفر کند چندجملهای مینیمال ماتریس نامیده میشود. محاسبهی چندجملهای مینیمال فصل را با معرفی نرم ماتریس ادامه میدهیم.اگر ماتریس باشد آنگاه نرم ماتریس با همراه با خواص زیر تعریف میشود.حال به تعریف چند نرم شناخته شده میپردازیم.نرم خطی (نرم یک),نرم بینهایت (ماکسیمم)نرم بینهایت ماتریس با نمایش داده و بصورت زیر تعریف میشود:نرم فروبنیوسنرم فروبنیوس ماتریس را با نمایش داده و بصورت زیر تعریف میشود: در ادامه به تعریف دو نوع تجزیه یک ماتریس میپردازیم.الف- فرض کنید یک ماتریس باشد، آنگاه یک ماتریس متعامد و یک ماتریس بالا مثلثی وجود دارد به طوری که ، که در آن ماتریس به فرم میباشد و ها هریک ماتریس هاوسهولدر میباشند.ب- فرض کنید یک ماتریس باشد، تجزیه ماتریس عبارت است از تبدیل ماتریس ضرایب به حاصل ضرب دو ماتریس و ، که در آن یک ماتریس پایین مثلثی و یک ماتریس بالامثلثی واحد است (یک ماتریس بالامثلثی که همه عناصر روی قطر اصلی آن یک هستند).