مينيمم كردن توابع چند متغيره

ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ

يك طراحي مهندسي به تابعي به شكل زير مي رسد:

كه در آن x و y پارامترهايي هستند كه بايد انتخاب شوند و يك تابع است، كه مربوط به مخارج ساخت و ساز است و بايد مينيمم شود.
روش هاي قابل استفاده براي بهينه سازي كردن نقاط را در اين فصل مطالعه مي كنيم.

مقدمه:
يك كاربرد مهم حساب ديفرانسيل، پيدا كردن مينيمم موضعي يك تابع است. مسائل مربوط به ماكزيمم كردن نيز با تئوري مينيمم كردن قابل حل هستند. زيرا ماكزيمم F در نقطه اي يافت مي شود كه -F مينيمم خود را اختيار مي كند.
در حساب ديفرانسيل تكنيك اساسي براي مينيمم كردن، مشتق گيري از تابعي كه مي‌خواهيم آن را مينيمم كنيم و مساوي صفر قرار دادن آن است.
نقاطي كه معادله حاصل را ارضا مي كنند، نقاط مورد نظر هستند. اين تكنيك را مي توان براي توابع يك يا چند متغيره نيز استفاده كرد. براي مثال اگر يك مقدار مينيمم را بخواهيم، به نقاطي نگاه مي كنيم كه هر سه مشتق پاره اي برابر صفر باشند.

اين روند را نمي توان در محاسبات عدي به عنوان يك هدف عمومي در نظر گرفت. زيرا نياز به مشتقي دارد كه با حل يك يا چند معادله بر حسب يك يا چند متغير بدست مي آيد. اين كار به همان سختي حل مسئله بصورت مستقيم است.

مسائل مقيد و نامقيد مينيمم سازي:
مسائل مينيمم سازي به دو شكل هستند:نامقيد و مقيد:
در يك مسئله ي مينيمم سازي نامقيد يك تابع F از يك فضاي n بعدي به خط حقيقي R تعريف شده و يك نقطه ي با اين خاصيت كه

جستجو مي شود.
نقاط در را بصورت z, y, x و… نشان مي دهيم. اگر نياز بود كه مولفه هاي يك نقطه را نشان دهيم مي نويسيم:

در يك مسئله ي مينيمم سازي مقيد، زير مجموعه ي K در مشخص مي شود . يك نقطة
جستجو مي شود كه براي آن:

چنين مسائلي بسيار مشكل ترند، زيرا نياز است كه نقاط در K در نظر گرفته شوند. بعضي مواقع مجموعه ي K به طريقي پيچيده تعريف مي شود.
سهمي گون بيضوي به معادله‌ي

را در نظر بگيريد كه در شكل ۱-۱۴ مشخص شده است. به وضوح مينيمم نامقيد در نقطه ي
(۱و۱) ظاهر مي شود، زيرا:

اگر
مينيمم مقيد ۴ است و در (۰،۰) اتفاق مي افتد.
Matlab داراي قسمتي است براي بهينه سازي كه توسط اندرو گريس طراحي شده و شامل دستورات زيادي براي بهينه سازي توابع عمومي خطي و غير خطي است.
براي مثال ما مي توانيم مسئله ي مينيمم سازي مربوط به سهمي گون بيضوي نشان داده شده در شكل ۱-۱۴ را حل نماييم.
ابتدا يك M-file به نام q1.m مي نويسيم و تابع را تعريف مي كنيم:
function f=q1(x)

آنگاه از Matlab استفاده مي كنيم تا مقدار مينيمم را در نزديكي نقطه ي براي اين تابع بدست آورد:
type q1

بدست مي آوريم كه نقطه ي مينيمم (۱،۱) است و مقدار تابع در اين نقطه ۲ ميباشد.

۱-۱۴حالت تك متغيره:
اين حالت، حالت خاصي است كه در آن يك تابع F بر روي R تعريف شده باشد. ابتدا بررسي مي كنيم كه براي حل اينگونه مسائل چگونه بايد عمل كرد، زيرا مسئله ي عمومي تر n متغيره معمولاً با يك دنباله از محاسبات روي مسائل يك متغيره حل مي شود.
فرض كنيد است و ما بدنبال يك نقطه ي مي گرديم كه:

توجه كنيد كه اگر هيچ فرضي در مورد F در نظر گرفته نشود، اين مسئله در فرم عمومي غير قابل حل است. براي مثال تابع هيچ نقطه اي مينيممي ندارد. حتي براي توابع خوش تعريفي مانند محاسبات عددي ممكن است به مشكلاتي بر بخورد كه علت آن اعداد بزرگ نقطه ي مينيمم مطلق است.
به شكل ۲-۱۴ نگاه كنيد و مسئله ي كامپيوتري ۶ را ببينيد. توجه كنيد كه نقطه ي z يك مينيمم موضعي تابع F است اگر همسايگي از z وجود داشته باشد كه براي تمام نقاط داخل آن داشته باشيم:

ما مي توانيم از Matlab براي بدست آوردن مقادير مينيمم موضعي تابع استفاده كنيم. ابتدا ما تابع را در يك فايل به نام q2.m مطابق زير تعريف مي كنيم.

سپس از matlab براي يافتن مقدار مينيمم در بازه ي استفاده مي كنيم:
type q2

نقطه ي محاسبه شده ممكن است يك مينيمم مطلق نباشد. براي يافتن مينيمم مطلق مي توانيم نقاط اوليه ي متفاوتي را انتخاب كنيم و مينيمم هاي مطلق را بيابيم، آنگاه مينيمم آن ها را پيدا كنيم.

F تك نما :
يك فرض قابل قبول اين است كه در يك بازه ي [a,b] كه از قبل به ما داده شده، F تنها داراي يك مينيمم موضعي باشد. اين خاصيت معمولاً با گفتن اين كه F بر روي [a,b] تك نمايي است بيان مي شود.
(توجه:در علم آمار تك نمايي مربوط به ماكزيمم موضعي است)
بعضي توابع تك نمايي در شكل ۳-۱۴ نشان داده شده اند:
يك خاصيت مهم توابع تك نمايي پيوسته، كه از شكل ۳-۱۴ نيز مشخص است، اين است كه اين توابع بصورت يكنوا كاهش مي يابند تا به نقطه ي مينيمم مي رسند و بعد از آن بصورت يكنوا افزايش مي يابند. براي مشخص كردن اين موضوع، را مينيمم تابع F در بازه ي [a,b] بگيريد و فرض كنيد براي مثال F بصورت يكنوا بر روي بازه ي كاهش نمي‌يابد، آنگاه نقاط و وجود دارند كه:
و
حال فرض مي كنيم يك نقطه ي مينيمم روي بازه ي باشد. (توجه كنيد كه تابع پيوسته روي يك بازه ي بسته، مينيمم خود را اختيار مي كند) ما مي توانيم فرض كنيم كه براي اينكه اگر مقدار اوليه ، انتخاب مي شد، مي توانستيم آن را با جايگذاري كنيم، زيرا
ولي اكنون مي بينيم كه يك نقطه ي مينيم F روي است و
وجود دو مينيمم موضعي، البته با تك نمايي بودن F تناقض دارد.

الگوريتم جستجوي فيبوناچي
اكنون مسئله اي را مطرح مي كنيم كه مربوط به جستجوي نقطة مينيمم از تابع پيوسته و تك نمايي F بر روي بازة معين مي باشد. تا چه اندازه دقيق مي توان نقطة مينيمم را با فقط n ارزيابي از F محاسبه كرد؟ بدون هيچ گونه ارزيابي از F بهترين چيزي كه مي توان گفت اين است كه ، و با گرفتن نقطة مياني به عنوان بهترين تخمين، خطاي را مي دهد. يك ارزيابي به تنهايي اين موقعيت را ثابت نمي نمايد و بنابراين بهترين تخمين و خطا به مانند مورد قبل باقي مي ماند. بنابراين حداقل دو ارزيابي تابع را نياز داريم، تا تخمين بهتري را بدست آوريم.
فرض كنيد F در و محاسبه شده باشند، نتيجه در شكل ۴-۱۴ نشان داده شده. اگر چون در سمت راست صعودي است مي توانيم مطمئن باشيم كه . از طرف ديگر، استدلال مشابه در مورد نشان مي دهد كه . براي اينكه دو بازة فوق را به حداقل ممكن برسانيم را به چپ و را به راست حركت مي دهيم. بنابراين F مي بايستي در دو نقطة نزديك در هر طرف از نقطة مركزي ارزيابي شود، همچنانكه در شكل ۵-۱۴ نشان داده شده است. فرض كنيد:

با گرفتن نقطة مركزي زير بازة يا به عنوان بهترين تخمين از در مي يابيم كه خطا از فرا تر نمي رود. اين را خواننده به راحتي مي تواند تأييد نمايد.
براي n=3، دو ارزيابي در و از بازة را در نظر مي گيريم يعني و

از دو مقدار و ، مي توان تعيين نمود كه آيا و يا است البته هر دو مورد مشابه اند. فرض كنيد بنابراين نقطة مينيمم بايد در بازة باشد، همچنانكه در شكل ۶-۱۴ نشان داده شده است. سومين ارزيابي (نهايي) نزديك به انجام مي گيرد، براي مثال در اگر خواهيم داشت با گرفتن نقطة مركزي اين بازه، را به عنوان تخمين از بدست مي آوريم و در مي يابيم كه از طرف ديگر اگر آنگاه . دوباره نقطة مركزي را در نظر مي گيريم، و در مي‌يابيم كه بنابراين اگر از مقدار كوچك صرفه نظر كنيم، در سه ارزيابي F، دقتمان مي باشد.

با دامنة الگوي فوق در n ارزيابي از F به تخمين از مي رسيم كه خطاي آن از مقدار زير تجاوز نمي كند. در اينجا امين عضو از دنبالة فيبوناچي است.
(۱)
(۲)
براي مثال تا عبارتند از ۲۱،۱۳، ۸،۵، ۳، ۲، ۱، ۱
در الگوريتم جستجوي فيبوناچي در ابتدا تعداد مراحل N براي خطاي مطلوب را برابر انديس كوچكترين عدد فيبوناچي بزرگتر از انتخاب مي كنيم حال دنباله اي از بازه ها را تعريف مي كنيم. با شروع از بازة با طول و براي از فرمول هاي زير استفاده مي كنيم.

(۳)
در مرحلة قرار مي دهيم.

در نهايت به بازه مي رسيم كه از آن تخمين را بدست مي آوريم. اين الگوريتم بعد از مرحلة اول تنها به يك ارزيابي تابع در هر مرحله نياز دارد.
براي اثبات الگوريتم، موقعيت نشان داده شده در شكل ۷-۱۴ را در نظر مي گيريم از آنجا كه خواهيم داشت.
(۴)
بنابراين طول بازة مربوط با فاكتور كاهش يافته است، مرحلة بعد بدست مي دهد.
(۵)
عملاً فاصله بين است بنابراين يكي از نقاط قبلي كه در آن تابع ارزيابي شد در انتها يا طرف ديگر است يعني

با معادلات (۲)، (۴)،(۵).
با توجه به معادلة (۴) واضح است كه پس از ارزيابي تابع طول بازة نهايي برابر طول بازة ابتدايي خواهد بود، بنابراين طول نهايي است و خطاي ماكزيمم (۱) برقرار مي باشد. مرحلة نهايي شبيه به آنچه طرح شد مي باشد، و F در نقطه اي به فاصله از مركز بازة نهايي محاسبه مي شود و در نهايت از بازة نهايي قرار مي دهيم
يك عيب جستجوي فيبوناچي اين است كه الگوريتم، تقريباً پيچيده است. هم چنين، دقت مطلوب بايستي از پيش داده شود و تعداد مراحل محاسبه براي اين دقت قبل از شروع محاسبه تعيين مي گردد. بنابراين نقاط ارزيابي اوليه براي تابع F بستگي به N، تعداد مراحل دارد.
الگوريتم جستجوي نسبت طلايي
الگوريتم مشابهي كه اين معايب را ندارد در زير توضيح داده مي شود. اين الگوريتم به اين
دليل جستجوي نسبت طلايي ناميده شده كه به نسبت r كه به عدد طلايي در نزد يونانيان باستان معروف بوده، بستگي دارد.

اين عدد در معادلة صدق مي كند. در هر مرحله از اين الگوريتم، بازة از اعمال قبلي بدست مي آيد. اين بازه، بازه اي است كه مي دانيم شامل نقطة مينيمم است و هدف ما يافتن بازة كوچكتري است كه شامل باشد. در هر مرحله دو مقدار از F مورد نياز است.
(۶)
دو حالت ممكن است پيش بيايد: يا فرض كنيد حالت اول اتفاق بيافتد شكل ۸-۱۴ اين موقعيت را نشان مي دهد. از آنجا كه فرض شده F پيوسته و تك نمايي است، مينيمم Fبايد در بازة باشد. اين بازه، بازة ورودي در آغاز مرحلة بعد است. حال مشاهده مي كنيد كه يك ارزيابي از F در بازة موجود است (در y ) و همچنين داريم:

زيرا در مرحلة بعد y نقش x را بازي مي كند، و ما به مقدار F در نقطة نياز داريم. بنابراين كاري كه بايد انجام دهيم اين است كه اين جايگذاري ها را به ترتيب انجام دهيم.

حالت ديگر هم مشابه است. اگر نمودار، مشابه شكل ۹-۱۴ مي باشد. در اين حالت نقطة مينيمم بايد در بازة باشد. در اين بازه يك مقدار از F در x موجود است و همچنين داريم:

(مسئله ۹ را نگاه كنيد) بنابراين حالا x نقش y را بازي مي كند و مقدار F در نقطة محاسبه مي شود، جايگزاي هاي زير اين كارها را انجام مي دهد.

مسئله هاي ۱۱-۱۰ به كمبودي از اين فرايند اشاره مي كنند، بسيار كند است. كندي در اين بافت اشاره به تعداد زيادي از ارزيابي هاي تابع دارد كه براي كسب دقت منطقي مورد نياز است. مي توان حدس زد كه اين كندي منسوب به عموميت بسيار زياد (نهايت) الگوريتم مي‌باشد، هيچ مزيتي از اينكه F مي تواند هموار باشد حاصل نمي گردد.
اگر بازة آغازي در جستجوي مينيمم F باشد، در آنصورت در آغاز با يك ارزيابي از F مي توانيم فقط مطمئن باشيم كه نقطة مينيمم در بازه اي به طول است در جستجوي نسبت طلايي، طولهاي معادل در مراحل پي در پي براي دو ارزيابي از F و براي سه ارزيابي از F و به همين ترتيب بعد از n مرحله نقطة مينيمم در بازه اي به طول معين گرديده است. چگونه اين را با الگوريتم جستجوي فيبوناچي كه از n ارزيابي استفاده مي نمايد مي توان مقايسه كرد؟ طول بازة نهايي در اين الگوريتم است. اكنون، الگوريتم فيبوناچي بايد بهتر باشد، چونكه بگونه اي طراحي شده كه با تعداد مراحل تجويزي تا حد ممكن خوب انجام گيرد. بنابراين ما انتظار داريم نسبت بزرگتر از يك باشد ولي اين نسبت به ۱۷/۱ ميل مي كند (مسئله ۸ را ببينيد) در نهايت پيچيدگي اضافي الگوريتم فيبوناچي و بستگي آن به تعداد ارزيابي ها ممكن است استفاده آنرا به طور كلي كاهش دهد.

الگوريتم درونيابي درجة دوم(مربعي)
فرض كنيد F به صورت سري تيلور در همسايگي نمايش داده شده باشد.

از آنجا كه F در مينيمم است داريم پس:

اين به ما مي گويد، در همسايگي با يك تابع درجة دوم تقريب زده مي‌شود كه مينيممش در است. از آنجا كه مجهول است و نمي خواهيم كه مشتقات را داخل الگوريتم خود كنيم، يك راه حل معمولي اين است كه F را با يك چند جمله اي درجة دوم تقريب بزنيم(درونيابي). براي اين منظور از هر ۳ نقطه مي توان استفاده كرد. نقطة مينيمم تابع درجة دوم بدست آمده تقريب بهتري براي نسبت به و يا است. نوشتن الگوريتمي كه اين ايده‌ها را داشته باشد چندان ساده نيست و حالت هاي نامطلوب زيادي را بايد در نظر گرفت. براي مثال اگر درونياب درجة دوم به جاي مينيمم، ماكزيمم داشت چه كار بايد بكنيم؟ همچنين اين احتمال وجود دارد كه ، در چه صورتي جملات با درجات بالاتر از سري تيلور طبيعت F حول را مشخص مي كند.
در اينجا طرح الگوريتم اين فرايند آورده شده است. در ابتدا ما تابع F را داريم كه به دنبال مينيمم آن مي باشيم. دو نقطة آغازين x و y همراه دو عدد كنترل كننده و داده شده اند. محاسبات با ارزيابي و محاسبة دو عدد زير آغاز مي شود.

حال فرض كنيد

در هر حالت فرض مي كنيم
در اين مرحله سه نقطه x و y و Z و مقاديري تابع در نقاط مزبور يعني u و v و w را داريم. در هر مرحله از اين الگوريتم يكي از اين نقاط و مقدار تابع در نقطة مزبور با نقطة جديد ديگري و مقدار تابع در آن جايگزين مي شود. اين فرايند تكرار مي گردد، تا موفقيت يا شكستي حاصل گردد.
درمحاسبة اصلي، چند جمله اي درجة دوم q براي دورنيابي F در نقاط جاري x و y و z تعيين مي گردد. فرمول ها در زير بحث مي شوند. در مرحلة بعد نقطة كه تعيين مي‌گردد. تحت شراي ايده آل t نقطة مينيمم q و تقريبي از نقطة مينيمم F است. بنابراين يكي از نقاط، x و y و z بايستي توسط t جايگزين شود. حال ما علاقه مند به امتحان براي تعيين شكل منحني q در نزديكي t مي باشيم.
براي توصيف كامل اين الگوريتم فرمول هايي براي t و بايستي داده شود كه بدين شكل بدست مي آيند.

اشتقاق هاي آن ها در مسئله ۱۲ طرح گرديده است.
مسئله در صورت زير حل مي شود.

شرط خاطر نشان مي كند كه در همسايگي t صعودي است و بنابراين t نقطه مينيمم q است و شرط دوم بيان مي دارد كه اين تخمين t، از مينيمم F، در فاصلة ۴ از هر يك از سه نقطة x، y، z مي باشد. در اين حالت t به عنوان جواب پذيرفته مي شود.

حالتي كه معمولاً اتفاق مي افتد اين است كه:
و
اين نابرابري ها خاطر نشان مي كند كه t نقطه مينيمم q است اما به اندازة كافي به ۳ نقطة ابتدايي نزديك نيست كه به عنوان جواب پذيرفته شود، نيز t دورتر از واحد از هر يك از x، y، z نيست و بنابراين به عنوان نقطة جديد قابل قبول مي تواند پذيرفته شود در مرحلة بعد نقطة قديمي كه بزرگترين مقدار تابع را دارد اكنون جايگزين t و مقدار آن جايگزين F(t) مي‌شود.
اولين حالت بد زماني اتفاق مي افتد كه
و
در اينجا t نقطة مينيمم q است اما بسيار دور است و خطر استفاده از آن به عنوان نقطة جديد وجود دارد. در اين حالت ما يكي از سه نقطه اولي كه دورترين نقطه از t است را شناسايي مي‌‌كنيم، براي مثال x و نيز نزديكترين نقطه به t مثلاًً z سپس x را با و u را با F(x) جايگزين مي كنيم. شكل ۱۰-۱۴ اين حالت را نشان مي دهد.
دومين حالت بد زماني اتفاق مي افتد كه

اين نشان مي دهد كه t نقطة ماكزيمم q است در اين مورد بزرگترين و كوچكترين عدد در ميان u و v و w را شناسايي مي كنيم فرض كنيد سپس x را با جايگزين مي كنيم. يك نمونه در شكل ۱۱-۱۴ نشان داده شده است.

مسائل ۱-۱۴
۱-براي تابع نقطه اي مينيمم را پيدا كنيد. سپس نقطه ي مينيمم را روي مجموعه ي K تعيين كنيد كه K با اين نامساوي ها تعيين مي شود:

سپس مسئله را در حالتي حل كنيد كه K به صورت زير تعريف مي شود:

۲-براي تابع ، نقطه ي مينيمم را پيدا كنيد.
راهنمايي:قرار دهيد و
۳-اگر F روي بازه ي پيوسته باشد و فقط يك نقطه ي مينيمم موضعي داشته باشد در اين صورت F چند ماكزيمم موضعي مي تواند داشته باشد؟
۴-در الگوريتم جستجوي فيبوناچي، براي دو حالت عبارتي براي بدست آوريد.
۵-از چهار مرحله ي الگوريتم جستجوي فيبوناچي با قرار دادن استفاده كنيد و مقادير زير را مشخص كنيد.
الف)مينيمم تابع روي
ب)مينيمم تابع روي
ج)ماكزيمم تابع روي
۶-فرض كنيد F يك تابع پيوسته ي تك نمايي تعريف شده روي بازه ي باشد. فرض كنيد مقادير F در n نقطه ي داده شده باشد. چگونه مي توان نقطه ي مينيمم را فقط از ميان مقادير و به طور دقيق معلوم كرد؟
۷-مي دانيم اعداد دنباله ي فيبوناچي را رابطة بازگشتي بدست مي‌آيند كه يك دنباله ي بازگشتي خطي با ضرايب ثابت است. با فرض كردن به اين نتيجه برسيد كه دو مقدار مي تواند داشته باشد و با شرايط ابتدايي ضرايب A و B را محاسبه كنيد كه در آن و همچنين تحقيق كنيد كه
نشان دهيد اين نتايج با معادلات (۹) و (۱۰) در بخش ۳-۳ سازگارند.
۸-با توجه به الگوريتم نسبت طلايي و مسئله ي قبل ثابت كنيد و و ، سپس تحقيق كنيد كه به ميل مي كند وقتي .
۹-تحقيق كنيد كه در الگوريتم نسبت طلايي برقرار است.
راهنمايي:از استفاده كنيد.
۱۰-اگر F تك نمايي روي بازه اي به طول L باشد، حداقل چند مرحله بايد الگوريتم نسبت طلايي انجام گيرد تا نقطه ي مينيمم با خطاي كمتر از تقريب زده شود.
۱۱-درمسئله قبلي n چقدر بايد بزرگ باشد اگر L=1 و K=10؟
۱۲-با استفاده كردن از الگوريتم تفاضل تقسيمي بر روي جدول
z y x
w v u
نشان دهيد كه درون يابي درجه دوم با روش نيوتون به صورت زير است:

كه a و b و c از معادلة (۷) بدست مي آيند. سپس فرمول هاي مربوط به t و را كه در (۷) داده شده تحقيق كنيد.
۱۳-اگر ضرايب به راحتي بتوانند براي نوشته شوند، روش نيوتون براي پيدا كردن نقطه ي مينيمم F چگونه مي تواند به كار گرفته شود.
۱۴-اگر ضرايب موجود باشند روش سكانت براي پيدا كردن نقطه ي مينيمم F چگونه مي تواند به كار گرفته شود؟
۱۵-نسبت طلايي ، خواص بسيار زيادي دارد براي مثال:
الف)
ب)
ج)
د)
اين خواص را ثابت كنيد.

مسائل كامپيوتري ۱-۱۴
۱)برنامه اي بنويسيد كه الگوريتم نسبت طلايي را براي يك تابع داده شده روي يك بازه انجام دهد. جستجو بايد ادامه پيدا كند تا يك خطاي كران هاي از پيش تعيين شده بروز كند ولي از ۱۰۰ مرحله در هر حالت تجاوز نكند.
۲)ادامه برنامه‌ي مسئله ي قبلي را روي اين مثال ها اجرا كنيد و يا از يك نرم افزار مانند Matlab استفاده كنيد.
الف) روي
ب) روي
ج) روي
د) روي
۳)الگوريتم زير را براي تخمين زدن نقطه مينيمم يك تابع يك متغيره روي بازه ي به صورت يك برنامه بنويسيد و اجرا كنيد:
در اين الگوريتم يك دنباله از دوتايي هاي كه را تعريف مي كند كه در ابتدا و و در هر مرحله اعداد ، را به صورت زير جايگزين مي كند:
,

توجه:در اين عمليات همواره برقرار است و مينيمم F همواره بين aو b قرار دارد. علاوه بر اين بعد از اولين حالت ، تنها يك مقدار F لازم است كه در هر مرحله محاسبه شود. مقدارهاي به يك حد ميل مي كنند كه همان نقطه ي مينيمم F است. به تشابهات اين روش با روش تصنيف در بخش ۱-۳ دقت كنيد.
۴)يك برنامه براي الگوريتم جستجوي فيبوناچي بنويسيد و امتحان كنيد. الگوريتم جزئي زير را براي جستجوي فيبوناچي تحقيق كنيد كه در ابتدا:

سپس K را از N-1 تا ۳ تغيير دهيد و مقادير جديد را به صورت زير جايگزين كنيد.

مرحله ي را نيز به آن اضافه كنيد.
۵)(الگوريتم برمن )فرض كنيد F روي تك نمايي باشد. همچنين اگر دو نقطه باشند طوري كه داريم:
نشان مي دهد كه
نشان مي دهد كه
نشان مي دهد كه
پس با محاسبه ي F در و و مقايسه كردن مقادير تابع، ما مي توانيم اندازه ي بازه اي كه مي دانيم شامل است كوچكتر كنيم. ساده ترين روش اين است كه ما در نقطه‌ي مياني شروع كنيم، اگر F روي نزولي باشد F را در نقاط با امتحان كنيم تا به يك نقطه ي برسيم كه در آنجا F دوباره شروع به افزايش كند(يا اينكه به b مي رسيم) سپس ما همين عمل را با شروع از و استفاده كردن از عدد كوچكتر انجام مي دهيم. يك زير برنامه بنويسيد كه الگوريتم برمن را اجرا كند و آن را براي محاسبه ي تخمين مقدار مينيمم تابع تك بعدي F امتحان كند.
توجه:تعداد نهايي محاسبه ي F كه لازم است تا اين الگوريتم اجرا شود به مكان بستگي دارد. اگر براي مثال ، ما q محاسبه در هر مرحله لازم داريم و اگر تعداد مراحل را K بگيريم در نهايت به ، محاسبه نياز داريم. اين عدد هنگامي كه به نزديكتر شود كاهش مي يابد و مي تواند براي q=4 نشان داده شود. تعداد محاسبات مورد انتظار، سه تا در هر مرحله است. جالب است كه كارآيي الگوريتم برمن را با با الگوريتم جستجوي فيبوناچي مقايسه كنيم.
۶)يك برنامه از program library خود و يا از يك نرم افزار مانند Matlab انتخاب كنيد كه نقطه ي مينيمم يك تابع تك متغيره را پيدا كند. تابع را امتحان كنيد تا مشخص شود اين برنامه با چه مشكلاتي براي پيدا كردن مقدار مينيمم نهايي رو به رو مي شود. نقاط اوليه را هم نزديك و هم دور از مقدار مينيمم در نظر بگيريد.