مقدمه و جلسه اول

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

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

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

مقدمات:

هر کاری نیاز به یه سری مقدمات داره ، آدم غیبت هم که می خواد بکنه قبلش یه کم تخمه ای چیزی میاره که مجلس خوش بگذره:)

آنالیز عددی هم مثل بقیه کارا ، اونم نیاز به یه سری مقدمات داره ( حتی اون سری مقدمات هم نیاز به یه سری مقدامات دارن :) ) پس بهتره که قبلش اون مقدمات رو آماده کنیم.

جدای از هم این چرندیات که بالا نوشتم ، وجداناً آنالیز عددی درسیه که نیاز به پیش نیاز خاصی نداره و همین جوریش هم بسیار قابل درکه ،حالا کار نداریم تو دانشگاه ها ممکنه این درس رو بعد از یه درس دیگه ارائه بدن و بگن که این درس صد در صد نیاز به پیش نیاز داره ،ولی اینجا که دانشگاه نیست :) ،قوانینشون مال خوشون ، ما قانون خودمونو داریم :))

هدف آنالیز عددی در کل یه چیزه : آنالیز و تحلیل به روش عددی :)

یه زمانایی که هنوز کامپیوتر ماپیوتر ابداع نشده بود آدمهایی مثل نیوتن ( و از اون هم قدیمی تر آدمایی مثل Heron  ) دنبال روش های الگوریتمی یا تکراری بودن که بتونن با استفاده از اون روش ها به جواب های خاصی از بعضی مسائل با دقت خاص دست پیدا کنن،در ادامه سعی می کنیم با بعضی از این مسائل آشنا بشیم ،ولی در کل موضوع خیلی وسیع و گسترده ای و تو این چند خط نمیشه کمال مطلب رو فهمید :)

و اما پیش نیاز ها

حد تابع:

تعریف حد در ظاهر یکی از ساده تری تعاریف ریاضی (برای اونایی که الکی ادعا دارن) و در عمل یکی از پیچیده ترین مفاهیم ریاضی است .(اگه تو این جمله شک دارین برید ببیند نیوتن تونست به زبان ریاضی حد رو تعریف کنه یا نه؟؟ :) )

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

می گیم حد   تابع f در نزدیکی نقطه a برابر با L می باشد به طوری که هر وقت که به a نزدیک میشیم (ولی دقیقاً بهش نمی رسیم) اونوقت f به L نزدیک میشه.

به قولی :

یعنی اگه یه بازه بین L-e و L+e انتخاب کنیم اونوقت بتونیم یه بازه بین a-d و a+d انتخاب کنیم به طوری که به ازای همه x هایی که توی این بازه دومیه هستن f(x) a توی اون بازه اولیه نزدیک L باشه :O

یعنی توی شکل زیر هر چه قدر که دو تا خط افقی رو به هم نزدیک کنیم بتونیم دو تا خط عمودی متاظر با اونا رو پیدا کنیم  که شرط بالا توش صدق کنه(شکل از هم چیز بهتر توضیح میده)

(راستی این شکل دزدیه :این نکته رو در جهت حفظ امانت گفتم :) )

تعریف پیوستگی :

می گوییم تابع f در نقطه a پیوسته است اگر حد آن در این نقطه موجود و با مقدار تابع در این نقطه (a)  برابر باشد.

مشتق:

هر گاه تابع f در نقطه a تعریف شده باشد و حد زیر موجود باشد:

در این صورت می گوییم f در نقطه a مشتق پذیر است و حد فوق را مقدار مشتق f در نقطه a می نامیم و آن را با f'(a)a نشان می دهیم.

اینم تعبیر هندسی مشتق (مجدداً عکس دزدیه :)) )

قضیه:اگر تابع f در نقطه a مشتق پذیر باشد آنگاه f در a پیوسته است.

قرار داد:

اگر X زیر مجموعه از R باشد آنگاه مجموعه تمام توابعی که بر X دارای n مشتق پیوسته هستند را با Cn(X)a نشان می دهیم .همچنین تمام توابعی که از هر مرتبه مشتق پذیر هستند را با  C(X)a نشان می دهیم ( ex نمونه ای از این نوع توابع است).همین نماد گذاری را برای بازه [a,b] به صورت Cn[a,b]a به کار می بریم ، هنگامی که n=1 باشد از نوشتن آن صرف نظر می کنیم.

قضیه مقدار اکسترمم:

اگر تابع f عضو C[a,b]a باشد آنگاه نقاطی مانند c و d موجودند به طوری که :

اینم تصویر مربوطه به این قضیه :(این که این تصویر مال کجاست تابلوئه :) )

باور کنید این قضیه خیلی مهمه!!!!!!!!!

قضیه رُل (Rolle's Theorem):

اگر تابع f بر [a,b] پیوسته و بر (a,b)  مشتق پذیر باشد و f(a)=f(b)a باشد آنگاه نقطه ای مانند c که a<c<b وجود دارد به طوری که f'(c)=0 است.

اثبات:

چون f بر [a,b] پیوسته است پس بنا در این بازه هم مقدار ماکسیمم داره و هم مقدار مینیمم!

حالا این مقادیر اکسترمم یا در نقاط انتهایی بازه اتفاق می افتن ، یا یه جایی داخل بازه

اگه داخل بازه اتفاق بیفتن دو حالت داره : یا در این نقطه مشتق صفره یا تعریف نشده است ، ولی ما گفتیم که fدر (a,b) مشتق پذیره ، پس نمی تونه مشتق در نقاط اکسترمم تعریف نشده باشه.

اگه ماکسیمم یا مینیمم یه جایی داخل بازه روی نقطه c اتفاق بیفته a<c<b اونوقت f'(c)=0 و کار تمومه!اگه این حالت اتفاق نیفته اونوقت هم ماکسیمم و هم مینیمم باید روی نقاط انتهایی بازه اتفاق بفتن.

می دونیم که هر مقدار تابع f روی بازه [a,b] بین مقادیر ماکسیمم و مینیممش قرار می گیره.

حال چون در این حالت فرض کردیم مینیمم و کاسیمم روی نقاط انتهایی بازه اتفاق میفتن و چون f در این نقاط برابره (بنا به فرضf(a)=f(b)b) پس تمام مقادیر تابع روی این بازه بین f(a)a      و f(b)b قرار میگیرن (ساندویچ می شن:) ) و نتیجه می گیریم که تو کل این بازه :

f(x)=f(a)=f(b)b

و این یعنی این که f یک خط افقیه که مشتق همه جاش صفره ، پس هر جای این بازه که عشقمون کشید می تونیم یه c انتخاب کنیم که توش f'(c)=0 باشه و تمام.

حالا بریم سراغ یه قضیه با حال تر و مهم تر:

قضیه مقدار میانگین (Mean Value Theorem):

اگر تابع f(x)a بر بازه [a,b] پیوسته و بر (a,b) مشتق پذیر باشد آنگاه نقطه ای مانند cبه طوری که a<c<b وجود دارد به طوری که:

اینم دو تا شکل که این قضیه رو توضیح می دن:

خب فکر کنم که شکل همه چیز رو خوب نشون میده ، اگه تو شکل های بالا نقطه a رو ثابت نگه دارم و تابع رو طوری بچرخونیم که f(b)b مقابل f(a)a قرار بگیره (یعنی بعد از چرخش داشته باشیم f(a)=f(b)b ) اونوقت این میشه همون قضیه رل ،ولی خب چون این استدلال خیلی خودمونیه بزارید یه استدلال درست درمون بیارم که قانع شید:

اثبات:

فرض کنید داشته باشیم:

 با استفاده از مقدار m یک تابع جدید معرفی می کنیم به نام g و به صورت زیر:

g(x)=f(x) - m*(x - a) - f(a)a

dچون g'(x)=f '(x) - m (از تعریف g مشتق بگیرید) پس g(x)b هم مثل f(x)b تو کل بازه مشتق پذیره.

داریم g(a)=f(a) - m*(a-a)-f(a) =0 و

g(b)=f(b) - m*(b-a) - f(a)a

با جایگذاری تعریف m به جای m داریم:

پس g(a)=g(b)=0 ،پس بنا به قضیه رُل نقطه c ای بین a و b وجود داره که g'(c)=0 ،ولی چون g'(c)=f'(c) - m نتیجه می گیریم که g'(c)=0=f'(c) - m =0 و این یعنی f'(c)=m

 و اگه تعریف m رو به جای m بزاریم اثبات قضیه به پایان میرسه(دیگه این کار رو خودتون انجام بدین)    :).

و اما شاخ قضیه های این بخش :

قضیه مقدار میانی (Intermediate Value Theorem):

اگر تابع f(x)x بر بازه [a,b] پیوسته باشد و K مقداری بین f(a)a و f(b)b باشد آنگاه نقطه ای مانند c در [a,b] وجود دارد به طوری که f(c)=K.

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

نمه نمه دیگه بریم سر اصل مطلب!!!!

حل معادله f(x)=0 یا همون پیدا کردن ریشه معادله f(x)x:

فرض کنید که یه تابع f داریم و می خواهیم یه ریشه اون رو پیدا کنیم؟؟؟ چه راهی پیشنهاد می کنید؟؟؟اگه تابع یه چند جمله ای درجه یک یا دو باشه ،زارت از همون فرمول معروفه استفاده می کنیم و جواب رو به دست میاریم ، ولی اگه درجه چند جمله ای زیاد باشه یا اصلاً تابع مورد نظر چند جمله ای نباشه چه گلی به سرمون بزنیم؟؟؟:)

