Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


38. Kurvenanpassung



Übungen

  1. Approximieren Sie die Funktion lg x in den Punkten 1, 2, 3, 4 und 5 mit Hilfe eines Interpolationspolynoms vierten Grades. Beurteilen Sie die Güte der Näherung durch Berechnung der Summe der Fehlerquadrate in den Punkten 1,5; 2,5; 3,5 und 4,5.
  2. Lösen Sie das gleiche Problem für die Funktion sin x. Stellen Sie die Funktion und die Näherung, wenn möglich, mit Ihrem Computersystem grafisch dar.
  3. Lösen Sie die obengenannten Probleme unter Verwendung eines kubischen Splines anstelle eines Interpolationspolynoms.
  4. Approximieren Sie die Funktion lg x durch einen kubischen Spline unter Verwendung von Knoten in den Punkten 2N für N zwischen 1 und 10. Versuchen Sie, eine bessere Anpassung zu erhalten, indem Sie mit anderen Anordnungen von Knoten im gleichen Intervall experimentieren.
  5. Was geschieht bei der Datenanpassung mit Hilfe der Methode der kleinsten Quadrate, falls eine der Funktionen die Funktion fi(x) = 0 für einige i ist?
  6. Benutzen Sie eine Kurvenanpassung mit Hilfe der Methode der kleinsten Quadrate, um die Werte von a und b zu ermitteln, die die beste Formel der Form aN ln N + bN zur Beschreibung der Gesamtzahl der Anweisungen ergeben, die ausgeführt werden, wenn Quicksort für eine zufällige Datei abgearbeitet wird.
  7. Welche Werte von a, b, c realisieren den kleinsten quadratischen Fehler bei Benutzung der Funktion f(x) = ax log x + bx + c zur Approximation der Beobachtungen f(1) = 0, f(4) = 13, f(8) = 41?
  8. Wie viele Multiplikationen sind erforderlich, wenn man die Methode der kleinsten Quadrate anwendet, um auf der Basis von N Beobachtungen M Koeffizienten zu bestimmen. Dabei ist der Abschnitt mit der Gaußschen Elimination unbeachtet zu lassen?
  9. Unter welchen Umständen wäre die Matrix, die bei der Kurvenanpassung mit Hilfe der Methode der kleinsten Quadrate auftritt, singulär?
  10. Führt die Methode der kleinsten Quadrate zum Ziel, wenn zwei verschiedene Beobachtungen für den gleichen Punkt einbezogen werden?


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]