Determináns gyorsan, pontosan
2010-07-29T12:05:52+02:00
2010-07-30T19:38:12+02:00
2022-07-01T05:42:30+02:00
  • Határozottan pontosabb lesz, a műveletigény nem nő minőségileg O(a*n^3)-ről O(b*n^3)-re, vagyis csak konstans-szorosan.
    Mutasd a teljes hozzászólást!
  • Néhány javalsat:

    1. A Numerical Recipes-ben érdemes elolvasni az idevágó fejezeteket. (A kicsit régebbi változata a könyvnek elérhető ingyenesen online, kiindulásnak teljesen jó).

    2. a wiki LU dekompoziciót javasol det számításra, sztem megér egy próbát.

    3. Nem vagyok teljesen biztos benne, hogy egy iteratív algoritmus itt működni fog. Az érvelésem a következő:

    Tekintsünk az egyszerűség kedvéért valami ilyesmit:

    Ax = b (ezt oldja meg a Gauss)

    ahol x-et keressük, b-és A adott. "A" a "gép", ami x-el csinál valamit, hogy b-t kapjuk (pl. egy mátrix és lin. trafót csinál). Az ilyen iterativ javitó algoritmusok valahogy úgy működnek, hogy van valami kiindulási megoldás x-re, nevezzük x0-nek, amire hattatjuk A-t, és kapunk valami b0-t. Ekkor van egy jóldefiniált hibánk: err = |b-b0|, amit használhatunk arra, hogy egy jobb becslést kaphassunk a valódi x megoldásra. Ezek után ezt ismételjük addig, amíg err egy bizonyos küszöb alá csökken. A determináns számításnál nem látok ellenőrzési lehetőséget. Adott az "A" mátrix, és azt redukáljuk 1 számmá, nem tudok abszolut hibát definiálni... Szóval szerintem nem a Gauss-os dolog kell neked. Ha tévedek, valaki okosabb majd kijavít.

    Még egy megjegyzés: minden számítás nagyon függ attól, hogy mekkora számok vannak a mátrixban, mekkora számok lépnek fel a köztes műveletek elvégzésekor. Ilyenkor jönnek olyan dolgok h Cahan összegzés, az összeadandók (szorzandók) nagyság szerinti rendezése és a műveletek ebben a sorrendben való elvégzése stb. De ezektől iszonyat lassú és bonyolult lesz az alg, cserébe talán picit pontosabb.

    Az ultimate tüneti kezelés pedig az, ha vesz az ember egy "tetszőlegesen hosszú" számokat kezelő rutin csomagot és azt használja:) Na ez nyilván vicc, illetve csak nagyon indokolt esetben ajánlott...
    Mutasd a teljes hozzászólást!
  • mennyivel lesz így pontosabb? a műveletigény, hogyan változik?
    (tudom, próbáljam ki...(ki is fogom))

    jelenleg: csak sorcsere van.
    (de már kész az oszlopcserét végző metódus is
    főátlóban haladva, minden iterációban lépcsős mátrix-xá alakítás történik (ez hanyagolható lesz)

    tehát kiválasztani a legnagyobb abszolútértékű elemet, és pozícióba hozni.

    köszönöm.

    ártalmatlan gyakorlásnak indult, de már látom, komoly, sőt kezd computeralgebrás lenni...
    Mutasd a teljes hozzászólást!
  • nem ismerem amiket felsoroltál.
    lehetne picit bővebben?

    egyébként programot szeretnék írni (c++ ban) ehhez gyűjtöm az információt
    Mutasd a teljes hozzászólást!
  • A pontosságot a főelemkiválasztás nevű módszerrel lehet javítani. Ha mondjuk ott tartunk, hogy az első oszlop elemeit akarjuk nullázni a sor legalsó elemének felhasználásával, ezzel a képlettel:
    sor[i][j] = sor[i][j] - sor[n][j]*sor[i][1]/sor[n][1]
    akkor még ezelőtt megkeressük az 1. oszlop maximális abszolútértékű elemét, és egy sorcserével elérjük, hogy az legyen az a[n][1]. Haladó esetben a maximumkeresést az egész mátrixra (mármint a pillanatnyilag átalakítatlan része) kiteresztjük, ekkor persze sor és oszlopcsere is kellene fog.

    A főelemkiválasztásos Gauss-módszer
    Mutasd a teljes hozzászólást!
  • szia

    math library-k teljesítményével nem vagy megelégedve?
    pl intel math lib, esetleg GPU alapú számítás (pl OpenCL, CUDA) nem jöhet szóba?
    Mutasd a teljes hozzászólást!
  • A mátrix determinánsát a mátrixot pl. felső 3 szögmátrix-xá alakítva a főátlóbeli elemek szorzataként viszonylag gyorsan ki lehet számolni. Ezt a módszert építettem bele készülő programomba, de nem vagyok megelégedve a pontosságával.
    A determináns kifejtése pontos, de lassú. A programban ez is benne van, de 10x10 mátrixnál javallott hanyagolni a használatát.

    Tegnap olvastam a Gauss eliminációval megoldott lineáris egyenletrendszer gyökeinek iteratív pontosításáról. A módszer tul.képpen a mátrix szorzás/összeadás disztributív tulajdonnságára épít.

    Azon gondolkodom van-e hasonló megoldás az eliminációval számolt determináns értékének pontosításához is. (Ami gyorsabb legyen a kifejtésénél

    Bármilyen tanácsot szívesen veszek.
    Mutasd a teljes hozzászólást!
abcd