Головна | Про нас | Зворотній зв'язок
Велику групу методів уточнення кореня представляють ітераційні методи - методи послідовних наближень. Тут на відміну від методу дихотомії задається не початковий інтервал місцезнаходження кореня, а його початкове наближення.
Найбільш популярним з ітераційних методів є метод Ньютона (метод дотичних).
Мал. 3. Метод дотичних
Нехай відомо деяке наближене значення Zn кореня X *. Застосовуючи формулу Тейлора і обмежуючись в ній двома членами, маємо
Геометрично цей метод пропонує побудувати дотичну до кривої y = f (x) в потрібній точці x = Zn. знайти точку перетину її з віссю абсцис і прийняти цю точку за чергове наближення до кореня (3).
Мал. 6 Геометрична інтерпретація методу простої ітерації
Звідси може бути побудований ітераційний процес
Візьмемо для прикладу рівняння x 3 + x -1000 = 0. Очевидно, що корінь даного рівняння дещо менше 10. Якщо переписати це рівняння у вигляді x = 1000 - x 3 і почати ітераційний процес при x0 = 10. то з перших же наближень очевидна його розбіжність. Якщо ж врахувати f '(x) = 3x 2 +1> 0 і прийняти за наближене значення максимуму f' (x) M = 300. то можна побудувати сходиться ітераційний процес на основі подання
Можна і штучно підібрати підходящу форму рівняння, наприклад:
Розглянемо задачу знаходження кореня рівняння методом Ньютона з використанням циклічних посилань. Візьмемо для прикладу квадратне рівняння: х 2 - 5х + 6 = 0. графічне представлення якого наведено на 7 Знайти корінь цього (і будь-якого іншого) рівняння можна, використовуючи всього одну клітинку Excel.
Для включення режиму циклічних обчислень в меню Сервіс / Параметри / вкладка Обчислення включаємо прапорець Ітерації. при необхідності змінюємо число повторень циклу в поле Граничне число ітерацій і точність обчислень в поле Відносна похибка (за замовчуванням їх значення рівні 100 і 0,0001 відповідно). Крім цих установок вибираємо варіант ведення обчислень: автоматично або вручну. При автоматичному обчисленні Excel видає відразу кінцевий результат, при обчисленнях, вироблених вручну. можна спостерігати результат кожної ітерації.
Мал. 7. Графік функції
Виберемо довільну клітинку, дамо їй нове ім'я, скажімо - Х. і введемо в неї рекуррентную формулу, що задає обчислення за методом Ньютона:
де F і F1 задають відповідно вираження для обчислення значень функції і її похідної. Для нашого квадратного рівняння після введення формули в комірці з'явиться значення 2. відповідне одному з коренів рівняння (рис. 8). У нашому випадку початкове наближення не ставити, ітераційний обчислювальний процес починався зі значення, за умовчанням зберігається в осередку Х і рівного нулю. А як отримати другий корінь? Зазвичай це можна зробити зміною початкового наближення. Вирішувати проблему завдання початкових установок в кожному випадку можна по-різному. Ми продемонструємо один прийом, заснований на використанні функції ЯКЩО. З метою підвищення наочності обчислень осередкам були присвоєні змістовні імена (рис 8).
· У осередок Хнач (В4) заносимо початкове наближення - 5.
· У осередок Хтекущ (С4) записуємо формулу:
= ЕСЛИ (Хтекущ = 0; Хнач; Хтекущ- (Хтекущ ^ 2-5 * Хтекущ + 6) / (2 * Хтекущ-5)).
· У осередок D4 поміщаємо формулу, що задає обчислення значення функції в точці Хтекущ. що дозволить стежити за процесом рішення.
· Зауважте, що на першому кроці обчислень в осередок Хтекущ буде поміщено початкове значення, а потім вже почнеться рахунок за формулою на наступних кроках.
· Щоб змінити початкове наближення, недостатньо змінити вміст комірки Хнач і запустити процес обчислень. У цьому випадку обчислення будуть продовжені, починаючи з останнього обчисленого
Мал. 8. Визначення початкових установок
значення. Щоб обнулити значення, що зберігається в осередку Хтекущ. потрібно заново записати туди формулу. Для цього достатньо для редагування вибрати комірку, що містить формулу, двічі клацнувши мишею на ній (при цьому вміст комірки відобразиться в рядку формул). Клацання по кнопці (натискання клавіші) Enter запустить обчислення з новим початковим наближенням.
• В клітинку С3 (рис. 10) введемо формулу для обчислення значення функції, що стоїть в рівнянні зліва від знака рівності. Як аргумент використовуємо посилання на осередок С2, тобто = С2 ^ 2-5 * C2 + 6.
• У вікні діалогу Підбір параметра (рис. 10) в поле Встановити в осередку введемо посилання на клітинку з формулою, в поле Значення - очікуваний результат, на полі Змінюючи значення осередки - посилання на осередок, в якій буде зберігатися значення підбирається параметра (вміст цієї осередку не може бути формулою).
• Після натискання на кнопку Ok Excel виведе вікно діалогу Результат підбору параметра. Якщо підібране значення необхідно зберегти, то
Повернемося до прикладу. Знову виникає питання: як отримати другий корінь? Як і в попередньому випадку необхідно задати початкове наближення. Це можна зробити наступним чином (рис. 11, а):
Мал. 11. Пошук другого кореня
• У осередок Х (С2) вводимо початкове наближення.
• У осередок Хi (С3) вводимо формулу для обчислення чергового наближення до кореня, тобто = X- (X ^ 2-5 * X + 6) / (2 * X-5).
• В клітинку С4 помістимо формулу, що задає обчислення значення функції, що стоїть в лівій частині вихідного рівняння, в точці Хі.
• Після цього вибираємо команду Підбір параметра, де в якості змінюваної осередку приймаємо осередок С2Результат обчислень зображений на рис. 11, б (в комірці С2 - кінцеве значення, а в осередку С3 попереднє). Однак все це можна зробити і дещо простіше. Для того щоб знайти другий корінь, досить як початкове наближення (рис. 10) в осередок C2 помістити константу 5 і після цього запустити процес Підбір параметра.
Команда Підбір параметра є зручною для вирішення завдань пошуку певного цільового значення, що залежить від одного невідомого параметра. Для більш складних завдань слід використовувати команду Пошук рішення (Вирішувач). Завдання, які можна вирішувати за допомогою Пошуку рішення. в загальній постановці формулюються так:
Шукані змінні - осередки робочого аркуша Excel - називаються регульованими осередками. Цільова функція F (х1. Х2. .... Хn). звана іноді просто метою, повинна задаватися у вигляді формули в осередку робочого аркуша. Ця формула може містити функції, визначені користувачем, і повинна залежати (посилатися) від регульованих осередків. У момент постановки задачі визначається, що робити з цільовою функцією. Можливий вибір одного з варіантів:
Функції G (х1. Х2. .... Хn) називаються обмеженнями. Їх можна задати як у вигляді рівності, так і нерівностей. На регульовані осередку можна накласти додаткові обмеження: невід'ємності та / або целочисленности, тоді шукане рішення шукається в області позитивних і / або цілих чисел.
Під цю постановку потрапляє найширше коло завдань оптимізації, в тому числі рішення різних рівнянь і систем рівнянь, завдання лінійного та нелінійного програмування. Такі завдання зазвичай простіше сформулювати, ніж вирішувати. І тоді для вирішення конкретної оптимізаційної задачі потрібно спеціально для неї сконструйований метод. Вирішувач має в своєму арсеналі потужні засоби виконання таких завдань: метод узагальненого градієнта, симплекс-метод, метод гілок і меж.
Розглянемо, як скористатися Пошуком рішення на прикладі того ж квадратного рівняння.
Мал. 11. Вікно діалогу Пошук рішення
Після відкриття діалогу Пошук рішення (11) необхідно виконати наступні дії:
2. для максимізації значення цільової осередки, встановити перемикач максимального значення в положення # 61496 ;, для мінімізації використовується перемикач мінімального значення. в нашому випадку встановлюємо перемикач в положення значенням і вводимо значення 0;
4. в поле Обмеження за допомогою кнопки Додати ввести всі обмеження, яким повинен відповідати результат пошуку: для нашого прикладу обмежень задавати не потрібно;
5. для запуску процесу пошуку рішення натиснути кнопку Виконати.
Для збереження отриманого рішення необхідно використовувати перемикач Зберегти знайдене рішення в вікні діалогу Результати пошуку рішення. Після чого робочий лист прийме вигляд, представлений на рис.12. Отримане рішення залежить від вибору початкового наближення, яке задається в осередку С4 (аргумент функції). Якщо в якості початкового наближення в клітинку С4 ввести значення, рівне 1,0. то за допомогою Пошуку рішення знайдемо другий корінь, що дорівнює 2,0.
Мал. 12. Результати пошуку
Опції, що керують роботою Пошуку рішення. задаються у вікні Параметри (вікно з'являється, якщо натиснути на кнопку Параметри вікна Пошук рішення), наступні (рис. 13):
Мал. 13. Налаштування параметрів розв'язувача
· Максимальний час - обмежує час, відведений на процес пошуку рішення (за замовчуванням задано 100 секунд, що достатньо для задач, що мають близько 10 обмежень, якщо завдання великої розмірності, то час необхідно збільшити).
· Граничне число ітерацій - ще один спосіб обмеження часу пошуку шляхом завдання максимального числа ітерацій. За замовчуванням задано 100, і, найчастіше, якщо рішення не отримано за 100 ітерацій, то при збільшенні їх кількості (в поле можна ввести час, що не перевищує 32767 секунд) ймовірність отримати результат мала. Краще спробувати змінити початкове наближення і запустити процес пошуку заново.
· Відносна похибка - задає точність, з якою визначається відповідність осередку цільового значення або наближення до вказаних обмежень (десяткова дріб від 0 до 1).
· Допустиме відхилення - задається в% тільки для задач з цілочисельними обмеженнями. Пошук рішення в таких завданнях спочатку знаходить оптимальне нецелочисленное рішення, а потім намагається знайти найближчу целочисленную точку, рішення в якій відрізнялося б від оптимального не більше, ніж на вказане даними параметром кількість відсотків.
· Відповідність - коли відносна зміна значення в цільовій комірці за останні п'ять ітерацій стає меншою від кількості (дріб з інтервалу від 0 до 1), зазначеного в даному параметрі, пошук припиняється.
· Лінійна модель - цей прапорець слід включати, коли цільова функція і обмеження - лінійні функції. Це прискорює процес пошуку рішення.
· Позитивне значення - цим прапорцем можна задати обмеження на змінні, що дозволить шукати рішення в позитивній області значень, не ставлячи спеціальних обмежень на їх нижню межу.
· Автоматичне масштабування - цей прапорець слід включати, коли масштаб значень вхідних змінних і цільової функції і обмежень відрізняється, можливо, на порядки. Наприклад, змінні задаються в штуках, а цільова функція, яка визначає максимальний прибуток, вимірюється в мільярдах рублів.
· Показувати результати ітерацій - цей прапорець дозволяє включити покроковий процес пошуку, показуючи на екрані результати кожної ітерації.
· Оцінки - ця група служить для вказівки методу екстраполяції - лінійна або квадратична, - використовуваного для отримання вихідних оцінок значень змінних в кожному одновимірному пошуку. Лінійна служить для використання лінійної екстраполяції вздовж дотичного вектора. Квадратична служить для використання квадратичної екстраполяції, яка дає кращі результати при вирішенні нелінійних задач.
· Різниці (похідні) - ця група служить для вказівки методу чисельного диференціювання, який використовується для обчислення приватних похідних цільових і обмежують функцій. Параметр Прямі використовується в більшості завдань, де швидкість зміни обмежень відносно невисока. Параметр Центральні використовується для функцій, що мають розривну похідну. Даний спосіб вимагає більше обчислень, однак його застосування може бути виправданим, якщо видається повідомлення про те, що отримати більш точне рішення не вдається.
· Метод пошуку - служить для вибору алгоритму оптимізації. Метод Ньютона було розглянуто раніше. У способі сполучених градієнтів запитується менше пам'яті, але виконується більше ітерацій, ніж в методі Ньютона. Даний метод слід використовувати, якщо завдання досить велика і необхідно економити пам'ять, а також якщо ітерації дають занадто мале відмінність у послідовних наближень.
Зберегти модель пошуку рішення за допомогою таких дій:
1. при збереженні книги Excel після пошуку рішення все значення, введені в вікнах діалогу Пошук рішення. зберігаються разом з даними робочого аркуша. З кожним робочим листом в робочій книзі можна зберегти один набір значень параметрів Пошуку рішення;
2. якщо в межах одного робочого листа Excel необхідно розглянути кілька моделей оптимізації (наприклад знайти максимум і мінімум однієї функції, або максимальні значення декількох функцій), то зручніше зберегти ці моделі, використовуючи кнопку Параметри / Зберегти модель вікна Пошук рішення. Діапазон для зберігається моделі містить інформацію про цільовій комірці, про змінюваних осередках, про кожного з обмежень і все значення діалогу Параметри. Вибір моделі для вирішення конкретної оптимізаційної задачі здійснюється за допомогою кнопки Параметри / Завантажити модель діалогу Пошук рішення;
3. ще один спосіб збереження параметрів пошуку - збереження їх у вигляді іменованих сценаріїв. Для цього необхідно натиснути на кнопку Зберегти сценарій діалогового вікна Результати пошуку рішень.
Крім вставки оптимальних значень в змінювані осередки Пошук рішення дозволяє представляти результати у вигляді трьох звітів: Результати. Стійкість і Межі. Для генерації одного або декількох звітів необхідно виділити їх назви у вікні діалогу Результати пошуку рішення. Розглянемо більш детально кожен з них.
Мал. 14. Звіт по стійкості
Звіт по стійкості (14) містить інформацію про те, наскільки цільова осередок чутлива до змін обмежень і змінних. Цей звіт має два розділи: один для змінюваних осередків, а другий для обмежень. Права колонка в кожному розділі містить інформацію про чутливість. Кожна змінна осередок і обмеження наводяться в окремому рядку. Розділ для змінюваних осередків містить значення нормованого градієнта, яке показує, як ціла осередок реагує на збільшення значення у відповідній змінною осередку на одну одиницю. Подібним чином, множник Лагранжа в розділі для обмежень показує, як цільова осередок реагує на збільшення відповідного значення обмеження на одну одиницю. При використанні цілочисельних обмежень Excel виводить повідомлення Звіти стійкість і Межі неспроможні для задач з цілочисельними обмеженнями. Якщо у вікні діалогу Параметри пошуку рішення встановлений прапорець Лінійна модель. то звіт по стійкості містить кілька додаткових стовпців інформації.
Мал. 15. Звіт за результатами
Звіт за результатами (15) містить три таблиці: в першій наведені відомості про цільової функції до початку обчислення, в другій - значення шуканих змінних, отримані в результаті рішення задачі, в третій - результати оптимального рішення для обмежень. Цей звіт також містить інформацію про таких параметрах кожного обмеження, як статус і різниця. Статус може приймати три стану: пов'язане, несвязанное або невиконане. Значення різниці - це різниця між значенням, які видає в осередку обмеження при отриманні рішення, і числом, заданим в правій частині формули обмеження. Пов'язане обмеження - це обмеження, для якого значення різниці дорівнює нулю. Несвязанное обмеження - це обмеження, яке було виконано з ненульовим значенням різниці.