چند نکته در مورد نگارش مقالات با لاتک

Some Latex writing tips
Michiel Hochstenbach, TU Eindhoven, 2016
NB: Several tips are taken from Nick Higham's Handbook of Writing for the Mathematical Sciences

General:
1- Use a spelling checker, such as the one available in WinEdt or Word. If possible, use more than one.
2- Before and after e.g., always use a comma (= for instance).
3- Before and after i.e., always use a comma (= that is).
4- Instead of "in order to" just use "to".
5- Always use comma's in a list such as in: A, B, C, and/or D.
6- Check on double common words, such as "the the".
7- Check on "a + vowel" which should be replaced by "an + vowel". For instance, "an integer", but also "an n x n matrix". NB: "a user" is correct.
8- Avoid using the same word several times, particularly in the same paragraph.
9- The last section should contain conclusions. It is good practice to include the main message of the paper in the abstract, the introduction, throughout the text, and in the conclusions.
10- Are the key words and AMS math codes complete?
11- Quotation marks: use `` and '' instead of "
12- In a revised version, please thank the referees.
13- Be careful using "novel" as this has the feeling of "shockingly new".

بررسی نکات و تست‌های مبانی آنالیز عددی

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

بررسی نکات و تست‌های مبانی آنالیز عددی در آزمون‌های دکتری

بررسی نکات و تست‌های مبحث مقادیر ویژه

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

بررسی نکات و تست‌های مبحث مقادیر ویژه در آزمون‌های دکتری

مسئله‌ی توزیع اقتصادی بار

در این پست به بیان یکی از کاربردهای بهینه‌سازی در علوم مهندسی می‌پردازیم. مسئله‌ی توزیع اقتصادی بار، یکی از مسائل مهم در حوزه‌ی بهره‌برداری از سیستم‌های قدرت (نیروگاه‌ها) است. هدف این مسئله، تأمین بار مورد نیاز با کمترین هزینه توسط نیروگاه‌های تولید برق می‌باشد.

تعریف مسئله:
در یک سیستم قدرت شامل $n$ واحد تولیدی که توسط تعدادی خطوط انتقال به مراکز مصرف متصل شد‌ه‌اند، مسئله‌ی توزیع اقتصادی بار به‌صورت «تعیین میزان تولید توان هر نیروگاه با هدف کمینه کردن هزینه‌ی تأمین مجموع بار شبکه» تعریف می‌شود. این مسئله‌ دارای دو صورت شناخته شده است که بسته به در نظر گرفتن یا نگرفتن تلفات انتقال شبکه‌ می‌باشد. در ادامه، فرمولبندی مسئله برای هر دو حالت بیان می‌گردد.

الف)‌ توزیع اقتصادی بار با در نظر گرفتن تلفات انتقال شبکه:

$$\begin{alignat}{3}
 & \text{minimize}\quad\underset{i=1}{\overset{n}{\mathop \sum }}\,{{F}_{i}}\left( {{P}_{i}} \right)=\underset{i=1}{\overset{n}{\mathop \sum }}\,\left( {{a}_{i}}P_{i}^{2}+{{b}_{i}}{{P}_{i}}+{{c}_{i}} \right) \\
 & \text{subject to} \quad\underset{i=1}{\overset{n}{\mathop \sum }}\,{{P}_{i}}=D+{{P}_{l}},\\
                 &\quad \quad \quad \quad \quad P_{i}^{min}\le {{P}_{i}}\le P_{i}^{max}.
\end{alignat}$$در مسئله‌ی فوق متغیرهای تصمیم ${{P}_{i}}$ها هستند که بایستی تعیین شوند. ${{P}_{i}}$ میزان توان تولیدی نیروگاه $i$ام است. تابع هدف، مجموع توابع هزینه‌ی واحدهای تولیدی است که یک تابع هدف درجه دوم می‌باشد. در واقع هزینه‌ی تولید توان ${{P}_{i}}$ توسط نیروگاه $i$ام به صورت زیر تعریف می‌شود:$${{F}_{i}}\left( {{P}_{i}} \right)={{a}_{i}}P_{i}^{2}+{{b}_{i}}{{P}_{i}}+{{c}_{i}}$$که در آن ضرایب ${{a}_{i}},{{b}_{i}},{{c}_{i}}$ اعدادی حقیقی هستند. لذا تابع هدف مسئله، جمع تمام هزینه‌های واحدهای تولید (نیروگاه‌ها) می‌باشد که باید کمینه شود. این مسئله شامل دو دسته قید است:

- قید تعادل:

به این معنی که مجموع تولید توان توسط تمام نیروگاه‎ها ($\underset{i=1}{\overset{n}{\mathop \sum }}\,{{P}_{i}}$) باید با مجموع توان مصرفی ($D$) و توان تلف‌شده (${{P}_{l}}$) برابر باشد. رابطه‌ی میان تلفات انتقال انرژی و میزان تولید هر نیروگاه، با استفاده از فیزیک شبکه‌های انتقال بدست می‌آید و بصورت زیر است:$${{P}_{l}}={{P}^{t}}BP=\underset{i=1}{\overset{n}{\mathop \sum }}\,\underset{j=1}{\overset{n}{\mathop \sum }}\,{{P}_{i}}{{B}_{ij}}{{P}_{j}}$$این رابطه، به دلیل وجود حاصلضرب ${{P}_{i}}$ها یک رابطه‌‌ی غیرخطی است. ${{B}_{ij}}$ها ضرایب تلفات نامیده می‌شوند.

-‌ قیود عملیاتی واحدها:

به این معنی که میزان تولید توان توسط نیروگاه $i$ام نباید از حدود مشخصی کمتر یا بیشتر باشد. مقادیر $P_{i}^{min},P_{i}^{max}$ به ترتیب حد بالا و پایین تولید توان برای هر نیروگاه می‌باشند.

ب)‌ توزیع اقتصادی بار بدون در نظر گرفتن تلفات انتقال شبکه:$$\begin{alignat}{3}
 & \text{minimize}\quad\underset{i=1}{\overset{n}{\mathop \sum }}\,{{F}_{i}}\left( {{P}_{i}} \right)=\underset{i=1}{\overset{n}{\mathop \sum }}\,\left( {{a}_{i}}P_{i}^{2}+{{b}_{i}}{{P}_{i}}+{{c}_{i}} \right) \\
 & \text{subject to} \quad\underset{i=1}{\overset{n}{\mathop \sum }}\,{{P}_{i}}=D,\\
                 &\quad \quad \quad \quad \quad P_{i}^{min}\le {{P}_{i}}\le P_{i}^{max}.
\end{alignat}$$در اینجا، مسئله‌ی حالت (الف) را به دلیل داشتن قیود غیرخطی، حل می‌کنیم.

آنالیز عددی، گذشته، حال و آینده

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

1. مقدمه

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

2. آنالیز عددی چیست؟

• آنالیز عددی علم و هنر محاسبه است.

از حدود 140 سال قبل از میلاد تا اوایل قرن هفدهم دانشمندان فیزیک و ریاضی با محاسبات فراوان و متنوع روبرو بودند و افراد شاخص نظیر غیاث‌الدین جمشید کاشانی جان نپر، بریگز، کپلر و توماس هاریوت در این زمینه زحمات زیادی متحمل شدند [1].

• آنالیز عددی ریاضیات محاسبات علمی است.

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

3. الگوریتم

پس از انجام بررسی‌های ریاضی لازم، یافته‌ها به صورت یک الگوریتم ارائه می‌شوند. الگوریتم طراحی شده باید دارای ویژگی‌های زیر باشد:

• پارامترها و داده‌های آن کاملاً مشخص باشد؛
• مراحل آن کاملاً مشخص و قابل اجرا باشد؛
• رعایت صرفه‌جویی در اشغال حافظه کامپیوتر و زمان CPU شده باشد؛
• پایان‌پذیر باشد.

اما آنچه در مورد یک الگوریتم حائز اهمیت است تجزیه و تحلیل یا آنالیز الگوریتم می‌باشد و واژه آنالیز در نام آنالیز عددی به معنی آنالیز ریاضی نیست بلکه به معنی تجزیه و تحلیل الگوریتم‌هایی است که برای بدست آوردن جواب‌های عددی مسائلی ساخته می‌شود که اثبات وجود آنها عمدتاً توسط قضایا و احکام آنالیز ریاضی انجام می‌شود. البته حدود نیمی از مباحث آنالیز عددی به جبر خطی مربوط می‌شود که اثبات وجود جواب برای مسائل این حیطه توسط قضیه‌ها و احکام جبر خطی صورت می‌گیرد.

نمایش اعداد در استاندارد IEEE 754

به لحاظ تاریخی، کامپیوترها‌ی گوناگون انتخاب‌های متفاوتی در تعیین مبنا، کران‎های نما و ارقام مانتیسِ نمایش ممیز شناور داشته‌اند. در سال 1985 با تلاش‌های گروهی متشکل از ریاضیدانان، دانشمندان علوم کامپیوتر و شرکت‎های تولید سخت‌افزار به سرپرستی ویلیام کاهان از دانشگاه کالیفرنیا، استانداردی برای نمایش اعداد ممیز شناور تحت عنوان IEEE 754 به سازندگان سخت‌افزارها عرضه شد. هم‌اکنون در بیشتر کامپیوترها از این استاندارد استفاده می‌شود. استاندارد IEEE، چند قالب کلی با دقت‌های مختلف از جمله دقت معمولی، دقت مضاعف و دقت‌های معمولی و مضاعف توسعه یافته برای نمایش اعداد ارائه می‌کند. در این‌جا به منظور آشنایی بیشتر با شیوه‌ی نمایش اعداد در این استاندارد، نحوه‌ی نمایش در دقت‌ معمولی و مضاعف را شرح می‌دهیم.

مبنای در نظر گرفته‌ شده در این استاندارد $\beta=2$ است. مطابق این استاندارد، در دقت معمولی از 32 بیت و در دقت مضاعف از 64 بیت برای نمایش یک عدد استفاده می‌شود. هر نمایش از سه بخش تشکیل می‌شود که عبارتند از علامت $(s)$، نمای تعدیل یافته $(c)$ و قسمت کسری مانتیس نرمال شده $(f)$.

این سه بخش با استفاده از روابط‌ زیر مشخص می‌شوند به‎صورت $(s|c|f)$ در کنار هم قرار می‌گیرند:

 دقت معمولی:$$x=\pm(1.f)_{2}\times2^{e}=(-1)^s(1.f)_2\times2^{c-127}$$

 دقت مضاعف:$$x=\pm(1.f)_{2}\times2^{e}=(-1)^s(1.f)_2\times2^{c-1023}$$

در دقت معمولی، از 32 بیت اختصاص داده شده برای نگهداری عدد، یک بیت برای علامت $(s)$ استفاده می‌شود به‌طوری که $s=0$ برای علامت مثبت و $s=1$ برای علامت منفی به‌کار می‌رود. از 31 بیت باقیمانده، 8 بیت آن برای نگهداری نمای تعدیل یافته $(c)$ و 23 بیت آن برای قسمت کسری مانتیس نرمال شده $(f)$ استفاده می‌شود. در دقت مضاعف، از 64 بیت اختصاص داده شده برای نگهداری عدد، یک بیت برای علامت $(s)$ و از 63 بیت باقیمانده، 11 بیت آن برای نگهداری نمای تعدیل یافته $(c)$ و 52 بیت آن برای قسمت کسری مانتیس نرمال شده $(f)$ استفاده می‌شود.
همان‌طور که ملاحظه می‌کنید شکل کلی قالب‌های ذکر شده در دقت‌های معمولی و مضاعف، کمی شبیه به نمایش ممیز شناور نرمال است. فقط باید توجه داشت که در استاندارد IEEE مانتیس $x$ به صورت $(1.f)_2$ نرمال و تنها قسمتی از مانتیس که با $f$ نشان داده شده است، نمایش داده می‌شود. در واقع، چون اولین بیت مانتیس نرمال شده همواره برابر با 1 است نیازی به ذخیره‌سازی آن نیست. در عوض، این بیت برای نمایش نما مورد استفاده قرار می‌گیرد.

مثال: عدد $x=-45.75$ را در نظر بگیرید. می‌خواهیم این عدد را در استاندارد IEEE با دقت معمولی نمایش دهیم. برای این منظور، ابتدا نمایش دودویی آن را می‌یابیم. داریم $x=-(101101.11)$. حال باید این عدد را به فرم $(1.f)_2\times2^e$ درآوریم: $$x=-(1.0110111)×2^5$$اکنون از این تساوی باید مقادیر s ،f و c را بیابیم. با توجه به قالب کلی دقت ساده داریم:$$s=1,~~ f=0110111,~~e=5=c-127$$ در نتیجه $c=132=(10000100)_2$ و بنابراین:$$x=1|10000100|01101110000000000000000$$مثال: عدد زیر در استاندارد IEEE با دقت معمولی نمایش داده شده است.$$y=0|10000001|10011000000000000000000$$می‌خواهیم نمایش اعشاری آن را بیابیم. با توجه به نمایش فوق داریم:$$s=0,~~ c=(10000001)_2=129,~~ f=10011$$بنابراین $y$ عددی مثبت است و $e=c-127=129-127=2$. در نتیجه:$$y=+(1.f)_2×2^e=(1.10011)_2×2^2=(110.011)_2=6.375$$ فرمت جدید unum

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

John L. Gustafson

 فرمت unum (universal number) از روی استاندارد IEEE ساخته می‌شود. مطابق تعریف unum، هر نمایش از شش بخش بصورت زیر تشکیل می‌گردد: $$s|e|f|u|es-1|fs-1$$

در این قالب:

• s علامت عدد است به‌طوری که $s=0$ برای علامت مثبت و $s=1$ برای علامت منفی به‌کار می‌رود.
• e نمای عدد است.
• f قسمت کسری عدد است.
  
• u بیت عدم قطعیت (uncertainty bit) نام دارد و در صورتی که مقدار بخش کسری دقیق باشد، برابر با 0 وگرنه برابر با 1 است.
• es سایز نما است. مثلا اگر برای ذخیره نما هشت بیت بکار رود es برابر ₂(111) خواهد بود.
• fs سایز کسر است. مثلا اگر برای ذخیره کسر بیست و سه بیت بکار رود fs برابر ₂(10110) خواهد بود.

برای آشنایی بیشتر با این فرمت، گوستافسون کتابی تحت عنوان «پایان خطا» منتشر کرده است که در انتهای همین پست می‌توانید آن را دریافت کنید.

برای اینکه ببینید که فرمت unum تا چه اندازه می‌تواند در میزان حافظه صرفه جویی کند، نمایش ثابت آووگادرو ($\approx6.022 \times 10^{23}$) را در نظر بگیرید. نمایش این عدد در استاندارد IEEE با دقت مضاعف (64 بیتی) به‌صورت زیر است:

0 10001001101 1111111000010101010011110100010101111110101000010011
|      |                          |
|      |                       fraction (hidden bit not shown)
|   exponent
|
sign bit

این عدد در فرمت unum به صورت زیر نمایش داده می‌شود اما این بار با 29 بیت.

0   11001101   111111100001   1   111   1011
|       |           |         |    |      |
|       |           |         |    |     frac. size
|       |           |         |    |
|       |           |         |   exp. size
|       |           |         |
|       |           |       uncertainty bit
|       |           |
|       |        fraction (hidden bit not shown)
|       |
|   exponent
|
sign bit

کتاب پایان خطا، جان. ال. گوستافسون

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

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

تاریخچه‌ی کوتاهی از روش‌های شبه‌نیوتن
در اواسط دهه‌ی 1950 دیویدان، فیزیکدان شاغل در آزمایشگاه ملی آرگون، روش‌ کاهش مختصاتی را برای انجام محاسبات بهینه‌سازی به کار می‌برد. در آن زمان دستگاه‌های کامپیوتری از توانایی محاسباتی بالایی برخوردار نبودند. بنابراین دیویدان تصمیم گرفت راهی پیدا کند که فرآیند تکرار الگوریتم را بهبود بخشد. الگوریتم او اولین الگوریتم شبه‌نیوتن بود که انقلابی در بهینه‌سازی غیرخطی ایجاد کرد. دیری نپایید که توسط فلچر و پاول  ثابت شد که این الگوریتم جدید بسیار سریع‌تر و قابل اطمینان‌تر از دیگر روش‌های موجود آن زمان است و این پیشرفت به‌طور چشمگیری بهینه‌سازی غیرخطی را دگرگون کرد. در طول بیست سال بعد الگوریتم‌های شبه‌نیوتن متعددی مطرح و در صدها مقاله به مطالعه‌ی آن‌ها پرداخته شد. حکایت تاریخی جالبی که در این زمینه وجود دارد آن است که، مقاله‌ی دیویدان حدود 30 سال و به بهانه‌ی این‌که صرفاً گزارشی فنی است برای انتشار پذیرفته نشد تا این‌که سرانجام در سال 1991 در مجله‌ی بهینه‌سازی $SIAM$ به چاپ رسید.
همان‌گونه که گفته شد پس از معرفی اولین روش شبه‌نیوتن توسط دیویدان، فلچر و پاول (1963) که به الگوریتم $DFP$ معروف است، الگوریتم‌های شبه‌نیوتن متعددی مطرح شدند. ابتدا روش تصحیح رتبه یک ($SR1$) به وسیله‌ی دیویدان و برویدن (1967) عرضه شد و سپس روش $BFGS$ را برویدن، فلچر، گلدفارب و شانو در سال 1970 مستقل از یکدیگر معرفی کردند. ادبیات موضوع نشان می‌دهد که این الگوریتم به‌عنوان مؤثرترین الگوریتم به‌هنگام‌سازی در مسائل نامقید پذیرفته شده است. روش خانواده‌ی برویدن در سال 1970 توسط برویدن مطرح شد. این روش که از ترکیب محدب دو روش $DFP$ و $BFGS$ حاصل می‌شود به صورت زیر است:
$${{H}_{k}}\left( B \right)={{\varphi }_{k}}{{H}_{BFGS}}+\left( 1-{{\varphi }_{k}} \right){{H}_{DFP}},~~~~~~~0\le {{\varphi }_{k}}\le 1,$$ یک روش برویدن بنا به تعریف روشی است که در هر تکرار آن یکی از اعضای خانواده‌ی برویدن به عنوان تقریب معکوس هسین در نظر گرفته می‌‌شود. ابتدا کوشش‌های فراوانی برای یافتن بهترین دنباله‌ی ${{\varphi }_{k}}$ها در یک روش برویدن انجام شد تا این‌که سرانجام دیکسون  در سال 1972 نشان داد که همه‌ی روش‌ها در حالت جستجوی خطی دقیق معادل یک‌دیگرند.
رده‌ی دیگری از روش‌های شبه‌نیوتن که محبوبیت خاصی در میان محققان پیدا کرده‌اند، روش‌های $LBFGS$ یا روش‌های $BFGS$ حافظه‌محدود هستند که الگوریتم $BFGS$ را با استفاده‌ی حداقلی از حافظه‌ی کامپیوتر برای مسائل در مقیاس بزرگ تقریب می‌کنند. نخستین الگوریتم $LBFGS$ را نوسدال در سال 1980 برای حل عددی مسائل بهینه‌سازی نامقید در ابعاد بزرگ ارائه داد.

ایده‌ی کلی روش‌های شبه‌نیوتن
همان‌طور که قبلاً گفته شد، روش نیوتن دو عیب اساسی دارد؛ اولین عیب این روش آن است که اگر تعداد متغیر‌های تابع هدف زیاد باشد به دست آوردن و معکوس کردن ماتریس هسین تابع، که در هر گام این روش انجام می‌شود، مستلزم محاسباتی سنگین است. عیب دوم این روش آن است که برای یک تابع هدف کلی همگرایی آن به جواب نمی‌تواند با شروع از هر نقطه‌ی ${{x}_{0}}$  تضمین شود. در حقیقت اگر نقطه‌ی شروع به اندازه‌ی کافی به جواب نزدیک نباشد ماتریس هسین ممکن است معین مثبت نباشد و الگوریتم خاصیت کاهشی را حفظ نکند.
روش‌های شبه‌نیوتن برای رفع مشکلات روش نیوتن طراحی شده‌اند و جانشین مناسبی برای آن هستند. از آن‌جا که این روش‌ها تنها از اطلاعات تابع هدف و مشتقات اول آن استفاده می‌کنند در آن‌ها نیازی به محاسبه‌ی‌ وارون ماتریس هسین و ذخیره‌سازی آن نیست. هم‌چنین این روش‌ها معمولاً دارای همگرایی فوق‌خطی هستند که از این نظر بینابین روش تندترین کاهش و نیوتن قرار دارند.

تعیین حدود مقادیر ویژه‌ی یک ماتریس

یکی از مسائل اساسی که در جبر خطی عددی بررسی می‌شود، تعیین مقادیر ویژه یک ماتریس است. در این مطلب برخی از قضایا را که در تعیین کران‌های مقادیر ویژه یک ماتریس به کار می‌روند، بیان می‌کنیم.

