Polynomdivision, weiß nich was ich falschmache

Uederli

Hallo,

ich habe ein Problem mit meinen Programm, das kubische Gleichungen mit Polynomdivision löst.
Die Ausgangsgleichung ist von dieser Struktur: a*x^3 + b*x^2+ c*x +d = 0
Hier erst mal der entscheidende Teil des Quellcodes:

for ( double loop_pol = -1000; loop_pol < 0; loop_pol += 0.001)
{								   
pol = loop_pol;							
if( a*pol*pol*pol + b*pol*pol + c*pol + d == 0)
{
x1 = pol;

double p = (b+x1*a)/a;
double q = (c+x1*b+x1*x1*a)/a;
x2 = -(p/2)+ sqrt(((p*p)/4)-q);					    
x3 = -(p/2)- sqrt(((p*p)/4)-q);

 cout << "\n x1 = " << x1;      					   
cout << "\n x2 = " << x2;						 
 cout << "\n x3 = " << x3; 
}	   
}

Wenn ich die folgende Zeile so umschreibe, dann funktioniert es aber nur, wenn die 1.Lösung der Gleichung(x1) eine Ganze Zahl ist:

for ( double loop_pol = -1000; loop_pol < 0; loop_pol += 1)

Mein Problem ist, dass nach der 1.Variante (also mit loop_pol += 0.001) das Programm nicht funktioniert.

Wenn die zu lösende Gleichung z.B. 1*x^3 + 6*x^2 + 3*x - 10 ist (Lösungen -5;1;-2):
Irgendwann muss pol nach beiden Varianten bei -5 ankommen. Zu Beginn ist pol noch -1000. Nach Variante 1 wird immer 0,001 dazu addiert, bei Variante 2 immer 1.
Wenn pol -5 ist, ist bei diesem Beispiel die Bedingung if( a*pol*pol*pol + b*pol*pol + c*pol + d == 0) erfüllt und die anderen x Werte werden berechnet. Leider klappt das aber nur bei Variante 2 und bei Variante 1 nicht. Weiß jemand warum?

vielen Dank für die Antworten schon mal im Voraus

Ad aCTa

Nur mal so eine Behauptung: Wäre es nicht wesentlich effizienter in einem Programm statt Polynomdivision das Newton-Verfahren zu nutzen?

Uederli

das kann sein, aber ich weiß nich wie das Newton-Verfahren funktioniert.

knivil

Wenn ich die folgende Zeile so umschreibe, dann funktioniert es aber nur, wenn die 1.Lösung der Gleichung(x1) eine Ganze Zahl ist:

Wie du siehst ist dein Algorithmus fuer den Normalfall nicht geeignet. Auch funktioniert dein Ansatz nur, wenn das Polynom sich als Produkt von zwei Polynomen darstellen laesst. Was selten der Fall ist.

das kann sein, aber ich weiß nich wie das Newton-Verfahren funktioniert.

Dann wirst du wohl dumm sterben ... schon mal google benutzt?

Und ueberhaupt, warum verwendest du nicht die Loesungsformel fuer Polynome dritten Grades?

Uederli

Wie du siehst ist dein Algorithmus fuer den Normalfall nicht geeignet. Auch funktioniert dein Ansatz nur, wenn das Polynom sich als Produkt von zwei Polynomen darstellen laesst. Was selten der Fall ist.

Also ich dachte duch Polynomdivision bekommt man alle Lösungen von einer kubischen Gleichung.
Und ich wollte ja wissen warum das Programm nur funktionerit wenn ich ganze Zahlen auf die Variabe pol addiere, und nichi bei gebrochenen, was ja rein logisch funktionieren müsste.

Ich wusste auch nicht dass es eine Lösungsformel für Polynome 3.Grades gibt.
Und ich finde dzau auch nur das hier :

Für Polynome dritten Grades und höher existieren keine Formeln, mit denen wir direkt die Nullstellen berechnen können. Wir müssen zunächst versuchen, den Grad durch Faktorisieren zu verkleinern

von: mathematik-wissen.de

und den Grad der Gleichung verkleinere ich ja duch die Polynomdivision, dazu muss ja eine Lösung ausprobiert werden. Da liegt dann das Problem, das es komischerweise nur mit ganzen Zahlen klappt und ich weiß nich warum

Bashar

knivil schrieb:

Wie du siehst ist dein Algorithmus fuer den Normalfall nicht geeignet. Auch funktioniert dein Ansatz nur, wenn das Polynom sich als Produkt von zwei Polynomen darstellen laesst. Was selten der Fall ist.

Was meinst du damit? Über IR ist jedes Polynom vom Grade 3 oder höher faktorisierbar. Und da man die Nullstellen von Polynomen 1. und 2. Grades leicht findet, ist es ein absolut gangbarer Weg, sich für Polynome 3. Grades auf irgendeinem Wege eine Nullstelle zu verschaffen und dann den Grad zu reduzieren.

Und ueberhaupt, warum verwendest du nicht die Loesungsformel fuer Polynome dritten Grades?

Vermutlich, weil sie ziemlich umständlich ist.

knivil

Hier sehr ausfuehrlich: http://www.mathe.tu-freiberg.de/~hebisch/seminar1/kubik.html oder http://de.wikipedia.org/wiki/Cardanische_Formeln oder http://de.wikipedia.org/wiki/Kubische_Gleichung . Loesungsformeln existieren fuer Polynome bis zum Grad 4.

