pari
rezaهنوز در کاربرد ،برای ماتریس های مشخص،حذف گاووسی با محورگیری جزیی تماما ناپایدار است.این تناقض ظاهری یک توضیح ایستا دارد.
پایداری و اندازه L و U
آنالیز پایداری بیشتر الگوریتم های جبر خطی عددی ، مجازا شامل همه ی آنهایی که مبتنی بر اعمال یکانی هستند ساده می باشد.اما از دهه 1950، آنالیز پایداری حذف گاووسی با محورگیری جزیی ، پیچیده و یک نکته دشوار در آنالیز عددی بوده است.این است دلیل این که ما حذفی گاووس را تا نیمه دوم این کتاب نگه داشته ایم.
در شکل (20.9) ماتریس نمونه 2X2 را داده ایم که روش حذفی گاووس برایش ناپایدار بود.در آن مثال فاکتور L ورودی به اندازه 10 به توان 20 داشت .تلاشی برای حل معادله بر اساس L یک خطای گرد کردن مرتبط به نظام اپسیلون ماشین را به نمایش گذاشت.از این رو همانطور که انتظار می رفت این دستور صحت نتیجه را تخریب نمود.
به گونه ای کاشف به عمل می آید که نمونه ما کاملا عمومی است.ناپایداری در حذف گاووسی ، با محورگیری یا بدون آن ،می تواند با بزرگ بودن یکی یا هردو فاکتور L و U نسبت به اندازه A بروز نماید.بنابراین،هدف محورگیری از نقطه نظر پایداری ،حصول اطمینان از این است که L و U بیش از اندازه بزرگ نباشند.همانقدر که کمیت های بینابینی در طی حذف بروز می کنند در اندازه ای قابل مدیریت هستند.خطا های منتشر شده بسیار کم و الگوریتم ،عقبگرد پایدار است.
قضیه ذیل این ایده را دقت می بخشد.این برای حذفی گاووس بدون محورگیری ذکر شده است،اما اگر A مایش ماتریس اصلی با سطر ها و/یا ستون های مناسب باشد ،این برای حذفی گاووس با محور گیری جزیی نیز اعمال شده است.
قضیه 22.1 فرض می کنیم فاکتور گیری A=LU از یک ماتریس نامنفرد {{*}} با روش حذفی گاووس بدون محورگیری محاسبه شده باشد(الگوریتم 20.1). بر روی رایانه ای که شروط (13.5) و (13.7) را ارضا می کند، اگر A یک فاکتور LU داشته باشد ،آنگاه برای همه اپسیلون های به قدر کافی کوچک فاکتور گیری با موفقیت در حساب ممیز شناور تکمیل می گردد(هیچ محور صفری در نظر گرفته نمی شود.)ماتریس های {{*}} و {{*}} ارضا می شوند.
{{*}}
برای بعضی {{*}}
بصورت معمول در جبرخطی عددی ادعایی در باره {{*}}یا {{*}} نمی کنیم.فقط درباره {{*}} بحث میکنیم.
در نگاه اول ممکن است این تخمین مانند نیمی از صفحات دیگر این کتاب همانند (16.3) و (17.3)بنظر برسد.چیزی که آنرا متفاوت می سازد این است که مخرج {{*}} است، نه {{*}}.اگر {{*}}آنگاه {{*}} اثبات می کند که روش حذفی گاووس پایدار عقبگرد است.اما اگر {{*}} باید انتظار ناپایداری عقبگرد را داشته باشیم.
برای حذف گاووسی بدون محورگیری،هم L و هم U می توانند بدون حد و مرز بزرگ باشند.این الگوریتم با هر استانداردی ناپایدار است و نباید بیش از این درباره اش بحث نماییم.درعوض، از حالا باید توجهمان را معطوف روش حذفی گاووس با محورگیری جزیی نماییم.
فاکتور های رشد
حذفی گاووس با محورگیری جزیی را در نظر بگیرید.چون هر محورگیری شامل بیشینه سازی روی یک ستون می گردد،این الگوریتم یک ماتریس L با ورودی های با ارزش کامل =<1 , و پایین مثلثی تولید می کند.
این یعنی {{*}} در هرنرم.پس برای حذفی گاووس با محورگیری جزیی ، (22.1 ) به شرایط {{*}} کاسته می شود.نتیجه می گیریم که الگوریتم پایدار عقبگرد است {{*}}.
فروموله سازی مجدد این استنتاج شاید واضحتر باشد.حذفی گاووس یک ماتریس کاملA را به یک ماتریس بالامثلثی U خلاصه می کند.دیده ایم که پرسش کلیدی برای پایداری این است که آیا تقویت ورودی ها در طی این تلخیص روی می دهد؟بطور خاص فرض کنید فاکتور رشد A بصورت نرخ زیر محاسبه شود.
{{*}}
اگر {{*}} از نوع یک باشد ،رشد کافی اتفاق نیفتاده است و پروسه ی حذف پایدار است.اگر {{*}} بزرگتر از این باشد ، باید انتظار عدم پایداری را داشته باشیم.بطور خاص،از آنجاییکه {{*}} و از آنجاییکه (22.2) یعنی {{*}} نتیجه زیر استنباط قضیه 22.1 است.
قضیه 22.2 :فرض کنید فاکتور گیری PA=LU از ماتریس {{*}} بروش حذفی گاووس با محورگیری جزیی (الگوریتم 21.1).در رایانه ای که شرایط (13.5)و (13.7) را ارضا می کندمحاسبه شده باشد.سپس ماتریس های محاسبه شده ی {{*}} و{{*}} و {{*}} ارضا می شوند.
(22.3)
برای بعضی از {{*}} ، هر جا که {{*}} فاکتور رشد A باشد اگر {{*}} برای هر {{*}}، به این معنا که هیچ گره ای در انتخاب محور در محاسبه دقیق وجود ندارد، آنگاه برای هر {{*}}بقدر کافی کوچک،{{*}}.
آیا حذف گاووس پایدار عقبگرد می باشد؟براساس قضیه (22.2) و تعریف ما (14.5) از پایداری عقبگرد ،پاسخ مثبت است اگر {{*}}.
وحالا پیچیدگی آغاز می شود!
ناپایداری بدترین حالت
برای ماتریس های مشخصه ی A ،برغم تبعات مثبت محورگیری، {{*}} بسیار بزرگ می شود.برای مثال ماتریس A را فرض نمایید :
(22.4)
در گام اول هیچ محورگیری انجام نمی شود.اما ورودی های {{*}} در ستون آخر از 1 به 2 مضاعف می گردند.یک افزایش مضاعف دیگر در گام های حذف بعدی اتفاق می افتد و در پایان داریم:
(22.5)
فاکتور گیری نهایی PA=LU به گونه ی زیر به چشم می آید .
برای این ماتریس {{*}} ، فاکتور رشد {{*}} است.برای یک ماتریس {{*}} از فرم مشابه ، می شود {{*}}.(به همان بزرگی که {{*}} می تواند باشد.تمرین 22.1 را ببینید.)
یک فاکتور رشد به شکل {{*}} مطابق است با از دست رفتن دقت m بیت که برای محاسبات واقعی فاجعه بار است.از آنجاییکه یک رایانه معمولی اعداد ممیز شناور را با فقط 64 بیت نشان می دهد،درحالیکه مسایل ماتریسی در صد ها ویا هزاران بعد همیشه حل شده هستند،یک کاهش دقت m بیتی برای محاسبات حقیقی غیرقابل تحمل است.
این مارا به نقطه نابخردانه ای می رساند.در اینجا ،در مبحث حذفی گاووس با محورگیری تنها در محدوده ی همین کتاب ، تعاریف مطرح شده در باره پایداری در سرفصل 14 مارا به شکست میرساند.براساس تعاریف،همه مشکل در یافتن پایداری یا پایداری رو به عقب ، وجود محدوده مشخصی می باشد که بصورت یکنواخت نسبت به همه ماتریس ها برای هر بعد ایستای m کاربردی است.
با وجود m ، یکنوایی مورد نیاز نیست.در اینجا برای هر m ما محدوده ی یکواخت شامل ثابت {{*}} داریم.پس طبق تعاریف ، حذفی گاووس پایدار عقبگرد می باشد.
قضیه 22.3 : بر طبق تعاریف سرفصل 14 ،حذفی گاووس با محورگیری جزیی پایدار رو به عقب است.
این استنتاج مضحک است،اما از دید وسعت {{*}} برای مقادیر کاربردی m.
برای باقیمانده این فصل ، از خواننده می خواهیم به تعاریف رسمی درباره پایداری توجه نکند و یک استفاده غیر رسمی (و استانداردتر ) از واژگان را بپذیرد.
حذفی گاووس برای ماتریس های مشخصه ، بیش از حد ناپایدار است.همانطور که می تواند توسط آزمایش های عددی در MATLAB ، LINPAC ، LAPACK و یا بسته های نرم افزاری نامی بی نقص دیگر تایید شود(تمرین 22.2).
پایداری در کاربرد
اگر حذفی گاووس ناپایدار است، چرا اینقدر معروف و سرشناس است؟این ما را به جایی می رساند که نه تنها یک اثر هنری از تعاریف است، بلکه حقیقتی بنیادین درباره رفتار این الگوریتم است.برغم مثالهایی چون (22.4)،حذفی گاووس با محورگیری جزیی واضحا در کاربرد پایدار است.فاکتور های بزرگ U مثل (22.5) هیچگاه بنظر نمی رسد که در کابرد ظاهر شوند.در عمر پنجاه ساله ی محاسبه ، هیچ مسئله ماتریسی که پایداری کامل را به بار آورد شناخته شده نیست که بصورت طبیعی تشریح شده باشد.
این واقعا شرایط نادری است.چگونه یک الگوریتم که برای ماتریس های مشخصه شکست می خورد
می تواند در کابرد کاملا قابل اعتماد باشد ؟! بنظر می رسد که پاسخ این باشد که اگرچه بعضی از ماتریس ها باعث ناپایداری می گردند، اما چنین سهم بیش از حد کوچکی از دسته همه ماتریس ها را نمایندگی می کند که هیچگاه به سادگی برای دلایل ایستا بروز نمی کنند.
می توان درباره این پدیده با توجه به ماتریس های تصادفی بیشتر آموخت، ماتریس هایی که در کاربرد جلوه می کنند به هیچ وجه معمول تصادفی نیستند.اگر کسی تلاش کند آنان را به عنوان نمونه های تصادفی از بعضی توزیع ها تفصیل کند ،آن مجبور خواهد بود واقعا توزیع نادری باشد.این مطمئنا نامستدل است که انتظار داشته باشیم توزیع مخصوصی از ماتریس های تصادفی با رفتار ماتریس های بروز کرده در کاربرد در یک روش کمی جفت و جور شود.
اما پدیده مشروح ، مشکلی برای دقت کمی نیست.ماتریس های با فاکتور رشد بزرگ ، در کاربرد نایاب هستند.اگر بتوانیم نشان دهیم آنها در میان ماتریس های تصادفی در بعضی کلاسه های خوش تعریف نایاب هستند، مکانیسم های مشمول باید مطمئنا متشابه باشند.آرگومان به اندازه (یافت نشدنی ) قابل پذیرش هر فاکتور کاربردی همچون 2 یا 10 یا 100 بستگی ندارد.
اشکال 22.1 و 22.2 همانطور که در تمرین 12.3 نشان داده شده ،آزمایش هایی با ماتریس های تصادفی را نشان می دهد:هر ورودی یک نمونه مستقل از توزیع نرمال حقیقی بمعنی 0 و انحراف استاندارد {{*}} است.در شکل 22.1 یک دسته از ماتریس های تصادفی از ابعاد متعدد فاکتور شده اند و فاکتور رشد بصورت یک مبحث نامتمرکز نشان داده شده است .تنها دو ماتریس فاکتور رشدی به بزرگی {{*}}را داده اند.در شکل 22.2 نتیجه ی فاکتور گیری یک میلیون ماتریس هر کدام از بعد m=8 و 16 و 32 ، نشان داده شده اند.اینجا فاکتور های رشد به طول 0.2 جمع آوری ،و اطلاعات مورد نتیجه همچون یک توزیع حجم احتمال دسته بندی شده اند.توزیع حجم احتمال فاکتور رشد ، برای کاهش توانی اندازه ظاهر می شود.در میان این سه میلیون ماتریس، اگرچه فاکتور رشد حداکثری در اصل ممکن است 2147483648 شده باشد، بیشینه مورد توجه واقعا 11.99 بود.نتایج مشابه توسط ماتریس های تصادفی تعریف شده که با توزیع های حجمی احتمال دیگر تعریف شده اند، همچون ورودی های توزیعی یکنوا در {{*}} یافته شده اند. (تمرین 22.3) .
اگر یک میلیارد ماتریس تصادفی را در نظر بگیرید ، قریب به اطمینان ماتریسی که با حذفی گاووس ناپایدار باشد پیدا نخواهید کرد.
تشریح
نباید تلاش کنیم که یک توضیح کامل از این ارایه دهیم که چرا ماتریس هایی که حذفی گاووس برای آنها ناپایدار است بسیار کمیابند.این غیر ممکن خواهد بود،همانطور که مشکل هنوز کاملا درک نشده است.اما بهتر است یک طرح کلی از تعریف راارایه دهیم.
اگر PA=LU ، آنگاه {{*}}.در ادامه یعنی که آیا حذف گاووسی وقتی به ماتریس A اعمال می گردد ناپایدار است یانه ،به این معنا که {{*}} بزرگ است.آنگاه {{*}} نیز باید بزرگ باشد .حالا ، همانطور که می بینیم ماتریس های مثلثی تصادفی به داشتن وارونگی هایی که بصورت توانی همچون توابعی از بعد m بزرگ باشند گرایش دارند(تمرین 12.).
شکل 22.1فاکتور های رشد برای حذفی گاووس با محورگیری جزیی که به 496 ماتریس(مستقل ،ورودی های توزیع شده نرمال) از ابعاد متعدد اعمال گشته اند .اندازه معمول {{*}} از شکل {{*}} بسیار کمتر از ماکسیمال ممکن {{*}} است.
شکل 22.2 توزیع حجمی احتمال برای فاکتورهای رشد ماتریس های تصادفی از ابعاد m=8 و 16 و 32
براساس اندازه های نمونه یک میلیون برای هر بعد.بنظر ، حجم بصورت توانی با {{*}} کم می شود.
زمزمه های نزدیک به پایان هر قوس یک اثر هنری از اندازه های نمونه متناهی است .
دراصل این برای ماتریس های مثلثی تصادفی به فرمی که توسط حذفی گاووس با محورگیری جزیی ارایه شد درست است.با 1 بر روی قطر و ورودی های =<1 .
وقتی حذفی گاووس به ماتریس های تصادفی A اعمال شده است، بااینحال اما فاکتور های مورد نتیجه L هر عدد تصادفی می توانند باشند.همبستگی های در میان علامت های ورودی های L که این ماتریس ها را بیش از حد خوش شرط ارایه می کنند ظاهر می گردند.یک ورودی معمول از {{*}} ، به دور از این که بصورت نمایی بزرگ باشد ، معمولا از نظر قدر مطلق کمتر از 1 است.شکل 22.3 گواه این پدیده مبتنی بر یک ماتریس (عموما) منفرد از بعد m=128 است.
پس به این پرسش می رسیم که :چرا ماتریس های L حاصل از حذفی گاووس تقریبا هیچگاه معکوس های بزرگ ندارند؟
پاسخ در توجه به فضای ستون ها نهفته است.از آنجاییکه U بالا مثلثی می باشد ، و PA=LU ، فضاهای ستون PA و L مشابه اند.بدین وسیله ما معنا می کنیم که ستون نخست PA همچون ستون اول L فضای مشابه ای را گسترش می دهد. دو ستون اول PA بصورت مشابه دو ستون اول L گسترده می شوند و ... .اگر A تصادفی باشد ، فضا های ستون آن تصادفی گرا هستند و این و در ادامه آن،بصورت مشابه این موضوع باید برای {{*}}هم درست باشد.اما این شرایط با بزرگ بودن وارون L ناسازگار است.می تواند نشان داده شود که اگر وارون L بزرگ باشد ، آنگاه فضاهای ستون L یا هر جایگزینی از {{*}} ، باید به گونه ای دور از تصادف منحرف گردد.
شکل 22.4 گواه این است.شکل همچون شکل 22.3 در فضا های متوالی ستونی دو ماتریس نشان می دهد که"انرژی کجاست".
ابزار انجام این کار پورتره ی Q است که توسط دستورات MATLAB تعریف شده است.
(22.6)
این دستورات نخست یک فاکتور گیری QR از ماتریس را حساب می کنند.سپس مطابق با هر ورودی بزرگتر از انحراف استاندارد {{*}} یک نقطه در جای هر Q رسم می کند.شکل تشریح می کند که برای هر ماتریس تصادفی A حتی پس از تعویض ردیف ها به شکل PA ، فضا های ستون تقریبا تصادفی گرایش می کنند درحالیکه برای یک ماتریس A که فاکتور رشد بزرگی را می دهد، گرایش ها بسیار دور از تصادف هستند.این می تواند اثبات آن باشد که فاکتور های رشد بزرگتر از شکل {{*}} بصورت نمایی در میان ماتریس های تصادفی برای هر {{*}} و {{*}} کمیابند.احتمال رویداد{{*}} برای همه m های بقدر کافی کوچک ، کمتر است از {{*}} .مثل این نوشته ، صحت این قضیه هنوز اثبات نشده است.
اجازه دهید پایداری حذفی گاووس با محورگیری جزیی را خلاصه کنیم.الگوریتم بسیار برای ماتریس های مشخصه A ناپایدار است .برای رخ دادن ناپایداری ، فضا های ستون A باید بصورت خیلی خاصی منحرف شوند که حداقل در یک کلاس ماتریس تصادفی بسیار نادر است .دهه ها تجربه محاسبات پیشنهاد می کنند که ماتریس هایی که فضاهای ستونی شان بدین گونه منحرف شده است ، در کاربرد بسیار کم ظهور می کنند.
شکل 22.3 فرض کنید A یک ماتریس تصادفی {{*}}با فاکتور گیری PA=LU باشد .در سمت چپ، {{*}}نشان داده شده است .نقطه ها نشاندهنده ورودی های با بزرگنمایی >=1 هستند.در سمت راست ، یک تصویر مشابه یرای {{*}} ، جاییکه {{*}} متشابه L است بجز اینکه علامت های ورودی های زیر قطر آن تصادفی شده اند.حذفی گاووس گرایش به تولید ماتریس های L دارد که بسیار خوش شرط می باشند.
شکل 22.4 پورتره یQ دو ماتریس مشابه (22.6). در سمت چپ ماتریس تصادفی A پس از جایگزینی به فرم PA ، یا هم ارزی فاکتور L. در سمت راست ماتریس {{*}}با علامت های تصادفی .فضا های ستونی {{*}} به روشی نمایی منحرف شده اند.بر خلاف آنچه در کلاس های معمولی ماتریس های تصادفی بروز می نماید.