numerikus módszerek

Algoritmusok

Sziasztok!

van egy feladatom, amin nem igazán tudom, hogy hogyan induljak el, egy egyenlet/egyenlőtlenség rendszert kellene megoldani polinom időben, ha egyáltalán lehetséges:

x2,x1,x0 változókkal (egészek):

1.) x1^2 = 4*x2*x0
2.) y1^2 +2*y1*x1 = 4*y0*(y2+x0) + 4*x2*y0
3.) 100*x2+10*x1+x0 < 100*y2+10*y1+y0

és y2,y1,y0 konstansok, és egészek.

Gondolkoztam azon, hogy valahogy a Newton iterációval meg lehetne oldani a feladatot, de ott valós számokkal dolgoznak, illetve amit én ismerek az egy változós függvényeket használ és nem igazán tudom, hogy hogyan lehetne kiterjeszteni három dimenzióra.

Köszi!

-----------------------

na párszor javítottam, most már minden OK :)

  • 2986 megtekintés

( denes | 2008. 01. 15., k – 00:17 )

amugy ehhez minek numerikus modszerek? harom ismeretlen, harom egyenlet, sima ugy papiron is.

szerk: ja, lineris egyenelet(es egyenlotlenseg) rendszerekre valoban vannak numerikus modszerek. most speciel csak a gauss eliminacio jut eszembe, de tudom, hogy erre vannak ilyen szep matrixos vagy milyen algoritmusok - nyilvan tanultatok, azert kerdezik. na bocs, nem nagyon tudok segiteni, mert mar elfelejtettem ezeket.

- Use the Source Luke ! -

a gauss eliminacio valoban nem. de papiron minden egyenlet/egyenlotlensegbol sorban kifejezni valamelyik ismeretlent mig marad egy kb. masodfoku egy ismeretlenes egyenlet/egyenlotlenseg amit konnyen meg lehet oldani - nos ez jarhato, es elso mondatomban erre gondoltam.

- Use the Source Luke ! -

( apal v | 2008. 01. 15., k – 00:19 )

a (2) egyenletbol x1 egyertelmuen kijon, igy ilyen alakra hozhato az egyenlet:

x0*x2 = c1 (1')
100x2+x0 < c2 (2')

(c1 = x1^2/4, a (2) egyenlet megoldasabol, c2=100y2+10y1+y0-10x1)

ha c1 egesz (marpedig ha x0 es x2 is csak az lehet, akkor kenytelen az lenni; ha megsem, akkor nincs az egyenletnek megoldasa), akkor x0 es x2 meghatarozhato, csak ordo(log(c1)) esetet vegigprobalsz, melyekre teljesul a (2') egyenlet. Ha megis maradunk valos szamoknal akkor az (1') es (2') egyenlet az a tipikus gimis "hiperbola es egyenes altal kozrefogott terulet" vagy vmi hasonlo problema, ennek megoldasa mar enyhen szolva egyszeru".

Valami olyasmit lehet akkor csinalni, hogy a 3. egyenletben bevezetsz egy parametert (legyen p, pozitiv), azaz ugy hogy jobboldal + p = baloldal fennaljon (es ha x-ek es y-k is egeszek, akkor p is egesz lesz). Ekkor a (2) es a (3) egyenletekbol az x0-t es az x2-et p es x1 segitsegevel ki tudod fejezni, az sima mezei linearis egyenlet. Majd ha ezt beirod az (1)-be, akkor egy tisztan masodfoku egyenletet kapsz x1-re. Annak a D diszkriminansa nyilvan fuggeni fog p-tol (az y-okon tul). Az x1 pedig akkor lesz egesz, ha D egyreszt nemnegativ (ez meg hogy p > 0 belhatarolja a lehetseges p-k halmazat) masreszt D az negyzetszam.

( strangelove | 2008. 01. 15., k – 08:19 )

két nagy irányba lehet elindulni.

első:
megnézni, hogy ki konvex/ki affin; (egyoldalra történő rendezés után), ezután pedig büntető v. akadályfüggvényezni.

második:
formális manipulációk/ad hoc egyszerűsítések után megnézni, hogy kezelhető méretűvé redukálódott-e az egész hóbelebanc.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

( sebist v | 2008. 01. 15., k – 10:08 )

Az ilyen es ehhez hasonlo feladatokkal az operaciokutatas temakorben lehet talalkozni. Ezek az un: linearis programozasi feladatok. Arra nem vallalkozok, hogy megoldjam neked, de irok meg egy-ket kulcsszot, amire erdemes keresni:
simplex modszer
solver

Udv:
Istvan

Csak az a baj, hogy ez nemlineáris programozás, mert a megadott egyenletek/egyenlőtlenségek nem lineáris korlátok.
Ehhez segítség található:

Bazaraa, M.S., H.D. Sherali, C.M. Shetty: Nonlinear Programming, Theory and Algorithms, Wiley, New York, 1993.
Gill, P.E., W. Murray, M.H. Wright: Practical Optimization, Academic Press, London, 1981.
Komlósi Sándor: Nemlineáris Optimalizálás, JPTE, Pécs, 1997.
Krekó Béla: Optimumszámítás. Nemlineáris Programozás, Közgazdasági és Jogi Könyvkiadó, Budapest, 1972.

Üdv!
____________________________________________________________
Slackware 12/current - linux-2.6.23.12-olorin - KDE 3.5.8

( machobymb v | 2008. 01. 15., k – 10:50 )

Ha el szeretnél benne mélyülni, én az alábbiból tanultam annak idején:
Imreh Balázs: Operációkutatás.
De a haveromék a GDF-nél is tanultak, annak is a címe Operációkutatás, csak nem tudom ki a szerző.

Üdv: Laci

( neuro | 2008. 01. 15., k – 16:16 )

Köszönök minden segítséget, megpróbálok utánanézni az ajánlott dolgoknak!

( takdavid | 2008. 01. 15., k – 21:44 )

Elemi átalakításokkal is (majdnem) sikerült a végére járni.

Ha van megoldás, x0*x2 teljes négyzet, ez világos 1)-ből.
(Az is, hogy x1 páros, sőt y1 is páros, de ez nem használható fel, úgy tűnik.)

Lehet x0=x2, ekkor a 2)-ből egyszerűen kifejezhető x0 (x0 = ((y0y2-(y1/2)^2)/(y1-2y0)) vagy mi), ami =x2, és így adott x1 is, 3) pedig legfeljebb kizárja ezt az egy lehetséges megoldást.

Lehet x0!=x2, ekkor hasonló egyenlőség jön ki 2)-ből x0+x2-re, ez már tényleg diofantoszi, végtelen megoldás, de ezt korlátozza 3), és a kipróbálandó xi-k száma legfeljebb lineáris y2-vel.