У математиці метод хибного положення це дуже давній метод розв’язання рівняння з одним невідомим; цей метод у зміненому вигляді використовується досі. По-простому, це метод проб і помилок із використанням («хибних») припущень для значень змінної та подальшого підправлення тестового значення відповідно до отриманого результату. Це іноді також називають «вгадай і перевір». Версії методу передують появі алгебри та використанню рівнянь.
Як приклад розглянемо задачу 26 у папірусі Рейнда, в якій треба знайти розв'язок (тут поданого в сучасному записі) рівняння x + x/4 = 15. Розв'язок знаходимо виходячи з хибного положення. Спочатку припускаємо, що x = 4, щоб отримати ліворуч 4 + 4/4 = 5. Це припущення хороший вибір, бо воно створює ціле число. Однак 4 це не розв'язок заданого рівняння, бо воно дає значення, яке втричі замале. Щоб надолужити нестачу, помножимо x (наразі встановлений у 4) на 3 і знову підставимо, щоб отримати 12 + 12/4 = 15, переконавшись, що рішення це x = 12.
У сучасних версіях методики ми використовуємо систематичні способи вибору нових пробних значень і переймаємось питаннями про те, можна отримати наближення до розв'язку чи ні, і якщо можна, то як швидко можна знайти наближення.
Два історичні типи
Історично можна виділити два основних типи методу хибного положення: просте хибне положення та подвійне хибне положення.
Подвійне хибне положення спрямоване на розв'язання складніших задач, які алгебрично можна записати у вигляді: визначити x так, що
якщо a і b відомі. Метод починається з використання пробного вхідного значення x′ і знаходження відповідного вихідного значення b′ шляхом множення: ax′ = b′. Потім правильну відповідь знаходять шляхом пропорційного підправляння, x = b/ b′ x′
Просте хибне положення спрямоване на розв'язання задач, що стосуються прямої пропорції. Такі задачі можна записати алгебрично у вигляді: визначити x таке, що
якщо відомо, що
Подвійне помилкове положення математично рівнозначне лінійній інтерполяції. Використовуючи двійку пробних входів і відповідну двійку виходів, вислід цього алгоритму, заданий як
можна запам'ятати й виконувати.
Для афінної лінійної функції,
подвійне хибне положення забезпечує точне рішення, тоді як для нелінійної функції f воно забезпечує наближення, яке можна послідовно покращувати ітеративним шляхом.
Числовий аналіз
Метод хибного положення надає точний розв'язок для лінійних функцій, але більш прямі алгебричні методи витіснили його використання для цих функцій. Однак у чисельному аналізі подвійне хибне положення стало алгоритмом пошуку коренів, який використовується в ітеративних методах чисельної апроксимації.
Багато рівнянь, включаючи більшість складніших, можна розв’язати лише за допомогою ітераційної чисельної апроксимації. Це метод проб і помилок, під час якого пробуються різні значення невідомої величини. Таким методом проб і помилок можна керувати обчислюючи на кожному кроці процедури нову оцінку для розв'язку. Є багато способів отримати розрахункову оцінку, і цей метод надає один із них.
У заданому рівнянні, перемістіть усі його члени в одну сторону, щоб воно мало вигляд f (x) = 0, де f це деяка функція невідомої змінної x. Значення c, яке задовольняє це рівняння, тобто f (c) = 0, називається коренем або нулем функції f і це розв'язок вихідного рівняння. Якщо f — неперервна функція і існують дві точки a0 і b0 такі, що f (a0) і f (b0) протилежних знаків, то за теоремою про проміжне значення функція f має корінь на проміжку (a0, b0).
Існує багато алгоритмів знаходження кореня, які можна використовувати для отримання наближених значень такого кореня. Один із найпоширеніших це метод Ньютона, але він може не знайти корінь за певних обставин і може бути обчислювально дорогим, бо вимагає обчислення похідної функції. Потрібні інші методи, і один загальний клас методів – це методи двоточкового дужкування. Ці методи просуваються створюючи послідовність все менших проміжків [ak, bk] на k -му кроці, так що (ak, bk) містить корінь f.
Методи двоточкового дужкування
Ці методи починаються з двох значень x, спочатку знайдених методом проб і помилок, при яких f (x) має протилежні знаки. Згідно з припущенням безперервності, корінь f гарантовано лежить між цими двома значеннями, тобто ці значення «закривають» корінь. Потім вибирається точка, що лежить між цими двома значеннями, і використовується для створення меншого проміжку, який все ще бере в дужки корінь. Якщо вибрана точка c, то маємо менший інтервал, який пролягає від c до кінцевої точки, де f (x) має знак, протилежний знаку f (c). У малоймовірному випадку, коли f (c) = 0, корінь знайдено, і алгоритм зупиняється. В іншому випадку процедура повторюється так часто, як необхідно, щоб отримати наближення до кореня з будь-якою бажаною точністю.
Точку, обрану в будь-якому поточному інтервалі, можна розглядати як оцінку рішення. Різні варіанти цього методу передбачають різні способи обчислення цієї оцінки рішення.
Збереження дужок і забезпечення того, що оцінки рішення лежать всередині інтервалів дужок, гарантує, що оцінки рішення будуть збігатися до розв’язку, ця гарантія недоступна з іншими методами пошуку кореня, такими як метод Ньютона або метод січної.
Це гарантує, що ck лежить між ak і bk, тим самим гарантуючи збіжність до рішення.
А що довжина проміжку дужкування зменшується вдвічі на кожному кроці, похибка методу поділу навпіл зменшується в середньому вдвічі з кожною ітерацією. Таким чином, кожні 3 ітерації метод отримує приблизно коефіцієнт 2 3, тобто приблизно десятковий знак, у точності.
Метод хибного положення.
Швидкість збіжності методу поділу навпіл можна було б покращити за допомогою іншого оцінювання розв'язку.
Метод хибного положення обчислює нову оцінку розв’язку як точку перетину x відрізка, що з’єднує кінцеві точки функції на поточному інтервалі дужок. По суті, корінь апроксимується шляхом заміни фактичної функції відрізком лінії на проміжку дужкування, а потім використанням класичної формули подвійного хибного положення на цьому відрізку лінії.
Точніше, припустімо, що на k-й ітерації проміжок дужкування це (ak, bk). Збудуємо пряму через точки (ak, f (ak)) і (bk, f (bk)), як показано на рисунку. Ця пряма це січна або хорда графіка функції f. У формі з коефіцієнтом нахилу її рівняння задається як
Тепер виберемо ck як точку перетину цієї лінії з віссю x, тобто значення x, для якого y = 0, і підставимо ці значення, щоб отримати
Розв'язування цього рівняння для c k дає:
Ця остання симетрична форма має обчислювальну перевагу:
З наближенням до розв’язку ak і bk будуть дуже близькими одне до одного і майже завжди з однаковим знаком. При такому відніманні можна втратити значущі розряди. А що f (bk) і f (ak) завжди мають протилежний знак, «віднімання» в чисельнику вдосконаленої формули фактично є додаванням (як і віднімання в знаменнику).
На ітерації з номером k число ck обчислюється, як зазначено вище, а потім, якщо f (ak) і f (ck) мають однаковий знак, встановлюємо ak + 1 = ck і bk + 1 = bk, інакше встановлюємо ak + 1 = ak і bk + 1 = ck. Цей процес повторюється до тих пір, поки корінь не буде достатньо добре апроксимований.
Наведена вище формула також використовується в методі хорд, але метод хорд завжди зберігає останні дві обчислені точки, тому, хоча він трохи швидший, він не зберігає дужкування і може не збігатися.
Той факт, що метод хибного положення завжди збігається має версії, які добре уникають сповільнення, робить його добрим вибором, коли потрібна швидкість. Однак швидкість його збіжності може бути нижчою, ніж у методу бісекції.
Аналіз
А що початкові кінці проміжку a0 і b0 обрані так, що f (a0) і f (b0) мають протилежні знаки, на кожному кроці одна з кінцевих точок буде наближатися до кореня f. Якщо друга похідна f має на проміжку постійний знак (тобто немає точки перегину), тоді одна кінцева точка (та, де f також має той самий знак) залишатиметься фіксованою для всіх наступних ітерацій, тоді як інша кінцева точка оновлюватиметься. Як наслідок, на відміну від методу поділу навпіл, відстань між дужками не прагне до нуля (якщо тільки нуль не знаходиться в точці перегину навколо якого sign(f ) = −sign(f ")). Як наслідок, лінійна апроксимація f (x), який використовується для вибору хибної позиції, не покращується настільки швидко, наскільки це можливо.
Одним із прикладів цього явища є функція
на початковому проміжку [− 1,1]. Лівий кінець, −1, ніколи не замінюється (він не змінюється спочатку та після перших трьох ітерацій, f " від'ємна на інтервалі), тому ширина проміжку ніколи не опускається нижче 1. Отже, права кінцева точка наближається до 0 з лінійною швидкістю (кількість точних цифр зростає лінійно, зі швидкістю збіжності 2/3).
Для функцій з розривами можна очікувати, що цей метод знайде лише точку, де функція змінює знак (наприклад, при x = 0 для або знакової функції). На додаток до зміни знаку, також можливо, щоб метод збігався до точки, де границя функції рівна нулю, навіть якщо функція не визначена (або має інше значення) у цій точці (наприклад, при x = 0 для функції, задана f (x) = abs(x) − x2 коли x ≠ 0 і через f (0) = 5, починаючи з інтервалу [-0,5, 3,0]). Математично це можливо, щоб у функції з розривами метод не збігся до нульової границі або зміни знаку, але це не завдає клопоту на практиці, бо знадобиться нескінченна послідовність збігів, щоб обидві кінцеві точки застрягти й не збіглись до розривів, в яких знак не змінюється, наприклад при x = ±1 в
Метод поділу навпіл дозволяє уникнути цієї гіпотетичної проблеми збіжності.
Примітки
- Katz, Victor J. (1998), A History of Mathematics (вид. 2nd), Addison Wesley Longman, с. 15, ISBN
- Smith, D. E. (1958) [1925], History of Mathematics, т. II, Dover, с. 437—441, ISBN
- Conte, S.D.; Boor, Carl de (1965). Elementary Numerical Analysis: an algorithmic approach (вид. 2nd). McGraw-Hill. с. 40. OCLC 1088854304.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici metod hibnogo polozhennya ce duzhe davnij metod rozv yazannya rivnyannya z odnim nevidomim cej metod u zminenomu viglyadi vikoristovuyetsya dosi Po prostomu ce metod prob i pomilok iz vikoristannyam hibnih pripushen dlya znachen zminnoyi ta podalshogo pidpravlennya testovogo znachennya vidpovidno do otrimanogo rezultatu Ce inodi takozh nazivayut vgadaj i perevir Versiyi metodu pereduyut poyavi algebri ta vikoristannyu rivnyan Yak priklad rozglyanemo zadachu 26 u papirusi Rejnda v yakij treba znajti rozv yazok tut podanogo v suchasnomu zapisi rivnyannya x x 4 15 Rozv yazok znahodimo vihodyachi z hibnogo polozhennya Spochatku pripuskayemo sho x 4 shob otrimati livoruch 4 4 4 5 Ce pripushennya horoshij vibir bo vono stvoryuye cile chislo Odnak 4 ce ne rozv yazok zadanogo rivnyannya bo vono daye znachennya yake vtrichi zamale Shob nadoluzhiti nestachu pomnozhimo x narazi vstanovlenij u 4 na 3 i znovu pidstavimo shob otrimati 12 12 4 15 perekonavshis sho rishennya ce x 12 U suchasnih versiyah metodiki mi vikoristovuyemo sistematichni sposobi viboru novih probnih znachen i perejmayemos pitannyami pro te mozhna otrimati nablizhennya do rozv yazku chi ni i yaksho mozhna to yak shvidko mozhna znajti nablizhennya Dva istorichni tipiIstorichno mozhna vidiliti dva osnovnih tipi metodu hibnogo polozhennya proste hibne polozhennya ta podvijne hibne polozhennya Podvijne hibne polozhennya spryamovane na rozv yazannya skladnishih zadach yaki algebrichno mozhna zapisati u viglyadi viznachiti x tak sho a x b displaystyle ax b yaksho a i b vidomi Metod pochinayetsya z vikoristannya probnogo vhidnogo znachennya x i znahodzhennya vidpovidnogo vihidnogo znachennya b shlyahom mnozhennya ax b Potim pravilnu vidpovid znahodyat shlyahom proporcijnogo pidpravlyannya x b b x Proste hibne polozhennya spryamovane na rozv yazannya zadach sho stosuyutsya pryamoyi proporciyi Taki zadachi mozhna zapisati algebrichno u viglyadi viznachiti x take sho f x a x c 0 displaystyle f x ax c 0 yaksho vidomo sho f x 1 b 1 f x 2 b 2 displaystyle f x 1 b 1 qquad f x 2 b 2 Podvijne pomilkove polozhennya matematichno rivnoznachne linijnij interpolyaciyi Vikoristovuyuchi dvijku probnih vhodiv i vidpovidnu dvijku vihodiv vislid cogo algoritmu zadanij yak x b 1 x 2 b 2 x 1 b 1 b 2 displaystyle x frac b 1 x 2 b 2 x 1 b 1 b 2 mozhna zapam yatati j vikonuvati Dlya afinnoyi linijnoyi funkciyi f x a x c displaystyle f x ax c podvijne hibne polozhennya zabezpechuye tochne rishennya todi yak dlya nelinijnoyi funkciyi f vono zabezpechuye nablizhennya yake mozhna poslidovno pokrashuvati iterativnim shlyahom Chislovij analizMetod hibnogo polozhennya nadaye tochnij rozv yazok dlya linijnih funkcij ale bilsh pryami algebrichni metodi vitisnili jogo vikoristannya dlya cih funkcij Odnak u chiselnomu analizi podvijne hibne polozhennya stalo algoritmom poshuku koreniv yakij vikoristovuyetsya v iterativnih metodah chiselnoyi aproksimaciyi Bagato rivnyan vklyuchayuchi bilshist skladnishih mozhna rozv yazati lishe za dopomogoyu iteracijnoyi chiselnoyi aproksimaciyi Ce metod prob i pomilok pid chas yakogo probuyutsya rizni znachennya nevidomoyi velichini Takim metodom prob i pomilok mozhna keruvati obchislyuyuchi na kozhnomu kroci proceduri novu ocinku dlya rozv yazku Ye bagato sposobiv otrimati rozrahunkovu ocinku i cej metod nadaye odin iz nih U zadanomu rivnyanni peremistit usi jogo chleni v odnu storonu shob vono malo viglyad f x 0 de f ce deyaka funkciya nevidomoyi zminnoyi x Znachennya c yake zadovolnyaye ce rivnyannya tobto f c 0 nazivayetsya korenem abo nulem funkciyi f i ce rozv yazok vihidnogo rivnyannya Yaksho f neperervna funkciya i isnuyut dvi tochki a0 i b0 taki sho f a0 i f b0 protilezhnih znakiv to za teoremoyu pro promizhne znachennya funkciya f maye korin na promizhku a0 b0 Isnuye bagato algoritmiv znahodzhennya korenya yaki mozhna vikoristovuvati dlya otrimannya nablizhenih znachen takogo korenya Odin iz najposhirenishih ce metod Nyutona ale vin mozhe ne znajti korin za pevnih obstavin i mozhe buti obchislyuvalno dorogim bo vimagaye obchislennya pohidnoyi funkciyi Potribni inshi metodi i odin zagalnij klas metodiv ce metodi dvotochkovogo duzhkuvannya Ci metodi prosuvayutsya stvoryuyuchi poslidovnist vse menshih promizhkiv ak bk na k mu kroci tak sho ak bk mistit korin f Metodi dvotochkovogo duzhkuvannya Ci metodi pochinayutsya z dvoh znachen x spochatku znajdenih metodom prob i pomilok pri yakih f x maye protilezhni znaki Zgidno z pripushennyam bezperervnosti korin f garantovano lezhit mizh cimi dvoma znachennyami tobto ci znachennya zakrivayut korin Potim vibirayetsya tochka sho lezhit mizh cimi dvoma znachennyami i vikoristovuyetsya dlya stvorennya menshogo promizhku yakij vse she bere v duzhki korin Yaksho vibrana tochka c to mayemo menshij interval yakij prolyagaye vid c do kincevoyi tochki de f x maye znak protilezhnij znaku f c U malojmovirnomu vipadku koli f c 0 korin znajdeno i algoritm zupinyayetsya V inshomu vipadku procedura povtoryuyetsya tak chasto yak neobhidno shob otrimati nablizhennya do korenya z bud yakoyu bazhanoyu tochnistyu Tochku obranu v bud yakomu potochnomu intervali mozhna rozglyadati yak ocinku rishennya Rizni varianti cogo metodu peredbachayut rizni sposobi obchislennya ciyeyi ocinki rishennya Zberezhennya duzhok i zabezpechennya togo sho ocinki rishennya lezhat vseredini intervaliv duzhok garantuye sho ocinki rishennya budut zbigatisya do rozv yazku cya garantiya nedostupna z inshimi metodami poshuku korenya takimi yak metod Nyutona abo metod sichnoyi c k a k b k 2 displaystyle c k frac a k b k 2 Ce garantuye sho ck lezhit mizh ak i bk tim samim garantuyuchi zbizhnist do rishennya A sho dovzhina promizhku duzhkuvannya zmenshuyetsya vdvichi na kozhnomu kroci pohibka metodu podilu navpil zmenshuyetsya v serednomu vdvichi z kozhnoyu iteraciyeyu Takim chinom kozhni 3 iteraciyi metod otrimuye priblizno koeficiyent 2 3 tobto priblizno desyatkovij znak u tochnosti Metod hibnogo polozhennya Pershi dvi iteraciyi metodu hibnogo polozhennya Chervona kriva pokazuye funkciyu f a sini liniyi sichni Shvidkist zbizhnosti metodu podilu navpil mozhna bulo b pokrashiti za dopomogoyu inshogo ocinyuvannya rozv yazku Metod hibnogo polozhennya obchislyuye novu ocinku rozv yazku yak tochku peretinu x vidrizka sho z yednuye kincevi tochki funkciyi na potochnomu intervali duzhok Po suti korin aproksimuyetsya shlyahom zamini faktichnoyi funkciyi vidrizkom liniyi na promizhku duzhkuvannya a potim vikoristannyam klasichnoyi formuli podvijnogo hibnogo polozhennya na comu vidrizku liniyi Tochnishe pripustimo sho na k j iteraciyi promizhok duzhkuvannya ce ak bk Zbuduyemo pryamu cherez tochki ak f ak i bk f bk yak pokazano na risunku Cya pryama ce sichna abo horda grafika funkciyi f U formi z koeficiyentom nahilu yiyi rivnyannya zadayetsya yak y f b k f b k f a k b k a k x b k displaystyle y f b k frac f b k f a k b k a k x b k Teper viberemo ck yak tochku peretinu ciyeyi liniyi z vissyu x tobto znachennya x dlya yakogo y 0 i pidstavimo ci znachennya shob otrimati f b k f b k f a k b k a k c k b k 0 displaystyle f b k frac f b k f a k b k a k c k b k 0 Rozv yazuvannya cogo rivnyannya dlya c k daye c k b k f b k b k a k f b k f a k a k f b k b k f a k f b k f a k displaystyle 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 Cya ostannya simetrichna forma maye obchislyuvalnu perevagu Z nablizhennyam do rozv yazku ak i bk budut duzhe blizkimi odne do odnogo i majzhe zavzhdi z odnakovim znakom Pri takomu vidnimanni mozhna vtratiti znachushi rozryadi A sho f bk i f ak zavzhdi mayut protilezhnij znak vidnimannya v chiselniku vdoskonalenoyi formuli faktichno ye dodavannyam yak i vidnimannya v znamenniku Na iteraciyi z nomerom k chislo ck obchislyuyetsya yak zaznacheno vishe a potim yaksho f ak i f ck mayut odnakovij znak vstanovlyuyemo ak 1 ck i bk 1 bk inakshe vstanovlyuyemo ak 1 ak i bk 1 ck Cej proces povtoryuyetsya do tih pir poki korin ne bude dostatno dobre aproksimovanij Navedena vishe formula takozh vikoristovuyetsya v metodi hord ale metod hord zavzhdi zberigaye ostanni dvi obchisleni tochki tomu hocha vin trohi shvidshij vin ne zberigaye duzhkuvannya i mozhe ne zbigatisya Toj fakt sho metod hibnogo polozhennya zavzhdi zbigayetsya maye versiyi yaki dobre unikayut spovilnennya robit jogo dobrim viborom koli potribna shvidkist Odnak shvidkist jogo zbizhnosti mozhe buti nizhchoyu nizh u metodu bisekciyi AnalizA sho pochatkovi kinci promizhku a0 i b0 obrani tak sho f a0 i f b0 mayut protilezhni znaki na kozhnomu kroci odna z kincevih tochok bude nablizhatisya do korenya f Yaksho druga pohidna f maye na promizhku postijnij znak tobto nemaye tochki pereginu todi odna kinceva tochka ta de f takozh maye toj samij znak zalishatimetsya fiksovanoyu dlya vsih nastupnih iteracij todi yak insha kinceva tochka onovlyuvatimetsya Yak naslidok na vidminu vid metodu podilu navpil vidstan mizh duzhkami ne pragne do nulya yaksho tilki nul ne znahoditsya v tochci pereginu navkolo yakogo sign f sign f Yak naslidok linijna aproksimaciya f x yakij vikoristovuyetsya dlya viboru hibnoyi poziciyi ne pokrashuyetsya nastilki shvidko naskilki ce mozhlivo Odnim iz prikladiv cogo yavisha ye funkciya f x 2 x 3 4 x 2 3 x displaystyle f x 2x 3 4x 2 3x na pochatkovomu promizhku 1 1 Livij kinec 1 nikoli ne zaminyuyetsya vin ne zminyuyetsya spochatku ta pislya pershih troh iteracij f vid yemna na intervali tomu shirina promizhku nikoli ne opuskayetsya nizhche 1 Otzhe prava kinceva tochka nablizhayetsya do 0 z linijnoyu shvidkistyu kilkist tochnih cifr zrostaye linijno zi shvidkistyu zbizhnosti 2 3 Dlya funkcij z rozrivami mozhna ochikuvati sho cej metod znajde lishe tochku de funkciya zminyuye znak napriklad pri x 0 dlya abo znakovoyi funkciyi Na dodatok do zmini znaku takozh mozhlivo shob metod zbigavsya do tochki de granicya funkciyi rivna nulyu navit yaksho funkciya ne viznachena abo maye inshe znachennya u cij tochci napriklad pri x 0 dlya funkciyi zadana f x abs x x2 koli x 0 i cherez f 0 5 pochinayuchi z intervalu 0 5 3 0 Matematichno ce mozhlivo shob u funkciyi z rozrivami metod ne zbigsya do nulovoyi granici abo zmini znaku ale ce ne zavdaye klopotu na praktici bo znadobitsya neskinchenna poslidovnist zbigiv shob obidvi kincevi tochki zastryagti j ne zbiglis do rozriviv v yakih znak ne zminyuyetsya napriklad pri x 1 v f x 1 x 1 2 1 x 1 2 displaystyle f x frac 1 x 1 2 frac 1 x 1 2 Metod podilu navpil dozvolyaye uniknuti ciyeyi gipotetichnoyi problemi zbizhnosti PrimitkiKatz Victor J 1998 A History of Mathematics vid 2nd Addison Wesley Longman s 15 ISBN 978 0 321 01618 8 Smith D E 1958 1925 History of Mathematics t II Dover s 437 441 ISBN 978 0 486 20430 7 Conte S D Boor Carl de 1965 Elementary Numerical Analysis an algorithmic approach vid 2nd McGraw Hill s 40 OCLC 1088854304