Nullstellen mit Bisektion finden?

[AndiE]

Hallo,

ich habe mich belesen und Excel geärgert.

Wenn du Phils Beispiel ansiehst, dann wird dir auffallen, daß dabei x1^2+x2^2=q ist, in diesem Fall =1.

Ich kann das zwar nicht aus x^2+px+q=0 herleiten, aber aus der Lösungsgleichung.

Somit lässt sich erstmal allgemein feststellen: Zumindest für Quadratische Gleichungen gilt, daß die Lösungen der Gleichungen auf einem Kreis mit dem Radius r=wurzel(q) liegen.

Für den Kreis gilt:

Realanteil= r*sin(alpha)

Imaginäranteil=r*cos(alpha)

Für 0<alpha<360° kannst du die komplexen Werte berechnen. Wie du sehen wirst, bildet das Ergebnis, wenn man es mit der Diagrammfunktioin grafisch darstellt, eine zusammenhängende Schleife mit zwei Windungen- weil Polynom 2. Ordnung.

Und wenn dann Re=0 und Im=0, hast du eine Nullstelle gefunden.

Wenn mans weiß, ist das so genial einfach.

Ob das bei höhrern Ordnungen auch so ist, und was sich evtl. ändert, konnte ich noch nicht eindeutig feststellen.

[flashpixx]

Wie du sehen wirst, bildet das Ergebnis, wenn man es mit der Diagrammfunktioin grafisch darstellt, eine zusammenhängende Schleife mit zwei Windungen- weil Polynom 2. Ordnung.

Und wenn dann Re=0 und Im=0, hast du eine Nullstelle gefunden.

Poste doch einmal das Bild. Eine Schleife ist nach meiner Vorstellung unstetig in dem Schnittpunkt und die Nullstelle existiert sehr wohl, damit kann die Kurve in der Nullstelle nicht unstetig sein

Phil

[AndiE]

Hallo,

hier das Bild

Ich hoffe , ich habe es richtig interpretiert?

[Ocram7]

@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]

[flashpixx]

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?

Nein. Du hast mein Zitat über die lokale Konvergenz des Wikiartikels gelesen?

Phil

[AndiE]

Die Form der Gleichungen mach ja "cool" sein, aber am besten nachvollziehbar wären sie, wenn du sie in Normalform oder im Horner- Schema schreibst:

aus (5-x)*(25-x)-11*11=0

wird

x^2-30x+4=0

oder

(x-30)*x+4=0

[AndiE]

Hi,

Versuche mal, mit deinem Algorithmus die Lösungen zu finden für:

(((x-10)*x+35)*x-50)*x+24=0

Es sollten sein :1, 2, 3, 4

Poste bitte das Ergebnis

[Ocram7]

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]

Als Lösung für Deine Gleichung wäre 15 +- 221^(1/2). Ich kann mich nur wiederholen, dass Dein Lösungversuch nicht gut genug ist.

Nutze fertige Bibliotheken, bis Du annähernd diese Funktionalität erreichst, vergehen Jahre. Nur Du scheinst mir diesbezüglich uneinsichtig zu sein

Phil

[AndiE]

Hallo,

nein, sie findet sie nicht widerspruchslos. Sieh dir mal die Intervallwerte an. Im Nomalen müßten sie 0 und 10 sein, mit den Werten 4 und -196, wenn du bei -100 beginnst und mit Schrittweite 10 rechnest.

Also solltest du erstmal damit beginnen, das das Programm diese Nullübergänge findet und den Intervall (links,rechts) anzeigt.

Die Differenz zum Näherungswert sinkt auch nicht kontinuierlich.

[Ocram7]

[...] Also solltest du erstmal damit beginnen, das das Programm diese Nullübergänge findet und den Intervall (links,rechts) anzeigt. Die Differenz zum Näherungswert sinkt auch nicht kontinuierlich.

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?

[...] Nutze fertige Bibliotheken, bis Du annähernd diese Funktionalität erreichst, vergehen Jahre. Nur Du scheinst mir diesbezüglich uneinsichtig zu sein

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.

[flashpixx]

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.

Nein. Schreibe Dir ein PHP Modul:

Simplified Wrapper and Interface Generator

PHP: PHP at the Core: A Hacker's Guide to the Zend Engine - Manual

Es ist der erste Treffer bei Google !

Phil

[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?

[flashpixx]

Ich kann doch ein PHP Modul lokal entwickeln !? Du solltest sicher nicht Dein Produktivsystem für die Entwicklung verwenden. Wie Dein Server konfiguriert ist, das ist natürlich eine Sache. Auf dem Server müssen natürlich die GSL Libraries installiert sein und Dein PHP Modul muss dann eingebunden werden. Sehe ich aber nicht das Problem, denn Du möchtest eine sinnvolle Lösung für Dein Problem und ein Server (auch wenn man nur einen VServer nimmt) kostet nicht die Welt.

Mit Deinem Algorithmus wirst Du immer Probleme haben, denn den naiven Ansatz, den Du gehst, wird eben nicht das gewünschte liefern. Du siehst es selbst. Du möchtest ein System, dass Dir jedes Polynom vom Grad n löst und Dir die nicht trivialen Nullstellen liefert.

Wie Du an den bisherigen Post sehen kannst, werden Dir sehr schnell Beispiele gezeigt, die Dein System nicht lösen kann bzw unzureichend löst.

Die Diskussion dreht sich im Kreis, denn Du möchtest an Deiner Lösung fest halten.

Phil

[AndiE]

Hallo,

ich gebe Phil recht, wir drehen uns hier im Kreis. Daher wäre mein Vorschlag an den OP, mal den PC auszulassen.

Als die Algorihmen entwickelt wurden, wurde mit der Hand gerechnet.

Versuche mal, deine Gleichungen mit der Hand und der Bisektion zu lösen.

Überprüfe dabei auch deinen Algortithmus.

Mal sehen, was dabei passiert!