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

چکیده
حل مساله کمترین مربعات وزندار به صورت از طریق روش تجزیه قائم کامل موردنظر است‌.‌در عمل ماتریس وزن‌ها می‌تواند بسیار بدحالت باشد و در نتیجه روش‌های متداول، ممکن است جواب‌های نادقیق بدست بدهند‌.‌استوار و تاد یک نرم‌ کراندار را برای مساله کمترین مربعات وزندار برقرار کردند که مستقل از ماتریس وزن 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 داده‌های نزدیک به هم باشند و s(d2), s(d1) جواب‌های مساله p در داده‌های فوق باشند، در این صورت عدد حالت (cond(p)) p حول d1 و d2 به صورت زیر تعریف می‌شود: تذکر 1‌.‌3‌.‌6‌.‌اگر عدد حالت بزرگ باشد، مساله بدحالت و اگر کوچک باشد، مساله خوش حالت تعریف می‌شود‌.‌ تذکر 1‌.‌3‌.‌7‌.‌برای مسائل بدحالت نمی‌توان انتظار داشت که حتی الگوریتم‌های پایدار نیز جواب خوبی به دست دهند‌.‌معمولاً برای مسائل بدحالت، جواب‌های محاسبه شده با خطاهایی فاحش همراه هستند.

لم 1‌.‌3‌.‌2‌.‌اگر در این صورت می‌توان خطای ضرب داخلی را به صورت زیر نشان داد: اگر xiها و yiها هم‌علامت باشند، آنگاه و حد بالای خطا کوچک خواهد شد‌.‌ولی اگر xiها و yiها هم‌علامت نباشند، در این صورت امکان تولید خطای زیاد موجود است، به ویژه زمانی که .

با توجه به لم بالا و همچنین لم (1‌.‌3‌.‌1) فرض می‌کنیم که ، در این صورت داریم: که c یک ثابت از مرتبه (1) است.

1‌.‌3‌.‌4 نمایش ماتریس در سیستم نقطه شناور اگر ، در این صورت نمایش ماتریس در سیستم نقطه شناور معادل با نمایش هر درایه به عنوان عدد حقیقی در سیستم نقطه شناور خواهد بود.

تعریف 1‌.‌‌3‌.‌6‌.‌‌ اگر، یک ماتریس n m باشد، آنگاه را به عنوان تقریب نقطه شناور ماتریس A می‌نامیم و به صورت زیر تعریف می‌کنیم: , تعریف 1‌.‌‌3‌.‌‌7‌.‌‌ اگر تقریب ماتریس A باشد، آنگاه خطای نسبی به صورت زیر خواهد بود: 1‌.‌‌3‌.‌‌5 تحلیل خطا برای عملیات پایه ای ماتریس در سیستم نقطه شناور]10[ اگر A و B ماتریسهای شناور باشند و یک حقیقی در این سیستم باشد، آنگاه روابط زیر برقرارند: , , , , و همچنین داریم: , , 1‌.‌‌4 تجزیه ماتریس(]4[، ]5[ و ]10[) تجزیه‌های ماتریس اساسی ذیل را در بخشهای آتی بررسی می‌کنیم: 1‌.‌‌4‌.‌‌1‌.‌‌تجزیه مقادیر تکین(SVD) 1‌.‌‌4‌.‌‌2‌.‌‌تجزیه چولسکی.

1‌.‌‌4‌.‌3‌.‌‌تجزیه QR.

1 ‌.‌‌4‌.‌‌1‌.‌‌تجزیه مقادیر تکین(SVD) قضیه 1‌.‌‌4‌.‌‌1‌.‌‌برای هر ماتریس ، ماتریسهای قائم نرمال و و ماتریس قطری یافت می‌شوند به طوری که: که بطوری که ، و ، ماتریسهای متعامدند.

تذکر1‌.‌‌4‌.‌‌1‌.‌‌در تجزیه SVD ماتریس A ، روابط و برای برقرارند، که در آن ها، مقادیر تکین و و، به ترتیب بردارهای تکین راست و چپ گفته می‌شوند.

نتایج زیر به سادگی قابل دستیابی هستند: (1 (2 (3 , , , (4 , , , (5 (6 1‌.‌4‌.‌‌1‌.‌‌1‌.‌‌وارون تعمیم یافته تعریف1‌.‌4‌.‌‌1‌.‌‌وارون تعمیم یافته یک ماتریس وارونپذیر همان وارون آن است و وارون تعمیم یافته یک ماتریس قطری ترانهاده آن ماتریس با وارون قطریهای غیر صفر می‌باشد‌.‌وارون تعمیم یافته A را با A+ نمایش می‌دهیم و با استفاده از تجزیه SVD داریم: , خواص1‌.‌‌4‌.‌‌1‌.‌(شبه وارون): , (1 , (2 , (3 (4 (5 1‌.‌4‌.‌‌2‌.‌‌تجزیه چولسکی تعریف 1‌.‌4‌.‌‌2‌.‌‌ماتریس متقارن را معین مثبت گویند هرگاه برای هر بردار n بعدی داشته باشیم: این تعریف معادل است با: همه مقادیر ویژه مثبت هستند.

همه مینورهای اصلی معین مثبت هستند.

همه بلوکهای گوشه چپ A معین مثبت هستند.

ماتریس A را می‌توان به صورت تجزیه کرد که G یک ماتریس پایین مثلثی است.

الگوریتم 1‌.‌4‌.‌‌1‌.‌(تجزیه چولسکی با استفاده از Matlab)، فرض کنیمیک ماتریس متقارن معین مثبت باشد، در اینصورت این الگوریتم یک ماتریس پایین مثلثی را محاسبه می‌کند بطوری که و برای هر ، را در قرار می‌دهد.

اجرای این الگوریتم نیاز به فلاپ دارد.

تذکر1‌.‌4‌.‌2‌.‌روش چولسکی باعث رشد نتایج محاسبه شده در روند اجرای عملیات نمی شود.

تذکر1‌.‌4‌.‌3‌.‌می‌توان نشان داد که G محاسبه شده در روش چولسکی رابطه زیر را صدق می‌دهد: ، 1‌.‌4‌.‌3‌.‌تجزیه QR 1‌.‌4‌.‌3‌.‌1‌.‌تبدیلات(ماتریس) قائم هاوس هولدر تعریف 1‌.‌4‌.‌3‌.‌1‌.‌فرض کنیم که ، در اینصورت ماتریس H به صورت زیر را یک ماتریس هاوس هولدر می‌نامند: , و بردار u را یک بردار هاوس هولدر می‌نامند.

خواص 1‌.‌4‌.‌1‌.‌(ماتریس هاوس هولدر): 1) یعنی H متقارن است.

2) یعنی H متعامد نرمال و H وارون H است.

3) (ماتریسهای متعامد تحت نرم- 2 دارای تبدیلات پایدار هستند).

4) .

5) اگرa و b به گونه ای باشند که ، آنگاه یک ماتریس هاوس هولدر(با قرار دادن به عنوان بردار هاوس هولدر) وجود دارد.به طوری که Ha=b و Hb=b.

تذکر1‌.‌4‌.‌4‌.‌اگر که ( ستون اول ماتریس همانی است)، آنگاه روابط زیر برقرارند: ، 1‌.‌4‌.‌3‌.‌2‌.‌محاسبه بردار هاوس هولدر زمانی که .

با قرار دادن نتیجه می‌گیریم که ، چون ، پس و با نرمال کردن آن نسبت به ، و این در ذخیره سازی در ماتریس A به ما کمک خواهد کرد.

الگوریتم 1‌.‌4‌.‌2‌.‌(برای محاسبه بردار هاوس هولدر با استفاده از Matlab)‌.‌فرض کنیم یک بردار دلخواه باشد، در اینصورت این تابع، یک بردار را محاسبه می‌کند به طوری که ، برداری به دست می‌دهد که همه مولفه‌های آن به جز مولفه اول، صفر هستند.

1‌.‌4‌.‌3‌.‌3‌.‌محاسبه HA و AH اگر A یک ماتریس دلخواه و H یک ماتریس هاوس هولدر باشد، در اینصورت خواهیم داشت: (1) ; ; (2) ; ; الگوریتم 1‌.‌4‌.‌3‌.‌(محاسبه HA با استفاده از Matlab)‌.‌فرض کنیم یک ماتریس دلخواه و با یک بردار هاوس هولدر باشد، در اینصورت این الگوریتم HA را محاسبه می‌کند، به طوری که یک ماتریس هاوس هولدر باشد.

الگوریتم 1‌.‌4‌.‌4‌.‌(محاسبه AH با استفاده از Matlab)‌.‌فرض کنیم یک ماتریس دلخواه و با یک بردار هاوس هولدر باشد، در اینصورت این الگوریتم AH را محاسبه می‌کند، به طوری که یک ماتریس هاوس هولدر باشد.

1‌.‌4‌.‌3‌.‌4‌.‌آنالیز خطا می توان نشان داد که بردار هاوس هولدر به واقعی خیلی نزدیک است، به طوری که اگر ، آنگاه ]10[.

و به علاوه، , , تذکر1‌.‌4‌.‌5‌.‌اگر با فرض () یک ماتریس دلخواه باشد و به طوری که H یک ماتریس هاوس هولدر باشد، در اینصورت اگر بخواهیم ماتریس B را محاسبه کنیم و در A قرار دهیم به صورت زیر عمل می‌کنیم: 1‌.‌4‌.‌3‌.‌5‌.‌محاسبه الگوریتم 1‌.‌4‌.‌5‌.‌(محاسبهQ با استفاده از Matlab)‌.‌اگر uو H به ترتیب بردار و ماتریس هاوس هولدر باشند، در اینصورت این الگوریتم را برای محاسبه می‌کند، به طوری که و .

که تعداد فلاپ مورد نیاز برابراست.

1‌.‌4‌.‌3‌.‌5‌.‌تجزیه QR هاوس هولدر]10[.

الگوریتم 1‌.‌4‌.‌6‌.‌(تجزیه QR با استفاده از Matlab)‌.‌فرض کنیم با یک ماتریس دلخواه باشد، در اینصورت این الگوریتم زیر ماتریسهای راپیدا می‌کند، به طوری که یک ماتریس متعامد و یک ماتریس بالا مثلثی می‌باشد، که در قسمت بالا مثلثی َ، قسمت بالا مثلثی R و مؤلفه‌های j+1 تاm از بردار هاوس هولدر jام را در ، که ، قرار می‌دهد.

این الگوریتم به فلاپ نیاز دارد‌.‌توجه داریم که و مقادیر محاسبه شده، به عنوان مثال برای یک ماتریس A ، به صورت زیر ذخیره می‌شوند: , 1‌.‌4‌.‌3‌.‌7‌.‌تجزیه QR هاوس هولدر با محورگیری ستونی(مسئله رتبه ناقص) یک ستون با بیشترین نرم در ماتریس باقی مانده اختیار می‌شود و با ستون پاشنه (محور) جابجا می‌شود، سپس تبدیل هاوس هولدر روی ستون پاشنه انجام می‌گیرد‌.‌این عمل را آنقدر ادامه می‌دهند‌.‌تا ستون پاشنه با بیشترین نرم در ماتریس باقی مانده برابر صفر (در عمل یک عدد کوچک) شود، بدین ترتیب داریم: که R11 ماتریس بالا مثلثی وارونپذیر است و P=P1…Pr و Q=H1…Hr به صورت حاصلضرب عوامل Hi ها (ui ها) نگهداری می‌شود‌.‌پس می‌توان نوشت: که P یک ماتریس جابجایی است.

روش محاسبه QR ماتریسهای هاوس هولدر H1,…,Hk-1 و ماتریسهای جابجایی P1,…,Pk-1 را محاسبه می‌کنیم به طوری که: که R11(k-1) یک ماتریس بالا مثلثی وارونپذیر است‌.‌حال فرض می‌کنیم که یک افراز ستونی باشد و p کوچکترین اندیس در باشد، به طوری که: , توجه می‌کنیم که اگر ، آنگاه ماکسیمم برابر صفر است و کار تمام است، در غیرر این صورت فرض می‌کنیم که Pk یک ماتریس یکانی با جابجایی ستونهایp و k و Hk یک ماتریس هاوس هولدر باشد‌.‌حال اگر ، آنگاه ‌.‌‌و از طرفی، Pk ستون با بیشترین نرم در R22(k-1) را به وضعیت ستون محور انتقال می‌دهد و مولفه زیر قطریهایش را صفر می‌کند‌.‌نرم ستونها مجدداً می‌تواند در هر مرحله محاسبه شود‌.‌برای کاهش عملیات اصلی، توجه داریم که برای هر ماتریس متعامد ، می‌توان نوشت: که و ‌.‌با استفاده از رابطه بالا ، تعداد عملیات از O(mn2) به O(mn) فلاپ کاهش می‌یابد‌.‌پس داریم: الگوریتم 1‌.‌4‌.‌7‌.‌(تجزیه QR هاوس هولدر با محور گیری ستوتی با استفاده ازMatlab).

اگرو ، آنگاه این الگوریتم r را به عنوان رتبه ماتریسA، Q=H1,…,Hr، ماتریس هاوس هولدر و P=P1,…,Pr ماتریس جابجایی را محاسبه می‌کند و در جایگذاری مجدد برای ذخیره سازی در A ، در قسمت بالا مثلثی A، قسمت بالا مثلثی R و مولفه‌های j+1:m از بردار هاوس هولدر jام را در A(j+1:m,j) قرار می‌دهد و ماتریسهای جابجایی را به صورت یک بردار صحیح p مشخص می‌کند‌.‌به طور خاص Pi ماتریس یکانی است که سطرهای j و p(j) جابجا می‌شوند‌.‌ تعداد فلاپ لازم برای محاسبه تجزیه برابر با .

تذکر1‌.‌4‌.‌6‌.‌در تجزیه QR رابطه زیر برقرار است:[10].

, , که چند جمله ای از درجه پاین برحسبn است.

تذکر 1‌.‌4‌.‌7‌.‌اگر A=QrRPT تجزیه QR با محورگیری ستونی باشد، آنگاه روابط زیر برقرارند: عدد حالت A ، در نرم اقلیدسی ، برابر است با عدد حالت R.

G=Qr و K=Qm-r به ترتیب ماتریسهای پایه برای R(A) و N(AT) می‌باشند.

1‌.‌5 دستگاه خطی ]5.[ تعریف 1‌.‌5‌.‌1‌.‌مسئله Ax=b رایک دستگاه خطی گویند، که در آن و داده ها و جواب مسئله است.

تذکر 1‌.‌5‌.‌1‌.‌اگر ، آنگاه دستگاه خطیAx=b را سازگار گویند.

تذکر 1‌.‌5‌.‌2‌.‌اگر دستگاه خطی Ax=b دارای جواب باشد، آنگاه جواب عمومی دستگاه به صورت زیر خواهد بود: ، ، 1‌.‌5‌.‌1‌.‌حالت دستگاه خطی ]4[.

1‌.‌5‌.‌1‌.‌1‌.‌اثر تغییرات در طرف راستb.

فرض کنیم با تغییر به ، جواب به تغییر یابد، در اینصورت: 1‌.‌5‌.‌1‌.‌2‌.‌اثر تغییرات در ماتریس ضرایبA.

فرض کنیم با تغییر به جواب به تغییر یابد، در اینصورت: 1‌.‌5‌.‌1‌.‌3‌.‌اثر تغییرات در طرف راستو در ماتریس ضرایب.

فرض کنیم با تغییر به ، و با تغییر به جواب به تغییر یابد، در اینصورت: تذکر 1‌.‌5‌.‌3‌.‌عدد را به عدد حالت دستگاه خطی گویند.

1‌.‌5‌.‌2‌.‌حل دستگاه خطی(]4[،]5[و]10[) 1‌.‌5‌.‌2‌.‌1‌.‌دستگاه پایین مثلثی دستگاه را که یک ماتریس پایین مثلثی است، یک دستگاه پایین مثلثی گویند.

الگویتم 1‌.‌5‌.‌1‌.‌(جایگذاری پیشرو با استفاده از Matlab)‌.‌ فرض کنیم یک ماتریس پایین مثلثی وارونپذیر و ‌.‌این الگوریتم جوابرا در قرار می‌دهد.

اجرای این الگوریتم به فلاپ نیاز دارد.

تذکر 1‌.‌5‌.‌4‌.‌فرض کنیم جواب محاسبه شده دستگاه باشد، آنگاه رابطه زیر برقرار است: , 1‌.‌5‌.‌2‌.‌2‌.‌دستگاه بالا مثلثی دستگاه را که یک ماتریس بالا مثلثی است، یک دستگاه مثلثی گویند.

الگوریتم 1‌.‌5‌.‌2‌.‌(جایگذاری پسرو با استفاده از Matlab).

فرض کنیم یک ماتریس بالا مثلثی وارونپذیر باشد و ‌.‌این الگوریتم جواب را در قرار می‌دهد.

تذکر 1‌.‌5‌.‌5‌.‌فرض کنیم جواب محاسبه شده دستگاه باشد، آنگاه رابطه زیر برقرار است: , 1‌.‌5‌.‌2‌.‌3‌.‌روش چولسکی برای حل دستگاه خطی با معین مثبت، با استفاده از تجزیه چولسکی به صورت زیر عمل می‌کنیم: , الگوریتم 1‌.‌5‌.‌3.

تجزیه چولسکی را محاسبه کن(که به ) فلاپ نیاز دارد).

دستگاه خطی پایین مثلثی را برایحل کن.

دستگاه خطی بالا مثلثی را برای حل کن.

1‌.‌5‌.‌2‌.‌4‌.‌روش(SVD).

برای حل دستگاه خطیبا ، و با استفاده از تجزیه SVD به صورت زیر عمل می‌کنیم: , , الگوریتم 1‌.‌5‌.‌4.

تجزیه SVD را برای ماتریس A محاسبه کن، به طوری که .

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

اگر ، آنگاه دستگاه ناسازگار است و متوقف شو.

دستگاه قطری را برای حل کن‌.‌( برای ) تبدیل را برای محاسبه کن.

1‌.‌5‌.‌2‌.‌5‌.‌روش QR برای حل دستگاه خطی با و با استفاده از تجزیه QR به صورت زیر عمل می‌کنیم: , الگوریتم 1‌.‌5‌.‌5.

تجزیه QR را برای ماتریس A با استفاده از محورگیری ستونی محاسبه کن: .

تبدیل ، را محاسبه کن.

دستگاه بالا مثلثی را برای حل کن.

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

این روش برای حل دستگاه به فلاپ نیاز دارد.

فصل دوم مسئله کمترین مربعات وزندار و روشهای تجزیه در این فصل به بررسی مسئله کمترین مربعات وزندار و حل آن با استفاده از ماتریسها می‌پردازیم‌.‌این فصل شامل چهار بخش به صورت زیر است؛ بخش اول و دوم به یادآوری و بررسی مختصری در مورد کمترین مربعات خطی و خواص آن می‌پردازد‌.‌بخش سوم به بررسی مسئله کمترین مربعات وزندار(که موضوع اصلی این رساله می‌باشد) می‌پردازد‌.‌بخش چهارم حل ای مسئله با استفاده از روشهای تجزیه ماتریسها از نقطه نظر عددی و پایداری مورد تحلیل قرار می‌گیرد، که برای مشاهده مطالب بیشتر می‌توان به ]4[،]5[و ]10[ مراجعه نمود.

2‌.‌1 مسئله کمترین مربعات خطی 2‌.‌1‌.‌1‌.‌تعریف سیستم‌های ناسازگار در دستگاه خطی ممکن است که ‌.‌در این حالت به دنبال ای هستیم، به طوری که به ازای همه های دیگر کمترین باشد‌.‌این مسئله موسوم به مسئله کمترین مربعات خطی است: 2‌.‌1‌.‌2‌.‌برازش داده ها(Data Fitting) به عنوان نمونه ای از کمترین مربعات خطی، برازش مدل P(x) به عنوان تابعی از x به طوری که P(x) در یک مفهوم خاص، داده‌های (ti,bi) را پیشگویی کند، مطرح شود.

بنابراین برای P به عنوان پیشگویی داده توابع پایه (براساس تجربه یا پیشنهاد کاربر) در نظر گرفته می‌شود، و هدف پیدا کردناست به طوری که مینیمم شود،که P(x)ترکیبی خطی از توابع پایه است‌.‌ تذکر2‌.‌1‌.‌1‌.‌با تعریف ماتریس A به صورت به طوری که هر ستون آن مقادیر تابع در نقاط داده شده باشد، در اینصورت مسئله را به صورت زیر داریم: تعریف 1‌.‌1‌.‌2‌.‌برای هر ، برداررا بردار مانده می‌نامیم‌.‌در واقع، در مسئله کمترین مربعات خطی به دنبال ای هستیم که نرم مانده، مینیمم شود.

تذکر2‌.‌1‌.‌2‌.‌اگر دستگاه سازگار باشد، آنگاه به عنوان جواب مسئله به دست می‌آید و در نتیجه داریم: ]5[.

2‌.‌2 خواص کمترین مربعات خطی در مسئله کمترین مربعات خطی، فرض کنید که، ‌.‌یادآوری می‌کنیم، که برای برخی ]5[‌.‌ و حال فرض کنیم، آنگاه بعد برد A برابر r و بعد پوچ AT برابر m-r می‌باشد.

2‌.‌2‌.‌1‌.‌توصیف مانده مینیمم فرض کنیم داده شده ، در اینصورت هر بردار را می‌توان به صورت یک بردار و بیان کرد، به طوری که (2‌.‌2‌.‌1.) بردارهای cR و cN یگانه هستند و برای برخی از cA ها خواهیم داشت: (2‌.‌2‌.‌2.) , , یگانگیcR و cN ایجاب می‌کند که مولفه‌های برد و پوچ بردارهای مساوی باید همچنین مساوی باشند که به صورت زیر داریم: (2‌.‌2‌.‌3.) , حال با فرض یگانگیcR ، پس بردار cA یگانه است اگر و فقط اگر ستونهای A مستقل خطی باشند]5[.

از طرفی ، چون نرم اقلیدسی با ضرب داخلی تعریف می‌شود در نتیجه یک رابطه مهم از روابط (2‌.‌2‌.‌1.) و (2‌.‌2‌.‌2.) به صورت زیر به دست می‌آید: (2‌.‌2‌.‌4.) حال مسئله کمترین مربعات خطی را به صورت زیر در نظر می‌گیریم: که و به ترتیب طرف راست و مانده مسئله هستند‌.‌صورت (1.2.2.) را می‌توان برای هر دو بردار به صورت زیر نوشت: (5.2.2.) , (6.2.2.) , با ترکیب رابطه با روابط(5.2.2.) و (6.2.2.) داریم: از طرفی، چون ، پس مولفه فضای برد برابر و مولفه پوچ آن برابر خواهد بود، و در نتیجه رابطه بالا به صورت زیر صدق می‌کند: , مسئله کمترین مربعات شامل مینیمم کردن مانده مسئله می‌شود و ممکن است و در نتیجه و ‌.‌با توجه به رابطه (4.2.2.) برای مربع نرم اقلیدسی مانده برای هرx داریم: پس روابط کلی به صورت زیر خواهد بود: , (7.2.2.) تذکر 1.2.2‌.‌دستگاه سازگار دارای جواب یگانه x است رتبه ستونی A کامل باشد‌.‌ همچنین استقلال خطی ستونهایA متناظر با استقلال خطی پایه نسبت به داده‌های (t1,…,tm) است.

2‌.‌3 مسئله کمترین مربعات وزندار 1.3.2 مسئله زیر مورد نیاز است: (1.3.2) که ، و (ماتریس وزن)، داده‌های مسئله می‌باشند‌.‌این موسوم به کمترین مربعات وزندار است]10[.

2.3.2‌.‌ مسئله کمترین مربعات وزندار (2.3.2.) را با فرضهای زیر در نظر می‌گیریم (]3[و]9[): ماتریس دارای رتبه ستونی کامل است.

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

ماتریس بسیار بد حالت است‌.‌ کاربرد مسئله فوق در بهینه سازی ]7[، شبکه‌های الکتریکی ]13[ و المانهای متناهی ]8[ است‌.‌بد حالتی D نیز از همین کاربردها ناشی می‌شود‌.‌پس ماتریس ضرایب مسئله کمترین مربعات وزندار می‌تواند بسیار بدحالت باشد، و در نتیجه روشهای متداول برای حل این مسئله جوابهای نادقیق بدست می‌دهد‌.‌بررسی روشهای مختلف و استفاده از این روشها در حل این مسئله از نقطه نظر عددی و پایداری مورد نظر ماست‌.‌از این رو، مادام که D بسیار بدحالت باشد ما به دنبال الگوریتم هایی هستیم که خاصیت پایداری زیر را داشته باشد: (3.3.2) که در آن جواب دقیق،جواب محاسبه شده ،f(A) تابعی از A مستقل از D و خطای ماشین است.

1.4.2‌.‌مسئله (2.3.2.) با فرضهای (1) و (2) دارای جواب یگانه است(]1[و]12[.) اثبات: باید ثابت کنیم که ATD-1A وارونپذیر است.

از تجزیه SVD ماتریس A به صورت زیر استفاده می‌کنیم: , چون متعامد و یک ماتریس قطری با قطریهای مثبت است ، در نتیجه وارونپذیر و وارونپذیر خواهد بود پس y جواب مسئله(2.3.2)یگانه است.

2‌.‌‌4 تجزیه ماتریس برای حل مسئله کمترین مربعات وزندار[4] روشهای متعددی برای حل مسئله کمترین مربعات وزندار وجود دارند که به صورت زیر خلاصه می‌کنیم: 1.4.2‌.‌‌معادلات نرمال.

2.4.2‌.‌‌تجزیه QR‌.‌ 3.4.2‌.‌‌تجزیه SVD‌.‌ 4.4.2‌.‌‌تبدیل به یک دستگاه خطی‌.‌ خواهیم دید که روش اول ، سریعترین روش ولی کمترین دقت را داراست‌.‌این روش تا وقتی که عدد حالت ، کوچک باشد مناسب است‌.‌ روش دوم ، یک روش استاندارد است ، که تقریباً دو برابر روش اول عملیات لازم دارد ولی از نظر دقت عددی نسبت به روش اول از وضعیت بهتری برخوردار است‌.‌ روش سوم ، روشی است که برای مسائل بد حالت مورد استفاده قرارمی گیرد(وقتی ماتریس A رتبه کامل نباشد) ، و از تعداد عملیات بیشتری نسبت به دو روش قبلی برخوردار است‌.‌ حال سه روش اول را در این فصل و روش آخر را که مربوط به حل دستگاه معادلات است در فصل بعدی مورد بررسی خواهیم داد‌.‌ 1.4.2‌.‌‌معادلات نرمال ([5] و [10]) مسئله (2.3.2) را در نظر می‌گیریم: با قرار و مسئله فوق به صورت زیر خواهد بود: .(1.4.2) با توجه به رابطه(8.2.2)،مسئله(1.4.2) به صورت زیر نتیجه می‌شود: که با توجه به فرضهای(1) و (2) نتیجه می‌گیریم که ماتریس متقارنِ معینِ مثبت، خواهد بود‌.‌دستگاه یک دستگاه خطی مرسومبه دستگاه نرمال است،که از روش تجزیه چولسکی قابل حل است.

الگوریتم 1.4.2‌.‌(با استفاده از روش معادلات نرمال) فرض کنیم ، و و ماتریس یک ماتریس متقارنِ معینِ مثبت و قطری حقیقی و بسیار بد حالت باشد‌.‌در اینصورت این الگوریتم جواب y را برای مسئله(2.3.2) محاسبه می‌کند.

تبدیل و را بدست آور،که تعداد عملیات برابر است.

قسمت پایین مثلثی را بدست آور،که تعداد عملیات برابر است.

قرار ده ، که تعداد عملیات برابر است.

تجزیه چولسکی G=GGT را محاسبه کن، که تعداد عملیات برابر است.

دستگاه پایین مثلثی Gz=d را برای z محاسبه کن، که تعداد عملیات برابراست.

دستگاه بالا مثلثی GTy=z را برای y محاسبه کن، که تعداد عملیات برابر است.

در مجموع تعداد کل فلاپها برابر می باشد.

الگوریتم 2.4.2‌.‌(روش معادلات برای حل مسئله (2.3.2)با استفاده از Matlab) بحث راجع به الگوریتم معادلات نرمال برای مسئله (2.3.2) الف) ماتریس محاسبه شده و به جای در روابط زیر صدق می‌کنند: (2.4.2) , و (3.4.2) , ب) محاسبه شده به جای در رابطه زیر صدق می‌کند: