روشهای تکراری پیش فرض در مسائل گسسته خطی
از منظر معکوس" بایسیان"
دانشکده ریاضیات و مرکزی برای مدل سازی سیستم های متابولیک کامل دانشگاه کمیس غربی کلوند، OH 44106 آمریکا
دریافتی 3 فویه 2005 دریافتی صورت اصلاح شده 24 آگوست 2005
چکیده:
در این مقاله ما با مسائل گسسته خطی که با روشهای تکراری قابل حل می باشد از نظر آماری معکوس بایسیان روبرو خواهیم شد پس از بررسی اجمالی روش های تکراری عمده برای حل مسائل ناقص خطی و برخی نتایج آماری اولیه و روشهای آماری استراتژیهای ترسیمی را مورد تجزیه و تحلیل قرار خواهیم داد. نمونه های محاسبه شده رابط بین این دو را تشریح می کند.
کلمات کلیدی: حل های معکوس( امتحانی) فضای فرعی" کریلا" و روش معکوس" بایسیان"
پیش فرضها مسائل ناقص
(1) مقدمه
استفاده از روشهای تکراری برای حل سیستمهای خطی معادلات روشی انتخابی است هنگامی که ابعاد سیستم آنقدر بزرگ باشد که
فاکتورسازی ماتریس A را غیر عملی سازد یا هنگامی که ماتریس آن بطور صریح مجهول باشد و ما بآسانی بتوانیم حاصلضرب آن را با هر گونه بردار معلومی محاسبه کنیم. هنگامی که سیستم خطی در رابطه با گسستگی مسائل خطی ناقص سمت راست b اطلاعات و فرضیات را مورد بررسی قرار دهد، نقش مسائل متوالی در ماتریس A افزایش می یابد و بنابراین حل مسائل برای یافتن خطا در داده ها مهم و ضروری به نظر می رسد. بمنظور حفظ خطا در نشان دادن صورت b برخی از روشهای بدست آوردن مجهولات بایستی مشخص شود در زمینه روشهای معکوس بمنظور حل مجهولات بواسطه توقف کردن تکرار قبل از همگرایی در حل سیستم های خطی بهتر است به تکرار های ناقص رجوع شود. تجزیه و تحلیل کامل در ویژگی های معلوم کردن به روش CG در معادلات کامل هنگامی که می توان از معیارهای بازدارندگی مناسب استفاده کرد در بخش ] 10 [ قابل بحث می باشد.
در صورتیکهM ماتریس معکوس باشد، براساس ویژگی های طیفی MA همگرایی سریعترین برای روشهای حل تکراری ایجاد می کند. ماتریس M ماتریس شرطی سمت چپ برای سیستم خطی(1) نامیده می شود قابلیت امتحان ماتریس M نشان میدهد که سیستم های (1) و (2) راه حل یکسانی دارند انتخاب یک ماتریس شرطی مقدم M نشان می دهد که چنین ماتریسی نه تنها ویژگی های طیفی ماتریس A را تغییر می دهد بلکه بمنظور حل سیستم های خطی با مضروب ماتریس A بآسانی می توان آن را در کل بردار ضرب کرد. در حقیقت در هنگام حل سیستم 2 به روش تکرار لازم است ضرب ماتریس در بردار را در فرم مورد محاسبه قرار دهیم. سیستم خطی (1) با معادله زیر قابل جانشینی است.
(3)
ماتریس معکوس
در صورتی کهM ماتریس معکوس باشد در این مورد M ماتریس شرطی اولیه را ست نامیده می شود و از آنجائیکه هنگام حل سیستم خطی لازم است ضرب ماتریس در بردار را که بصورت نشان داده می شود محاسبه کنیم حل سیستم خطی با ضریب ماتریس A نیز ضروری به نظر می رسد یکی از شرایط برای روشهای حل تکراری در سیستم های خطی را می توان در بخش 19 مشاهده کرد زمانی که سیستم خطی از پراکندگی مسائل ناقص خطی ناشی می شود لازم و ضروری است که این مسائل را حل کرد در عوض تغییر مسیر از شتاب دهنده های همگرا به یک افزایش دهنده کیفیت در حل مسائل محاسبه شده به هیچ روش امکان پذیر نمی باشد. علاوه بر آن سمت و جهتی که معکوس ماتریس بکار می رود بسیار مهم است.در حل تکراری مسائل خطی یک شرط اولیه سمت راست مرتبط با داده های کاملاً منسجم و موجود در مورد حل در حالیکه شرایط لازم الاجرای سمت چپ داده هایی در مورد تمایز ویژگی های آماری ارائه می دهد در حالی که کاربرد این فرضیات در رابطه با روشهای تکراری در سیستم های خطی مشابه و مسائل خطی ناقص بر هم مرتبط است ساخت این پیش فرضیات مناسب کاملاً متغیر بوده و در موارد بعدی برای فهم اینکه چگونه این پیش فرضیات بر کیفیت حل مسائل اثر گذارنده مهم بنظر می رسد.
برخی انواع داده های قبلی در مورد حل ممکن است قابل تغیر به یک تغییرات مناسب در جهت حل های تکراری باشد بعنوان مثال داده هایی در مورد حد های بالایی و پائینی در حل اعداد صحیح بواسطه مراحل ترسیم سازی، پس از ترسیم روش تقریبی روش های تکراری با استفاده از روش های حل ترسیمی بعنوان یک سری حدسیات اولیه جدید آغاز می شود رجوع شود به] 3 [ فرایند ادامه می یابد تا یک معیاری برای توقف حاصل شود این امر باعث می شود روشهای موثر محاسباتی نسبت به مدل های استاندارد تاثیر بهتری داشته باشد.
این مقاله به صورت زیر تنظیم شده است در بخش 2 ما مختصراً برخی از تحقیقات در زمینه روشهای تکراری کریلا و را برای مسائل ناقس و گسسته خطی مورد بررسی قرار می دهیم بخس 3 یک بررسی اجمالی در مورد نتایج آماری مورد نیاز می باشد بخش 4 رابطه بین پیش فرضیات و مسائل معکوس آماری" بایسیان" را با اطلاعات آماری در زمینه حل و نقص را عنوان میکند بخش 5 چگونگی استفاده از استراتژیهای ترسیمی را باری فائق آمدن بر حدهای بالایی و پائینی در حل مسائل نشان میدهد. در بخش 6 ما دیدگاهی را مورد چگونگی انتخاب حدهای مناسب برای یک مجموعه مسائل خطی ناقص هنگامی که راه حل هایی برای حل حدها بخوبی شناخته نشده باشد و چگونگی فائق آمدن بر آن ها را با پیش فرضیات سمت راست مورد بررسی قرار می دهیم. رابطه بین پیش فرضیات سمت چپ و ویژگی های آماری در بخش 7 می آید بخش 8 نمونه های حل شده ای از عملکرد پیش فرض ها و استراتژی های ترسیمی را در بخشهای پیشین ارائه می دهد. نتایج و رئوس مطالب در بخش 9 موجود است.
2 – رو شهای تکراری- پیش فرضها و مسائل ناقص
در این بخش ما نتایج مختصری در رابطه با روش های تکراری از پیش فرض شده برای استفاده خوانندگان برای ارائه یک سری اطلاعات آماری را نشان می دهیم خوانندگان با روشهای زیر فضایی" کریلا" و برای حل مسائل ناقص که در بخش بعدی خواهیم آورد آشنا خواهند شد حل های تکراری سسیتم های خطی معادلات ناشی از مسائل ناقص خطی یک روش انتخابی است که هنگامی که بعد مسائل آنقدر بزرگ باشد که فاکتورسازی ماتریس را غیرممکن سازد نقص ماتریسهای مضروب این سیستم های خطی آنقدر زیاد می شود که برخی فرمها و روشهای معلوم سازی نیاز است قاعده سازی" تیکانفر"از مهمترین رو شهای قاعده سازی بر سیستم خطی را مطرح می کند یکی دیگر از روشهای قاعده سازی و روشی که ما در این مقاله به آن اشاره می کنیم روش تکراری ناقص است که مبنای آن در جملات تکراری اولیه روش حل محاسباتی ما را بر یک حل صریح و معلوم هدایت می کند اما جملات تکراری ادامه دارد و اجزای ناقص برای مشخص کردن راه حلهای محاسبه شده می شود بنابراین برای ساخت روشهای تکراری منسب در حل مسائل ناقص گسسته خطی لازم است با معیارهای پایان دهنده مناسبی آشنا باشیم که از این تکراریات قبل از آغاز روشهای حل جلوگیری کنیم یک راه حل تقریبی اولیه را برای سیستم های خطی(1) در نظر بگیرید روش" کریلا" راه حل های تقریبی را با حل مسائل در یک زیرفضائی مناسب از یک بردار اولیه و ماتریس A قابل تمایز است ارائه می دهد. در بخش انتهایی این مقاله ما فرض خواهیم کرد که مسائل حل و زیر فضای
" کریلا" یعنی جائیکه چنین مسائلی قابل حل است رو شهای تکراری را نشان می دهد. اولین روش تکراری" کریلا" در حل مسائل گسسته خطی بکار می رود که ترکیبی از روشهای قبلی است از آنجائیکه روش های قبلی CG تنها هنگامی که ضرایب ماتریس مثبت باشد بکار می رود، در صورتی که سیستم خطی(1) سیستم بدون توان باش شکل های مختلف روش CG ، CGLS نامیده می شود که در معادلات معمولی بدون شکل واقعی معادلات معمولی مورد استفاده قرار می گیرد. روشهای CGLA,CG در بخش (9) a مورد بررسی قرار می گیرد.
روشهای تقریبی با روشهایCG در حل مسائل مینیموم سازی بکار می رود.
(5)
در اینجا یک مجهول صریح بوده و فضای فرعی" کریلا" می باشد .
روشهای تقریبی در معادلات تکراری با روشهای CGLS مسائل مینیمم سازی را حل میکند.
(6)
در صورتی که:
و نشاندهنده حالت هندسه اقلیدسی است.
کمیت های گسستگی سیستم های خطی(1) نامیده می شود که درواقع با حل های تقریبی در ارتباط است استفاده از روشهای CGLS برا ی حل مسائل ناقص گسستگی کمتر از حاصلضرب خطا در سمت راست باشد روش CGLS یک روش تشخیص مناسب است.
ایده مناسب از روش تکراری GMRES همواره با یک معیار پایان دهی مناسب بر ای حل معادلات ناقص و یا یک ماتریس جذری همراه است روشهای تقریبی با روشهای حل GMRES مسائل مینیموم سازی را حل می کند.
از آنجا که فضاهای فرعی" کریلا" در جائیکه مسائل مینیموم سازی حل شده قرار گرفته اند حالتهای گسستگی یک توالی را به حالت های طبیعی و بدون گسستگی درمی آورد. شکل تغییر یافته GMRES روش PRGMRES است که مسائل مینینوم سازی را در فضاهای فرعی" کریلا" حل میکند بنابراین در روش حل را به رتج A تبدیل می کند گرچه روش های محاسباتی پس از مراحل K از روش PRGMRES کاملاً متمایز از روش محاسباتی پس از مرحله k در روش CGLS است هر دو روش مسائل را به روش کاملاً در ستی حل می کند.
روشهایی که پراکندگی ساختار است و یا هنگامی که نقص زیاد است از این روش ها استفاده می کنیم برای ارائه بحثهای بیشتر در مورد PRGMRESبه بخش 6 مراجعه کنید بحث مربوط به حل روشهای تکراری فضاهای فرعی" کریلا" در مسائل ناقص در ] 4 [ دیده می شود.
دیدگاه اصلی این است که مشخص کنیم چگونه روش های تکراری ناقص با پیش فرضهایی برای مسائل ناقص ادامه پیدا میکند پس از 12 بسیاری از پیش فرضهایی با حضور اولیه مقادیر A که با سیگنال ها و یا نقص هایی روبرو است سپس صورتهای قبلی را با برطرف کردن آخرین نقص ها جمع میکنیم. این صورتهای پیش فرض 2 مساله اصلی را در بر می گیرد اولاً جداکردن طیفهای نوری همواره ساده نبوده و دوم اینکه مسائل جداسازی عموماً بر میزان اختلالات و نقص ها در سمت راست بستگی دارد.
یک دیدگاه کاملاً متمایز برای حل و برطرف کردن این نقصها روشهای تکراری ناقص در مسائل ناقص دارای پیش فرضها بعنوان ابزاری برای رفع 2 موضوع فوق می باشد که بهتر است از ویژگی های طیفی ماتریس A . اگر M معکوس باشد روش های حل سیستم های خطی دارای پیش فرضیات سمت راست برابر است با روش مربوط از سیستم اصلی بنا به آن پیش فرضیات سمت راست روش کاملاً متمایزی در حل معادلات می باشد بعلاوه از آنجائیکه حل مسائل ابتدایی و اصلی در رنج M صورت می گیرد اگر ماتریس از پراکندگی اپراتورهای متغیری حاصل شود روش امتحان آن یک روش ساده است. تغییر مسائل جذری اصلی بر مسائل شکل 2 با استفاده از ماتریس متمایز اولیه یا ثانویه و روش حل مسائل تغییر یافته با پیش فرضیات سمت راست الگوریتم CGLS در بخش آورده شده است. استفاده موثر از یک نسخه پیش فرض الگوریتم CGLS با چنین ماتریس هایی مفید به نظر می رسد اما از آنجائیکه آنها معکوس نیستند بعنوان پیش فرضهایی برای روشهای GMRES و RR GMRES مناسب نمی باشند.
پیش فرضهای معکوس مرتبط با اولین و دومین ماتریس های متمایز اخیراً مورد بررسی قرار گرفته این پیش فرضها در روشهای CGLS و GMRES مورد استفاده قرار گرفته و می توانند راه حل هایی با کیفیت های بهتر ارائه نماید هنگامیکه هیچ پیش فرض مورد استفاده قرار نمی گیرد هر چند در جملات با تکرا رهای کمتری نیازی به استفاده از آن نیست برای جزئیات بیشتر و مقایسه پیش فرضهای noninvertible, invertible به بخش] 7 [ مراجعه کنید.
بردارهای رندوم، شواهد و روشهای اثبات:
در این بخشها برخی مفاهیم اصلی در زمنیه تئوری احتمالات و بردارهای رندوم آماری را مورد بررسی قرار میدهیم مفاهیمی که در واقع یک امر کلیدی برای پیشرفت خواهد بود و بطور جزئی مورد بحث قرار خواهد گرفت خوانندگان آشنا با مسائل آماری و عددی بهتر این بخش را خواهند فهمید بقیه خوانندگان باید یک بررسی عمیق تری در مورد جزئیات انجام دهند.
ما با این فرض شروع می کنیم که یک بردار رندوم n بعدی است. ساختار توزیعی جمع پذیرx بصورت می آید.
در اینجا احتمالات موجود در پرانتز و مقادیر ثابت رندوم x متغیر می باشد در صورتیکه متوالی باشد ساختار چند متغیری از x شکل تغییر یافته براساس همه اجزای موجود در آن است.
و ساختار توزیعی ترکیبی 2 رندوم y,x متغیر به صورت و ساختار ترکیبی صورت تغییر یافته براساس تمامی جزء های y,x می باشد.
صورت مورد انتظار از رندوم متغیر x
بردار متوسط ازx بصورت است.
ارتباط I امین و j امین جزء های x است.
ارتباط ماتریس از بردار x تمامی این ارتباطات را نشان می دهد کوواریانس ماتریس از x یک ماتریس مرتبط با بردار می باشد.
بنابراین:
اگر چه همانظور که در شرایط واقعی اتفاق میافتد میزان و مقادیر متغیرهای x " گاسین" شناخته شده نیست اما یک مجموعه ای از نمونه ها مثل موجود است و می توان را براساس این نمونه ها با توجه به فرمول بدست آورد تخمین نهایی برای اندازه گیری میزان متوسط" میانگین نمونه" نامیده می شود پس و ماکوواریانس را از نمونه ای بواسطه کوواریانس نمونه تخمین می زنیم
دومتغیر رندوم x,y مستقل اند در صورتیکه
دو متغیر رندوم x,y غیر مرتبط به هم می باشند در صورتیکه
جزء های xدر صورتیکه کوواریانس ماتریس قطری باشد غیرمرتبط بوده اعداد صحیح قطبی واریانس از جزء های x ارائه می دهد. بردار x با رندوم n بعدی بردار نرمالی است اگر ساختارش به صورت زیر باشد.
ما از عبارات استفاده می کنیم بردارهای رندوم با میزان متوسط صفر و ماتریسی با کوواریانس مشخص را" سفید white " می نامیم بررسی کنید اگر x سفید و یک شکل تغییر یافته قائم باشد مثل پس نیز سفید است مسائل سفید را می توان با فرمول زیر بدست آورد یک متغیر x را در نظر بگیرید شکل تغییر یافته خطی بر آن به مانند نیز سفید است فرض کنید که x میزان متوسط صفری دارد اگر مقدار تجزیه شده بوده و مقادیر همگی مثبت باشند چک کردن این امر ساده به نظر می رسد که یک ماتریس سفید است.
ما نشان خواهیم داد که یک مساله سفید تنها یک راه حل ندارد در حقیقت برای هرگونه فاکتورسازی صورتی مانند یک ماتریس سفید است بویژه اینکه ما می توانیم V را بصورت شکل تغییر یافته ای از فاکتور " چالسکی" در نظر بگیریم. این مشاهدات یکی رویتی برای مشخص کردن پیش فرضهای چپ و راست است که اطلاعاتی را در مورد نواقص و راه حل متغیرهای رندومی در اختیار ما قرار می دهد.
4- معکوسات آماری، فرمول بایز و پیش فرضها
این مقاله استفاده از پیش فرضهای سمت راست را برای حل معادلات ناقص خطی با توجه به این نکته که انواع مختلف را ه حل ها به انواع مختلف پیش فرض اختصاص دارد مورد بحث قرار میدهد. از آنجائیکه با معرفی یک پیش فرش راست ما میتوانیم راه حلهای تقریبی را مورد ارزیابی قرار دهیم ارتباط بین پیش فرضهای راست برای هدفمند کردن اپرا تورها بمنظور قاعده سازی" تیکانو" لازم و ضروری به نظر می رسد. استفاده از روش های قاعده سازی تیکانو مرتبط با متغیر های اولیه و ثانویه کاملاً مشهور است. اپراتور های قاعده سازی معکوس" تیکانو" زمانیکه به صورت پیش فرض های سمت راست مورد استفاده قرار می گیرد با روش معکوس میتواند تاثیرگذار باشد از آنجائیکه انتخاب اپراتور های تیکانو یا پیش بردارهای سمت راست با ایده های قبلی ما در مورد روشهای حل تطابق دارد طبیعی است که آن را از منظر معکوس" بایسیان" نیز مورد بررسی قرار دهیم با فرض اینکه خوانندگان آشنایی چندی با این زمینه آماری ندارند برخی از نتایج اساسی و اولیه را براساس منظر فوق مورد بررسی قرار می دهیم. در مسائل" بایسیان" تمامی متغیرها، متغیرهای رندوم می باشد زیرا اگر فاقد آن باشد ما با کمبود اطلاعات در زمینه مقادیر مواجهیم براساس آن در صورتیکه B ،X و E متغیرهای رندوم و A ماتریسی معلوم باشد.
(9)
ما با مقادیر احتمالی قبلی x را نشان دادیم که صحه ای بر عقاید قبلی ما در رابطه با x قبل از تعیین مقدار B است اگر x یک متغیر رندوم Gaussian باشد.
و (10) فاکتورسازی" چالسکی" از عکس کوواریانس ماتریس xاست بنابراین انتخاب مناسب برای اپراتور قاعده ساز" تیخانو" ماتریس L است در معکوسات آماری حل مساله 9 با ارائه مقادیر برای متغیر x امکان پذیر است مقدار مشابه مشخص شده با فرمول مقدار احتمالی B است بر این مبنا که متغیر رندوم x برروی مقدار x برابر است باx . احتمال تراکم x که مسائل معکوس را حل می کند تراکم پسین در چهارچوب" بایسیان" نامیده می شود و اغلب با () نشان داده می شود و ارتباط بین تراکم های پسین و پیشین با فرمول" بایاس" مشخص می شود.
به محض اینکه تراکم پسین موجود شده تخمین ها و ارزیابی های مختلفی در مورد رندوم متغیر x بدست می آیند در این میان یکی از معروفترین آنها تخمین پسین ماکزیمم است
در صورتیکه E,x متغیرهای رندوم گاسین مستقل با Gaussian می توان نتیجه گرفت.
یا بطور مشابه
در صورتکیه s با تجزیه قابل تعریف است بنابراین MAP نشان می دهد که همچنین یک روش حلی" تیخانو" با اپراتور های قاعده است که از ماتریس کوواریانس قبلی و حداقل خطاهای جذری حاصل می شود خطاهایی که نتیجه تغییر مکان فاکتور" چالسکی" از عکس کوواریانس خطا حاصل می شود نشان داده می شود که:
در صورتیکه w مینی ملایر(کاهنده) این ساختار است.
مشاهدات بالا در مورد رابطه بین روشهای تکراری ناقص و روشهای" تیخانو" اتنقال میدهد که با حل سیستم های خطی تکراری می توان به نزدیک شد که پیش فرضهای (1) را از سمت چپ (12) مشخص و پیش فرضهای سمت راست را از فاکتور های" چالسکی" در مورد معکوسیت ماتریسهای کوواریانس معین می کند ما نشان دادیم با وجود اینکه ماتریسهای کوواریانس این راه حل ها و نقص های موجود در آن در سیگنال ها و پردازش تصاویر مورد استفاده قرار می گیرد زمانیکه فرآیند پاک سازی( سفیدکردن) یک مرحله میانی در بسیاری از الگوریتم ها است. با توجه به اطلاعات ما، پاک سازی" تبدیل" اطلاعات به پیش فرضهای مورد استفاده در روشهای ناقص تکرار، مساله جدیدی است. بمنظور بررسی مجدد مسائل معکوس آماری از منظر محاسباتی ما به یک کتاب کلاسیک] 21 [ رجوع می کنیم. بحث ها بالا چگونگی ساخت پیش فرضهای سمت راست را برای روشهای معکوس ناقص در مسائل ناقص تشریح می کند هنگامی که اطلاعات آماری مربوط به حل موجود باشد مدلسازی x به عنوان متغیر رندوم Gauosian که کوواریانس آن از نمونه بدست، بدست می آید قابل ساخت می باشد ما نشان دادیم که اغلب ماتریسهای کوواریانس براساس نقصشان دسته بندی می شوند زیرا نمونه ها باندازه کافی بزرگ نبوده یا نمونه های حاوی بردارهای مستقل خطی نمیباشد بمنظور جلوگیری از مسائل ماتریس تک جمله ای ما به کوواریانس های ساده یک ضریب کوچکی اضافه می کنیم تاثیر اینصورت از قاعده سازی کوواریانس تنها ایجاد متغیرهای ماتریس نمی باشد. انتخاب پارامترهای قاعده سازی ماتریسهای کوواریانس برای انعکاس ابعاد بی قاعده ای که قابل انتظار است یا تعیین ریشه دوم اپسیلونهای مکانیکی قابل تغییر است. بحث در مورد تاثیرات تقریب های برپایه نمونه و اهمیت قاعده سازی ماتریسهای کوواریانس برای انعکاس ابعاد بی قاعده ای که قابل انتظار است یا تعیین ریشه دوم اپسیلونهای مکانیکی قابل تغیر است بحث در مورد تاثیرات تقریب های بر پایه نمونه و اهمیت قاعده سازی و اریانسها در رابطه با دیدگاه تحلیلی اجزاء اصلی در بخش] 8 [ دیده می شود.
5- جبرهای حدی و روشهای تکراری ترسیم شده:
اثبات شده است که برخی اعداد صحیح در راه حل های نشاندهنده مقادیر جبری حدی مشخص می باشد. بعنوان مثال با استفاده فیزیکی از پارامترهای جبرهای حدی معمول برای حل مسائل ناقص موجود در تصاویر و پردازش های سیگنالی در صورتی که در مدلسازی واکنش های شیمیایی غیرمعمول نیست که برخی از راه حل ها به واسطه رنج های پارامتری خوب تعریف شده صورت گیرد در چهارچوب" بایسیان" این اطلاعات بخشی از اطلاعات قبلی است که کاملاً تجزیه شده است تا تمامی اطلاعات موجود به منظور ارزیابی را مد نظر داشته باشد. در این بخش ها بررسی می کنیم که چگونه این نسبت از مقدار اطلاعات قبلی را می توان و ارد یک حل کننده خطی معکوس کرد بعنوان مثال بدون نیاز به تعیین نقاط متذکر می شویم گرچه دیدگاه موجود در این بخش متمایز از دیدگاه بخش قبلی است این نمونه از چگونگی کاربرد موثر ویژگی های معکوس" بایسیان" در زمینه حل کنند های تکراری است.
حل محاسباتی سیستم های خطی که تغییرات جبری حدی را از شکل یک مساله خطی به غیرخطی نشان می دهد باعث افزایش پیچیدگی در محاسبات می شود اگر ما بخواهیم ثابت کنیم که راه حل محاسباتی یک مساله تواندار خطی با اعداد صحیح غیرمنفی همراه است ما بایستی از الگوریتم های برای تشخیص این جبرها استفاده کنیم در صورتیکه اما ابتدا مقادیر غیر جبری را محاسبه و سپس تمامی مقادیر منفی را به صفر برسانیم این روش حل عمدتاً روش حل بهتری خواهد بود این امر اغلب در مورد تصاویر فضایی صورت می پذیرد یعنی در شرایطی که حضور نقاط روشن برروی یک زمینه تاریک منجر به ایجاد نقاط مصنوعی می شود هنگامی که مثبت بودن(منفی نبودن) راه حلهای محاسباتی از آغاز کار مدنظر نیست در مقاله اخیر منفی نبودن راه حلهای محاسباتی با اولین محاسبه راه حل تقریبی با یک حل کننده خطی تکراری حاصل می شود. تزریق آن به یک مدخل چندگانه غیر منطقی و سپس آغاز مجدد ترسیم یک نمودار تکراری باید همراه کننده های روش حدسی اولیه برای چندین بار این فرآیند تکرار شد تا یک معیار متوقف سازی حاصل شود نسخه هایی از CGLS,RRGMRES,GMRE برروی مجموعه ای از مسائل تست شده موجود و عمل متوقف سازی پس از حاصل شدن ماده ای برای گسستگی مورد استفاده قرار گرفت. از آنجائیکه این روش بکارگیری جبری تنها مستلزم راه حلی برای سیستم های خطی با روش تکراری است تمامی اختلالات محاسباتی مربوط به مسائل جبری نمی شود. علاوه بر آن برای چندین نمونه مورد محاسبه قرار گرفته نتایج بهتر زمانی حاصل می شود که از یک روش تفسیر جبری استفاده شود متذکر می شویم هنگامی که (1) را با یک حل کننده مستقیم حل کنیم استفاده از عدم منفی ات بدون مطرح کردن آن مساله بعنوان یک مساله کاهش مقادیر چیزی امکان پذیر نمی باشد بنابراین روشهای تکراری بایستی بخوبی مدنظر قرار گیرد نه فقط بخاطر کارآئیش در حل مسائل ناقص با پراکندگی زیاد در نهاسیت خاطر نشان می کنیم که استراتژی ذکر شده بالا می تواند هم در ارتباط با پیش فرضهای راست و هم چپ اطلاعات زیادی در مورد حل بالا به ما ارائه دهد.
پیش فرضهای سمت راست و نقاط حدی
مسائل معموس که با استقرار یک سیگنال محدود از یک نمونه ناقص همراه است انتخاب یک شرایط حدی مناسب برای رسیدن به نتیجه مطلوب می تواند بسیار مهم تلقی شود. مساله چگونگی رسیدن به شرایط حدی برای سالیان درازی توسط افراد مختلف عموماً حذف نقض در تصاویر مدنظر بوده است یعنی در شرایطی که رسیدن به نتایج اشتباه میتواند خطرناک باشد و نتایج مختلفی نیز ارائه شده است که برای تعداد کثیری از مسائل موثر بوده اما برای تعداد یگری خطرناک بوده است به عنوان مثال هنگامی که در یک حدی جواب به صفر نزدیک می شود مشخص کردن شرایط حدی" دیریکلت" بسیار طبیعی است هر چند که این جواب ممکن است در برخی نسبت های حدی کاملاً متفاوت باشد نقاط حدی"دیریکلت" بمنظور تحت پوشش قراردادن خطوط افزایش یافته مصنوعی از بخشهای مرزی افزایش می یابد د رحالیکه در برخی مسائل مشخص شده است که نقاط حدی مناسب می باشند در مسائل دیگر این امر اثبات شده در راستای تشریح و تفسیر" تئوری بایسیان" ما با مسائل حاوی نقاط حدی روبرو شده و فرضیات حداقلی در مورد عملکرد این نقاط ارائه و اطلاعاتی برای ارائه یک راهکار نهایی دست می یابیم بنابراین می توانیم حدس بزنیم که راهکارهای دوبعدی عملکرد مناسبی برروی خطوط مرزی ایجاد می کند فیلسوف یونانی ارسطو اطلاعاتی در زمینه یک تخته سنگ ارائه داد ساخته شدن لایه به لایه یک تخته سنگ با بدست آوردن اطلاعاتی در مورد آن از آنجائیکه دیدگاه ما در مورد نقاط حدی( مرزی) ادامه مدل ارسطوست ما به آن نقاط مرزی ارسطویی می گوئیم باری کسب اطلاعات بیشتر به بخش] 2 [ رجوع شود.
بمنظور تشریح این که چگونه این دیدگاه برای ساخت یک پیش فرض سمت راست که ما آنرا پیش فرضی برای ارتباط با روش های قبلی می دانیم، فرض کنید یک نمونه ( مثال) تک بعدی از یکی از شرایط حدی نامعلوم را درنظر بگیرید. اگر برای توابع کامل شناخته شده باشد ما می توانیم یک پیش فرض براساس تقریبهای متمایز محدود از متغیرهای ثانویه در نقاط تکراری ایجاد کنیم.
در صورتیکه باشد ماتریس
در قاعده سازی تیکانو با صافی سطح در مرحله دوم مورد استفاده قرار می گیرد و به صورت پیش فرضهایی برای CGLS مورد استفاده قرار می گیرد و برای قراردادن در یک منظر" بایسیان" ما با فرض اینکه مقادیر حدی شناخته شده اند شروع می کنیم با فرض و با تقسیمات و پیشین بخشهای داخلی احتمالی در مورد مقادیر داخلی fاین فرضیات پیش می آید که مقادیر حدی مشخص است. ما فرض می کنیم از آنجائیکه در واقعیت مقادیر حدی مجهول است ما یک hypreior را برای آن می نویسیم در صورتی که کم بودن اطلاعات درباره به شکل ساختار متراکم احتمالی درآید بواسطه چهارچوب نرمال ما می نویسیم .در صورتیکه یک متغیر باشد ما در بخش زیر در مورد چگونگی انتخاب یک مقدار برای بحث خواهیم کرد. بنابراین پس از معلوم کردن متغیر x به صورت زیر در می آید.
در صورتیکه ماتریس باشد.
ماتریس ماتریس معکوس است و بنابراین یک توزیع نرمال خوب تعریف شده است بعد از آن ما باید تشریح کنیم که چگونه می توان مقداری برای پارامتر ای مشخص کرد که در یک معیار منطقی مستلزم وجود واریانس جزء بوده که بایستی در لایه های داخلی نیز متحدالشکل باشد بنابراین مقدار واریانس در نقاط انتهایی داخلی و در نقاط میانی را یکسان فرض می کنیم و در صورتی که جز باشد واریانس در رابطه با قابل توجیه است در صورتی که یک بردار واحد j امین استاندارد باشد نتایج بدست آمده از معادله(13) مقدار را نشان میدهد. در] 2 [ یک روش تقریبی موثر برای حل ارائه شده است ماتریس هم دومین سطح را در نقاط داخلی و هم فرضیات اولیه ها را در مورد مقادیر حدی شامل می شود ما به بعنوان یک پیش فرض مرزی( حدی) ارسطویی نگاه می کنیم نظرات نهایی در مورد پارامتر B هم در حال ارائه است. B تغییرپذیری کلی X را کنترل می کند و بطورکلی ناشناخته است و بعنوان یک مجهولی که باسیق معلوم شود شناخته شده است بنابراین ما را به سمت مدل سلسله مراتبی سوق میدهد. برای کسب اطلاعات جزئی در مورد چگونگی محاسبه hyperior ها به فصل 16 بخش 307 رجوع شود. در بخش 2 ما اطلاعات بیشتری را در مورد افزایش بعدی آن ارائه میدهد.
در ابعاد2 گانه صافی سطوح داخلی برروی مقادیر حدی امر مشروطی است.
پیش فرضهای سمت چپ و نقص ها
در 3بخش قبلی ما بحث کردیم که چگونه از یافت های قبلی در مورد محل پیش فرضهای ساختاری استفاده کنیم از آنجا که اطلاعات در مسائل ناهموار متناقص است ما میتوانیم از اطلاعاتی در مورد آمار مربوط به این اختلالات در حل کننده ها برای افزایش کیفیت روش های حل محاسباتی استفاده کنیم این امر در پردازش سیگنالی و ترسیم استفاده کنیم در صورتیکه سفیدکردن( از بین بردن) اختلالات و نقصها اغلب یک مرحله پیش پردازشی برای یک الگوریتم معکوس است. در چهارچوب حل کنند خطی تکراری این از بین بردن نقص ها عموماً با یک پیش فرض سمت چپ با استفاده از مدل 12 قابل تعریف است. در حالیکه نتایج بدست آمده در بخش 2 و 3 چندان تعجب برانگیز نیست از آنجائیکه اطلاعات ما شامل مثالهایی در زمینه پیش فرضهای سمت چپ برای مسائل ناقص که از ماتریس کوواریانس حاصل شده است نمی باشد. ما خاطر نشان می کنیم که کاربرد پیش فرضهای سمت چپ استفاده از پیش فرضهای سمت راست و استراتژی مختلف را دربر نمی گیرد. مثالی از تاثیرات مثبت و پیش فرضهای سمت چپ از مسائل آماری مشخص شده در مثالهای 5 و 6 بخش بعدی آماده است.
8- مثالهای محاسبه شده
در این بخش ما نتایجی از مثالهای مورد محاسبه را که استفاده آماری از پیش فرضها مشخص شده را نشان میدهد آورده ایم مثال:
در این مثال ما معادله کلی را می آوریم:
طرف سمت راست با استفاده از برنامه درایو 2 از ابزارهای تشخیص کد توسط هانسن با دیده شده، بدست می آید. برای جزئیات بیشتر به بخش 4 رجوع کنید. ما به سمت راست e, b را اضافه می کنیم مثل حل واقعی و حقیقی با یک نمودار صاف امکان پذیر بود و یک سیگنال ناقص قابل ارائه است بنابراین با بحث های موجود در بخش 2 و 3 مایک پیش فرض سمت راست را که سطوح و نقاط داخلی را مدل سازی می کند تعیین می کنند بعنوان مثال اپراتور متمایز کننده مرتبه دوم نقاط حدی به 2 روش مختلف بدست می آید. ابتدا ما فرض می کنیم که سیگنال در خارج از حوزه با دریافت ماتریس "توپلیتر" نقاطش پیشرفت کند، با عدد 2- در قطر اصلی و 1+ د ر قطر فرعی سپس فرضیه بعدی این است که سیگنال ها با نقاط افزایش یافته و این امکان را به نقاط مرزی می دهیم که هرمقداری را پذیرفته با فرض اینکه این نقاط، نقاط مستقلی اند که متغیرهای نرمال نامیده می شود. ما سیستم های فعلی را با پیش فرضهای سمت راست 13qr با استفاده از یکی از الگوریتم های CGLS که مشخص شده یک روش حل مناسب در حل مسائل جذری ناقص است حل می کنیم موارد شستگی برای پایان دادن این تکرارها بکار می رود. تخمین های محاسبه شده تقریبی MAP در شکل نشان داده شده است واضح و مبرهن است که در این مثال تعیین نقاط مرزی بسیار سودمند است در شکل مشاهده شده است که خطاهای حدی در همه شرایط دیده می شود.
مثال 2: یکی از مسائل مهم که در استفاده از پیش فرضها مدنظر است این است که آیا نقاط حدی به مسائل منفی در جایی که محلول در نقاط انتهایی ناپدید خواهد شد تاثیر گذار خواهد بود.
این مساله در معادله انتگرالی" فرد هلم" از نوع اول مورد بررسی قرار دهید:
با این روش حل روش کرنل و روش سمت راست
ما یک مسئله را با استفاده از زیرروال Phillips از ابزار تخشیص دهنده MATLAB که توسط هانسان با جمع آوری شده است ایجاد می کنیم بردار اضافه شده به B با تمایز یک متغیر رندوم نرمال سفید تا جائیکه شود حاصل شدنی است با سیستم خطی را با gmres ناقص با سه استراتژی پیش فرض مختلف که در مثا لهای قبلی عنوان شده بود حل می کنیم همانطور که در شکل 3و 4 می بینید نقاط حدی مشخص شده برای افزایش اطلاعات بطور منفی به نتایج نهایی محاسبه شده تاثیر نخواهد گذاشت. به مانند مثالهای قبلی ما از تکرار جلوگیری می کنیم به محض اینکه نرم گسستگی کمتر از نرم اختلال و تناقضات باشد.
مثال 3: در این مثال ما نشان میدهیم که چگونه اطلا عات د رمورد حدهایی بالا و پائین را میتوان برای بالابردن کیفیت حل های محاسباتی افزایش داد بدون انیکه پیچیدگی های محاسباتی افزایش می یابد. مدل کدها استفاده می کنیم معادلات انتگرالی" فرد هلم" می باشد در صورتی که fنقاط سفید وسیاه را بر بالای سمت چپ شکل 5 نشان داده و k یک " کرنل نرمال" باشد سیستم خطی(1) با پراکندگی مسائل جذری با پیکسل های بدست می آید کرنل با انحراف از معیار مساوی 4 با یک ماتریس تاپلیتر با پهنای باند مساوی با 12 از یک کدی از بسته ابزاری تشخیصی استفاده شده است مورد که بر سمت راست اضافه می شود متغیر نرمال سفید باندازه اجرا به تصاویر می باشد. تصاویر با شکل 5 جایگزین می شود. روش تکراری قابل استفاده ادر gmres براساس دیدگاه گسستگی متوقف می شود(25)grmes پس از سومین تکرار ، تکرار متوقف میشود ما این راه حل را با مجموعه ای از بردارها و نقاط بین 0 و 4 بدست و (25) grmes را از این حدسیات اولیه دوباره آغاز میکنیم. ما این مرحله را با 15 بار برای بدست آوردن تصاویر نشان داده شده در سمت راست در قسمت پائین شکل 5 بدست می آوریم نرم خطا برای حل های بدست آمده 29/0 است شکل 5 بطور واضح کاربرد آن را در مسائل بعدی نشان می دهد.
مثال 4: در این مثال ما موردی را در نظر می گیریم که بواسطه راه حلهای احتمالی برای حل ما در واقع یک پایگاه اطلاعاتی در مورد این راه حل ها داشته باشیم ما تعداد از دندانهای آسیاب در اندازه های مختلف با رندوم های ثابت را نشان می دهیم. ما فرض کردیم که ساختار این نقاط به صورت حد ماست. تشریحاتی جزئی در مورد اینکه چگونه پایگاه های اطلاعاتی ایجاد می شوند در بخش 8 نشان داده شده است این اطلاعات مجموعه ای از 60 پروژکشن پرتوی هوازی پرتونگاری است که زوایای توزیع شده از تا را نشان می دهد. تعداد نقاط در هر پروژکشن 60 عدد است بنابراین سایز بردار اطلاعتتی 3600 می باشد شکل هندسی این مساله در شکل 6 نشان داده شده است. ما به مقادیر مورد انتظار ماتریس کوواریانس از نمونه های باندازه 2000 نزدیک می شویم و از پیش فرضهای سمت راست محاسبه شده بواسطه نمونه ها استفاده می کنیم. برای حل سیستم خطی با از 1 sqr ناقص استفاده می کنیم ما فرض می کنیم که یک نمونه از راه حل های بخصوص با ویژگی های آماری مشابه به مشابه تراکم توزیع تراکم در ارتباط با اطلاعات موجود است. بنابراین ما شاخص ناقصی را انتخاب می کنیم تا جائیکه تعداد ماکسیمم نقاط افزایش نیابد و تعداد خطاهای مربوط کاهش یابد حداکثر 30 نقطه در 1 sqr وجود دارد شکل 7 مقادیر اورجینالی را نشا ن میدهد با بازسازی دوباره با 10 نقطه از 1 sqr بر سیستم خطی بدون پیش فرضها در نهایت بازسازی دوباره پس از 30 مرحبه از 1 sqr پیش فرضها در سمت راست.
مثال 5 : ما مثالهایی را که نشاندهنده اثر استفاده از پیش فرضهای سمت چپ مشخص شده از ویژگیهای آماری نقصهاست نشان میدهیم. در ابتدا ما یک مساله پرتونگاری 2 بعدی با زاویه محدود را مدنظر قرار میدهیم. هندسه یکی از این مثالهاست. در مدلسازی معکوس ما تصاویر را به پیکسل تقسیم می کنیم در شکل 8( سمت چپ) یک جذب کامل نشان داده شد ه است. شکل هندسی این مساله به مشابه مثالهای قبلی است. اطلاعات شامل یک بخش از سیدگرمهاست که اختلالاتی در آن شده است ما در فرضیات خود نشان دادیم که اطلاعات پروژکشنی در
بطور متناوب عاری از نقص است و متغیر استاندارد افزایش می یابد زمانیکه به میزان حداکثر افزایش پیدا می یابد زمانیکه سطح نقص 10 درصد از حداکثر سیگنال عاری از نقص باشد اطلاعات در شکل 8 نشان داده شده است خاطر نشان می شویم که در این مورد نقاط اختلال انگیز سفید نیست با استفاده از نقطه مختل کننده ای که زاویه تشریح کننده آن با امین نقطه باشد ما داریم:
که کوواریانس ماتریس را نشان میدهد ما یک فرآیندی را که در آن توزیع جذب توده ای ساده و بدرستی صورت می گیرد فرض می کنیم از آنجائیکه اطلاع خاصی در موردمقادیر مرزی در دسترس ما نیست و ما از وضعیت حدی ارسطویی با نقاط داخلی استفاده می کنیم بنابراین:
فاکتورها( چالسکی) و به سمت سیستم های خطی با پیش فرضهای سمت راست و چپ سوق داده می شود.
شکل 9 یک محاسبه بازسازی شده را با 20 مرحله از 1sqr را با پیش فرضهای سمت چپ و بدون استفاده از پیش فرضهای سمت راست نشان می دهد. دقت داشته باشید که بدون پیش فرضهای سمت چپ ورقه های مصنوعی به موزات خطوط شروع به پیدایس می کنند. با پیش فرضهای سمت چپ شروع به ناپدیدشدن می کنند. می توان نتایج را بآسانی تفسیر کرد. پیش فرضهای سمت چپ مقادیر کمتری را برای مشاهده ارائه میدهد. شکل 10 نتایج محاسبه شده را با یا بدون پیش فرضهای سمت چپ پس از 55 مرحله تکرار 1sqr نشان میدهد.
مثال 6: مثال آخر استفاده از پیش فرضها را با حضور نقص های ایجادشده مشخص می کند این یک مساله مدلسازی برای مسائل تصویر سازی 2 بعدی است که در بخش 9 مورد بحث قرار خواهد گرفت. f یک سیگنالی برروی پرانتز است.
جزء های نقطه نرمالی اند که با واریانس متسقلند با استفاده از این اطلاعات ما می خواهیم مقدار f محدود شده به حدفاصل فرعی را مورد ارزیابی قرار میدهیم.
ما انتگرال بالا را به صورت می نویسیم بخش اول حاوی اطلاعاتی در مورد تابع در فواصل موردنظر است در صورتی که بخش دوم بخش کلاتر حدی است.
ما پرانتز را به 3 پرانتز n3 و انتگرال های بالایی تجزیه می کنیم فرض کنید اولین جزءهای n مقادیرمورد نظر ماست در حالیکه جزءهای بعدی کلاتر های حدی است.
برای محاسبه کوواریاانس بردار w ما فرض می کنیم که x یک مقدار نرمال ارسطویی است با در نظر گرفتن(نقطه بین ) ما می توانیم توزیعات اصلی را به توزیعات حاشیه ای نزدیک کنیم.
با مشخص کردن ، ماتریس های کوواریانس حاشیه ای مربوطه، است در نتیجه کوواریس برابر است با:
این ماتریس غیرقطری است بنابر آن پیش فرضهای سمت راست در این مورد غیر تکراری است.
شکل 11 سه ساختار از سیگنال ها را با کرنل راندمان نشان میدهد. میزان اختلال( نقص) 1% از حداکثر سیگنال های کامل است در این مورد کلی تر حدی یک بخش از پیش تعیین شده این نقص است در شکل 12 ما نرم تمایزات بین بردارهای حقیقی و بردارهای دوباره ساخته شده به صورت تابعی از تکراریات نشان می دهد.
9- نتایج و کاربردهای آینده:
در این مقاله روشهای تکراری پیش فرضی را برای حل مسائل ناقص گسسته فعلی از دیدگاه" بایسیان" که دیدگاه های محاسباتی مختلف را به اطلاعات قدیمی در مورد حل و اختلال در اطلاعات پیوند می دهد مورد بررسی قرار میدهیم بطور دقیق تر ما نشان دادیم که چگونه ماتریسهای کوواریانس راه حل های صحیح را بواسطه پیش فرضهای سمت راست و چپ ارائه می دهد و چگونه اطلاعات قبلی از نوع پرانتزی در زمینه روش های تکراری قابل استفاده است در مواردی که اطلاعات در مورد حل بصورت اشکال متراکم نباشد مقادیر تقریبی مورد انتظار ماتریس کوواریانس مورد استفاده قرار می گیرد. کارهای بیشتر برای ایجاد پیش فرضهایی در این مقاله که برای مسائل با ابعاد بالا موثر است صورت گرفته و هنوز حاوی اطلاعات آماری گسترده ا ی است.
فهرست منابع
1) ای- بجارک روش های آماری در مسائل حداقل جذری SIAM ، فیلادلفیا پی ای 1996
2) دی ، کالوتی، جی کایپیو، ای سامسولا، نقاط حدی ارسطویی، اینترنت، محاسبات ریاضی(2006)
3) د ی، کالوتی، جی لاندی ال، ریشل، اف، روشهای تکراری مثبت برای مسائل ناقص، مسائل معکوس(2004) 20 ص 1758- 1747
4) دی، کالوتی، بی، لوئیس، ال، راشل ویژگی های قاعده سازی روش GMRES ریاضیات آماری (2002) 91 ص. 625-605
7) دی کالوتی، بی لوئیس ال، راشل مسائل ناقص گسسته و منحی ال BIT GMRES (2002) 42 ص 65-44
8)دی کالوتی، ال راشل ای شائبی پیش فرضهای تکراری برای مسائل خطی ناقص ریاضیات آماری کاربردی(2005) 54 ص 149-135
9) دی کالوتی، ال راشل، ای شائبی،پیش فرضهایی برای سیستم های خطی مسائل معکوس (2005) 21 ص 1418- 1379
10) ام هانک روشهایی از نوع نرمال برای مسئل ناقص لانگ سن نیویورک 1995
11) ام هان .پی سی هانسان روشهای تشخیص برای مسائل با مقادیر مجهول زیاد ریاضیات صنعتی(1993) 3 ص 312- 25 3
12) ام هانگ ، جی ناجی. آر. پلامن روشهای تشخیصی تکراری با پیش فرضهایی برای مسائل ناقس در راشل ای راتن .ار اس وارجا، جبرهای خطی آماریدی کریتو، برلین آلمان 1993 صفحات 163-141
13) ام هانگ جی، جی C و مرگان دیدگاه نیوتن برای تصاویر مثبت کاربرد جبری خطی(2000)316 ص 236- 2230
14) پی سی هانسان، مسائل ناقص گسسته SIAM ، فیلادلفیا PA ، 1998
15) پی سی هانسان، ابزارهای تشخیص سازی بسته های" مطلب" برای تجزیه و حل مسائل ناقص گسسته ناقص آمارا لگوریتم 611994 ص 35-1
16) ا جی کایپیو. ای سامه سالو – مسائل معکوس محاسباتی و آماری اسپیرنیگر برلین 2005
17) ام کا. آرج دابلیوسی تانگ الگوریتمی برای مدل ها با نقاط حدی نیومن – SIMA ، علم کامپیوتر (1999) 21 صفحات 866-851
18) ای- پاپیلوس – اس یوپیلای ، متغیرهای رندوم احتمالی و فرآیندهای اسکاتیک مک گرا – هیل نیویورک 2002
19) وای .سد روشهای تکراری برای سیستم های خطی SIAM فیلودلفیا PA ، 2003
20) اس. سراگپیزانو، یادداشتی در مورد نقاط حدی و مدل های سریع حذف نقص ها، علم کامپیوترپ(2004) 25 ص 1315-1357
21) ای تارانتول تئوری مسائل معکوس و ارزیابی پارامتر های مدلسازی SIAM فیلادلفیا PA 2004
60