MINISTERIUM FÜR BILDUNG UND WISSENSCHAFT DER RUSSISCHEN FÖDERATION

Staatliche Selbstständige Bildungseinrichtung

höhere Berufsausbildung

"Ural Federal University benannt nach dem ersten Präsidenten Russlands B. N. Jelzin"

Institut für Funkelektronik und Informationstechnologien - RTF

Stuhl Automatisierungs- und Informationstechnik

Spline-Interpolation

METHODISCHE ANLEITUNGEN Für Laborarbeiten AUF DER DISZIPLIN " Numerische Methoden»

Zusammengestellt von I.A. Selivanova, Dozentin.

SPLINE-INTERPOLATION: Leitfaden für praktische Übungen im Fach "Numerische Methoden"

Die Anleitung richtet sich an Studierende aller Bildungsformen der Richtung 230100 - "Informatik und Technische Informatik".

Ó FSAEI HPE „UrFU benannt nach dem ersten Präsidenten Russlands B.N. Jelzin“, 2011

1. INTERPOLATION DURCH SPLINES. vier

1.1. Kubische Splines. vier

1.2. Eine spezielle Form, einen Spline zu schreiben. 5

1.3. Quadratische Splines. 13

1.4. Übungsaufgabe. achtzehn

1.5. Aufgabenoptionen. 19

Referenzen 21

1. Interpolation durch Splines.

In Fällen, in denen das Intervall [ a,b], auf dem es erforderlich ist, die Funktion zu ersetzen f(x) groß, können Sie Spline-Interpolation anwenden.

1.1. Kubische Splines.

Interpolations-Splines 3 Ordnung sind Funktionen, die aus Teilen von Polynomen bestehen 3 th bestellen. Die Konjugationsknoten stellen die Kontinuität der Funktion, ihrer ersten und zweiten Ableitung sicher. Die Näherungsfunktion setzt sich in der Regel aus getrennten Polynomen gleich kleinen Grades zusammen, die jeweils auf ihrem eigenen Teil des Segments definiert sind.

Lassen Sie das Intervall [ a, b] reelle Achse x das Raster ist gegeben, in dessen Knoten die Werte definiert sind
Funktionen f(x). Es ist erforderlich, auf dem Segment aufzubauen [ a, b] kontinuierliche Spline-Funktion S(x), die folgende Bedingungen erfüllt:

Um den gewünschten Spline zu konstruieren, müssen Sie die Koeffizienten finden
Polynome
,ich=1,… n, d.h. 4 n unbekannte Koeffizienten, die erfüllen 4 n-2 Gleichungen (1), (2), (3). Damit das Gleichungssystem eine Lösung hat, werden zwei weitere (Rand-)Bedingungen hinzugefügt. Es werden drei Arten von Randbedingungen verwendet:

Die Bedingungen (1), (2), (3) und eine der Bedingungen (4), (5), (6) bilden eine Auftrags-SLAE 4 n. Das System kann mit der Gauß-Methode gelöst werden. Durch die Wahl einer speziellen Schreibweise eines kubischen Polynoms kann man jedoch die Ordnung des zu lösenden Gleichungssystems deutlich reduzieren.

1.2. Eine spezielle Form, einen Spline zu schreiben.

Betrachten Sie das Segment
. Führen wir die folgende Notation für Variablen ein:

Hier
- Segmentlänge
,

,
- Hilfsvariablen,

x- Zwischenpunkt auf dem Segment
.

Wann x durchläuft alle Werte im Intervall
, variabel wechselt von 0 auf 1, und
wechselt von 1 auf 0.

Lassen Sie das kubische Polynom
auf dem Segment
sieht aus wie:

Variablen und
werden in Bezug auf ein spezifisches Interpolationssegment bestimmt.

Ermitteln Sie den Wert des Splines
an den Segmentenden
. Punkt
ist der Anfangsbuchstabe für das Segment
, deshalb =0,
=1 und nach (3.8):
.

Am Ende des Abschnitts
=1,
=0 und
.

Für Intervall
Punkt
ist endgültig, also =1,
=0 und aus Formel (9) erhalten wir:
. Damit ist die Stetigkeitsbedingung für die Funktion erfüllt S(x) an den Knotenpunkten kubischer Polynome, unabhängig von der Wahl der Zahlen  i .

Um die Koeffizienten  i zu bestimmen, ich=0,… n wir differenzieren (8) zweimal als komplexe Funktion von x. Dann

Definieren Sie die zweiten Ableitungen des Splines
und
:

Für Polynom
Punkt ist der Anfang des Interpolationssegments und =0,
=1, also

Aus (15) und (16) folgt, dass auf der Strecke [ a,b]Spline-Funktion, "zusammengeklebt" aus Polynomstücken 3. Ordnung, hat eine stetige Ableitung 2. Ordnung.

Um die Stetigkeit der ersten Ableitung einer Funktion zu erhalten S(x), In den internen Interpolationsknoten müssen folgende Bedingungen erfüllt sein:

Für natürlichen kubischen Spline
, daher sieht das Gleichungssystem wie folgt aus:

und das Gleichungssystem (17) sieht so aus:

Beispiel.

Ausgangsdaten:

Funktion ersetzen
interpolierender kubischer Spline, dessen Werte an den gegebenen Knotenpunkten (siehe Tabelle) mit den Werten der Funktion an denselben Punkten übereinstimmen. Berücksichtigen Sie unterschiedliche Randbedingungen.

Lassen Sie uns den Wert der Funktion an den Knotenpunkten berechnen. Dazu setzen wir die Werte aus der Tabelle in die angegebene Funktion ein.

Für verschiedene Randbedingungen (4), (5), (6) finden wir die Koeffizienten kubischer Splines.

1. Betrachten Sie die ersten Randbedingungen.

In unserem Fall n=3,
,
,
. Finden
verwenden wir das Gleichungssystem (3.18):

Berechnen und , unter Verwendung der Formeln (7) und (11):

Wir setzen die erhaltenen Werte in das Gleichungssystem ein:

.

Systemlösung:

Unter Berücksichtigung der ersten Randbedingungen ergeben sich die Spline-Koeffizienten:

Betrachten Sie die Definition der Spline-Koeffizienten unter Berücksichtigung der Randbedingungen (3.5):

Finden wir die Ableitung der Funktion
:

Berechnen
und
:

Setzen wir die Werte in das Gleichungssystem (21) ein und :

Mit Formel (20) bestimmen wir  0 und  3:

Gegebene spezifische Werte:

und Koeffizientenvektor:

Berechnen wir die Werte des kubischen Splines S(x) an den Mittelpunkten der Interpolationssegmente.

Mittelteile:

Um den Wert des kubischen Splines an den Mittelpunkten der Interpolationssegmente zu berechnen, verwenden wir die Formeln (7) und (9).

3.1.

Lass uns finden und
:

In Formel (3.9) ersetzen wir die Koeffizienten

3.2.

Lass uns finden und
:

, für Randbedingungen (4), (5), (6):

3.3.

Lass uns finden und
:

In Formel (9) ersetzen wir die Koeffizienten
, für Randbedingungen (4), (5), (6):

Machen wir eine Tabelle:

	(1 Cr. Zustand.)	(2 Cr. Konditionen)	(3 Cr. Konditionen)

Die Hauptaufgabe Interpolation- Auffinden des Wertes einer Tabellenfunktion an den Punkten innerhalb eines gegebenen Intervalls, wo er nicht angegeben ist. Die ersten tabellarischen Daten können sowohl experimentell (in diesem Fall gibt es grundsätzlich keine Zwischendaten ohne zusätzliche Arbeit) als auch durch Berechnung mit komplexen Abhängigkeiten (in diesem Fall den Wert durch Interpolation finden) erhalten werden komplexe Funktion ist einfacher als die direkte Berechnung mit einer komplexen Formel)

Konzept der Interpolation

Die Lösung von Interpolations- und Extrapolationsproblemen wird durch die Konstruktion der Interpolationsfunktion bereitgestellt L(x), ersetzt ungefähr das Original f(x), in einer Tabelle angegeben und alle gegebenen Punkte durchlaufen - Interpolationsknoten. Mit dieser Funktion können Sie an jeder Stelle den gewünschten Wert der Originalfunktion berechnen.

Im Zusammenhang mit der Interpolation werden drei Hauptprobleme betrachtet.

1) Wahl der Interpolationsfunktion L(x);

2) Schätzung des Interpolationsfehlers R(x);

3) Platzierung von Stützstellen, um eine höchstmögliche Genauigkeit der Wiederherstellung der Funktion zu gewährleisten ( x 1 , x 2 ,…,x n).

Spezielle Interpolationsverfahren ermöglichen es, den gewünschten Wert der Funktion ohne direkte Konstruktion der Interpolationsfunktion zu ermitteln. Grundsätzlich liefern alle Interpolationsverfahren, die auf der Verwendung von Polynomen als Interpolationsfunktion beruhen, die gleichen Ergebnisse, jedoch mit unterschiedlichen Kosten. Das liegt daran, dass das Polynom n Grad enthält n+1 Parameter und das Durchlaufen aller gegebenen n+1 Punkte, - der einzige. Außerdem kann ein Polynom als abgeschnittene Taylor-Reihe dargestellt werden, in der die ursprüngliche differenzierbare Funktion erweitert wurde. Dies ist vielleicht einer der Hauptvorteile des Polynoms als Interpolationsfunktion. Daher wird das erste Problem der Interpolation häufiger gelöst, indem ein Polynom als Interpolationsfunktion gewählt wird, obwohl andere Funktionen verwendet werden können (z. B. trigonometrische Polynome, andere Funktionen, die aus den informellen Bedingungen eines sinnvollen Problems ausgewählt werden).

Reis. 3.2 Darstellung der Interpolation

Die Wahl der Art der Interpolationsfunktion ist generell eine wichtige Aufgabe, insbesondere wenn man bedenkt, dass beliebig viele Funktionen durch gegebene Punkte gezogen werden können (Abb. 3.2). Es sei darauf hingewiesen, dass es einen offensichtlichen Weg gibt, eine Interpolationsfunktion zu konstruieren: Aus der Bedingung, dass die Funktion durch alle Punkte geht, wird ein Gleichungssystem erstellt, aus dessen Lösung seine Parameter gefunden werden. Dieser Weg ist jedoch bei weitem nicht der effizienteste, insbesondere bei einer großen Anzahl von Punkten.

Es ist üblich, zwischen lokaler und globaler Interpolation zu unterscheiden. In dem Fall, in dem das Polynom für den gesamten Interpolationsbereich gleich ist, sagen wir, dass die Interpolation global. In Fällen, in denen die Polynome zwischen verschiedenen Knoten unterschiedlich sind, spricht man von stückweise oder lokale Interpolation.

Lineare Interpolation

Die einfachste und am häufigsten verwendete Form der lokalen Interpolation ist lineare Interpolation. Es besteht darin, dass die gegebenen Punkte M(x ich, y ich) (ich = 0, 1, …,n) durch gerade Liniensegmente verbunden sind, und die Funktion f(x) nähert sich einem Polygonzug mit Eckpunkten an diesen Punkten (Abb. 3.3) .

Reis. 3.3 Lineare Interpolation

Die Gleichungen jedes Segments einer gestrichelten Linie sind im Allgemeinen unterschiedlich. Da gibt es n Intervalle (x ich , x ich + 1), dann für jeden von ihnen als Gleichung

Das Interpolationspolynom verwendet die Gleichung einer geraden Linie, die durch zwei Punkte verläuft. Insbesondere z ich - Intervall können wir die Gleichung einer geraden Linie schreiben, die durch die Punkte verläuft ( x ich, y ich) und ( x ich + 1 , y ich + 1), als:

(3.2)

Daher müssen Sie bei Verwendung der linearen Interpolation zuerst das Intervall bestimmen, in das der Wert des Arguments fällt x, und setzen Sie es dann in Formel (3.2) ein und finden Sie den ungefähren Wert der Funktionen an diesem Punkt.

Abbildung 3.4 zeigt ein Beispiel für die Verwendung der linearen Interpolation im MathCAD-Programm. Zur linearen Interpolation wird die Funktion verwendet interp (x,j,z). Hier x, j- Ausgangsdaten, z- der Punkt, an dem sich der Wert der Funktion befindet.

Reis. 3.4. Lineare Interpolation

Quadratische Interpolation

Im Fall von quadratische Interpolation als Interpolationsfunktion auf dem Intervall ( x ich — 1 , x ich + 1) nimm ein quadratisches Trinom. Die Gleichung eines quadratischen Trinoms hat die Form

y = a ich x 2 + b ich x + c ich , x ich — 1 x x ich + 1 , (3.3)

Interpolation für jeden Punkt x [x 0 , xn] wird über die drei nächstgelegenen Punkte gezogen.

Kubische Spline-Interpolation

BEI letzten Jahren ein neuer Zweig der modernen Computermathematik entwickelt sich intensiv - die Theorie Keile. Splines ermöglichen es, die Probleme der Verarbeitung experimenteller Abhängigkeiten zwischen Parametern, die eine ziemlich komplexe Struktur haben, effektiv zu lösen.

Die oben diskutierten Verfahren der lokalen Interpolation sind im Wesentlichen die einfachsten Splines ersten Grades (für lineare Interpolation) und zweiten Grades (für quadratische Interpolation).

Die breiteste praktischer Nutzen, fanden aufgrund ihrer Einfachheit kubische Splines. Die Grundideen der Theorie der kubischen Keile sind das Ergebnis von Versuchen, flexible Schienen aus elastischem Material (mechanische Keile) mathematisch zu beschreiben, die seit langem von Zeichnern verwendet werden, wenn es notwendig wurde, eine ausreichend glatte Kurve durchzuziehen gegebene Punkte. Es ist bekannt, dass eine Schiene aus einem elastischen Material, die an bestimmten Punkten fixiert ist und sich in einer Gleichgewichtslage befindet, eine Form annimmt, in der ihre Energie minimal ist. Diese grundlegende Eigenschaft macht es möglich, Splines effektiv bei der Lösung praktischer Probleme der Verarbeitung experimenteller Informationen zu verwenden.

Im Allgemeinen für eine Funktion y=f(x) ist es erforderlich, eine Annäherung zu finden y = j(x) so dass f(x ich)= j(x ich) an Punkten x = x i , a an anderen Punkten des Segments [ ein, b] Werte

Funktionen f(x) und j(x) lagen nah beieinander. Mit einer kleinen Anzahl experimenteller Punkte (z. B. 6–8) kann eines der Verfahren zum Konstruieren von Interpolationspolynomen verwendet werden, um das Interpolationsproblem zu lösen. Bei einer großen Anzahl von Knoten werden Interpolationspolynome jedoch praktisch unbrauchbar. Dies liegt daran, dass der Grad des Interpolationspolynoms nur um eins kleiner ist als die Anzahl der Erfahrungswerte der Funktionen. Es ist natürlich möglich, das Segment, auf dem die Funktion definiert ist, in Abschnitte zu unterteilen, die eine kleine Anzahl von experimentellen Punkten enthalten, und für jeden von ihnen Interpolationspolynome zu konstruieren. In diesem Fall wird die Näherungsfunktion jedoch Punkte haben, an denen die Ableitung nicht stetig ist, d. h. der Graph der Funktion wird „Knickpunkte“ enthalten.

Kubische Splines haben diesen Mangel nicht. Studien zur Balkentheorie haben gezeigt, dass ein flexibler dünner Balken zwischen zwei Knoten recht gut durch ein kubisches Polynom beschrieben wird, und da er nicht kollabiert, muss die Näherungsfunktion zumindest stetig differenzierbar sein. Das bedeutet, dass die Funktionen j(x), j'(x), j"(x) muss auf dem Segment [ ein, b].

Kubischer Interpolations-Spline , für diese Funktion geeignet f(x) und gegebenen Knoten x ich , Funktion genannt j(x), folgende Bedingungen erfüllen:

1. auf jedem Segment [ x ich — 1 , x ich], ich = 1, 2, ..., n Funktion j(x) ist ein Polynom dritten Grades,

Funktion j(x), und auch seine erste und zweite Ableitung sind stetig auf dem Intervall [ ein, b],

kubischer Spline aus Polynomen dritten Grades zusammengeklebt wird, was z ich Abschnitt sind wie folgt geschrieben:

Jeweils für das gesamte Intervall P kubische Polynome mit unterschiedlichen Koeffizienten aich, b ich, c ich, d ich. Meistens sind die Knoten während der Spline-Interpolation gleichmäßig beabstandet, d. h. Xich +1 -Xich = konst = h (obwohl dies nicht erforderlich ist).

Es ist notwendig, vier Koeffizienten unter der Bedingung zu finden, dass jedes Polynom durch zwei Punkte (x ich, ja ich) und (x ich +1 , ja ich +1 ) , was zu den folgenden offensichtlichen Gleichungen führt:

Die erste Bedingung entspricht dem Durchgang des Polynoms durch den Startpunkt, die zweite - durch den Endpunkt. Es ist unmöglich, alle Koeffizienten aus diesen Gleichungen zu finden, da es weniger Bedingungen als die erforderlichen Parameter gibt. Daher werden diese Bedingungen durch die Bedingungen für die Glattheit der Funktion (dh die Stetigkeit der ersten Ableitung) und die Glattheit der ersten Ableitung (dh die Stetigkeit der zweiten Ableitung) an den Stützstellen ergänzt. Mathematisch werden diese Bedingungen jeweils als Gleichungen der ersten und zweiten Ableitung am Ende geschrieben ich Mai und am Anfang ( ich+1 )-te Grundstücke.

Seit und , dann

(j’ (x ich +1 ) Am Ende ich-ten Abschnitt ist gleich du(Xich +1 ) am Anfang ( ich+1 )-ten),

(bei"(Xich +1 ) Am Ende ich-ten Abschnitt ist gleich y" (xich +1 ) am Anfang ( ich+1)-te).

Das Ergebnis ist ein lineares Gleichungssystem (für alle Abschnitte), das 4n - 2 Gleichungen mit 4n Unbekannten enthält (Unbekannte a 1 , a 2 ,…, a n , b 1 ,…, d n - Spline-Koeffizienten). Um das System zu lösen, werden zwei Randbedingungen eines der folgenden Typen hinzugefügt (1 wird häufiger verwendet):

Die gemeinsame Lösung von 4n Gleichungen ermöglicht das Auffinden aller 4n Koeffizienten.

Um die Ableitungen wiederherzustellen, kann man das entsprechende kubische Polynom auf jedem Abschnitt differenzieren. Wenn es notwendig ist, die Ableitungen an den Knoten zu bestimmen, gibt es spezielle Techniken, die die Definition von Ableitungen auf die Lösung eines einfacheren Gleichungssystems bezüglich der gewünschten Ableitungen zweiter oder erster Ordnung reduzieren. Ein wichtiger Vorteil der kubischen Spline-Interpolation besteht darin, eine Funktion zu erhalten, die eine möglichst geringe Krümmung aufweist. Zu den Nachteilen der Spline-Interpolation gehört die Notwendigkeit, eine relativ große Anzahl von Parametern zu erhalten.

Lösen wir das Interpolationsproblem mit dem Programm MathCAD. Dazu verwenden wir die eingebaute Funktion interp(VS,x,y,z) . Variablen x und j setze die Koordinaten der Knotenpunkte, z ist ein Funktionsargument, VS definiert den Typ

Randbedingungen an den Enden des Intervalls.

Wir definieren Interpolationsfunktionen für drei Arten von kubischen Splines

Hier cSpline (VX , VY) gibt einen Vektor zurück VS zweite Ableitungen bei Annäherung an Bezugspunkte an ein kubisches Polynom;

Spline(VX, VY) gibt einen Vektor zurück VS zweite Ableitungen beim Annähern der Stützpunkte an die Parabelkurve;

lSpline(VX, VY) gibt einen Vektor zurück VS zweite Ableitungen beim Anfahren der Stützpunkte der Geraden;

interp(VS, VX, VY, x) gibt einen Wert zurück j(x) für gegebene Vektoren VS, VX, VY und Wert einstellen x.

Wir berechnen die Werte der Interpolationsfunktionen an gegebenen Punkten und vergleichen die Ergebnisse mit genaue Werte

Beachten Sie, dass die Ergebnisse der Interpolation durch verschiedene Arten von kubischen Splines an den internen Punkten des Intervalls praktisch gleich sind und mit den genauen Werten der Funktion übereinstimmen. In der Nähe der Ränder des Intervalls wird der Unterschied deutlicher, und wenn sie außerhalb des angegebenen Intervalls extrapoliert werden, ergeben verschiedene Arten von Splines deutlich unterschiedliche Ergebnisse. Zur besseren Übersicht stellen wir die Ergebnisse in der Grafik dar (Abb. 3.5)

Reis. 3.5 Kubische Spline-Interpolation

Wenn die Funktion diskret angegeben wird, werden Datenmatrizen für die Interpolation angegeben.

Bei der globalen Interpolation wird am häufigsten die Polynominterpolation verwendet n Grad oder Lagrange-Interpolation.

Der klassische Ansatz basiert auf der Forderung nach striktem Matching von Werten f(X) und j(X) an Punkten x ich(ich = 0, 1, 2, … n).

Wir suchen nach der Interpolationsfunktion j(X) als Gradpolynom n.

Dieses Polynom hat n+ 1 Koeffizient. Es ist selbstverständlich, das anzunehmen n+ 1 Bedingungen

j(x 0) = j 0 , j(x 1) = j 1 , . . ., j(x n) = ja n (3.4)

dem Polynom überlagert

ermöglichen es, seine Koeffizienten eindeutig zu bestimmen. In der Tat erfordern j(X) Erfüllung der Bedingungen (3.4) , Wir bekommen das System n+ 1 Gleichungen mit n+ 1 unbekannt:

(3.6)

Lösen dieses Systems für die Unbekannten a 0 , a 1 , …, ein wir erhalten einen analytischen Ausdruck für das Polynom (3.5). System (3.6) hat immer eine eindeutige Lösung , Weil seine Determinante

in der Algebra bekannt als Vandermonde-Determinante, von Null verschieden . dies impliziert , Was ist das Interpolationspolynom? j(X) für die Funktion f(X) in einer Tabelle existiert und eindeutig ist.

Die resultierende Kurvengleichung geht genau durch die gegebenen Punkte. Außerhalb der Stützstellen kann das mathematische Modell einen erheblichen Fehler aufweisen

Lagrange-Interpolationsformel

Lassen Sie die Werte einer Funktion bekannt sein f(X) in n+ 1 verschiedene willkürliche Punkte y ich = f(x ich) , ich = 0,…, P. Irgendwann eine Funktion interpolieren (wiederherstellen). X, Zugehörigkeit zum Segment [ x 0 , x p], Es ist notwendig, ein Interpolationspolynom n-ter Ordnung zu konstruieren, das im Lagrange-Verfahren wie folgt dargestellt wird:

Und das ist leicht zu sehen Qj(x ich) = 0, wenn ich¹ j, und Qj(x ich) =1, wenn ich= j. Wenn wir das Produkt aller Klammern im Zähler erweitern (im Nenner sind alle Klammern Zahlen), dann erhalten wir ein Polynom n-ter Ordnung aus X, da der Zähler n Faktoren erster Ordnung enthält. Daher ist das Lagrange-Interpolationspolynom trotz der speziellen Schreibweise nichts anderes als ein gewöhnliches Polynom n-ter Ordnung.

Schätzen Sie den Interpolationsfehler an einem Punkt X aus [ x 0 , xn] (d. h. löse die zweite

Interpolationsproblem) kann durch die Formel angegeben werden

In der Formel - der Maximalwert der (n+1)-ten Ableitung der ursprünglichen Funktion f(X) auf dem Segment [ x 0 , xn]. Um den Interpolationsfehler abzuschätzen, sind daher einige zusätzliche Informationen über die ursprüngliche Funktion erforderlich (dies sollte klar sein, da eine unendliche Anzahl verschiedener Funktionen die gegebenen Anfangspunkte passieren kann, für die der Fehler unterschiedlich sein wird). Solche Informationen sind die Ableitung der Ordnung n + 1, die nicht so leicht zu finden ist. Im Folgenden wird gezeigt, wie Sie aus dieser Situation herauskommen. Wir bemerken auch, dass die Anwendung der Fehlerformel nur möglich ist, wenn die Funktion n + 1 mal differenzierbar ist.

Zum Bauen Lagrange-Interpolationsformel in MathCAD ist es bequem, die Funktion zu verwenden wenn.

wenn (cond, x, y)

Gibt den Wert von x zurück, wenn cond nicht 0 (wahr) ist. Gibt y zurück, wenn cond 0 (falsch) ist (Abbildung 3.6).

Interpolationsformeln von Lagrange, Newton und Stirling etc. bei Verwendung vieler Stützstellen auf dem gesamten Segment [ a, b] führen aufgrund der Häufung von Fehlern im Berechnungsprozess oft zu einer schlechten Annäherung. Außerdem führt eine Erhöhung der Knotenzahl aufgrund der Divergenz des Interpolationsprozesses nicht zwangsläufig zu einer Erhöhung der Genauigkeit. Um Fehler zu reduzieren, wird das gesamte Segment [ a, b] wird in Teilsegmente unterteilt und auf jedem wird die Funktion durch ein Näherungspolynom niedrigen Grades ersetzt. Das heißt Stückweise polynomiale Interpolation.

Eine der Interpolationsmethoden für das gesamte Segment [ a, b] ist Spline-Interpolation.

Spline heißt stückweise Polynomfunktion definiert auf dem Segment [ a, b] und mit einer bestimmten Anzahl kontinuierlicher Derivate auf dieses Segment. Die Vorteile der Spline-Interpolation gegenüber herkömmlichen Interpolationsverfahren liegen in der Konvergenz und Stabilität des Rechenvorgangs.

Betrachten Sie einen der häufigsten Fälle in der Praxis - die Interpolation der Funktion kubischer Spline.
Lassen Sie das Segment [ a, b] ist eine stetige Funktion. Lassen Sie uns eine Partition des Segments einführen:

und bezeichnen, .

Ein Spline, der einer gegebenen Funktion und Stützstellen (6) entspricht, ist eine Funktion, die die folgenden Bedingungen erfüllt:

1) auf jedem Segment ist die Funktion ein kubisches Polynom;

2) die Funktion , sowie ihre erste und zweite Ableitung sind stetig auf der Strecke [ a, b] ;

Die dritte Bedingung wird aufgerufen Interpolationsbedingung. Ein durch die Bedingungen 1) - 3) definierter Spline wird aufgerufen interpolierender kubischer Spline.

Betrachten Sie ein Verfahren zum Konstruieren eines kubischen Splines.

Auf jedem der Segmente suchen wir eine Spline-Funktion in Form eines Polynoms dritten Grades:

(7)

wo gewünschten Koeffizienten.

Wir differenzieren (7) dreimal nach X:

woraus folgt

Aus der Interpolationsbedingung 3) erhalten wir:

Sie folgt aus den Stetigkeitsbedingungen der Funktion.

Ministerium für Bildung und Wissenschaft der Russischen Föderation

Bundeshaushalt Bildungseinrichtung höhere Berufsausbildung

"Don State University"

Fachgebiet „Software für Technische Informatik und Automatisierte Systeme“ „POVT und AS“

Spezialität: Mathematische Unterstützung und Verwaltung von Informationssystemen

KURSARBEIT

in der Disziplin „Rechenmethoden“

zum Thema: "Interpolation durch Splines"

Arbeitsleiter:

Medwedew Tatjana Alexandrowna

Rostow am Don

ÜBUNG

für eine Hausarbeit im Fach "Methods of Computation"

Student: Alexander Moiseenko VBMO21-Gruppe

Thema: "Interpolation durch Splines"

Abgabefrist für Verteidigungsarbeiten „__“ _______ 201_

Anfangsdaten für Seminararbeit: Vorlesungsunterlagen zu Berechnungsmethoden, ru.wikipedia.org, Buch. Workshop zur höheren Mathematik Sobol B.V.

Abschnitte des Hauptteils: 1 ÜBERSICHT, 2 INTERPOLATIONSFORMEL, 3 WÜRFELINTERPOLATIONSALGORITHMUS, 4 SOFTWAREDESIGN, 5 SOFTWAREBETRIEBSERGEBNISSE.

Arbeitsleiterin: /Medvedeva T.A./

AUFSATZ

Der Bericht enthält: Seiten-19, Grafiken-3, Quellen-3, Blockdiagramm-1.

Schlüsselwörter: INTERPOLATION, SPLINE, Mathcad System, KUBISCHE INTERPOLATION DURCH SPLINES.

Die Methode der Interpolation durch kubische Splines wird ausführlich betrachtet. Das entsprechende Softwaremodul wird angezeigt. Dargestellt ist das Blockschaltbild des Programmoduls. Mehrere Beispiele wurden betrachtet.

EINLEITUNG

1. THEORETISCHE ÜBERPRÜFUNG

2. INTERPOLATION

2.1 Interpolation mit einem quadratischen Spline

2.2 Interpolation mit einem kubischen Spline

2.3 Problemstellung

3. INTERPOLATIONSALGORITHMUS UNTER VERWENDUNG DES CUBIC SPLINE

4. SOFTWAREDESIGN

5. ERGEBNISSE DES BETRIEBES DER SOFTWARE

5.1 Beschreibung von Beispielen

5.2 Testergebnis

5.3 Testfall 1

5.4 Testfall 2

5.5 Testfall 3

FAZIT

LITERATURVERZEICHNIS

EINLEITUNG

Die Annäherung von Funktionen besteht in der ungefähren Ersetzung der gegebenen Funktion f(x) durch eine Funktion j( x) so dass die Abweichung der Funktion j( x) aus f(x) im gegebenen Bereich war am kleinsten. Funktion j( X) wird Annäherung genannt. Ein typisches Funktionsapproximationsproblem ist das Interpolationsproblem. Die Notwendigkeit der Funktionsinterpolation hat hauptsächlich zwei Gründe:

1. Funktion f(x) hat eine komplexe analytische Beschreibung, die bestimmte Schwierigkeiten bei der Verwendung verursacht (z. B. f(x) ist eine spezielle Funktion: Gamma-Funktion, elliptische Funktion usw.).

2. Analytische Beschreibung der Funktion f(x) unbekannt, d.h. f(x) ist in einer Tabelle angegeben. In diesem Fall ist eine ungefähr repräsentative analytische Beschreibung erforderlich f(x) (zum Beispiel um die Werte zu berechnen f(x) an beliebigen Punkten, Definitionen von Integralen und Ableitungen von f(x) usw.).

1. THEORETISCHE ÜBERPRÜFUNG

Interpolation - in der Computermathematik eine Möglichkeit, Zwischenwerte einer Größe aus einer vorhandenen diskreten Menge zu finden bekannte Werte. Bei der Lösung von Problemen mit wissenschaftlichen und technischen Berechnungen ist es oft erforderlich, mit empirisch oder methodisch gewonnenen Wertesätzen zu arbeiten zufällige Probe. In der Regel ist es erforderlich, auf der Grundlage dieser Sätze eine Funktion zu konstruieren, auf die andere erhaltene Werte mit hoher Genauigkeit fallen könnten. Dieses Problem wird Approximation von Funktionen genannt. Interpolation ist eine Art Approximation von Funktionen, bei der die Kurve der konstruierten Funktion genau durch die verfügbaren Datenpunkte verläuft.

Spline ist eine Funktion, deren Definitionsbereich in eine endliche Anzahl von Segmenten unterteilt ist, auf denen der Spline mit einem algebraischen Polynom zusammenfällt. Der maximale Grad der verwendeten Polynome wird als Grad des Splines bezeichnet. Die Differenz zwischen dem Grad des Splines und der daraus resultierenden Glätte wird als Spline-Defekt bezeichnet.

Splines ermöglichen es, die Probleme der Verarbeitung experimenteller Abhängigkeiten zwischen Parametern, die eine ziemlich komplexe Struktur haben, effektiv zu lösen.

Kubische Splines haben eine breite praktische Anwendung gefunden. Die Grundideen der Theorie der kubischen Keile sind das Ergebnis von Versuchen, flexible Schienen aus elastischem Material (mechanische Keile) mathematisch zu beschreiben, die seit langem von Zeichnern verwendet werden, wenn es notwendig wurde, eine ausreichend glatte Kurve durchzuziehen gegebene Punkte. Es ist bekannt, dass eine Schiene aus einem elastischen Material, die an bestimmten Punkten fixiert ist und sich in einer Gleichgewichtslage befindet, eine Form annimmt, in der ihre Energie minimal ist. Diese grundlegende Eigenschaft macht es möglich, Splines effektiv bei der Lösung praktischer Probleme der Verarbeitung experimenteller Informationen zu verwenden.

2. INTERPOLATION

2.1 Interpolation mit einem quadratischen Spline

Auf jedem Teilsegment der Interpolation bauen wir also eine Funktion der Form:

Wir suchen nach Spline-Koeffizienten unter den folgenden Bedingungen:

a) Lagrange-Bedingungen

b) Stetigkeit der ersten Ableitung an Knotenpunkten

Die letzten beiden Bedingungen geben Gleichungen, während die Anzahl der unbekannten Koeffizienten. Die fehlende Gleichung kann aus zusätzlichen Bedingungen gewonnen werden, die dem Verhalten des Splines auferlegt werden. Beispielsweise können Sie fordern, dass der Wert der ersten Ableitung des Splines s 1 am Punkt x 0 Null ist, d. h.

Die Substitution dieser Ausdrücke führt zu den folgenden Gleichungen

wo die Notation

Lassen Sie uns die Koeffizienten aus der zweiten Gleichung ausdrücken c 1 , nachdem die Werte der Koeffizienten darin eingesetzt wurden a 1 aus der ersten Gleichung:

Wenn wir dann diesen Ausdruck in die Gleichung des Systems einsetzen, erhalten wir eine einfache rekursive Beziehung für die Koeffizienten

Nun wird der Algorithmus zur Bestimmung der Koeffizienten von Splines ziemlich offensichtlich. Zuerst bestimmen wir mit der Formel die Werte aller Koeffizienten unter Berücksichtigung der Tatsache, dass. Dann berechnen wir gemäß der Formel die Koeffizienten. Die Koeffizienten werden aus der ersten Gleichung des Systems bestimmt. In diesem Fall muss das Verfahren zum Berechnen der Spline-Koeffizienten nur einmal durchgeführt werden.

Nachdem die Koeffizienten berechnet wurden, genügt es, um den Spline selbst zu berechnen, die Nummer des Intervalls zu bestimmen, in das der Interpolationspunkt fällt, und die Formel zu verwenden. Um die Intervallnummer zu bestimmen, verwenden wir einen ähnlichen Algorithmus wie im vorherigen Beispiel für die stückweise quadratische Interpolation.

2.2 Interpolation mit einem kubischen Spline

Kubischer Interpolations-Spline , für diese Funktion geeignet f(x) und gegebenen Knoten x ich, Funktion genannt S(x), folgende Bedingungen erfüllen:

1. Auf jedem Segment [ x ich- 1 , x ich], ich = 1, 2, ..., N Funktion S(x) ist ein Polynom dritten Grades,

2. Funktion S(x), und auch seine erste und zweite Ableitung sind stetig auf dem Intervall [ ein, b],

3. S(x ich)= f(x ich), ich = 0, 1, ..., N.

Auf jedem der Segmente [x ich- 1 , x ich], ich = 1, 2, ..., N Wir werden nach einer Funktion suchen S(x)=S ich(x) in Form eines Polynoms dritten Grades:

S ich(x)= ein ich+b ich(x-x ich- 1)+c ich(x-x ich- 1) 2 +d ich(x- 1) 3 ,

x ich- 1 Ј xЈ x ich,

wo a ich,b ich, c ich, d ich- überhaupt zu bestimmende Koeffizienten n elementare Segmente. Damit ein algebraisches Gleichungssystem eine Lösung hat, muss die Anzahl der Gleichungen genau gleich der Anzahl der Unbekannten sein. Wir sollten also 4 bekommen n Gleichungen.

Erste 2 n Wir erhalten die Gleichungen aus der Bedingung, dass der Graph der Funktion S(x) müssen die vorgegebenen Punkte passieren, d.h.

S ich(x ich- 1)= ja ich- 1 , S ich(x ich) = j ich.

Diese Bedingungen können geschrieben werden als:

S ich(x ich- 1)= ein ich= ja ich- 1 ,

S ich(x ich)= ein ich+b ichh ich+c ichh + d ichh = j ich,

h ich= x ich- x ich- 1 , ich = 1, 2, ..., n.

Weiter 2 n- 2 Gleichungen folgen aus der Bedingung der Stetigkeit der ersten und zweiten Ableitung an den Interpolationsknoten, d. h. der Bedingung der Glattheit der Kurve an allen Punkten.

S" ich + 1 (x ich)=S" ich(x ich), ich = 1, ..., n - 1,

S"" ich + 1 (x ich)=S"" ich(x ich), ich = 1, ..., n - 1,

S" ich(x)= b ich + 2 c ich(x-x ich- 1) + 3 d ich(x-x ich- 1),

S" ich + 1 (x)= b ich + 1 + 2 c ich + 1 (x-x ich) + 3 d ich + 1 (x-x ich).

Gleichsetzen an jedem internen Knoten x = x ich die Werte dieser Ableitungen, berechnet in den Intervallen links und rechts vom Knoten, erhalten wir (unter Berücksichtigung h ich= x ich- x ich- 1):

b ich + 1 = b ich + 2 h ichc ich + 3h d ich, ich = 1, ..., n - 1,

S"" ich(x) = 2 c ich + 6 d ich(x-x ich- 1),

S"" ich + 1 (x) = 2 c ich + 1 + 6 d ich + 1 (x-x ich),

wenn x = x ich

c ich + 1 = c ich + 3 h ichd ich, ich = 1, 2, ..., n- 1.

Auf der diese Phase wir haben 4 n unbekannt und 4 n- 2 Gleichungen. Daher müssen zwei weitere Gleichungen gefunden werden.

Bei freier Fixierung der Enden kann die Krümmung der Leitung an diesen Punkten gleich Null gesetzt werden. Aus den Bedingungen der Nullkrümmung an den Enden folgt, dass die zweiten Ableitungen an diesen Stellen gleich Null sind:

S 1" " (x 0) = 0 und S n" "(x n) = 0,

c ich = 0 und 2 c n + 6 d nh n = 0.

Die Gleichungen bilden ein System linearer algebraischer Gleichungen zur Bestimmung von 4 n Koeffizienten: a ich,b ich, c ich, d ich (ich = 1, 2, . . ., n).

Dieses System kann auf eine bequemere Form reduziert werden. Aus der Bedingung können Sie sofort alle Koeffizienten finden a ich .

ich = 1, 2, ..., n- 1,

Einsetzend erhalten wir:

b ich = - (c ich + 1 + 2c ich), ich = 1, 2, ..., n- 1,

b n = - (h nc n)

Eliminiere die Koeffizienten aus der Gleichung b ich und d ich. Schließlich erhalten wir nur für die Koeffizienten das folgende Gleichungssystem Mit ich:

c 1 = 0 und c n+ 1 = 0:

h ich- 1 c ich- 1 + 2 (h ich- 1 + h ich) c ich+ h ichc ich + 1 = 3 ,

ich = 2, 3, ..., n.

Nach den gefundenen Koeffizienten Mit ich leicht zu berechnen d ich,b ich.

2.3 Problemstellung

Auf dem Abschnitt [ ein, b] sind gegeben n + 1 Punkte x ich = X 0 , X 1 , . . ., X n, die Knoten genannt werden Interpolation , und der Wert einer Funktion f(x) an diesen Stellen

f(x 0)= ja 0 , f(x 1) = j 1 , . . ., f(x n)= ja n.

Verwenden von kubischen Splines zum Erstellen einer Interpolationsfunktion f(x).

3. INTERPOLATIONSALGORITHMUS UNTER VERWENDUNG DES CUBIC SPLINE

Machen wir uns mit dem Algorithmus des Programms vertraut.

1. Berechnen Sie die Werte und

2. Basierend auf diesen Werten berechnen wir die Sweep-Koeffizienten und o.

3. Basierend auf den erhaltenen Daten berechnen wir die Koeffizienten

4. Dann berechnen wir den Wert der Funktion mit dem Spline.

4. SOFTWAREDESIGN

5. ERGEBNISSE DER SOFTWARE

5.1 Beschreibung der Testfälle

Im Zuge dieser Studienarbeit wurde ein Softwaremodul entwickelt, das eine ihnen entsprechende Kurve durch die zur Verfügung stehenden Punkte zeichnet. Um die Wirksamkeit der Arbeit zu überprüfen, wurden Testfälle durchgeführt.

5.2 Testergebnisse

Zur Überprüfung der korrekten Ausführung von Testfällen wird die im MATHCAD-Paket eingebaute Funktion cspline verwendet, die bei Annäherung an ein kubisches Polynom an den Referenzpunkten den Vektor der zweiten Ableitung zurückliefert.

5.3 Testfall 1

Abbildung 1.1 - das Ergebnis des Programms

Testfall 2

Abbildung 1.2 - das Ergebnis des Programms

Testfall 3

Abbildung 1.3 - das Ergebnis des Programms

FAZIT

Spline-Interpolationsfunktion rechnerisch

In der Computermathematik spielt die Interpolation von Funktionen eine wesentliche Rolle, d.h. Konstruktion einer gegebenen Funktion einer anderen (normalerweise einfacheren), deren Werte an einer bestimmten Anzahl von Punkten mit den Werten der gegebenen Funktion übereinstimmen. Darüber hinaus hat die Interpolation sowohl praktische als auch theoretische Bedeutung. In der Praxis tritt oft das Problem auf, eine stetige Funktion aus ihren Tabellenwerten wiederherzustellen, die man zum Beispiel im Laufe eines Experiments erhält. Um viele Funktionen zu berechnen, erweist es sich als effizient, sie durch Polynome oder gebrochene rationale Funktionen zu approximieren. Die Theorie der Interpolation wird bei der Konstruktion und Untersuchung von Quadraturformeln für die numerische Integration verwendet, um Methoden zum Lösen von Differential- und Integralgleichungen zu erhalten. Der Hauptnachteil der Polynominterpolation besteht darin, dass sie auf einem der bequemsten und am häufigsten verwendeten Gitter instabil ist - einem Gitter mit äquidistanten Knoten. Wenn es das Problem zulässt, kann dieses Problem gelöst werden, indem ein Gitter mit Tschebyscheff-Knoten gewählt wird. Wenn wir jedoch Stützstellen nicht frei wählen können oder nur einen Algorithmus benötigen, der nicht zu anspruchsvoll bei der Wahl der Stützstellen ist, dann kann die rationale Interpolation eine geeignete Alternative zur polynomialen Interpolation sein.

Zu den Vorteilen der Spline-Interpolation gehört die hohe Verarbeitungsgeschwindigkeit des Rechenalgorithmus, da der Spline eine stückweise Polynomfunktion ist und bei der Interpolation gleichzeitig Daten für eine kleine Anzahl von Messpunkten verarbeitet werden, die zum betrachteten Fragment gehören dieser Moment. Die interpolierte Fläche beschreibt die räumliche Variabilität verschiedener Skalen und ist gleichzeitig glatt. Letzterer Umstand ermöglicht es, die Geometrie und Topologie der Oberfläche direkt mit analytischen Verfahren zu analysieren.

LITERATURVERZEICHNIS

1. B. V. Sobol, B. Ch. Meskhi, I. M. Peshkhoev. Workshop zur Computermathematik. - Rostow am Don: Phoenix, 2008;

2. N.S. Bakhvalov, N.P. Schidkow, G.M. Kobelkov. Numerische Methoden. Verlag "Labor für Grundlagenwissen". 2003

3. www.wikipedia.ru/spline

Ähnliche Dokumente

Rechenmethoden der linearen Algebra. Funktionsinterpolation. Newtons Interpolationspolynom. Interpolationsknoten. Lagrange-Interpolationspolynom. Spline-Interpolation. Koeffizienten kubischer Splines.

Laborarbeit, hinzugefügt am 06.02.2004


In der Computermathematik spielt die Interpolation von Funktionen eine wesentliche Rolle. Lagrange-Formel. Interpolation nach dem Aitken-Schema. Newtonsche Interpolationsformeln für äquidistante Knoten. Newtonsche Formel mit geteilten Differenzen. Spline-Interpolation.

Kontrollarbeiten, hinzugefügt am 01.05.2011


Bauen Interpolationspolynom Newton. Zeichnen Sie einen Graphen und markieren Sie darauf Stützpunkte. Konstruieren Sie das Lagrange-Interpolationspolynom. Führen Sie eine Spline-Interpolation dritten Grades durch.

Laborarbeit, hinzugefügt am 06.02.2004


Die Rolle der Interpolation von Funktionen, deren Werte mit den Werten einer bestimmten Funktion an einer bestimmten Anzahl von Punkten übereinstimmen. Interpolation von Funktionen durch Polynome, direkt stetige Funktionen auf einer Strecke und in einem Punkt. Definition des Begriffs Interpolationsfehler.

Seminararbeit, hinzugefügt am 10.04.2011


Kontinuierliche und Punktnäherung. Interpolationspolynome von Lagrange und Newton. Globaler Interpolationsfehler, quadratische Abhängigkeit. Methode der kleinsten Quadrate. Auswahl empirischer Formeln. Stückweise konstante und stückweise lineare Interpolation.

Seminararbeit, hinzugefügt am 14.03.2014


Bekanntschaft mit der Entstehungsgeschichte der Methode des Goldenen Schnitts. Berücksichtigung der grundlegenden Konzepte und Algorithmen zur Durchführung von Berechnungen. Studium der Fibonacci-Zahlenmethode und ihrer Eigenschaften. Beschreibung von Beispielen zur Implementierung der Methode des Goldenen Schnitts in der Programmierung.

Hausarbeit, hinzugefügt am 09.08.2015


Probleme der globalen und lokalen Interpolation von Lagrange und Newton; Kollektivverhalten des Interpolationspolynoms; Runge-Funktionen. Ein Spline ist eine Gruppe von Polynomen, die als kubische Polynome bezeichnet werden, mit einem nicht durchlässigen ersten und einem anderen ähnlichen, die Vorteile der Spline-Interpolation.

Präsentation, hinzugefügt am 06.02.2014


Methoden der numerischen Differentiation. Berechnung der Ableitung, die einfachsten Formeln. Numerische Differentiation basierend auf Interpolation durch algebraische Polynome. Approximation durch das Lagrange-Polynom. Differenzierung durch Interpolation.

Seminararbeit, hinzugefügt am 15.02.2016


Beschreibung von Methoden zum Lösen eines Systems linearer algebraischer Gleichungen: inverse Matrix, Jacobi, Gauß-Seidel. Formulierung und Lösung des Interpolationsproblems. Auswahl der polynomialen Abhängigkeit nach der Methode der kleinsten Quadrate. Merkmale der Entspannungsmethode.

Laborarbeit, hinzugefügt am 06.12.2011


Das Problem der Extremumsfindung: Wesen und Inhalt, Optimierung. Lösung durch Methoden der quadratischen Interpolation und des Goldenen Schnitts, ihre vergleichenden Eigenschaften, Bestimmung der wichtigsten Vor- und Nachteile. Anzahl der Iterationen und Schätzung der Genauigkeit.

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 der zusätzlichen Bedingungen richtet sich nach der Art des betrachteten Problems und manchmal einfach nach dem Wunsch des Benutzers. 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 aufzubauen. Bei Interpolationsproblemen ist es erforderlich, dass der Spline-Graph durch Punkte verläuft, die erlegt seinen Koeffizienten m + 1 zusätzliche Bedingungen (Gleichungen) auf. 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 der Strecke (a, 6) glatt ist und an den Gitterknoten o die gegebenen Werte annimmt, d. h. durch Auferlegen zusätzlicher Bedingungen an die zu konstruierende Funktion kann man die notwendige Eindeutigkeit erreichen oft wird es notwendig, eine gegebene Funktion analytisch durch eine hinreichend vorgeschriebene Funktion zu approximieren gute Eigenschaften . Beispielsweise in Fällen, in denen die Berechnung der Werte einer gegebenen Funktion f(x) an Punkten des Segments [a, 6] mit erheblichen Schwierigkeiten verbunden ist und/oder die gegebene Funktion f(x) die nicht hat erforderlicher Glätte, ist es bequem, eine andere Funktion zu verwenden, die eine gegebene Funktion gut genug annähert und frei von ihren festgestellten Mängeln ist. Funktionsinterpolationsproblem. Konstruieren Sie auf dem Intervall [a, 6] eine glatte Funktion a(x), die an den Knoten des Gitters w mit der gegebenen Funktion f(x) zusammenfällt. 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 das Vorhandensein bestimmt zusätzliche Information auf das Verhalten der angenäherten Funktion f(x). 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 Berechnungserfahrungen zeigen, dass in der betrachteten Situation Randbedingungen vom Typ 4 die geeignetste Wahl sind. B. Wahl der Stützstellen. Wenn die dritte Ableitung f " " (x) der Funktion ist an einigen Stellen der Strecke [a, b] unstetig, dann sollten zur Verbesserung der Güte der Approximation diese Stellen in die Anzahl der Stützstellen mit einbezogen werden. zweite Ableitung / "(x), Um ein Schwingen des Keils in der Nähe der Unstetigkeitspunkte zu vermeiden, müssen dann besondere Maßnahmen ergriffen werden Stützstellen werden so gewählt, dass die Unstetigkeitsstellen der zweiten Ableitung in das Intervall \xif) fallen, so dass. Der Wert von a kann durch numerische Experimente gewählt werden (oft reicht es aus, a = 0,01 zu setzen). Es gibt eine Reihe von Rezepten zur Überwindung der Schwierigkeiten, die auftreten, wenn die erste Ableitung f "(x) unstetig ist. Als eines der einfachsten können wir Folgendes vorschlagen: Unterteile das Approximationssegment in Intervalle, in denen die Ableitung stetig ist, und bilde a Spline auf jedem dieser Intervalle Auswahl einer Interpolationsfunktion (Vor- und Nachteile) Ansatz 1. Lagrange-Interpolationspolynom Für ein gegebenes Array SPLINE-THEORIE-Beispiele für Lösungen (Abb. 3) Das Lagrange-Interpolationspolynom wird durch die Formel bestimmt Es ist ratsam zu berücksichtigen die Eigenschaften des Lagrange-Interpolationspolynoms aus zwei entgegengesetzten Positionen, Erörterung der Hauptvorteile getrennt von den Nachteilen -ter Ansatz: 1) der Graph des Lagrange-Interpolationspolynoms verläuft durch jeden Punkt des Arrays, 2) die konstruierte Funktion ist leicht zu beschreiben ( die Anzahl der Koeffizienten des Lagrange-Interpolationspolynoms auf dem zu bestimmenden Gitter u ist gleich m + 1), 3) die konstruierte Funktion hat stetige Ableitungen jeder Pore 4) das Interpolationspolynom ist durch ein gegebenes Array eindeutig definiert. 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 durch ein Polynom so gut wie gewünscht auf diesem Intervall 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 Intervalls [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 leiden an einer 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 das gegebene 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 kubische Interpolations-Spline hat einen weiteren 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 Erfüllung der Randbedingungen eines der drei angegebenen Typen ist eindeutig definiert Definition: Ein kubischer Spline, der das Funktional J(f) minimiert und die Randbedingungen des i-Typs erfüllt, heißt glättender Spline des i-Typs .dieses Segment 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 der Gitter 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 Addiert man zu diesen m - 1 Gleichungen zwei weitere, die sich aus und von den Randbedingungen ergeben, erhält man 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. Linearer Raum kubischer Spline-Funktionen Die Menge kubischer Splines, die auf dem Segment [a, 6) durch den Knoten wcra + l konstruiert wird, ist ein linearer Raum der Dimension m + 3: 1) die Summe zweier kubischer Splines, die durch das Gitter u> konstruiert wird und das Produkt eines kubischen Splines, das auf dem Gitter u> aufgebaut ist, 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 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 bestimmt durch die rekursive Formel zweite in \7\x) Grade 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 verschieden sein. 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 Rand Bedingungen der ersten Art), werden diese Koeffizienten aus dem System der folgenden Form berechnet Werte b-i und &m+i erhalten wir ein lineares System mit den Unbekannten 5q, ... , bm und einer Drei-Diajunal-Matrix. Die Bedingung gewährleistet eine diagonale Dominanz und damit die Möglichkeit, die Sweep-Methode anzuwenden, um sie aufzulösen. 3MMCHMYU 1. Lineare Systeme ähnlicher Form ergeben sich auch bei der Betrachtung anderer Interpolationsprobleme. Zmmchm* 2. Im Vergleich zu den in Abschnitt 1.1 beschriebenen Algorithmen können Sie durch die Verwendung von R-Spline bei * Interpolationsproblemen die Menge der gespeicherten Informationen reduzieren *, dh die Anforderungen an den Computerspeicher erheblich reduzieren, obwohl dies zu führt eine Erhöhung der Zahl der Operationen. 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. in einem beliebigen Intervall)