Autor Beitrag
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Mo 10.03.03 20:04 
Hi!

Aus diesem Thread ist ein Programm geworden, welches ich der Vollständigkeit halber mal hier posten möchte.

Ausführbares gibt es hier!
Dazu braucht man noch eine dll-Datei!
Der Source von beiden ist hier!

Beim Source muss ich mich wohl für meine Faulheit beim Benennen von Datein entschuldigen.

MfG,
Peter

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Ernald
Hält's aus hier
Beiträge: 7



BeitragVerfasst: Sa 05.04.03 19:59 
Titel: Neues Programm
Ich habe mal ein Programm geschrieben, was ohne Grenzen und Genauigkeit auskommt.

exe-Datei: home.arcor.de/r.raus...k/delphi/polynom.exe
Qullcode: home.arcor.de/r.raus...k/delphi/polynom.zip

-Ernald-
Christian S. Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Sa 05.04.03 20:50 
Wenn ich das richtig verstehe, funktioniert das Programm rekursiv, richtig? Zumindest schon mal bei Berechnung der Extrema.

Wenn Du dann die Extrema hast (ab hier vermute ich jetzt mal, durch den Quelltext bin ich noch nicht ganz durchgestiegen) kannst Du auch bestimmen, ab wo keine Nullstellen mehr auftauchen können. Dann kommst Du ohne Grenzen aus. Gute Idee! Die werde ich mit entsprechendem Hinweis auf Dein Programm mal übernehmen.

Nun zur Genauigkeit:
1. Delphi hat eine interne Genauigkeit.
2. An verschiedenen Stellen im Programm verwendest Du entweder eine Rundung (mit der von Dir geschriebenen Funktion) oder aber Du setzt Werte, die kleiner als ein Grenzwert sind, auf Null. Du verwendest also doch eine gewisse Genauigkeit, auch wenn sie vom Benutzer nicht eingegeben wird.

Trotzdem, das mit der rekursiven Berechnung der Extrema finde ich echt gut!

MfG,
Peter

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Christian S. Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Sa 05.04.03 21:24 
Ich habe ein Problem in Deinem Programm gefunden.

Es geht um folgende Zeilen:

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
if ((extrema[i].Art = 2) and (extrema[i].Y > 0))
        or ((extrema[i].Art = 1) and (extrema[i].Y < 0))
        or ((extrema[i].Art = 0) and (extrema[i].Y > 0) and (OrdinateBerechnen(Eingabe, extrema[i].X - 1) < extrema[i].Y))
        or ((extrema[i].Art = 0) and (extrema[i].Y < 0) and (OrdinateBerechnen(Eingabe, extrema[i].X - 1) > extrema[i].Y)) then
        begin
          Ausgabe[j] := Abtasten(Eingabe, extrema[i].X, extrema[i].X);
          j := j + 1;
        end;

Es geht darum, dass Du um 1 nach links gehst. Aber Du weiß nicht, was dazwischen passiert. Dein Programm könnte dort massiv ins Leere laufen und nie mehr wieder kommen!

Besonders zusammen mit diesem Teil aus der Funktion "abtasten":
ausblenden Quelltext
1:
2:
3:
4:
if A = Z then
      begin
        vorX := Z -1;
        jetztX := Z;

Auch hier wieder der Schritt um 1 nach links, der auch in der Nachfolgenden (Endlos-)Schleife gemacht wird. Man kann sicherlich ein Polynom f finden, welches folgende Eigenschaften hat:
1. Sattelpunkt S mit Funktionswert > 0.
2. f(S.x-1) < f(S.x)
3. f(S.x-1) > 0

Bis dahin alles gut. Nun soll am Punkt f(S.x-1) jedoch ein Minimum sein und zwar das letzte dieses Polynoms! Dann wird Dein Algorithmus die Endlosschleife für A=Z in der Funktion "abtasten" nicht mehr verlassen!

Leider kann ich für jeden Schritt nach links (also nicht 1, sondern 0,5 oder 1/Pi oder sonst was) ein solches Polynom finden.

Ich hoffe, ich irre mich, denn wenn ich mich irren würde, könnte ich dieses Vorgehen in meinem Programm verwenden. Bitte zeige mir einen Fehler in meiner Argumentation!

MfG,
Peter

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Ernald
Hält's aus hier
Beiträge: 7



BeitragVerfasst: Mo 07.04.03 20:01 
Titel: stimmt schon
Das Programm bestimmt zuerst die Extrama, mit hilfe dieser Werte ist das gesamte Monotonieverhalten der Funktion bekannt. Mit hilfe der Monotonie und einer Gewissen Vorzeichenwechselüberprüfung werden dann gewisse Bereiche abgetastet.

Die Funktion "Abtasten()" wird nur dann aufgerufen wenn sich die Prozedur "Hochgradig()" sicher ist das in einem bestimmten Bereich !eine! Nullstelle ist.

Die letzten beiden Parameter von "Abtasten" sind die grenzen des abzutastenden Intervalls. Es können auch unendliche Intervalle abgetastet werden (und zwar dann wenn die Grenzen Unlogisch sind).
Bedingungen:
A < Z : ]A;Z[
A > Z : ]A;unendlich[ <- unlogisch für unendliches Intervall
A = Z : ]-unendlich;Z[ <- unlogisch für unendliches Intervall

Deine Beispiele:
Die Verzweigung in deinen ersten Beispiel wird ja nur verwendet wenn die Bedingung "if i = 0 then" gegeben ist d.h. die Extremstelle aus dem ersten Array-Element untersucht wird. Die Extremma sind nach ihren X-Werten geordnet -> i=0: Extrema mit kleinsten X-Wert. Vor dem ersten Extrama (mit kleinsten X-Wert) und auch nach dem letzten, findet kein Monotoniewechsel mehr stat. Wenn das erstes Extrema also unter der X-Achse liegt und der Anstieg vor diesem Extrema negativ ist, so gibt es mit 100%iger warscheinlichkeit eine Nullstelle vor diesem Extrema. Ich rufe also "Abtasten()" mit A = Z auf.

Ich kann mir also in deinem zweiten Beispiel leisten eine Enlosschleife durchzuführen. Die Bedingung Vorzeichenwerchsel "if ((VorY < 0) and (jetztY > 0)) or ((VorY > 0) and (jetztY < 0)) then" oder "vorY = 0" für den Abbruch wird also in jedem Fall erfüllt.

Ich hoffe für dich: du verstest die Funktionsweise dieser monomentalen Rekursion jetzt etwas besser. :shock:
Ich hoffe für mich: das ich alle Fälle die auftreten könnten berücksichtigt habe und sich meine Rekursion nicht verselbstständigt. :wink: :?: :idea:

-Ernald-
Christian S. Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Mo 07.04.03 20:34 
Ah, jetzt verstehe ich es.

Das scheint wirklich zu funktionieren :D

Aber ich muss nochmal drüber nachdenken. Ich werde das mit den Extrema selbst mal verwenden, vielleicht finde ich dann noch irgendetwas. Aber hoffentlich nicht.

MfG,
Peter

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Bunny
Hält's aus hier
Beiträge: 1



BeitragVerfasst: Mi 28.06.06 21:02 
user profile iconChristian S. hat folgendes geschrieben:
Hi!

Aus diesem Thread ist ein Programm geworden, welches ich der Vollständigkeit halber mal hier posten möchte.

Ausführbares gibt es hier!
Dazu braucht man noch eine dll-Datei!
Der Source von beiden ist hier!

Beim Source muss ich mich wohl für meine Faulheit beim Benennen von Datein entschuldigen.

MfG,
Peter


wäre nett wenn jmd. es nocheinmal uppen könnte !
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Mi 28.06.06 21:46 
Das Problem "Nullstellen bei Polynomen finden" lässt sich effizienter und genauer Lösen. Funktionsauswertungen von Polynomen hohen Grades (z.B. "(x-1)*(x-2)*...(x-30)") an der Stelle zwischen 29 und 30 kannst du unter Umständen vergessen. Bei Polynomen hohen Grades wird das "numerische Rauschen" so hoch dass du unter Umständen hunderte von Nullstellen hast, die eigentlich gar keine sind. Das Abtasten "im Dunkeln" finde ich ausserdem nicht sehr elegant (obwohl man selbstverständlich systematisch vorgehen kann und auch beweisen kann, dass es funktioniert).

Um das Problem zu lösen stellt man üblicherweise die Companion Matrix zum zugehörigen Polynom auf und berechnest deren Eigenwerte. Die Eigenwerte sind die Nullstellen des charakteristischen Polynoms einer Matrix; und dieses Polynom ist nach Konstruktion der Matrix gerade identisch zum gegebenen Polynom. Der Vorteil dieser etwas mathematischeren Methode: Du erhältst die Vielfachheit der Nullstellen und die Nullstellen können auch komplex sein.

PS: Einen Eigenwertsolver zu programmieren ist natürlich keine Trivialität. Bei den "numerical Recipes" bzw. in Linpack sollte man aber zu mindest C/Fortran Code dafür finden.
Edit Eigenwertsolver in Pascal: perso.orange.fr/jean...reau/p_matrices.html => Siehe TEST_HQR.PAS