Approximationsfrage der kleinsten Quadrate

11

Ich nehme an einem Kurs über wissenschaftliche Berechnungen teil, und wir haben gerade die Annäherung der kleinsten Quadrate durchgearbeitet. Meine Frage bezieht sich speziell auf die Approximation mit Polynomen. Ich verstehe, dass Sie, wenn Sie n + 1 Datenpunkte haben, ein eindeutiges Polynom vom Grad n finden können, das alle diese Punkte beschreibt. Ich kann aber auch sehen, warum dies nicht immer ideal ist. Bei einem solchen Ansatz kann zwischen den Datenpunkten viel Rauschen auftreten. Ich nehme an, es ist schön, ein Polynom niedrigeren Grades zu erhalten, das Ihre Daten gut genug schätzt.

Meine Frage ist: Wie entscheiden Sie in der Praxis, welchen Grad an Polynom Sie verwenden werden? Gibt es eine Faustregel oder hängt sie nur vom jeweiligen Problem ab? Müssen wir bei der Entscheidung zwischen mehr oder weniger Abschlüssen verschiedene Kompromisse berücksichtigen? Oder verstehe ich hier etwas falsch?

Danke im Voraus.

Uday Pramod
quelle
2
Ich denke, in der Praxis verwenden Leute Dinge wie Spline-Interpolation en.wikipedia.org/wiki/Spline_interpolation, so dass Polys niedriger Ordnung verwendet werden, aber sie passen gut über die gesamte Domäne zueinander. Auf diese Weise muss man nicht für eine Gesamtpolynomordnung raten.
Nasser
Danke für den Link. Wir haben Splines noch nicht besprochen, daher ist dies eine interessante Lektüre.
Uday Pramod
Was genau möchten Sie tun? Versuchen Sie, die Punkte zu interpolieren oder bestimmte Daten anzupassen? Zum Beispiel ist es sinnlos, Daten, die aus einer Normalverteilung bestehen, mit Rauschen zu interpolieren. Für die erstere ist Nassers Antwort gut. Für letztere hängt die Anpassungsfunktion ausschließlich vom vorliegenden Problem ab und ist in vielen Fällen nicht polynomisch.
Hauntergeist
Die Antworten auf diese Frage könnten Sie interessieren .
Bort

Antworten:

18

Der wichtigste Aspekt der Interpolation und Kurvenanpassung besteht darin, zu verstehen, warum Polynomanpassungen hoher Ordnung ein Problem sein können und welche anderen Optionen es gibt, und dann zu verstehen, wann sie eine gute Wahl sind / nicht.

Einige Probleme mit Polynomen höherer Ordnung:

  • Polynome sind natürlich Schwingungsfunktionen. Wenn die Ordnung des Polynoms zunimmt, nimmt die Anzahl der Schwingungen zu und diese Schwingungen werden stärker. Ich vereinfache hier, die Möglichkeit von mehreren und imaginären Wurzeln macht es ein bisschen komplexer, aber der Punkt ist der gleiche.

  • Polynome nähern sich +/- unendlich mit einer Rate, die der Polynomordnung entspricht, wenn x auf +/- unendlich geht. Dies ist oft kein gewünschtes Verhalten.

  • Das Berechnen von Polynomkoeffizienten für Polynome hoher Ordnung ist typischerweise ein schlecht konditioniertes Problem. Dies bedeutet, dass kleine Fehler (z. B. Rundungen in Ihrem Computer) zu großen Änderungen in der Antwort führen können. Das lineare System, das gelöst werden muss, beinhaltet eine Vandermonde-Matrix, die leicht schlecht konditioniert werden kann.

Ich denke, dass das Herzstück dieses Problems vielleicht die Unterscheidung zwischen Kurvenanpassung und Interpolation ist .

Interpolation wird verwendet, wenn Sie der Meinung sind, dass Ihre Daten sehr genau sind und Ihre Funktion genau mit den Datenpunkten übereinstimmen soll. Wenn Sie Werte zwischen Ihren Datenpunkten benötigen, verwenden Sie normalerweise am besten eine glatte Funktion, die dem lokalen Trend der Daten entspricht. Kubische oder hermitische Splines sind häufig eine gute Wahl für diese Art von Problem, da sie viel weniger empfindlich auf nicht lokale (dh an Datenpunkten, die weit von einem bestimmten Punkt entfernt sind) Änderungen oder Fehler in den Daten reagieren und weniger oszillierend sind als ein Polynom. Betrachten Sie den folgenden Datensatz:

x = 1   2   3   4   5   6   7   8   9  10
y = 1   1 1.1   1   1   1   1   1   1   1

Interpolation
Eine Polynomanpassung hat viel größere Schwingungen, insbesondere in der Nähe der Kanten des Datensatzes, als ein Hermite-Spline.

Andererseits ist die Approximation der kleinsten Quadrate eine KurvenanpassungTechnik. Die Kurvenanpassung wird verwendet, wenn Sie eine Vorstellung von der erwarteten Funktionalität Ihrer Daten haben, Ihre Funktion jedoch nicht erforderlich ist, um alle Datenpunkte genau zu durchlaufen. Dies ist typisch, wenn die Daten Messfehler oder andere Ungenauigkeiten enthalten können oder wenn Sie den allgemeinen Trend der Daten extrahieren möchten. Die Approximation der kleinsten Quadrate wird am häufigsten in einem Kurs durch Verwendung von Polynomen für die Kurvenanpassung eingeführt, da dies zu einem linearen System führt, das mit den Techniken, die Sie wahrscheinlich früher in Ihrem Kurs gelernt haben, relativ einfach zu lösen ist. Techniken der kleinsten Quadrate sind jedoch viel allgemeiner als nur Polynomanpassungen und können verwendet werden, um jede gewünschte Funktion an einen Datensatz anzupassen. Wenn Sie beispielsweise einen exponentiellen Wachstumstrend in Ihrem Datensatz erwarten,

Schließlich ist die Auswahl der richtigen Funktion für Ihre Daten ebenso wichtig wie die korrekte Durchführung der Interpolations- oder Kleinstquadratberechnungen. Dies ermöglicht sogar die Möglichkeit einer (vorsichtigen) Extrapolation. Betrachten Sie die folgende Situation. Angesichts der Bevölkerungsdaten (in Millionen von Menschen) für die USA von 2000 bis 2010:

Year:  2000   2001   2002   2003   2004   2005   2006   2007   2008   2010
Pop.: 284.97 287.63 290.11 292.81 295.52 298.38 301.23 304.09 306.77 309.35

Die Verwendung einer exponentiell linearisierten Anpassung der kleinsten Quadrate N(t)=A*exp(B*t)oder eines Polynominterpolanten 10. Ordnung ergibt die folgenden Ergebnisse:
Bevölkerungsgrundstück

Das Bevölkerungswachstum in den USA ist nicht ganz exponentiell, aber ich lasse Sie die bessere Passform beurteilen.

Doug Lipinski
quelle
1
Ein Punkt, den ich mit Ihrem Diagramm der US-Bevölkerung ansprechen möchte: Aus dem Gedächtnis heraus bedeutet eine gute Anpassung an die Domäne nicht, dass sie gut extrapoliert werden kann. In diesem Licht kann es irreführend sein, die großen Polynomfehler außerhalb der Region anzuzeigen, in der Sie Daten haben.
Daryl
@Daryl Einverstanden, deshalb habe ich betont, dass die Extrapolation vorsichtig erfolgen sollte und dass die Auswahl einer geeigneten Funktion in diesem Fall von entscheidender Bedeutung ist.
Doug Lipinski
@DougLipinski Danke für die aufschlussreiche Antwort. Können Sie erklären, was Sie unter linearisierten kleinsten Quadraten im Gegensatz zu kleinsten Quadraten verstehen?
bela83
@ bela83 Richtig zu antworten wäre zu lang für einen Kommentar. Ich denke, es wäre eine sehr gute neue Frage, wenn Sie sie stellen möchten.
Doug Lipinski
@ DougLipinski Ich werde es versuchen!
bela83
2

Sehr unwissenschaftlich, aber eine gute Faustregel ist, dass Polynome 3. Grades normalerweise ein guter Anfang sind, und in der Praxis habe ich noch nie jemanden gesehen, der mehr als ein Polynom 6. Grades verwendet, um gute Ergebnisse zu erzielen.

Das "ideale" Polynom wäre das Polynom niedrigster Ordnung, das die rauschfreien Daten für Ihren Zweck gut genug darstellt.

Wenn Ihre Daten klein genug sind, um dies zuzulassen (normalerweise), können Sie einfach versuchen, Polynome höherer Ordnung anzupassen, bis Sie Oszillationen sehen, die tendenziell ein Zeichen für "Überanpassung" sind.

Eine Alternative wäre ein glättender Spline , der jedoch sehr stark von der Anwendung abhängt. Splines und Glättungssplines eignen sich nur zur Interpolation. Bei verrauschten Daten bevorzuge ich Polynomanpassungen gegenüber der Glättung von Splines, aber die Daten, mit denen ich arbeite, werden durch die Polynome normalerweise gut angenähert.

LKlevin
quelle
1

Ein anständig effektiver Ansatz, den ich bei der Polynomnäherung verwendet habe, besteht darin, die Polynome der kleinsten Quadrate für verschiedene Grade (z. B. von 1 bis 10) zu berechnen und dann die Kurve zu wählen, die den mittleren quadratischen Fehler an Punkten auf halbem Weg zwischen aufeinanderfolgenden (wann) minimiert sortiert nach x) Punkten in Ihrem Datensatz. Dies hilft, Kurven mit zu starken Schwingungen auszuschließen.

dan04
quelle