Лабораторна робота 6. Розв’язування нелінійних рівнянь у системі matlab

1.  Набрати в системі MATLAB та відлагодити текст програми розв’язування нелінійних рівнянь.

2.  Визначити максимальні розміри областей збіжності ітераційного процесу розв’язування нелінійного рівняння до двох розв’язків кожного з трьох рівнянь (х²-1=0; sin(x)=0; tan(x)=0). Відзначити кількість ітерацій в кожному випадку.

3.   Пояснити всі оператори MATLAB-програми.

Під час виконання лабораторної роботи спочатку за графіком функції треба оцінити значення розв’язків та вибрати ті, для яких будемо визначати області збіжності ітераційного процесу.

Далі треба знайти граничні розміри початкового відрізка пошуку, за яких ітераційний процес пошуку збігається до обраного розв’язку. Початковий відрізок задає другий аргумент функції fzero. Треба багато разів знайти обраний розв’язок, поступово розширюючи початковий відрізок аж до найбільшого, за якого функція fzero ще знаходить цей розв’язок. Цей найбільший відрізок і є областю збіжності ітераційного процесу.

Процес пошуку області збіжності треба повторити для двох розв’язків кожного з трьох рівнянь: x²-1=0; sin(x)=0; tan(x)=0. Зверніть увагу на кількість ітерацій у процесі пошуку розв’язку та кількість розв’язків кожного рівняння.

Контрольні завдання до розділу 6

1. Перелічіть переваги та недоліки ітераційних методів розв’язування нелінійного рівняння з одним невідомим.

2. Запишіть ітераційні співвідношення метода простих ітерацій та метода Ньютона для систем нелінійних рівнянь.

Розділ 7. Методи безумовної оптимізації

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

Оптимізація здійснюється завдяки зміні деяких параметрів задачі, які називають параметрами оптимізації. Число цих параметрів є розмірністю задачі оптимізації. Оптимальний розв’язок знаходять за допомогою спеціальної функції від параметрів оптимізації, яку називають функцією мети, або критерієм якості. В процесі оптимізації функція мети досягає екстремального значення, тобто максимального чи мінімального. Відповідні значення параметрів оптимізації є розв’язком задачі. До речі, максимум функції мети співпадає з мінімумом функції мети з оберненим знаком.

Отже, математична задача оптимізації полягає в мінімізації функції мети f=f(x₁, x₂,..., x_n) за n-вимірним вектором параметрів оптимізації x=(x₁, x₂,..., x_n) у межах області Ω:

. (7.1)

Є два типи задач оптимізації – безумовні та умовні.

Задача (7.1) є безумовною. Відповідний розв’язок x_opt називають глобальним мінімумом. Прикладом безумовної оптимізації є розв’язування СЛАР за методом найменших квадратів (2.5). Тут параметрами оптимізації є складові вектора x=(x₁, x₂), функція мети f(x₁, x₂)= = , а область Ω – це вся область дійсних чисел.

Складнішими є умовні задачі, де на параметри накладено обмеження у вигляді рівнянь

(7.2)

і (або) нерівностей

. (7.3)

Обмеження загалом звужують область оптимізації. Задачу (7.1)-(7.3) називають умовною задачею оптимізації, а її розв’язок – локальним мінімумом.

Наведемо просту задачу умовної оптимізації.

Треба спроектувати контейнер у формі прямокутного паралепіпеда об’ємом 1м³, причому з мінімальними витратами матеріалу. За незмінної товщини стінок остання умова означає мінімальну поверхню контейнера. Якщо позначити х₁, х₂, х₃ довжини ребер контейнера, то задача полягає у мінімізації функції мети f=2(х₁х₂+х₁х₃+х₂х₃) за трьома параметрами х₁, х₂, х₃ з обмеженням х₁х₂х₃=1.

Рівняння-обмеження можна використати для виключення одного параметра: х₃=1/х₁х₂; f=2(х₁х₂+1/х₁+1/х₂). Таким чином, задача стала безумовною з двома параметрами. Її розв’язок є сумісним розв’язком двох рівнянь з двома невідомими: ∂f/∂x₁=2(х₂–1/х₁²)=0; ∂f/∂x₂=2(х₁–1/х₂²)=0. Майже очевидний їх розв’язок: х₁=х₂=1. З рівняння х₃=1/х₁х₂ маємо х₃=1. Отже, шуканий контейнер має форму куба з ребрами 1м.

Вивчає та розв’язує задачі умовної оптимізації важливий розділ прикладної математики – математичне програмування.

Розгляд методів оптимізації почнемо з найпростіших: безумовних одновимірних задач, тобто задач мінімізації функції одного аргументу f(x), якщо x лежить на відрізку [a,b] (a≤x≤b).

Шукати екстремальні точки функції f(x) легко, якщо на відрізку [a,b] існує похідна df(x)/dx. Тоді екстремум знаходиться або на границі відрізка [a,b], або у точках, що є розв’язками рівняння df(x)/dx=0.

Розглянемо приклад. Нехай треба знайти екстремуми функції f(x)=x³/3–x² на відрізку [1,3]. Похідна df(x)/dx=x²–2x. Розв’язки рівняння x²–2x=0 такі: x₁=0; x₂=2. Але точка x₁=0 є поза відрізком [1,3]. Отже, екстремальними можуть бути точки: a=1; x₂=2; b=3. Значення функції f(x) у цих точках такі: f(1)=–2/3; f(2)=–4/3; f(3)=0. Простим порівнянням значень функції знаходимо, що f_min=f(2)=–4/3, а f_max=f(3)=0. На рис. 20 показано графік функції та екстремальні точки.

Однак обчислити похідну можна не завжди. Часто функція мети задана лише сукупністю значень в певних точках. Можливий вихід – інтерполювати функцію мети степеневим поліномом або сплайном, для яких легко обчислити похідну. Недолік відповідних інтерполяційних методів – у появі похибок інтерполяції.

Загальна ідея числових пошукових методів полягає у послідовному звуженні інтервалу з екстремумом, поки розмір інтервалу не відповідатиме заданій точності ε.

Прямий перебір полягає у поділі відрізка [a,b] на n=2(b-a)/ε частин, обчисленні значень функції f(x) у кожній точці поділу та порівнянням значень виділити точки з найменшим значенням. Метод гранично простий, але вимагає обчислень значень функції (n+1) раз. Нехай довжина відрізка [a,b] рівна 1, а ε=0.001. Тоді значення функції треба обчислити 2001 раз.

Деяке ускладнення методу прямого перебору значно зменшує необхідні обчислення. Поділимо відрізок [a,b] не на 2000, а на 20 частин і знайдемо точку з найменшим значенням функції (21 обчислення функції). Далі відрізок, утворений сусідніми до екстремальної точками, поділимо ще на 20 частин і знайдемо точку з мінімумом функції вже у межах цього відрізка (ще 19 обчислень функції). Наступне наближення забезпечує задану точність знаходження екстремуму, а загальна кількість обчислень функції всього 59 проти 2001 при прямому переборі.

Метод „золотого січення” є найощадливішим методом глобальної оптимізації функцій однієї змінної. Тут вповні реалізовано основну ідею пошукових методів – побудова послідовності вкладених відрізків, що стягуються до точки мінімума, причому для кожного наступного відрізка значення функції обчислюється лише один раз. Це можливо завдяки простому правилу поділу відрізка на більшу і меншу частини за принципом „золотого січення”: відношення довжини відрізка до його більшої частини дорівнює відношенню більшої частини до меншої (дивись рис. 21).

Це правило вперше зустрічається в працях давньогрецького математика і філософа Евкліда (Eνκλειδηζ, Euclid, 3-тє ст. до н. е.), а відоме було ще Піфагору (Πυθαγορασ, Pythagoras, 6-те ст. до н. е.). Назву „золоте січення” дав знаменитий італійський митець, інженер і філософ кінця 15-го – початку 16-го сторіч Леонардо да Вінчі (Leonardo da Vinci). З його легкої руки багато наступних митців та дослідників вбачали в „золотому січенні” фундаментальне співвідношення живої та неживої природи, хоча об’єктивних підстав для цього вкрай мало.

Пошук мінімума функції починається „золотим січенням” початкового відрізка на частини, як показано на рис. 21. Серед значень функції у чотирьох точках знаходимо мінімальне і наступний відрізок утворюють точка мінімуму та ще дві найближчі до неї точки. Для „золотого січення” цього відрізка треба знайти лише одну нову точку. Саме тому кількість обчислень є мінімальною. Пошук триває, поки довжина чергового відрізка не стане меншою заданої точності.

