Алгоритм, за яким працює функція fzero
Як вже говорилося в розділі Основні способи звернення до fzero. при зверненні до fzero можливо вказати:
- або початкове наближення до кореня;
- або відрізок, на якому досліджувана функція приймає значення різних знаків.
Якщо задано початкове наближення, то fzero починає пошук відрізка, що містить корінь, тобто такого, на межах якого досліджувана функція змінює знак.Реалізованний в fzero спосіб пошуку цього відрізка описаний нижче в розділі Пошук в функції fzero інтервалу, що містить корінь. Коли відрізок знайдений, то починає роботу алгоритм уточнення кореня, заснований на декількох методах чисельного рішення рівнянь (див. Розділ Алгоритм уточнення кореня в функції fzero). Якщо ж з самого початку в fzero було поставлено відрізок, на межах якого функція змінює знак, то цей алгоритм щодо уточнення кореня відразу починає роботу.
Пошук в функції fzero інтервалу, що містить корінь
Якщо функція fzero викликана з початковим наближенням до кореню
а не з відрізком, на межах якого відбувається зміна знака досліджуваної функції, то відбувається пошук такого відрізка з метою відокремлення кореня. Алгоритм відділення кореня в функції fzero досить простий.
Спочатку вибирається крок рівний (для не дорівнює 0), або (для рівного 0). Далі обчислюється значення досліджуваної функції в точці і порівнюється зі значенням досліджуваної функції в точці. Якщо і різних знаків, то корінь відділений, а якщо знаки збігаються, то відбувається розширення проміжку вправо від точка до і порівнюються знаки функції в точках a і b. Якщо вони різні, то корінь відділений, а якщо немає, то в циклі відбувається послідовне збільшення кроку в раз і розширення проміжку вліво, а потім і вправо від точки з перевіркою знаків функції на кордонах. Як тільки знаки стануть різними, відділення кореня припиняється і починає працювати алгоритм щодо його уточнення, описаний в розділі Алгоритм уточнення кореня в fzero.
У вищеописаному алгоритмі відділення кореня проводиться перевірка: чи є значення досліджуваної функції в одержуваних точках кінцевими і речовими. Якщо значення функції виявилися комплексними, або в процесі обчислень виникло переповнення при обчисленнях з плаваючою точкою, то робота fzero припиняється і виводиться відповідне повідомлення в командне вікно.
Такий алгоритм може і не відокремити корінь при невдало заданому початковому наближенні. Наприклад, візьмемо рівняння
і поставимо в якості початкового наближення значення = 500. Простежимо за кожним кроком алгоритму fzero. Для цього поставимо в якості третьої вхідного аргументу структуру opts з полем Display, значення якого встановлено в 'iter'. Структуру opt сформуємо за допомогою функції optimset (див. Розділ Вхідні аргументи fzero).
Отримуємо, що після першого ж розширення проміжку вліво стався вихід за обидва кореня і подальше збільшення проміжку призводить до переповнення.
Завдання ж значення = 498.5 призводить до вдалого відділенню одного з коренів уже на другому кроці (рівного 498, тому що спочатку відбувається розширення проміжку вліво) і його подальшому уточненню. У розділі Основні способи звернення до fzero був розглянутий приклад рівняння
для якого вказівку 3.2 в якості початкового наближення призвело до зупинки роботи fzero через вихід за область визначення функції (подкоренное вираз ставало негативним) і появі комплексних значень при відділенні кореня.
Дані приклади свідчать про важливість попереднього дослідження рівняння з метою відокремлення його коренів.
Алгоритм уточнення кореня в функції fzero
Якщо корінь уже відділена, або в при виклику fzero з самого початку було поставлено відрізок, на межах якого досліджувана функція змінює знак, то відбувається уточнення кореня. Для цього використовується алгоритм, який є комбінація трьох методів чисельного рішення нелінійних рівнянь:
- метод половинного ділення (bisection);
- метод січних (secant або linear interpolation);
- метод зворотного квадратичної інтерполяції (inverse quadratic interpolation).
Наведемо короткі відомості про ці методи.
Метод половинного ділення заснований на теоремі Больцано-Коші, згідно з якою безперервна функція, що приймає на кордонах відрізка значення різних знаків, має на цьому відрізку хоча б один корінь. Метод полягає в наступному.
- Заданий відрізок [a, b]. на кордонах якого функція приймає значення різних знаків (передбачається, що функція неперервна).
- Відрізок ділиться навпіл точкою і з отриманих половин [a, c] і [c, b] вибирається та, на кордонах якої знаки різні. Обрана половина відрізка позначається [a, b].
- Так триває до тих пір, поки довжина отриманого відрізка не стане менше заданої точності. Оскільки корінь безперервної функції весь час знаходиться між точками a і b. то за наближене із заданою точністю значення до кореня можна взяти або точку a. або точку b (див. малюнок).
Для безперервних функції метод половинного ділення завжди призводить до знаходження кореня з заданою точністю. Недоліком його є надто повільна збіжність, на кожному кроці помилка зменшується всього лише в 2 рази. Тому в арсеналі fzero містяться ще два методи: метод січних і метод зворотного квадратичної інтерполяції, які більш швидко сходяться до кореня, ніж метод половинного ділення, в разі, якщо функція задовольняє деяким додатковим умовам. Таким чином, на практиці, як правило, виявляється, що fzero знаходить корінь істотно швидше, ніж метод половинного ділення.
Примітка.
Якщо для уточнення кореня рівняння використовуються ітераційні методи, які за поточним наближенню xk будують нове наближення xk +1. то їх можна порівняти по порядку збіжності. Під порядком збіжності ітераційного методу розуміють наступне. Якщо ek = xk -x * - помилка на кожній ітерації (тут x * - точне рішення рівняння), то порядком збіжності називають число p таке, що:
Примітка.
При порівнянні ефективності чисельних методів для уточнення кореня функції слід брати до уваги не тільки порядки збіжності методів. Справа в тому, що деякі методи вимагають обчислення на кожній ітерації не тільки вихідної функції, але і знаходження значень деяких інших функцій (наприклад похідною від). Кращим виявляється той метод, який дозволяє знайти корінь з заданою точністю за найменшу кількість обчислень функції. тому це найдорожча операція при уточненні кореня, а зовсім не той метод, який вимагає менше ітерацій.
Звернемося тепер до другого методу уточнення кореня, використовуваному в алгоритмі функції fzero.
Метод січних полягає в тому, що вибираються дві початкові точки, через які проводиться січна. В якості нового наближення до кореня береться абсциса перетину січної і осі Ox (див. Малюнок).
-7 тут викликана похибкою при знаходженні власних чисел супроводжує матриці функцією eig, використовуваної в алгоритмі функції roots. Самі коефіцієнти полінома були знайдені точно.
Тепер змінимо коефіцієнт при x 11 у вихідному поліномі на 10 -5 і знайдемо корені полінома з такими коефіцієнтами.
Отримуємо, що шість коренів полінома стали комплексними з досить великою уявної частиною в порівнянні з обуренням в коефіцієнті.
У тому, що з'явилися комплексні корені, можна переконатися і побудувавши графік полінома з обуреними коефіцієнтами