Geometrische Glättung mit Splines. Ändern Sie den Typ der Unterobjekte

Spline(Englisch) Keile - Balken, Schiene) - eine Funktion, deren Definitionsbereich in eine endliche Anzahl von Segmenten unterteilt ist, auf denen der Spline mit einer algebraischen Funktion übereinstimmt. Der maximale Grad der verwendeten Funktionen (meist Polynome) wird als Grad des Splines bezeichnet. Der Unterschied zwischen dem Grad des Splines und der Glätte seines Umrisses (das Fehlen von Diskontinuitäten in den Koordinaten, in der ersten und zweiten Ableitung) wird als Spline-Defekt bezeichnet. Beispielsweise ist eine durchgehende unterbrochene Linie aus Liniensegmenten ein Spline Grad 1 und Defekt 1 (an den Verbindungspunkten der Spline-Segmente bricht die erste Ableitung - Glätte wird verletzt).

Splines haben zahlreiche Anwendungen, sowohl in der mathematischen Theorie als auch in einer Vielzahl von Computeranwendungen. Insbesondere Splines mit zwei Variablen werden intensiv verwendet, um Oberflächen in verschiedenen Computermodellierungssystemen zu definieren.

Mit der in Abb. 2.8 wird die ursprüngliche Funktion durch Segmente von kubischen Parabeln ersetzt, die durch vier benachbarte Knotenpunkte gehen. Die Koeffizienten der Parabeln werden so berechnet, dass die Koordinaten sowie die erste und zweite Ableitung an den Konjugationspunkten der Spline-Fragmente zusammenfallen (der Spline-Defekt ist gleich Null).

Die Linie, die solche Spline-Funktionen beschreiben, ähnelt in ihrer Form einem flexiblen Lineal, das an Knotenpunkten fixiert ist.

Die Berechnung eines Splines läuft normalerweise auf die Lösung eines linearen Gleichungssystems hinaus.

2.4. Annäherung

Eine weitverbreitete Aufgabe der Datenverarbeitung und -modellierung ist die Darstellung ihrer Gesamtheit durch eine Funktion f(x). Die Aufgabe der Approximation besteht darin, die Parameter dieser Funktion so zu erhalten, dass die Funktion die „Wolke“ von Anfangspunkten mit approximiert der kleinste mittlere quadratische Fehler . Die Annäherung basiert normalerweise auf Methode der kleinsten Quadrate.

2.4.1. Polynomische Annäherung

Polynom - ein Ausdruck der Form: beim=a 0 +a 1 Std X+a 2 Std X 2 +...+a nH x n

In jedem n Punkte, für die Werte bekannt sind x ich und j ich, finden wir die Summe der quadrierten Abweichungen der berechneten und gemessenen Werte

Um die beste Näherung zu finden, ist es notwendig, das Minimum dieser Funktion für die Variablen zu finden: aÜber, a 1 , a 2 , ..., a n.

Entscheidung: Funktion differenzieren f für jede dieser Variablen und setzen die Ableitung mit Null gleich. Nach einfachen Umformungen erhalten wir ein lineares Gleichungssystem. Durch Lösen dieses Systems kann man die unbekannten Koeffizienten des Polynoms finden aÜber, a 1 , a 2 , ..., a n.


Koeffizienten für Unbekannte Frei
ein ... eine 2 ein o Mitglied
...
...
... ... .... ..... ....
... N

Ein Beispiel für eine Polynomdaten-Approximation ist in Abb. 2 dargestellt. 2.10.

Reis. 2.10 Polynomische Approximation

2.4.2. Lineare Näherung

Ein besonderer, aber auch der beliebteste Fall der Polynomnäherung ist die lineare Näherung. Mit einer linearen Näherung ist die Funktion j(x) beschreibt eine Gerade und hat die Form j(x) = a + bx (Abb. 2.11).

Reis. 2.11. Lineare Näherung

2.4.3. Methode der kleinsten Quadrate für eine beliebige Funktion

Funktion j(x) kann durch eine beliebige differenzierbare Funktion dargestellt werden (Abb. 2.12). In der Praxis wird davon abgeraten, Funktionen mit Potenzen größer als 4-6 zu verwenden – die Implementierungsfehler nehmen stark zu.

Reis. 2.12. Approximation durch beliebige Funktionen

2.5. Datenglättung

Die Daten der meisten Experimente haben zufällige Komponenten (verrauscht), sodass eine statistische Datenglättung erforderlich ist.

Damit wird die Menge berechnet Z =z 1 ,z 2 ,...z n geglättete Funktionswerte f(x,j), gegeben durch Mengen von Argumentwerten X =x 1 ,x 2 ,...x n und Y =j 1 ,j 2 ,...j n entsprechende Funktionswerte.

Funktionsglättung, gegeben durch eine Wertetabelle an ungleich beabstandeten Punkten, unter Verwendung eines Polynoms ersten Grades, aufgebaut nach k (mindestens drei Punkte) zu aufeinanderfolgenden Punkten nach der Methode der kleinsten Quadrate (Abb. 2.13).

Reis. 2.13. Datenglättung

Beim k= 3 - für jeweils drei aufeinanderfolgende Punkte (x j -2 , j j-2),( x j-1 , j j-1), ( x j , j j) zum j=3,...n eine Folge von Polynomen ersten Grades wird konstruiert W j ( x)=m j x+b j, wobei an diesen Stellen die kleinste Abweichung von den Vorgegebenen im Sinne der kleinsten Quadrate angegeben wird.

Definition von Koeffizienten m j und b j Polynom W j ( x) nach der Methode der kleinsten Quadrate hergestellt.

Erforderliche geglättete Werte z j = W j ( x) = m j x + b j berechnet nach der Formel:

2.6. Datenhochrechnung (Vorhersage)

Bei der Extrapolation aus einer Reihe gegebener Punkte wird eine bestimmte Zahl errechnet N nachfolgende Punkte.

Auf Abb. 2.14 die durchgezogene Linie zeigt den Graphen der Funktion, die die Lage der gegebenen Punkte beschreibt, die gepunktete Linie zeigt die Vorhersage (Extrapolation des Graphen).

Reis. 2.14. Daten-Extrapolation

2.7. Numerische Differenzierung

Geometrische Interpolation der ersten Ableitung - sie ist gleich der Tangente der Steigung der Tangente.

Wenn Sie die Ableitung einer durch eine Tabelle gegebenen Funktion berechnen, müssen Sie die Werte der Funktion bestimmen j links und rechts gleich weit von diesem Wert entfernt x , für die wir den Wert der Ableitung berechnen wollen, und dividieren ihre Differenz durch h (In der Praxis läuft dies auf eine ungefähre Bestimmung der Tangente der Steigung der Tangente hinaus, je kleiner h , desto genauer das Ergebnis (Abb. 2.15):


Reis. 2.15. Numerische Differenzierung

.

Werte kann durch Interpolation gefunden werden.

2.8. Berechnung eines bestimmten Integrals

Die geometrische Interpretation eines bestimmten Integrals ist die Fläche der geometrischen Figur, die durch den Graphen des Integranden und die x-Achse im Intervall gebildet wird.

Ein einfacher und gleichzeitig guter Weg ist folgender: Das Integrationssegment wird in mehrere gleich kleine Intervalle unterteilt. Das Integral über jedes kleine Intervall wird ungefähr gleich dem Produkt aus der Länge des Intervalls und dem Mittelwert des Integranden an dessen Anfang und Ende betrachtet. Diese Methode wird aufgerufen trapezförmige Methode , weil das Ergebnis so ist, als ob in jedem kleinen Intervall der Bogen des Graphen durch seine Sehne ersetzt wird und die Fläche unter diesem Bogen (der Wert des Integrals) durch die Fläche des resultierenden Trapezes mit vertikalen Basen ersetzt wird ( Abb. 2.16).

Reis. 2.16. Trapezverfahren

Die entsprechende Formel sieht so aus:

wo es der Kürze halber bezeichnet wird.

Eine noch effizientere Formel kann erhalten werden, wenn die Kurve auf einem kleinen Intervall durch eine Parabel ersetzt wird, d.h. quadratischer Abhängigkeitsgraph.

Teilen wir das Integrationssegment ab x = a Vor x= b in eine gerade Anzahl gleicher Intervalle. Intervallgrenzen: . Geben Sie die Länge des Intervalls an h , so .

Diese Formel heißt Simpsons Formel . Die Vorteile der Simpson-Formel gegenüber der Trapez-Formel werden mit zunehmender Anzahl besonders deutlich n Splitting-Intervalle. Es lässt sich zeigen, dass in diesem Fall der Fehler der Trapezformel umgekehrt proportional abnimmt n 2 , und der Fehler der Simpson-Formel ist umgekehrt proportional zu n 4 .

2.9. Numerische Lösung von Differentialgleichungen

Differentialgleichung erster Ordnung: ,

wo j ist eine unbekannte Funktion aus x .

Üblicherweise wird angenommen, dass diese Gleichung bezüglich der Ableitung lösbar ist, d.h. sieht aus wie: . Um die Gleichung zu lösen, müssen die Anfangsbedingungen eingestellt werden: x = x 0 und j = j 0 .

Wenn die Gleichung aussieht und die Anfangsbedingungen gegeben sind x=x 0 und j=j 0 , dann Ersetzen der Werte x 0 und j 0 in die Funktion finden wir den Wert der Ableitung am Punkt x 0: .

Funktionswert: , wobei D x - kleine Erhöhung x .

Daher der Wert der Funktion j 1 = j(x 1) = ,

wo x 1 = x 0+D x .

Nun, nehmen wir den Punkt ( x 1 ,j 1) Für das Original können Sie auf genau die gleiche Weise einen Punkt erhalten j 2 = j(x 2) = , wo x 2 = x 1+D x . So können Sie Schritt für Schritt die Werte der Funktion für verschiedene nacheinander berechnen x .

Ein Beispiel für eine Differentialgleichung erster Ordnung ist die grundlegende Zuggleichung: , wo - spezifische resultierende Kraft, abhängig von der Geschwindigkeit.

Die Konstruktion der Zuggeschwindigkeitskurve als Funktion der zurückgelegten Strecke basiert auf der grafischen oder analytischen Integration der Hauptzugbewegungsgleichung:

, wobei die spezifische resultierende Kraft ist. (ein)

Zur grafischen Integration der Grundgleichung der Zugbewegung wurden verschiedene Verfahren entwickelt (Lipets-Verfahren, Uprein-Verfahren), die auf der Approximation des Geschwindigkeitsverlaufs durch Tangentensegmente (Lipets) oder Kreisbögen (Uprein) beruhen ).

Analytische Integrationsmethoden sind in der Regel mit der Nutzung verbunden Euler-Methode und auf dieser Grundlage wird in voller Übereinstimmung mit den aus der Mathematik bekannten Bestimmungen auf die Genauigkeit der Konstruktion der Kurve geschlossen.

Das Euler-Strichlinienverfahren basiert auf der Idee, eine Lösung einer Differentialgleichung grafisch zu konstruieren. Dieses Verfahren bietet gleichzeitig eine Möglichkeit, die gewünschte Funktion in numerischer (tabellarischer) Form zu finden.

Die Idee des Verfahrens besteht darin, dass bei einem kleinen Änderungsintervall der unabhängigen Variablen die Integralkurve der Differentialgleichung durch ein gerades Liniensegment (Tangente) ersetzt wird.

Von hier aus kann der Vorgang für das Intervall usw. wiederholt werden. Anzahl h ist ein Tabellenschritt.

Arbeitsformel zur Ermittlung von Werten j nach dem Euler-Verfahren hat die Form , wo

Die geometrische Integralkurve wird durch eine gestrichelte Linie namens Euler-Strichlinie ersetzt (Abb. 2.17).

Das Euler-Verfahren hat eine geringe Genauigkeit, außerdem nimmt der Fehler jedes neuen Schritts im Allgemeinen systematisch zu. In diesem Fall ist die akzeptable Methode zur Bewertung der Genauigkeit die Doppelzählungsmethode - mit einer Stufe h und mit einem Schritt h/ 2. Die Übereinstimmung der Dezimalstellen in den auf zwei Arten erhaltenen Ergebnissen gibt einen natürlichen Grund, sie als richtig zu betrachten. Der Methodenfehler ist proportional h2 . Es gibt verschiedene Verfeinerungen des Euler-Verfahrens, die seine Genauigkeit erhöhen, sodass der Fehler des Verfahrens proportional wird h 3 .

Reis. 2.17. Integralkurve und polygonaler Euler

Auf Abb. 2.18 zeigt die Geschwindigkeitskurve, aufgebaut nach dem Rechenschema des Euler-Verfahrens.

Reis. 2.18. Das vorgeschlagene Schema zum Erstellen einer Geschwindigkeitskurve

In diesem Fall basieren alle Methoden der analytischen und grafischen Integration der Grundgleichung der Zugbewegung auf der Implementierung eines anderen Rechenschemas.

Auf Abb. 2.19 zeigt die gemäß dem tatsächlich implementierten Algorithmus konstruierte Geschwindigkeitskurve.

Reis. 2.19. Das eigentliche Schema zur Darstellung der Geschwindigkeitskurve

Wie Sie sehen, stimmt die Konstruktion nur im ersten Schritt überein, und bei den nächsten Schritten unterscheiden sich die Prinzipien für die Konstruktion der Kurve. Der tatsächliche Konstruktionsfehler ist im zweiten Fall nicht nur geringer als im ersten, sondern hat auch eine deutliche Tendenz zur weiteren Abnahme.

Der Grund für diese Diskrepanz ist wahrscheinlich folgender.

Bei der Konstruktion der Geschwindigkeitskurve wird die Grundgleichung der Zugbewegung auf die Form gebracht

oder 2)

Diese Gleichung unterscheidet sich von Gleichung 1, für die eigentlich das Euler-Verfahren vorgesehen ist. Gleichzeitig kann die Ableitung (der Tangens der Steigung der Tangente in der geometrischen Interpretation) zunächst nicht bestimmt werden, sondern wird durch Auswahl des Inkrements der einzigen unabhängigen Variablen berechnet v . Funktionale Abhängigkeit der Größe der Ableitung vom Weg S ist nicht in der rechten Seite von Gleichung 2 enthalten. Dies ist eine Konstante, die von der reduzierten Neigung unter dem Zug abhängt und sich nur ändert, wenn sie sich ändert, wobei alle Eigenschaften einer Konstante beibehalten werden.

Gleiches gilt für die Konstruktion des Geschwindigkeitsverlaufs durch Integration der Grundgleichung der Zugbewegung über die Zeit, wenn für ein bestimmtes Zeitintervall auch der Gleisabstand entsprechend dem Geschwindigkeitsabstand gewählt wird.

Die Grundgleichung der Zugbewegung kann nur über die Geschwindigkeit integriert werden, die einzige wirklich unabhängige Variable, die darin enthalten ist, während das Euler-Verfahren eine Integration über den Weg annimmt.

Die Schätzung der tatsächlichen Genauigkeit der Konstruktion der Geschwindigkeitskurve gehört zum Bereich der statistischen Forschung. Praktisch alle Anfangsdaten der Traktionsberechnung, mit Ausnahme der Daten zum Längsprofil und Gleisplan, sind durchschnittlich.

Daher ist die Erhöhung der Genauigkeit der Traktionsberechnung als Befreiung der verwendeten Rechentechnik von eigenen Fehlern, Annahmen und Vereinfachungen zu verstehen, um sich dem mathematisch erwarteten Ergebnis wenn nicht exakt, so doch anzunähern.

Der moderne Entwicklungsstand der Computertechnik beseitigt nahezu alle Beschränkungen, um die Genauigkeit der Traktionsberechnung in diesem Sinne zu verbessern.

Die Genauigkeit der Konstruktion der Geschwindigkeitskurve hängt wesentlich vom Integrationsschritt ab - es gibt jetzt keine Hindernisse mehr, den Schritt zu reduzieren.

Die Konstruktionsgenauigkeit kann durch Implementierung von Algorithmen mit Rückgaben erhöht werden, wenn nach der Berechnung des Geschwindigkeitsinkrements entlang der Tangente, die am Anfang des Intervalls erstellt wurde, das Inkrement entlang der Tangente in seinem mittleren Teil mit Wiederholungen neu berechnet wird, bis sich die numerische Lösung stabilisiert.

Die Grenze zur Erhöhung der Genauigkeit liegt wahrscheinlich in der Implementierung des Algorithmus mit Rückgaben bei der Neuberechnung des Geschwindigkeitsinkrements nicht im Hinblick auf den Wert der Resultierenden bei der Durchschnittsgeschwindigkeit , und gemäß dem mittleren Vorzeichen der Resultierenden , wo sind die Anfangs- und Endgeschwindigkeiten auf dem Intervall.

Alle diese Algorithmen sind unter modernen Bedingungen leicht zu implementieren.

Aus Sicht der Organisation des Berechnungsprozesses ist die attraktivste Wahl das Zeitinkrement als Integrationsschritt. In diesem Fall werden unter dem Gesichtspunkt der Genauigkeit und Geschwindigkeit des Algorithmus das Geschwindigkeitsinkrement und dementsprechend der Pfad bei jedem Berechnungsschritt automatisch optimiert.

Bei niedrigen Geschwindigkeiten sind die Weginkremente auch klein, was eine hohe Konstruktionsgenauigkeit bietet. Wenn die Geschwindigkeit des Zuges zunimmt, nehmen die Inkremente des Gleises zu, was die Baugeschwindigkeit erhöht. In diesem Fall sind die Geschwindigkeitsinkremente klein und beginnen abzunehmen, wenn sie sich der konstanten Geschwindigkeit nähern, wodurch das Problem erzwungener Änderungen des Integrationsschritts bei unterschiedlichen Zuggeschwindigkeiten beseitigt wird.

Auf Abb. 2.20 zeigt die Graphen der Weg- und Geschwindigkeitsinkremente, die durch Konstruktion der Kurve durch analytische Integration der Grundgleichung der Zugbewegung in Zeit (min) auf der Baustelle bei Beschleunigung des Zuges auf eine konstante Geschwindigkeit erhalten wurden.

Dieser Ansatz wird im bekannten Traktionsberechnungsprogramm "ERA-TEP" implementiert - einem Standardprogramm der JSC Russian Railways (V.A. Anisimov, Far East State University of Transportation).

Reis. 2.20. Geschwindigkeitskurve (a) und Diagramme der Inkremente von Weg und Geschwindigkeit als Funktion der zurückgelegten Entfernung (b)

2.10. Geländemodellierung

Das Endergebnis der ingenieurgeodätischen und ingenieurgeologischen Untersuchungen liegt derzeit vor Digitales Geländemodell .

Ein digitales Geländemodell (DGM) ist eine Menge, deren Elemente topografische und geodätische Informationen über das Gelände sind. Es enthält:

Metrische Informationen - geodätische Raumkoordinaten von charakteristischen Punkten des Reliefs und der Lage;

Syntaktische Informationen zur Beschreibung der Verbindungen zwischen Punkten - die Grenzen von Gebäuden, Wäldern, Ackerland, Stauseen, Straßen, Wassereinzugs- und Überlauflinien, Neigungsrichtungen zwischen charakteristischen Punkten an Hängen usw.;

Semantische Informationen, die die Eigenschaften von Objekten charakterisieren - technische Parameter von Ingenieurbauwerken, geologische Eigenschaften von Böden, Daten über Bäume in Wäldern usw.;

Strukturinformationen, die die Beziehung zwischen verschiedenen Objekten beschreiben - die Beziehung von Objekten zu einer beliebigen Menge: einzelne Punkte der Eisenbahnlinie, Gebäude und Strukturen der Siedlung, Gebäude und Strukturen der entsprechenden Industrien usw.;

Allgemeine Informationen - Name des Standorts, Koordinaten- und Höhensystem, Nomenklatur.

Topografisches DGM charakterisiert die Situation und das Gelände. Es besteht aus einem digitalen Geländemodell (DGM) und einem digitalen Geländekontur(lage)modell (DTM). Zusätzlich kann der DTM um ein Special Engineering Model (CMI) ergänzt werden.

In der Ingenieurpraxis wird häufig eine Kombination aus digitalen Modellen verwendet, die Situation, Relief, hydrologische, ingenieurgeologische, technische, wirtschaftliche und andere Indikatoren charakterisieren. Ein auf einem Maschinenmedium in bestimmten Strukturen und Codes aufgezeichnetes digitales Geländemodell ist eine elektronische Karte (Abb. 2.21).

Reis. 2.21. Elektronische Karte basierend auf DSM, die aus Laserscandaten gewonnen wurde

Bei der Lösung ingenieurwissenschaftlicher und geodätischer Probleme am Computer wird eine mathematische Interpretation digitaler Modelle verwendet. Sie rufen Sie an mathematisches Geländemodell (MMM).

Computergestütztes Design auf der Grundlage von DMM und MMM reduziert die Arbeits- und Zeitkosten um das Zehnfache im Vergleich zur Verwendung von topografischen Karten und Plänen aus Papier für diese Zwecke.

Ausgangsdaten für die Erstellung digitaler Geländemodelle sind die Ergebnisse einer topografischen Aufnahme, Daten zur Geologie und Hydrographie des Gebietes.

Digitales Höhenmodell Terrain (DTM) ist ein Array von Vermessungspunktkoordinaten X ,Y ,H .

Mathematisches Reliefmodell(DRM) kombiniert ein digitales Höhenmodell und Methoden zur Approximation von Vermessungspunkten und Interpolation der Bodenoberfläche zwischen ihnen.

Es gibt eine große Anzahl von DTM- und MTM-Typen, die sich jeweils in der Art und Weise der Annäherung des Reliefs, das durch das Netzwerk von Vermessungspunkten modelliert wird, und den Regeln für die Annäherung an Vermessungspunkte und die Interpolation - die Reihenfolge der Berechnung der Höhe - unterscheiden H Punkt gegeben durch Koordinaten X, Y im allgemeinen Fall, das heißt, wenn der angegebene Punkt mit keinem der Vermessungspunkte zusammenfällt.

Lineare und Spline-Interpolation von Höhen ist möglich.

Mit Hilfe eines digitalen Höhenmodells ist es möglich, ein Längsprofil der Erde in beliebiger Richtung zu erhalten (Abb. 2.22).

Reis. 2.22. Digitales Höhenmodell und Längsprofil der Erde in einer bestimmten Richtung

Am gebräuchlichsten ist das Triangulations-Geländemodell ( ZINN ) mit linearer Interpolation der Höhen.

Die Essenz des Modells ZINN in seinem Namen - "Irregular triangular network" (im englischen Original - Trianguliertes unregelmäßiges Netzwerk ). In seiner räumlichen Ausprägung handelt es sich um ein Netz von Dreiecken mit Höhenmarkierungen an den Knotenpunkten, was uns erlaubt, die simulierte Oberfläche facettenreich darzustellen (Abb. 2.23).

Reis. 2.23. Beispiel Triangulation

Die Aufgabe, ein Triangulationsmodell zu konstruieren, wurde erstmals 1934 in der Arbeit des sowjetischen Mathematikers B.N. Delaunay.

Um das Delaunay-Triangulationsverfahren zu verstehen, ist es notwendig, mehrere Definitionen einzuführen.

Definition 1. Ein planarer Graph heißt Triangulierung, dessen innere Bereiche alle Dreiecke sind (Abb. 2.23).

Definition 2. Das Problem der Konstruktion einer Triangulation aus einer gegebenen Menge zweidimensionaler Punkte ist das Problem der Verbindung gegebener Punkte durch sich nicht schneidende Segmente, so dass ein System sich nicht schneidender Dreiecke entsteht. Die Aufgabe, eine Triangulation basierend auf der anfänglichen Menge von Punkten zu konstruieren, ist mehrdeutig, d.h. hat viele Lösungen.

Definition 3. Triangulation wird als optimal bezeichnet, wenn die Summe der Längen aller Kanten unter allen möglichen Triangulationen minimal ist, die auf denselben Startpunkten aufgebaut sind (in diesem Fall fällt keiner der gegebenen Triangulationspunkte in den Kreis, der um ein konstruiertes Dreieck herum beschrieben wird) ( Abb. 2.24) .

Reis. 2.24. Delaunay-Triangulation

Alle derzeit bekannten Computer Aided Design (CAD)-Systeme unterstützen die Erstellungsfunktion ZINN .

2.11. Simulation eines Längsprofils und Plans bei der Rekonstruktion von Eisenbahnen

Während des Betriebs, unter dem Einfluss von fahrenden Zügen und Naturereignissen, verliert die Achse des Eisenbahngleises ihre korrekte geometrische Form im Grundriss und im Längsprofil, was zu einer Verschlechterung der Dynamik des Zugverkehrs, einem erhöhten Verschleiß der Schienen und Rollmaterial. Bei Reparaturen und Rekonstruktionen der Straße werden der Plan und das Längsprofil regelmäßig in die richtige geometrische Form gebracht, was die Erstellung geeigneter Berechnungen und die Modellierung der Ausgangsdaten erfordert.

Beim Umbau von Eisenbahnen sind die Ausgangsdaten für Berechnungen die Ergebnisse der Vermessung des Bestandsgleises im Grundriss und im Längsschnitt.

Das digitale Modell des Längsprofils (Abb. 2.25) ermöglicht Optimierungs- und interaktive Entwurfsmethoden, um Schienenkopfmarkierungen zwischen Vermessungspunkten zu erhalten. Als Achse der Bahn wird immer die Abszisse genommen.

Reis. 2.25. Simulation des Längsprofils von Eisenbahnen

Die Designmarkierungen des Längsprofils werden unter Berücksichtigung des Vorhandenseins vertikaler Kurven berechnet, die an den Unterbrechungen der Designlinie angeordnet sind, wenn der Unterschied in den Neigungen der Verbindungselemente einen bestimmten Wert erreicht, genauer gesagt, wenn die Korrektur von der vertikalen Kurve überschreitet 0,01 m und die algebraische Steigungsdifferenz , wo R v- Radius der vertikalen Kurve (Abb. 2.26).

Reis. 2.26. Vertikale Kurve, Berechnungsschema

Im Allgemeinen wird die Bildmarke durch den folgenden Algorithmus bestimmt:

Profilbruchstelle;

- Voreingenommenheit j -tes Profilelement;

- Neigungsunterschied, ‰;

Wenn , dann wird die Korrektur sonst nicht eingeführt

- Markierung am Konstruktionspunkt ohne Berücksichtigung der vertikalen Kurve;

Tangente der vertikalen Kurve;

wenn die Korrektur nicht eingegeben wird - der Punkt liegt außerhalb der vertikalen Kurve), sonst

- Korrektur von der vertikalen Kurve;

wenn anders

Die Durchführung einer solchen Berechnung im automatischen Modus setzt das Vorhandensein eines digitalen Modells des Längsprofils voraus. Bei der „manuellen“ Berechnung wird implizit auch ein solches Modell (Rechenschema) erstellt.

Planmodellierung ermöglicht es Ihnen, die Parameter seiner Elemente zu berechnen - gerade, kreisförmige und Übergangskurven.

Das Planmodell des Bestandsgleises in einem rechtwinkligen Koordinatensystem (Abb. 2.27) setzt die Verwendung eines ähnlichen Koordinatenmodells des Projekttrassenplans (Abb. 2.28) voraus. Das „manuelle“ Arbeiten mit solchen Modellen ist so zeitaufwändig, dass dieser Ansatz vor dem Aufkommen von Computern nicht verwendet wurde.

Reis. 2.27. Vorhandenes Gleisplankoordinatenmodell

Reis. 2.28. Koordinatenmodell des Projektpfadplans

Für Berechnungen (massiv und arbeitsintensiv) wurden Planmodelle (Bestands- und Projektgleise) in einem krummlinigen Koordinatensystem verwendet, wobei die Achse des Bestandsgleises als Abszissenachse genommen wurde.

Es wurden zwei Arten von Modellen verwendet – das Winkeldiagramm und das Krümmungsdiagramm (Pfeil).

Die Verwendung dieser Modelle (auf Kosten einiger Annahmen und Vereinfachungen) ermöglicht es Ihnen, die Parameter der Planelemente "manuell" zu berechnen, unter anderem unter Verwendung einfacher und bequemer grafisch-analytischer Methoden.

Im Winkeldiagramm (Abb. 2.29) sind die Drehwinkel der Kurve entlang der y-Achse aufgetragen.

Auf geraden Linien ist der Winkel konstant,

Auf kreisförmigen Kurven - ändert sich linear,

Auf den Übergangskurven - die Änderung des Drehwinkels kann mit einigen Annahmen durch eine quadratische Parabel beschrieben werden.

Reis. 2.29. Winkeldiagramm

Um der Achse des Pfads die richtige geometrische Form zu geben, müssen Verschiebungen (Begradigungen) ihrer Achse um einen bestimmten Betrag durchgeführt werden, der durch die Berechnung bestimmt wird.

Bei der Verwendung von Winkeldiagrammen beträgt der Betrag der Verschiebung:

, wo Ug , U v – Rotationswinkel des Entwurfs und der vorhandenen Gleisachse in Abhängigkeit von der Entfernung vom Messbeginn (Winkeldiagramme), S - Entfernung vom Beginn der Vermessung bis zum berechneten Punkt.

Die grafische Interpretation des Integrals ist die Fläche. Also - der Unterschied zwischen den Bereichen des Designs und bestehenden Winkeldiagrammen.

Auf der Krümmungskurve (Pfeile) (Abb. 2.30) ist die Krümmung der Bahn (Krümmungspfeile) entlang der y-Achse aufgetragen. Die Krümmung ist der Kehrwert des Radius. Pfeil (Abb. 2.31), f - Abstand von der Achse des Pfades zu einer Sehne einer bestimmten Länge a , (normalerweise 20 m). Ein Krümmungsdiagramm unterscheidet sich von einem Pfeildiagramm darin, dass die Krümmung an einem Punkt definiert ist, während ein Pfeil an einer Sehne definiert ist. Unterschiede treten nur in den Übergangszonen von einer geraden Linie zu einer Übergangskurve und von einer Übergangskurve zu einer kreisförmigen Kurve auf.

Reis. 2.30. Krümmungsdiagramm (Pfeile)

Reis. 3.31. Messung von Biegepfeilen

Wenn der Pfeil in Millimetern gemessen wird, dann mit a = 20m: .

Für einen Designpfad, der in die richtige geometrische Position passt:

Auf geraden Linien - Krümmung (Pfeil) ist gleich Null,

Auf kreisförmigen Kurven - die Krümmung (Pfeil) ist konstant,

Auf Übergangskurven - Krümmung (Pfeil) ändert sich linear.

Verschiebung , wo: Kg , Kv ist die Krümmung der Bahnachse im Entwurf und vorhandene Positionen in Abhängigkeit von der Entfernung vom Beginn des Erfassungsbereichs, s ; S - die Entfernung vom Anfang des Abschnitts bis zum berechneten Punkt.

Das Doppelintegral wird berechnet, indem die Flächen des Krümmungsdiagramms (Pfeile) zweimal aufsummiert werden.

3. MATHEMATISCHE METHODEN

3.1. Implementierung des numerischen Modells auf einem Computer

Um eine besonders optimale Designlösung zu finden, ist zwangsläufig ein Variantenansatz erforderlich.

Die Verwendung mathematischer Methoden ermöglicht es uns, die Anzahl der verglichenen Optionen auf das notwendige und ausreichende Minimum zu reduzieren, sie ist jedoch immer groß, und nur der Einsatz von Computertechnologie ermöglicht es uns, das Problem in einer akzeptablen Zeit zu lösen.

Der Kostenfaktor Rechenzeit ist von entscheidender Bedeutung bei der Auswahl einer Methode zur Lösung eines konkreten Anwendungsproblems. „Von einer effektiven Lösungsmethode kann nur gesprochen werden, wenn sie Probleme dieser Art tatsächlich auf realen Computern in echter Rechenzeit löst“ .

Dementsprechend unterscheidet sich das Konzept einer Methode in der Computermathematik von der traditionellen, dh von ihrer Darstellung als Folge von Anweisungen, deren Ausführung in endlich vielen Schritten zwangsläufig zum gewünschten Ergebnis führt.

Sie sprechen in der Regel nicht von einer Methode, sondern von einem allgemeinen Ansatz zur Lösung eines bestimmten Problems, der im Rahmen verschiedener Rechenschemata (numerisch angewandte Methoden) implementiert werden kann, unter denen es ein optimales gibt, und diese Optimalität ist immer im Sinne eines Minimums an Rechenzeit zu verstehen ( ceteris paribus).

Apropos „spezifisches Designproblem“, es ist notwendig, seine formalen Merkmale in Bezug auf beispielsweise die Wahl der kontrollierten Variablen, die objektive Funktion der Aufgabe, das System der den kontrollierten Variablen auferlegten Beschränkungen streng zu definieren.

Das numerische Verfahren ist noch nicht programmierbar Algorithmus (die aus getrennten Operationen besteht, die in einer einwertigen Folge ablaufen), hat einen bestimmten Anfang sowie ein Ende, das nach einer endlichen Anzahl von Schritten erreichbar ist, und kann daher im Prinzip von einer Maschine realisiert werden.

Methodenauswahlkriterien. Zur Lösung des Problems gibt es in der Regel mehrere Methoden (Ansätze). Die Wahl eines bestimmten Verfahrens zur numerischen Lösung eines Problems und seine abschließende Transformation in einen programmierbaren Algorithmus ist immer ein Optimierungsversuch, und als Nebenbedingungen wirken die anfänglichen Vorgaben und Nebenforderungen, von denen die wichtigsten die folgenden sind:

Startpositionen:

Darstellung des Problems und Annahmen über einen rationalen Lösungsansatz;

Zusatzinformationen zu den Quelldaten (Zahlenraum, Art des Zahlenmaterials etc.);

Eigenschaften der Computertechnologie (Geschwindigkeit, Speicher usw.);

Datendarstellung, Genauigkeit, Rundung etc.

Anforderungen:

Besondere Anforderungen an Ausgabedaten (z. B. Genauigkeitsanforderungen, Ausgabe von Zwischenergebnissen, Ausgabe von Grafiken, auch interaktive, etc.);

Der Grad der Universalität (ob eine einzelne Aufgabe gelöst werden soll oder universelle Software in Bezug auf einen gültigen Datensatz erforderlich ist);

Kostenminimierung (Rechenzeit).

Diese Bedingungen überlappen sich teilweise (Widerspruch) und versuchen daher, bei dem Versuch, sie zu erfüllen, ein bestimmtes Optimum zu erreichen. Verwenden Sie dazu eine Reihe von Regeln, die durch gesunden Menschenverstand und vorherige Rechenerfahrung bestimmt werden.

Grundlage für die Methodenwahl ist Direktauftragsprinzip : Sie müssen möglichst eine Methode wählen, die genau die Aufgabe löst und nicht über einige Teilaufgaben zu einer Lösung führt. „Mathematisch elegante“ Lösungen sind oft unsichtbar hinsichtlich Fehlerfortpflanzung und Stabilität, numerisch ungünstig.

Die wichtigsten Gründe für eine übermäßige Fehlerhäufung sind die häufige Verwendung von Differenzen (führt zum Verlust signifikanter Stellen) und die Division durch Zahlen unbekannter Ordnung (führt zum Überlaufen des Bitgitters) - dies sollte durch die richtige Organisation vermieden werden des Programms.

3.2. Zielfunktion. Einschränkungen

In allen Tätigkeitsbereichen müssen ständig Entscheidungen getroffen werden. In den Fällen, in denen die Situation, in der sie akzeptiert werden, formalisiert werden kann, kann es sehr nützlich sein, den mathematischen Apparat zu verwenden.









































Bei praktischen Problemen auftretende Kurven und Flächen haben oft eine recht komplexe Form, die eine allgemeingültige analytische Spezifikation als Ganzes mit Hilfe elementarer Funktionen nicht zulässt. Daher sind sie aus relativ einfachen glatten Fragmenten zusammengesetzt - Segmenten (Kurven) oder Schnitten (Flächen), die jeweils recht zufriedenstellend mit elementaren Funktionen von einer oder zwei Variablen beschrieben werden können. Gleichzeitig ist es ganz natürlich zu fordern, dass glatte Funktionen, die zur Konstruktion von Teilkurven oder Flächen verwendet werden, eine ähnliche Natur haben, beispielsweise Polynome gleichen Grades sein müssen. Und damit die resultierende Kurve oder Oberfläche ausreichend glatt ist, ist es notwendig, an den Verbindungsstellen der entsprechenden Fragmente besonders vorsichtig zu sein. Der Grad der Polynome wird nach einfachen geometrischen Überlegungen gewählt und ist in der Regel klein. Für eine sanfte Änderung der Tangente entlang der gesamten zusammengesetzten Kurve reicht es aus, die Verbindungskurven durch Polynome dritten Grades, kubische Polynome, zu beschreiben. Die Koeffizienten solcher Polynome können immer so gewählt werden, dass die Krümmung der entsprechenden zusammengesetzten Kurve stetig ist. Kubische Splines, die beim Lösen eindimensionaler Probleme entstehen, können an die Formgebung von Fragmenten zusammengesetzter Oberflächen angepasst werden. Und hier treten ganz natürlich bikubische Splines auf, die in jeder der beiden Variablen durch Polynome dritten Grades beschrieben werden. Das Arbeiten mit solchen Splines erfordert viel mehr Berechnungen. Aber ein richtig organisierter Prozess wird es ermöglichen, die ständig wachsenden Möglichkeiten der Computertechnologie maximal zu berücksichtigen. Spline-Funktionen Let auf dem Segment , dh Bemerkung. Der Index (t) der Zahlen a^ zeigt dies an. dass der Koeffizientensatz, durch den die Funktion S(x) auf jedem Teilsegment D bestimmt wird, sein eigener ist. Auf jedem der Segmente D1 ist der Spline 5(x) ein Polynom vom Grad p und wird auf diesem Segment durch den Koeffizienten p + 1 bestimmt. Gesamtteilsegmente - dann. Um den Spline vollständig zu bestimmen, muss man also (p + 1) dann Zahlen finden Bedingung) bedeutet die Stetigkeit der Funktion S(x) und ihrer Ableitungen an allen internen Gitterknoten w. Die Anzahl solcher Knoten ist m – 1. Um die Koeffizienten aller Polynome zu finden, werden somit p(m – 1) Bedingungen (Gleichungen) erhalten. Für eine vollständige Definition des Splines reichen (Bedingungen (Gleichungen)) nicht aus. Die Wahl zusätzlicher Bedingungen wird durch die Art des betrachteten Problems und manchmal einfach durch den Wunsch des Benutzers bestimmt. SPLINE-THEORIE Lösungsbeispiele Am häufigsten werden Interpolations- und Glättungsprobleme betrachtet, wenn es erforderlich ist, den einen oder anderen Spline aus einer gegebenen Reihe von Punkten auf einer Ebene zu erstellen.Bei Interpolationsproblemen ist es erforderlich, dass der Spline-Graph durch Punkte verläuft, die ihren Koeffizienten m + 1 zusätzliche Bedingungen (Gleichungen) auferlegt. Die verbleibenden p - 1-Bedingungen (Gleichungen) für die eindeutige Konstruktion eines Splines werden am häufigsten in Form von Werten der unteren Ableitungen des Splines an den Enden des betrachteten Segments festgelegt [a, 6] - Grenze ( Randbedingungen). Durch die Möglichkeit, verschiedene Randbedingungen auszuwählen, können Sie Splines mit einer Vielzahl von Eigenschaften erstellen. Bei Glättungsproblemen wird ein Spline so aufgebaut, dass sein Graph in der Nähe der Punkte (i "" Y "), * = 0, 1, ..., m verläuft und nicht durch sie hindurchgeht. Das Maß dieser Nähe kann auf unterschiedliche Weise definiert werden, was zu einer beträchtlichen Vielfalt von Glättungs-Splines führt. Die beschriebenen Wahlmöglichkeiten bei der Konstruktion von Spline-Funktionen sind in ihrer Vielfalt noch lange nicht erschöpft. Und wurden anfangs nur stückweise polynomische Spline-Funktionen betrachtet, so tauchten mit zunehmendem Anwendungsbereich Splines auf, die auch von anderen elementaren Funktionen „verklebt“ wurden. Kubische Splines für die Interpolation Formulierung des Interpolationsproblems Sei das Gitter w auf dem Intervall [a, 6) gegeben. Betrachten Sie ein Zahlenproblem. Konstruieren Sie eine Funktion, die auf dem Segment (a, 6) glatt ist und an den Knoten des Gitters o die gegebenen Werte annimmt, d. h. „Indem Sie der zu konstruierenden Funktion zusätzliche Bedingungen auferlegen, kann man die notwendige Eindeutigkeit erreichen Anwendungen wird es oft notwendig, eine analytisch gegebene Funktion durch eine Funktion mit vorgeschriebenen hinreichend guten Eigenschaften zu approximieren, beispielsweise in Fällen, in denen die Berechnung der Werte einer gegebenen Funktion f(x) an den Punkten Segment [a, 6] mit erheblichen Schwierigkeiten verbunden ist und/oder die gegebene Funktion /(x) nicht die erforderliche Glätte hat, ist es bequem, eine andere Funktion zu verwenden, die die gegebene Funktion gut genug approximiert und frei von ihren Mängeln ist. [a, 6] eine glatte Funktion a(x), die an den Gitterknoten w mit der gegebenen Funktion zusammenfällt /(X). Definition eines interpolierenden kubischen Splines Ein interpolierender kubischer Spline S(x) auf einem Gitter w ist eine Funktion, die 1) auf jedem der Segmente ein Polynom dritten Grades ist, 2) auf dem Segment [a, b] zweimal stetig differenzierbar ist ], also zur Klasse C2[ a, 6] gehört, und 3) die Bedingungen erfüllt. Auf jedem der Segmente ist der Spline S(x) ein Polynom dritten Grades und wird auf diesem Segment durch vier Koeffizienten bestimmt. Die Gesamtzahl der Segmente ist m. Das bedeutet, dass es notwendig ist, um den Spline vollständig zu definieren, 4m Zahlen zu finden. Die Bedingung bedeutet die Stetigkeit der Funktion S (x) und ihrer Ableitungen S "(x) und 5" (x) an allen internen Gitterknoten w. Die Anzahl solcher Knoten ist m - 1. Um also die Koeffizienten aller Polynome zu finden, werden 3 (m - 1) weitere Bedingungen (Gleichungen) erhalten. Zusammen mit den Bedingungen (2) werden Bedingungen (Gleichungen) erhalten. Randbedingungen (Randbedingungen) Zwei fehlende Bedingungen werden als Einschränkungen für die Werte des Splines und/oder seiner Ableitungen an den Enden des Intervalls angegeben [a, 6]. Beim Konstruieren eines interpolierenden kubischen Splines werden am häufigsten die Randbedingungen der folgenden vier Typen verwendet. A. Randbedingungen des 1. Typs. - Am Ende des Intervalls [a, b] werden die Werte der ersten Ableitung der gewünschten Funktion angegeben. B. Randbedingungen des 2. Typs. - Am Ende des Intervalls (a, 6) werden die Werte der zweiten Ableitung der gewünschten Funktion eingestellt. B. Randbedingungen der 3. Art. werden periodisch genannt. Es ist natürlich, die Erfüllung dieser Bedingungen in Fällen zu fordern, in denen die interpolierte Funktion periodisch mit der Periode T = b-a ist. D. Randbedingungen des 4. Typs. bedürfen eines besonderen Kommentars. Kommentar. An inneren Sepsisknoten ist die dritte Ableitung der Funktion S(x) im Allgemeinen diskontinuierlich. Die Anzahl der Unstetigkeiten der dritten Ableitung kann jedoch durch Verwendung von Bedingungen des 4. Typs reduziert werden. In diesem Fall ist der konstruierte Spline dreimal auf Intervallen stetig differenzierbar Konstruktion eines interpolierenden kubischen Splines Es soll ein Verfahren zur Berechnung der Koeffizienten eines kubischen Splines beschrieben werden, bei dem die Anzahl der zu bestimmenden Größen gleich ist. Auf jedem der Intervalle wird die Interpolations-Spline-Funktion in der folgenden Form gesucht Für Randbedingungen des 1. und 2. Typs hat dieses System die folgende Form, wobei die Koeffizienten von der Wahl der Randbedingungen abhängen. Randbedingungen des 1. Typs: Randbedingungen des 2. Typs: Bei Randbedingungen des 3. Typs wird das Zahlensystem wie folgt geschrieben. Für Randbedingungen des 4. Typs hat das System zur Bestimmung von Zahlen die Form Die Matrizen aller drei linearen algebraischen Systeme sind Matrizen mit diagonaler Dominanz. Diese Matrizen sind nicht entartet, und daher hat jedes dieser Systeme eine eindeutige Lösung. Satz. Ein kubischer Interpolations-Spline, der die Bedingungen (2) und eine Randbedingung von einem der aufgelisteten vier Typen erfüllt, existiert und ist eindeutig. Einen interpolierenden kubischen Spline zu konstruieren bedeutet also, seine Koeffizienten zu finden. Wenn die Koeffizienten des Splines gefunden sind, kann der Wert des Splines S(x) an einem beliebigen Punkt des Segments [a, b] unter Verwendung der Formel ( 3). Für praktische Berechnungen ist jedoch der folgende Algorithmus zum Auffinden der Größe S(x) besser geeignet. Sei x 6 [x“, zunächst werden die Werte A und B nach den Formeln berechnet und dann der Wert 5(x) gefunden: Die Verwendung dieses Algorithmus reduziert den Rechenaufwand zur Ermittlung des Wertes deutlich Benutzer Die Wahl der Randbedingungen und Interpolationsknoten erlaubt bis zu einem gewissen Grad, die Eigenschaften von Interpolations-Splines zu steuern. A. Wahl der Randbedingungen (Randbedingungen). Die Wahl der Randbedingungen ist eines der zentralen Probleme bei der Interpolation von Funktionen. Es gewinnt besondere Bedeutung in dem Fall, wenn es notwendig ist, eine hohe Genauigkeit der Approximation der Funktion f(x) durch den Spline 5(g) nahe den Enden des Segments sicherzustellen [a, 6]. Die Grenzwerte haben einen merklichen Einfluss auf das Verhalten des Splines 5(g) in der Nähe der Punkte a und b, und dieser Effekt schwächt sich schnell ab, wenn wir uns von ihnen entfernen. Die Wahl der Randbedingungen wird oft durch die Verfügbarkeit zusätzlicher Informationen über das Verhalten der zu approximierenden Funktion f(x) bestimmt. Wenn die Werte der ersten Ableitung f "(x) an den Enden des Segments (a, 6) bekannt sind, ist es naheliegend, die Randbedingungen des 1. Typs zu verwenden. Wenn die Werte des zweiten Ableitung f "(x) an den Segmentenden [a, 6] bekannt sind, dann handelt es sich um natürliche Randbedingungen 2. Art. Kann zwischen den Randbedingungen des 1. und 2. Typs gewählt werden, ist den Bedingungen des 1. Typs der Vorzug zu geben. Wenn f(x) eine periodische Funktion ist, dann sollten wir bei den Randbedingungen des 3. Typs aufhören. Liegen keine zusätzlichen Informationen über das Verhalten der zu approximierenden Funktion vor, werden häufig die sogenannten natürlichen Randbedingungen verwendet, wobei jedoch zu beachten ist, dass bei einer solchen Wahl der Randbedingungen die Genauigkeit der Approximation der Funktion f (x) durch den Spline S (x) in der Nähe der Enden des Segments (a, ft] stark abnimmt. Manchmal werden Randbedingungen des 1. oder 2. Typs verwendet, jedoch nicht mit den genauen Werten der entsprechenden Ableitungen, aber mit ihren Differenznäherungen.Die Genauigkeit dieses Ansatzes ist gering.Praktische Erfahrungen mit Berechnungen zeigen, dass in der betrachteten SituationRandbedingungen des 4. Typs die geeignetste Wahl sind. B. Wahl der Stützstellen. Weist die dritte Ableitung f""(x) der Funktion an einigen Stellen des Segments [a, b] einen Sprung auf, so sollten zur Verbesserung der Approximationsqualität diese Stellen in die Anzahl der Stützstellen mit einbezogen werden. Wenn die zweite Ableitung /"(x) unstetig ist, müssen besondere Maßnahmen getroffen werden, um ein Schwingen des Splines in der Nähe der Unstetigkeitsstellen zu vermeiden. Üblicherweise werden die Stützstellen so gewählt, dass die Unstetigkeitsstellen der zweiten Ableitung hineinfallen das Intervall \xif), so dass. und kann durch numerisches Experiment gewählt werden (es reicht oft aus, a = 0,01 zu setzen). Es gibt eine Reihe von Rezepten zur Überwindung der Schwierigkeiten, die auftreten, wenn die erste Ableitung f "(x) ist diskontinuierlich. Als eine der einfachsten können wir Folgendes vorschlagen: Unterteilen Sie das Approximationssegment in Intervalle, in denen die Ableitung stetig ist, und bauen Sie auf jedem dieser Intervalle einen Spline auf. Wahl der Interpolationsfunktion (Plus und Minus) Vorgehensweise 1. Lagrange-Interpolationspolynom Gemäß einem gegebenen Array SPLINE THEORY Lösungsbeispiele (Abb. 3) wird das Lagrange-Interpolationspolynom durch die Formel bestimmt Es ist ratsam, die Eigenschaften des Lagrange-Interpolationspolynoms von zwei entgegengesetzten Positionen aus zu betrachten und die Hauptvorteile getrennt davon zu diskutieren Nachteile. Die Hauptvorteile des 1. Ansatzes: 1) der Graph des Lagrange-Interpolationspolynoms geht durch jeden Punkt des Arrays, 2) die konstruierte Funktion ist leicht zu beschreiben (die Anzahl der Koeffizienten des Lagrange-Interpolationspolynoms auf dem Gitter u ist zu bestimmen). gleich m + 1 ist), 3) die konstruierte Funktion stetige Ableitungen beliebiger Ordnung hat, 4) bei gegebenem Array das Interpolationspolynom eindeutig bestimmt ist. Die Hauptnachteile des 1. Ansatzes: 1) Der Grad des Lagrange-Interpolationspolynoms hängt von der Anzahl der Gitterknoten ab, und je größer diese Zahl ist, desto höher ist der Grad des Interpolationspolynoms und desto mehr Berechnungen sind daher erforderlich, 2 ) das Ändern mindestens eines Punktes im Array erfordert eine vollständige Neuberechnung der Koeffizienten des Lagrange-Interpolationspolynoms, 3) das Hinzufügen eines neuen Punktes zum Array erhöht den Grad des Lagrange-Interpolationspolynoms um eins und führt sogar zu einer vollständigen Neuberechnung seiner Koeffizienten , 4) bei unbegrenzter Netzverfeinerung steigt der Grad des Lagrange-Interpolationspolynoms unendlich an. Das Verhalten des Lagrange-Interpolationspolynoms bei unbegrenzter Netzverfeinerung erfordert im Allgemeinen besondere Aufmerksamkeit. Bemerkungen A. Approximation einer stetigen Funktion durch ein Polynom. Es ist bekannt (Weierstraß, 1885), daß jede stetige (und noch mehr glatte) Funktion auf einem Intervall so gut wie gewünscht auf diesem Intervall durch ein Polynom angenähert werden kann. Lassen Sie uns diese Tatsache in der Sprache der Formeln beschreiben. Sei f(x) eine auf dem Segment [a, 6] stetige Funktion. Dann gibt es für jedes e > 0 ein Polynom Рn(x), so dass für jedes x aus dem Intervall [a, 6] die Ungleichung erfüllt ist (Abb. 4) , es gibt unendlich viele. Auf dem Segment [a, 6] konstruieren wir ein Gitter w. Es ist klar, dass seine Knoten im Allgemeinen nicht mit den Schnittpunkten der Graphen des Polynoms Pn(x) und der Funktion f(x) zusammenfallen (Abb. 5). Daher ist für das genommene Gitter das Polynom Pn(x) kein Interpolationspolynom. Wenn eine stetige Funktion durch ein Jla-grajj-Interpolationspolynom approximiert wird, muss ihr Graph nicht nur nicht an jedem Punkt des Segments [a, b) nahe am Graphen der Funktion f(x) liegen, sondern kann davon abweichen diese Funktion beliebig oft. Lassen Sie uns zwei Beispiele geben. Beispiel 1 (Rung, 1901). Bei unbegrenzter Erhöhung der Knotenzahl für eine Funktion auf dem Intervall [-1, 1] ist die Grenzgleichheit erfüllt (Abb. 6) Beispiel 2 (Berichtein, 1912). Eine Folge von Lagrange-Interpolationspolynomen, die auf einheitlichen Gittern nm für eine stetige Funktion /(x) = |x| konstruiert sind auf dem Segment mit zunehmender Knotenzahl tendiert m nicht zur Funktion f(x) (Abb. 7). Ansatz 2. Stückweise lineare Interpolation Wird die Glätte der interpolierten Funktion aufgegeben, kann das Verhältnis zwischen der Anzahl der Vorteile und der Anzahl der Nachteile merklich in Richtung ersterer verändert werden. Konstruieren wir eine stückweise lineare Funktion, indem wir nacheinander Punkte (xit y,) mit geraden Strecken verbinden (Abb. 8). Die Hauptvorteile des 2. Ansatzes: 1) der Graph einer stückweise linearen Funktion geht durch jeden Punkt des Arrays, 2) die konstruierte Funktion ist leicht zu beschreiben (die Anzahl der Koeffizienten der entsprechenden linearen Funktionen ist für das Gitter zu bestimmen ( 1) ist 2m), 3) die konstruierte Funktion ist durch ein gegebenes Array eindeutig definiert, 4) der Grad der Polynome, die zur Beschreibung der Interpolationsfunktion verwendet werden, hängt nicht von der Anzahl der Gitterknoten ab (gleich 1), 5) einer wird geändert Punkt in der Reihe erfordert die Berechnung von vier Zahlen (die Koeffizienten von zwei geradlinigen Verbindungen, die von dem neuen Punkt ausgehen), 6) das Hinzufügen eines zusätzlichen Punkts zu der Reihe erfordert die Berechnung von vier Koeffizienten. Die stückweise lineare Funktion verhält sich beim Verfeinern des Gitters recht gut. i Der Hauptnachteil des 2. Ansatzes besteht darin, dass die approximierende stückweise lineare Funktion nicht glatt ist: Die ersten Ableitungen erleiden eine Diskontinuität an den Gitterknoten (Interpolationsohren). Ansatz 3. Spline-Interpolation Die vorgeschlagenen Ansätze können kombiniert werden, so dass die Anzahl der aufgeführten Vorteile beider Ansätze erhalten bleibt, während die Anzahl der Nachteile reduziert wird. Dies kann durch Konstruieren einer glatten interpolierenden Spline-Funktion vom Grad p erfolgen. Die Hauptvorteile des 3. Ansatzes: 1) der Graph der konstruierten Funktion geht durch jeden Punkt des Arrays, 2) die konstruierte Funktion ist relativ einfach zu beschreiben (die Anzahl der Koeffizienten der entsprechenden Polynome ist für das Gitter zu bestimmen ( 1) ist 3) die konstruierte Funktion eindeutig durch ein gegebenes Array bestimmt ist, 4) der Grad der Polynome nicht von der Anzahl der Gitterknoten abhängt und sich daher nicht mit ihrer Erhöhung ändert, 5) die konstruierte Funktion stetige Ableitungen nach oben hat bis zur Ordnung p - 1 einschließlich, 6) die konstruierte Funktion hat gute Näherungseigenschaften. Kurzer Hinweis. Der vorgeschlagene Name - Spline - ist kein Zufall - die von uns eingeführten glatten stückweisen Polynomfunktionen und das Zeichnen von Splines sind eng verwandt. Stellen Sie sich ein flexibles, idealerweise dünnes Lineal vor, das durch die Referenzpunkte des Arrays verläuft, das sich auf der (x, y)-Ebene befindet. Nach dem Bernoulli-Euler-Gesetz hat die linearisierte Gleichung eines gekrümmten Lineals die Form Die Funktion S(x), die die Lineale beschreibt, ist ein Polynom dritten Grades zwischen jeweils zwei benachbarten Punkten des Arrays (Stützen) und auf dem gesamten Intervall (a, 6) zweimal stetig differenzierbar. Kommentar. 06 Interpolation einer kontinuierlichen Funktion Im Gegensatz zu Lagrange-Interpolationspolynomen konvergiert eine Folge von kubischen Interpolationssplines auf einem einheitlichen Gitter immer zu einer interpolierten kontinuierlichen Funktion, und mit der Verbesserung der differentiellen Eigenschaften dieser Funktion steigt die Konvergenzrate. Beispiel. Für eine Funktion ergibt ein kubischer Spline auf einem Gitter mit der Knotenzahl m = 6 einen Näherungsfehler in der gleichen Größenordnung wie das Interpolationspolynom Ls(z), und auf einem Gitter mit der Knotenzahl m = 21 ist dieser Fehler gleich so klein, dass es im Maßstab einer gewöhnlichen Buchzeichnung einfach nicht dargestellt werden kann (Abb. 10) (das Interpolationspolynom 1>2o(r) ergibt in diesem Fall einen Fehler von etwa 10.000 W). Eigenschaften eines interpolierten kubischen Splines A. Näherungseigenschaften eines kubischen Splines. Die Approximationseigenschaften des interpolierenden Splines hängen von der Glattheit der Funktion f(x) ab – je höher die Glattheit der interpolierten Funktion, desto höher die Approximationsordnung, und wenn das Netz verfeinert wird, desto höher die Konvergenzrate. Wenn die interpolierte Funktion f(x) auf dem Intervall stetig ist Wenn die interpolierte Funktion f(x) auf dem Intervall [a, 6] eine stetige erste Ableitung hat, also einen Interpolations-Spline, der die Randbedingungen der 1. oder erfüllt 3. Typ, dann gilt für h In diesem Fall konvergiert nicht nur der Spline gegen die interpolierte Funktion, sondern auch die Ableitung des Splines konvergiert gegen die Ableitung dieser Funktion. Wenn der Spline S(x) die Funktion f(x) auf dem Segment [a, b] annähert, und seine erste und zweite Ableitung die Funktion B annähern, bzw. Extremale Eigenschaft eines kubischen Splines. Der interpolierende kubische Spline hat eine weitere nützliche Eigenschaft. Betrachten Sie das folgende Beispiel. Beispiel. Konstruieren Sie eine Funktion /(x), die das Funktional auf der Klasse von Funktionen aus dem Raum C2 minimiert, deren Graphen durch die Punkte des Arrays x verlaufen), die die Randbedingungen erfüllt und ein Extremum (Minimum) für das Funktional liefert. Bemerkung 2. Es ist interessant festzustellen, dass der interpolierende kubische Spline die oben beschriebene extremale Eigenschaft auf einer sehr breiten Klasse von Funktionen hat, nämlich auf der Klasse |0, 5]. 1.2. Kubische Splines glätten Zur Formulierung des Glättungsproblems Gegeben seien ein Gitter und eine Menge von Zahlen. Tatsächlich bedeutet dies, dass für jeden ein Intervall angegeben wird und jede Zahl aus diesem Intervall als Wert von y genommen werden kann, . Es ist beispielsweise bequem, die Werte von y als Ergebnisse von Messungen einer Funktion y(x) für gegebene Werte der Variablen x zu interpretieren, die einen zufälligen Fehler enthalten. Bei der Lösung des Problems der Wiederherstellung einer Funktion aus solchen "experimentellen" Werten ist es kaum ratsam, eine Interpolation zu verwenden, da die Interpolationsfunktion gehorsam bizarre Oszillationen reproduziert, die durch eine zufällige Komponente im Array (y,) verursacht werden. Ein natürlicherer Ansatz basiert auf einem Glättungsverfahren, das darauf ausgelegt ist, das Element der Zufälligkeit als Ergebnis von Messungen irgendwie zu reduzieren. Üblicherweise ist es bei solchen Aufgabenstellungen erforderlich, eine Funktion zu finden, deren Werte für x = x, * = 0, 1, .... m in die entsprechenden Intervalle fallen würden und die darüber hinaus hinreichend gute Eigenschaften aufweisen. Beispielsweise hätte er stetige erste und zweite Ableitungen, oder sein Graph wäre nicht zu stark gekrümmt, also nicht stark oszillierend. Ein Problem dieser Art tritt auch auf, wenn gemäß einem gegebenen (exakten) Array eine Funktion konstruiert werden soll, die durch nicht gegebene Punkte, aber in deren Nähe gehen und sich außerdem ziemlich glatt ändern würde. Mit anderen Worten, die gewünschte Funktion hat das gegebene Array sozusagen geglättet und nicht interpoliert. Gegeben sei ein Gitter w und zwei Zahlenmengen SPLINE THEORIE Lösungsbeispiele Problem. Konstruieren Sie eine glatte Funktion auf dem Segment [a, A], deren Werte an den Knoten des Gitters und von den Zahlen y um die gegebenen Werte abweichen. Das formulierte Glättungsproblem ist Wiederherstellung glatte Funktion in einer Tabelle angegeben. Es ist klar, dass ein solches Problem viele verschiedene Lösungen hat. Indem wir der konstruierten Funktion zusätzliche Bedingungen auferlegen, können wir die notwendige Eindeutigkeit erreichen. Definition eines glättenden kubischen Splines Ein glättender kubischer Spline S(x) auf einem Netz w ist eine Funktion, die 1) auf jedem der Segmente ein Polynom dritten Grades ist, 2) auf dem Segment [a, 6] zweimal stetig differenzierbar ist ], das heißt, gehört zur Klasse C2 [a , b], 3) liefert ein Minimum an das Funktional mit gegebenen Zahlen, 4) erfüllt die Randbedingungen eines der drei unten angegebenen Typen. Randbedingungen (Randbedingungen) Randbedingungen werden als Einschränkungen für die Werte des Splines und seiner Ableitungen an den Randknoten des Netzes w angegeben. A. Randbedingungen des 1. Typs. - Am Ende des Intervalls [a, b) werden die Werte der ersten Ableitung der gewünschten Funktion angegeben. Randbedingungen des 2. Typs. - die zweiten Ableitungen der gewünschten Funktion an den Enden des Intervalls (a, b] sind gleich Null. B. Randbedingungen des 3. Typs werden als periodisch bezeichnet. Satz. Kubischer Spline S (x), Minimierung der Funktion (4 ) und die Randbedingungen eines der drei angegebenen Typen erfüllt, ist eindeutig definiert Definition: Ein kubischer Spline, der die Funktion J(f) minimiert und die Randbedingungen vom i-Typ erfüllt, wird als glättender Spline vom i-Typ bezeichnet durch vier Koeffizienten.Gesamtsegmente - m.Um also den Spline vollständig zu definieren, müssen Sie 4m Zahlen finden.Die Bedingung bedeutet die Stetigkeit der Funktion 5(ar) und aller Ableitungen an allen internen Knoten des Gitters o. "Die Anzahl solcher Knoten ist m - 1. Um also die Koeffizienten aller Polynome zu finden, werden 3(m - 1) Bedingungen (Gleichungen) erhalten. wobei die Anzahl der zu bestimmenden Größen 2m + 2 ist. Auf jedem der Intervalle wird die glättende Spline-Funktion in der folgenden Form gesucht Beschreiben wir zunächst, wie die Größen n* gefunden werden. Für Randbedingungen des 1. und 2. Typs wird das lineare Gleichungssystem zur Bestimmung der Werte von Hi in der folgenden Form geschrieben, wobei die bekannten Zahlen sind). Die Koeffizienten hängen von der Wahl der Randbedingungen ab. Randbedingungen des 1. Typs: Randbedingungen des 2. Typs: Bei den Randbedingungen des 3. Typs wird das System zur Bestimmung der Zahlen wie folgt geschrieben: Außerdem werden alle Koeffizienten nach den Formeln (5) berechnet (die Größen mit Indizes k und m + k werden als gleich betrachtet: Wichtiger* Hinweis. Die Matrizen von Systemen sind nicht entartet, und daher hat jedes dieser Systeme eine eindeutige Lösung. Wenn die Zahlen n, - gefunden werden, lassen sich die Mengen leicht durch die Formeln bestimmen Wenn alles und der Glättungsspline sich als Interpolationsspline herausstellt. Das bedeutet insbesondere, je genauer die Werte angegeben werden, desto kleiner ist der Prescale-Wert der entsprechenden Gewichtungskoeffizienten. Ist es hingegen erforderlich, dass der Spline durch den Punkt (x^, yk) verläuft, so muss der ihm entsprechende Gewichtsfaktor p\ gleich Null gesetzt werden. Bei praktischen Berechnungen ist die Wahl der Werte pi-Let D, - der Messfehler des Wertes y, am wichtigsten. Dann ist es natürlich zu fordern, dass der Glättungs-Spline die Bedingung oder erfüllt, was dasselbe ist Im einfachsten Fall können die Gewichtskoeffizienten pi beispielsweise in der Form angegeben werden, wobei c eine hinreichend kleine Konstante ist. Eine solche Wahl der Gewichte p erlaubt jedoch keine Verwendung des "Korridors" aufgrund von Fehlern in den Werten von y, -. Ein rationellerer, aber auch zeitaufwändigerer Algorithmus zur Bestimmung der Werte von p,- könnte wie folgt aussehen. Wenn die Werte bei der fc-ten Iteration gefunden werden, wird davon ausgegangen, dass e eine kleine Zahl ist, die experimentell unter Berücksichtigung des Bitrasters des Computers, der Werte von D und der Genauigkeit von ausgewählt wird Lösung des linearen algebraischen Gleichungssystems. Wenn bei der fc-ten Iteration am Punkt i die Bedingung (6) verletzt wird, dann sorgt die letzte Formel für eine Verringerung des entsprechenden Gewichtskoeffizienten p,. Wenn dann bei der nächsten Iteration eine Erhöhung von p zu einer vollständigeren Nutzung des "Korridors" (6) und schließlich zu einem glatteren sich ändernden Spline führt. Ein bisschen Theorie A. Begründung der Formeln zur Berechnung der Koeffizienten des kubischen Splines der Interpolation. Wir führen die Notation ein, wobei m, unbekannte Größen sind. Ihre Zahl ist gleich m + 1. Den Spline, geschrieben in der Form, wo er die Interpolationsbedingungen erfüllt und auf dem ganzen Intervall [a, b\: Einsetzen der Formel stetig ist, erhalten wir jeweils eine stetige erste Ableitung auf dem Intervall [a, 6]: Ableitungsbeziehung (7) und Einstellung erhalten wir das entsprechende. eigentlich. Zeigen wir, dass die Zahlen m so gewählt werden können, dass die Spline-Funktion (7) eine stetige zweite Ableitung auf dem Intervall [a, 6] hat. Berechnen Sie die zweite Ableitung des Splines auf dem Intervall: Am Punkt x, - 0 (bei t = 1) haben wir Berechnen Sie die zweite Ableitung des Splines auf dem Intervall An dem Punkt haben wir Aus der Bedingung der Stetigkeit der zweiten Ableitung an den internen Gitterknoten a; wir erhalten die Beziehung m - 1 wobei Addieren zu diesen m - 1 Gleichungen zwei weitere, die sich aus und von den Randbedingungen ergeben, erhalten wir ein System von m + 1 linearen algebraischen Gleichungen mit m + I unbekannt miy i = 0, 1. ... , m. Das Gleichungssystem zur Berechnung der Werte von gw bei Randbedingungen des 1. und 2. Typs hat die Form wobei (Randbedingungen des 1. Typs), (Randbedingungen des 2. Typs). Für periodische Randbedingungen (Randbedingungen 3. Art) ist das Gitter o; um einen weiteren Knoten verlängern und annehmen Dann wird das System zur Bestimmung der Werte von r* am zweiten und (th - !)-ten Gitterknoten die Form Stetigkeit haben. Wir haben Aus den letzten beiden Beziehungen erhalten wir die fehlenden zwei Gleichungen, die den Randbedingungen des 4. Typs entsprechen: Schließt man die Unbekannte r0 aus den Gleichungen und die Unbekannte pc aus den Gleichungen heraus, erhält man als Ergebnis ein Gleichungssystem Beachten Sie, dass die Anzahl der Unbekannten in diesem System gleich r - I ist. 6. Begründung der Formeln zur Berechnung der Effizienz eines glättenden subischen Splines. Wir führen die Schreibweise ein, wobei Zi und nj noch unbekannte Größen sind. Ihre Anzahl ist gleich 2m + 2. Die in der Form geschriebene Spline-Funktion ist stetig auf dem gesamten Intervall (a, 6]: Wenn wir diese Formel einsetzen, erhalten wir jeweils. Lassen Sie uns zeigen, dass die Zahlen z und n können so gewählt werden, dass der in der Form (8) geschriebene Spline eine stetige erste Ableitung auf dem Intervall [a, 6] hat Berechnen Sie die erste Ableitung des Splines S(x) auf dem Intervall : An einem Punkt haben wir Von der Bedingung der Stetigkeit der ersten Ableitung des Splines an den inneren Knoten des Gitters und --> wir erhalten eine Beziehung m - 1. Es ist zweckmäßig, diese Beziehung in Matrixform zu schreiben. Beziehung (8) und Einstellung, wir erhalten, bzw. wird die Yeshe-Olyu-Matrixbeziehung aus der Bedingung des Minimums der Funktion (4) erhalten. Wir haben Die letzten beiden Matrixgleichungen können als lineares System von 2m + 2 linearen algebraischen Gleichungen in 2m + 2 Unbekannten betrachtet werden. Ersetzen wir die Spalte r in der ersten Gleichheit durch ihren aus Beziehung (9) erhaltenen Ausdruck, gelangen wir zu den Lösungsbeispielen der Matrixgleichung SPLINE THEORY zur Bestimmung der Spalte M. Diese Gleichung hat eine eindeutige Lösung aufgrund der Tatsache, dass die Matrix A + 6HRH7 ist immer nicht entartet. Wenn wir ihn finden, können wir Mr. Eamshine leicht identifizieren. Die Elemente der dreieckmagolalen Matrizen A und H bestimmen n nur durch die Gitterparameter u (mit Schritten hi) und hängen nicht von den Werten yj ab. Der lineare Raum kubischer Spline-Funktionen Die Menge kubischer Splines, die auf dem Segment [a, 6) durch den Knoten wkra + l aufgebaut ist, ist ein linearer Raum der Dimension m + 3: 1) die Summe zweier kubischer Splines, die durch das Gitter u gebildet werden > und das Produkt eines kubischen Splines, aufgebaut auf dem Gitter u>, eine beliebige Zahl geheimer sind kubische Splines, die auf diesem Gitter aufgebaut sind, 2) jeder kubische Spline, der auf dem Gitter aufgebaut und vom Knoten vollständig durch m + 1 bestimmt ist der Wert der Werte von y "an diesen Knoten und zwei Randbedingungen - nur + 3 Parameter. Indem wir in diesem Raum eine Basis wählen, die aus m + 3 linear unabhängigen Splines besteht, können wir einen beliebigen kubischen Spline a(x) als Linearkombination auf eindeutige Weise schreiben. Kommentar. Eine solche Spline-Spezifikation ist in der Computerpraxis weit verbreitet. Besonders praktisch ist die Basis, bestehend aus den sogenannten kubischen B-Splines (Basis- oder Fundamental-Splines). Die Verwendung von D-Splines kann die Anforderungen an den Computerspeicher erheblich reduzieren. L-Splines. B-Spline nullten Grades, aufgebaut auf einem Zahlenstrahl entlang des Gitters w, ist die Funktion der Gabelung B-Spline Grad k ^ I, aufgebaut auf einem Zahlenstrahl entlang des Gitters u, wird durch die rekursive Formel sekunde bestimmt in\7\x) Grad sind in Abb. 11 bzw. 12 dargestellt. B-Splines mit beliebigem Grad k können nur auf einem bestimmten Segment (definiert durch k + 2 Knoten) von Null abweichen. Es ist bequemer, kubisches B zu nummerieren -Splines, so dass der Spline B,-3* (n) auf der Strecke ir,-+2 von Null verschieden war]. Geben wir eine Formel für einen kubischen Spline dritten Grades für den Fall eines gleichmäßigen Gitters (mit a Schritt A). ​​Wir haben in anderen Fällen. Ein typisches Diagramm eines kubischen B-Splines ist in Abb. 13. Die Funktion a) ist auf einem Segment zweimal stetig differenzierbar, dh sie gehört zur Klasse C2 [a, "), c) ist nur auf vier aufeinanderfolgenden Segmenten des erweiterten Gitters w * mo ungleich Null Es ist notwendig, eine Familie von m + 3 kubischen B-Splines zu konstruieren: Diese Familie bildet eine Basis im Raum der kubischen Splines auf dem Segment (a, b). Somit wird ein beliebiger kubischer Spline S(z) konstruiert auf dem Segment |s, 6] des Gitters o; aus +1 Knoten, auf diesem Segment als Linearkombination darstellbar, wobei die Koeffizienten ft dieser Entwicklung eindeutig durch die Problembedingungen bestimmt sind. ... Für den Fall, dass die Werte der Funktion an den Knoten des Gitters und die Werte der ersten Ableitung der Funktion an den Enden des Gitters "(Interpolationsproblem mit Randbedingungen erster Art), werden diese Koeffizienten aus dem System der folgenden Form i und &m+i berechnet, erhalten wir ein lineares System mit den Unbekannten 5q, ... , bm und einer Dreidiagonalmatrix. Die Bedingung liefert Diagonale Dominanz und damit die Möglichkeit, sie mit der Sweep-Methode zu lösen Interpolationsprobleme Zmmchm* 2. Im Vergleich zu den in Abschnitt 1.1 beschriebenen Algorithmen reduziert die Verwendung des R-Splines bei Interpolationsproblemen * die Menge der gespeicherten Informationen, dh die Anforderungen an den Computerspeicher werden erheblich reduziert, obwohl dies zu einer Erhöhung der Anzahl der Operationen führt . Konstruktion von Spline-Kurven mit Hilfe von Spline-Funktionen Oben wurden Arrays betrachtet, deren Punkte so nummeriert wurden, dass ihre Abszissen eine streng steigende Folge bildeten. Beispielsweise der in Abb. 14, wenn verschiedene Punkte des Arrays die gleiche Abszisse haben, nicht erlaubt. Dieser Umstand bestimmte sowohl die Wahl der Klasse der Näherungskurven (Funktionsverkehr) als auch die Methode ihrer Konstruktion. Das oben vorgeschlagene Verfahren ermöglicht es jedoch, eine Interpolationskurve in einem allgemeineren Fall ziemlich erfolgreich zu konstruieren, wenn die Nummerierung von Array-Punkten und ihre Lage in der Ebene in der Regel nicht zusammenhängen (Abb. 15). Darüber hinaus können wir, wenn wir das Problem der Konstruktion einer Interpolationskurve stellen, das gegebene Array als nicht planar betrachten, das heißt, es ist klar, dass es zur Lösung dieses allgemeinen Problems notwendig ist, die Klasse der zulässigen Kurven erheblich zu erweitern, einschließlich darin sowohl geschlossene Kurven als auch Kurven mit Selbstschnittpunkten und räumliche Kurven. Es ist bequem, solche Kurven mit parametrischen Gleichungen zu beschreiben. außerdem gehören die Funktionen, damit sie ausreichend glatt sind, beispielsweise zur Klasse C1 [a, /0] oder zur Klasse. Um die parametrischen Gleichungen einer Kurve zu finden, die nacheinander durch alle Punkte des Arrays geht, gehen Sie wie folgt vor. 1. Schritt. Auf einem beliebigen Segment (\displaystyle ), wird genannt polynomischer Spline Befehl m (\displaystyle m) mit Knoten x j ∈ (a ≤ x 0< . . . < x n ≤ b) {\displaystyle x_{j}\in (a\leq x_{0}<..., falls auf jedem der Segmente [ x j − 1 , x j) (\displaystyle (3) (\displaystyle \left[(\begin(array)(*(20)(c))((P_(j))((t_(j)))= f((t_(j))))\\((P_(j))((t_(j-1)))=f((t_(j-1))))\\(((P") _(j))((t_(j)))=f"((t_(j))))\\(((P")_(j))((t_(j-1)))=f "((t_(j-1))))\\\end(array))\right]\qquad (3))

ermöglicht es Ihnen, die vier Koeffizienten des Polynoms eindeutig zu bestimmen. Bei einem Polynom 5. Grades wäre die Gleichheitsbedingung der 2. Ableitung an den Enden der Strecke hinzuzufügen usw. Aus dem Gesagten sollte klar werden, warum Splines hauptsächlich aus Polynomen ungeraden Grades (mit eine gerade Anzahl von Koeffizienten).

Für Polynome geraden Grades beim Zusammensetzen von System (3):

  • die Ableitung bleibt an einem der Enden des Segments unbestimmt;
  • und die Bedingung der Gleichheit der Ableitungen (Glättung der Kurve) wird nicht erfüllt,

Daher ist es für ein Polynom 2. Grades unmöglich, die Gleichheit der 1. Ableitung an den Verbindungspunkten zu erreichen, und für den 4. Grad - die 2. Ableitung usw. Um Splines mit geraden Graden zu konstruieren, werden zusätzliche Bedingungen künstlich hinzugefügt um ein Gleichungssystem zu bilden, ähnlich wie (3). Wenn die Ableitungen eines Spline-Polynoms genauso definiert sind wie die entsprechenden Ableitungen der interpolierten Funktion, wird der Spline aufgerufen hermitesch.

P j (n) (t j) = f n (t j) , P j (n) (f j − 1) = f n (t j − 1) (4) (\displaystyle P_(j)^((n))((t_ (j)))=(f^(n))((t_(j))),\qquad P_(j)^((n))((f_(j-1)))=(f^(n ))((t_(j-1)))\qquad (4))

Es gibt lokale Methoden zum Konstruieren von Bessel- und Akimi-Splines, B-Splines [ ] . Wenn es um Splines geht, sind im Grunde Splines gemeint, die aus algebraischen Polynomen aufgebaut sind. Dies sind die oben angegebenen Definitionen. Diese Splines sind die am besten untersuchten. Ein Spline kann jedoch aus Fragmenten von Funktionen beliebiger Klassen bestehen. BEIM [ ] wird der Aufbau solcher Splines betrachtet und ihre Eigenschaften untersucht. Autor [ wer?] gibt keine allgemeine Definition von konstruierten Splines. Offensichtlich ist die am Anfang des Artikels gegebene Definition für alle Klassen von Funktionen, aus denen der Spline besteht, nicht ganz geeignet. Wenn zum Beispiel der Spline aus Segmenten des Exponenten besteht, dann verliert das Konzept eines Spline-Defekts seine Bedeutung. Obwohl die Anzahl der kontinuierlichen Ableitungen ein wichtiges Merkmal bleiben wird. Die Konstruktion eines Splines, dessen Fragmente diskontinuierliche Funktionen (rationale Funktionen, Pade-Funktionen) sind, geht etwas über den Rahmen der Spline-Idee hinaus, da einer der Hauptvorteile von Splines ihre Glätte ist. Werden solche Konstruktionen beliebig erweitert, so werden die Unterschiede zwischen Splines und Lumpy-Funktionen gelöscht. Ein weiterer Vorteil von Splines ist die Recheneffizienz. Eine übermäßige Komplikation von Fragmenten verringert den Vorteil von Splines gegenüber klassischen Funktionen erheblich.

Splines zeichnen sich durch folgende Merkmale aus: Ein Spline besteht aus Fragmenten - Funktionen der gleichen Klasse, die sich nur in ihren Parametern unterscheiden, an den Verbindungspunkten werden benachbarte Fragmente bestimmten Bedingungen auferlegt, die auf die Kontinuität von Werten reduziert werden und einige erste Ableitungen. Splines sind ein sich intensiv entwickelnder Zweig der angewandten Mathematik. Im Internet gibt es eine umfangreiche Bibliographie zu Splines (Spline Bibliography Database (SBD)).

Spline-Klassifizierung

Wie oben erwähnt, gibt es eine große Anzahl von Strukturen, die als Splines bezeichnet werden. Daher ist es notwendig, eine bestimmte Klassifizierung in diese Sorte einzuführen, mit dem Ziel, diejenigen Merkmale hervorzuheben, die es Ihnen ermöglichen, Splines auszuwählen, die für ein bestimmtes Anwendungsproblem geeignet sind.

Zuordnung von Splines. Zweckmäßigerweise können drei Hauptgruppen von Splines unterschieden werden: „Interpolations-Splines“ oder „Funktions-Splines“ - die genau durch bestimmte Punkte verlaufen, „Glättungs-Splines“ - die durch bestimmte Punkte verlaufen, wobei die Fehler bei ihrer Bestimmung berücksichtigt werden; "Korrelations-Splines" - Durchlaufen der Korrelationspunktmenge und Anzeigen ihrer allgemeinen Abhängigkeit (Trend, Regression). Interpolation und funktionale Splines werden bei geometrischen Modellierungsaufgaben verwendet, beispielsweise beim Festlegen der Konturen von Wasser- und Flugzeugrümpfen. Glättungs-Splines werden am häufigsten verwendet, um die Abhängigkeiten von physikalischen Experimenten mit einem bekannten Messfehler zu beschreiben. Korrelations-Splines werden als nichtlineare Regressionsgraphen verwendet, von denen der einfachste als Beschreibung der Abhängigkeit durch eine schrittweise und stückweise lineare Funktion (Splines null und ersten Grades) angesehen werden kann.

Ansicht von Spline-Fragmenten. Die Tatsache, dass der Spline aus Fragmenten des gleichen Typs besteht, ist eines der Hauptmerkmale, das ihn von anderen Stückfunktionen unterscheidet. Es gibt jedoch kombinierte Splines, die aus Fragmenten verschiedener Splines bestehen.

Die bekanntesten Splines – bestehend aus Fragmenten – sind algebraische Polynome, die nicht höher als ein bestimmter Grad sind. In der Regel sind dies kubische Polynome oder Polynome ungeraden Grades: erster, dritter (kubischer), fünfter Grad. Höhere Grade werden aufgrund der Komplexität der Berechnungen und der im vorherigen Abschnitt beschriebenen Komplexität selten verwendet. Ihr Hauptvorteil ist die Einfachheit der Berechnungen und Analysen. Der Nachteil ist, dass relativ wenige reale physikalische Prozesse dieser Abhängigkeit entsprechen.

Exponentielle Splines. Wenn ein flexibles Metalllineal, das an den Knoten befestigt ist, gedehnt wird, ist die Lösung der Differentialgleichung kein algebraisches Polynom, sondern eine Exponentialfunktion. Daher werden solche Splines auch genannt Zeitform. Der Exponent beschreibt viele physikalische Prozesse in dynamischen Systemen. Der Nachteil ist die Komplexität der Berechnung.

Durch mechanische Analogie mit einem Metalllineal, das ein Konstruktionsmodell eines Balkens ist, werden Splines mit variabler Steifigkeit erhalten, die in den Arbeiten von Snigirev V.F. und Pavlenko A.P. beschrieben wurden. Anfänglich wurden solche Splines seit der Lösung des Originals als degeneriert oder logarithmisch bezeichnet Spline-Differentialgleichung, die ein Spline-Fragment ist, enthält natürliche logarithmische Funktionen. Die Steifigkeit in ihnen kann als Gewicht wirken, wenn sie vorgegeben ist, oder als Steuerfunktion, die sich aus den Mindestbedingungen für das Energiefunktional des Operators der ursprünglichen Spline-Gleichung ergibt, die der potentiellen Gesamtenergie ähnlich ist die Verformung des Lineals (Balken). Mit der Steifigkeitsfunktion können Sie die Form des Splines steuern. In dem Fall, dass die Steifigkeitsfunktion eine Steuerfunktion ist, werden solche Splines als Splines minimaler Steifigkeit bezeichnet.

Trigonometrisch sind Splines, deren Fragmente durch trigonometrische Polynome beschrieben werden. Sie haben ziemlich komplexe Berechnungsausdrücke. In den Werken von B. A. Popov sind mehr als fünfzig Spline-Fragmente verschiedener Typen beschrieben.

Es gibt auch rationale Splines und Padé-Splines. Ihr Merkmal ist die Möglichkeit, die Ableitungen auf Fragmente aufzubrechen, mit Kontinuität an den Knoten. M. Ansermet baut gebrochene Splines, bei denen die Fragmente mit der Gamma-Funktion angegeben werden.

Die Zweckmäßigkeit der Verwendung von Fragmenten eines bestimmten Typs richtet sich nach den konkreten Problembedingungen und Implementierungseinschränkungen. In der Regel besteht die Hauptanforderung darin, eine bestimmte Interpolationsgenauigkeit mit einem vertretbaren Zeit- und Ressourcenaufwand für die Implementierung zu erreichen. Eine gute Wahl der Fragmente, die der Art des Prozesses entspricht, reduziert die Rechenzeit und den benötigten Speicherplatz.

Anzahl der Fragmente. Offensichtlich ist die minimale Anzahl von Fragmenten eins. Die klassische Definition eines Splines begrenzt die Anzahl der Fragmente auf eine bestimmte Anzahl auf einem endlichen Segment. Es ist jedoch möglich, Splines mit einer unendlichen Anzahl von Fragmenten zu erstellen, aber in Wirklichkeit benötigen diese Verfahren und Algorithmen keine Informationen über eine bestimmte Anzahl von Fragmenten. Diese Splines werden dargestellt durch Kardinal von Schönberg erforschte Splines. Zum Erstellen von Splines mit einer unbegrenzten Anzahl von Fragmenten sind lokale Splines besser geeignet.

Fragmentbreite. Es ist notwendig, Splines mit gleicher Fragmentbreite auszuwählen. Dadurch können Sie die Berechnungsausdrücke erheblich vereinfachen, den Betrieb von Algorithmen beschleunigen und die Implementierungskosten senken. Eine gewisse Vereinfachung kann durch die Verwendung von Fragmenten mit mehrfacher Breite erreicht werden. Es gibt Splines mit Fragmenten der Breite Null (De Boer). Dies führt zu einer Vielzahl von Knoten und der Möglichkeit, Splines mit untrennbaren Fragmenten von unstetigen Funktionen zu approximieren. Berechnungsausdrücke werden als Ergebnis von Grenzübergängen erhalten. Splines können auch Fragmente mit unendlicher Breite haben. Diese Fragmente sollten extrem sein. Dadurch ist es manchmal möglich, die Randbedingungen natürlich zu setzen. Genau genommen hängt die Breite der Fragmente von der Wahl eines Parameters ab - dem Argument der Spline-Funktion, und dies erfordert die Lösung eines separaten Parametrisierungsproblems. Die ideale Wahl als Parameter ist die Länge der interpolierten Funktion, die nicht immer bekannt ist, daher gibt es viele Möglichkeiten, dieses Problem zu lösen. Die gebräuchlichste Methode der Parametrisierung ist die Akkorde.

Bedingungen zum Verbinden von Fragmenten. Ein weiteres wichtiges Merkmal, das Splines auszeichnet. Bei Splines gelten in der Regel Fragmente als fließend verbunden. Das heißt, die Kontinuität der Werte und der ersten Ableitung ist gewährleistet. Konzept Spline-Defekt hängt mit der Anzahl der stetigen Ableitungen zusammen, die eine Fragmentfunktion eines bestimmten Typs hat, und der Anzahl der Ableitungen, deren Stetigkeit an den Knoten garantiert ist. Der Exponent, die Sinuskurve, hat unendlich viele Ableitungen. Für sie macht dieses Konzept keinen Sinn. Daher ist es bequemer, direkt über die Anzahl der Ableitungen zu sprechen, deren Stetigkeit an den Knoten des Splines garantiert ist. In der Praxis sprechen wir von der Stetigkeit der Werte und der ersten, maximalen zweiten Ableitung. Die Lücke zwischen der zweiten und höheren Ableitungen ist visuell nicht wahrnehmbar und wird daher selten berücksichtigt. Es ist klar, dass die erste Ableitung an den Knotenpunkten auf unterschiedliche Weise angegeben werden kann. Am gebräuchlichsten sind zwei Ansätze. Der Wert der ersten Ableitung wird so gewählt, dass die Stetigkeit der zweiten gewährleistet ist (globale kubische Splines des minimalen Defekts). Die erste Ableitung ist gleich der ersten Ableitung der interpolierten Funktion (möglicherweise ungefähr) in Hermiteschen Splines.

Randbedingungen . Es gibt 4 Arten von klassischen Randbedingungen und eine Reihe von nicht-klassischen. Wenn Splines eine begrenzte Anzahl von Fragmenten haben, dann haben sie natürlich keine extremen Fragmente links und rechts, also gibt es nichts, womit man die extremen Knoten verbinden könnte. Die einzigen Ausnahmen sind periodische Splines, die eine natürliche Ausdehnung haben (3. Art der klassischen Randbedingungen). Manchmal werden Randbedingungen mit einer Nullableitung als natürlich bezeichnet, obwohl es keinen Grund gibt, sie als natürlicher als andere zu betrachten, aber für einen kubischen Spline sind natürliche (natürliche) Randbedingungen ein Sonderfall der 2. Art der klassischen Randbedingungen, die definiert zweite Ableitungen an den Kanten des Splines. In diesem Fall entlastet das Gleichsetzen der zweiten Ableitungen mit Null die Kanten des Metalllineals von der Belastung mit einem Biegemoment, das natürlich auftreten würde, wenn es auf feste (gegebene) Knoten im physischen Raum angewendet wird. Bei der 1. Art der klassischen Randbedingungen werden die ersten Ableitungen (tangential) an den Kanten des Splines gesetzt; im 2. Typ - zweite Ableitung (Krümmung) einstellen; der dritte Typ wird zur Interpolation geschlossener oder periodischer Linien verwendet und besteht darin, die äußersten Fragmente des Splines zu verbinden; Der vierte Typ wird verwendet, wenn weder die erste noch die zweite Ableitung an den Rändern des Splines bekannt sind, und besteht darin, benachbarte Paare extremer Fragmente (das erste mit dem zweiten und das letzte mit dem vorletzten) durch die dritte Ableitung zu verbinden, was in Die Praxis besteht darin, Paare durch die Knoten benachbarter extremer Fragmente einer Funktion zu ziehen, die einem Spline-Fragment ähnlich ist (für einen Polynom-Spline - ein Polynom desselben Grades wie das Spline-Fragment). Es werden verschiedene Kombinationen von Randbedingungen verwendet, die auf diese 4 Arten von klassischen Bedingungen reduziert werden. Wenn die Randbedingungen nicht auf diese vier Typen reduziert werden können, wie zum Beispiel die Änderung an einem Paar benachbarter extremer Fragmente des Splines seiner dritten Ableitung gemäß dem linearen (affinen) Gesetz, vorgeschlagen in den Arbeiten von Snigirev V. F., dann werden solche Bedingungen die nicht-klassische Version der Randbedingungen genannt. Nachfolgend einige Varianten, die auf die klassischen Randbedingungen reduzieren. Wenn der Spline Fragmente gleicher Breite hat, werden die fehlenden Fragmente gleicher Breite gezählt. Eine andere Möglichkeit besteht darin, die fehlenden Fragmente bis ins Unendliche verlängert zu betrachten. Der Vorteil dieses Ansatzes ist die Möglichkeit der Extrapolation. Sie können die Breite der Fragmente als Null betrachten. Berechnete Ausdrücke werden durch Grenzwertübergänge erhalten. Betrachtet man die Randbedingungen unter dem Gesichtspunkt der Bildung eines Splines aus Basisfunktionen, so reduzieren sie sich auf die Fortsetzung der entsprechenden lokalen Basisfunktionen. Die Breite benachbarter Fragmente beeinflusst ihre Form. Ein einfacher Schnitt führt oft zu Oszillationen und einer Erhöhung des Fehlers an den Kanten. Randbedingungen sind wichtig bei der Bildverarbeitung und bei Extrapolationsproblemen.

Zusätzliche Einschränkungen. Am häufigsten betreffen sie Derivate an Knoten. Manchmal ergeben sie sich aus der Physik des Prozesses. Bedingungen: Unveräußerlichkeit von Werten, Gleichheit von Momenten, Flächen, Normierungsbedingungen. Zusätzliche Bedingungen vereinfachen manchmal die Analyse von Spline-Eigenschaften, können aber die Konstruktions- und Implementierungskosten ernsthaft erschweren.

Gitter von Interpolationspunkten. Kann die Effizienz von Berechnungen erheblich beeinträchtigen. Wichtig sind die Fälle eines gleichmäßigen Gitters und eines gleichmäßigen Gitters mit einem Abstand zwischen Punkten, der ein Vielfaches des Abstands zwischen den Knoten des Splines ist. Das Auffinden eines Gitters von Interpolationspunkten (Interpolationsknoten) ist eine Parametrisierungsaufgabe, die bereits im Abschnitt Fragmentbreite besprochen wurde.

Lokale Eigenschaften von Basisfunktionen. Ein Spline kann als Summe gewichteter Basis-Splines dargestellt werden. Die Breite dieser Basisfunktionen ist wesentlich. Bei globalen Splines sind also die Basis-Splines auf dem gesamten Interpolationssegment ungleich Null. Obwohl es erwähnenswert ist, dass sie mit einer gewissen Genauigkeit (ausreichend für viele technische Berechnungen) als lokal betrachtet werden können. Für lokale Splines ist die Breite der Basisfunktionen klein (vier Fragmente für kubische hermitische Splines). Dies wirkt sich erheblich auf die Effizienz von Kalkulationen und Implementierungskosten aus.

Präsentationsformular. Funktionen, die Fragmente eines Splines definieren, hängen in der Regel von vielen Parametern ab, aufgrund derer sie ihre Form ändern. Die Parameterwerte auf jedem der Fragmente sind individuell. Diese Parameter können einen bestimmten Spline spezifizieren. Bei Polynom-Splines sind dies die Polynomkoeffizienten. Ein Spline kann also durch einen Satz von Funktionsparametern für jedes der Fragmente dargestellt werden. Nennen wir diese Darstellung pro Fragment. Eine solche Darstellung ist illustrativ und hat oft eine klare physikalische Bedeutung. Aber die Anzahl der Parameter ist zu groß. Für einen kubischen Spline benötigen Sie also 4 * (r-1) Parameter ( r ist die Anzahl der Spline-Knoten). Diese Darstellung ergibt sich durch unbestimmte Integration eines Fragments der ursprünglichen Spline-Differentialgleichung und wird in Analogie zu Polynom-Splines als analoge stückweise Polynomform (pp-Form) bezeichnet. Um die Koeffizienten explizit durch die bereits bekannten Werte der Koordinaten der Knotenpunkte auszudrücken, wird eine Zerlegung einer ähnlichen stückweisen Polynomform in Grundfunktionen verwendet, indem sie in die Hermite-Randbedingungen (Randbedingungen für ein Spline-Fragment , Bedingungen für die Interpolation und das Verlassen auf Ableitungen). Das Ergebnis ist die Grundform (B-Form) des Splines. Diese Darstellung eines Splines ist viel kompakter und kann in Form von grundlegenden Spline-Funktionen in der Form geschrieben werden:

S (x) = ∑ j = 1 r a j B j (x) (\displaystyle S(x)=\sum \limits _(j=1)^(r)((a_(j))(B_(j)) (x))),

wo B.j (x) (\displaystyle (B_(j))(x))- grundlegende Spline-Funktionen (normalerweise lokal), ein j (\displaystyle a_(j))- numerische Koeffizienten, die das Gewicht der Basisfunktionen bei der Bildung eines Splines angeben, dessen physikalische Bedeutung die verallgemeinerten (linearen und winkligen) Verschiebungen des Metalllineals in den Knoten sind. Die Anzahl der Parameter, die den Spline definieren, ist gleich der Anzahl der Spline-Knoten. Es besteht eine Beziehung zwischen den Parametern der Funktion auf dem Fragment und den Koeffizienten des Polynom-Splines, was es ermöglicht, andere mit einigen Koeffizienten zu finden, obwohl die Formeln ziemlich komplex sein können.

Die Transformation einer ähnlichen stückweisen Polynomform der Spline-Darstellung in die Grundform verringert die Ordnung des Systems linearer algebraischer Gleichungen zum Auffinden unbekannter Spline-Koeffizienten, da sie teilweise in Form bereits bekannter Parameter ausgedrückt werden - den Koordinaten gegebener Punkte ( Knoten), die den Rechenaufwand durch die Möglichkeit der Anwendung kostengünstiger Lösungsverfahren, wie dem algebraischen Sweep-Verfahren oder Varianten des Gauß-Verfahrens für dünnbesetzte (Band-)Matrizen mit der Wahl des führenden Elements der Spalte, erheblich reduzieren können.

Inhalt des Spline-Koeffizienten. Wie im vorherigen Absatz erwähnt, wird der Inhalt der Spline-Parameter in der Fragmentdarstellung durch den Funktionstyp bestimmt. Bei einer Polynomdarstellung sollte man den Fall herausgreifen, wenn die Koeffizienten die gleiche physikalische Bedeutung wie die Eingangsdaten haben. Das heißt, die Koeffizienten sind die Werte des Splines an den Knoten. Diese Form wird in Analogie zum Lagrange-Polynom Lagrange genannt. Es sei darauf hingewiesen, dass die grundlegenden Splines dieser Form am zentralen Knoten gleich eins und an allen anderen gleich Null sind.

Die Interpolationskoeffizienten und funktionalen Splines enthalten immer die Werte der Koordinaten der gegebenen Punkte, die sich aus den Interpolationsbedingungen ergeben. Außerdem enthalten sie, abhängig von den Bedingungen für die Verwendung von Ableitungen, die Werte der entsprechenden Ableitungen an den Grenzen des Spline-Fragments (an Knotenpunkten). Beim Schreiben solcher Bedingungen basiert in der Regel ein Spline-Fragment an seinen Grenzen auf der ersten oder zweiten Ableitung. Das auf den ersten Ableitungen ruhende Spline-Fragment spiegelt deutlich die physikalische Bedeutung wider, da die ersten Ableitungen (tangential) die Winkelverschiebungen (Rotationen) des Metalllineals relativ zur Querachse sind. Das Verlassen auf die zweiten Ableitungen des Splines wird verwendet, um die Form von Berechnungsausdrücken zu vereinfachen, um Fehler zu reduzieren, wenn sie manuell umgeschrieben werden, jedoch kann die Verwendung solcher Ausdrücke unter irgendwelchen zusätzlichen Bedingungen in einigen Fällen zu trivialen Lösungen führen.

Spezielle Keile. In manchen Fällen werden Funktionen berücksichtigt, die nahe an der Grenze zwischen Splines und gewöhnlichen Funktionen liegen, sowie Splines und Lumpy-Funktionen. Dies sind beispielsweise Splines, die aus zwei Fragmenten bestehen. Sie haben eine vereinfachte Version der Konstruktion, jedoch sollte besonderes Augenmerk auf die Randbedingungen gelegt werden.

Zu den speziellen Splines gehört ein mehrdimensionaler orthogonaler normalisierter Spline, der ein nichtlineares Modell eines künstlichen Neurons beschreibt (Khakimovs Spline-Modell). Wird verwendet, um die Abhängigkeit einer Funktion von mehreren Argumenten zu modellieren.

siehe auch

Anmerkungen

  • Vershinin VV, Zavyalov Yu, S, Pavlov NN Extremale Eigenschaften von Splines und das Problem der Glättung. - Nowosibirsk: Nauka, 1988, UDC 519.651
  • Roshenko Alexander Iosifovich. Theorie und Algorithmen der Variations-Spline-Approximation: Dis. … Dr. Phys.-Math. Wissenschaften: 01.01.07: Nowosibirsk, 2003 231 p. RSL OD, 71:05-1/136
  • Shikin E. V., Plis L. I. Kurven und Flächen auf einem Computerbildschirm. Eine Anleitung zu Splines für Benutzer. - M.: DIALOG-MEPhI, 1996. - 240 S. ISBN 5-86404-080-0 , UDC 681.3 Sh57
  • Khakimov B.V. Modellierung von Korrelationsabhängigkeiten durch Splines an Beispielen aus Geologie und Ökologie. - St. Petersburg. : Newa, 2003. - 144 p. -ISBN 5-211-04588-2.
  • Pawlenko Alexej Petrowitsch. Anwendung verallgemeinerter Lösungen für den Entwurf von Trägerelementen von Flugzeugstrukturen und die Bildung von funktionalen Splines: Dis. … cand. Technik. Wissenschaften: 05.07.02, 05.13.18 Kasan, 2007. 185 RSL OD, 61 07-5/5391
  • Splines (Spline - stückweise Polynomfunktion) sind zweidimensionale geometrische Objekte, die völlig unabhängig sind und als Grundlage für die Konstruktion komplexerer dreidimensionaler Körper dienen können. Äußerlich sind Splines verschiedene Linien, die Form der Linie wird durch die Art der Scheitelpunkte bestimmt, durch die sie verläuft. Splines können sowohl einfache geometrische Formen sein: Rechtecke, Sterne, Ellipsen usw., als auch komplexe Polylinien oder Kurven sowie Konturen von Textzeichen.

    Die Hauptelemente von Splines sind Scheitelpunkte (Vertex) und Segmente (Segment). Scheitelpunkte werden Punkte genannt, die sich auf dem Spline befinden, während der erste Scheitelpunkt, der den Beginn des Splines anzeigt, mit einem weißen Quadrat markiert ist. Ein Segment wird allgemein als Abschnitt einer Spline-Linie verstanden, die durch zwei benachbarte Scheitelpunkte begrenzt wird – Segmente können entweder gerade oder gekrümmte Segmente sein. Die Spline-Eckpunkte unterscheiden sich im Typ, was den Grad der Krümmung der an diese Eckpunkte angrenzenden Spline-Segmente bestimmt. Insgesamt werden vier Arten von Scheitelpunkten unterschieden (Abb. 1):
    Ecke (Winkel) - Oberseite, in der der Spline unterbrochen ist und angrenzende Segmente ohne Krümmung sind.
    Glatt (Geglättet) - ein Scheitelpunkt, durch den die Spline-Kurve mit einer glatten Biegung gezogen wird und die Krümmung der an den Scheitelpunkt angrenzenden Segmente auf beiden Seiten gleich ist.
    Bezier (Bezier) - ein Scheitelpunkt, der einem glatten ähnelt und sich davon in der Fähigkeit unterscheidet, den Krümmungsgrad beider Segmente zu steuern. Letzteres wird aufgrund des Vorhandenseins von Tangentenvektoren am Scheitelpunkt ausgeführt, die an den Enden durch Markierungen in Form von grünen Quadraten und sogenannten Bezier-Griffen begrenzt sind. Durch Verschieben der Bézier-Griffe können Sie die Richtung ändern, in der die Spline-Segmente in den Scheitelpunkt eintreten und ihn verlassen, und durch Ändern des Abstands von den Griffen zum Scheitelpunkt können Sie den Krümmungsgrad der Spline-Segmente steuern. Scheitelpunkte dieses Typs haben miteinander verbundene Bezier-Griffe, und das Bewegen eines von ihnen bewirkt automatisch, dass sich der zweite bewegt.
    Bezier-Ecke (Winkel-Bezier) - ein Scheitelpunkt mit Tangentenvektoren, mit denen Sie den Grad der Krümmung der Segmente steuern können. Im Gegensatz zu Bezier-Ecken-Scheitelpunkten sind Tangentenvektoren an Bezier-Ecken-Scheitelpunkten jedoch nicht miteinander und mit der Bewegung eines verbunden der Markierungen hängt nicht von der Bewegung der anderen ab.

    Segmente unterscheiden sich auch im Typ: Kurve (Kurve) oder Linie (Linie). Durch Auswahl des Kurventyps können Sie gekrümmte Segmente erhalten, wenn die Scheitelpunkte glatt sind oder vom Bezier-Typ sind, während im Fall von Eckscheitelpunkten das Segment linear bleibt, selbst wenn der Kurventyp eingestellt ist. Die Auswahl des Linientyps bewirkt, dass der Scheitelpunkttyp ignoriert wird, wodurch ein Segment dieses Typs immer linear aussieht.

    Die obige Diskussion der Interpolation zeigt, dass eine Erhöhung der Genauigkeit der Approximation einer glatten Funktion durch Erhöhung des Grads des Interpolationspolynoms möglich ist (siehe Satz 11.8), jedoch mit einer erheblichen Erhöhung des Rechenaufwands verbunden ist. Darüber hinaus erfordert die Verwendung von Polynomen hohen Grades besondere Vorsichtsmaßnahmen auch bei der Wahl ihrer Notationsform, und Berechnungen gehen mit einer Häufung von Rundungsfehlern einher.

    Daher wird in der Praxis eine stückweise Polynominterpolation unter Verwendung von Polynomen niedrigen Grades bevorzugt. Allerdings hat diese Näherungsmethode einen Nachteil: An den „Verbindungspunkten“ zweier benachbarter Polynome hat die Ableitung in der Regel einen Sprung (siehe Beispiel 11.12). Oft spielt dieser Umstand keine wesentliche Rolle. Gleichzeitig ist es oft erforderlich, dass die Näherungsfunktion glatt ist, und dann wird die einfachste stückweise polynomische Interpolation unannehmbar.

    Das natürliche Bedürfnis nach Approximationsfunktionen, die die lokale Einfachheit eines Polynoms niedrigen Grades und die globale Glättung über das gesamte Intervall kombinieren, führte 1946 zum Erscheinen der sogenannten Spline-Funktionen oder Splines - auf besondere Weise konstruierte glatte stückweise Polynomfunktionen . Splines, die in den 60er Jahren als Mittel zur Interpolation komplexer Kurven an Popularität gewonnen haben, sind heute zu einem wichtigen Bestandteil einer Vielzahl von Berechnungsmethoden geworden und haben eine breite Anwendung bei der Lösung verschiedener wissenschaftlicher, technischer und ingenieurwissenschaftlicher Probleme gefunden.

    Lassen Sie uns eine strenge Definition eines Splines geben. Das Segment sei durch Punkte in Teilsegmente unterteilt Ein Grad-Spline ist eine Funktion, die folgende Eigenschaften hat:

    1) Die Funktion ist stetig auf dem Intervall zusammen mit all seinen Ableitungen bis zu einer bestimmten Ordnung

    2) Auf jedem Teilintervall fällt die Funktion mit einem algebraischen Gradpolynom zusammen

    Die Differenz zwischen dem Grad des Splines und der höchsten Ordnung der stetigen Ableitung auf dem Segment wird als Defekt des Splines bezeichnet.

    Das einfachste Beispiel eines Splines ist eine stetige, stückweise Lineare

    eine Funktion (Abb. 11.8), die ein Spline ersten Grades (linearer Spline) mit einem Fehler gleich eins ist. Tatsächlich ist die Funktion selbst (Nullableitung) auf dem Intervall stetig. Gleichzeitig fällt es auf jedem Teilsegment mit einem Polynom ersten Grades zusammen.

    In der Praxis am weitesten verbreitet sind Splines dritten Grades (kubische Splines) mit einem Fehler gleich 1 oder 2. Solche Splines auf jedem der Teilsegmente stimmen mit dem kubischen Polynom überein:

    und haben mindestens eine stetige Ableitung auf dem Intervall

    Der Begriff "Spline" kommt vom englischen Wort (flexible ruler, rod) - der Name eines Geräts, das von Zeichnern verwendet wird, um glatte Kurven durch vorgegebene Punkte zu ziehen. Wenn Sie ein flexibles Stahllineal auf eine Kante legen und seine Position durch Biegen an den Knotenpunkten fixieren (Abb. 11.9), erhalten Sie ein mechanisches Analogon eines kubischen Splines. Aus dem Festigkeitsverlauf von Materialien ist nämlich bekannt, dass die Gleichung des freien Gleichgewichts des Profils des Lineals wie folgt lautet: Im Intervall zwischen zwei benachbarten Knoten befindet sich also ein Polynom dritten Grades. Gleichzeitig zeigt das Fehlen von Knicken im Lineal die Kontinuität der Tangente an den Graphen der Funktion und Krümmung an, dh Ableitungen

    2. Interpolations-Spline.

    Eine Funktion sei durch eine Tabelle ihrer Werte gegeben. Ein Spline heißt interpolierend, wenn für alle Werte die Steigung des Splines an einem Punkt genannt wird

    Beachten Sie, dass auf einem Segment der interpolierende kubische Spline eindeutig durch das Setzen der Werte bestimmt wird, tatsächlich folgt die folgende Formel aus Gleichheit (11.31):

    Verschiedene Methoden der Interpolation durch kubische Splines unterscheiden sich in der Art und Weise, wie sie Steigungen auswählen.Lassen Sie uns einige davon besprechen.

    3. Lokaler Spline.

    Wenn an den Punkten x die Werte der Ableitung bekannt sind, dann ist es natürlich, für alle dann auf jedem Teilsegment gemäß Formel (11.64) den Spline durch die Werte ( weshalb es ein lokaler Spline genannt wird). Beachten Sie, dass es mit dem kubischen Hermite-Interpolationspolynom (11.31) für das Segment übereinstimmt

    Ungleichung (11.33) liefert folgende Abschätzung für den Interpolationsfehler durch einen lokalen kubischen Spline:

    wobei Ashach das Maximum der Längen der Teilsegmente ist.

    Beachten Sie, dass für einen auf diese Weise konstruierten Spline nur die Funktion und ihre erste Ableitung 53 garantiert stetig auf dem Intervall sind, d. h. sein Defekt ist 2.

    Es gibt andere Möglichkeiten, die Koeffizienten a zu wählen, die zu lokalen Splines führen (kubisches Bessel-Polynom, Akima-Verfahren usw.).

    4. Globale Methoden zum Konstruieren von kubischen Splines.

    Damit der Spline eine kontinuierliche zweite Ableitung auf dem Segment hat, müssen die Steigungen a so gewählt werden, dass an den Punkten x, der "Verbindung" der Polynome, die Werte ihrer zweiten Ableitungen übereinstimmen:

    Mit Formel (11.64) finden wir den Wert

    Aus einer ähnlichen Formel geschrieben

    Gleichungen (11.66) führen also bezüglich der Koeffizienten zu folgendem Gleichungssystem

    Beachten Sie, dass dieses Gleichungssystem unterbestimmt ist, da die Anzahl der Gleichungen des Systems (gleich kleiner als die Anzahl der Unbekannten (gleich) ist. Die Wahl der beiden verbleibenden Gleichungen ist normalerweise mit einigen zusätzlichen Bedingungen verbunden, die dem Spline bei der auferlegt werden Randpunkte (Randbedingungen) Lassen Sie uns auf einige der bekanntesten Randbedingungen hinweisen .

    1°. Wenn die Werte der ersten Ableitung an den Randpunkten bekannt sind, dann ist es natürlich zu setzen

    Ergänzt man das System (11.69) mit den Gleichungen (11.70), erhält man ein Gleichungssystem mit tridiagonaler Matrix, das sich leicht mit der Sweep-Methode lösen lässt (siehe Kap. 5). Der resultierende Spline wird als fundamentaler kubischer Spline bezeichnet.

    2°. Sind an den Randpunkten die Werte der zweiten Ableitung bekannt, so können dem Spline Randbedingungen auferlegt werden, die zu folgenden Gleichungen führen:

    (es genügt bei Gleichheit (11.68), a in Gleichheit zu nehmen

    3°. Setzt man in den Gleichungen voraus, ob diese Bedingungen für die interpolierte Funktion erfüllt sind), so gelangt man zu einem Gleichungssystem, das den sogenannten natürlichen kubischen Spline definiert.

    4°. Oft gibt es keine zusätzlichen Informationen über die Werte der Derivate an den Enden des Segments. Ein Ansatz, der in dieser Situation verwendet wird, besteht darin, die Bedingung "Kein Knoten" zu verwenden. Die Steigungen werden so gewählt, dass für den resultierenden Spline folgende Bedingungen erfüllt sind, dazu genügt die Forderung, dass die entsprechenden dritten Ableitungen in den Punkten zusammenfallen:

    Die äquivalenten algebraischen Gleichungen sehen so aus:

    Die gleiche Näherungsfunktion kann auf etwas andere Weise erhalten werden. Reduzieren wir die Anzahl der Teilsegmente, indem wir die Segmente paarweise zusammenfassen, was einer punktuellen Teilung des Segments an der Stelle und dem Aufbau des entsprechenden Interpolations-Splines entspricht.

    5°. Handelt es sich um eine periodische Funktion mit einer Periode gleich o, so sollte das System (11-69) um die Bedingungen ergänzt werden