Kettősség

A dichotómia ( görögül διχοτομία : δῐχῆ , „ketté” + τομή , „felosztás”) elágazás , következetes felosztás két részre, amelyek belül jobban összefüggenek, mint egymás között. Az osztályok alosztályokra való logikai felosztásának módszere, amely abból áll, hogy az osztható fogalmat teljesen két, egymást kizáró fogalomra osztják. A dichotóm felosztás a matematikában , a filozófiában , a logikában és a nyelvészetben egy fogalom vagy kifejezés alfejezeteinek kialakításának módja, és az elemek osztályozásának kialakítására szolgál.

Előnyök és hátrányok

A dichotóm felosztás egyszerűségében vonzó. Valójában egy dichotómiában mindig csak két osztállyal foglalkozunk, amelyek kimerítik az osztható fogalom hatókörét. Így a dichotóm felosztás mindig arányos; osztástagok kiegészítik egymást, mivel az osztható halmaz minden egyes objektuma csak az a osztályok egyikébe esik vagy nem a ; a felosztást egy alapon hajtják végre - valamilyen jel megléte vagy hiánya. Ha az osztható fogalmat a betűvel jelöljük, és a kötetében kiemelünk egy bizonyos típust, mondjuk a b , az a kötetet két részre oszthatjuk - b és nem b részre .

A dichotóm felosztásnak van egy hátránya: amikor egy fogalom hatókörét két fogalomra osztjuk, minden alkalommal rendkívül határozatlan marad annak a része, amelyhez a „nem” részecske tartozik. Ha a tudósokat történészekre és nem történészekre osztjuk , akkor a második csoport nagyon homályos. Ráadásul, ha egy dichotóm felosztás kezdetén általában meglehetősen könnyű megállapítani egy ellentmondásos fogalom jelenlétét, akkor ahogy távolodunk az első fogalompártól, egyre nehezebb megtalálni azt.

Alkalmazás

A dichotómiát általában segédeszközként használják az osztályozás felállításához.

Ismert egy meglehetősen széles körben használt keresési módszerről is, az úgynevezett dichotómiás módszerről . Valós értékű függvény értékeinek meghatározására szolgál, amelyeket valamilyen kritérium határoz meg (ez lehet egy minimum , maximum vagy egy adott szám összehasonlítása). Tekintsük a feltételes egydimenziós optimalizálás dichotómia módszerét (a minimalizálás határozottsága érdekében).

Dichotómia módszer

A dichotómia módszer némileg hasonlít a felező módszerhez , de eltér attól a végek eldobásának kritériumában.

Legyen adott függvény . $f(x):\;[a,\;b]\to \mathrm {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$

Osszuk ketté a mentálisan adott szakaszt, és vegyünk a középpontra szimmetrikusan két pontot , így: $x_{1}$ $x_{2}$

{\begin{array}{ccc}x_{1}&=&{\frac {a+b}{2}}-\delta ,\\x_{2}&=&{\frac {a+ b }{2}}+\delta ,\end{tömb}}

hol van valamilyen szám az intervallumban . $\delta$ $\left(0,\;{\frac {ba}{2))\right)$

Számítsunk ki két függvényértéket két új pontban. Összehasonlításképpen meghatározzuk, hogy a két új pont közül melyikben a legnagyobb a függvény értéke. Eldobjuk az eredeti szegmens végét, amelyhez közelebbinek bizonyult a függvény maximális értékű pontja (emlékezzünk vissza, minimumot keresünk ), azaz: $f(x)$ $f(x)$

Ha , akkor a szegmens felvételre kerül , és a szegmens eldobásra kerül. $f(x_{1})>f(x_{2})$ $[x_{1},\;b]$ $[a,\;x_{1}]$
Ellenkező esetben a rendszer a középhez képest tükröződő szegmenst veszi és elveti . $[a,\;x_{2}]$ $[x_{2},\;b]$

Az eljárást addig ismételjük, amíg el nem érjük a megadott pontosságot, például amíg a szakasz hossza el nem éri a megadott hiba értékének kétszeresét.

Minden iterációnál új pontokat kell számolni. Biztosítható, hogy a következő iterációnál csak egy új pontot kell számítani, ami jelentősen hozzájárulna az eljárás optimalizálásához. Ezt az aranymetszetben lévő szelvény tükörosztásával érik el , ebben az értelemben az aranymetszet módszere a dichotómia módszer továbbfejlesztésének tekinthető azzal a paraméterrel , ahol az aranymetszet . $\delta =(ba)\left({\frac {1}{\Phi }}-{\frac {1}{2}}\right)$ $\Phi \!={\frac {{\sqrt {5}}+1}{2}}\kb 1{,}6180339887\pont$

Lásd még

Irodalom

Levitin A. V. 11. fejezet Kényszerek leküzdése: A felezési módszer // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 476-480. — 576 p. — ISBN 978-5-8459-0987-9
Akulich I. L. Matematikai programozás példákban és feladatokban: Proc. diákgazdasági juttatás. háziállatok. egyetemek. - M . : Felsőiskola, 1986.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Számítási módszerek mérnökök számára. - M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerikus módszerek. - 8. kiadás - M . : Alapismeretek Laboratóriuma, 2000.
Volkov E. A. Numerikus módszerek. — M. : Fizmatlit, 2003.
Gill F., Murray W., Wright M. Gyakorlati optimalizálás. Per. angolról. - M .: Mir, 1985.
Korn G., Korn T. Matematikai kézikönyv tudósok és mérnökök számára. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
Maksimov Yu. A. Lineáris és diszkrét programozási algoritmusok. — M. : MEPhI, 1980.

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás