بخشی از مقاله
چكيده
حل مساله كمترين مربعات وزندار به صورت از طريق روش تجزيه قائم كامل موردنظر است.در عمل ماتريس وزن‌ها مي‌تواند بسيار بدحالت باشد و در نتيجه روش‌هاي متداول، ممكن است جواب‌هاي نادقيق بدست بدهند.استوار و تاد يك نرم كراندار را براي مساله كمترين مربعات وزندار برقرار كردند كه مستقل از ماتريس وزن 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 يك ماتريس و الگوريتم‌هاي مربوط به آن مي‌پردازد.بخش پنجم، مختصري در مورد تعريف و حالت و حل روش‌هاي مختلف دستگاه‌هاي خطي را بررسي مي‌كند.
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 باشند، در اينصورت روابط زير برقرار هستند:
1. PX همان X با جابجايي سطرها و XP همان X با جابجايي ستون‌هاست.
2. P-1=PT.
3. .
4. 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. زيرفضاهاي مكمل متعامدند:
لم 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 خلاصه مي‌كند.
توضيحات بعد ماتريس پايه زيرفضا
A=GH m×r G R(A)
GTK=0 m×(m-r) K N(AT)
HZ=0 n×(n-r) Z N(A)
YTZ=0 n×r Y(=HT) R(AT)
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 خيلي بزرگ باشد، آنگاه e¬A¬ مي‌تواند بزرگ و اگر 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(d¬2), s(d¬1) جواب‌هاي مساله 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 ، روابط و برای برقرارند، که در آن ها، مقادیر تکین و و ، به ترتیب بردارهای تکین راست و چپ گفته می‌شوند.
