DMUG-Archiv 1998

Frühere

 

Chronologischer Index

 

Spätere

Vorherige

 

Thematischer Index

 

Nächste

Re: Wurzeln komplizierter (weil umfangreicher) polynomialer Gleichun

On Jun 3,  5:33pm, ww14ckrd@XXXXXXX.de wrote:
> Subject: Wurzeln komplizierter (weil umfangreicher) polynomialer Gleichun
> Liebe Mathematica-User,
>
> weisz jemand zufaellig, ob und wo es eine robuste Mathematica-Routine
> zur Auffindung ALLER Wurzeln eines (sehr umfangreichen) Systems von n
> polynomialen, algebraischen Gleichungen in n Unbekannten gibt?
> "NSolve" schmiert leider schon bei mittelschweren Problemen ab und
> "FindRoot" liefert, wenn ueberhaupt, nur eine Wurzel. In der
> Hoffnung, dasz irgendwer schon ein aehnliches Problem geloest hat,
> verbleibe ich

Eine Moeglichkeit polynomiale Gleichungssysteme zu Loesen, ist die Theorie der
Groebner Basen zu verwenden. Ein gegebenes Gleichungssystem kann man mit Hilfe
des Buchberger Algorithmus in ein aequivalentes Gleichungssystem umformen, das
dann "Groebner Basis" genannt wird (aehnlich wie man ein lineares System, auf
Dreiecksgestalt bringt).
Hat man ein Gleichungssystem und berechnet die Groebner Basis bezueglich der
lexikografischen Ordnung dieses Systems, so ist die Groebner Basis in
Dreiecksgestalt, d.h. sie enthaelt Polynome in n Variablen, (n-1) Variablen,
(n-2) Variablen usw. Enthaelt die Groebner Basis eine Konstante, so hat das
System keine Loesung, gibt es ein Polynom in einer Variablen, dann hat das
System endlich viele Loesungen (in C), gibt es nur Polynome mit >= 2 Variablen,
so hat das System unendlich viele Loesungen.
Wenn's nur endlich viele Loesungen gibt, kann man sich sukzessive nach oben
arbeiten. Hier ein Beispiel:

In[1]= f = {x^2+y+z-1, x+y^2+z-1,x+y+z^2-1};

In[2]= g = GroebnerBasis[f,{x,y,z}, MonomialOrder->Lexicographic]

Out[2]= {-z^2 + 4*z^3 - 4*z^4 + z^6, -z^2 + 2*y*z^2 + z^4,
  -y + y^2 + z - z^2, -1 + x + y + z^2}

In[5]= Solve[g[[1]] == 0,z]

Out[5]= {{z -> 0}, {z -> 0}, {z -> 1}, {z -> 1},
  {z -> -1 - Sqrt[2]}, {z -> -1 + Sqrt[2]}}

Alle Loesungen des 1. Polynoms kann man jetzt ins 2. Polynom einsetzten und
dieses dann nach y loesen usw.
Mir scheint, dass Solve das automatisch macht:

In[6]=
Solve [{x^2+y+z-1==0, x+y^2+z-1==0,x+y+z^2-1==0},{x,y,z}]


Out[6]= {{x -> 0, y -> 0, z -> 1}, {x -> 0, y -> 0, z -> 1},
  {x -> 0, y -> 1, z -> 0}, {x -> 1, y -> 0, z -> 0},
  {x -> -2 + 2*Sqrt[2] + 7/(3 - 2*Sqrt[2]) -
     (5*Sqrt[2])/(3 - 2*Sqrt[2]),
   y -> (7 - 5*Sqrt[2])/(-3 + 2*Sqrt[2]),
   z -> -1 + Sqrt[2]}, {x ->
    -2 - 2*Sqrt[2] + 7/(3 + 2*Sqrt[2]) +
     (5*Sqrt[2])/(3 + 2*Sqrt[2]),
   y -> (-7 - 5*Sqrt[2])/(3 + 2*Sqrt[2]),
   z -> -1 - Sqrt[2]}}

Theoretisch kann man so fuer ein System mit endl. vielen Loesungen alle reellen
Loesungen finden. Das Problem ist, dass die zugrundeliegenden Algorithmen so
komplex sind, dass sie fuer groessere Probleme nicht mehr in ertraeglicher Zeit
und Speicherverbrauch laufen. Eine weitere Moeglichkeit, Variablen aus dem
polynomialen Gleichungssystem zu eliminieren waere die Resultante
(implementiert in MMA: Resultant[poly_1,poly_2,var]), aber fuer groessere
Polynome ist das praktisch nicht mehr durchfuehrbar. Weiters gibt es den MMA
Befehl Eliminate[eqns, var], der Variable aus einem System eliminiert. Ich
vermute, dass dieser Befehl im Prinzip Groebner Basen und/oder Resultanten
ausrechnet, d.h. es ist fraglich ob er fuer groessere Systeme noch
funktioniert, aber man kann's ja mal probieren...

Gruesse,
  Andreas





-- 

Andreas Unterkircher              Institut fuer Umformtechnik
ETH Zentrum / CLA, Tannenstr. 3, CH-8092 Zuerich, Switzerland
Phone: ++43 1 632 66 21                http://www.ifu.ethz.ch        


Verweise:
Wurzeln komplizierter (weil umfangreicher) polynomialer Gleichun
ww14ckrd, 03.06.1998

Frühere

 

Chronologischer Index

 

Spätere

Vorherige

 

Thematischer Index

 

Nächste

DMUG-Archiv, http://www.mathematica.ch/dmug-liste.html; Letzte Änderung: 08.09.2003 20:44