Regula fałszywa

W matematyce , regula falsi , metoda fałszywej pozycji lub metoda fałszywej pozycji jest bardzo starą metodą rozwiązywania równania z jedną niewiadomą; ta metoda, w zmodyfikowanej formie, jest nadal w użyciu. Mówiąc prościej, metoda ta jest prób i błędów polegającą na użyciu wartości testowych („fałszywych”) dla zmiennej, a następnie dostosowaniu wartości testowej zgodnie z wynikiem. Czasami jest to również określane jako „zgadnij i sprawdź”. Wersje metody poprzedzają nadejście algebry i użycie równań .

Jako przykład rozważmy problem 26 w papirusie Rhinda , który prosi o rozwiązanie (zapisanego współczesnym zapisem) równania x + x /4 = 15 . Jest to rozwiązane przez fałszywą pozycję. Najpierw zgadnij, że x = 4 , aby otrzymać po lewej stronie 4 + 4/4 = 5 . To przypuszczenie jest dobrym wyborem, ponieważ generuje wartość całkowitą. Jednak 4 nie jest rozwiązaniem pierwotnego równania, ponieważ daje wartość trzykrotnie za małą. Aby to zrekompensować, pomnóż x (obecnie ustawione na 4) przez 3 i podmień ponownie, aby uzyskać 12 + 12/4 = 15 , sprawdzając, czy rozwiązaniem jest x = 12 .

Nowoczesne wersje tej techniki wykorzystują systematyczne sposoby wybierania nowych wartości testowych i dotyczą pytań, czy można uzyskać przybliżenie rozwiązania, a jeśli tak, to jak szybko można znaleźć przybliżenie.

Dwa typy historyczne

Historycznie można wyróżnić dwa podstawowe typy metody fałszywej pozycji, prostą fałszywą pozycję i podwójną fałszywą pozycję .

Prosta fałszywa pozycja ma na celu rozwiązanie problemów dotyczących bezpośredniej proporcji. Takie problemy można zapisać algebraicznie w postaci: wyznacz x takie, że

${\ displaystyle ax = b,}$

jeśli a i b są znane. Metoda rozpoczyna się od użycia testowej wartości wejściowej x ′ i znalezienia odpowiedniej wartości wyjściowej b ′ przez pomnożenie: ax ′ = b ′ . Prawidłową odpowiedź można następnie znaleźć za pomocą regulacji proporcjonalnej, x = b / b ′ x ′ .

Podwójna fałszywa pozycja ma na celu rozwiązanie trudniejszych problemów, które można zapisać algebraicznie w postaci: wyznacz x takie, że

${\ Displaystyle f (x) = topór + c = 0,}$

jeśli wiadomo, że

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

Podwójna fałszywa pozycja jest matematycznie równoważna interpolacji liniowej . Używając pary wejść testowych i odpowiadającej im pary wyjść, wynik tego algorytmu podany przez,

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

byłyby zapamiętywane i wykonywane na pamięć. Rzeczywiście, reguła podana przez Roberta Recorde w jego Ground of Artes (ok. 1542) brzmi:

Gesse w tym worku jako Happe Doth Leade. Przez przypadek do truee możesz kontynuować. I najpierw pracuj nad pytaniem, chociaż nie ma w tym prawdy. Takie kłamstwo jest tak dobrą podstawą, że prawda wkrótce zostanie znaleziona. Od wielu bate do wielu mo, Od do kilku również do niewielu. Z zbyt dużą ilością joyne do niewielu znowu, do niewielu adde do wielu zwykłych. W crossewaies mnożą przeciwne rodzaje, All truee by falsehode for fynde.

Dla afinicznej funkcji liniowej

${\ Displaystyle f (x) = topór + c,}$

podwójna fałszywa pozycja zapewnia dokładne rozwiązanie, podczas gdy dla funkcji nieliniowej f zapewnia przybliżenie , które można sukcesywnie poprawiać przez iterację .

Historia

Prostą technikę fałszywej pozycji można znaleźć na tabliczkach klinowych ze starożytnej matematyki babilońskiej oraz na papirusach ze starożytnej matematyki egipskiej .

Podwójna fałszywa pozycja powstała w późnej starożytności jako algorytm czysto arytmetyczny. W starożytnym chińskim tekście matematycznym zatytułowanym Dziewięć rozdziałów o sztuce matematycznej (九章算術), datowanym na okres od 200 pne do 100 rne, większość rozdziału 7 była poświęcona algorytmowi. Tam procedura została uzasadniona konkretnymi argumentami arytmetycznymi, a następnie twórczo zastosowana do szerokiej gamy problemów fabularnych, w tym do tego, który dotyczy czegoś, co nazwalibyśmy siecznymi liniami na przekroju stożka . Bardziej typowym przykładem jest ten problem „wspólnych zakupów” obejmujący warunek „nadwyżki i deficytu”:

Teraz przedmiot jest kupowany wspólnie; każdy wnosi 8 [monet], nadwyżka to 3; każdy wnosi 7, deficyt wynosi 4. Powiedz: Liczba osób, cena przedmiotu, jaka jest każda? Odpowiedź: 7 osób, cena za sztukę 53.

Między IX a X wiekiem egipski matematyk Abu Kamil napisał zaginiony traktat o stosowaniu podwójnej fałszywej pozycji, znany jako Księga Dwóch Błędów ( Kitāb al-khaṭāʾayn ). Najstarszym zachowanym pismem na temat podwójnej fałszywej pozycji z Bliskiego Wschodu jest pismo Qusta ibn Luqa (X w.), arabskiego matematyka z Baalbek w Libanie . Uzasadnił tę technikę formalnym dowodem geometrycznym w stylu euklidesowym . W tradycji średniowiecznej matematyki muzułmańskiej podwójna fałszywa pozycja była znana jako hisāb al-khaṭāʾayn („rachunek na podstawie dwóch błędów”). Wykorzystywano go przez wieki do rozwiązywania problemów praktycznych, takich jak kwestie handlowe i prawne (podziały majątkowe według zasad dziedziczenia koranicznego ), a także problemy czysto rekreacyjne. Algorytm był często zapamiętywany za pomocą mnemoników , takich jak werset przypisywany Ibn al-Yasamin i diagramy skali równowagi wyjaśnione przez al-Hassara i Ibn al-Banna , wszyscy trzej są matematykami pochodzenia marokańskiego .

Leonardo z Pizy ( Fibonacci ) poświęcił rozdział 13 swojej książki Liber Abaci (1202 r.) Wyjaśnieniu i zademonstrowaniu zastosowań podwójnej fałszywej pozycji, nazywając metodę regulis elchatayn po metodzie al-khaṭāʾayn , której nauczył się ze źródeł arabskich . W 1494 roku Pacioli użył terminu el cataym w swojej książce Summa de arithmetica , prawdopodobnie biorąc ten termin od Fibonacciego. Inni pisarze europejscy podążali za Paciolim i czasami dostarczali tłumaczenie na łacinę lub język narodowy. Na przykład, Tartaglia tłumaczy zlatynizowaną wersję terminu Pacioli na rodzime „fałszywe pozycje” w 1556 r. Termin Pacioli prawie zniknął w XVI-wiecznych dziełach europejskich, a technika ta nosiła różne nazwy, takie jak „Reguła fałszu”, „Reguła pozycji” i „ Zasada fałszywego stanowiska”. Regula Falsi pojawia się jako zlatynizowana wersja Rule of False już w 1690 roku.

Kilku XVI-wiecznych autorów europejskich poczuło potrzebę przeprosin za nazwę metody w nauce, która szuka prawdy. Na przykład w 1568 roku Humphrey Baker mówi:

Reguła fałszu jest tak nazwana nie dlatego, że uczy kogokolwiek oszustwa lub fałszu, ale dlatego, że na podstawie ustalonych liczb zebranych we wszystkich przygodach uczy znaleźć prawdziwą liczbę, która jest odkryta, i to ze wszystkich wulgarnych Reguł, które są w praktyce ) jest ^najwyższą doskonałością.

Analiza numeryczna

Metoda fałszywej pozycji zapewnia dokładne rozwiązanie dla funkcji liniowych, ale bardziej bezpośrednie techniki algebraiczne wyparły jej użycie dla tych funkcji. Jednak w analizie numerycznej podwójna fałszywa pozycja stała się algorytmem wyszukiwania pierwiastków używanym w iteracyjnych technikach aproksymacji numerycznej.

