Iterationsverfahren: Wie oft Abbruch prüfen?

JohnnyBravo · Newbie Anmeldungsdatum: 14.04.2006 Beiträge: 1

Hallo,

ich habe folgendes Problem: Ich implementiere ein iteratives Lösungsverfahren und möchte herausfinden, wie oft eine Prüfung des Abbruchkriteriums des Verfahrens sinnvoll ist. Es gibt folgende Größen:

w: Wahrscheinlichkeit, dass das Abbruchkriterium nach einem Schritt erfüllt ist (nicht notwendigerweise geprüft), wenn es davor nicht erfüllt war

t: Zeit, die für einen Iterationsschritt benötigt wird

n*t: Zeit, die für das Prüfen des Abbruchkriteriums benötigt wird

Zu bestimmen ist:

x: Anzahl der Iterationsschritte, die zwischen zwei Prüfungen des Abbruchkriteriums liegen

Bisherige Überlegungen:

Wahrscheinlichkeit, dass das Abbruchkriterium zwischen zwei Prüfungen erfüllt wird: 1-(1-w)^x

Zeit, die durch Prüfung gespart wird, falls Kriterium erfüllt: x*t (Iterationsschritte bis zur nächsten Prüfung)

Erwartungswert der Zeitersparnis: (1-(1-w)^x)*x*t

Zeit, die durch Prüfung verschwendet wird, falls Kriterium nicht erfüllt: n*t

Erwartungswert der Zeitverschwendung: ((1-w)^x)*n*t

Gesamtbilanz: (1-(1-w)^x)*x*t - ((1-w)^x)*n*t --> max

Ableitung nach x: -((1-w)^x)*t * (ln(1-w)*x+1+ln(1-w)*n) = 0

<==> x = -n - 1/ln(1-w)

Das Problem beim Ergebnis ist, dass x und n negativ zusammenhängen. Je langsamer die Prüfung ist, desto häufiger sollte man sie Durchführen? Das kann doch nicht sein!
Meine Rechnungen sind vermutlich richtig, der Fehler muss irgendwo im Ansatz liegen, aber ich weiß nicht wo. Meine Intuition sagt mir, dass x=n sein müsste, aber ich würd's gern beweisen.

Bin für Antworten sehr dankbar!

algebrafreak · Verfasst am: 15 Apr 2006 - 17:47:19 Titel: