Teubner Studienbucher Mathematik Bohmer: Spllne-Funktionen Theorie und Anwendungen. 340 Seiten. OM 24,80 Clegg: Varlallonsrechnung 138 Seiten. OM 16,80 Collatz: Dlfferentialglelchungen Eine Einfiihrung unter besonderer Beriicksichtigung der Anwendungen. 5. Aufl. 226 Seiten. OM 21,80 (LAMM) CollatzlKrabs: Approxlmationstheorle Tschebyscheffsche Approximation mit Anwendungen. 208 Seiten. OM 26,80 Constantinescu: Dlstrlbutionen und Ihre Anwendung In der Physik 144 Seiten. OM 17,80 Fischer/Sacher: Elnlllhrung In die Algebra 238 Seiten. OM 15,80 Grigorieff: Numerlk gewCShnllcher Dlfferentialglelchungen Band 1: Einschrittverfahren. 202 Seiten. 14,80 OM Band 2: Mehrschrittverfahren Hainzl: Mathematik Ilir Naturwlssenschaltler 311 Seiten. OM 29,- (LAMM) Hilbert: Grundlagen der Geometrle 11. Aufl. VII, 271 Seiten. OM 19,80 Jaeger/Wenke: Llneare Wlrtschaltsalgebra Eine Einfiihrung Band 1: XVI, 174 Seiten. OM 18,80 (LAMM) Band 2: IV, 160 Seiten. OM 18,80 (LAMM) Kochendorffer: Determlnanten und Matrlzen IV, 148 Seiten. OM 16,80 Krabs: Opllmlerung und Approximation 208 Seiten. OM 24,80 Stiefel: Elnlllhrung In die numerische Mathematik Eine Oarstellung unter Betonung des algorithmischen Standpunktes 4. Aufl. 257 Seiten. OM 21,80 (LAMM) StummeJ/Hainer: Praktische Mathematik 299 Seiten. OM 26,80 Topsee: Inlormationstheorle Eine Einfiihn'''~ PQ "-,,~- .... ~.A 1 t fin We'- ,,0 ... oJ. Mathemallsche Stallsllk ,e Einfiihrung in Tt>-- 1 Mett>nrlp" l. Auf;. 223 Sp"· Optimierung und Approximation Von Dr. rer. nat. Werner Krabs Professor an der Techn. Hochschule Darmstadt 1975. Mif 14 Abbildungen, 43 Aufgaben und zahlreichen Beispielen Springer Fachmedien Wiesbaden GmbH Prof. Dr. rer. nat. Werner Krabs Geboren 1934 in Hamburg-Altona. 1954 bis 1959 Studium an der Universitat Hamburg, AbschluB als Diplom-Mathe matiker. 1963 Promotion an der Universitat Hamburg. 1967(68 Visiting Assistant Professor an der University of Washington in Seattle. 1968 Habilitation. Seit 1970 Wissen schaftlicher Rat und Professor an der Technischen Hoch schule Aachen. 1971 Visiting Associate Professor an der Michigan State University in East Lansing. Seit 1972 Pro fessor an der TH Darmstadt. OP-Kurztitelaufnahme der Deutschen Bibliothek Krabs, Werner Optimierung und Approximation_ (Teubner-Studienbiicherl ISBN 978-3-519-02055-4 ISBN 978-3-322-94887-8 (eBook) DOI 10.1007/978-3-322-94887-8 Das Werk ist urheberrechtlich geschJtzt. Die dadurch begriindeten Rechte, besonders die der tibersetzung, des Nachdrucks, der Bildent nahme, der Funksendung, der Wiedergabe auf photomechanischem oder iihnlichem Wege, der Speicherung und Auswertung in Daten verarbeitungsanlagen, bleiben, auch bei Verwertung von Teilen des Werkes, dem Verlag vorbehalten. Bei gewerblichen Zwecken dienender VervielnUtigung ist an den Verlag gemiiJb § 54 UrhG eine Vergiitung zu zahlen, deren Hohe mit dem Verlag zu vereinbaren ist. © Springer Fachmedien Wiesbaden 1975 Urspriinglich erschienen bei B. G. Teubner, Stuttgart 1975 Satz: G. Hartmann, Nauheim Umschlaggestaltung: W. Koch, Sindelfingen Vorwort Dieses Buch ist dem lusammenhang zwischen Optimierung und Approximation gewid met. Es ist aus Vorlesungen hervorgegangen, die ich in den Jahren 1971 bis 1973 in Aachen und Darmstadt gehalten habe. Die Approximationstheorie hat sich zunachst als selbstandige Disziplin entwickelt, und auch der Optimierungstheorie lagen zu Beginn andere lielsetzungen als die Anwendung auf Approximationsprobleme zugrunde. Eine so1che Anwendung liegt aber sehr nahe, da man jedes Approximationsproblem auch als eine Optimierungsaufgabe auffassen kann. Bei der SUbsumption der Approximation unter das allgemeinere Konzept der Optimierung gehen zweifellos speziellere Eigenschaften des Approximationsproblerns verloren, so daB man nicht hoffen kann, alle approximationstheoretischen Fragen auf dem Wege tiber die Optimierung zu beantworten. Bei der Frage nach der Charakterisierung bester Approximierender und nach der Berech nung oder Abschatzung der Minimalabweichung hat sich jedoch der Einsatz der Opti mierungstheorie als sehr fruchtbar erwiesen. Auch bei der Frage nach der Existenz bester Approximierender liefert sie wertvolle Anhaltspunkte, weniger jedoch bei der Eindeu tigkeit, die in der Optimierung eine untergeordnete Rolle spielt. Nicht zuletzt lassen sich auch die mannigfachen Methoden zur Uisung von Optimierungsproblemen mit Gewinn auf Approximationsaufgaben anwenden, worauf allerdings in diesem Buch nicht einge gangen wird. Seine lielsetzung besteht vie1mehr darin zu zeigen, wie sich zahlreiche verschiedenartige Approximationsprobleme, die sich zum Teil aus direkten physikalisch-technischen Anwendungen und zum Teil aus anderen Fragestellungen der angewandten Mathematik ergeben, im Rahmen der Optimierungstheorie einheitlich behandeln lassen. Es besteht aus drei Kapiteln tiber lineare, konvexe und allgemein nichtlineare Probleme und einem Anhangskapitel, in dem funktionalanalytische Hilfsmittel bereitgestellt werden. Jedes der ersten drei Kapitel beginnt mit einer Reihe von Beispielen, auf die nach Entwicklung der entsprechenden theoretischen Grundlagen gr6~tenteils wieder eingegangen wird, urn auf diese Weise auch einen Eindruck von der Reichweite der Theorie zu vermitteln_ Die hier gewahlte induktive Darstellung hat zwar den Nachteil einer gewissen Redun danz, hat aber andererseits den Vorteil, daB jedes der drei Kapitel tiber Optimierungs probleme in sich geschlossen ist und unabhangig von den anderen beiden gelesen werden kann und daB die fur die jeweilige Problemklasse spezifische Struktur gleich zu Beginn deutlich hervortritt und nicht erst aus der nachst allgemeineren Klasse hergeleitet wer den mu~. 1m tibrigen wurden nichtlineare Probleme nicht in der allgemeinen Form vor gestellt, aus der man die zuvor behandelten konvexen Probleme herleiten kann, son dern von vornherein in einer Gestalt, die auf die Anwendung auf Approximationspro bleme zugeschnitten ist. lur Vertiefung des Stoffes wurden immer wieder Aufgaben eingestreut, und kleinere Beweislticken wurden dem Leser oft als Vbung tiberlassen. 4 Vorwort Aus der Fiille der inzwischen auch bei infiniten Optimierungsproblemen vorhandenen Literatur konnte nur eine Auswahl angesprochen werden, die im Literaturverzeichnis zusammengestellt ist und auf die im Text durch die Verfassernamen mit den letzten beiden Ziffern des Erscheinungsjahres in eckigen Klammern verwiesen wird. Zitate, die einen unrnittelbaren Bezug zum dargestellten Stoffhaben, wurden meistens direkt in den Text eingefligt und solche von erganzendem Charakter in gesonderten Abschnitten mit bibliographischen Bemerkungen zusammengestellt. Es gibt zur Zeit bereits mehrere BUcher Uber infinite Optimierung, die teilweise auch Anwendungen auf die Approximationstheorie enthalten, z.B. das von P s c hen i . t s c h n y [72] und L u e n b erg e r [69]. Die beiden BUcher von Hoi m e s [72] und La u r en t [72] sind sogar ausdrucklich dem Zusammenhang der beiden Gebiete gewidmet. 1m deutschsprachigen Bereich gibt es aber zur Zeit kein Buch mit ahnlicher Intention. Das vorliegende Buch versucht, diese LUcke zu schlieBen und dabei besonders die mannigfachen Anwendungen zu betonen. Da es sich primar mit infiniten Optimie rungsproblemen befaBt, ist der Einsatz von Hilfsmitteln aus der Funktionalanalysis unvermeidlich. 1m Zentrum stehen dabei die Trennungssatze flir konvexe Mengen. Diese Hilfsmittel werden zwar in einem Anhangskapitel zusammengestellt, zum Tei! aber ohne Beweise. Eine gewisse Vertrautheit mit den Grundlagen der Funktionalanalysis normier ter Vektorraume ist daher flir die LektUre der theoretischen Teile dieses Buches not wendig. Die Herren Dr. K. Glashoff und E. Sachs haben das Manuskript kritisch durchgesehen, mir zahlreiche Verbesserungsvorschlage gemacht und mich auch zusammen mit den Herren D. Arndt, Prof. Dr. F. Lempio und Prof. Dr. E. Boh! beim Lesen der Korrektu ren unterstlitzt. Ihnen allen geblihrt me in herzlicher Dank eben so wie Frau G _ Oelschla gel, die das Manuskript geschrieben und mir bei allen redaktionellen Arbeiten tatkraftig geholfen hat. Dem Teubner-Verlag danke ich flir seine Bereitschaft, dieses Buch in seine Serie der StudienbUcher aufzunehmen, und flir die sehr gute Ausstattung. w. Darmstadt, im Frlihjahr 1975 Krabs Inhalt Lineare Probleme Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9 1.1 Dber den Zusammenhang zwischen Approximation und Optimierung ... 9 1.2 Ein Kontroll-Approximationsproblem bei der Aufheizung von Metallen .. 11 1.3 Semi-infinite Optimierung bei der Kontrolle der Luftverschmutzung 13 1.4 Ausblick auf konvexe und allgemein nichtlineare Probleme. . . . . . . . . .. 14 2 Einige Beispiele linearer Approximations-und Optimierungsprobleme 15 2.1 GleichmaEige Approximation von Funktionen. . . . . . . . . . . . . . . . . .. 15 2.1.1 Der allgemeine Fall, 2.1.2 Approximation mit Interpolations nebenbedingungen, 2.1.3 Der diskrete Fall 2.2 GleichmaBige Approximation bei der Anfangs-Randwertaufgabe (ARWA) der Warmeleitung ..................................... 17 2.3 Ein lineares Optimierungsproblem bei der Lasung einer Randwertaufgabe fUr die Potentialgleichung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19 2.4 Lineare Randwertaufgaben und gleichmaBige Approximation. . . . . . . .. 21 2.4.1 Der allgemeine Fall, 2.4.2 Aufgaben von monotoner Art und einseitige Approximation 2.5 Ein lineares Kontroll-Approximationsproblem . . . . . . . . . . . . . . . . . .. 23 3 Das allgemeine line are Optimierungsproblem. . . . . . . . . . . . . . . . . . . . . .. 24 3.1 Problemstellung, ein schwacher Dualitatssatz und einfache Folgerungen .. 24 3.2 Der semi-inifinite Fall. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 26 3.3 Semi-infinite Probleme in Funktionenraumen . . . . . . . . . . . . . . . . . .. 27 3.3.1 Anwendung auf eine Randwertaufgabe fUr die Potentialgleichung, 3.3.2 Anwendung auf eine line are Randwertaufgabe von monotoner Art. 3.4 Gegenbeispiele gegen die Giiltigkeit allgemeiner Existenz-und Dualitats- aussagen ........................................... 34 3.4.1 Unlosbarkeit eines semi-infiniten Problems, 3.4.2 Auftreten einer Dualitatsliicke 3.5 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 38 4 Existenz-und Dualitatssatze ................................. 38 4.1 DoppeJte Dualisierung eines Optimierungsproblems . . . . . . . . . . . . . .. 38 4.2 Subzulassigkeit und Normalitat eines Optimierungsproblems . . . . . . . .. 40 4.3 Allgemeine Existenz-und Dualitatssatze ..................... " 43 4.4 Existenzaussagen fUr das duale Problem ..................... " 46 4.4.1 Dualisierung des Existenzsatzes in Abschn. 4.3, 4.4.2 Anwendung auf das semi-infinite Problem, 4.4.3 Ein direkter Existenzsatz fUr das duale Problem 4.5 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 50 6 Inhalt 5 Anwendungen........................................... 53 5.1 Semi-infinite Probleme in Funktionenraumen . . . . . . . . . . . . . . . . . .. 53 5.2 Gleichma~ige Approximation von Funktionen. . . . . . . . . . . . . . . . . .. 55 5.3 Einseitige gleichma~ige Approximation . . . . . . . . . . . . . . . . . . . . . .. 62 5.4 Anwendung auf eine Randwertaufgabe flir die Potentialgleichun~ .... " 66 5.5 Ein Kontroll-Approximationsproblem in der Warmeleitung ......... 68 II Konvexe Probleme Einige Beispiele konvexer Approximations-und Optimierungsprobleme . . . .. 75 1.1 Das allgemeine lineare Approximationsproblem ................. 75 1.2 Optimale Fehlerabschatzungen bei linearen Operatorgleichungen. . . . . .. 77 1.2.1 Defektabschatzungen, 1.2.2 Operatorabschatzungen 1.3 Ein Problem der optimalen Steuerung. . . . . . . . . . . . . . . . . . . . . . . .. 84 2 Konvexe Funktionen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 85 2.1 Konvexe Funktionale .................................. , 85 2.2 Konvexe Abbildungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 88 2.3 Existenzaussagen flir line are Kontrollprobleme. . . . . . . . . . . . . . . . . .. 91 3 Das allgemeine konvexe Optimierungsproblem: Existenz-und Dualitatsaus- sagen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 93 3.1 Problemstellung, Existenzaussagen und Subzulassigkeit . . . . . . . . . . . .. 93 3.2 Das duale Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 96 3.3 Allgemeine Existenz-und Dualitatssatze . . . . . . . . . . . . . . . . . . . . . .. 98 3.4 Der lineare Fall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 102 3.5 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 103 4 Min-Sup-, Max-Inf- und Sattelpunktaussagen ....................... 104 4.1 Das Optimierungsproblem als Min-Sup-Problem ................. 104 4.2 Das duale Problem als Max-Inf-Problem . . . . . . . . . . . . . . . . . . . . . .. 106 4.3 Die Aquivalenz der Min-Sup=Max-Inf-Aussage mit einer Sattelpunkt- aussage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 107 4.4 Das verallgemeinerte Theorem von Kuhn-Tucker. . . . . . . . . . . . . . . .. 108 4.5 Existenzaussagen flir das duale Problem . . . . . . . . . . . . . . . . . . . . . .. 110 4.6 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 111 5 Anwendung auf Approximationsprobleme. . . . . . . . . . . . . . . . . . . . . . . .. 112 5.1 Existenzaussagen bei konvexen Approximationsproblemen in normierten Vektorraumen ....................................... 112 5.2 Gleichma~ige Approximation von Funktionen ................... 113 5.2.1 Der allgemeine konvexe Fall, 5.2.2 Der allgemeine line are Fall 5.3 Ein Approximationsproblem mit einer gemischten Norm ........... 117 5.4 Berechnung der Minimalabweichung bei einem konvexen Approximations- problem ........................................... 119 Inhalt 7 6 Konvexe Optimierungsprobleme in Funktionenriiumen ............... 122 6.1 Problemstellung und Charakterisierung der Optimalitiit . . . . . . . . . . . .. 122 6.2 Ein gemischt linear-konvexes Problem ....................... 126 6.3 Anwendungen ........................................ 130 6.3.1 GleichmiiBige lineare Approximation mit Interpolation, 6.3.2 Ein semi-infinites Problem bei der Kontrolle der Luftverschmutzung III Nichtlineare Probleme Einige Beispiele nichtlinearer Approximations-und Optimierungsprobleme. .. 136 1.1 Nichtlineare Approximation in normierten Vektorriiumen . . . . . . . . . .. 136 1.1.1 Allgemeine Bemerkungen, 1.1.2 GleichmiiBige Approximation von Funktionen, 1.1.3 Allgemeine rationale Approximation 1.2 Ein-und zweiseitige Approximation bei nichtlinearen Randwertaufgaben. 138 1.2.1 Der allgemeine Fall, 1.2.2 Ein Beispiel 1.3 Defektabschiitzungen bei nichtlinearen Randwertaufgaben. . . . . . . . . .. 142 2 Minimierung konvexer Funktionale auf beliebigen Mengen ............. 146 2.1 Tangentialkegel in normierten Vektorriiumen ................... 146 2.2 Notwendige Bedingungen flir Minimalpunkte konvexer Funktionale auf beJiebigen Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 148 2.2.1 Ein allgemeiner Satz, 2.2.2 Anwendung auf Approximation in normierten Riiumen, 2.2.3 Anwendung auf gleichmiiBige Approximation von Funktionen, 2.2.4 Anwendung auf L -Approximation J 2.3 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 156 3 Nichtlineare Optimierung mit unendlich vielen Nebenbedingungen. . . . . . . .. 157 3.1 Notwendige Bedingungen flir Minimalpunkte ................... 157 3.1.1 Der allgemeine Fall, 3.1.2 Der differenzierbare Fall 3.2 Hinreichende Bedingungen flir Minimalpunkte .. ' ................. 163 3.3 Anwendung auf nichtlineare gleichmiiBige Approximation. . . . . . . . . .. 165 3.4 Semi-infinite nichtlineare Optimierung ....................... 169 3.5 Bibliographische Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 172 IV Anhang: Hilfsmittel Konvexe Kegel und lineare Abbildungen ......................... 174 1.1 Konvexe Kegel und Halbordnungen ......................... 174 1.2 Der (topologische) Dualraum ............................. 176 1.3 Lineare Abbildungen ................................... 179 2 Eigenschaften konvexer Kegel und Darstellung positiver Linearformen ..... 181 2.1 Abgeschlossenheit konvexer Kegel. . . . . . . . . . . . . . . . . . . . . . . . . .. 181 2.2 Adjungierte Kegel ..................................... 182 2.3 Darstellung positiver Linearformen auf Vektorriiumen stetiger Funktionen 184 2.4 Darstellung stetiger Linearformen auf Vektorriiumen stetiger Funktionen. 187 8 Inhalt 3 Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 190 3.1 Algebraische und topo!ogische Eigenschaften ................... 190 3.2 Trennungssatze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 193 3.3 Schwache Konvergenz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 193 Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 196 Sachverzeichnis ........................................... 204 I Lineare Probleme 1 Einleitung l.1 Uber den Zusammenhang zwischen Approximation und Optimierung Die Entwicklung der Optimierungstheorie wurde zunachst vorwiegend aus der Sicht okonomischer Problemstellungen und im Zusarnmenhang mit der Spieltheorie voran getrieben, durch die ebenfalls wirtschaftliches und strategisch vernlinftiges Verhal ten mathematisch beschrieben werden sollte. Gleichzeitig wurde aber auch die schon recht weit entwickelte Approximationstheorie durch das Aufkommen der elektronischen Rechenanlagen neu belebt, indem Algorith men zur Losung von Approximationsaufgaben entwickelt werden konnten, die zuvor wegen des zu groBen Rechenaufwandes nicht praktikabel gewesen waren. Der Zusarnmenhang zwischen den beiden Disziplinen wurde zunachst bei den sog. dis k ret e n lin ear e nAp pro x i mat ion s pro b Ie men erkannt, bei denen es sich darum handelt, eine vorgegebene reellwertige Funktion f fur endlich viele Argumente tl, ... , tm aus einer Menge M (etwa den reellen Zahlen) durch Funktionen v einfacherer Bauart (z.B. durch Polynome oder trigonometrische Summen) anzuna hem. Oft sind die vorgegebenen Funktionswerte fj = f( tJ, i = 1, ... , m, irgendwelche MeBwerte, so daB f als Funktion auf M gar nicht explizit als algebraischer oder analy tischer Ausdruck bekannt ist. Flir die Funktionen v gibt man sich im Falilinearer Approximationsprobleme einen endlich-dimensionalen Funktionenraum V vor, beste hend aus allen Linearkombinationen o v(t) = L XjVj(t), tEM (1.1) j= I mit reellen Koeffizienten XI> ... ,Xo und Funktionen vI, ... , vo, deren Werte sich leicht berechnen lassen. Urn die Abweichung der Funktionen v aus V von f in den Punk ten tl, ... , tm EM zu messen, wird man jede Funktion mit dem m-Vektor ihrer Werte in den Punkten tj (die man fest durchnumeriert) identifizieren und im Vektorraum Rm aller reellen m-Tupel eine geeignete Norm II . II zugrundelegen. Dann stellt sich das Pro blem, ein v E V derart zu wahlen, daB die Abweichung IIv - fll moglichst klein ausfallt. 1m Faile der euklidischen Norm im Rm handelt es sich dabei urn die klassische Aufgabe der Au s g lei c h s r e c h nun g, die sich durch Auflosung eines einzigen linearen Gleichungssystems (der sog. Normalgleichungen) in geschlossener Form Ibsen laBt. Legt man in RID die Maximum-Norm zugrunde, so liegt ein Problem der sog. dis k r e - ten lin ear e n T s c h e b y s c h e f f -A P pro x i mat ion vor, das sich in ein Problem der g e w 0 h n I i c hen lin ear e nap tim i e run g liberftihren laBt (vgl. dazu Abschn. 2.1.3).