Quadratisches Gleichungssystem

[Matthias Noske]

Hallo,
Ich habe folgendes Gleichungssystem:
(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R
Die Großbuchstaben S,T,U,P,Q,R sind bekannte Konstanten; x,y,z sind die
gesuchten Variablen. Die Quadrate zusammen mit den gemischten Termen machen
das ganze unangenehm. Mit normalem Auflösen komm ich da nicht weiter. Wäre
nett, wenn mir jemand bei der Lösung helfen könnte. Ein numerisches
Verfahren wär auch OK. (Mein Kenntnisstand: Analysis I,II und LA.)
mfg,
Matthias Noske

[Alfred Flaßhaar]

Post by Matthias Noske
Hallo,
(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R

(...)

"derive" meint nach 60 s, daß fürchterliche Bandwürmer als
geschlossene Ausdrücke für die Lösung herauskommen. Woher
stammt die Aufgabe?

Alfred

[Matthias Noske]

Post by Alfred Flaßhaar
Woher
stammt die Aufgabe?

Da muss ich jetzt etwas weiter ausholen. Ich habe drei bekannte Punkte im
Raum, deren Abstand bekannt ist. Der Abstand zwischen den Punkten ist im
realen 3-D-Raum P,Q und R.
Jetzt habe ich ein Foto, aus dem ich Richtungsvektoren S,T,U für drei
Geraden bestimme, auf denen die Punkte liegen müssen, die Kamera ist im
Ursprung und die drei Geraden sind Ursprungsgeraden mit folgenden
Gleichungen (im |R^3):
g1(x)=Sx
g2(y)=Ty
g3(z)=Uz
Jetzt weiß ich, dass ein Punkt auf g1, einer auf g2 und einer auf g3 liegt.
Es geht jetzt quasi darum, ein Dreieck mit den Seitenlängen P,Q und R so zu
legen, dass die Ecken auf den drei Geraden liegen. Es gilt also:
||g1(x)-g3(z)||=P
||g1(x)-g2(y)||=Q
||g2(y)-g3(z)||=R

mit einsetzen und quadieren ergibt das:
(I) SS*x^2-2*SU*xz+UU*z^2=P^2
(II) SS*x^2-2*ST*xy+TT*y^2=Q^2
(III) TT*y^2-2*TU*yz+UU*z^2=R^2
SS,SU,UU usw. sind Skalarprodukte von zwei Vektoren, also reelle Zahlen.
Und wenn man jetzt davon absieht, dass die konstanten Faktoren etwas anders
aussehen, haben wir das ursprüngliche Problem, wo ich nicht mehr weiter komm
(und wies ausschaut derive auch nicht :)

Matthias

[Alfred Flaßhaar]

(...) [praktischer Hintergrund]
Lassen sich die Koeffizienten in Intervalle einschließen?
Möglicherweise ist dann eine iterierbare Form
x(n+1):=A(x(n)) erreichbar. x ist hierbei der Lösungsvektor
und A der kontrahierende Operator.

(...)

Noch eine Idee, die ich bei einzelnen Problemen früher
genutzt habe:

Die iterierbare Form kann auch sein B(x(n+1))=A(x(n)). Darin
sei B ein leicht handhabbarer Operator. Im vorliegenden Fall
wäre nach Umformung der Gleichungen auszuprobieren
(Fallunterscheidungen lasse ich hier weg, nachfolgend ist
"0" die Zahl Null):

S*x(n+1)+0*y(n+1)+U*z(n+1) = sqrt(P+S*U*x(n)*z(n))

S*x(n+1)+T*y(n+1)+0*z(n+1) = sqrt(Q+S*T*x(n)*y(n))

0*x(n+1)+T*y(n+1)+U*z(n+1) = sqrt(R+T*U*y(n)*z(n))

Mit der Koeffizientendeterminate 2*S*T*U ist die höher
Iterierte als Lösung eines lin. Gleichungssystems leicht
auszurechnen. Entscheidend aber sind die Größen der
Parameter S, T, .... Damit hättest du eine Möglichkeit, ohne
die Undurchsichtigkeit eines maschinengängigen solvers
auszukommen.

Gruß, Alfred

[Hermann Kremer]

Matthias Noske schrieb in Nachricht ...

Post by Matthias Noske
Hallo,
(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R
Die Großbuchstaben S,T,U,P,Q,R sind bekannte Konstanten; x,y,z sind die
gesuchten Variablen. Die Quadrate zusammen mit den gemischten Termen machen
das ganze unangenehm. Mit normalem Auflösen komm ich da nicht weiter. Wäre
nett, wenn mir jemand bei der Lösung helfen könnte. Ein numerisches
Verfahren wär auch OK. (Mein Kenntnisstand: Analysis I,II und LA.)

Aus (I) kannst Du U*z als Funktion von S*x ausdrücken, aus (II) T*y als
Funktion von S*x , jeweils als Lösung(en) einer quadratischen Gleichung,
und aus (III) erhältst Du dann eine algebraische Gleichung ziemlich hohen
Grades für S*x ... wie schon Alfred gepostet hat, wird das ganze aber wirklich
extrem häßlich ...

Grüße
Hermann
--

Post by Matthias Noske
mfg,
Matthias Noske

[Matthias Noske]

Post by Hermann Kremer
Aus (I) kannst Du U*z als Funktion von S*x ausdrücken, aus (II)

T*y als

Post by Hermann Kremer
Funktion von S*x , jeweils als Lösung(en) einer quadratischen Gleichung,
und aus (III) erhältst Du dann eine algebraische Gleichung ziemlich hohen
Grades für S*x ...

Ja das stimmt schon. Aber mit diesem unangenehmen Ding komm ich der Lösung
leider nicht näher, ich bekomme lediglich etwas noch unübersichtlicheres,
das ich auch nicht lösen kann :(
Da muss es doch irgendein numerisches Verfahren geben, mit dem man entweder
das System (I) (II) (III) oder die aufgelöste Version lösen kann.

Post by Hermann Kremer
wie schon Alfred gepostet hat, wird das ganze aber wirklich
extrem häßlich ...

Das kann ich auch unterschreiben.

Matthias

[Jan C. Hoffmann]

Post by Hermann Kremer

Post by Hermann Kremer
Aus (I) kannst Du U*z als Funktion von S*x ausdrücken, aus

(II)

Post by Hermann Kremer
T*y als

Post by Hermann Kremer
Funktion von S*x , jeweils als Lösung(en) einer quadratischen Gleichung,
und aus (III) erhältst Du dann eine algebraische Gleichung

ziemlich

Post by Hermann Kremer
hohen

Post by Hermann Kremer
Grades für S*x ...

Ja das stimmt schon. Aber mit diesem unangenehmen Ding komm ich der Lösung
leider nicht näher, ich bekomme lediglich etwas noch

unübersichtlicheres,

Post by Hermann Kremer
das ich auch nicht lösen kann :(
Da muss es doch irgendein numerisches Verfahren geben, mit dem man entweder
das System (I) (II) (III) oder die aufgelöste Version lösen kann.

Numerisch sollte das mit einem Solver lösbar sein.

Beispiel

3 nichtlineare Gleichungen

(S_ * x_) ^ 2 + S_ * U_ * x_ * z_ + (U_ * z_) ^ 2 - P_ = 0

(S_ * x_) ^ 2 + S_ * T_ * x_ * y_ + (T_ * y_) ^ 2 - Q_ = 0

(T_ + y_) ^ 2 + T_ * U_ * y_ * z_ + (U_ * z_) ^ 2 - R_ = 0

Eingabewerte

P_ = 1
Q_ = 2
R_ = 3
S_ = 1
T_ = 2
U_ = 3

Ergebnisse

x_ = 1.14825552
y_ = -0.789839164
z_ = -0.226545265


--
Gruss Jan C. Hoffmann
http://ourworld.compuserve.com/homepages/MTEC/

[Matthias Noske]

Post by Jan C. Hoffmann
Ergebnisse
x_ = 1.14825552
y_ = -0.789839164
z_ = -0.226545265

Das ist doch schon mal ganz gut. Das Problem ist also für einen "dummen"
Computer lösbar. Ich nehme mal an, es wurde ein Programm wie Maple oder
etwas in der Richtung verwendet? Ich bräuchte allerdings einen/den
Algorithmus, mit dem das Ergebnis bestimmt wurde, damit ich ohne externe
Programme wie Maple die Lösung ermitteln kann.
Oder vielleicht den Namen eines numerischen Verfahrens, mit dem man
derartige Probleme anpackt.
Gruß Matthias

[Jan C. Hoffmann]

Post by Matthias Noske

Post by Jan C. Hoffmann
Ergebnisse
x_ = 1.14825552
y_ = -0.789839164
z_ = -0.226545265

Das ist doch schon mal ganz gut. Das Problem ist also für einen "dummen"
Computer lösbar.

Das kann man auch manuell lösen. Das würde ich aber nicht empfehlen.

Post by Matthias Noske
Ich nehme mal an, es wurde ein Programm wie Maple oder
etwas in der Richtung verwendet? Ich bräuchte allerdings einen/den
Algorithmus, mit dem das Ergebnis bestimmt wurde, damit ich ohne externe
Programme wie Maple die Lösung ermitteln kann.

Siehe hierzu

H.R. Schwarz, Numerische Mathematik, B.G. Teubner Stuttgart
Beispiel 5.10, Seite 215

Post by Matthias Noske
Oder vielleicht den Namen eines numerischen Verfahrens, mit dem man
derartige Probleme anpackt.

Lösungsverfahren: Iterationsalgorithmus nach Newton

Partielles Ableiten und iteratives Lösen eines linearen
Gleichungssystems. Das lineare Gleichungssystem wird nach dem
Eliminationsverfahren nach Gauß gelöst.


--
Gruss Jan C. Hoffmann
http://ourworld.compuserve.com/homepages/MTEC/

[Matthias Noske]

Danke an alle, Problem gelöst.
Der Autor dieser Seite http://www.uni-magdeburg.de/kowalski/newton.htm hat
mich aufs "allgemeine Newtonsche Iterationsverfahren" aufmerksam gemacht.
Das tuts.

Matthias

[Wolfgang Kirschenhofer]

Post by Matthias Noske
Danke an alle, Problem gelöst.
Der Autor dieser Seite http://www.uni-magdeburg.de/kowalski/newton.htm hat
mich aufs "allgemeine Newtonsche Iterationsverfahren" aufmerksam gemacht.
Das tuts.
Matthias

Hallo Matthias !

Zunächst eine Bemerkung:Aufgrund eines Abschreibfehlers von Jan ist
sein Ergebnis falsch,wie du leicht nachprüfen kannst.
Für deine Zwecke ist das Problem ja gelöst.
Trotzdem möchte ich zeigen,daß man durch geschicktes Vereinfachen das
von dir ursprünglich angegebene Gleichungssystem algebraisch lösen kann.
Wir setzen S*x=:u,T*y=:v und U*z=:w .
Das System hat dann folgende Gestalt:

u^2+u*w+w^2=P (1)
u^2+u*v+v^2=Q (2)
v^2+v*w+w^2=R (3)

Aus (1) und (2) folgt w^2-v^2+u*(w-v)=P-Q
und daraus weiter
(u+v+w)*(w-v)=P-Q (4)

Aus (2) und (3) folgt u^-w^2+v*(u-w)=Q-R
und daraus weiter
(u+v+w)*(u-w)=Q-R (5)
Wir haben nun das neue System,bestehend aus den Gleichungen (3),(4)
und (5), welches sich leicht lösen läßt.
Man kommt schließlich auf eine biquadratische Gleichung.
Im allgemeinsten Fall erhält man vier Lösungstripel (x,y,z).
Beim Lösen muß man aber beachten,daß auch P=Q oder P=R oder Q=R sein
kann (triviale Lösungsfälle).
Der schwierigere Fall liegt vor,wenn P,Q,R paarweise verschieden sind.
Rechnet man mit den Werten von Jan,d.h. mit P=1,Q=2,R=3,S=1,T=2,U=3
dann erhält man z.B.: x_1=sqrt(6)/(3*sqrt(3+sqrt(6)))=0.34976508...
y_1=(6+sqrt(6))/(6*sqrt(3+sqrt(6)))=0.60325553168...
z_1=sqrt(3+sqrt(6))/9= 0.259379575...

x_2=-sqrt(6)/(3*sqrt(3-sqrt(6)))= -1.100453416...
y_2=(6-sqrt(6))/(6*sqrt(3-sqrt(6)))= 0.797547969...
z_2=sqrt(3-sqrt(6))/9 = 0.08244042....

Die weiteren zwei Lösungstripel kannst du leicht selbst ermitteln.

Grüße,
Wolfgang Kirschenhofer

[Jan C. Hoffmann]

Post by Wolfgang Kirschenhofer

Post by Matthias Noske
Danke an alle, Problem gelöst.
Der Autor dieser Seite

http://www.uni-magdeburg.de/kowalski/newton.htm hat

Post by Wolfgang Kirschenhofer

Post by Matthias Noske
mich aufs "allgemeine Newtonsche Iterationsverfahren" aufmerksam gemacht.
Das tuts.
Matthias

Hallo Matthias !
Zunächst eine Bemerkung:Aufgrund eines Abschreibfehlers von Jan ist
sein Ergebnis falsch,wie du leicht nachprüfen kannst.

Vergleich der Gleichungen

Post by Wolfgang Kirschenhofer
(S_ * x_) ^ 2 + S_ * U_ * x_ * z_ + (U_ * z_) ^ 2 - P_ = 0
(S_ * x_) ^ 2 + S_ * T_ * x_ * y_ + (T_ * y_) ^ 2 - Q_ = 0
(T_ + y_) ^ 2 + T_ * U_ * y_ * z_ + (U_ * z_) ^ 2 - R_ = 0

(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R

Eingabewerte

P_ = 1.000000
Q_ = 2.000000
R_ = 3.000000
S_ = 1.000000
T_ = 2.000000
U_ = 3.000000

Ergebnisse

x_ = 1.148256
y_ = -0.789839
z_ = -0.226545

Ich kann keinen Übertragungs-/Abschreibfehler erkennen. Die Gleichungen
und Beispieldaten werden bei mir per Programm übertragen.

Kannst Du mir bitte einen weiteren Hinweis geben?


--
Gruss Jan C. Hoffmann
http://ourworld.compuserve.com/homepages/MTEC/

[Matthias Noske]

Eine saubere algebraische Lösung ist mir natürlich auch lieber als etwas
numerisches.

v^2+v*w+w^2=R (3)

...

(u+v+w)*(w-v)=P-Q (4)

...

(u+v+w)*(u-w)=Q-R (5)
Wir haben nun das neue System,bestehend aus den Gleichungen (3),(4)
und (5), welches sich leicht lösen läßt.

Hmm, vielleicht stehe ich gerade auf der Leitung, aber mir ist noch nicht
klar, wie man das lösen kann. Könntest du das noch etwas detaillierter
erklären?

Grüße, Matthias

[Wolfgang Kirschenhofer]

Post by Matthias Noske
Eine saubere algebraische Lösung ist mir natürlich auch lieber als etwas
numerisches.

v^2+v*w+w^2=R (3)

...

(u+v+w)*(w-v)=P-Q (4)

...

(u+v+w)*(u-w)=Q-R (5)
Wir haben nun das neue System,bestehend aus den Gleichungen (3),(4)
und (5), welches sich leicht lösen läßt.

Hmm, vielleicht stehe ich gerade auf der Leitung, aber mir ist noch nicht
klar, wie man das lösen kann. Könntest du das noch etwas detaillierter
erklären?
Grüße, Matthias

Hallo Mathias !

Ich betrachte nur den schwierigeren Fall ,daß P,Q und R paarweise
verschieden sind. Die Feinheiten mit Fallunterscheidungen überlasse
ich dir.Die Rechnung ist zwar aufwendig aber mathematisch trivial.
Ich verwende jetzt zusätzlich noch Gleichung (2).
Dividiert man Gleichung (4) durch Gleichung (5),dann erhält man:
(w-v)/(u-w)=(P-Q)/(Q-R)=:c und daraus folgt sofort
u=(w*(c+1)-v)/c (6)
Aus (6) folgt dann u+v+w=(w*(2*c+1)+v*(c-1))/c .
Setzt man dies in (4) ein,dann erhält man eine Gleichung der Form
v^2*a_1+v*w*b_1+w^2*c_1 = d_1 (7)
Die Gleichung (3) lautet v^2+v*w+w^2=R
Wir multiplizieren nun (7) mit R und (3) mit d_1 und anschließend
subtrahieren wir die eine Gleichung von der anderen und erhalten eine
Gleichung der Form
v^2*a_2+v*w*b_2+w^2*c_2 = 0 .
Diese letzte Gleichung dividieren wir durch v^2 ,falls v^2 ungleich
Null ist (Fallunterscheidungen !) und erhalten die quadratische
Gleichung a_2+t*b_2+t^2*c_2 = 0 (8)
,wobei wir w/v=:t gesetzt haben
(8) hat im allgemeinen zwei Lösungen für t.
Es ist dann w=v*t.Setzt man dies in (6) und dann noch in (2) ein,dann
erhält man eine reinquadratische Gleichung für v und damit hat man im
allgemeinen vier Lösungen für das Tripel (u,v,w) aus denen man wegen
S*x=u,T*y=v und U*z=w dann (x,y,z) erhält.
Wichtig sind natürlich auch die einfachen Fallunterscheidungen.
Ich habe dir nun die wesentlichen Schritte erklärt;das müßte genügen.
Zur Einübung kannst du ja zunächst mit den Werten von Jan rechnen.
Zwei Lösungen habe ich dir ohnehin schon angegeben.Die beiden anderen
erhälts du ja sofort,wenn du beachtest,daß mit (x,y,z) auch (-x,-y,-z)
Lösung des Systems ist.

Grüße,
Wolfgang

[Rudolf Polzer]

Post by Matthias Noske
Hallo,
(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R
Die Großbuchstaben S,T,U,P,Q,R sind bekannte Konstanten; x,y,z sind die
gesuchten Variablen.

Also mal umformen:

(Sx)^2 + (Sx)(Sz) + (Sz)^2 = P
(Sx)^2 + (Sx)(Sy) + (Sy)^2 = Q
(Sy)^2 + (Sy)(Sz) + (Sz)^2 = R

Jetzt erinnert das schon stark an den Kosinussatz für einen Winkel
von 120°. Das Problem wird jetzt ein Geometrisches:


A
\
Ty\
\_______B
/F Uz
Sx/
C

Gesucht sind bei diesen festen Winkeln die Punkte A, B, C mit BC = P,
CA = Q, AB = R.

In anderen Worten: man konstruiere das Dreieck aus den Seitenlängen P,
Q, R und bestimme den Fermat-Punkt F. Danach ist x = FC/S, y = FA/T,
z = FB/U.

Sollte eine der Variablen P, Q, R negativ sein, dann existiert keine
Lösung für das Gleichungssystem, denn a^2 + ab + b^2 liegt für alle a,
b im Intervall [a^2 + b^2, (a+b)^2] oder [(a+b)^2, a^2 + b^2] und beide
Intervallgrenzen sind nicht negativ.

Hat das Dreieck keinen Fermat-Punkt, dann gibt es trotzdem noch eine
Lösung mit einem negativen Sx, Ty oder Uz. Die Gleichungen müssten die
Gleichen sein. Allerdings muss man dann die "Richtige" der Entfernungen
negativ zählen.

Wie man die Formeln am Ende in erträgliche Längen bekommt, sehe ich jetzt
zwar nicht, aber das sollte zumindest ausreichen, um überhaupt zu einer
Lösung zu kommen.

[Rainer Lachner]

Post by Matthias Noske
Hallo,
(I) (Sx)^2+SUxz+(Uz)^2=P
(II) (Sx)^2+STxy+(Ty)^2=Q
(III) (Ty)^2+TUyz+(Uz)^2=R

Hi,

den Hinweis auf das Newtonverfahren hast Du ja schon bekommen.

Allerdings: Falls mehrere Lösungen (x,y,z) existieren (das ist der
Regelfall!) liefert Dir das Newtonverfahren abhängig vom Startwert mal
die eine und mal die andere. Die "Einzugsbereiche" (Menge aller
Startwerte, die zu einer bestimmten Lösung konvergieren) sind in der
Regel Fraktale.

Schau Dir mal
http://citeseer.nj.nec.com/226752.html
an, falls Dich etwas Theorie nicht schreckt. Dort wird ein
Lösungsverfahren für ein entspechendes Problem angegeben - allerdings
nur zwei polynomiale Gleichungen in zwei Unbekannten.

Vielleicht kann man das auf drei Gleichungen übertragen.