Polynom- und Spline-Programmierhandbuch

Ursprünglicher Autor: Words and Buttons Online
  • Übersetzung


Du bist also ein Programmierer. Warum brauchen Sie überhaupt Polynome? Zum Beispiel ist dies ein guter geometrischer Ton, aus dem Sie verschiedene Dinge herstellen können.

Aus unserem Artikel , der das Wesen der mathematischen Analyse am Beispiel von Python, Blut und Dynamit erläutert, ist klar, dass Sie beliebige Funktionen als Polynome analysieren und synthetisieren können. Es ist jedoch nicht notwendig, mit Funktionen zu arbeiten. Manchmal müssen Sie einen Spline aus mehreren Punkten oder Eigenschaften simulieren, z. B. Tangentialkurven. Beispielsweise müssen Sie eine Art Animation oder einen schönen Videoeffekt erstellen oder eine Kurve durch bestimmte Punkte zeichnen oder an einer Stelle eine flache Oberfläche und an einer anderen eine gekrümmte Oberfläche erstellen.

Polynome, auch Splines, sind zwar nicht immer das beste Werkzeug für diese Aufgabe, verfügen jedoch über einige Funktionen, die Programmierer zu schätzen wissen. Sie sind einfach und vielseitig und vor allem sehr leistungsfähig. Nehmen Sie zum Beispiel folgendes Polynom:



Zur Berechnung sind nur 6 Multiplikationsaktionen und 3 Additionen erforderlich. Dies ist wichtig, da Ihr Modell ständig Berechnungen unterzogen wird. Aber hier können wir optimieren. Dies wird uns helfen, Horners Schema. Mit seiner Hilfe kann dasselbe Polynom in das Formular geschrieben werden



Und das sind nur 3 Multiplikationen und 3 Ergänzungen. Wir haben gerade erst angefangen, und Sie haben bereits gelernt, ein Drittel der Berechnungen loszuwerden.

Polynominterpolation


Die Aufgabe, ein Polynom des n- ten Grades unter n + 1 Raumpunkt anzupassen, wird als Polynominterpolation bezeichnet. Es gibt mehrere Möglichkeiten, dies zu implementieren. Sie können die Interpolationsformeln von Newton oder Lagrange verwenden , aber der einfachste Weg, ein Interpolationspolynom zu erhalten, besteht darin, ein System linearer Gleichungen zu lösen.

Wenn ein Polynom einen Punkt durchläuft, können wir natürlich behaupten, dass P (xi) = yi ist . Angenommen, wir möchten ein Polynom an drei Punkte anpassen. Das bedeutet:



Im Allgemeinen können wir keine Linie durch drei beliebige Punkte ziehen. Und deshalb müssen wir es drehen und eine Parabel bilden. Oder mit anderen Worten ein Polynom zweiten Grades einführen, das auch als quadratische Funktion bekannt ist.



Da xs und ys bekannt sind, können wir nur das System lösen und die Koeffizienten a, b, c herausfinden. Da dieses System aus drei Gleichungen und drei Variablen besteht, können wir normalerweise eine einzige Lösung erhalten.

Um dies zu sehen, verschieben Sie die Position der drei Punkte in der unteren Grafik und sehen Sie, was passiert.



Diese Grafik ist auch sehr nützlich für die mentale Analyse linearer Systeme. Im Allgemeinen ist es nicht möglich, an drei Punkten eine gerade Linie festzulegen, ebenso wie es unmöglich ist, eine Lösung für ein System von n Gleichungen mit n-1 unbekannten Variablen zu finden. Aber manchmal ist es möglich. Zum Beispiel in Fällen, in denen einige der Punkte übereinstimmen oder alle absichtlich auf einer geraden Linie liegen.

Die umgekehrte Situation ist noch interessanter. Wir können unendlich viele Parabeln durch zwei gegebene Punkte zeichnen. Alle sind gleichermaßen als Lösung des Problems geeignet. Und gleichzeitig können wir keine eindeutig bessere Lösung für Systeme mit n Gleichungen und n + 1 Variablen erhalten.

Aber was ist, wenn es noch möglich ist? Was ist, wenn wir einige zusätzliche Kriterien für die Auswahl der am besten geeigneten Option einführen können?

Synthesis


Ähnliche Fragen führen uns in das Gebiet der Polynomsynthese. In unserem Fall ist dies eine Kreuzung zwischen Polynomserien und Polynominterpolation. Mit Hilfe von Serien können wir eine Funktion basierend auf ihren Ableitungen zu einem bestimmten Zeitpunkt modellieren, und mit Hilfe der Synthese können wir sowohl Punkte als auch Ableitungen verwenden (und nicht nur sie, sondern zu einem anderen Zeitpunkt).

Die Ableitung einer Funktion hängt eng mit den geometrischen Eigenschaften ihres Graphen zusammen. Die erste Ableitung bestimmt den Tangens des Neigungswinkels der Tangente und die zweite - die Krümmung.

Angenommen, wir müssen eine Funktion definieren, die zwei Punkte durchläuft, und deren Tangens an beiden Punkten kennen. In diesem Fall können wir es leicht in Form eines Polynoms synthetisieren.

Wie zuvor müssen wir das Gleichungssystem aufschreiben. Jetzt brauchen wir vier Bedingungen, also sollten wir ein Polynom vom Grad 3 wählen, dh eine kubische Funktion.



Einige der Gleichungen basieren auf Punkten, während andere abgeleitet werden. Hier können Sie auch Integrale hinzufügen, um die notwendigen Eigenschaften der Integrität einzuführen, was diese Technik sehr effektiv macht.

Wir werden jedoch weiterhin eine Funktion in Betracht ziehen, die zwei Punkte einer durchgehenden glatten Linie mit tangentialen Beschränkungen an diesen Punkten verbindet.





Runge-Phänomen


Die Polynominterpolation hat eine unangenehme Eigenschaft, die sich in einem Anstieg des Oszillationswachstums an beiden Enden des Intervalls mit einer Zunahme der Anzahl von Punkten äußert. Dieses Phänomen wird als Runge-Phänomen bezeichnet. Sie beschränkt die Möglichkeiten der Anwendung einfacher Polynominterpolationen.

Ein weiterer Nachteil dieses Ansatzes ist seine Globalität, dh die Änderung der gesamten Funktion zusammen mit der geringsten Änderung der Position von mindestens einem Punkt. In Kombination mit Schwingungen stellt sich das größte Chaos heraus.



Chebyshev-Knoten


Eine der Möglichkeiten, dem Chaos zu begegnen, besteht darin, ein spezielles Netz für die Interpolation auszuwählen - die Chebyshev-Knoten . Dies sind spezielle Werte von x, die durch Unterteilen eines Halbkreises mit Radius 1 in gleiche Fragmente und Projizieren auf die x-Achse erhalten werden.

Im Allgemeinen liegt in dieser Technik eine gewisse mathematische Magie, aber aus pragmatischer Sicht soll das Phänomen von Runge minimiert werden. Und obwohl die Interpolation nicht vollständig vorhersagbar gemacht werden kann, funktioniert alles stabil auf dem Segment (-1: 1).



Natürlich können Sie das Intervall entlang der X-Achse beliebig verlängern, indem Sie eine eindimensionale affine Transformation verwenden. Es ist nicht notwendig, an dem Segment (-1; 1) festzuhalten .

Die Interpolation behält jedoch gleichzeitig ihre Allgegenwart. Die Änderung im ersten Punkt wirkt sich immer noch auf die Funktion der letzten Funktion aus, wenn auch nicht so signifikant.

Splines


Es gibt viele Splines, aber alle haben ein Anwendungsszenario. Sobald die globale Interpolation aus irgendeinem Grund nicht mehr für unsere Aufgaben geeignet ist, können wir unser Intervall in kleinere Fragmente unterteilen und separate Funktionen für die Interpolation für jede von ihnen definieren.

Das einzige, was wir beachten müssen, ist die Notwendigkeit, sie an den Enden miteinander zu verbinden, um die Kontinuität zu gewährleisten. Wenn wir die Kontinuität nicht nur der endgültigen, stückweise gegebenen Funktion, sondern auch ihrer ersten Ableitung gewährleisten, dann fallen die Tangenten jedes ihrer Segmente zusammen und der Graph wird glatt aussehen.

Es gibt eine bestimmte KlassifizierungSplines Nehmen Sie zum Beispiel einen Polynom-Spline, der aus zwei Fragmenten besteht. Wenn jedes seiner Fragmente durch ein Polynom dritten Grades bestimmt wird, wird es kubisch genannt. Es kann beispielsweise eine solche Eigenschaft aufweisen, wie die Kontinuität der ersten Ableitung, da die Tangenten an der Verbindung der Fragmente zusammenfallen. Ihre Fragmente sind nicht gleich der Breite. Es ist nicht natürlich, dass wir die Derivate an ihren Enden verwalten können. Und natürlich ist dies ein Interpolations-Spline, da er genau durch die von uns angegebenen Gitterpunkte verläuft.



Fazit


Die Wahrscheinlichkeit, dass Sie Ihre eigene Interpolation jemals in der Praxis implementieren müssen, ist äußerst gering. Es gibt viele vorgefertigte Lösungen und in den meisten Fällen müssen Sie nur das richtige Werkzeug für den Job auswählen. Dieses Wissensgebiet ist nicht so schwierig, aber die Anzahl der unbekannten Wörter und Namen kann verfremden.

Ziel dieses Leitfadens war es, Ihnen ein grundlegendes Verständnis der Ideen zu vermitteln, die für die Arbeit mit Polynomen und Splines verwendet werden. In keinem Fall erhebt er den Anspruch auf Vollständigkeit, denn tatsächlich wurden für jedes der kleinen Kapitel dieses Materials ganze Bücher geschrieben. Wir hoffen jedoch zumindest, dass eine interaktive Herangehensweise an die Präsentation in diesem Material nicht nur für eine kurze Einführung nützlich ist, sondern, falls dies erforderlich ist, Ihnen helfen wird, fortgeschrittenere Themen zu meistern.

Bild

Jetzt auch beliebt: