حل دستگاه معادلات دیفرانسیل خطی

یکی از کاربردهای مهم ماتریس نمایی در حل دستگاه معادلات دیفرانسیل معمولی است. برای بررسی این موضوع ابتدا قضیه­‌ی زیر را بیان می­‌کنیم.

قضیه: فرض کنید $A\in {{\mathbb{R}}^{n\times n}}$ و تابع برداری $w~:\mathbb{R}\to {{\mathbb{R}}^{n}}$ پیوسته باشد. در این صورت جواب مسأله‌ی مقدار اولیه‌­ی\begin{cases}{X}'\left(t\right)=AX\left(t\right)+w\left(t\right) \\X\left({{t}_{0}}\right)={{X}_{0}}\in{{\mathbb{R}}^{n}} \end{cases} به ازای هر $t\ge {{t}_{0}}$ به‌صورت زیر خواهد بود:

$$X\left( t \right)={{e}^{\left( t-{{t}_{0}}\right)A}}{{X}_{0}}+ \int_{{t}_{0}}^{t} \,{{e}^{\left( t-s \right)A}}w\left( s \right)ds.$$اثبات: با ضرب معادله­‌ی دیفرانسیل در ${{e}^{(-tA)}}$ داریم: ${{e}^{-tA}}{{X}^{'}}\left( t \right)-{{e}^{-tA}}AX\left( t \right)={{e}^{-tA}}w\left( t \right)$ که معادل است با:$$\frac{d}{dt}({{e}^{-tA}}X\left( t \right))={{e}^{-tA}}w\left( t \right)$$با انتگرالگیری از طرفین این رابطه روی بازه‌­ی $\left[ {{t}_{0}},t \right]$، داریم

$$\int_{{t}_{0}}^{t}\frac{d}{dt}({{e}^{-sA}}X\left( s \right))ds=\int_{{t}_{0}}^{t}\,{{e}^{-sA}}w\left( s \right)ds$$ بنابراین:$${{e}^{-tA}}X\left( t \right)-{{e}^{-{{t}_{0}}A}}X\left( {{t}_{0}} \right)=\int_{{t}_{0}}^{t}\,{{e}^{-sA}}w\left( s \right)ds$$ و در نتیجه با ضرب طرفین این رابطه در ${{e}^{tA}}$ خواهیم داشت:

$$X\left( t \right)={{e}^{\left( t-{{t}_{0}} \right)A}}{{X}_{0}}+\int_{{t}_{0}}^{t}\,{{e}^{\left( t-s \right)A}}w\left( s \right)ds.$$ حال به کمک قضیه­‌ی بالا، برنامه­‌ی Matlab حل یک دستگاه معادلات دیفرانسیل خطی نمونه را به صورت زیر می‌نویسیم.

clear

clc

syms s t

A=[7 -4 ;8 -5]

w_t=[exp(t);exp(t)]

X0=[1;2]

X_t=expm(t*A)* X0+int(expm((t-s)*A)*(subs(w_t,t,s)),s,0,t);

disp('the solution X(t) is:')

X_t

این برنامه دستگاه زیر را حل می­‌کند:$$\left\{\begin{matrix}{{x}_{1}}^{'}=7{{x}_{1}}\left(t\right)-4{{x}_{2}}\left(t\right)+{{e}^{t}},   {{x}_{1}}\left( 0 \right)=1 \\{{x}_{2}}^{'}=8{{x}_{1}}\left(t\right)-5{{x}_{2}}\left( t \right)+{{e}^{t}},    {{x}_{2}}\left(0\right)=2\\\end{matrix} \right.$$و خروجی آن عبارت است از:

$$X\left(t\right)=\left( \begin{matrix}{{x}_{1}}\left(t\right)\\{{x}_{2}}\left(t\right) \\\end{matrix} \right)$$

که در آن:$$\left\{\begin{matrix} {{x}_{1}}\left( t \right)={{e}^{-t}}-\frac{1}{2}{{e}^{t}}+\frac{1}{2}{{e}^{3t}},  \\ {{x}_{2}}\left( t \right)=2{{e}^{-t}}-\frac{1}{2}{{e}^{t}}+\frac{1}{2}{{e}^{3t}}. \\\end{matrix} \right.$$

آشنایی با روش‌های بهینه‌سازی نامقید (2)

نظریه‌‌ی الگوریتمی بهینه‌سازی نامقید

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

مثال: مطلوب است کمینه‌سازی $f\left( {{x}_{1}},{{x}_{2}} \right)=x_{1}^{2}-{{x}_{1}}{{x}_{2}}+x_{2}^{2}-3{{x}_{2}}$ .

حل: با مساوی صفر قرار دادن مشتقات جزئی مرتبه اول $f$، به دستگاه معادلات زیر می‌رسیم:

$$\begin{align}  & 2{{x}_{1}}-{{x}_{2}}=0 \\  & {{x}_{1}}+2{{x}_{2}}=3  \end{align}$$

این دستگاه معادلات دارای جواب یکتای ${{x}_{1}}=1$ و ${{x}_{2}}=2$ است. از طرفی، ماتریس هسین تابع $f$ در این جواب برابر است با:

$$H={{\nabla }^{2}}f\left( 1,2 \right)=\left( \begin{matrix} 2 & -1\\ -1 & 2\\\end{matrix} \right)$$

که معین مثبت است. بنابراین نقطه‌ی $\left( 1,2 \right)$ کمینه‌ی سراسری تابع $f$ می‌باشد.

در بسیاری از مواقع، دستگاه معادلاتی که از برقرار ساختن شرایط لازم به‌دست می‌آید، به سادگی قابل حل نیست و هر قدر که ابعاد مسئله گسترش یابد، این دستگاه پیچیده‌تر می‌گردد. به‌ویژه هنگامی ­که تابع $f$ نامحدب باشد، دیگر نمی‌توان از قضایای شرایط لازم و کافی استفاده کرد. در چنین مواقعی لازم است از شیوه‌های عددی‌ که جواب مسئله را با دقت مناسب محاسبه کرده و نیز از نظر محاسبات، زمان انجام و حجم حافظه‌­ی اشغال‌­شده مقرون به‌­صرفه باشند استفاده کنیم. در ادامه‌ی این آموزش به ارائه‌ و تحلیل برخی از این روش‌ها پرداخته می‌شود. اگرچه زمینه و انگیزه‌ی طرح این روش‌ها و جزئیات تحلیل آن‌ها تفاوت‌های بسیاری با هم دارند، تقریباً همگی دارای جنبه‌ی مشترکی هستند و آن این‌که تمام این روش‌ها از نوع الگوریتم تکراری کاهشی هستند؛ هر یک از آن‌ها از یک نقطه‌ی اولیه مانند ${{x}_{0}}$ شروع نموده و با تولید دنباله‌ای مانند $\left\{ {{x}_{k}} \right\}$ از نقاط به پیش می‌روند به‌طوری که هر نقطه‌ی جدید، تقریب بهتری از جواب بهینه را به دست می‌دهد. به این معنی که $f\left( {{x}_{k+1}} \right)\le f\left( {{x}_{k}} \right)$. البته الگوریتم‌های غیر یکنوایی نیز وجود دارند که لزوماً در هر تکرار مقدار تابع $f$ را کاهش نمی‌دهند ولی پس از $m$ تکرار این اتفاق می‌افتد، یعنی:

$$f\left( {{x}_{k+m}} \right)\le f\left( {{x}_{k}} \right).$$

نقطه‌ی اولیه‌ی ${{x}_{0}}$ را می‌توان با توجه به مقتضیات مسئله به‌گونه‌ای که نزدیک به جواب واقعی مسئله باشد، یا توسط یک الگوریتم دیگر یا به دلخواه اختیار نمود. تولید دنباله‌ی نقاط $\left\{ {{x}_{k}} \right\}$ تا جایی ادامه می‌یابد که یا نتوان نقطه‌ی بعد را محاسبه نمود یا این ‌که نقطه‌‌ی به‌دست آمده تقریب مناسبی از کمینه‌ی مسئله باشد. برای این‌که بدانیم که یک شیوه‌ی تکراری، به تقریب مناسبی از کمینه‌ی مورد نظر رسیده است یا خیر، معمولاً یکی از شرط‌های

$\left \| x_{k+1} -{x_{k}}\right \|< \varepsilon$      یا     $\left| f\left( {{x}_{k+1}} \right)-f\left( {{x}_{k}} \right) \right|<\varepsilon $     یا    $\left \| \nabla f\left( {{x}_{k}} \right)\right \|<\varepsilon $

که در آن‌ها $\varepsilon $ یک عدد کوچک مثبت است، به عنوان شرط خاتمه‌ی الگوریتم در نظر گرفته می‌شود.

برای رفتن از نقطه‌ی ${{x}_{k}}$ به ${{x}_{k+1}}$ به یک جهت کاهشی و فاصله‌ای که باید در راستای این جهت پیموده شود نیاز است. طبیعی است که انتظار داشته باشیم انتخاب این پارامترها به‌گونه‌ای باشد که بیش‌ترین کاهش ممکن در هر تکرار الگوریتم رخ دهد. در حقیقت تفاوت عمده‌ی بین الگوریتم‌های کاهشی نیز، مربوط به نحوه‌ی انتخاب این دو پارامتر، یعنی جهت جستجو و طول گام مناسب است. انتخاب این دو پارامتر می‌تواند به چند راه صورت گیرد؛ این کار ممکن است صرفاً متکی بر مقادیر تابع و اطلاعات به‌دست آمده از تکرارهای قبلی و یا متکی بر اطلاعاتی از مشتقات جزئی تابع باشد. الگوریتم‌هایی که از شیوه‌ی اول استفاده می‌کنند، عموماً به روش‌های جستجوی مستقیم معروفند و از جمله‌ی این روش‌ها، می‌توان به دو روش جستجوی فیبوناچی و روش سادکی نلدر و مید اشاره کرد. سایر الگوریتم‌ها که از شیوه‌ی دوم استفاده می‌کنند به روش‌های گرادیانی معروف‌اند. روش‌های تندترین کاهش، نیوتن و شبه‌نیوتن از جمله روش‌های گرادیانی هستند. هم‌چنین می‌توان در مورد این‌‌که کدام یک از دو پارامتر جهت جستجو یا طول گام مناسب زودتر از دیگری انتخاب شود، تصمیم گرفت. این تصمیم‌گیری منجر به معرفی دو راهبرد جستجوی خطی و ناحیه‌ی اطمینان می‌شود.

تابع لبگ و نقاط مناسب درونیابی

فرض کنید بخواهیم تابع $f$ را روی یک مجموعه از نقاط متمایز در $ \left[ a,b \right]$ با یک چندجمله‌ای از درجه‌ی $n$ مانند $p_{n}$ درونیابی کنیم. مسئله این است که نقاطی که $f$ در آن‌ها درونیابی می‌شود، تا چه‌اندازه می‌توانند در دقت چندجمله‌ای درونیاب حاصل مؤثر باشند. در اینجا خطا را به کمک نرم بی‌نهایت می‌سنجیم. یعنی قرار می‌دهیم: $$E({{p}_{n}}):={{\left\| f-{{p}_{n}} \right\|}_{\infty }}=\underset{a\le x\le b}{\mathop{\max }}\,\left| f(x)-{{p}_{n}}(x) \right|$$ فرض کنید $p_{n}^{*}$ بهترین تقریب چندجمله‌ای درجه‌ی $n$ برای تابع $f$ در بازه‌ی $ \left[ a,b \right]$ باشد. به این مفهوم که:$${{\left\| f-p_{n}^{*} \right\|}_{\infty }}=\underset{p\in {{P}_{n}}}{\mathop{\min }}\,(\underset{a\le x\le b}{\mathop{\max }}\,\left| f(x)-p(x) \right|)$$چندجمله‌ای $p_{n}^{*}$ معمولا چندجمله‌ای مینیماکس تابع $f$ در بازه‌ی $ \left[ a,b \right]$ نامیده می‌شود.

اکنون می‌توان ارتباط خطای چندجمله‌ای درونیاب تابع $f$ و خطای چندجمله‌ای مینیماکس تابع $f$ را به کمک قضیه‌ی زیر بیان کرد.

آشنایی با روش‌های بهینه‌سازی نامقید (1)

ضرورت و پیشینه:

هنگامی که مسائل بهینه‌سازی نامقید را مطالعه می‌کنیم ممکن است این‌طور به نظر آید که این مسائل چنان عاری از ویژگی‌های ساختاری هستند که مانع از کاربری آن‌ها به‌عنوان مدل‌های مفید برای مسائل با اهمیت می‌شوند. اما به دو دلیل، کاملاً عکس این مطلب صحیح است؛ اولاً می‌توان این استدلال قانع کننده را پیش کشید که اگر قلمروی مسئله گسترش یابد به‌طوری که همه‌ی متغیرهای مربوط به تصمیم‌گیری در نظر گرفته شوند، وجود هیچ قیدی لازم نیست. به عبارت دیگر، قیود مبیّن محدودیت تصنعی میدان عمل هستند و زمانی که این میدان توسعه داده شود از صحنه خارج می‌شوند. بنابراین به‌طور مثال، می‌توان استدلال کرد که قید بودجه یک مشخصه‌ی لازم در فرموله‌کردن یک مسئله‌ی معنی‌دار نیست؛ زیرا دست‌یابی به منابع مالی بیش‌تر همواره با وام گرفتن با یک نرخ بهره‌ی مشخص امکان‌پذیر است و بنابراین به جای معرفی قید بودجه، می‌توان جمله‌ای که هزینه‌ی پول مورد استفاده را منعکس سازد به‌کار گرفت. شبیه همین استدلال در مورد قیودی که مبین دسترس‌پذیری منابع دیگری هستند و با هزینه‌ی مشخص (هر چند زیاد) قابل تأمین می‌باشند، نیز صادق است.

دلیل دوم برای این‌که بسیاری از مسائل مهم را می‌توان بدون قید در نظر گرفت، آن است که مسائل مقید در برخی مواقع به سادگی قابل تبدیل به مسائل نامقید هستند. برای مثال تأثیر نهایی قیود تساوی در یک مسئله‌ی مقید فقط این است که درجات آزادی را، با معرفی برخی از متغیرها به عنوان توابعی از سایر متغیرها محدود کند. این وابستگی‌ها در برخی موارد به‌طور صریح قابل توصیف‌اند و می‌توان یک مسئله‌ی جدید که تعداد متغیرهایش همان درجه‌ی واقعی آزادی است، مشخص کرد. به عنوان یک نمونه‌ی ساده فرض کنید قیدی به‌صورت ${{x}_{1}}+{{x}_{2}}=B$ در یک مسئله‌ی مقید وجود داشته باشد. این قید را می‌توان با جای‌گذاری ${{x}_{1}}=B-{{x}_{2}}$ در تمام قیودی که متغیر ${{x}_{1}}$ در آن‌ها حضور دارد، به سادگی حذف نمود.

مطالعه‌ی مسائل نامقید صرف‌نظر از این‌که به تبیین دسته‌ی مهمی از مسائل عملی می‌انجامد، مسلماً گامی است در راه دسترسی به حالت کلی‌تر یعنی مسائل مقید. بسیاری از جنبه‌های نظری و الگوریتم‌ها در حالت نامقید، و قبل از تعمیم به حالت مقید، به‌صورت بسیار طبیعی‌تری قابل طرح و تحقیقند.

تاریخ بهینه‌سازی نامقید و به‌طور کلی روش‌های بهینه‌یابی را می‌توان به روزگار ریاضی‌دانان گذشته از جمله نیوتن، لاگرانژ و کوشی مرتبط دانست. نخستین مسئله‌ی بهینه‌سازی، 300 سال قبل از میلاد مسیـح توسط اقلیدس شکل گرفت؛ وی نشـان داد که کم‌ترین فاصله‌ی بین یک نقطه و یک خط، طول پاره‌خطی است که از آن نقطه بر خط مورد نظر عمود می‌شود. توسعه‌ی روش‌های بهینه‌سازی در حساب دیفرانسیل مدیون کارهای نیوتن و لایبنیتس است. نیوتن (1669) اندکی پس از ابداع حسابان، با خطی‌سازی توابع، روشی را برای یافتن ریشه‌های یک چندجمله‌ای ارائه کرد. رافسون (1690) روش نیوتن را به کل توابع تعمیم داد. البته نه نیوتن و نه رافـسون هیچ‌کدام از مشتق توابع استفاده نکردند تا این‌که با معرفی سری تیلور (1715)، شکل امروزی این روش که به روش نیوتن- رافسون معروف است، به‌صورت

$${{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{{f}'\left( {{x}_{n}} \right)},~~{{x}_{0}}\in \left( a,b \right),~n=0,1,2,\ldots $$

ثابت شد. ایده‌ی اولیه‌ی روش نیوتن در بهینه‌سازی نامقید از همین روش شکل گرفت. لاگرانژ (1806) برای نخستین بار با معرفی روش ضرایب لاگرانژ، روش بهینه‌سازی برای توابع هدف با محدودیت را طرح نمود و کوشی برای نخستین بار در سال 1847 روش تندترین کاهش را برای حل مسائل بهینه‌سازی نامقید ارائه کرد. تحولات اساسی در بهینه‌سازی نامقید در قرن بیستم رخ داد و ظهور رایانه به این تحولات سرعت بسیاری بخشید. دهه‌ی 1960 را می‌توان دهه‌ی اصلی توسعه‌ی روش‌های عددی در بهینه‌سازی نامقید دانست. در این دهه، هستینز و اشتیفل روش گرادیان مزدوج را ابداع نمودند و دیویدان نخستین روش‌‌ شبه‌نیوتن را به دست آورد. عمده‌ی کارهای محققان در طی دهه‌های بعدی، طرح روش‌های جدید، اصلاح روش‌های قبلی و یا تعمیم روش‌های موجود به مسائلی در ابعاد بزرگ‌تر بوده است و مثلاً از میان آن‌ها می‌توان به ابداع روش $BFGS$ توسط برویدن، فلچر، گلدفارب و شانو ، اصلاح اشنیبل و اسکوو از روش نیوتن و تعمیم روش $BFGS$ به مسائل در مقیاس بزرگ توسط نوسدال اشاره کرد.

طرح مسئله:

یک مسئله‌‌ی بهینه‌سازی در کلی‌ترین صورت خود شامل پیدا کردن مقدار بهینه (بیشینه یا کمینه) تابع $f\left( {{x}_{1}},\ldots ,{{x}_{n}} \right)$ با $n$ متغیر ${{x}_{n}},\ldots ,{{x}_{1}}$ است. در اینجا باید توجه کنیم که از نقطه نظر ریاضی، در نظر گرفتن بیشینه‌سازی و کمینه‌سازی، هر دو، ضرورت ندارد، زیرا بیشینه‌سازی $~f$ هم‌ارز کمینه‌سازی $-f$ است. در نتیجه طبیعتاً در ادامه‌، بحث ما محدود به کمینه‌سازی خواهد شد. گاهی اوقات ممکن است متغیرهای مسئله‌ی بهینه‌سازی به قید یا قیود خاصی محدود شده باشند، که در این صورت با یک مسئله‌ی بهینه‌سازی مقید سروکار داریم و چنان‌چه قیدی روی متغیرها نباشد، مسئله از نوع بهینه‌سازی نامقید است که در این جا، هدف ما آشنایی با این نوع مسائل است. در حالت کلی یک مسئله‌ی بهینه‌سازی نامقید به صورت زیر است:

$$\min\left\{ f\left( x \right)|~x\in {{\mathbb{R}}^{n}} \right\},$$

که در آن فرض می‌شود که $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ تابعی دو بار به‌طور پیوسته مشتق‌پذیر است. برای مطالعه‌ی مسئله‌ی کلی فوق لازم است دو نوع از نقاط جواب، یعنی نقاط کمینه‌ی موضعی و نقاط کمینه‌ی سراسری را متمایز ‌کنیم.

مرور برخی از مفاهیم جبرخطی عددی

مطالب این پست می‌تواند برای یادآوری برخی مفاهیم جبرخطی عددی مفید واقع شود.

تعریف 1. یک میدان، مجموعه‌­ا­ی است مانند $\mathbb{F}$ همراه با دو عمل  \[+,\,\cdot :\mathbb{F}\times \mathbb{F}\to \mathbb{F}\] که در شرایط زیر صدق می­‌کنند:

الف) برای هر$x,y,z\in \,\mathbb{F}$ ، $x+(y+z)=(x+y)+z$  (خاصیت شرکت­‌پذیری جمع)؛

ب) عضو یکتای $0\in \,\mathbb{F}$ وجود دارد به­‌طوری­که برای هر $x\in \,\mathbb{F}$، \[x+0=0+x=x\] (عضو خنثی جمع)؛

ج) برای هر$x\in \,\mathbb{F}$ ، عضو یکتای $-x\in \,\mathbb{F}$ وجود دارد به­ طوری­که برای هر $x\in \,\mathbb{F}$، $x+(-x)=0$ (عضو قرینه نسبت به جمع)؛

د) برای هر$x,y\in \,\mathbb{F}$ ، $x+y=y+x$ (خاصیت جابجایی جمع)؛

هـ) برای هر $x,y\in \,\mathbb{F}$، $x\cdot y=y\cdot x$ (خاصیت جابجایی ضرب)؛

و) برای هر$x,y,z\in \,\mathbb{F}$ ، $x\cdot (y\cdot \,z)=(x\cdot y)\cdot z$ (خاصیت شرکت­‌پذیری ضرب)؛

ز) عضو یکتای $1\in \,\mathbb{F}$ وجود دارد به­‌طوری­که برای هر$x\in \,\mathbb{F}$ ،$1\cdot x=x$  (عضو خنثی ضرب)؛

ح) برای هر عضو ناصفر $x\in \,\mathbb{F}$، عضو یکتای ${{x}^{-1}}\,\in \,\mathbb{F}$ وجود دارد به­‌طوری­که $x\cdot {{x}^{-1}}=1$  (عضو وارون ضرب)؛

ط) برای هر $x,y,z\in \,\mathbb{F}$ ،$x\cdot (y+z)=x\cdot y+x\cdot z$  (خاصیت توزیع­‌پذیری ضرب نسبت به جمع).

اعضای یک میدان، معمولاً اسکالر نامیده می­‌شوند.

در تعریف فوق، ویژگی­های (الف)، (ب) و (ج) بیان می‌کنند که $(\mathbb{F},+)$ یک گروه است و درصورتی­‌که شرط (د) نیز برقرار باشد، $(\mathbb{F},+)$ یک گروه آبلی است. ویژگی­های (هـ)، (و)، (ز) و (ح) بیان می­‌کنند که $(\mathbb{F}-\left\{ 0 \right\},\cdot )$ نیز یک گروه آبلی است.