در ادامه سعی می کنیم یه روش هایی رو بررسی کنیم که یه ریشه معادله رو پیدا می کنن.

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

حالت خاصی از قضیه رل:

فرض کنید که f روی بازه [a,b] پیوسته باشه و تابع روی این بازه یه سرش زیر محور x=0 باشه و سر دیگه اش بالای محور x=0 یعنی داشته باشیم f(a)*f(b)<0 ،اونوقت ادعا می کنیم که تابع توی این بازه یه صفر داره .( وقتی می گیم تابع یه صفر داره یعنی یه نقطه ای وجود داره که تو اون f(x)=0  است.

مثل شکل زیر:

توجه کنید که عکس قضیه بالا درست نیست ، یعنی اگه f(a)*f(b)>=0 باشه نمی شه گفت که f توی این بازه ریشه نداره ، مثل شکل زیر:

خب ، حالا که چی؟؟؟گیریم که یه بازه داشته باشیم که توش f(a)*f(b)<0 باشه ، چه دخلی به حال ریشه f توی این بازه داره؟؟؟

ببینیم چی کار می شه کرد؟؟

اگر c نقطه وسط a و b  باشه (یعنی c=(a+b)/2 ) اونوفت f(c)c سه حالت داره:

1) یا f(c)=0 است که در این حالت c ریشه f  است (این "است" خیلی ضایعست:) ، ولی جایگزین خوب براش ندارم:) ) .

2) f(c)>0  است ، در این حالت یا f(c)c با f(b)b هم علامته یا با f(a)a ، اگه f(c)c با 

f(b)b هم علامت باشه اونوقت با f(a)a مختلف العلامته ، پس یه ریشه توی بازه [a,c] داریم ، اگه f(c)c با f(a)a هم علامت باشه اونوقت با f(b)b مختلف العلامته پس یه ریشه تو بازه [b,c] داریم ، در هر صورت پس از محاسبه c می تونیم توی یه بازه که نصف بازه اولیه است به دنبال ریشه باشیم.

3) اگر f(c)<0 باشه هم استدلالی مشابه با استدلال بالا میاریم.

نتیجه کلی رو میشه به صورت یک الگوریتم تکراری در آورد که به الگوریتم تنصیف مشهوره:

الگوریتم تنصیف(Bisection Algorithm):

تابع پیوسته f و بازه [a,b] داده شده است به طوری که f(a)*f(b)<0 (توجه کنید که این شرط ضروریه شروع الگوریتمه ).

1) نقطه c=(a+b)/2  را محاسبه می کنیم.

2) اگر sign(f(c))=sign(f(a))a آنگاه قرار می دهیم a=c و b=b (یعنی b بدون تغییر می مونه)

و به 4 می رویم.

3) اگر sign(f(c))=sign(f(b))b آنگاه قرار می دهیم a=a و b=c .

4) اگر بازه مورد نظر به اندازه کافی کوچک باشد آنگاه می توانیم c را به عنوان تقریبی از ریشه f بیان می کنیم.در غیر این صورت به 1 می رویم.

نکته:برای خروج از الگوریتم بالا می تونیم چند تا شرط بزاریم و با یکی از اونا از برنامه خارج بشیم:

1) f(c)c به اندازه کافی به صفر نزدیک بشه ( اندازه کافی که دیگه به نظر خودتون بستگی داره)

2) بازه مورد نظر به اندازه کافی کوچیک شده باشه.

3) الگوریتم به تعداد مورد نظر (مثلا M تا ، که M هم به خودتون بستگی داره) تکرار شده.

نکته:به جای اینکه از شرط f(a)*f(b)<0 استفاده کنیم ، علامت های f(a)a و f(b)b رو با هم مقایسه می کنیم ، چون وقتی بازه کوچیک میشه استفاده از ضرب میزان خطاش زیاده !!!!!!

و اما کد نویسی:

اول کد sign که بچه بازیه:) :

و اینم کد الگوریتم تنصیف :

تو کد بالا مقادیر M و delta و eps رو هر جور که خودتون دوست دارید مقدار دهی کنید .

تابع f تو کد بالا یه تابع است که مقدار تابع ریاضی ای که قصد داریم ریشه اش رو محاسبه کنیم ،توی یه نقطه خاص محاسبه می کنه.

نکته : استفاده از c=(a+b)/2 ممکنه به دلیل خطاهای کامپیوتری باعث بشه که c خارج بازه بیفته به جاش بهتره که c رو به صورت c=a+e محاسبه کنید!!!!

e همیشه اندازه نصف بازه رو نگه می داره.

نکته دیگه ای هم اگه مونده خودتون بگید( تو رو خدا تعارف نکنید :) )

 

نظرات

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

دست شما درد نكنه....! در انتظار مطالب بعدي هستيم!!

ممنون ، مطالب بعدی رو هم می

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