دانلود تحقیق حل مساله کمترین مربعات وزندار با استفاده از تجزیه قائم کامل

چکیده
حل مساله کمترین مربعات وزندار به صورت از طریق روش تجزیه قائم کامل موردنظر است‌.‌در عمل ماتریس وزن‌ها می‌تواند بسیار بدحالت باشد و در نتیجه روش‌های متداول، ممکن است جواب‌های نادقیق بدست بدهند‌.‌استوار و تاد یک نرم‌ کراندار را برای مساله کمترین مربعات وزندار برقرار کردند که مستقل از ماتریس وزن D است‌.‌واوازیز یک زوش پایدار (NSH) را بر اساس نرم کراندارد برقرار کرد‌.‌جواب محاسبه شده بوسیله الگوریتم پایدار فوق یک کران دقیق را که مستقل از ماتریس وزن بدحالت D است، برقرار کرد‌.‌تحلیل خطای پیشرو نشان می‌دهد که الگوریتم COD در این حالت پایدار است، اما این الگوریتم نسبت به الگوریتم NSH که بوسیله واوازیز بررسی شد، ساده‌تر است.

پیشگفتار
حل مساله کمترین مربعات وزندار به صورت

از طریق روش‌های مستقیم با توجه به فرض‌های زیر موردنظر است:
1.

ماتریس دارای رتبه ستونی کامل باشد.

2.

ماتریس متقارن معین مثبت و قطری حقیقی باشد.

3.

ماتریس بسیار بدحالت باشد.

همچنین دستگاه خطی مربعی به صورت

را یک دستگاه تعادلی گویند، که با توجه به فرض‌های فوق با مساله کمترین مربعات بالا در بدست آوردن جواب y معادل است.

این دستگاه کاربردهای زیادی دارد‌.‌در سال 1988 استرنگ برخی از کاربردهای آن را در زمینه‌های بهینه‌سازی، المان‌های متناهی و شبکه‌های الکتریکی مشاهده کرد و به این نتیجه رسید که در اکثر موارد ماتریس وزن D برای آنها بسیار بدحالت می‌شدند‌.‌این موجب شد که یک سال بعد استوارت یک نرم کراندار را برای دستگاه‌های تعادلی فوق برقرار کند‌.‌این حرکتی شد برای واوایز که در سال 1994 روش پایدار NSH را برای دستگاه‌های تعادلی فوق تحت نتایج تعریف شده استوار بوجود آورد‌.‌از آن پس روش NSH به عنوان یکی از روش‌های مفید برای دستگاه‌های تعادلی که ماتریس وزن D آنها بسیار بدحالت بودند، مورد استفاده قرار گرفت‌.‌
نشان داده شد که کران بالای جواب این روش مستقل از D و عدد حالت D است‌.‌این مزیتی برای روش NSH محسوب می‌شود، زیرا روش‌های قبلی فاقد چنین کرانی بودند.

بالاخره در سال 1997 هاگ و واوازیز، روش پایدار دیگری را تحت نتایج تعریف شده استوارت بوجود آوردند که به روی COD موسوم شد.

این روش هم از لحاظ کارایی، و هم از نظر سادگی تکنیک‌های استاندارد بکار گرفته شده و هم به خاطر دارا بودن یک آزمون برای وابستگی سطرهای ماتریس A در مقابل وزن‌هایشان، به عنوان روشی بسیار مفید برای حل اینگونه مسائل مورد استفاده قرار گرفت.

این رساله به صورت زیر سازماندهی می‌شود:
1.

در فصل اول مقدماتی از جبر خطی عددی را بررسی خواهیم کرد که شامل نمادها و الگوریتم‌های پایه‌ای، آنالیز ماتریس، آنالیز خطا، تجزیه ماتریس و دستگاه‌های خطی می‌باشد.

در فصل دوم حل مساله کمترین مربعات وزندار را با استفاده از روش‌های دستگاه معادلات نرمال، تجزیه QR و SVD از نظر عددی و پایداری بررسی خواهیم کرد.

