Метод хибного положення

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

Як приклад розглянемо задачу 26 у папірусі Рейнда, в якій треба знайти розв'язок (тут поданого в сучасному записі) рівняння Шаблон:Math. Розв'язок знаходимо виходячи з хибного положення. Спочатку припускаємо, що Шаблон:Math, щоб отримати ліворуч Шаблон:Nobr. Це припущення хороший вибір, бо воно створює ціле число. Однак 4 це не розв'язок заданого рівняння, бо воно дає значення, яке втричі замале. Щоб надолужити нестачу, помножимо Шаблон:Mvar (наразі встановлений у 4) на 3 і знову підставимо, щоб отримати Шаблон:Nobr, переконавшись, що рішення це Шаблон:Math.

У сучасних версіях методики ми використовуємо систематичні способи вибору нових пробних значень і переймаємось питаннями про те, можна отримати наближення до розв'язку чи ні, і якщо можна, то як швидко можна знайти наближення.

Два історичні типи

Історично можна виділити два основних типи методу хибного положення: просте хибне положення та подвійне хибне положення.

Подвійне хибне положення спрямоване на розв'язання складніших задач, які алгебрично можна записати у вигляді: визначити Шаблон:Math так, що

$ax=b,$

якщо Шаблон:Math і Шаблон:Math відомі. Метод починається з використання пробного вхідного значення Шаблон:Math і знаходження відповідного вихідного значення Шаблон:Math шляхом множення: Шаблон:Math. Потім правильну відповідь знаходять шляхом пропорційного підправляння, Шаблон:Math

Просте хибне положення спрямоване на розв'язання задач, що стосуються прямої пропорції. Такі задачі можна записати алгебрично у вигляді: визначити Шаблон:Math таке, що

$f(x)=ax+c=0,$

якщо відомо, що

$f(x_1)=b_1,f(x_2)=b_2.$

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

$x=\frac{b_1{x}_2-b_2{x}_1}{b_1-b_2},$

можна запам'ятати й виконувати.

Для афінної лінійної функції,

$f(x)=ax+c,$

подвійне хибне положення забезпечує точне рішення, тоді як для нелінійної функції Шаблон:Math воно забезпечує наближення, яке можна послідовно покращувати ітеративним шляхом.

Числовий аналіз

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

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

У заданому рівнянні, перемістіть усі його члени в одну сторону, щоб воно мало вигляд Шаблон:Math, де Шаблон:Mvar це деяка функція невідомої змінної Шаблон:Mvar. Значення Шаблон:Mvar, яке задовольняє це рівняння, тобто Шаблон:Math, називається коренем або нулем функції Шаблон:Mvar і це розв'язок вихідного рівняння. Якщо Шаблон:Mvar — неперервна функція і існують дві точки Шаблон:Math і Шаблон:Math такі, що Шаблон:Math і Шаблон:Math протилежних знаків, то за теоремою про проміжне значення функція Шаблон:Math має корінь на проміжку Шаблон:Math.

Існує багато алгоритмів знаходження кореня, які можна використовувати для отримання наближених значень такого кореня. Один із найпоширеніших це метод Ньютона, але він може не знайти корінь за певних обставин і може бути обчислювально дорогим, бо вимагає обчислення похідної функції. Потрібні інші методи, і один загальний клас методів – це методи двоточкового дужкування. Ці методи просуваються створюючи послідовність все менших проміжків Шаблон:Math на Шаблон:Mvar -му кроці, так що Шаблон:Math містить корінь Шаблон:Math.

Методи двоточкового дужкування

Ці методи починаються з двох значень Шаблон:Mvar, спочатку знайдених методом проб і помилок, при яких Шаблон:Math має протилежні знаки. Згідно з припущенням безперервності, корінь Шаблон:Mvar гарантовано лежить між цими двома значеннями, тобто ці значення «закривають» корінь. Потім вибирається точка, що лежить між цими двома значеннями, і використовується для створення меншого проміжку, який все ще бере в дужки корінь. Якщо вибрана точка Шаблон:Mvar, то маємо менший інтервал, який пролягає від Шаблон:Mvar до кінцевої точки, де Шаблон:Math має знак, протилежний знаку Шаблон:Math. У малоймовірному випадку, коли Шаблон:Math, корінь знайдено, і алгоритм зупиняється. В іншому випадку процедура повторюється так часто, як необхідно, щоб отримати наближення до кореня з будь-якою бажаною точністю.

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

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

$c_k=\frac{a_k+b_k}{2}.$

Це гарантує, що Шаблон:Mvar лежить між Шаблон:Mvar і Шаблон:Mvar, тим самим гарантуючи збіжність до рішення.

А що довжина проміжку дужкування зменшується вдвічі на кожному кроці, похибка методу поділу навпіл зменшується в середньому вдвічі з кожною ітерацією. Таким чином, кожні 3 ітерації метод отримує приблизно коефіцієнт 2 ³, тобто приблизно десятковий знак, у точності.

Метод хибного положення.

Перші дві ітерації методу хибного положення. Червона крива показує функцію Шаблон:Mvar, а сині лінії — січні.

Швидкість збіжності методу поділу навпіл можна було б покращити за допомогою іншого оцінювання розв'язку.

Метод хибного положення обчислює нову оцінку розв’язку як точку перетину [[Нуль функції|Шаблон:Mvar відрізка]], що з’єднує кінцеві точки функції на поточному інтервалі дужок. По суті, корінь апроксимується шляхом заміни фактичної функції відрізком лінії на проміжку дужкування, а потім використанням класичної формули подвійного хибного положення на цьому відрізку лінії.

Точніше, припустімо, що на Шаблон:Mvar-й ітерації проміжок дужкування це Шаблон:Math. Збудуємо пряму через точки Шаблон:Math і Шаблон:Math, як показано на рисунку. Ця пряма це січна або хорда графіка функції Шаблон:Math. У формі з коефіцієнтом нахилу її рівняння задається як

$y-f(b_k)=\frac{f(b_k)-f(a_k)}{b_k-a_k}(x-b_k).$

Тепер виберемо Шаблон:Math як точку перетину цієї лінії з віссю Шаблон:Mvar, тобто значення Шаблон:Mvar, для якого Шаблон:Math, і підставимо ці значення, щоб отримати

$f(b_k)+\frac{f(b_k)-f(a_k)}{b_k-a_k}(c_k-b_k)=0.$

Розв'язування цього рівняння для c _k дає:

$c_k=b_k-f(b_k)\frac{b_k-a_k}{f(b_k)-f(a_k)}=\frac{a_{k}f(b_k)-b_{k}f(a_k)}{f(b_k)-f(a_k)}.$

Ця остання симетрична форма має обчислювальну перевагу:

З наближенням до розв’язку Шаблон:Mvar і Шаблон:Mvar будуть дуже близькими одне до одного і майже завжди з однаковим знаком. При такому відніманні можна втратити значущі розряди. А що Шаблон:Math і Шаблон:Math завжди мають протилежний знак, «віднімання» в чисельнику вдосконаленої формули фактично є додаванням (як і віднімання в знаменнику).

На ітерації з номером Шаблон:Math число Шаблон:Mvar обчислюється, як зазначено вище, а потім, якщо Шаблон:Math і Шаблон:Math мають однаковий знак, встановлюємо Шаблон:Math і Шаблон:Math, інакше встановлюємо Шаблон:Math і Шаблон:Math. Цей процес повторюється до тих пір, поки корінь не буде достатньо добре апроксимований.

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

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

Аналіз

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

Одним із прикладів цього явища є функція

$f(x)=2x^3-4x^2+3x$

на початковому проміжку [− 1,1]. Лівий кінець, −1, ніколи не замінюється (він не змінюється спочатку та після перших трьох ітерацій, Шаблон:Math від'ємна на інтервалі), тому ширина проміжку ніколи не опускається нижче 1. Отже, права кінцева точка наближається до 0 з лінійною швидкістю (кількість точних цифр зростає лінійно, зі швидкістю збіжності 2/3).

Для функцій з розривами можна очікувати, що цей метод знайде лише точку, де функція змінює знак (наприклад, при Шаблон:Math для Шаблон:Math або функції знаку). На додаток до зміни знаку, також можливо, щоб метод збігався до точки, де границя функції рівна нулю, навіть якщо функція не визначена (або має інше значення) у цій точці (наприклад, при Шаблон:Math для функції, задана Шаблон:Math коли Шаблон:Math і через Шаблон:Math, починаючи з інтервалу [-0,5, 3,0]). Математично це можливо, щоб у функції з розривами метод не збігся до нульової границі або зміни знаку, але це не завдає клопоту на практиці, бо знадобиться нескінченна послідовність збігів, щоб обидві кінцеві точки застрягти й не збіглись до розривів, в яких знак не змінюється, наприклад при Шаблон:Math в

$f(x)=\frac{1}{(x-1{)}^2}+\frac{1}{(x+1{)}^2}.$

Метод поділу навпіл дозволяє уникнути цієї гіпотетичної проблеми збіжності.