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

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

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

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

را یک دستگاه تعادلی گویند، که با توجه به فرض‌های فوق با مساله کمترین مربعات بالا در بدست آوردن جواب y معادل است.
این دستگاه کاربردهای زیادی دارد‌.‌در سال 1988 استرنگ برخی از کاربردهای آن را در زمینه‌های بهینه‌سازی، المان‌های متناهی و شبکه‌های الکتریکی مشاهده کرد و به این نتیجه رسید که در اکثر موارد ماتریس وزن D برای آنها بسیار بدحالت می‌شدند‌.‌این موجب شد که یک سال بعد استوارت یک نرم کراندار را برای دستگاه‌های تعادلی فوق برقرار کند‌.‌این حرکتی شد برای واوایز که در سال 1994 روش پایدار NSH را برای دستگاه‌های تعادلی فوق تحت نتایج تعریف شده استوار بوجود آورد‌.‌از آن پس روش NSH به عنوان یکی از روش‌های مفید برای دستگاه‌های تعادلی که ماتریس وزن D آنها بسیار بدحالت بودند، مورد استفاده قرار گرفت‌.‌
نشان داده شد که کران بالای جواب این روش مستقل از D و عدد حالت D است‌.‌این مزیتی برای روش NSH محسوب می‌شود، زیرا روش‌های قبلی فاقد چنین کرانی بودند.
بالاخره در سال 1997 هاگ و واوازیز، روش پایدار دیگری را تحت نتایج تعریف شده استوارت بوجود آوردند که به روی COD موسوم شد.
این روش هم از لحاظ کارایی، و هم از نظر سادگی تکنیک‌های استاندارد بکار گرفته شده و هم به خاطر دارا بودن یک آزمون برای وابستگی سطرهای ماتریس A در مقابل وزن‌هایشان، به عنوان روشی بسیار مفید برای حل اینگونه مسائل مورد استفاده قرار گرفت.
این رساله به صورت زیر سازماندهی می‌شود:
در فصل اول مقدماتی از جبر خطی عددی را بررسی خواهیم کرد که شامل نمادها و الگوریتم‌های پایه‌ای، آنالیز ماتریس، آنالیز خطا، تجزیه ماتریس و دستگاه‌های خطی می‌باشد.
در فصل دوم حل مساله کمترین مربعات وزندار را با استفاده از روش‌های دستگاه معادلات نرمال، تجزیه QR و SVD از نظر عددی و پایداری بررسی خواهیم کرد.
در فصل سوم دستگاه‌های تعادلی و حل مساله کمترین مربعات وزندار را با استفاده از الگوریتم‌های مربوط به این دستگاه (روش‌های فضای پوچ و NSH)، از نظر عددی و پایداری مورد تحلیل قرار خواهیم داد.
در فصل چهارم حل مساله را با استفاده از تجزیه قائم کامل COD از نظر عددی و پایداری بررسی خواهیم کرد.
در فصل پنجم الگوریتم‌های فوق را از نظر عددی، پایداری و کارایی مورد مقایسه قرار
می‌دهیم‌.‌الگوریتم‌ها را با استفاده از 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‌.‌ماتریس قطری
در حالت کلی ماتریس قطری به صورت زیر نشان داده می‌شود:

فایل : 116 صفحه

فرمت : Word