معین نامنفی است زیرا:,,, نشان دهیم قرار دهیم یک ماتریس,,, نامیده می شند اگر ma, mi مقادیر تکین یک ماتریس Values: Sigula m باشد آنگاه ماتریس فرض کنید یک ماتریس بنابراین مقادیر یژه نامنفی می باشند. اگر این مقادیر یژه را با ma ma ma () () آنگاه از رابط فق داریم:,,, مقادیر تکین ماتریس در اینصرت مقادیر داریم زیرا براي با رشی مشابه ثابت می شد. بیژه اگر m نامنفرد باشد y y mi ma ma y در نتیجه اگر که در آن ماتریس متقارن (هرمیتی) منفرد باشد, به ترتیب بزرگترین کچکترین مقدار یژه می باشند زیرا. () Sigula Values decompositio U mمانند m باشد آنگاه یک ماتریس یکانی m U V که در آن لذا i i یع ین i i در نتیجه تجزیه مقادیر تکین یک ماتریس قضیه: فرض کنید یک ماتریس دلخاه (مختلط) V جد دارند بقسمی که یک ماتریس یکانی مانند یک ماتریس m قطري به شکل زیر است D,( D,, diag,),,, مقادیر تکین مخالف صفر هستند رتبه ماتریس است. همچنین مقادیر تکین غیر صفر UV می باشد تجزیه,, دقیقا برابر اعداد قضیه را ثابت می کنیم. براي تجزیه تکین مقدار نامیده می شد. چیزي براي اثبات جد m برقرار باشد. فرض کنید بزرگترین مقدار باشد. اگر بردار یژه نظیر فرض کنیم اثبات: با استفاده از استقرا بر ري m ندارد. فرض کنید براي m آنگاه. از اینر فرض کنیم براي ماتریس 9
,, باشد بعلاه فرض کنیم اختیار می کنیم که دسته بردارهاي بنابراین. حال بردار را بقسمی,,, دبه د متعامد بعلاه یکانی باشند. اگر تعریف کنیم. y y X X I بنابراین X,, m بعلاه تعریف می کنیم:, ym, را بقسمی بدست می آریم که بردارهاي y زیرا بردارهاي فضاي,y ym,, یک دسته بردار یکا متعامد در y. Y Y I اضح است که Y y, y, y تشکیل دهند. تعریف می کنیم: Y X e Y Y y Y y e () Y X e X Ye X y X X X e m m با تجه به این رابط می تان نتیجه گرفت که ماتریس Y X داراي شکل زیر است: ()() m Y X بر طبق فرض استقرا ماتریس هاي یکانی U V یافت می شند بطریکه D U V,( D, diag,) ()()()()()() m m, m U, V V X خاهیم داشت: U Y حال با تعریف V U U V Y X U V U V D D U V همچنین داریم diag(,,,,,,)() V UU V V V هستند چن,,,,,, از رابطه () نتیجه می شد که مقادیر یژه مقادیر مقدار تکین است پس لازم است داشته باشیم بزرگترین V در بردارنده بردارهاي یژه ضمنا رابطه () نشان می دهد که ماتریس است. به طر مشابه U VV U U U () است. رابطه () نشان می دهد ماتریس Uدربردارنده بردارهاي یژه تجه: مقادیر یژه غیر صفر مثال: تجزیه مقدار تکین ماتریس زیر را به دست آرید. یکسان هستند.( بنا به ) 9
/ 96 / 7 / / 8 96 حل: طبق قضیه داریم 6/ 3/ 84 B, det() B I,, / / 9 3 3 84 3 88 ستنهاي V بردارهاي یژه از ماتریس می باشند که طل آنها برابر یک است. بنابراین U عبارتند. u v 9 4 3 4 3 5 5 5 5 V v 3 4 3 4 5 5 5 5 حال به محاسبه ماتریس می پردازیم. از رابطه U V نتیجه می شد که ستنهاي 4 5 3 5 بنابراین v v U. u u v از v 3 4 9 5 5 5 u. v لذا v داریم 4 3 5 5 5 3 4 5 5. U در نتیجه 4 3 5 5 3 4 4 3 5 5 3 5 5 4 3 3 4 5 5 5 5 مثال: / 6 / 6 / / 8 4 4,, 3,, 3 براي تشکیل V بنا به تجه بردارهاي یژه را بدست می آریم vi i vi v, v, v 3 براي تشکیل U بردارهاي یژه را بدست می آریم. / 4 / 44 / / 44 8 / 8 / 6 / / u i i u i u 6, u 8, u, u 3 4 بنابراین خاهیم داشت 9
3 / 8 / 6 / / 6 8 مثال) تجزیه مقدار تکین ماتریس زیر را به دست آرید. 6 6 حل) داریم 4 34 6 B 34 37, det() B I, 8, 9 3 4 3 در نتیجه 3 9 3 مقادیر تکین هستند. بردارهاي یژه یکه متناظر با v, v, v 3 3 3 3 3 3 3 3 3 3 u v, u v 3 3 3 U V 9 3 3 3 3 3 3 3 3 3 3 3 عبارتند از در نتیجه شبه معکس معکس تعمیم یافته معکس پن رز (Peose) 93 براي یک ماتریس m به شکل, i, i,,,. معکس پن رز آن یک ماتریس m به شکل زیر است: در حالت کلی براي یک ماتریس m معکس پن رز به صرت زیر تعریف می شد:
U V V U نامنفرد باشد آنگاه زیرا () U V V U V U اگر یک ماتریس مثال: براي ماتریس در مثال قبل / 8 / 6 / / 6 8 / 4 / 3 / / 6 8 X جد دارد که در چهار خاصیت زیر که خاص پن رز () X () XX ()() 3 X ()() 4 X قضیه: متناظر با هر ماتریس حداکثر یک ماتریس X X X Y جد داشته باشد که در چهار خاصیت فق صدق کند در این صرت ()()()(),() 3 4 () (),()()() 3 4 نامیده می شد صدق می کند. اثبات: فرض کنیم د ماتریس X X XX XYX XYYYX ()()()() X Y Y Y X X Y YY X Y YY ()() Y Y Y YYY YY Y داریم: تمرین: منحصربفرد است. ثابت کنید شبه معکس یک ماتریس داراي چهار خاصیت پن رز است. از این ر شبه معکس تمرین: در صرتی که ماتریس m با m داراي رتبه ستنی کامل باشد نشان دهید که () در صرتی که ماتریس m با m داراي رتبه سطري کامل باشد نشان دهید () تمرین: نشان دهید براي هر ماتریس دلخاه داریم, مثال: شبه معکس ماتریس زیر را به دست آرید. 5 4,,() P 3 9 3 4 5 3 9, 9, 94
, V 5 4 7 4 5 5 4 3,()() P 3 9 3 9 5 7 5 9,, 3 4 3 3 3 3 38 54 3 8 3 8,,, 38 6 54 U 4 3 4 4 4 7 38 6 54 4 7 38 6 54 9, 9 در نتیجه شبه معکس ماتریس به صرت زیر به دست می آید V U 7 6 49 3 9 6 7 7 4 چن m از رابطه زیر نیز را می تان محاسبه کرد () 5 4 7 6 49 3 (), 9 4 5 76 7 7 4 فرض کنید UV تجزیه مقدار تکین ماتریس m باشد که در آن D, D diag(,,,), U که در آن همچنین براي تعریف می کنیم V D, D diag(,,,).. a() می تان ماتریس را یک تقریب براي ماتریس در نظر گرفت. قضیه هستند ماتریس m که داراي رتبه به ضح داریم زیر کیفیت این تقریب را نشان می دهد. قضیه: از بین تمام ماتریس هاي است به این مفهم که به ازاي هر بهترین تقریب براي ماتریس a()b داریم با B B. V ( v, v,,) v به سادگی می تان دید u v, u v m i i i i i i i i. U ( u, u,,) u m به علاه برهان: فرض کنید 95
v iuivi ( u,,)( u diag,,,) i v D U V,,). D diag(,,,, از این که ماتریس هاي U V یکانی هستند داریم D () D D. a()b داریم B m در نتیجه که در آن حال فرض کنید dim(ull()) B dim(age()) B a() B. E spa v, v,, v داریم همچنین فرض کنید dim(ull()) B dim()()() E. این رابطه نشان می دهد که بردار غیرصفري مثل w در E ull() B جد دارد. بدن از دست دادن کلیت i فرض می کنیم. w بنابراین Bw اسکالرهایی مثل, i,, جد دارند به V w z V. در نتیجه (,,,,,) که در آن w ivi طري که, V i. حال براي کامل کردن اثبات داریم i i i B () B w w UV w i i داریم آنگاه b.. اگر b b m, b m قضیه: فرض کنید. b mi b که الف- ب- براي هر بردار اثبات- الف) فرض کنیم تجزیه مقدار تکین به صرت باشد. قرار می دهیم z, c U V c U b بردارهاي z c را به صرت زیر افراز می کنیم c c که در آن با این افراز داریم c m z z b U ()() b VV U b U V V z c D z Dz c c z Dz c c c در نتیجه بردار z عبارت فق را می نیمم می کند هرگاه z D c دلخاه می باشد. z D c z در صرتی که z در نتیجه از قرار می دهیم خاهیم داشت Vz 96
D c D c Vz V V c c V c V U b b. با تجه به الف داریم ب) حال فرض کنیم جاب دیگري از مسا له الف باشد D c Vz V, z z D c Vz D c z z D c z Vz در نتیجه داریم مثال: مسا له کمترین مربعات زیر را حل کنید. 3 3 3 3 4 حل: داریم 3 3, b 3 3 4 شبه معکس ماتریس را به صرت زیر به دست آردیم 7 6 49 3 9 6 7 7 4 در نتیجه b 6 9 36 همچنین از راه دستگاه نرمال خاهیم داشت 5 4 6 b 4 5 6 4 5 6 5 6 4, 36 5 4 9 5 4 9 4 5 4 5 mi را به b حل دستگاه هاي مستطیلی با استفاده از رش کمترین تانهاي دم m با m را که در آن دستگاه b را در نظر می گیریم. می خاهیم دست آریم. براي این منظر تجزیه QR ماتریس را به دست می آریم داریم 97
() h R h R h R h h h m m R حال اگر دستگاه h. h h b b QR Q Q b R Q b R که در آن به صرت زیر به دست می آید را حل کنی م جاب بهینه دستگاه mi b h 3 3 b مثال: دستگاه زیر را حل کنید.. b به کمک رش هسهلدر تجزیه QR ماتریس را به حل ( داریم دست می آید 3 5 Q 3 5 3, R 6 3 5 3 3 3 3 Q b, h, h [ ] R به صرت زیر به دست می آید h بنابراین دستگاه 3 3 3, mi b h 3 تمرین: دستگاه زیر را حل کنید. 4 3 3 3 تمرین: تجزیه مقدار تکین ماتریس زیر را پیداکنید شبه معکس آن را بیابید. 8 3 6 4 98
ب. a() m که m تمرین: فرض کنید مقادیر تکین غیر B()() I باشند. براي تعریف می کنیم. نشان دهید صفر. lim()b ()B از آنجا نتیجه بگیرید () به صرت مقادیر تکین تمرین: فرض کنید E ماتریس هاي E با E E باشند. ثابت کنید: الف) اگر E منفرد باشد آنگاه ( ماتریسی مانند مجد است به طري که E منفرد باشد. تعریف می کنیم تمرین: فرض کنید U V تجزیه مقدار تکین باشد براي که در آن مقادیر تکین مخالف صفر هستند رتبه ماتریس U V است. ثابت کنید از بین تمام ماتریس هاي m که داراي رتبه هستند ماتریس بهترین تقریب براي ماتریس. است داریم رش هاي تکراري ریچاردسن گرادیان (سریع ترین کاهش) براي حل دستگاه b را یک شکافت از گییم هرگاه M نامنفرد را به صرت M N, فرض کنید M N باشد. حال اگر. در این صرت b باشد دستگاه یک شکافت از ماتریس M N بازنیسی می کنیم. چن M نامنفرد است داریم M N M b رابطه به صرت زیر به دست می آید ()() M N M b ()() رابطه تکراري B d حاصل می شد که به b d M b ()M N b تکراري معادل براي حل دستگاه قرار می دهیم B M N آن یک رابطه تکراري ایستا می گییم. رش هاي تکراري ژاکبی گاس- سایدل SOR که قبلا بیان کردیم B در آن ها ثابت است. نیز جزء رش هاي ایستا می باشند زیرا ماتریس تکرار یعنی رش تکراري ریچاردسن: رابطه تکراري زیر بیان می شد این رش جزء رش هاي تکراري ایستا می باشد. براي این رش با () b ()()() () () I b ()B است. براي همگرایی ماتریس تکرار رش I B() به صرت ) مقدار یژه ( می باشند ma mi N I M بنابراین I رش با تجه به اینکه مقادیر یژه ماتریس تکرار که ma داریم mi به ترتیب کچکترین بزرگترین مقادیر یژه ماتریس هستند. بنابراین می تان گفت که رش ریچاردسن همگراست اگر فقط اگر. ma حال فرض کنید ماتریس متقارن معین mi در نتیجه در رابطه زیر صدق می کند ma مثبت باشد. به ضح می تان دید که شعاع طیفی (()) B ma{, } ma mi می خاهیم opt را طري بیابیم که 99
(()) B opt همگرایی رش (()) B mi(()) B opt ma. opt همچنین داریم به سادگی می تان دید که mi ma (()) B opt mi ma mi ma ma mi mi () ma mi ma () mi رابطه بالا نشان می دهد که اگر () خیلی بزرگ باشد آنگاه ریچاردسن بسیار کند خاهد بد. رش گرادیان (سریع ترین کاهش): این رش جزء رش هاي تکراري ناایستا می باشد. دستگاه را به با : یک ماتریس معین مثبت متقارن است. تابع را در نظر می گیریم که در آن b b تعریف می کنیم. قضیه زیر بیان می کند که حل دستگاه () صرت b مینیمم کردن تابع معادل است. b جاب دستگاه b قضیه: فرض کنید است اگرفقط اگر یک ماتریس معین مثبت متقارن است. بردار ()(). داریم h را مینیمم کند. تابع اثبات: براي هر h نشان می دهیم ()()()()() h h h h b b h h h h h b h h b h h h () b h h. ()() h بنابراین حال اگر جاب دستگاه b باشد آنگاه h h ()() یعنی تابع را مینیمم می کند. برعکس فرض کنید تابع را مینیمم کند. در h b این صرت داریم ()()() h h b h h s زیرا در غیراینصرت با فرض h s از رابطه فق داریم ادعا می کنیم b ()() h s s h h h h h h h h که تناقض است بنابراین. b حال به اراي ه رش سریع ترین کاهش می پردازیم. فرض کنید باشد. در تکرار p از رش سریع ترین کاهش بردار ()ام یک حدس الیه از جاب دستگاه می کنیم که عدد حقیقی را طري محاسبه mi(). () به ضح می تان دید که p p p ()() p, p p p. b در نتیجه d () p p p p براي مینیمم کردن تابع بالا بایستی داشته باشیم d p معین مثبت متقارن است بنابراین d زیرا () p p p همچنین. d p p p p p را مینیمم می کند در نتیجه قرار می دهیم () p ي به دست آمده تابع ال آنچه ح.
است. با تجه به اینکه تابع در خلاف جهت بردار p خاهد بد. همچنین داریم (). Choose a iitial guess. Fo,,, util covegece do 3. b 4. 5. 6. Ed do از اهمیت یژه اي برخردار است انتخاب بردار جهت p گرادیان سریع ترین کاهش را دارد یک انتخاب مناسب به صرت. p b در نتیجه () b الگریتم رش گرادیان با مقایسه الگریتم سریعترین کاهش ریچاردسن ملاحظه می کنیم که د رش شبیه به هم هستند تنها p عمد است. همچنین در هر تفاتشان در انتخاب پارامتر است. همچنین داریم () b b () با تجه به رابطه بالا نحه محاسبه در الگریتم داریم p یعنی هر بردار جهت بر بردار جهت تکرار قبلی یعنی تکرار از الگریتم رش گرادیان د ضرب ماتریس در بردار انجام می شد (گام 3 5) در صرتی که با استفاده از رابطه () می تان الگریتم را به صرت زیر بازنیسی کرد که از یکی از ضرب ها صرفنظر شد ()(). Choose a iitial guess, b. Fo,,, util covegece do 3. 4. 5. 6. Ed do, y تعریف می کنیم تمرین: فرض کنید یک ماتریس معین مثبت هرمیتی باشد. براي هر است. این ضرب داخلی ري نرم ma mi ضرب داخلی ري )یک,) نشان دهید.(,)( y,) y (,)(,) را تعریف می کند که به نرم- معرف است. تمرین (نامساي کانتریچ): فرض کنید یک ماتریس معین مثبت متقارن باشد به ترتیب کچکترین بزرگترین مقادیر یژه باشند. ثابت کنید به ازاي هر داریم (,)(,)() (,) ma mi ma 4mima mi. قضیه: فرض کنید یک ماتریس معین مثبت متقارن باشد مقادیر یژه باشند. در این صرت نرم- بردارهاي خطا در رش گرادیان یعنی به ترتیب کچکترین بزرگترین e در رابطه e ma mi e ma mi زیر صدق می کند بنابراین رش همگراست. اثبات: داریم
e () b همچنین ma ma e e,).(,)( بنابراین می تان نشت e ( e,)( e,) e (,)( e,)(,)( e,) e (,) e (,)( e,) e e (,) e (,)(,) e e (,)(,) e e (,)(,) e (,) (,) (,)(,) e (,) (,) mi mi () بزرگ باشد همگرایی حال با استفاده از نامساي کانتریچ نتیجه به دست می آید قسمت دم با تجه به اینکه برقرار است. تذکر: مانند رش ریچاردسن با تجه به قضیه قبل می تان نتیجه گرفت که اگر را در نظر بگیرید که در آن رش گرادیان بسیار کند خاهد بد. تمرین: دستگاه b / /, b / 499 / 5 نشان دهید معین مثبت است. سپس دستگاه را با رش گرادیان با حدس الیه بردار صفر شرط تقف حل کنید. M N تمرین: فرض کنید یک شکافت براي باشد. قرار می دهیم M()(),() M N, N M M باشند. N مقادیر یژه ()() با هر بردار الیه M()()() N M b I I S M()(). فرض کنید N تجه کنید که که در آن آنگاه دنباله ثابت کنید اگر () همگراست. سپس نشان دهید mi(()())(()()) M N M N. که در آن تمرین: فرض کنید درایه هاي قطري ماتریس معین مثبت متقارن یک باشند رند تکراري زیر را در نظر می گیریم ماتریس همانی است. براي حل دستگاه b ()() (),, I S b. () الا نشان دهید این رند تکراري با هر حدس الیه به جاب دستگاه b همگزاست اگر تنها اگر بزرگترین مقدار یژه است. ثانیا مقدار بهینه پارامتر را به دست آرید. که در آن