جلسه دوم

در محاسبات عددی numerical analysis

 

مباحث این جلسه رو می تونید از طریق لینک زیر به صورت نسخه پی دی افی نیز دانلود کنید

دانلود جلسه دوم محاسبات عددی

جلسه دوم:

تا اینجا یه مقداری پیش نیاز های ریاضی رو بررسی کردیم و با یکی از کاربرد های محاسبات عددی آشنا شدیم ، الآن شما یک روش در دست دارید که می تونید با اون یه ریشه رو توی یه بازه به دست بیارید ولی اگه یادتون باشه گفتیم که انتخاب بازه اولیه مهمه ،همچنین گفتیم که تعیین شرط خروج به میل خودتون بستگی داره.

حالا فرض کنید که سه نفر داریم به نام های

جمشید 

خشایار

چنگیز

یه معادله f بهشون می دیم و می گیم که با استفاده از روش تنصیف ریشه f رو محاسبه کنند ، تضمین هم می کنیم که f تنها یه ریشه ساده داره.

این سه نفر به این صورت عمل می کنند:

جمشید بازه اولیه [2,20000] رو انتخاب می کنه و الگوریتم رو 20 بار اجرا می کنه

خشایار بازه اولیه [1,5] رو انتخاب می کنه و الگوریتم رو 3 بار اجرا می کنه

چنگیز بازه اولیه  [1,3]  رو انتخاب می کنه و الگوریتم رو 50 بار اجرا می کنه

فرض کنید که هر سه نفر بازه اولیه رو درست انتخاب کردند یعنی برای هر سه نفر بازه های انتخاب شده دارای شرط f(a)*f(b)<0 است.

سوالی که پیش میاد اینه:

1) جواب کدوم یکی از این سه نفر دقیق تره؟؟؟

2) دقیق ترین جواب چه قدر دقیقه؟؟؟اصلاً رضایت بخش هست؟؟ (ممکنه هر سه نفر گند زده باشن و جواباشون به درد نخوره)

اول بیایید بازه های انتخابی این سه نفر رو مورد بررسی قرار بدیم ببینیم کدومشون بازه بهتری رو انتخاب کرده:

به طور شهودی میشه گفت که انتخاب چنگیز انتخاب بهتریه چون طول بازه کوچیکتره ، ولی چرا ما بازه های با طول کمتر رو ترجیح می دیم؟؟

فرض کنید که بازه [a,b]  به ما داده شده و ما می دونیم که r ریشه معادله f عضوی از این بازه است ، ما می خواهیم نقطه ای به نام x عضوی از این بازه رو انتخاب کنیم و اون رو به عنوان تقریبی از r بیان کنیم .

چون هم r و هم x عضوی از بازه [a,b] هستند فاصلشون از هم دیگه نمی تونه بیشتر از فاصله ی b از a باشه درنتیجه اگه اختلاف r و x رو با |x-r| نشون بدیم (قدر مطلق تفاضل این دو مقدار) اونوقت:

به عبارت |x-r|  می گیم خطای مطلق.

این مقدار حداکثر اختلاف بین تقریب x و مقدار r رو نشون میده. در نتیجه قبل از شروع الگوریتم انتخاب چنگیز منجر به خطای کمتری میشه.

حالا ببینیم وقتی این سه نفر الگوریتم رو اجرا می کنن چه اتفاقی می افته:

قبل از شروع الگوریتم بازه ای که داریم بازه [a,b]  است ، خطای مطلق این بازه هم که بالا اشاره کردیم به صورت b-a  هست ، در اولین اجرای برنامه نقطه c وسط این بازه انتخاب میشه ، پس از این انتخاب ریشه یا تو سمت چپ c قرار داره یا سمت راستش و یا خودش ریشه است در هر صورت بازه جدیدی داریم که ریشه توشه و طول این بازه نصف طول بازه اولیه است( یا بازه سمت چپیه یا بازه سمت راستیه) پس بعد از اولین اجرای برنامه خطا به صورت زیر می باشد:

از اون جایی که پس از تعیین بازه جدید الگوریتم این بازه رو جایگیزین بازه قبلی می کنه ، پس فعلاً بازه جدیده طولش نصفه بازه اولیه است ، در دومین اجرای الگوریتم این بازه جدیده هم نصف میشه پس خطا به صورت زیر میشه:

 و پس از n بار اجرای الگوریتم خطا به صورت زیر خواهد :

خطای الگوریتم تنصیف پس از n تکرار:

می بینیم که خطا به صورت نمایی کاهش پیدا می کنه (همچنین می بینیم که جوابی که چنگیز حساب می کنه از بقیه دقیق تره ).

جواب قسمت دوم سوالی که در ابتدا مطرح شده بود رو خودتون حساب کنید (b=3,a=1,n=50).

خب تا اینجا با مفهوم خطای مطلق آشنا شدیم ، خطای الگوریتم تنصیف رو هم حساب کردیم ، ممکنه الآن پیش خودتون فکر کنید که الگوریتم تنصیف خیلی الگوریتم خفنیه ولی سخت در اشتباهید در ادامه پته این روش رو میریزیم رو آب :) .

همچنین ممکنه فکر کنید که خطای مطلق همیشه معیار خوبیه برای خطا ولی نشون می دیم که اینطور نیست.

مثال

هنگامی که از قلی می پرسیم فاصله تو از جایی که نشسته ای تا در یخچال که در آشپزخانه قرار داد چه قدر است پاسخ می دهد 9 متر ، محاسبات نشان می دهد فاصله دقیق او تا در یخچال 8 متر است در نتیجه قلی به میزان 1 متر در محاسبات خود اشتباه کرده است . هنگامی که از قلی می پرسیم فاصله تو از جایی که نشسته ای تا در اتاق مدیر دانشکده چه قدر است پاسخ می دهد 30329 متر.محاسبات نشان می دهد که فاصله دقیق او تا در اتاق مدیر دانشکده 30328 متر است لذا قلی به میزان یک متر در محاسبات خود اشتباه کرده است . 

مشاهده می کنیم که در هر دو حالت قلی به میزان 1 متر دچار خطا شده است در کدام یک از این دو حالت خطا به نظر شما قابل چشم پوشی است ؟؟؟

مطمئناً در حالت دوم (اینکه قلی چگونه می تواند فاصله خود تا دانشکده را اینگونه محاسبه کند همچنان بی پاسخ مانده است :) )

در اینجا به طور ذهنی برای قابل قبول بودن یا قابل قبول نبودن تقریب میزان خطای مطلق را با اندازه واقعی در مقام قیاس قرار می دهیم و سپس نظر می دهیم برای همین فکر می کنیم که خطای حالت دوم قابل چشم پوشی است  ، 

خطایی که در این حالت استفاده می کنیم به خطای نسبی معروف است و  به صورت زیر تعریف می شود.

اگر x تقریبی از r باشد خطای نسبی به صورت زیر خواهد بود:

توجه کنید که معمولاً به دلیل اینکه r از قبل مشخص نیست (و معمولاً بعداً هم مشخص نخواهد شد) لذا کمتر اتفاق می افتد که قادر به محاسبه دقیق خطای نسبی یا خطای مطلق باشیم ، در اکثر موارد سعی ما بر این است که برای این خطا ها یک حد بالا تعیین کنیم (مانند آن حدی که برای خطای الگوریتم تنصیف ارائه کردیم).

نکته: این که از خطای مطلق یا خطای نسبی استفاده کنیم به شرایط مسئله ای که قصد حل کردن آن را داریم بستگی دارد ، معمولاً هنگامی که r بزرگ باشد استفاده از خطای نسبی معیار مناسب تری است ، همچنین هنگامی که r نزدیک صفر باشد خطای مطلق معیار مناسب تری است.

فعلاً اجازه دهید تا کمی از مباحث نظری مربوط به خطا ها دور شویم و مجدداً به بررسی کاربرد ها بپردازیم.

تا الآن توانستیم یک حد بالا برای خطای الگوریتم تنصیف به دست بیاوریم ، سوال مهمی که الآن مطرح می شود این است : " آیا می توانیم قبل از شروع الگوریتم  تنصیف تعداد تکرار های لازم این الگوریتم برای اینکه خطا کمتر از مقدار معین eps باشد را تعیین کنیم؟؟؟" 

با اجازه بزرگ تر ها پاسخ این سوال مثبت است.:) :)

تا الآن تونستیم یه حد بالا برای خطای الگوریتم تنصیف تو تکرار n ام به دست بیاریم ، حالا می خواهیم ببینیم برای اینکه خطای این روش کمتر از eps بشه به چند تا تکرار نیاز داریم.

با توجه به حرف های بالا بعد از تکرار n ام باید داشته باشیم:

چون می خواهیم n رو به دست بیاریم باید اونو یه طرف به صورت جدا داشته باشیم،برای اینکار  2n رو می بریم اون ور ، b-a رو میاریم این ور:)

اینو میتونیم اینجوری هم بنویسیم:

حالا از طرفین لگاریتم می گیریم:

دیگه خواص لگاریتم رو جا نمیشه بخوام توضیح بدم (خودتون می دونید دیگه).

مثال:

برای یافتن ریشه معادله x2-2x-5=0  در بازه [3,4] با دقت 0.00001  به چند تکرار از الگوریتم تنصیف نیاز داریم:

در نتیجه برای این مسئله برای اینکه به دقت مورد نظر برسیم حداقل 17 تکرار لازمه.

نکته:مبنای لگاریتم رو هر چی که دوست دارید می تونید انتخاب کنید ولی بهتره اونو طوری انتخاب کنید که محاسبات ساده تر بشه معمولاً هم مبنای 10 انتخاب خوبیه ، من اینجا لگاریتم چند تا عدد رو تو مبنای 10 براتون آوردم که معمولاً به درد می خورن:

log(1) = 0.00
log(2) = 0.30
log(3) = 0.48
log(5) = 0.70
log(7) = 0.85
log(11) = 1.04
log(13) = 1.11
log(17) = 1.23
log(23) = 1.36

 

من اینجا تا دو رقم اعشار چاپ کردم ،ولی معمولاً تا یه رقم اعشار کافیه!!!!!(البته باید گرد کنید).

با اینکه خیلی دلم می خواد بیشتر رو این الگوریتم تنصیف بحث کنیم ،ولی باشه شاید در آینده ای نه چندان نزدیک دوباره روش بحث کردیم.

ولی فعلاً بیایید پرونده اش رو ببندیم:

نقاط قوت الگوریتم تنصیف:

1) شرطی که روی تابع f میزاره بسیار کمه (فقط کافیه که f توی بازه مورد نظر پیوسته باشه).

2)حد خطاش به سادگی قابل محاسبه است.

3)همواره همگراست (این مهم ترین خاصیتشه).

نقاط ضعف:

1) پیدا کردن بازه اولیه که شرط f(a)*f(b)<0 توش بر قرار باشه ممکنه سخت باشه.

2)همگراییش نسبت به خیلی از روش های دیگه کند تره(توضیح: اینکه می گم همگراییش کند تره یعنی اگه این و یه روش دیگه بخوان به یه دقت خاص برسن این روش نیاز به تعداد تکرار های بیشتری داره).

3) به راحتی نمیشه اون رو برای حل معادله هایی با ابعاد بیشتر بسط داد. (یعنی وقتی تعداد متغیر های تابع مورد نظر افزایش پیدا کنه دیگه به همین راحتی ها نمی تونیم از این روش استفاده کنیم.)

یه سری ضعف های دیگه هم داره این روش که فعلاً جاش نیست بگم.

و اما در مورد ضعف شماره یک:

چون متاسفانه عده قلیلی وجود دارن که بعد از دو سه خط کد زدن زارت ادعای برنامه نویسیشون میشه ممکنه که این عده قلیل فکر کنن که مشکل اول مشکلی نیست .

البته ممکنه یه عده غیر از دسته بالا (یعنی یه عده از غیر مدعیان) هم همچین فکری بکنند ، برای همین با مثال این موضوع رو مو شکافی می کنیم که خیال همه راحت شه:

فرض کنید که تابع کلی f به صورت زیر باشه:

(کی میگه این تابع پیوسته نیست؟؟؟؟؟)

این تابع رو برای M=2,M=20 و M=200 براتون رسم کردم:

M=2

خب مثل اینکه برای M=2 پیدا کردن یه بازه که توش f(a)*f(b)<0 باشه خیلی سخت نیست. 

حالا بریم سراغ M=20:

M=20

فکر کنم تو این حالت یه کم برای کامپیوتر یا هر ماشین محاسباتی دیگه یه مقدار پیدا کردن بازه مناسب برای شروع الگوریتم تنصیف سخت باشه.

و اما این هم M=200:

M=200

می بینیم که با افزایش M پیدا کردن بازه مناسب برای شروع الگوریتم تنصیف هم سخت تر میشه .

نکته:

خواهشاً نیایید بازه مناسب رو دستی پیدا نکنید بعد بیایید بگید " بابا این که کاری نداره ، بیا اینم بازه مناسب" :) ، اگه اینجوری باشه که خوب اصلاً ریشه رو هم دستی محاسبه می کنیم! ، پس توجه کنید که ما دنبال روش های الگوریتمی هستیم که بشه اونا رو توی یه ماشین محاسباتی (معمولاً کامپیوتر) پیاده سازی کرد و خود این ماشین بتونه مسئله رو حل کنه. برای همین وقتی میگیم پیدا کردن بازه مناسب تو مثال بالا سخته منظور اینه که نوشتن یه برنامه کامپیوتری که از ماهیت f از قبل خبر نداره و بخواد بازه مناسب رو برای الگوریتم تنصیف پیدا کنه خیلی کار ساده ای نیست. حالا از ما گفتن بود.:) :)

در ضمن مثال بالا فقط یه مثال بود!!!!!!!

نکته پایانی این قسمت:معمولاً از این الگوریتم به عنوان یک مرحله ابتدایی برای الگوریتم های دیگه استفاده می شه به این صورت که اول با این روش یه ریشه تقریبی به دست میاریم و بعد با یه روش سریعتر دقت ریشه رو بهبود می بخشیم.

 

نظرات

خسته نباشيد

دست شما درد نكنه!

ممنون

ممنون