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

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

Як приклад розглянемо задачу 26 у папірусі Рейнда, в якій треба знайти розв'язок (тут поданого в сучасному записі) рівняння x + x/4 = 15. Розв'язок знаходимо виходячи з хибного положення. Спочатку припускаємо, що x = 4, щоб отримати ліворуч 4 + 4/4 = 5 . Це припущення хороший вибір, бо воно створює ціле число. Однак 4 це не розв'язок заданого рівняння, бо воно дає значення, яке втричі замале. Щоб надолужити нестачу, помножимо x (наразі встановлений у 4) на 3 і знову підставимо, щоб отримати 12 + 12/4 = 15, переконавшись, що рішення це x = 12 .

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

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

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

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

$ax=b,$

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

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

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

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

$f(x_{1})=b_{1},\qquad f(x_{2})=b_{2}.$

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

$x={\frac {b_{1}x_{2}-b_{2}x_{1}}{b_{1}-b_{2}}},$

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

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

$f(x)=ax+c,$

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

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

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

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

У заданому рівнянні, перемістіть усі його члени в одну сторону, щоб воно мало вигляд f (x) = 0, де f це деяка функція невідомої змінної x . Значення c, яке задовольняє це рівняння, тобто f (c) = 0, називається коренем або нулем функції f і це розв'язок вихідного рівняння. Якщо f — неперервна функція і існують дві точки a₀ і b₀ такі, що f (a₀) і f (b₀) протилежних знаків, то за теоремою про проміжне значення функція f має корінь на проміжку (a₀, b₀) .

Існує багато алгоритмів знаходження кореня, які можна використовувати для отримання наближених значень такого кореня. Один із найпоширеніших це метод Ньютона, але він може не знайти корінь за певних обставин і може бути обчислювально дорогим, бо вимагає обчислення похідної функції. Потрібні інші методи, і один загальний клас методів – це методи двоточкового дужкування. Ці методи просуваються створюючи послідовність все менших проміжків [a_k, b_k] на k -му кроці, так що (a_k, b_k) містить корінь f .

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

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

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

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

$c_{k}={\frac {a_{k}+b_{k}}{2}}.$

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

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

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

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

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

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

Точніше, припустімо, що на k-й ітерації проміжок дужкування це (a_k, b_k). Збудуємо пряму через точки (a_k, f (a_k)) і (b_k, f (b_k)), як показано на рисунку. Ця пряма це січна або хорда графіка функції f. У формі з коефіцієнтом нахилу її рівняння задається як

$y-f(b_{k})={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-b_{k}).$

Тепер виберимо c_k як точку перетину цієї лінії з віссю x, тобто значення x, для якого y = 0, і підставимо ці значення, щоб отримати

$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})}}.$

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

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

На ітерації з номером k число c_k обчислюється, як зазначено вище, а потім, якщо f (a_k) і f (c_k) мають однаковий знак, встановлюємо a_{k + 1} = c_k і b_{k + 1} = b_k, інакше встановлюємо a_{k + 1} = a_k і b_{k + 1} = c_k . Цей процес повторюється до тих пір, поки корінь не буде достатньо добре апроксимований.

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

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

Аналіз

А що початкові кінці проміжку a₀ і b₀ обрані так, що f (a₀) і f (b₀) мають протилежні знаки, на кожному кроці одна з кінцевих точок буде наближатися до кореня f . Якщо друга похідна f має на проміжку постійний знак (тобто немає точки перегину), тоді одна кінцева точка (та, де f також має той самий знак) залишатиметься фіксованою для всіх наступних ітерацій, тоді як інша кінцева точка оновлюватиметься. Як наслідок, на відміну від методу поділу навпіл, відстань між дужками не прагне до нуля (якщо тільки нуль не знаходиться в точці перегину навколо якого sign(f ) = −sign(f ") ). Як наслідок, лінійна апроксимація f (x), який використовується для вибору хибної позиції, не покращується настільки швидко, наскільки це можливо.

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

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

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

Для функцій з розривами можна очікувати, що цей метод знайде лише точку, де функція змінює знак (наприклад, при x = 0 для 1/x або знакової функції ). На додаток до зміни знаку, також можливо, щоб метод збігався до точки, де границя функції рівна нулю, навіть якщо функція не визначена (або має інше значення) у цій точці (наприклад, при x = 0 для функція, задана f (x) = abs(x) − x² коли x ≠ 0 і через f (0) = 5, починаючи з інтервалу [-0,5, 3,0]). Математично це можливо, щоб у функції з розривами метод не збігся до нульової границі або зміни знаку, але це не завдає клопоту на практиці, бо знадобиться нескінченна послідовність збігів, щоб обидві кінцеві точки застрягти і не збіглись до розривів, в яких знак не змінюється, наприклад при x = ±1 в

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

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