Wiele równań, w tym większość tych bardziej skomplikowanych, można rozwiązać jedynie za pomocą iteracyjnego przybliżenia numerycznego. Polega to na próbach i błędach, w których wypróbowywane są różne wartości nieznanej wielkości. Metodą prób i błędów można kierować się, obliczając na każdym etapie procedury nowe oszacowanie rozwiązania. Istnieje wiele sposobów na uzyskanie obliczonego oszacowania, a regula falsi zapewnia jeden z nich.

Mając dane równanie, przenieś wszystkie jego wyrazy na jedną stronę, tak aby miało ono postać f ( x ) = 0 , gdzie f jest pewną funkcją nieznanej zmiennej x . Wartość c , która spełnia to równanie, czyli f ( c ) = 0 , nazywana jest pierwiastkiem lub zerem funkcji f i jest rozwiązaniem pierwotnego równania. Jeśli f jest funkcją ciągłą i istnieją dwa punkty a ₀ i b ₀ takie, że ₀ f ( a ) i ₀ f ( b ) mają przeciwne znaki, to zgodnie z twierdzeniem o wartości pośredniej funkcja f ma pierwiastek z przedziału ₀₀ ( a , b ) .

Istnieje wiele algorytmów znajdowania pierwiastków , których można użyć do uzyskania przybliżeń takiego pierwiastka. Jedną z najpowszechniejszych jest metoda Newtona , ale w pewnych okolicznościach może się nie udać znaleźć pierwiastka i może być kosztowna obliczeniowo, ponieważ wymaga obliczenia pochodnej funkcji . Potrzebne są inne metody, a jedną ogólną klasą metod są metody z nawiasami dwupunktowymi . Metody te polegają na utworzeniu sekwencji zmniejszających się przedziałów [ a _k , b _k ] w punkcie k -ty krok taki, że ( a _k , b _k ) zawiera pierwiastek z f .

Metody nawiasów dwupunktowych

Metody te rozpoczynają się od dwóch wartości x , początkowo znalezionych metodą prób i błędów, przy których f ( x ) ma przeciwne znaki. Przy założeniu ciągłości pierwiastek f z pewnością leży między tymi dwiema wartościami, to znaczy, że te wartości „ują w nawiasy” pierwiastek. Następnie wybierany jest punkt znajdujący się dokładnie pomiędzy tymi dwiema wartościami i używany do utworzenia mniejszego przedziału, który nadal obejmuje pierwiastek. Jeśli wybranym punktem jest c , to mniejszy przedział biegnie od c do punktu końcowego, gdzie f ( x ) ma znak przeciwny do znaku f ( c ) . W nieprawdopodobnym przypadku, gdy f ( c ) = 0 , znaleziono pierwiastek i algorytm się zatrzymuje. W przeciwnym razie procedurę powtarza się tak często, jak to konieczne, aby uzyskać przybliżenie do pierwiastka z dowolną pożądaną dokładnością.

Punkt wybrany w dowolnym bieżącym przedziale można traktować jako oszacowanie rozwiązania. Różne odmiany tej metody obejmują różne sposoby obliczania tego oszacowania rozwiązania.

Zachowanie nawiasów i upewnienie się, że oszacowania rozwiązań leżą wewnątrz przedziałów nawiasów, gwarantuje, że oszacowania rozwiązań będą zbieżne w kierunku rozwiązania, co jest gwarancją niedostępną w przypadku innych metod wyszukiwania pierwiastków, takich jak metoda Newtona lub metoda siecznych .

Najprostsza odmiana, zwana metodą bisekcji , oblicza oszacowanie rozwiązania jako punkt środkowy przedziału nawiasów. Oznacza to, że jeśli w kroku k bieżący przedział nawiasów wynosi [ a _k , b _k ] , to nowa estymata rozwiązania c _k jest uzyskiwana przez:

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

Zapewnia to, że c _k jest między a _k a b _k , gwarantując w ten sposób zbieżność w kierunku rozwiązania.

Ponieważ długość przedziału nawiasów zmniejsza się o połowę na każdym kroku, błąd metody bisekcji zmniejsza się średnio o połowę w każdej iteracji. Stąd, co 3 iteracje, metoda zyskuje w przybliżeniu współczynnik 2 ³ , tj. mniej więcej jedno miejsce po przecinku, w dokładności.

regula falsi (fałszywa pozycja).

Pierwsze dwie iteracje metody fałszywej pozycji. Czerwona krzywa przedstawia funkcję f , a niebieskie linie to sieczne.

