Effizientes Finden von Nullstellen

08.07.2013, 09:59	Mr. Gecko	Auf diesen Beitrag antworten »
Effizientes Finden von Nullstellen Hallo zusammen! Ich habe eine Frage zum effizienten finden von Nullstellen bei Polynomen 3. Grades. Könnt ihr mir einen Tip geben, was mir am schnellsten die Lösung liefert? Folgende beiden Verfahren sind mir in den Sinn gekommen: 1. Lösung mit Cardanischen Formeln Ich habe immer die Form $\begin{eqnarray} ax^3+bx^2+cx+d=0 \end{eqnarray}$ und es gibt immer 3 reelle Lösungen, diese Randbedingungen sind fest. Also ist das ganze leicht zu implementieren. 2. Newton-Verfahren Wegen der immer gleichen Form kann ich die Jacobi-Matrix vorher bestimmen. Außerdem weiß ich, dass eine der Nullstellen immer relativ nah an 0 sein wird, d.h. ich hätte einen guten Start-Wert. Die anderen Nullstellen können in einem Bereich von etwa -3000 bis 3000 liegen. Was denkt ihr, 1 oder 2? Danke schonmal! Korrekturen im zweiten Beitrag eingebaut, zweiten Beitrag gelöscht. Steffen
08.07.2013, 17:40	Dopap	Auf diesen Beitrag antworten »
hast du nun konkrete Voraussetzungen, ausser, dass 3 reelle Nullstellen vorliegen? und bei $\begin{eqnarray} x^3+29988x^2+1240000x+10560000=0 \end{eqnarray}$ halten sich die Nullstellen überhaupt nicht an die Vorgaben. Es gibt aber den Satz, dass die Nullstellen im Wesentlichen im Intervall $\begin{eqnarray} -\frac {a_2}{a_3} < x < \frac {a_2}{a_3} \end{eqnarray}$ zu suchen sind. Das kannst du ja mal überprüfen.
08.07.2013, 18:40	thk	Auf diesen Beitrag antworten »
RE: Effizientes Finden von Nullstellen Schneller (vergleichsweise 0,nix) bist du in jedem Fall mit den Cardanischen Formeln, mit denen du auch Exzentriker wie in Dopaps Beispiel erschlagen kannst. Die Genauigkeit kann dann schon mal nachlassen ohne weitere Tricks. I. allg. genauer, aber langsamer und unzuverlässiger ist Newton-Verf.. Es braucht einige Tests des Graphen auf NSt, Aussondern der mehrfach gefundenen... Bei extremen Anstiegen von f (oft bei weit draußen gelegenen) kann schnell eine "übersehen" werden. Daher rate ich zu Variante 1.
08.07.2013, 19:44	Dopap	Auf diesen Beitrag antworten »
ja klar, das kommt halt auch stark auf die Hilfsmittel an. Eine reelle Nst. ist ja auf jeden fall vorhanden, dann noch schnell mit Horner an dieser Stelle ausgewertet und der quadratische Rest ist ermittelt. Cardanische Formeln wüsste ich nicht mal auswendig, und muss man da nicht erst vorher eine Substitution durchführen ?
10.07.2013, 15:07	Mr. G	Auf diesen Beitrag antworten »
Hallo zusammen! Vielen Dank schonmal für die Beteiligung! Vielleicht gehe ich nochmal einen Schritt zurück, um das Problem klarer zu machen: Ich hab eine symmetrische 3x3 Matrix (genauer gesagt einen Spannungstensor aus der Mechanik): $\begin{eqnarray} \underline{\underline{\sigma}} = \begin{pmatrix} \sigma_{xx} & \tau_{xy} & \tau_{xz} \\ & \sigma_{yy} & \tau_{yz}\\ sym & & \sigma_{zz} \end{pmatrix} \end{eqnarray}$ Die numerischen Werte der Spannungen können maximal etwa Werte zwischen -1000 bis 1000 annehmen. Für diesen Tensor möchte ich nun möglichst effizient die Eigenwerte und Eigenvektoren bestimmen, wobei ich bereits vorher weiß, dass einer der Eigenwerte immer relativ nah an der Null ist (für Mechanik-Kenner: Es geht um Spannungen an einer Oberfläche, so dass eine der Hauptspannungen theoretisch immer 0 sein muss. Da die Werte des Tensors aus einer FEM-Berechnung kommen, ist sie jedoch nicht genau gleich Null.) Ein möglicher Algorithmus, um diese Aufgabe zu erledigen, sind die Cardanischen Formeln (der erste Treffer der Googgle-Suche nach "3d hauptspannungen" zeigt diesen Algorithmus). Eine weitere Variante wäre die Nutzung von Newton. Das sind die beiden Möglichkeiten, die mir in den Sinn gekommen sind. Meine Frage ist nun, wie ich das Problem, mit den Informationen, die ich über den Tensor habe am effizientesten lösen kann, da ich dies in einem Programm extrem häufig tun muss. P.S.: Kann es sein, dass die Bestätigungsmail beim anmelden etwas länger dauert? Irgendwie kommt nix an...
13.07.2013, 16:49	thk	Auf diesen Beitrag antworten »
In diesem Fall besteht die Möglichkeit, die symmetrische Matrix numerisch auf Eigenwertgestalt zu transformieren, z.B. mit dem JACOBIschen Rotationsverfahren. Ob das bei mehrfachen EW einwandfrei funktioniert, hab ich nie getestet. Ich hab es mal auf nichtsymm. Probleme erweitert und bin an diesen Fällen gescheitert. Bei 3x3 lässt sich das Problem vllt sogar exeln, hab aber nicht genauer drüber nachgedacht.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »