Quelle Nummer 121
Rubrik 27 : MATHEMATIK Unterrubrik 27.02 : FACHWISSENSCHAFTLICH
TSCHEBYSCHEFF-APPROXIMATION
GUENTHER SCHMITGEN
TSCHEBYSCHEFF-APPROXIMATION VON INTERVALLFUNKTIONEN
DURCH VERALLGEMEINERTE INTRVALLPOLYNOME,
GESELLSCHAFT FUER MATHEMATIK UND DATENVERARBEITUNG
DURCH VERALLGEMEINERTE INTRVALLPOLYNOME,
BONN, NR. 26, BIRLINGHOVEN 1970, S. 1-13
001 Inhaltsübersicht. Die vorliegende Arbeit befaßt sich
002 mit der Einschließung von Intervallfunktionen durch
003 Intervallpolynome. Die Grundlagen der Intervallanalysis - in
004 dieser Arbeit stets im Gitter der reellen Zahlen zu verstehen -
005 dürfen als bekannt vorausgesetzt werden; man siehe hierzu z *bpn
006 B. Moore oder Krückeberg. Die über die
007 intervallarithmetischen Grundoperationen hinaus notwendigen
008 Begriffe und Definitionen sind in Kapitel 1 zusammengestellt. Im
009 weiteren wird dort in die Problemstellung eingeführt: Zu einer
010 gegebenen Intervallfunktion F werden Intervallpolynome P gesucht,
011 derart daß P F einschließt, und diese Einschließung
012 möglichst eng ist. Als Maß für die Güte der Approximation
013 dient dabei die Metrik (Formel) wobei (Formel) eine Norm für (Formel) bedeutet.
014 Es handelt sich hierbei um ein Approximationsproblem im Bereich
015 der (Formel) wertigen Funktionen unter konvexen beschränkenden
016 Bedingungen. Diese Fragestellung führt über das Gebiet der
017 Approximation reellwertiger Funktionen hinaus. Andererseits
018 erhält man durch Berücksichtigung der konkreten Gegebenheiten des
019 intervallanalytischen Problems stärkere Aussagen, als wenn man
020 nur die allgemeine Theorie der Approximation in normierten Räumen
021 anwenden würde. Kapitel 2 befaßt sich mit der Existenz von
022 einschließenden Intervallpolynomen, von solchen bester
023 Approximation im oben angedeuteten Sinn, und mit der Konvergenz
024 der Elemente bester Approximation gegen F, wenn man zur
025 Approximation eine Folge von Intervallpolynommengen wachsender
026 Dimension zugrunde legt. In Kapitel 3 werden Charakterisierungen
027 für Intervallpolynome bester Approximation in Form des
028 Kolmogoroff-Kriteriums und mit Hilfe linearer
029 Punktfunktionale aufgestellt. Daraus lassen sich in Kapitel 4
030 Aussagen über die Gesamtheit der Elemente bester Approximation,
031 speziell deren Dimension herleiten. Weiterführende Aussagen
032 erhält man, wenn für die zu approximierende Intervallfunktion
033 gewisse Struktureigenschaften vorausgesetzt werden. Von besonderer
034 Bedeutung sind dabei die beiden Spezialfälle, daß F symmetrisch,
035 bzw. daß F eine Punktfunktion ist; schon deshalb, weil man
036 jede Intervallfunktion in einen symmetrischen und einen Punktanteil
037 aufspalten kann. In Kapitel 5 und Kapitel 6 werden für diese
038 beiden Fälle die Charakterisierungen so präzisiert, daß sich
039 Methoden zur effektiven Berechnung von Intervallpolynomen bester
040 Approximation ergeben. Der erste Teil von Kapitel 7 enthält
041 einfache Beispiele, die die Aussagen der früheren Kapitel
042 illustrieren sollen. Im zweiten Teil wird auf die numerische
043 Bestimmung der Intervallpolynome bester Approximation eingegangen.
044 An Hand von Zahlenwerten, die mit Hilfe von FORTRAN 2
045 - Programmen auf der Rechenanlage IBM 7090-1410 der GMD
046 Bonn gewonnen wurden, werden dabei auftretende Fragen erläutert.
047 Für die Anregung und Förderung dieser Arbeit bin ich Herrn
048 Prof. Dr. F. Krückeber g zu großem Dank
049 verpflichtet.Einleitung. In vielen Gebieten der
050 angewandten Mathematik ist in den letzten Jahren mit großem
051 Erfolg Intervall-Analysis eingesetzt worden. Erst nur als
052 Intervallarithmetik, als Rechentechnik zur absolut sicheren
053 Fehlererfassung konzipiert, hat sie sich zur selbständigen
054 Disziplin mit eigenen Mitteln und Methoden entwickelt. Als
055 besonders brauchbares Mittel haben sich dabei Intervallpolynome
056 erwiesen. Auf ihre Bedeutung und Anwendung braucht hier nicht
057 weiter eingegang en zu werden, es genügt, auf Krückeberg zu
058 verweisen. Ebenfalls ist aber dort auch auf die Notwendigkeit
059 hingewiesen, Methoden zu entwickeln, für Intervallfunktionen
060 einschließende Intervall polynome zu berechnen, die in einem
061 näher zu präzisierenden Sinn optimal sind. In dieser Arbeit
062 wird die Güte der Intervallpolynomapproximation in
063 Verallgemeinerung des Gedankens der Tschebyscheff-
064 Approximation bei reellen Funktionen definiert. Das entspricht
065 besonders eng dem Grundkonzept der Intervallanalysis, nämlich der
066 sicheren, aber möglichst engen Einschließung. Aus der
067 Intervallanalysis ergibt sich also hier eine Fragestellung der
068 Approximationstheorie, wobei jedoch der speziellen, aus dem
069 Kalkül der Intervallarithmetik herrührenden Gestalt der
070 Intervallpolynome Rechnung zu tragen ist. Alle Untersuchungen in
071 dieser ArArbeit werden im Gitter der reellen Zahlen durchgeführt.
072 Wollte man gleich ein endliches Gitter zugrunde legen, wie es z.B.
073 auf einer Rechenanlage realisiert ist, so ergäben sich
074 äußerste Schwierigkeiten, da dann fast der gesamte Apparat der
075 Analysis micht mehr anwendbar wäre. Die im reellen Gitter
076 erhaltenen Charakterisisierungen für Intervallpolynome bester
077 Approximation lassen sich jedoch nachträglich benutzen, um, mit
078 ähnlichen Met hoden, wie sie von Härtrich - Sprinkmeier im
079 Spezialfall angewendet werden, optimale Intervallpolynome im
080 endlichen Gitter zu erhalten. Für die hier angestellten
081 Betrachtungen erwies sich der Begriff des Intervallpolynoms in der
082 normalen Form (Formel) als zu eng. Schon allein die Tatsache, daß
083 die geometrische Gestalt solcher Polynomstreifen sehr vom zugrunde
084 liegenden Definitionsintervall abhängig und nicht felxibel genug
085 ist, gab Anlaß zur Definition des verallgemeinerten
086 Intervallpolynoms (Formel) mit beliebigen Punktfunktionen (Formel). Beim
087 Übergang zur Maschinenintervallarithmetik ist dabei die Forderung
088 zu stellen, daß sich die (Formel) ähnlich wie die Potenzen (Formel) leicht
089 und mit minimalem Genauigkeitsverlust auswerten lassen.
090 Kapitel 1: Grundlegende Begriffe und Problemstellung. (Formel)
091 sei die Menge aller abgeschlossenen endlichen reellen Intervalle.
092 Ist (Formel), dann werde mit (Formel), bzw. (Formel) die linke, bzw.
093 rechte Ecke von a bezeichnet; für a kann also auch (Formel)
094 geschrieben werden. Bekanntlich läßt sich (Formel) in (Formel) durch die
095 Zuordnung (Formel) einbetten. Für (Formel) sei die " Weite " von a durch
096 (Formel) definiert. Dann gilt: (Formel). (Formel) bedeute eine beliebige Norm
097 in (Formel); speziell werden später folgende Normen benutzt werden:
098 (Formel), (Formel). Im folgenden Lemma werden einige bekannte Aussagen
099 über die Normen (Formel) zusammengestellt, die weiterhin häufig
100 benutzt werden: Lemma: Sei (Formel) und (Formel). Dann
101 gilt: (Formel). Sei (Formel). Dann wird für (Formel) die N orm (Formel),
102 genau dann minimal auf S, wenn (Formel). Sei A ein kompakter
103 metrischer Raum (später wird A häufig als Intervall vorausge
104 setzt werden), C (A) die Menge der stetigen reellwertigen
105 Funktionen auf A. Für (Formel) sei (Formel) die Tschebyscheff - Norm.
106 Sind (Formel), (Formel), dann (Formel); analog für (Formel). Für (Formel) seien (Formel),
107 (Formel) und (Formel) wie folgt definiert: (Formel) falls (Formel) sonst (Formel) falls (Formel)
108 sonst (Formel) Es ist (Formel); (Formel). Definition: (Formel) heißt
109 Intervallfunktion genau dann, wenn für alle (Formel) gilt (Formel), d.h.
110 für alle (Formel) ist (Formel). Die Menge aller Intervallfunktionen
111 aus (Formel) werde mit (Formel) bezeichnet. Für (Formel) sei (Formel) als
112 Mittelfunktion von F definiert. Ist (Formel), d. h. (Formel), so
113 heiße F symmetrisch. Ist (Formel), so heiße F Punkt (intervall)
114 funktion. Durch (Formel) wird (Formel) in (Formel) eingebettet. Dabei entspricht
115 (Formel) gerade der Menge der Punktintervallfunktionen. Für (Formel) sei
116 definiert: (Formel). Sei F Intervallfunktion, (Formel) eine (Formel)-
117 Norm, dann sei: (Formel) Ist (Formel), so werde (Formel) geschrieben. (Formel)
118 heiße die durch die (Formel)-Norm (Formel) erzeugte
119 Intervallfunktionennorm. Erweitert man die Definition von (Formel) auf
120 (Formel), so ist (Formel) eine Norm für (Formel), und die Menge der
121 Intervallfunktionen bildet einen abgeschlossenen konvexen Kegel mit
122 Spitze in (Formel) in dem Banachraum (Formel). Dabei ist 0 die
123 Nullfunktion in (Formel). Intervallpolynome. Seien (Formel), (Formel),
124 linear unabhängig; (Formel) sei die Menge aller Polynome in (Formel).
125 Für (Formel) sei (Formel) die Menge der Elemente bester Tschebyscheff-
126 Approximation (T-Approximation) aus H an f. (Formel) sei die
127 Minimalabweichung. Bekanntlich ist (Formel) stets nicht leer, und
128 besteht genau dann für alle (Formel) aus genau einem Element, wenn (Formel)
129 ein Tschebyscheff-System (T-System) auf A bilden.
130 Definition Seien (Formel), (Formel). Dann heiße (Formel) mit (Formel) (Formel)
131 (die Multiplikation und Addition ist hier im Sinne der
132 Intervallarithmetik zu verstehen) ein (verallgemeinertes)
133 Intervallpolynom. P ist Intervallfunktion und es gilt, wenn man
134 P nach den Regeln der Intervallarithmetik auswertet: (Formel). Man
135 beachte, daß (Formel) ein echtes Punktpolynom ist, d. h. (Formel);
136 dagegen sind (Formel) und (Formel) i. a. keine Polynome, sondern haben
137 nur stückweise Polynomcharakter, nämlich in Teilmengen von A,
138 die keine Zeichenwechsel von (Formel), enthalten. P läßt sich als
139 Paar (Formel) darstellen, wobei (Formel) und (Formel) die oben angegebene Gestalt
140 haben. Seien nun (Formel), (Formel), so soll diese Darstellung als
141 Definition für (Formel) dienen. Die Menge aller (Formel) mit (Formel) werde mit
142 V bezeichnet, W oder W (Formel), falls das System (Formel) besonders
143 gekennzeichnet werden soll, sei die Menge aller Intervallpolynome,
144 d. h. aller (Formel) mit (Formel). Ist (Formel) eine Intervallfunktion,
145 dann sei (Formel). Für (Formel) und (Formel) seien folgende charakteristischen
146 Mengen definiert: Definition *ne (Formel). Wegen der
147 Stetigkeit von F und P (d. h. Stetigkeit von (Formel)) sind
148 diese Mengen kompakt. Es sei besonders darauf hingewiesen, daß
149 in den Ausdrücken P (math.Op.) F und (Formel) (math.Op.) (Formel) das Minuszeichen nicht
150 im Sinne der Intervallarithmetik, sondern als (Formel) (math.Op.) Operation
151 zu verstehen ist. Es entspricht der Operation *yd bei Ortolf.
152 Generell bedeutet, wenn (Formel) ist, (Formel). Speziell werde verabredet,
153 daß für gemischte Ausdrücke mit (Formel), (Formel) gelten soll: (Formel).
154 Das Approximationsproblem, das in dieser Arbeit behandelt wird,
155 lautet nun: Problemstellung: Gegeben sei eine
156 Intervallfunktion F, eine Intervallfunktionennorm (Formel) und ein
157 Kegel W von Intervallpolynomen. Gesucht sind diejenigen P *ye
158 W mit P *ye W (F) (Formel) Die Menge aller P *ye
159 W, die und erfüllen, werde mit TW (F) bzeichnet.
160 Ist dabei speziell eine der Normen (Formel), (Formel), gemeint, so werde
161 das durch den Index r in T W (F) und E W (F) gekennzeichnet.
162 Das Problem ist eine Übertragung der einseitigen T-
163 Approximation für reellwertige Funktionen, wie in der Literatur
164 z. B bei Laurent behandelt, auf (Formel)-wertige Funktionen.
165 Hinzu kommt allerdings als weitere beschränkende Bedingung, daß
166 die approximierenden (Formel)-Polynome die unter angegebene
167 spezielle Gestalt haben müssen, insbesondere, daß für die
168 Koeffizientenpaare (Formel) gelten muß (Formel) d. h. (Formel). Aus der
169 Problemstellung ergeben sich nun folgende Fragen:
170 Wann ist (Formel), wann (Formel)? (Existenz)) Wann besteht (Formel) aus
171 genau einem Element? (Eindeutigkeit) Wie läßt sich (Formel)
172 beschreiben? (Charakterisierung) + Die Frage läßt
173 sich leicht generell beantworten. Die Lösung von geschieht
174 mit Hilfe von Verallgemeinerungen des Kolmogoroff-Kriteriums
175 und mittels linearer Punktfunktionale, die auf den Mengen (Formel) und
176 (Formel) basieren. Frage läßt sich nur in Spezialfällen unter
177 einschränkenden Bedingungen positiv beantworten. Im allgemeinen
178 liegt keine Eindeutigkeit vor, jedoch lassen sich Schranken für
179 die Dimension von (Formel) angeben. Die Aufgabe kann ebenfalls nur
180 in Spezialfällen durch einen eigenen problemorientierten
181 Algorithmus gelöst werden, schon au s dem Grunde, daß man für
182 die Konvergenz vom Verfahren meist Eindeutigkeit verlangen muß.
183 Der allgemeine Fall mit den Normen (Formel) und (Formel) läßt sich
184 jedoch durch Diskretisierung auf ein Problem des Linear
185 Programming zurückführen. Kapitel 2: Existenzfragen.
186 Sei (Formel) und V wie in Kapitel 1 definiert. Dann wird durch die
187 Zuordnung (Formel) mit (Formel), (Formel) eine lineare Abbildung (Formel) definiert.
188 Satz: Die Abbildung *yf ist bijektiv genau dann,
189 wenn (Formel) linear unabhängig sind. Beweis: Daß *yf
190 surjektiv ist, ergibt sich sofort aus der Definition von V. Es
191 bleibt also zu zeigen, daß für alle (Formel) mit (Formel) gilt genau dann,
192 wenn (Formel) linear unabhängig sind. Angenommen, es seien (Formel) und (Formel),
193 d. h (Formel) und (Formel) Durch Addition von und
194 ergibt sich (Formel) und daraus wegen der linearen Unabhängigkeit der
195 (Formel) (Formel) Sei (Formel), dann erhält man durch Einsetzen von in
196 und (Formel). Mit (Formel) ist also (Formel) und damit (Formel) linear
197 abhängig. Ist umgekehrt (Formel) mit (Formel) erfüllt, so definiert (Formel)
198 durch (Formel) und (Formel). Es ist (Formel), und a und b erfüllen mit *n r;
199 d. h. es gilt (Formel). Analog, wie sich (Formel) in (Formel) einbetten
200 läßt, so lassen sich auch die Koeffiziententupel der
201 Intervallpolynome in (Formel) einbetten. Definiere: (Formel) M ist
202 abgeschlossener konvexer Kegel in (Formel) mit (Formel), denn es ist (Formel).
203 Sei nämlich (Formel), dann definiere (Formel) durch (Formel), (Formel). Dann sind
204 (Formel) und (Formel). Jedem (Formel) wird nun mittels *yf ein Intervallpolynom
205 zugeordnet, d. h. es ist (Formel). Wegen der Linearität von
206 *yf ist also (Formel) und (Formel). korollar: Sei A ein
207 Intervall und (Formel) ein Tschebyscheff-System auf A; dann ist
208 (Formel). Beweis: Nach Satz und den obigen Bemerkungen
209 ist zu zeigen, daß (Formel) linear unabhängig sind Wegen der
210 Haarschen Bedingung besitzt jedes (Formel) nur endlich viele
211 Nullstellen. Es gibt also ein nicht ausgeartetes Intervall B (math.Op.)
212 A, in dem die (Formel) vorzeichenfest sind. Dann gilt also in B:
213 (Formel) mit (Formel). Diese Linearkombination kann also in B, falls
214 mindestens ein (Formel) ist, nur endlich viele Nullstellen haben. Also
215 sind (Formel) linear unabhängig. Satz: (Formel) Beweis:
216 Angenommen, für (Formel) sei (Formel). Dann ist (Formel) für alle (Formel) und
217 damit (Formel) für alle (Formel). Für alle (Formel) mit (Formel) ist dann (Formel). Da
218 (Formel) und A kompakt ist, gibt es ein (Formel), so daß (Formel). Für (Formel)
219 definiere: (Formel). Dann ist (Formel) und es gilt: (Formel); analog (Formel),
220 also F (math.Op.) P und damit (Formel). Satz: Für alle (Formel)
221 ist (Formel) abgeschlossen und konvex. Beweis: Für (Formel) ist
222 die Behauptung richtig; also (Formel). " abgeschlossen ": Sei (Formel)
223 Cauchyfolge mit (Formel) und (Formel). (W ist abgeschlossen in V, V als
224 endlich dimensionaler U nterraum abgeschlossen in dem Banachraum
225 (Formel), also existiert das Grenzelement P). Dann konvergieren (Formel)
226 und (Formel) gegen (Formel) und (Formel) im Sinne der Tschebyscheff-Norm von
227 (Formel). Die Relationen (Formel) und (Formel) bleiben daher beim Grenzübergang
228 erhalten, und es gilt also (Formel) und (Formel), d. h. (Formel).
229 " konvex ": Seien (Formel) und (Formel). Dann gilt mit (Formel), (Formel) auch (Formel)
230 und (Formel), d. h. (Formel).: Sei (Formel) und (Formel). Dann
231 ist (Formel) abgeschlossen, konvex und nicht leer. Bemerkung:
232 Hierbei kann der mengenwertige Operator T im Sinne einer durch
233 eine beliebige (Formel)-Norm induzierten Intervallfunktionennorm
234 (gemäß Kapitel 1) aufgefaßt werden. Beweis: Nach
235 Satz ist (Formel) abgeschlossen konvexe Teilmenge des normierten
236 Raumes (Formel); da W endlich dimensional ist, ist (Formel) also auch
237 schwach lokal kompakt. Damit ist Köthe Satz (1), S.
238 347, anwendbar, der die Existenz mindestens eines Lotpunktes
239 sichert, d. h. (Formel); aus dem Beweis des zitierten Satzes
240 folgt ferner die Konvexität und Abgeschlossenheit der Lotpunkte.
241 Bei der Approximation reellwertiger Funktionen durch Polynome
242 besagt der Approximationssatz von Weierstraß, daß man jede
243 stetige Funktion f beliebig genau durch Polynome approximieren kann,
244 wenn man nur den Grad der Polynome hinreichend groß wählt.
245 Entsprechend stellt sich bei der Approximation durch
246 Intervallpolynome die Frage, unter welchen Bedingungen man eine
247 beliebige Intervallfunktion durch verallgemeinerte
248 Intervallpolynome beliebig genau approximieren kann. Genauer
249 formuliert: Sei (Formel) eine Folge von linear unabhängigen
250 Funktionensystemen, (Formel) die Menge der von (Formel) erzeugten
251 Intervallpolynome. Für alle (Formel) gelte ferner: (Formel) d. h.
252 die (Formel) sind inklusiv geordnet. Daraus braucht nicht zu folgen,
253 daß (Formel), wegen (Formel) gilt jedoch (Formel) für alle (Formel). Die
254 aufgeworfene Frage lautet nun: Wann gilt für alle
255 Intervallfunktionen (Formel), daß (Formel)? Von besonderem Interesse ist
256 auch die speziellere Fragestellung: Wann gilt obige Relation
257 für alle Punktfunktionen (Formel)? Vorausgesetzt sei im weiteren,
258 daß für alle (Formel), bzw. (Formel) stets (Formel), bzw. (Formel). Da alle
259 (Formel) Normen äquivalent sind, und damit auch die
260 Intervallfunktionennormen, ist es gleich, welche für die
261 folgenden Betrachtungen zugrunde gelegt wird. Speziell sei hier
262 (Formel) gewählt.
Zum Anfang dieser Seite