Практичні методи одновимірної мінімізації є, як правило, комбінованими, тобто поєднують, наприклад, інтерполяційний та метод „золотого січення”.

Значно складнішими є методи мінімізації функції багатьох аргументів. Якщо обмежень немає, то мінімум функції f=f(x₁, x₂,..., x_n) знаходять серед точок, що є розв’язками системи рівнянь f(x₁, x₂,..., x_n)/x_i=0, (i=1,…,n). Приклад такої мінімізації показано трьома сторінками раніше при пошуку паралелепіпеда з найменшою поверхнею. Але далеко не завжди можна легко обчислити похідні функції мети. Тоді застосовують числові пошукові методи.

Одразу можна відкинути методи перебору, які є неприпустимо громіздкими для багатовимірних задач мінімізації. Необхідні спеціальні числові методи цілеспрямованого пошуку.

Порівняно простим є метод покоординатного спуску. Пошук мінімума функції мети f=f(x₁, x₂,..., x_n) починаємо з початкової точки з координатами x₁⁽⁰⁾, x₂⁽⁰⁾,..., x_n⁽⁰⁾. Зафіксуємо у цій точці всі координати, крім першої. Тоді f=f(x₁,x₂⁽⁰⁾,..., x_n⁽⁰⁾) є функцією лише однієї змінної x₁, і задача мінімізації розв’язується методами, що розглянуті вище. Знайдена точка мінімума з координатами x₁⁽¹⁾, x₂⁽⁰⁾,..., x_n⁽⁰⁾ є початковою для наступного кроку, де мінімізується функція мети f=f(x₁⁽¹⁾, x₂, x₃⁽⁰⁾,..., x_n⁽⁰⁾) за другою змінною. Послідовність кроків продовжується, поки задана точність не досягнена. Метод є послідовністю одновимірних задач оптимізації, але існує клас задач, які він принципово не може розв’язати. Часто графічне зображення функції мети має яроподібний вигляд, що у двовимірному випадку нагадує вузький яр зі стрімкими стінками і пологим дном. Метод покоординатного спуску швидко досягає дна яру, але подальший рух до мінімума за його дном різко сповільнюється або й зовсім зупиняється. Математично це означає, що функція мети досягла мінімума за кожною змінною зокрема, але це ще не є мінімум за всіма змінними одночасно.

Успішно справляється з яроподібними задачами метод градієнтного спуску. В природі є чимало оптимізаційних задач. Наприклад, вода стікає на дно ями за найкоротшими траєкторіями, що відповідають найбільшій крутизні стінок ями. Ця крутизна математично виражається поняттям градієнта. Градієнтом функції f=f(x₁, x₂,..., x_n) у точці (x₁⁽⁰⁾, x₂⁽⁰⁾,..., x_n⁽⁰⁾) є вектор, складові якого є частинними похідними функції у заданій точці:

. (7.4)

Вектор градієнту показує напрям найбільшого зростання функції. Отже, якщо зробити крок у напрямі антиградієнта, то функція загалом зменшується. Величину кроку визначають спеціальні адаптивні алгоритми. Нова точка (x₁⁽¹⁾, x₂⁽¹⁾,..., x_n⁽¹⁾), у якій значення функції мети зменшилось, є початковою для наступного кроку. У цій точці знову обчислюють градієнт

(7.5)

та здійснюють крок у протилежному напрямку. Процес пошуку неухильно наближується до точки мінімума, де всі складові градієнта рівні нулю. Недоліком градієнтного спуску є обчислення градієнта (7.5) на кожному кроці. Аналітичне диференціювання функції мети можливе у виключних випадках. Як правило, складові градієнта знаходять наближено:

. (7.6)

Обчислення градієнта на кожному кроці обтяжливе. Метод найшвидшого спуску, вперше запропонований знаменитим радянським математиком і економістом Л. В. Канторовичем, є поширеною модифікацією градієнтного метода. За методом найшвидшого спуску рух у напрямі антиградієнта триває не один крок, а поки функція мети зменшується. Коли мінімум досягнено, рух продовжується за новим напрямом, що вказує обчислений антиградієнт у цій точці. Таким чином, точок обчислення градієнта значно менше. По суті, метод найшвидшого спуску поєднує методи покоординатного і градієнтного спуску. Мінімізація функції мети за антиградієнтом є одновимірною задачею мінімізації вздовж напряма антиградієта, а в методі покоординатного спуску напрям співпадає по черзі з осями координат.