قضیه‌ گرشگورین:
فرض کنید $A$ یک ماتریس $n\times n$ باشد. در این‌صورت اجتماع دیسک‌های زیر، موسوم به دیسک‌های گرشگورین، تمام مقادیر ویژه‌ی $A$ را در بر می‌گیرد:$$\left| z-{{a}_{ii}} \right|\le \sum\limits_{j=1,j\ne i}^{n}{\left| {{a}_{ij}} \right|};~~~~i=1,2,...,n~~~~(1)$$همچنین اجتماع هر $k$ دیسک گرشگورین که $(n-k)$ تای دیگر را قطع نکنند، دقیقا شامل $k$ مقدار ویژه $A$ با احتساب تکرار می‌باشد.
نتیجه: با توجه به اینکه مجموعه‌ی مقادیر ویژه‌ $A$ و ${{A}^{H}}$ با هم برابرند می‌توان قضیه فوق را در مورد ${{A}^{H}}$ به کار گرفت. به عبارت دیگر مقادیر ویژه‌ی $A$ در دیسک‌های زیر نیز قرار دارند:$$\left| z-{{a}_{jj}} \right|\le \sum\limits_{i=1,i\ne j}^{n}{\left| {{a}_{ij}} \right|};~~~~j=1,2,...,n~~~~(2)$$بنابراین اگر اجتماع دیسک‌های تعریف شده در (1) را با ${{C}_{r}}$ و اجتماع دیسک‌های تعریف شده در (2) را با ${{C}_{c}}$ نشان ‌دهیم می‌توان گفت تمام مقدار ویژه‌های $A$ در ${{C}_{r}}\cap {{C}_{c}}$ قرار می‌گیرند.
مثال:  فرض کنید$$A=\left[ \begin{matrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 5 & 1 \\ \frac{1}{2} & 1 & 1 \\\end{matrix} \right]$$چون ماتریس $A$ متقارن و حقیقی است، تمام مقدار ویژه‌ها حقیقی هستند و قضیه گرشگورین و نتیجه‌ی بعد آن هر دو به یک جواب منجر می‌شوند. دیسک‌های گرشگورین در این‌جا عبارتند از ${{D}_{1}}$ به مرکز $0$ و شعاع $1$، ${{D}_{2}}$ به مرکز $5$ و شعاع $1.5$ و ${{D}_{3}}$ به مرکز $1$ و شعاع $1.5$. بنابراین مقادیر ویژه‌ $A$ در فاصله‌های $[-1,2.5]$ و $[3.5,6.5]$ قرار دارند. می‌توان دید که مقادیر ویژه‌ی $A$ تا سه رقم اعشار عبارتند از:$${{\lambda }_{1}}=0.209,~~{{\lambda }_{2}}=5.305,~~{{\lambda }_{3}}=0.904$$

قضیه‌ی شور:
فرض کنید $A$ یک ماتریس $n\times n$ باشد و ${{\lambda }_{1}},...,{{\lambda }_{n}}$ مقادیر ویژه آن باشند. در این صورت:$${{\sum\limits_{k=1}^{n}{\left| {{\lambda }_{k}} \right|}^{2}}}\le {{\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{\left| {{a}_{ij}} \right|^{2}}}}}$$و علامت تساوی برقرار است اگر و تنها اگر $A$ نرمال باشد؛ یعنی $A{{A}^{H}}={{A}^{H}}A$. نامساوی اخیر، نامساوی شور نامیده می‌شود.

به آسانی می‌توان دید که ماتریس‌های هرمیتی، هرمیتی کج و یکانی و همینطور ماتریس‌های متقارن حقیقی، پادمتقارن و ماتری‍س‌های متعامد، نرمال هستند.
با توجه به این قضیه می‌توان گفت که اگر $\lambda$ مقدار ویژه‌ی دلخواهی از ماتریس $A$ باشد، آن‌گاه در نامساوی بالا ${{\left| \lambda \right|}^{2}}$ از مجموع سمت چپ کمتر یا با آن برابر است و بنابراین با جذر گرفتن از طرفین بدست می‌آوریم:$$\left| \lambda \right|\le \left({{{\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{\left| {{a}_{ij}} \right|^{2}}}}}}\right)^{1/2}$$توجه کنید که در این‌جا، عبارت سمت راست همان نرم فروبنیوس $A$ می‌باشد.
مثال: ماتریس زیر را در نظر بگیرید:$$A=\left[ \begin{matrix} 26 & -2 & 2 \\2 & 21& 4\\ 4 & 2 & 28  \\
\end{matrix} \right]$$از نامساوی شور داریم $\left| \lambda\right|\le \sqrt{1949}<44.2$.

(مقادیر ویژه‌ی $A$ عبارتند از $30$، $25$ و $20$ و داریم ${{30}^{2}}+{{25}^{2}}+{{20}^{2}}=1925<1949$. در واقع ماتریس $A$ نرمال نیست.)

 

قضیه پرون- فروبنیوس:
فرض کنید $A$ یک ماتریس مربعی حقیقی باشد که تمام عناصرش مثبتند. در این صورت $A$ حداقل یک مقدار ویژه حقیقی مثبت $\lambda $ دارد و بردار ویژه متناظر با این مقدار ویژه را می‌توان حقیقی انتخاب کرد به گونه‌ای که تمام مولفه‌هایش مثبت باشد.

از این قضیه‌ می‌توان نتیجه‌ی سودمند زیر را به‌دست آورد:

 قضیه‌ی کولاتز:
فرض کنید $A$ یک ماتریس $n\times n$ حقیقی باشد که تمام عناصرش مثبتند. $x$ را برداری حقیقی بگیرید که مولفه‌های آن، ${{x}_{1}},...,{{x}_{n}}$ مثبتند و فرض کنید ${{y}_{1}},...,{{y}_{n}}$ مولفه‌های بردار $y=Ax$ باشند. در این‌صورت فاصله‌ی بسته‌ای که روی محور حقیقی قرار دارد و با مینیمم و ماکسیمم مقدار از $n$ خارج قسمت ${{q}_{j}}=\frac{{{y}_{j}}}{{{x}_{j}}}$ کراندار شده است، حداقل یک مقدار ویژه $A$ را در بر دارد.
اثبات: با توجه به این که $y=Ax$ داریم $y-Ax=0~~(*)$ همچنین ترانهاده $A$ در شرایط قضیه‌ی پرون-فروبنیوس صدق می‌کند. بنابراین ${{A}^{T}}$ دارای یک مقدار ویژه‌ی مثبت $\lambda $ و متناظر با این مقدار ویژه، دارای یک بردار ویژه $u$ است که تمام مولفه‌های ${{u}_{j}}$ آن مثبتند. بنابراین ${{A}^{T}}u=\lambda u$ . با ترانهاده گرفتن از طرفین این تساوی داریم ${{u}^{T}}A=\lambda {{u}^{T}}$ . از اینجا و $(*)$ نتیجه می‌شود:$${{u}^{T}}(y-Ax)={{u}^{T}}y-{{u}^{T}}Ax={{u}^{T}}(y-\lambda x)=0$$یا $$\sum_{j=1}^nu_{j}(y_{j}-\lambda{x_{j}})=0$$از این که تمام مولفه‌های ${{u}_{j}}$ مثبت هستند نتیجه می‌شود که:

به‌ازای حداقل یک $j$ داریم ${{y}_{j}}-\lambda {{x}_{j}}\ge 0$، یعنی ${{q}_{j}}\ge \lambda $ و به‌ازای حداقل یک $j$ داریم ${{y}_{j}}-\lambda {{x}_{j}}\le 0$، یعنی ${{q}_{j}}\le \lambda $.

حال از آن‌جا که $A$ و ${{A}^{T}}$ مقادیر ویژه‌ی یکسان دارند، $\lambda $ مقدار ویژه‌ی $A$ نیز هست و با توجه به این نتیجه‌ حکم قضیه به اثبات می‌رسد.

مثال: فرض کنید $A=\left[ \begin{matrix} 8 & 1 & 1 \\ 1 & 5 & 2 \\ 1 & 2 & 5  \\\end{matrix} \right]$ با انتخاب $x=\left[ \begin{matrix}1\\1\\1\\\end{matrix} \right]$ داریم: $y=\left[ \begin{matrix}10\\8\\8\\\end{matrix} \right]$.

بنابراین ${{q}_{1}}=10$، ${{q}_{2}}=8$ و ${{q}_{3}}=8$ و قضیه‌ی کولاتز ایجاب می‌کند که یکی از مقادیر ویژه‌ی $A$ باید در فاصله‌ی $[8,10]$ قرار داشته باشد. البته طول چنین فاصله‌ای به انتخاب $x$ بستگی دارد. می‌توان نشان داد که $\lambda =9$ یک مقدار ویژه‌ی $A$ است.

پیاده‌ سازی روش گرادیان مزدوج

چنان که در آموزش قبل گفته شد، روش گرادیان مزدوج یک روش تکراری برای حل دستگاه معادلات خطی $Ax=b$ می‌باشد که در آن $A$ ماتریسی $n\times n$ متقارن و معین مثبت است. همچنین این روش، روشی برای حل مسئله‌ی بهینه‌سازی درجه دوم زیر است:

$$\min f\left( x \right)=\frac{1}{2}{{x}^{t}}Ax-{{b}^{t}}x$$

در این‌جا، می‌خواهیم این روش را برای یک مسئله‌ی نمونه با استفاده از نرم‌افزار Matlab پیاده‌سازی کنیم.

دستگاه معادلات خطی زیر را در نظر می‌گیریم:

$$\begin{bmatrix}3 & 0&2&0&0 \\0 & 2&0&1&-1\\2&0&2&-1&0\\0&1&-1&3&-1\\0&-1&0&-1&1 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\\x_4\\x_5 \end{bmatrix}=\begin{bmatrix}9\\3\\4\\6\\-1 \end{bmatrix}$$مسئله‎ی بهینه‌سازی نامقید متناظر، پنج متغیره و ضابطه‌ی تابع هدف آن، $f({{x}_{1}},{{x}_{2}},{{x}_{3}},{{x}_{4}},{{x}_{5}})$ ، بصورت زیر است:$$\frac{3}{2}x_1^2+x_2^2+x_3^2+\frac{3}{2}x_4^2+\frac{1}{2}x_5^2+2x_1x_3+x_2x_4-x_2x_5-x_3x_4-x_4x_5-9x_1-3x_2-4x_3-6x_4+x_5$$جواب دستگاه معادلات خطی بالا، مختصات نقطه‌ی کمینه‌ی این تابع را به دست می‌دهد.

