چکیده
حل مساله کمترین مربعات وزندار به صورت از طریق روش تجزیه قائم کامل موردنظر است.در عمل ماتریس وزنها میتواند بسیار بدحالت باشد و در نتیجه روشهای متداول، ممکن است جوابهای نادقیق بدست بدهند.استوار و تاد یک نرم کراندار را برای مساله کمترین مربعات وزندار برقرار کردند که مستقل از ماتریس وزن D است.واوازیز یک زوش پایدار (NSH) را بر اساس نرم کراندارد برقرار کرد.جواب محاسبه شده بوسیله الگوریتم پایدار فوق یک کران دقیق را که مستقل از ماتریس وزن بدحالت D است، برقرار کرد.تحلیل خطای پیشرو نشان میدهد که الگوریتم COD در این حالت پایدار است، اما این الگوریتم نسبت به الگوریتم NSH که بوسیله واوازیز بررسی شد، سادهتر است.
پیشگفتار
حل مساله کمترین مربعات وزندار به صورت
از طریق روشهای مستقیم با توجه به فرضهای زیر موردنظر است:
1. ماتریس دارای رتبه ستونی کامل باشد.
2. ماتریس متقارن معین مثبت و قطری حقیقی باشد.
3. ماتریس بسیار بدحالت باشد.
همچنین دستگاه خطی مربعی به صورت
را یک دستگاه تعادلی گویند، که با توجه به فرضهای فوق با مساله کمترین مربعات بالا در بدست آوردن جواب y معادل است.
این دستگاه کاربردهای زیادی دارد.در سال 1988 استرنگ برخی از کاربردهای آن را در زمینههای بهینهسازی، المانهای متناهی و شبکههای الکتریکی مشاهده کرد و به این نتیجه رسید که در اکثر موارد ماتریس وزن D برای آنها بسیار بدحالت میشدند.این موجب شد که یک سال بعد استوارت یک نرم کراندار را برای دستگاههای تعادلی فوق برقرار کند.این حرکتی شد برای واوایز که در سال 1994 روش پایدار NSH را برای دستگاههای تعادلی فوق تحت نتایج تعریف شده استوار بوجود آورد.از آن پس روش NSH به عنوان یکی از روشهای مفید برای دستگاههای تعادلی که ماتریس وزن D آنها بسیار بدحالت بودند، مورد استفاده قرار گرفت.
نشان داده شد که کران بالای جواب این روش مستقل از D و عدد حالت D است.این مزیتی برای روش NSH محسوب میشود، زیرا روشهای قبلی فاقد چنین کرانی بودند.
بالاخره در سال 1997 هاگ و واوازیز، روش پایدار دیگری را تحت نتایج تعریف شده استوارت بوجود آوردند که به روی COD موسوم شد.
این روش هم از لحاظ کارایی، و هم از نظر سادگی تکنیکهای استاندارد بکار گرفته شده و هم به خاطر دارا بودن یک آزمون برای وابستگی سطرهای ماتریس A در مقابل وزنهایشان، به عنوان روشی بسیار مفید برای حل اینگونه مسائل مورد استفاده قرار گرفت.
این رساله به صورت زیر سازماندهی میشود:
1. در فصل اول مقدماتی از جبر خطی عددی را بررسی خواهیم کرد که شامل نمادها و الگوریتمهای پایهای، آنالیز ماتریس، آنالیز خطا، تجزیه ماتریس و دستگاههای خطی میباشد.
2. در فصل دوم حل مساله کمترین مربعات وزندار را با استفاده از روشهای دستگاه معادلات نرمال، تجزیه QR و SVD از نظر عددی و پایداری بررسی خواهیم کرد.
3. در فصل سوم دستگاههای تعادلی و حل مساله کمترین مربعات وزندار را با استفاده از الگوریتمهای مربوط به این دستگاه (روشهای فضای پوچ و NSH)، از نظر عددی و پایداری مورد تحلیل قرار خواهیم داد.
4. در فصل چهارم حل مساله را با استفاده از تجزیه قائم کامل COD از نظر عددی و پایداری بررسی خواهیم کرد.
5. در فصل پنجم الگوریتمهای فوق را از نظر عددی، پایداری و کارایی مورد مقایسه قرار میدهیم.الگوریتمها را با استفاده از Matlab پیادهسازی میکنیم و مورد آزمون قرار میدهیم.
فصل اول
مقدمات
در فصل حاضر سعی بر این است که مقدمات لازم را برای فصول آینده جمعآوری کنیم.این فصل شامل پنج بخش به صورت زیر است.بخش اول، به یادآوری و بررسی مختصری از نمادها و الگوریتمهای پایهای از جمله: بردار، ماتریس، ضرب داخلی دو بردار، ضرب ماتریس با بردار، ضرب ماتریس با ماتریس و همچنین ماتریسهای متعامد و خواص آنها و....میپردازد.بخش دوم، به بررسی مختصری از آنالیز ماتریس از جمله فضای برد و پوچ و روشهای محاسبه ماتریس پایه برای این فضاها و همچنین نرمهای برداری و ماتریسی و خواص آنها میپردازیم.بخش سوم، بررسی آنالیز خطا از جمله تعریفی از سیستم نقطه شناور و نمایش اعداد حقیقی و ماتریس و تحلیل خطا و عملیات پایهای مربوط به آنها را در این سیستم و همچنین تحلیل الگوریتم از لحاظ پایداری و ناپایداری را شامل میشود.بخش چهارم، به بررسی اجمالی در مورد تجزیههای چولسکی، QR، SVD یک ماتریس و الگوریتمهای مربوط به آن میپردازد.بخش پنجم، مختصری در مورد تعریف و حالت و حل روشهای مختلف دستگاههای خطی را بررسی میکند.