Über IR ist jedes Polynom vom Grade 3 oder höher faktorisierbar.

Ich nehme mal an, dass mit IR die komplexen Zahlen gemeint sind. Aber ich sehe in dem Codefragment keine komplexen Zahlen.

Vermutlich, weil sie ziemlich umständlich ist.

Die Loesungsformeln sind schon so einfach wie moeglich.

Uederli

Ok, es gibt also bessere Verfahren, um eine kubische Gleichung zu lösen.
Aber ich weiß jetzt nicht, warum meine Lösung nicht sinnfoll ist/nicht funktioniert. wäre nett, wenn mir das jemand erklären könnte

knivil

... weil durch die Verwendung von double und das sukkessive Addieren von 0.0...01 Ungenauigkeiten entstehen. 0.1 ist nicht exakt als Fliesskommazahl darstellbar. Ist nun deine NST exakt -1 so wirst du sie nie mit deiner for-Schleife exakt treffen. D.h. die Bedingung

if( a*pol*pol*pol + b*pol*pol + c*pol + d == 0)

wird nie erfuellt.

Uederli

aber wenn ich immer 0,...01 dazuaddiere müsste doch pol auch immer imergentwann z.b -1 werden ,oder nicht?
Ich verstehe das nicht so ganz mit der Fliesskommazahl.

knivil

Das ist etwa so wie mit dem Bruch 1/3. In dezimaler Schreibweise ist der 0.33333..., aber wir koennen ihn nicht mit unendlich vielen Nachkommastellen aufschreiben und brechen z.B. nach der 5-ten Stelle ab. Jetzt ist natuerlich 1/3 + 1/3 + 1/3 gleich 1, aber 0.33333 + 0.33333 + 0.33333 ist eben nicht exakt 1. Das gleiche passiert dem Computer. Intern werden Zahlen im Binaerformat dargestellt. 0.1 (oder 0.01 oder 0.001 oder ...) sind nicht exakt darstellbar, genauso wie 1/3 im Dezimalsystem. Dadurch ergeben sich Ungenauigkeiten beim Addieren und die exakte Loesung wird nicht getroffen.

Uederli

achso das is dann im binarsystem keine exakte Zahl

Michael E.

knivil schrieb:

Über IR ist jedes Polynom vom Grade 3 oder höher faktorisierbar.

Ich nehme mal an, dass mit IR die komplexen Zahlen gemeint sind. Aber ich sehe in dem Codefragment keine komplexen Zahlen.

Er meint sicherlich die reellen Zahlen.

[Edit] War Müll.

Bashar

knivil schrieb:

Über IR ist jedes Polynom vom Grade 3 oder höher faktorisierbar.

Ich nehme mal an, dass mit IR die komplexen Zahlen gemeint sind.

Du hast mit Mathematik nicht so viel am Hut, oder? IR steht für den Körper der reellen Zahlen.

Vermutlich, weil sie ziemlich umständlich ist.

Die Loesungsformeln sind schon so einfach wie moeglich.

Aber vielleicht nicht einfach genug.

knivil

Bashar schrieb:

Du hast mit Mathematik nicht so viel am Hut, oder?

Doch schon, aber du hast geschrieben:

Grade 3 oder höher

Und ich ueberlege mir ein Polynom 4-ten Grades, das nicht faktorisierbar ist ... Ich habe komplexe Zahlen nur vermutet, weil es bestimmt ein Polynom 4-ten Grades gibt, dass keine reeelen Nullstellen hat.

Uederli

Gibt es denn im binarsystem eine exakte Zahl, die kleiner als eins ist und duch multiplikation zu eins ergänzt werden kann?

knivil

2 und alle Potenzen (...-2,1,0,1,2 ...).

Uederli

also geht mein Ansatz nur für ganze Zahlen, weil bei dem Computer z.b. 0.1*10 nicht exakt 1 ist?

Bashar

knivil schrieb:

Und ich ueberlege mir ein Polynom 4-ten Grades, das nicht faktorisierbar ist ...

Ja, x^4 + x^2 + 1 ist nicht in Linearfaktoren zerlegbar, gähn. Das hab ich aber auch nicht behauptet, also spar dir deine Energie und schlag lieber den Satz nach, der besagt, dass irreduzible Polynome über IR den Höchstgrad 2 haben.

Uederli

also geht mein Ansatz nur für ganze Zahlen, weil bei dem Computer z.b. 0.1*10 nicht exakt 1 ist?
aber dann müsste doch folgendes funktionieren:

if( aa*pol*pol*pol + bb*pol*pol + cc*pol + dd > -0.01 && aa*pol*pol*pol + bb*pol*pol + cc*pol + dd< 0.01)

leider funktioniet das auch nicht.
Das kann auch nicht daran liegen, dass die Abweichung höher als 0.01 ist weil das folgende funktioniert auch nicht:

if( aa*pol*pol*pol + bb*pol*pol + cc*pol + dd > -1 && aa*pol*pol*pol + bb*pol*pol + cc*pol + dd< 1)

zudem habe ich auch mal folgendes eingefügt:

pol = loop_pol;							
 cout << " " <<  pol;
if( aa*pol*pol*pol + bb*pol*pol + cc*pol + dd > -1 && aa*pol*pol*pol + bb*pol*pol + cc*pol + dd< 1)

in der Ausgabe werden dann aber auch ganze Zahlen angezeigt. Somit müssten auch ganze Zahlen als nullstellen erkannt werden.

Ist das jetzt doch nen andreres problen?