Ocram7

Aber wenn ich SWIG nutzen will, muss ich das doch auf meinem Server kompilieren. Und das geht doch auch nicht ohne Konsolen-/Shell-Zugriff, oder?

Daran liegt es glaub ich nicht. Ich glaube nämlich, dass ich den Fehler gefunden habe: Nach diesem Algorithmus wird ja der Funktionswert von c, also f© berechnet. Wenn f© > 0 ist, dann wird a=c, ansonsten b=c. Der Wert c soll also den Wert (a, ersetzen, der das gleiche Vorzeichen hat. Dass meine Bisektion manchmal nicht funktioniert, liegt daran, dass a und b die gleichen Vorzeichen haben. Dann kann die Bisektion ja nicht richtig funktionieren, oder? Habt ihr irgendeine Idee, was ich dagegen tun kann? Nein, ich habe schon verstanden, dass es mit einer fertigen Bibliothek viel einfacher und besser wäre. Aber ich habe noch nichts gefunden, was ich nutzen kann. Um z.B. GSL zu installieren, müsste ich einen Befehl in die Konsole eingeben. Ich habe aber keinen Konsolen-Zugriff. Außerdem habe ich ja jetzt den Fehler in der Bisektion gefunden (siehe oben), deshalb hoffe ich noch, dass es vielleicht klappt, wenn der Fehler nicht mehr auftritt.

Natürlich wäre das Horner-Schema besser, aber das würde auch wieder mehr Aufwand bedeuten. Ich müsste ja erst einmal die Gleichungen automatisch ins Horner-Schema umschreiben lassen, das ist ja nicht ganz einfach. Der Newton-Algorithmus ist doch nicht so gut, finde ich. Er braucht erstens viel länger, um eine Nullstelle zu finden. Außerdem - wie flashpixx schon geschrieben hat - funktioniert er nur, wenn der Startwert gut ist. Die Bisektion funktioniert immer. Deshalb habe ich jetzt wieder die Bisektion genommen. Die erste Nullstelle findet das Programm problemlos. Bei der zweiten hängt es sich aber irgendwie auf, es nimmt immer wieder dieselbe Näherung. Wisst ihr, warum das passiert? http://wp1080088.wp029.webpack.hosteurope.de/_3.php Bei deiner Gleichung macht mein Programm irgendwie gar nichts. Ich habe keine Ahnung, warum: http://wp1080088.wp029.webpack.hosteurope.de/_3.php?t=1 <?php error_reporting(E_ALL); function in_gleichung_einsetzen($gleichung, $wert) { $ersatzstring = '('.$wert.')'; $linke_seite = str_replace('x', $ersatzstring, $gleichung); $berechnung_befehl = "\$rechte_seite = ".$linke_seite.";"; eval($berechnung_befehl); return $rechte_seite; } function gleichung_loesen($gleichung, $genaue_stellen=5) { // findet die Nullstellen if ($gleichung[0] == '+') { $gleichung = substr($gleichung, 1); } $nullstelle_in_intervall = FALSE; $genauigkeit = pow(0.1, $genaue_stellen); // INTERVALL WAEHLEN ANFANG $intervall_schritt = 10; $intervall_a = -100; $intervall_b = -99; while ($nullstelle_in_intervall === FALSE && $intervall_schritt >= 0.3125) { // 10*(1/2)^5 = 0.3125 while ($nullstelle_in_intervall === FALSE && $intervall_b < 100) { $intervall_b = $intervall_b+$intervall_schritt; $temp1 = in_gleichung_einsetzen($gleichung, $intervall_a); if ($temp1 === FALSE) { return FALSE; } $temp2 = in_gleichung_einsetzen($gleichung, $intervall_; if ($temp2 === FALSE) { return FALSE; } if (($temp1*$temp2) < 0) { $nullstelle_in_intervall = TRUE; } if (abs($temp1) < $genauigkeit) { return $intervall_a; } if (abs($temp2) < $genauigkeit) { return $intervall_b; } } $intervall_schritt = $intervall_schritt*0.5; } // INTERVALL WAEHLEN ENDE echo '<p>Intervall ['.$intervall_a.', '.$intervall_b.'] für Gleichung '.$gleichung.'</p>'; $rechte_seite = 100; $intervall_c = 0; $gemachte_iterationsschritte = 0; // Abbruchbedingung, damit kein Timeout while (abs($rechte_seite) > $genauigkeit && $gemachte_iterationsschritte < 500) { $letzte_naeherung = $intervall_c; $intervall_c = ($intervall_a+$intervall_b)/2; $rechte_seite = in_gleichung_einsetzen($gleichung, $intervall_c); echo '<li>Näherung '.$intervall_c.'→'.$rechte_seite.' für Gleichung '.$gleichung.'</li>'; if ($rechte_seite !== FALSE) { // INTERVALL ANPASSEN (c ERSETZT ELEMENT[a,b] MIT GLEICHEM VORZEICHEN) ANFANG if ($rechte_seite > 0) { $intervall_a = $intervall_c; } else { $intervall_b = $intervall_c; } // INTERVALL ANPASSEN (c ERSETZT ELEMENT[a,b] MIT GLEICHEM VORZEICHEN) ENDE } $gemachte_iterationsschritte++; } if ($gemachte_iterationsschritte < 500) { $intervall_c = round($intervall_c, 3); // auf 3 Dezimalen runden nullstelle_gefunden($intervall_c, $gleichung); } else { nullstelle_gefunden(FALSE, $gleichung); } } function nullstelle_gefunden($nullstelle, $gleichung) { if ($nullstelle === FALSE) { echo '<p>keine Nullstelle für Gleichung '.$gleichung.'</p>'; } else { echo '<p>Nullstelle '.$nullstelle.' für Gleichung '.$gleichung.'</p>'; $gleichung = '('.$gleichung.')/(x-('.round($nullstelle, 3).'))'; gleichung_loesen($gleichung); } } $gleichung = '(5-x)*(25-x)-11*11'; if (isset($_GET['t'])) { $gleichung = '(((x-10)*x+35)*x-50)*x+24'; } gleichung_loesen($gleichung); ?> [/PHP]

@flashpixx: Ich versuche jetzt mal, die GNU Scientific Library (GSL) in PHP einzubinden. @AndiE: Ich weiß jetzt leider nicht, ob das wirklich stimmt mit der Schleifen-Theorie. Wenn es nur für quadratische Gleichungen gilt, bringt es mir natürlich nichts. Ansonsten wäre das aber sehr nützlich. Ich habs jetzt noch mal mit dem Newton-Algorithmus versucht: Beispiel-Rechnung mit 4 Nullstellen Leider muss ich angeben, wie viele Nullstellen es gibt, damit mein Programm funktioniert. Ansonsten gibt es nämlich ein Timeout. Geht das auch, ohne die Anzahl der Nullstellen anzugeben? <?php error_reporting(E_ALL); function in_gleichung_einsetzen($gleichung, $wert) { $ersatzstring = '('.$wert.')'; $linke_seite = str_replace('x', $ersatzstring, $gleichung); $berechnung_befehl = "\$rechte_seite = ".$linke_seite.";"; $rueckmeldung = eval($berechnung_befehl); if ($rueckmeldung === FALSE) { return FALSE; } return $rechte_seite; } function funktionswert_der_ableitung($gleichung, $wert) { $zweiter_punkt = $wert+0.00001; $f1 = in_gleichung_einsetzen($gleichung, $wert); if ($f1 === FALSE) { return FALSE; } $f2 = in_gleichung_einsetzen($gleichung, $zweiter_punkt); if ($f2 === FALSE) { return FALSE; } $ableitung = ($f1-$f2)/($wert-$zweiter_punkt); return $ableitung; } function gleichung_loesen($gleichung, $genaue_stellen=5) { // findet die Nullstellen if ($gleichung[0] == '+') { $gleichung = substr($gleichung, 1); } $nullstelle_in_intervall = FALSE; $genauigkeit = pow(0.1, $genaue_stellen); $proben = 0; $intervall_schritt = 10; $intervall_a = -1000; $intervall_b = -999; while ($nullstelle_in_intervall == FALSE && $proben < 50000) { while ($intervall_b <= 1000) { $intervall_b = $intervall_b+$intervall_schritt; if ($intervall_a > $intervall_ { continue; } $temp1 = in_gleichung_einsetzen($gleichung, $intervall_a); if ($temp1 === FALSE) { return FALSE; } $temp2 = in_gleichung_einsetzen($gleichung, $intervall_; if ($temp2 === FALSE) { return FALSE; } if (($temp1*$temp2) < 0) { $nullstelle_in_intervall = TRUE; } if (abs($temp1) < $genauigkeit) { return $intervall_a; } if (abs($temp2) < $genauigkeit) { return $intervall_b; } $proben++; } $intervall_schritt = $intervall_schritt/2; } $gemachte_iterationsschritte = 0; // Abbruchbedingung, damit kein Timeout $naeherung = ($intervall_a+$intervall_b)/2; $abbruch = FALSE; while ($abbruch == FALSE && $gemachte_iterationsschritte < 50000) { $f1 = in_gleichung_einsetzen($gleichung, $naeherung); if ($f1 === FALSE) { return FALSE; } $f2 = funktionswert_der_ableitung($gleichung, $naeherung); if ($f2 === FALSE) { return FALSE; } $alte_naeherung = $naeherung; if ($f2 == 0) { return FALSE; } $naeherung = $naeherung-($f1/$f2); echo '<li>'.$naeherung.'</li>'; if (abs($alte_naeherung-$naeherung) < 0.00001) { $abbruch = TRUE; } $gemachte_iterationsschritte++; } if ($naeherung == (($intervall_a+$intervall_b)/2)) { return FALSE; } return $naeherung; } $gleichung = 'pow((x-1),2)-1.5'; $gleichung = '(5-x)*(25-x)-11*11'; $gleichung = '(20-x)*pow((-1), (1+1))*+(10-x)*pow((-1), (1+1))*(0-x)*(0-x)-0*0+0*pow((-1), (1+2))*0*(0-x)-0*0+0*pow((-1), (1+3))*0*0-0*(0-x)+14*pow((-1), (1+2))*+14*pow((-1), (1+1))*(0-x)*(0-x)-0*0+0*pow((-1), (1+2))*0*(0-x)-0*0+0*pow((-1), (1+3))*0*0-0*(0-x)+0*pow((-1), (1+3))*+14*pow((-1), (1+1))*0*(0-x)-0*0+(10-x)*pow((-1), (1+2))*0*(0-x)-0*0+0*pow((-1), (1+3))*0+0*pow((-1), (1+4))*+14*pow((-1), (1+1))*0*0-0*(0-x)+(10-x)*pow((-1), (1+2))*0*0-0*(0-x)+0*pow((-1), (1+3))*0'; $hoechster_exponent = 4; echo '<h1>'.$gleichung.'</h1>'; $weitere_nullstelle_gefunden = TRUE; $gefundene_nullstellen = 0; while ($gefundene_nullstellen < $hoechster_exponent) { $weitere_nullstelle_gefunden = gleichung_loesen($gleichung); if ($weitere_nullstelle_gefunden !== FALSE) { echo '<p>'.round($weitere_nullstelle_gefunden, 5).'</p>'; $gleichung = '('.$gleichung.')/(x-('.$weitere_nullstelle_gefunden.'))'; } $gefundene_nullstellen++; } ?> [/PHP]

Eine allerletzte Frage habe ich noch, ich möchte nur noch wissen, ob ich das jetzt alles richtig verstanden habe. Also: Mit dem Newton-Verfahren kann man alle reellen Nullstellen finden. Wenn mir also die reellen Nullstellen reichen, ist der Newton dafür perfekt. Mit der Bisektion ist das etwas komplizierter, aber auch möglich. Wenn ich aber auch komplexe Nullstellen finden möchte, dann sollte ich besser externe Programme wie Matlab einbinden. Ist das alles richtig?

Danke, stimmt genau. Ich möchte Polynome lösen. Und mein Programm soll auch ohne Benutzereingaben zurecht kommen. Also muss es auch ohne Intervallgrenzen als Input auskommen. Die müsste es schon selbst finden. Matlab könnte ich in PHP höchstens nutzen, indem ich PHP die Gleichung / Rechenanweisungen in eine Datei schreiben lasse, dann mit passthru() Matlab starte, Matlab die Ergebnisse in eine Datei schreibt und PHP diese wieder ausliest. Das wäre relativ kompliziert und langsam. Meint ihr denn jetzt, dass diese Methode mit der Bisektion funktionieren würde? Wir nehmen an, dass f(x) = 2x mehrere Nullstellen hätte, und zwar -5, 0 und 3. 1) 2x = 0 wird gesetzt. 2) Die Bisektion findet die Nullstelle -5. 3) Wir ändern die Funktion zu: (2x)/(x-(-5)) = 0 4) Nun kann -5 nicht mehr eingesetzt werden, da man nicht durch 0 teilen darf. 5) Der Algorithmus findet automatisch die nächste Nullstelle: 0 (und später 3). Ansonsten käme wohl nur der Newton in Frage, und da habe ich ja noch keine Idee, wie das gehen könnte.

OK, war wohl ein dummes Beispiel. Ich würde gerne das Newton-Verfahren einsetzen oder das Brent-Verfahren. Ich habe auch schon Hunderte Seiten darüber gelesen, aber ich verstehe die Verfahren nicht ganz. Ich wüsste jetzt nicht, wie ich in meinem Beispiel konkret mit den beiden Verfahren umgehen müsste. Beim Newton braucht man ja z.B. eine Ableitung, die ist schwer zu finden, wenn man eine generelle Lösung für alle Gleichungen sucht. Newton-Verfahren Brent-Verfahren ? Wikipedia Super, danke für den Hinweis! Den kleinen Fehler hätte ich ja nie gefunden ... Ich werde es also so ändern: Die Funktion nimmt a = -1000 und sucht dann im Intervall 1 immer weiter einen b-Wert, für den das Produkt f(a)*f( < 0 wäre (d.h. es gibt Nullstellen dazwischen). Wenn bis +1000 kein geeigneter b-Wert gefunden wurde, geht es wieder bei a = -1000 los, dieses Mal im Intervall 0,5 usw. Der Tipp ist gut, werde ich so machen. Aber: Ich habe hier mal -1000 und +1000 genommen. Kann man das einfach so machen? Wenn ich 1000 nehme, kann es passieren, dass die Nullstelle bei 2000 liegt. Nehme ich aber z.B. 3000, dann ist der Aufwand viel höher, oder? Was wäre da am besten? Siehe oberer Teil meiner Antwort. + Bisektion ist doch ein bekanntes Verfahren, oder? Newton würde ich gerne nutzen, hab aber ja oben schon geschreiben, warum ich es (noch) nicht tue. #### Was sagt ihr denn zu der Idee, dass man immer durch eine gefundene Nullstelle teilt und dann so die nächste findet? Beispiel: Wir nehmen an, dass f(x) = 2x mehrere Nullstellen hätte, und zwar -5, 0 und 3. 1) 2x = 0 wird gesetzt. 2) Die Bisektion findet die Nullstelle -5. 3) Wir ändern die Funktion zu: (2x)/(x-(-5)) = 0 4) Nun kann -5 nicht mehr eingesetzt werden, da man nicht durch 0 teilen darf. 5) Der Algorithmus findet automatisch die nächste Nullstelle: 0 (und später 3). Das müsste doch gehen, oder?

Mein Algorithmus mit dem Rest der Testdatei: <?php function in_gleichung_einsetzen($gleichung, $wert) { $ersatzstring = '('.$wert.')'; $linke_seite = str_replace('x', $ersatzstring, $gleichung); $berechnung_befehl = "\$rechte_seite = ".$linke_seite.";"; $rueckmeldung = eval($berechnung_befehl); //if ($rueckmeldung == FALSE) { return FALSE; } return $rechte_seite; } function gleichung_loesen($gleichung, $genaue_stellen=5) { // findet die Nullstellen if ($gleichung[0] == '+') { $gleichung = substr($gleichung, 1); } $nullstelle_in_intervall = FALSE; $genauigkeit = pow(0.1, $genaue_stellen); while ($nullstelle_in_intervall == FALSE) { $intervall_a = -mt_rand(1, 50); $intervall_b = mt_rand(1, 50); $temp1 = in_gleichung_einsetzen($gleichung, $intervall_a); $temp2 = in_gleichung_einsetzen($gleichung, $intervall_; if (($temp1*$temp2) < 0) { $nullstelle_in_intervall = TRUE; } if (abs($temp1) < $genauigkeit) { return $intervall_a; } if (abs($temp2) < $genauigkeit) { return $intervall_b; } } //echo $intervall_a.' | '.$intervall_b; $rechte_seite = 100; $gemachte_iterationsschritte = 0; // Abbruchbedingung, damit kein Timeout while (abs($rechte_seite) > $genauigkeit && $gemachte_iterationsschritte < 50000) { $intervall_c = ($intervall_a+$intervall_b)/2; $rechte_seite = in_gleichung_einsetzen($gleichung, $intervall_c); if ($rechte_seite !== FALSE) { // INTERVALL ANPASSEN (c ERSETZT ELEMENT[a,b] MIT GLEICHEM VORZEICHEN) ANFANG if ($rechte_seite > 0) { $intervall_a = $intervall_c; } else { $intervall_b = $intervall_c; } // INTERVALL ANPASSEN (c ERSETZT ELEMENT[a,b] MIT GLEICHEM VORZEICHEN) ENDE } else { $intervall_a = -mt_rand(0, 200); $intervall_b = mt_rand(0, 200); } $gemachte_iterationsschritte++; } if ($gemachte_iterationsschritte < 50000) { $intervall_c = round($intervall_c, 3); // auf 3 Dezimalen runden return $intervall_c; } else { return FALSE; } } $gleichung = 'pow((x-1),2)-1.5'; echo gleichung_loesen($gleichung); ?> [/PHP] Die Intervallgrenzen werden zufällig bestimmt, bis es dazwischen eine Nullstelle gibt. Dann wird die Iteration gestartet. Es wird auch am Anfang geprüft, ob die Grenzen selber vielleicht eine Nullstelle sind.

OK, danke für die Hinweise! Ich habe aber noch eine neue Idee, wie man mehrere Nullstellen mit der Bisektion finden könnte: Man hat z.B. die folgende Gleichung: (x-1)^2-1=0 Die Nullstellen, die man sucht, sind 0 und 2. Als erstes findet man mit der Bisektion die 2. Damit man die 0 auch noch findet, ändert man die Gleichung. Man teilt die eigentliche Funktion durch (x-NULLSTELLE): ((x-1)^2-1) / (x-2)=0 Da man nicht durch 0 teilen darf, kann hier 2 nicht mehr als Nullstelle rauskommen. Also findet man automatisch die 0. Geht das so? Meint ihr, das wird funktionieren?

@AndiE: Der höchste Exponent in der Gleichung gibt also an, wie viele Nullstellen es gibt? @flashpixx: Ich meinte, man kann damit für alle Gleichungen, die auch Nullstellen haben, diese Nullstellen finden. Also: Dem Verfahren "entgeht" praktisch keine Nullstelle. Aber das stimmt wohl auch nicht, oder? Du meinst also, die Bisektion ist kein geeignetes Verfahren für das Finden von Nullstellen? Welches Verfahren wäre denn besser?

OK, da hast du Recht. Diese Gleichung könnte man auch einfacher lösen. Aber ich möchte eine Methode haben, mit der ich jede Gleichung lösen kann, also z.B. auch: (20-x)*(-1)^(1+1)*+(10-x)*(-1)^(1+1)*(0-x)*(0-x)-0*0+0*(-1)^(1+2)*0*(0-x)-0*0+0*(-1)^(1+3)*0*0-0*(0-x)+14*(-1)^(1+2)*+14*(-1)^(1+1)*(0-x)*(0-x)-0*0+0*(-1)^(1+2)*0*(0-x)-0*0+0*(-1)^(1+3)*0*0-0*(0-x)+0*(-1)^(1+3)*+14*(-1)^(1+1)*0*(0-x)-0*0+(10-x)*(-1)^(1+2)*0*(0-x)-0*0+0*(-1)^(1+3)*0+0*(-1)^(1+4)*+14*(-1)^(1+1)*0*0-0*(0-x)+(10-x)*(-1)^(1+2)*0*0-0*(0-x)+0*(-1)^(1+3)*0 = 0 Dafür wäre die Bisektion oder ein anders Näherungsverfahren perfekt. Leider finde ich mit der Bisektion auch bei der Gleichung oben nur eine Nullstelle. Deshalb suche ich eine Lösung für das Problem bei der Bisektion ...

Ich möchte die Nullstellen des folgenden Polynoms finden. Deshalb habe ich es mit 0 gleichgesetzt: (5-x)*(25-x)-11*11 = 0 Diese Gleichung löse ich mit der Bisektion (Intervallhalbierung) als Näherungsverfahren. Leider bekomme ich nur eine Nullstelle (0.133). Die andere (29.866) finde ich damit leider nicht. Woran liegt das? Kann man die auch mit der Bisektion finden? Danke im Voraus für eure Hilfe!

Danke für deine Antwort! Es muss nicht unbedingt PHP sein, aber es muss eine serverseitige Sprache sein. Und da ist PHP leider die einzige, die ich kann. Also du meinst, dass es nicht sinnvoll ist, so etwas selbst zu programmieren? Dann muss ich mir vielleicht mal die Grundlagen von einer anderen Sprache angucken, das wird ja reichen, um so eine Bibliothek einzubinden ... Aber vielleicht kann mir doch noch jemand in PHP weiterhelfen? Ich habe noch einige Seiten rausgesucht, auf denen es Erklärungen gibt: http://fed.matheplanet.com/mprender.php?stringid=1080115 Singular Value Decomposition (SVD) tutorial SVD and LSI Tutorial 4: Latent Semantic Indexing (LSI) How-to Calculations Singulärwertzerlegung ? Wikipedia Und der QR-Algorithmus: QR-Algorithmus ? Wikipedia

Hallo! Ich habe eine Matrix A: 1 1 0 1 1 0 Diese Matrix stelle ich in PHP ja wohl am besten als zweidimensionales Array dar, oder? Jetzt möchte ich die Singulärwertzerlegung (A=USV) daraus programmieren. Könnt ihr mir dabei helfen? Das wäre super! Danke im Voraus! Wer nicht weiß, was "Singulärwertzerlegung" ist, kann hier klicken.

OK, danke für eure Hilfe. Ich habe mich jetzt für einen Aufbau entschieden: 385 Input-Neuronen (6 für jedes Feld + 1 für "Wer ist am Zug") 4096 Output-Neuronen (64 Zielfelder pro Quellfeld) Das einzige, was mir jetzt noch fehlt, ist die Lernfunktion. Ich möchte das ja mit Temporal Difference Learning umsetzen. Dazu habe ich auch drei Sachen gefunden: Grafik 1 Grafik 2 Grafik 3 Leider verstehe ich das trotz dieser Hilfen noch nicht ganz. Könnt ihr mir da vielleicht helfen? Könnt ihr mir sagen, wie ich das programmieren könnte? Vielleicht in Pseudo-Code? Danke im Voraus!