به کمک روش گرادیان مزدوج، با نقطه‌ی شروع $x_0=(0,0,0,0,0)^t$، شرط توقف $\left \| \nabla f\left( {{x}^{k}} \right)\right \|<10^{-1}$ و پارامتر فلچر-ریوز این مسئله را حل می‌کنیم.

clear
clc
A=[3 0 2 0 0;
    0 2 0 1 -1;
    2 0 2 -1 0;
    0 1 -1 3 -1;
    0 -1 0 -1 1]
b=[9;3;4;6;-1]
x0=[0;0;0;0;0]
r0=A*x0-b;
p0=-r0;
k=0;
xk=x0;
rk=r0;
pk=p0;
iteration=0;
while norm(rk)>10^-1
    alphak=(rk'*rk)/(pk'*A*pk);
    xk=xk+alphak*pk
    rk1=rk+alphak*A*pk;
    betak1=(rk1'*rk1)/(rk'*rk);
    pk=-rk1+betak1*pk;
    rk=rk1;
    iteration=iteration+1;
end
disp('iteration='), disp(iteration)

با اجرای این برنامه ملاحظه می‌کنیم که جواب مسئله (دستگاه) عبارتست از $x^*=(x_1,x_2,x_3,x_4,x_5)^t=(1,2,3,4,5)^t$ و روش گرادیان مزدوج طی 5 گام به این جواب می‌رسد.

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

روش گرادیان مزدوج:

روش گرادیان‌ مزدوج، یک روش تکراری برای حل دستگاه معادلات خطی $Ax=b$ می‌باشد که در آن $A$ ماتریسی $n\times n$ متقارن و معین مثبت است. به سادگی دیده می‌شود که حل دستگاه فوق، هم‌ارز با حل مسئله‌ی بهینه‌سازی درجه دوم زیر است:

$$\min f\left( x \right)=\frac{1}{2}{{x}^{t}}Ax-{{b}^{t}}x$$

 این هم‌ارزی موجب می‌شود که روش گرادیان مزدوج به‌عنوان روشی برای یافتن کمینه‌ی توابع محدب درجه دوم مورد استفاده قرار گیرد. البته همانند بخش قبل می‌توان آن را برای توابع غیر درجه دوم نیز به‌کار برد. توجه کنید که: $$\nabla f\left( x \right)=Ax-b=r\left( x \right).$$ از آن‌جا که روش گرادیان مزدوج، بر پایه‌ی جهت‌های مزدوج بنا شده است، بنابراین ابتدا شرح مختصری از جهت‌های مزدوج می‌آوریم.

تعریف: فرض کنید $A$ یک ماتریس متقارن باشد. بردارهای ${{p}_{1}}$ و ${{p}_{2}}$ را $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه $p_{1}^{t}A{{p}_{2}}=0$. یک مجموعه‌ی متناهی از بردارها مانند $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ را یک مجموعه‌ی $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه به‌ازای هر $i\ne j$ داشته باشیم $p_{i}^{t}A{{p}_{j}}=0$.

مثال: بردارهای ${{p}_{1}}=\left(\begin{matrix}-7\\4\\\end{matrix}\right)$ و ${{p}_{2}}=\left(\begin{matrix}5\\-2 \\\end{matrix} \right)$  نسبت به ماتریس $A=\left( \begin{matrix}2 & 3\\ 3 & 4 \\\end{matrix} \right)$ مزدوج هستند. اگر $A=0$ آن‌گاه هر دو بردار دلخواه، مزدوج هستند و اگر $A=I$ آن‌گاه بردارهای مزدوج بر هم عمودند.

قضیه: فرض کنید $A$ یک ماتریس معین مثبت باشد. اگر مجموعه بردارهای ناصفر $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ ،$A$-متعامد باشند، آن‌گاه این بردارها مستقل خطی هستند.

اثبات: فرض کنید ثابت‌های ${{\lambda }_{1}},{{\lambda }_{2}},\ldots ,{{\lambda }_{l}}$ موجود باشند به‌طوری که:\[{{\lambda }_{1}}{{p}_{1}}+{{\lambda }_{2}}{{p}_{2}}+\ldots+{{\lambda }_{l}}{{p}_{l}}=0\]

چون برای $i\ne j$ ، $p_{i}^{t}A{{p}_{j}}=0$ ، پس با ضرب رابطه‌ی فوق در $A$ و تشکیل ضرب داخلی با ${{p}_{i}}$ داریم ${{\lambda }_{i}}p_{i}^{t}A{{p}_{i}}=0$ و از آن‌جا که $A$ معین مثبت است، پس ${{\lambda }_{i}}=0$.

در ادامه، روش جهت‌های مزدوج را بیان می‌کنیم. این روش به‌خوبی اهمیت جهت‌های مزدوج را نشان می‌دهد.