Лекції з методів оптимізації - файл n1.doc

Метод парабол

У цьому методі вершини кожних трьох ординат з'єднуються дугами квадратичних парабол, осі яких паралельні до осіy. Таким чином, замість двох прямокутних трапецій розглядають одну елементарну трапецію, обмежену параболічною дугою. Виходячи з цього можна бачити, що число розбиттяnу методі Сімпсона має бути парним.

Площі отриманих трапецій можна позначити якs12,s34, … ,sn- 1, n. Розглянемо першу із цих трапецій. Для спрощення обчислень можна перенести вісь ординат паралельно до самої себе так, щоб вона йшла вздовж ординатиyo. Зрозуміло, що з цього величина площі не зміниться.

Рівняння квадратичної параболи, вісь якої паралельна осіy, є

Оскількиxo= 0, x1= hтаx2= 2h, то, підставивши ці значення у наведене вище рівняння можна отримати:

Після вирішення цієї системи можна знайти:

; ;

Площаs12визначається інтегралом:

Підставивши знайдені значенняА0,А1іА2у це рівняння і навівши вільні члени, отримаємо:

Звідси можна знайти формулу методу парабол (або методу Сімпсона):

Або, у більш компактному вигляді:

Гранична абсолютна похибка методу Сімпсона:

, де

8.2.Метод Рунге подвійного рахунку для оцінки похибки.Метод потрійного рахунку.

Методи вирішення задачі Коші для звичайного диференціального рівняння.

1.1. Опр.Нехай дано відрізок [a, b].Рівномірною сіткоюна цьому відрізку назвемо безліч вузлів w h таке, що w h = < xj = jh, j = 0. n, h=(b-a)/n).

Опр.Сітковою функцією y = yj = y(xj) називається функція, задана у вузлах сітки.

Будь-яку сіточну функцію y j = y(xj) можна представити у вигляді вектора Y=(y0, y1, . yn-1, yn), і, отже, безліч сіткових функцій утворює кінцевий простір, в даному випадку розмірності n+1 . У цьому просторі можна ввести норму, наприклад, або .

Нехай дано диференціальне рівняння Lu(x) = f(x,u) (наприклад, ).

1.2.Замінимо Lu у вузлі сітки xi лінійною комбінацією значень сіткової функції yi на деякій множині вузлів сітки, що називається шаблоном. Така заміна Lu на Lh yh називається апроксимацією на сітці диференціального оператора L різницевим оператором Lh. Заміна безперервної функції f(x,u) у вузлах сітки на сіткову функцію j(xh,yh) називається апроксимацією правої частини.

Таким чином диференціальне рівняння можна апроксимувати (замінити) на сітцірізної схемою

Lh yh = j (xh, yh) (наприклад,).

Вивчення різницевих апроксимацій проводиться спочатку локально, тобто. у будь-якому фіксованому вузлі сітки.

Нехай uh - проекція безперервної функції u(x) на сітку (наприклад, uh = u(xj) = uj).

Опр.Похибкою апроксимації диференціального оператора Lu різницевим оператором Lh назвемо величину y 1 = (Lu)h - Lh uh , де (Lu)h - проекція на сітку результату дії диференціального оператора L на функцію u

(наприклад,).

Опр.Кажуть, що похибка апроксимації диференціального оператора має у вузлі xi порядок k , якщо y 1(xi) = O(h k )  0 при h0.

Опр.Похибкою апроксимації правої частини f сітковою функцієюj h назвемо величину y 2 = fh - j h , де fh - проекція насітку функції f(x,u) (наприклад, f(xj,uj)).

Опр.Похибка апроксимації правої частини має у вузлі xi порядок m, якщо y 2 = O(h m ) 0 при h 0

Опр.Похибкою апроксимації різницевої схеми на рішенні у вузлі xi (локальною похибкою) назвемо величину y , рівну

тут використано, що Lu=f.

Опр.Значення локальної похибки апроксимації у кожному вузлі xi утворюють сіткову функцію похибки апроксимації y i .

Зазвичай потрібно оцінка похибки апроксимації на сітці, тобто. оцінка функції y i у деякій сітковій нормі.

Опр.Кажуть, що похибка апроксимації різницевої схеми має m-ий порядок на сітці, якщо чкyчк = O(h m ).

Опр.Рішення різницевої схеми сходиться до розв'язання диференціального рівняння з порядком k на сітці, якщо похибка розв'язання

ч до zh ч до =ч до uh - yh ч до = O(h k ) ® 0 при h® 0.9.1.Інтегральне подання задачі Коші.9.2. Ейлера (метод дотичних, ламаних і т. д.) Оцінка похибки.9.3.Метод Ейлера-Коші (метод предиктор-коректор). Оцінка похибки.9.4.Метод Рунге-Кутти 4-го порядку точності.

Насправді широко поширенийМетод Рунге - Кутта четвертого порядку :

Ця схема має четвертий порядок апроксимації.

9.6.Понятие крайової завдання ОДУ 2-го порядка.

9.7.Метод стрілянини (пристрілки).

9.8.Приклад жорсткого завдання Коші.

Методи оптимізації функцій.

Підоптимізацієюрозуміють процес вибору найкращого варіанта з усіх можливих.

У процесі вирішення задач оптимізації зазвичай необхідно знайтиоптимальні значення деяких параметрів, що визначають це завдання. При розв'язанні задач ці параметри зазвичай називаютьзміннимиабофакторамиоптимізації. Їх число (x1, x2, …, xn) визначаєрозмірністьзадачі оптимізації.

Вибір оптимального рішення чи порівняння двох альтернативних рішень проводиться з допомогою деякої залежної величини. Ця величина називаєтьсяцільовою функцією. У процесі розв'язання задачі оптимізації мають бути знайдені такі значення змінних оптимізації, за яких цільова функція має мінімум (або максимум).

Цільову функцію у загальному вигляді можна записати в такий спосіб

Розрізняють одно- та багатофакторну оптимізацію. У разі однофакторної оптимізації цільова функція є функцією однієї змінної та її графік - деяка крива на площині. При n=2, наприклад, цільова функція є функцією двох змінних і її графіком є поверхня.

Цільова функція не завжди може бути представлена у вигляді формули. Іноді може приймати деякі дискретні значення, задаватися як таблиці тощо.

Завдання оптимізації.Можна виділити два типи завдань оптимізації - безумовні та умовні.