در فصل سوم دستگاه‌های تعادلی و حل مساله کمترین مربعات وزندار را با استفاده از الگوریتم‌های مربوط به این دستگاه (روش‌های فضای پوچ و NSH)، از نظر عددی و پایداری مورد تحلیل قرار خواهیم داد.

4.

در فصل چهارم حل مساله را با استفاده از تجزیه قائم کامل COD از نظر عددی و پایداری بررسی خواهیم کرد.

5.

در فصل پنجم الگوریتم‌های فوق را از نظر عددی، پایداری و کارایی مورد مقایسه قرار می‌دهیم‌.‌الگوریتم‌ها را با استفاده از Matlab پیاده‌سازی می‌کنیم و مورد آزمون قرار می‌دهیم.

فصل اول
مقدمات
در فصل حاضر سعی بر این است که مقدمات لازم را برای فصول آینده جمع‌آوری کنیم‌.‌این فصل شامل پنج بخش به صورت زیر است‌.‌بخش اول، به یادآوری و بررسی مختصری از نمادها و الگوریتم‌های پایه‌ای از جمله: بردار، ماتریس، ضرب داخلی دو بردار، ضرب ماتریس با بردار، ضرب ماتریس با ماتریس و همچنین ماتریس‌های متعامد و خواص آنها و‌.‌..‌.‌می‌پردازد‌.‌بخش دوم، به بررسی مختصری از آنالیز ماتریس‌ از جمله فضای برد و پوچ و روش‌های محاسبه ماتریس پایه برای این فضاها و همچنین نرم‌های برداری و ماتریسی و خواص آنها می‌پردازیم‌.‌بخش سوم، بررسی آنالیز خطا از جمله تعریفی از سیستم نقطه شناور و نمایش اعداد حقیقی و ماتریس و تحلیل خطا و عملیات پایه‌ای مربوط به آنها را در این سیستم و همچنین تحلیل الگوریتم از لحاظ پایداری و ناپایداری را شامل می‌شود‌.‌بخش چهارم، به بررسی اجمالی در مورد تجزیه‌های چولسکی، QR، SVD یک ماتریس و الگوریتم‌های مربوط به آن می‌پردازد‌.‌بخش پنجم، مختصری در مورد تعریف و حالت و حل روش‌های مختلف دستگاه‌های خطی را بررسی می‌کند.

1‌.‌1 نمادها و الگوریتم‌های پایه‌ای 1‌.‌1‌.‌1 نماد ماتریس فرض کنیم R نماذ مجموعه اعداد حقیقی باشد‌.‌در این صورت فضای تمام ماتریس‌های حقیق m×n را به صورت زیر نشان می‌دهیم: که A(i,j) درایه (i,j)ام ماتریس A می‌باشد.

1‌.‌1‌.‌2 نماد بردار اگر نماد Rn یک فضای برداری n بعدی حقیقی باشد، در این صورت هر را یک بردار می‌‌نامیم: که x(i) مولفه iام بردار x می‌باشد.

تذکر 1‌.‌1‌.‌1‌.‌هر بردار ستونی را یک ستونی n×1 و هر بردار سطری را یک ماتریس 1×n نیز می‌نامیم‌.‌ 1‌.‌1‌.‌3‌.‌نماد بلوک (زیرماتریس) فرض یک ماتریس و بردارهای صحیح باشند، به طوری که ‌.‌در این صورت A(i,j) را یک بلوک r×c می‌نامیم‌.‌هرگاه داشته باشیم: 1‌.‌1‌.‌4‌.‌نماد (:) این نماد وسیله مفید برای تعیین بردار و ماتریس می‌باشد.

1‌.‌1‌.‌5‌.‌نماد ماتریس به صورت ستونی و سطری صورت سطری و ستونی ماتریس به قرار زیر است: 1‌.‌1‌.‌6‌.‌نماد ماتریسی بلوکی ماتریس را یک ماتریس بلوکی می‌نامیم‌.‌هرگاه هر درایه از آن یک بلوک از ماتریس باشد و به صورت زیر نمایش می‌دهیم.

تعریف 1‌.‌1‌.‌1‌.‌یک جمع و ضرب پی در پی به صورت t=a+b×c را یک فلاپ گویند.

1‌.‌1‌.‌7‌.‌ضرب داخلی بردار اگر در آن صورت ضرب داخلی را به صورت زیر تعریف می‌کنیم: الگوریتم 1‌.‌1‌.‌1 (ضرب داخلی دو بردار با استفاده Matlab)‌.‌فرض کنیم در این صورت الگوریتم زیر z=xTy را محاسبه می‌کند: function z=dot(x,y) z=0 n=length(x) for i:1:n z=z+x(i)×y(i) end توجه داریم که در الگوریتم تعداد فلاپ‌های مورد نیاز برابر n است.

1‌.‌1‌.‌8‌.‌ضرب بردار با ماتریس فرض می‌کنیم در این صورت محاسبه y=Ax را می‌توان به صورت‌های زیر نوشت: (1) (2) (3) الگوریتم 1‌.‌1‌.‌2 (برای محاسبه y=Ax با بکارگیری رابطه 3 و با استفاده از Matlab)‌.‌فرض می‌کنیم به طوری که Aj بلوک ستونی jام A و n=(n1,…,nq).

function y=matvec(A,x,n) q=leght(n); [m,n]=size(A); y(1:m)=0;1=0 for j=1:q f=1+1=f+n(j)-1; w=A(:,f:1)×(f:1); y=y+w; end تعداد فلاپ‌ها در این حالت برابر mn است.

1‌.‌1‌.‌9‌.‌ضرب ماتریس با ماتریس اگر در این صورت حاصلضرب دو ماتریس را می‌توان به صورت‌های زیر نوشت: (4) (5) (6) الگوریتم 1‌.‌3‌.‌1 (برای محاسبه AB با بکارگیری صورت بلوکی (6) و با استفاده از Matlab)‌.‌فرض کنید دو ماتریس به طوری که Ai و Bi به ترتیب بلوک ستونی و سطری باشند و n(i) تعداد ستون‌های Ai و تعداد سطرهای .

function C=matmat (A, B, n) N=length(n); [m,r]=size(A)' [r,n]=size(B); C=zeros(n,m);1=0 for j=1:N f=1+1;1=f+n(i)-1 W=A(:,f:1)×B(f:1,:) end در این الگوریتم تعداد فلاپ‌ها برابر با mnr است.

1‌.‌1‌.‌10‌.‌ماتریس قطری در حالت کلی ماتریس قطری به صورت زیر نشان داده می‌شود: همچنین ضرب یک ماتریس قطری را با یک ماتریس به صورت زیر نمایش می‌دهیم: تعریف 1‌.‌1‌.‌2‌.‌ماتریس را بالا مثلثی گوییم، هرگاه برای و پایین مثلثی گوییم، هرگاه برای .

تعریف 1‌.‌1‌.‌3‌.‌ماتریس را یک ماتریس متعامد گوییم، هرگاه: در این صورت ATA=I‌.‌حال اگر m=n، آنگاه ATA=AAT=I که در این صورت، ماتریس A را متعامد نرمال و یا به اختصار نرمال گوییم.

تعریف 1‌.‌1‌.‌4‌.‌یک ماتریس جابجایی، یک ماتریس یکانی با جابجایی سطرها، با ستون‌هاست.

لم 1‌.‌1‌.‌1‌.‌فرض کنیم P2, P1, P ماتریس‌های جابجایی n×n باشند، در اینصورت روابط زیر برقرار هستند: PX همان X با جابجایی سطرها و XP همان X با جابجایی ستون‌هاست.

P-1=PT.

.

P1P2 نیز یک ماتریس جابجایی است.

1‌.‌2 آنالیز ماتریس 1‌.‌2‌.‌1‌.‌فضای برد، فضای پوچ و رتبه ماتریس برای ماتریس m×n, A زیرفضاهای برداری N(A), R(A) را به ترتیب فضای برد و فضای پوچ ماتریس A می‌نامیم و به صورت زیر تعریف می‌کنیم: زیرفضاهای N(A), R(A) به ترتیب زیرفضاهای برداری Rn, Rm هستند.

حال اگر افراز ستونی A باشد، در آن صورت و رتبه ماتریس، تعداد ستون‌ها با سطرهای مستقل خطی می‌باشد و به صورت تعریف می‌شود.

همچنین می‌توانیم نشان دهیم که و برای ماتریس روابط زیر را داریم: روابط فوق نشان می‌دهد که اگر rank(A)=n آنگاه A دارای رتبه ستونی کامل و ستون‌های آن یک پایه برای R(A) است‌.‌همچنین اگر باشد، آنگاه رتبه سطری A کامل و سطرهای آن یک پایه برای است، ولی اگر ، ماتریس A را رتبه ناقص گویند.

لم 1‌.‌2‌.‌1‌.‌روابط زیر برقرارند: زیرفضاهای مکمل متعامدند: زیرفضاهای مکمل متعامدند: لم 1‌.‌2‌.‌2‌.‌تجزیه رتبه نمای ماتریس A اگر با آنگاه می‌توان نشان داد که ماتریس‌های G، m×n و r×n, H موجودند، به طوری که: لم 1‌.‌2‌.‌3‌.‌برای با روابط زیر برقرار است: 1‌.‌2‌.‌2‌.‌ماتریس پایه برای زیرفضاها تعریف 1‌.‌2‌.‌1‌.‌یک ماتریس با ستون‌های مستقل خطی را که ستون‌هایش مولد زیرفضا باشد، یک ماتریس پایه برای زیرفضا گویند‌.‌توجه داریم که اگر آنگاه داریم: توجه: اگر n×(n-r), Z با ستون‌های مستقل خطی به گونه‌ای باشد که HZ=0 و n×r, Y با ستون‌های مستقل خطی به گونه‌ای باشد که YZ=0 آنگاه Z یک ماتریس پایه برای N(A) و Y یک ماتریس پایه برای R(AT) است‌.‌جدول زیر ماتریس‌های پایه را برای زیرفضاهای چهارگانه وابسته به ماتریس A خلاصه می‌کند.

1‌.‌2‌.‌3‌.‌نرم برداری تعریف 1‌.‌2‌.‌2‌.‌تابع را یک نرم‌برداری گویند، هرگاه دارای خواص زیر باشد: که می‌توان نشان داد که تعریف یک نرم است برای x=1 و p=2 داریم: نامساوی زیر را می‌توان اثبات کرد: (نامساوی کوشی ـ شوارتز) 1‌.‌2‌.‌4‌.‌نرم ماتریسی تعریف 1‌.‌2‌.‌3‌.‌تابع را یک نرم ماتریسی گویند هرگاه دارای خواص زیر باشد: می‌توان نشان داد که تعریف یک نرم ماتریسی است‌.‌این نرم را یک نرم ماتریسی وابسته به نرم‌برداری گویند‌.‌خواص زیر را می‌توان به اثبات رساند: در بالا ویژه مقدار iام ATA و بزرگترین مقدار تکین ماتریس A (بعداً در مورد مقادیر تکین توضیح خواهیم داد)، و نرم ||A||F نرم ماتریسی فروبینیوس با تعریف زیر است: (نرم ـ فروبینیوس) 1‌.‌3 آنالیز خطا تعریف 1‌.‌3‌.‌1‌.‌نماد معرف اعداد نقطه شناور در ماشین برای نمایش اعداد حقیقی است.

1‌.‌3‌.‌1‌.‌نمایش اعداد حقیقی نمایش اعداد حقیقی، در سیستم شناور به صورت زیر است: که برای که diها ارقام اعداد صحیح در مبنای و ‌.‌عدد صفر را به صورت نمایش می‌دهند‌.‌به این صورت نمایش اعداد، صورت نرمالیزه شده گویند.

تذکر 1‌.‌3‌.‌1‌.‌در سیستم مبنای عدد، p تعداد اعداد قابل ملاحظه در مانتیس، M بزرگترین نما، m کوچکترین نما و مقیاس سیستم است.

تذکر 1‌.‌3‌.‌2‌.‌در سیستم F، ناحیه زیرریز و سرریز به ترتیب به صورت زیر نشان داده می‌شود: تذکر 1‌.‌3‌.‌3‌.‌معمولاً در اجرای برنامه‌های کامپیوتری، اعداد واقع شده در ناحیه زیرریز به صورت تقریبی با صفر و در ناحیه سرریز، یک پیغام خطا توسط ماشین داده و اجرای برنامه متوقف می‌شود.

تذکر 1‌.‌3‌.‌4‌.‌خطای نسبی در روی گرد کردن و بریدن را به عنوان خطای روند عدد یک می‌نامند و با نشان می‌دهند‌.‌رابطه زیر برای هر عددی که در دو ناحیه سرریز یا زیر ریز واقع نشود، به صورت زیر برقرار است: که در آن fl(y) عددی است که در ماشین به جای y قرار می‌گیرد و که صورت (1) از روی گرد کردن و صورت (2) از روش بریدن بدست می‌آید.

1‌.‌3‌.‌2‌.‌عملیات سیستم نقطه شناور فرض کنیم اعداد x و y در سیستم نقطه شناور قابل نمایش باشند و به عنوان عملگر دو عملوند فوق باشد، در این صورت x op y مقدار دقیق و fl(x op y) به عنوان مقدار محاسبه شده توسط ماشین هستند‌.‌عملیات اصلی با انتقال عملوندها به ثبات‌ها (با حافظه 1+p2، برای مانیتس) و انجام عمل مربوطه در واحد محاسباتی و حفظ آن در ثبات دیگر انجام می‌شود و نهایتاً نتیجه، از ثبات نهایی به حافظه با p رقم روند می‌شود‌.‌چون خطا از رقم p به بعد ظاهر می‌شود، در نتیجه همان نتیجه قبلی برای خطا درست است و خواهیم داشت: به عبارت دیگر، داریم: تعریف 1‌.‌3‌.‌2‌.‌اگر تقریب ، آنگاه خطای مطلق (eA) و نسبی (eR) به صورت زیر تعریف می‌شوند: تذکر 1‌.‌3‌.‌5‌.‌خطای مطلق و نسبی در برخی موارد گمراه کننده هستند، یعنی اگر x خیلی بزرگ باشد، آنگاه eA می‌تواند بزرگ و اگر x خیلی کوچک باشد، آنگاه eR می‌تواند بزرگ باشد‌.‌گرچه تخمینی مناسب برای x باشد، تعریف زیر در بسیاری موارد مناسب‌تر است.

توجه داریم که در تعریف اخیر، اگر x خیلی کوچک باشد، رابطه و اگر x خیلی بزرگ باشد، رابطه را خواهیم داشت.

تعریف 1‌.‌3‌.‌3‌.‌گوییم از مرتبه ، ( توانی از عدد 10 است) هرگاه ای وجود داشته باشد، که پ و آن را با نمایش می‌دهیم 1‌.‌3‌.‌3‌.‌آنالیز الگوریتم لم 1‌.‌3‌.‌1‌.‌اگر عدد صحیح k و عدد مثبت به گونه‌ای باشد که در رابطه صدق کنند‌.‌آنگاه: یا تعریف 1‌.‌3‌.‌4‌.‌یک الگوریتم را نسبه به الگوریتم دیگر پایدارتر گویند اگر جواب‌های محاسبه شده توسط آن بر روی دسته مسائل بیشتری دارای خطای کمتری از جواب‌های محسابه شده توسط الگوریتم دیگر باشد.

تعریف 1‌.‌3‌.‌5‌.‌فرض کنیم d1, d2 داده‌های نزدیک به هم باشند و