Szybkość zbieżności metody bisekcji można ewentualnie poprawić, stosując inne oszacowanie rozwiązania.

Metoda regula falsi oblicza nowe oszacowanie rozwiązania jako punkt przecięcia z osią x odcinka linii łączącego punkty końcowe funkcji w bieżącym przedziale nawiasów. Zasadniczo pierwiastek jest przybliżany przez zastąpienie rzeczywistej funkcji odcinkiem linii w przedziale nawiasów, a następnie użycie klasycznej formuły podwójnej fałszywej pozycji na tym odcinku linii.

Dokładniej, załóżmy, że w k -tej iteracji interwałem nawiasów jest ( a _k , b _k ) . Skonstruuj prostą przechodzącą przez punkty ( a _k , f ( a _k )) i ( b _k , f ( b _k )) , jak pokazano na rysunku. Ta linia jest sieczną lub cięciwą wykresu funkcji f . W postaci nachylenia punktowego , jego równanie jest dane przez

${\ Displaystyle yf (b_ {k}) = {\ Frac {f (b_ {k}) -f (a_ {k})} {b_ {k} -a_ {k}}} (x-b_ {k} ).}$

Teraz wybierz c _k jako punkt przecięcia z osią x tej prostej, to znaczy wartość x , dla której y = 0 , i zastąp te wartości, aby otrzymać

${\ Displaystyle f (b_ {k}) + {\ Frac {f (b_ {k})-f(a_{k})}{b_{k}-a_{k}}}(c_{k}-b_{k})=0.}$

Rozwiązanie tego równania dla c _k daje:

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

Ta ostatnia symetryczna postać ma przewagę obliczeniową:

W miarę zbliżania się do rozwiązania a _k i b _k będą bardzo blisko siebie i prawie zawsze będą miały ten sam znak. Takie odejmowanie może spowodować utratę cyfr znaczących. Ponieważ f ( b _k ) i f ( a _k ) mają zawsze przeciwny znak, „odejmowanie” w liczniku ulepszonej formuły jest faktycznie dodawaniem (podobnie jak odejmowanie w mianowniku).

Przy numerze iteracji k liczba c _k jest obliczana jak powyżej, a następnie, jeśli f ( a _k ) i f ( c _k ) mają ten sam znak, ustaw a _{k + 1} = c _k i b _{k + 1} = b _k , w przeciwnym razie ustaw a _{k + 1} = a _k i b _{k + 1} = c _k . Proces ten jest powtarzany, aż pierwiastek zostanie wystarczająco przybliżony.

Powyższy wzór jest również używany w metodzie siecznych, ale metoda sieczna zawsze zachowuje dwa ostatnie obliczone punkty, więc chociaż jest nieco szybsza, nie zachowuje nawiasów i może nie być zbieżna.

Fakt, że reguła falsi zawsze jest zbieżna i istnieją wersje, które dobrze radzą sobie z unikaniem spowolnień, sprawia, że ​​jest to dobry wybór, gdy potrzebna jest szybkość. Jednak jego szybkość zbieżności może spaść poniżej metody bisekcji.

Analiza

Ponieważ początkowe punkty końcowe a ₀ i b ₀ są tak dobrane, że ₀ f ( a ) i ₀ f ( b ) mają przeciwne znaki, na każdym kroku jeden z punktów końcowych będzie się zbliżał do pierwiastka z f . Jeśli druga pochodna f ma stały znak (więc nie ma punktu przegięcia ) w przedziale, to jeden punkt końcowy (ten, w którym f ma również ten sam znak) pozostanie niezmieniony dla wszystkich kolejnych iteracji, podczas gdy zbieżny punkt końcowy zostanie zaktualizowany. W rezultacie, w przeciwieństwie do metody bisekcji , szerokość nawiasu nie dąży do zera (chyba że zero znajduje się w punkcie przegięcia, wokół którego znak ( f ) = -sign ( f ") ). W konsekwencji przybliżenie liniowe do f ( x ) , który jest używany do wybierania fałszywej pozycji, nie poprawia się tak szybko, jak to możliwe.

Jednym z przykładów tego zjawiska jest funkcja

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

w nawiasie początkowym [-1,1]. Lewy koniec, −1, nigdy nie jest zastępowany (nie zmienia się na początku, a po pierwszych trzech iteracjach f ” jest ujemny w przedziale), a zatem szerokość nawiasu nigdy nie spada poniżej 1. Stąd prawy punkt końcowy zbliża się 0 w tempie liniowym (liczba dokładnych cyfr rośnie liniowo, z szybkością konwergencji 2/3).

W przypadku funkcji nieciągłych można oczekiwać, że ta metoda znajdzie tylko punkt, w którym funkcja zmienia znak (na przykład przy x = 0 dla 1/ x lub funkcji znaku ). Oprócz zmian znaku możliwe jest również zbieżność metody do punktu, w którym granica funkcji wynosi zero, nawet jeśli funkcja jest niezdefiniowana (lub ma inną wartość) w tym punkcie (na przykład przy x = = 0 for the function given by f (x) = abs(x) − x² when x ≠ 0 i przez f (0) = 5 , zaczynając od przedziału [-0,5, 3,0]). Jest matematycznie możliwe, że w przypadku funkcji nieciągłych metoda nie doprowadzi do zbieżności do granicy zera lub zmiany znaku, ale w praktyce nie stanowi to problemu, ponieważ wymagałoby to nieskończonej sekwencji zbiegów okoliczności, aby oba punkty końcowe utknęły w zbieżności do nieciągłości, gdzie znak nie zmienia się, na przykład przy x = ±1 cal

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

Metoda bisekcji pozwala uniknąć tego hipotetycznego problemu zbieżności.

Ulepszenia w regula falsi

Chociaż reguła falsi zawsze jest zbieżna, zwykle znacznie szybciej niż bisekcja, istnieją sytuacje, które mogą spowolnić jej zbieżność - czasami w stopniu zaporowym. Ten problem nie jest unikalny dla regula falsi : poza bisekcją, wszystkie metody rozwiązywania równań numerycznych mogą mieć problem z powolną zbieżnością lub brakiem zbieżności w pewnych warunkach. Czasami metoda Newtona i metoda sieczna rozchodzą się zamiast zbiegać - i często robią to w tych samych warunkach, które spowalniają zbieżność regula falsi .

Ale chociaż regula falsi jest jedną z najlepszych metod i nawet w oryginalnej, nieulepszonej wersji często byłaby najlepszym wyborem; na przykład, gdy funkcja Newtona nie jest używana, ponieważ ocena pochodnej jest zbyt czasochłonna lub gdy metody Newtona i kolejne podstawienia nie są zbieżne.

Regula falsi jest łatwy do wykrycia: ten sam punkt końcowy zostaje zachowany dwa razy z rzędu. Problem można łatwo rozwiązać, wybierając zamiast tego zmodyfikowaną fałszywą pozycję, wybraną w celu uniknięcia spowolnień spowodowanych tymi stosunkowo nietypowymi niekorzystnymi sytuacjami. Zaproponowano szereg takich ulepszeń do regula falsi ; dwa z nich, algorytm Illinois i algorytm Andersona-Björka, opisano poniżej.

Algorytm Illinois

Algorytm Illinois zmniejsza o połowę wartość y zachowanego punktu końcowego w następnym obliczeniu oszacowania, gdy nowa wartość y (to znaczy f ( c _k )) ma ten sam znak co poprzedni ( f ( c _{k - 1} ) ), co oznacza, że ​​punkt końcowy poprzedniego kroku zostanie zachowany. Stąd:

${\ Displaystyle c_ {k} = {\ Frac {{\ Frac {1 }{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f( a_{k})}}}$

Lub

${\ Displaystyle c_ {k} = {\ Frac {f (b_ { k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f (a_{k})}},}$

zmniejszenie wagi jednej z wartości punktów końcowych, aby wymusić wystąpienie następnego c _k po tej stronie funkcji. Zastosowany powyżej współczynnik ½ wygląda arbitralnie, ale gwarantuje superliniową zbieżność (asymptotycznie algorytm wykona dwa regularne kroki po każdym zmodyfikowanym kroku i ma rząd zbieżności 1,442). Istnieją inne sposoby wyboru przeskalowania, które dają jeszcze lepsze współczynniki konwergencji superliniowej.

Powyższe dostosowanie do regula falsi jest nazywane przez niektórych uczonych algorytmem Illinois . Ford (1995) podsumowuje i analizuje ten i inne podobne superliniowe warianty metody fałszywej pozycji.

Algorytm Andersona-Björcka

Załóżmy , że w k - tej iteracji przedziałem nawiasowym jest [ a _k , b _k ] i że wartość funkcyjna nowej obliczonej estymaty c _k ma taki sam znak jak f ( b _k ) . W tym przypadku nowy odstęp w nawiasach [ a _{k + 1} , b _{k + 1} ] = [ a _k , c _k ] a lewy punkt końcowy został zachowany. (Jak dotąd jest to to samo, co zwykła Regula Falsi i algorytm Illinois).

Ale podczas gdy algorytm Illinois pomnożyłby f ( a _k ) przez 1 / 2 , algorytm Andersona-Björcka mnoży to przez m , gdzie m ma jedną z dwóch następujących wartości:

$${\ Displaystyle {\ rozpocząć {wyrównane} m '& = 1- {\ Frac {f (c_ {k})}} {f (b_ {k})}}, \\ m & = {\ rozpocząć {przypadki} m' &{\text{if }}m'>0,\\{\frac {1}{2}}&{\text{inaczej.}}\end{przypadki}}\end{wyrównane}}}$$

W przypadku prostych pierwiastków Anderson-Björck sprawdza się w praktyce bardzo dobrze.

Metoda ITP

Główny artykuł: metoda ITP

$1 + \ phi \ prawo)}$${\ Displaystyle \ kappa _ {1} \ w (0, \ infty), \ kappa _ {2} \ w \ lewo [1$ , , ${\ Displaystyle n_ {1/2} \ równoważnik \ lceil (b_ {0} -a_ {0}) / 2 \epsilon \rceil }$ i ${\ Displaystyle n_ {0} \ w [0, \ infty)}$ gdzie ${\ Displaystyle \ phi}$ to złoty podział ${\ Displaystyle {\ tfrac {1} {2} } (1 + {\ sqrt {5}})}$ , w każdej iteracji ${\ Displaystyle j = 0,1,2...}$ metoda ITP oblicza punkt ${\ displaystyle x_{\text{ITP}}}$ wykonując trzy kroki:

1. regulara $[$${\ Displaystyle x_ {f} \ równoważnik {\ Frac {bf (a) -af (b)} {f (a)$ falsi ;
2. [Krok obcięcia] Zakłócić estymator w kierunku środka: ${\ Displaystyle x_ {t} \ równoważnik x_ {f} + \ sigma \ delta}$ gdzie ${\ Displaystyle \ sigma \ równoważnik {\ tekst {znak}} (x_ {1/2} -x_ {f})}$ i ${\ Displaystyle \ delta \ równoważnik \ min \ {\ kappa _ {1} | ba | ^ {\ kappa _ {2}}, | x_ {1/2} -x_ {f} |\}}$ ;
3. ${\ Displaystyle x _ {\ tekst {ITP}} \ równoważnik x_ {1/2} - \ sigma \ rho _ {k$ Krok projekcji] Rzutuj estymator na przedział minmax: gdzie ${\ Displaystyle \ rho _ {k} \ równoważnik \ min \ lewo \ {\ epsilon 2 ^ {n_ {1/2} + n_ {0} -j} - {\ Frac {ba} {2}},| x_{t}-x_{1/2}|\prawo\}}$ .

wartość funkcji ${\ Displaystyle f (x _ {\ tekst {ITP}})}$ tym punkcie, a następnie przedział jest redukowany do pierwiastka w nawiasie, zachowując podprzedział z wartościami funkcji fa przeciwnego znaku na każdym końcu. Ta trzyetapowa procedura gwarantuje, że oszacowanie, jak również superliniowa zbieżność metody siecznych, pozwala cieszyć się właściwościami minmax metody bisekcji. Zaobserwowano, że przewyższa zarówno metody oparte na bisekcji, jak i interpolacji w przypadku funkcji gładkich i niegładkich.

Względy praktyczne

Przy rozwiązywaniu jednego równania lub tylko kilku za pomocą komputera metoda bisekcji jest odpowiednim wyborem. Chociaż bisekcja nie jest tak szybka jak inne metody — gdy są najlepsze i nie mają problemu — bisekcja gwarantuje jednak zbieżność z użyteczną szybkością, z grubsza zmniejszając błąd o połowę przy każdej iteracji — zyskując mniej więcej ułamek dziesiętny miejsce dokładności co 3 iteracje.

W przypadku obliczeń ręcznych za pomocą kalkulatora zwykle chce się używać szybszych metod, które zwykle, ale nie zawsze, zbiegają się szybciej niż bisekcja. Ale komputer, nawet stosując bisekcję, rozwiąże równanie z pożądaną dokładnością tak szybko, że nie ma potrzeby oszczędzania czasu przy użyciu mniej niezawodnej metody — a każda metoda jest mniej niezawodna niż bisekcja.

Wyjątkiem byłaby sytuacja, w której program komputerowy musiałby rozwiązywać równania bardzo wiele razy w trakcie swojego działania. Wtedy czas zaoszczędzony szybszymi metodami może być znaczący.

Następnie program mógłby rozpocząć się od metody Newtona, a jeśli metoda Newtona nie jest zbieżna, przejść na regula falsi , być może w jednej z jej ulepszonych wersji, takich jak wersje Illinois lub Anderson – Björck. Lub, jeśli nawet to nie jest zbieżne tak dobrze jak bisekcja, przełącz się na bisekcję, która zawsze zbiega się z użyteczną, jeśli nie spektakularną szybkością.

Kiedy zmiana y staje się bardzo mała, a x również zmienia się bardzo mało, wówczas metoda Newtona najprawdopodobniej nie będzie sprawiała problemów i będzie zbieżna. Tak więc w tych sprzyjających warunkach można było przejść na metodę Newtona, jeśli ktoś chciał, aby błąd był bardzo mały i chciał bardzo szybkiej zbieżności.

Przykład: wzrost sitowia

W rozdziale 7 Dziewięciu rozdziałów problem ze znalezieniem źródła można przetłumaczyć na współczesny język w następujący sposób:

Problem nadmiaru i deficytu nr 11:

• Sierść urosła pierwszego dnia o 3 jednostki. Pod koniec każdego dnia obserwuje się wzrost rośliny o 1/2 wzrostu z poprzedniego dnia.
• Klubowy pośpiech powiększył się o 1 jednostkę pierwszego dnia. Pod koniec każdego dnia roślina urosła 2 razy bardziej niż poprzedniego dnia.
• Znajdź czas [w ułamkach dni] , w którym pośpiech klubowy osiągnie wysokość sitowia.

Odpowiedź: ${\ Displaystyle (2 + {\ Frac {6} {13}})}$ dni; wysokość wynosi ${\ Displaystyle (4 + {\ Frac {8} {10}} + {\ Frac {6} {130}})}$ jednostek.

Wyjaśnienie:

• Załóżmy, że jest dzień 2. Gorączka klubowa jest krótsza niż sitowia o 1,5 jednostki.
• Załóżmy, że jest to dzień 3. Gorączka klubowa jest wyższa niż sitowia o 1,75 jednostki. ∎

Wykres funkcji F , jej pierwiastek dokładny (punkt K ) i pierwiastek przybliżony

Aby to zrozumieć, wymodelujemy wysokość roślin w dniu n ( n = 1, 2, 3...) na podstawie szeregu geometrycznego .

${\ Displaystyle B (n) = \ suma _ {i = 1} ^ {n} 3 \ cdot {\ Frac {1} {2 ^ { i-1}}} \ quad}$ sitowia do

$\ Displaystyle C (n) = \ suma _ {i = 1} ^ {n} 1 \ cdot 2 ^{i-1}\quad }$ Klubowy pośpiech

Dla lepszej notacji niech ${\ displaystyle k = i-1}$ . Przepisz serie wysokości roślin i wywołaj formułę $}$ . ${\ Displaystyle B (n), \ C (n$ )

${\ Displaystyle B (n) = \ suma _ {k = 0} ^ {n-1} 3 \ cdot {\ Frac {1} {2 ^ {k}}} = 3 \ lewo ({\ Frac {1- ({\frac {1}{2}})^{n-1+1}}{1-{\frac {1}{2}}}}\right)=6\left(1-{\frac { 1} {2 ^ {n}}} \ prawej)}$

${\ Displaystyle C (n) = \ suma _{k=0}^{n-1}2^{k}={\frac {1-2^{n}}{1-2}}=2^{n}-1}$

Teraz użyj regula falsi , aby znaleźć pierwiastek z ${\ Displaystyle (C (n) -B (n))}$

${\ Displaystyle F (n): = C (n) -B (n) = {\ Frac {6} 2^{n}}}+2^{n}-7}$

Ustaw ${\ Displaystyle x_ {1} = 2}$ i oblicz co jest równe ${\ Displaystyle F (x_ {1}) = F (2)}$${\ Displaystyle -1,5}$ („deficyt”). Ustaw i oblicz $3 ) x 2 = 3 {\$${\ Displaystyle F (x_ {2}) = F (3)}$ , co równa się ${\ Displaystyle 1,75}$ („nadmiar”).

Szacowany pierwiastek (1. iteracja):

${\ Displaystyle {\ kapelusz {x}} = {\ Frac {x_ {1} F (x_ {2}) -x_ {2} F (x_ {1})} {F (x_ {2}) -F ( x_{1})}}={\frac {2\razy 1,75+3\razy 1,5}{1,75+1,5}}\około 2,4615}$

Przykładowy kod

Ten przykładowy program, napisany w języku programowania C , jest przykładem algorytmu Illinois. Aby znaleźć liczbę dodatnią x , gdzie cos( x ) = x ³ , równanie przekształca się w postać znajdowania pierwiastków f ( x ) = cos ( x ) - x ³ = 0 .

 
 

   
      





   #include  <stdio.h>  #include  <math.h>  double  f  (  double  x  )  {  return  cos  (  x  )  -  x  *  x  *  x  ;  }  /* a,b: punkty końcowe przedziału, w którym szukamy  e: połowa górnej granicy błędu względnego  m: maksymalna liczba iteracji  */  double  FalsiMethod  (  double  (  *  f  )(  double          
     
       0
   
      
      

      0  ),  podwójne  a  ,  podwójne  b  ,  podwójne  e  ,  int  m  )  {  podwójne  c  ,  fc  ;  int  n  ,  bok  =  ;  /* wartości początkowe w punktach końcowych przedziału */  double  fa  =  f  (  a  );  podwójne  fb  =  fa  (  b  );  dla  (  n  =  ;  n     
                  
               
         
        

        <  m  ;  n  ++  )  {  do  =  (  fa  *  b  -  fb  *  za  )  /  (  fa  -  fb  );  if  (  fabs  (  b  -  a  )  <  e  *  fabs  (  b  +  a  ))  przerwa  ;  fc  =  fa  (  do  );  jeśli  (     0 
         
              
            
              
           
             0 
         
             fc  *  fb  >  )  {  /* fc i fb mają ten sam znak, skopiuj c do b */  b  =  c  ;  fb  =  fc  ;  jeśli  (  strona  ==  -1  )  fa  /=  2  ;  bok  =  -1  ;  }  else  if  (  fa  *  fc  >  )  {  /* fc i fa mają ten sam znak, skopiuj c do a */  a  =  c  ;  fa   
            
              
           
        
         
         
      
   
    


  
     =  fc  ;  jeśli  (  bok  ==  +  1  )  fb  /=  2  ;  bok  =  +  1  ;  }  else  {  /* fc * f_ bardzo małe (wygląda jak zero) */  break  ;  }  }  powrót  c  ;  }  int  main  (  void  )  {  printf  (  "%0.15f  \n  "  ,  FalsiMethod  (  0   
    0
 &  f  ,  1  ,  5E-15  ,  100  ))  ;  powrót  ;  } 

Po uruchomieniu tego kodu ostateczna odpowiedź to około 0,865474033101614.

Zobacz też

• Metoda ITP , odmiana z gwarantowanym minimum i zbieżnością superliniową
• Metoda Riddersa , kolejna metoda wyszukiwania korzeni oparta na metodzie fałszywej pozycji
• Metoda Brenta

Dalsza lektura

•   Ciężar, Richard L.; Targi, J. Douglas (2000). Analiza numeryczna (wyd. 7). Brooks/Cole. ISBN 0-534-38216-9 .
•   Sigler, LE (2002). Liber Abaci Fibonacciego, Księga obliczeń Leonarda Pisano . Springer-Verlag. ISBN 0-387-40737-5 .
•   Roberts, AM (2020). „Filologia matematyczna w traktacie o podwójnym fałszywym stanowisku w rękopisie arabskim na Uniwersytecie Columbia” . Spotkania filologiczne . 5 (3–4): 3–4. doi : 10.1163/24519197-BJA10007 . S2CID 229538951 . (O wcześniej niepublikowanym traktacie o podwójnej fałszywej pozycji w średniowiecznym rękopisie arabskim).