Dikotomia

Dikotomia ( kreikaksi διχοτομία : δῐχῆ , "kaksi" + τομή , "jako") on kahtiajako , johdonmukainen jakautuminen kahteen osaan, jotka liittyvät enemmän sisäisesti kuin keskenään. Menetelmä luokan loogiseksi jakamiseksi alaluokkiin, joka koostuu siitä, että jaettava käsite on täysin jaettu kahteen toisensa poissulkevaan käsitteeseen. Dikotominen jako matematiikassa , filosofiassa , logiikassa ja kielitieteessä on tapa muodostaa yhdestä käsitteestä tai termistä alajaksoja, ja se toimii elementtien luokituksen muodostamisessa.

Edut ja haitat

Dikotominen jako on houkutteleva yksinkertaisuudessaan. Itse asiassa dikotomiassa käsittelemme aina vain kahta luokkaa, jotka tyhjentävät jaettavan käsitteen laajuuden. Siten kaksijakoinen jako on aina suhteellinen; jaon jäsenet täydentävät toisiaan, koska jokainen jaettavan joukon objekti kuuluu vain yhteen luokista a tai ei a ; jako suoritetaan yhdellä perusteella - jonkin merkin läsnäolo tai puuttuminen. Merkimällä jaettavissa oleva käsite kirjaimella a ja korostamalla sen tilavuudessa tiettyä tyyppiä, esimerkiksi b , voimme jakaa tilavuuden a kahteen osaan - b eikä b .

Dikotomisella jaolla on haittapuoli: kun käsitteen laajuus jaetaan kahteen käsitteeseen, jää joka kerta äärimmäisen määrittelemättömäksi se osa siitä, johon partikkeli "ei" kuuluu. Jos tiedemiehet jaetaan historioitsijoiksi ja ei-historioitsijoiksi , toinen ryhmä on hyvin epäselvä. Lisäksi, jos kaksijakoisen jaon alussa on yleensä melko helppoa todeta ristiriitaisen käsitteen olemassaolo, niin kun siirryt pois ensimmäisestä käsiteparista, sen löytäminen on yhä vaikeampaa.

Sovellus

Dikotomiaa käytetään yleensä apuvälineenä luokituksen muodostamisessa.

Se tunnetaan myös melko laajalti käytetystä hakumenetelmästä, ns. dikotomiamenetelmästä . Sitä käytetään jollakin kriteerillä määritetyn reaaliarvoisen funktion arvojen etsimiseen (tämä voi olla minimi- , maksimi- tai tietyn luvun vertailu). Tarkastellaan ehdollisen yksiulotteisen optimoinnin dikotomiamenetelmää (minimoinnin tarkkuuden vuoksi).

Dikotomiamenetelmä

Dikotomiamenetelmä on jossain määrin samanlainen kuin puolittamismenetelmä , mutta eroaa siitä päiden hylkäämiskriteerissä.

Olkoon funktio annettu . $f(x):\;[a,\;b]\to \mathrm {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$

Jaetaan mentaalisesti annettu segmentti puoliksi ja otetaan kaksi pistettä, jotka ovat symmetrisiä keskustan suhteen ja siten, että: $x_{1}$ $x_{2}$

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

missä on jokin luku välissä . $\delta$ $\left(0,\;{\frac {ba}{2))\right)$

Lasketaan kaksi funktioarvoa kahdessa uudessa pisteessä. Vertailun vuoksi määritetään, missä kahdesta uudesta pisteestä funktion arvo on suurin. Hylkäämme alkuperäisen segmentin pään, jota lähempänä piste, jolla on funktion maksimiarvo, osoittautui olevan lähempänä (muista, etsimme minimiä ), eli: $f(x)$ $f(x)$

Jos , segmentti otetaan ja segmentti hylätään. $f(x_{1})>f(x_{2})$ $[x_{1},\;b]$ $[a,\;x_{1}]$
Muussa tapauksessa segmentti, joka peilataan suhteessa keskikohtaan, otetaan ja hylätään . $[a,\;x_{2}]$ $[x_{2},\;b]$

Toimenpide toistetaan, kunnes määritetty tarkkuus saavutetaan, esimerkiksi kunnes segmentin pituus saavuttaa kaksi kertaa määritetyn virheen arvon.

Jokaisella iteraatiolla on laskettava uudet pisteet. On mahdollista varmistaa, että seuraavassa iteraatiossa on tarpeen laskea vain yksi uusi piste, joka edistäisi merkittävästi menettelyn optimointia. Tämä saavutetaan segmentin peilijaolla kultaleikkauksessa , tässä mielessä kultaleikkausmenetelmää voidaan pitää parannuksena dikotomiamenetelmään parametrilla , jossa on kultaleikkaus . $\delta =(ba)\left({\frac {1}{\Phi }}-{\frac {1}{2}}\right)$ $\Phi \!={\frac {{\sqrt {5}}+1}{2}}\noin 1{,}6180339887\pisteet$

Katso myös

Kirjallisuus

Levitin A. V. Luku 11. Rajoitusten voittaminen: Bisection Method // Algoritmit. Johdatus kehittämiseen ja analyysiin - M . : Williams , 2006. - S. 476-480. — 576 s. — ISBN 978-5-8459-0987-9
Akulich I. L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. lemmikkejä. yliopistot. - M . : Korkeakoulu, 1986.
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Laskennalliset menetelmät insinööreille. - M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeeriset menetelmät. - 8. painos - M . : Perustiedon laboratorio, 2000.
Volkov E. A. Numeeriset menetelmät. - M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmit epälineaaristen ohjelmointiongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineaariset ja diskreetit ohjelmointialgoritmit. - M .: MEPhI, 1980.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi