Nullstellen mehrerer Variable < mehrere Veränderl. < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:11 Mi 22.08.2007 | | Autor: | Mumrel |
Hallo,
ich wollte mal fragen, welche gängigen Verfahren (numerisch/algebraisch) es gibt um die Nullstellen einer Funktoin mehrerer Variablen (f: [mm] \IR^n [/mm] -> [mm] \IR) [/mm] berechnen.
Also ich erwarte natürlich keine ellenlangen Vortröge, aber so Name die grundlegende Idee und Schlagworte aus dem Kontext wären schön :).
Also das einzig mir bekannte ist dass Auflösen und Einsetzten, sowie das geschickte Addieren, multiplizieren etc.
Aber wirklich algorithmisch kommt man da ja meines Wissens nicht weit, ich weiß auch nicht ob man damit überhaupt ale denkbaren Fragestellugnen lösen kann.
Grüße Mumrel
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:28 Mi 22.08.2007 | | Autor: | Mumrel |
Oh, falls die Variablen nur linear auftreten kann man natürlich ein LGS noch anwenden.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:05 Do 23.08.2007 | | Autor: | moody |
Koeffizientenmatrizen vll.?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:49 Do 23.08.2007 | | Autor: | rainerS |
Hallo Mumrel,
> ich wollte mal fragen, welche gängigen Verfahren
> (numerisch/algebraisch) es gibt um die Nullstellen einer
> Funktoin mehrerer Variablen (f: [mm]\IR^n[/mm] -> [mm]\IR)[/mm] berechnen.
Meinst du wirklich eine Funktion [mm]f: \IR^n \rightarrow\IR[/mm] oder allgemein [mm]f: \IR^n \rightarrow\IR^m[/mm]?
Du hast nämlich in deiner Mitteilung von einem linearen Gleichungssystem geschrieben, und das bedeutet ja, dass du mehr als eine Gleichung hast, also [mm]m>1[/mm].
Nimm zum Beispiel die Funktion [mm]f: \IR^2 \rightarrow\IR[/mm], [mm] f(x,y) = x^2+y^2-1 [/mm]. Die hat alle Punkte auf dem Einheitskreis als Nullstellen. Nimmst du eine zweite Gleichung, zum Beispiel [mm]g(x,y) =x+y =0[/mm] hinzu, hast du einzelne Lösungspunkte, die du einfach ausrechnen kannst.
Allgemein kann man bei solchen Gleichungssystemen mit Polynomen noch recht gut die Lösungen bestimmen. Hast du zum Beispiel zwei Polynome [mm]p(x,y)=0,q(x,y)=0[/mm], kannst du [mm]p(x,y)[/mm] als Polynom in x mit Parameter y ansehen und im Prinzip dessen Nullstellen bestimmen. Diese [mm]x_i(y)[/mm] setzt du dann in q ein: [mm]q(x_i(y),y)=0[/mm], sodass du nur noch eine Gleichung in einer Unbekannten hast. Das Spiel kann man für mehrere Variablen entsprechend erweitern.
Das hat zwei große Nachteile: 1. enthält schon die Gleichung [mm]q(x_i(y),y)=0[/mm] in der Regel unangenehme Wurzelausdrücke, und 2. gibt es für Polynome ab dem 5. Grad keine allgemeine Formel für die Nullstellen.
Es gibt allerdings Algorithmen, mit denen man in vielen Fällen sehr weit kommt. Durch Berechnung einer Groebnerbasis kann man in vielen Fällen solche polynomialen Gleichungssysteme durch einfachere ersetzen. Dabei ergibt sich, wenn man Glück hat, eine Art Dreiecksform:[mm]p_1(x_1,x_2,x_3)=0, p_2(x_2,x_3)=0, p_3(x_3)=0[/mm]. Sind die einzelnen Polynome nicht allzu kompliziert, kann man zuerst die letzte Gleichung lösen, in die vorletzte einsetzen, diese lösen, und so weiter.
Ganze Klassen anderer Funktionen lassen sich auf Polynome zurückführen, insbesondere algebraische und trigonometrische Ausdrücke. Enthält die Gleichung einen Wurzelterm [mm]\sqrt{r(x,y)}[/mm], so ersetzt man den durch eine neue Variable u und fügt die Gleichung [mm]u^2 - r(x,y)=0[/mm] hinzu. Das macht man so lange, bis alle Wurzelterme ersetzt sind und hat damit nur noch Polynome.
Ähnlich bei trigonometrischen Ausdrücken: zunächst werden alle trigonometrischen Funktionen durch Sinus und Cosinus einer Variablen ausgedrückt, sagen wir [mm]\sin(\phi)[/mm] und [mm]\cos(\phi)[/mm]. Dann ersetzt man diese durch neue Variablen u und v und fügt [mm]u^2+v^2-1=0[/mm] hinzu. Wieder nur noch Polynome.
Das geht aber nur, wenn das [mm]\phi[/mm] nur in den Winkelfunktionen vorkommt. Eine Gleichung wie [mm]\cos(\phi)-\phi=0[/mm] kann man damit nicht lösen.
Und damit bin ich auch schon bei den vielen Gleichungen, für die es keine einfachen Lösungswege gibt. Da bleibt einem häufig nur die numerische Approximation, sieh zum Beispiel ![[]](/images/popup.gif) hier in der Wikipedia.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:00 Fr 24.08.2007 | | Autor: | Mumrel |
Hallo Rainer,
wow, danke schon mal für die EInblicke. Ich kommentiere deinen Text einfach mal mit dem was mir dazu gerade durch den Kopf schwirrt.
> Meinst du wirklich eine Funktion [mm]f: \IR^n \rightarrow\IR[/mm]
> oder allgemein [mm]f: \IR^n \rightarrow\IR^m[/mm]?
Interessieren würde mich beides. Aber du hast Recht die Frage ist nich klar gestellt. Mir gehts im wesentlichen drum einen Überblick für alle Fälle zu bekommen Also n, m [mm] \in \IN.
[/mm]
Für n=m=1 kommt dann natürlich noch Newton, sowie die algebraischen Lösungsverfahren hinzu.
Und kann man n=1 m>1 nicht dadurch lösen, dass man die Nullstellen jeder Komponenten vereinigt.
> Nimm zum Beispiel die Funktion [mm]f: \IR^2 \rightarrow\IR[/mm],
> [mm]f(x,y) = x^2+y^2-1 [/mm]. Die hat alle Punkte auf dem
> Einheitskreis als Nullstellen. Nimmst du eine zweite
> Gleichung, zum Beispiel [mm]g(x,y) =x+y =0[/mm] hinzu, hast du
> einzelne Lösungspunkte, die du einfach ausrechnen kannst.
Das würde ich jetzt über Auflösen von 2 und einsetzten in 1 machen.
Ein ähnliches Problem war wohl auch der Anstoß zu dieser Frage.
Manchmal sitz ich an meinen Übungsaufagebn und brauche eine Zeit bis ich das habe (also jetzt nicht gerade das Bsp von oben). Und da habe ich mich halt gefragt wie man das im Reallife macht. Denn die Übungsaufagben sind ja meistens noch einigermaßen schön, aber falls man die Problemgröße etwas hochschraubt kann ich mir schon vorstellen, dass man das nicht mehr von Hand machen will/kann.
> Allgemein kann man bei solchen Gleichungssystemen mit
> Polynomen noch recht gut die Lösungen bestimmen. Hast du
> zum Beispiel zwei Polynome [mm]p(x,y)=0,q(x,y)=0[/mm], kannst du
> [mm]p(x,y)[/mm] als Polynom in x mit Parameter y ansehen und im
> Prinzip dessen Nullstellen bestimmen. Diese [mm]x_i(y)[/mm] setzt du
> dann in q ein: [mm]q(x_i(y),y)=0[/mm], sodass du nur noch eine
> Gleichung in einer Unbekannten hast. Das Spiel kann man für
> mehrere Variablen entsprechend erweitern.
Das ist interessant.
> Das hat zwei große Nachteile: 1. enthält schon die
> Gleichung [mm]q(x_i(y),y)=0[/mm] in der Regel unangenehme
> Wurzelausdrücke, und 2. gibt es für Polynome ab dem 5. Grad
> keine allgemeine Formel für die Nullstellen.
Ok, d,h, bis Grad 4 kann man wenn man symbolisch rechnen kann (bzw. der PC) die NST also exakt bestimmen, richtig?
> Es gibt allerdings Algorithmen, mit denen man in vielen
> Fällen sehr weit kommt. Durch Berechnung einer
> Groebnerbasis kann man in vielen Fällen solche polynomialen
> Gleichungssysteme durch einfachere ersetzen. Dabei ergibt
> sich, wenn man Glück hat, eine Art
> Dreiecksform:[mm]p_1(x_1,x_2,x_3)=0, p_2(x_2,x_3)=0, p_3(x_3)=0[/mm].
Wenn da nicht irgendwo Lineare Algebra drin steckt ;)?
> Ganze Klassen anderer Funktionen lassen sich auf Polynome
> zurückführen, insbesondere algebraische und
> trigonometrische Ausdrücke. Enthält die Gleichung einen
> Wurzelterm [mm]\sqrt{r(x,y)}[/mm], so ersetzt man den durch eine
> neue Variable u und fügt die Gleichung [mm]u^2 - r(x,y)=0[/mm]
> hinzu.
Das erinnert mich an die Nährungsweise Berechnung Wurzeln über die Nullstellen und mit dem Newton Verfahren. Da macht man ja genau den gleichen Ansatz.
>Das macht man so lange, bis alle Wurzelterme ersetzt
> sind und hat damit nur noch Polynome.
Auch interessant. Erinnert mich daran, wie oft man versucht Probleme auf andere Probleme zu reduzieren. Mir ist das im ersten Semester in Logik begegnet. Kann man Entscheidbarkeit effizient lösen kann man Äquivalenz lösen etc. Irgendwie erinnert mich das an diese Technik.
> Ähnlich bei trigonometrischen Ausdrücken: zunächst werden
> alle trigonometrischen Funktionen durch Sinus und Cosinus
> einer Variablen ausgedrückt, sagen wir [mm]\sin(\phi)[/mm] und
> [mm]\cos(\phi)[/mm]. Dann ersetzt man diese durch neue Variablen u
> und v und fügt [mm]u^2+v^2-1=0[/mm] hinzu. Wieder nur noch
> Polynome.
Aber da macht man dann schon Fehler, oder? Zumindest scheint mir das ja nicht eine äquvalente Charakterisierung d. sin/cos zu sein?
Du sagtest oben dass bei Polynomen vom Grad 5 (inklusive, exlusive?) Schluss ist.
Darf man prunzipiell erwarten, dass in der Zukunft Verfahren entwickelt werden könnten die das Problem für höhrere Polynome lösen? Oder gibt es da (Nicht)Extistenzbeweise, die Nachweisen, dass dies oder jenes nicht sein kann?
Wird auf dem Gebiet was getan, oder sind die Nährungsverfahren so gut, dass man sich zufrieden gibt?
Also nochmal danke für deinen wirklich informativen Text!![[ok]](/images/smileys/ok.gif "[ok]")
Weißt du genausoviel auch über Nullstellen vektorwertiger Fnktionen ;)? Das einzige was ich dazu weiß, ist, dass es anscheinend ein Newton Verfahren fürs mehrdim gibt. Aber da wars dann auch schon.
Grüße Mumrel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:16 Fr 24.08.2007 | | Autor: | rainerS |
Hallo Mumrel,
> Für n=m=1 kommt dann natürlich noch Newton, sowie die
> algebraischen Lösungsverfahren hinzu.
Der Newton geht auch in höheren Dimensionen.
> Ok, d,h, bis Grad 4 kann man wenn man symbolisch rechnen
> kann (bzw. der PC) die NST also exakt bestimmen, richtig?
Richtig. Allerdings sind die Formeln alles andere als schön. Ab Grad 5 geht es nur manchmal.
> > Es gibt allerdings Algorithmen, mit denen man in vielen
> > Fällen sehr weit kommt. Durch Berechnung einer
> > Groebnerbasis kann man in vielen Fällen solche polynomialen
> > Gleichungssysteme durch einfachere ersetzen. Dabei ergibt
> > sich, wenn man Glück hat, eine Art
> > Dreiecksform:[mm]p_1(x_1,x_2,x_3)=0, p_2(x_2,x_3)=0, p_3(x_3)=0[/mm].
> Wenn da nicht irgendwo Lineare Algebra drin steckt ;)?
Eher nichtlineare Algebra. Die Polynome bilden einen Ring, das Gleichungssystem definiert ein Ideal. Man versucht eine möglichst einfache Darstellung dieses Ideals zu finden.
> > Ähnlich bei trigonometrischen Ausdrücken: zunächst werden
> > alle trigonometrischen Funktionen durch Sinus und Cosinus
> > einer Variablen ausgedrückt, sagen wir [mm]\sin(\phi)[/mm] und
> > [mm]\cos(\phi)[/mm]. Dann ersetzt man diese durch neue Variablen u
> > und v und fügt [mm]u^2+v^2-1=0[/mm] hinzu. Wieder nur noch
> > Polynome.
> Aber da macht man dann schon Fehler, oder? Zumindest
> scheint mir das ja nicht eine äquvalente Charakterisierung
> d. sin/cos zu sein?
Doch, das ist äquivalent. [mm]\sin^2+\cos^2=1[/mm] ist ja exakt und überall gültig.
> Du sagtest oben dass bei Polynomen vom Grad 5 (inklusive,
> exlusive?) Schluss ist.
> Darf man prunzipiell erwarten, dass in der Zukunft
> Verfahren entwickelt werden könnten die das Problem für
> höhrere Polynome lösen? Oder gibt es da
> (Nicht)Extistenzbeweise, die Nachweisen, dass dies oder
> jenes nicht sein kann?
Ja, die Galoistheorie beschäftigt sich damit. Es gibt keine allgemeine Darstellung der Nullstellen eines Polynoms vom Grade 5 oder mehr durch Radikale (Wurzelausdrücke). Das geht nur für Spezialfälle, zum Beispiel [mm]x^5-2=0[/mm].
> Weißt du genausoviel auch über Nullstellen vektorwertiger
> Fnktionen ;)?
Du kannst jedes Gleichungssystem als vektorwertige Funktion f=0 auffassen.
> Das einzige was ich dazu weiß, ist, dass es
> anscheinend ein Newton Verfahren fürs mehrdim gibt. Aber da
> wars dann auch schon.
Das Newtonverfahren lässt sich direkt übertragen. Schau mal in die Wikipedia-Links, die ich genannt habe.
Grüße
Rainer
|
|
|
|
!
![[lehrer]](/images/smileys/lehrer.gif "[lehrer]"){kind=small}
