Bücher der Reihe International Numerical Mathematics

Das Mathematische Forschungsinstitut Oberwolfach veranstaltet seit längerer Zeit in etwa zweijährigem Turnus Tagungen über numerische Methoden der Approximationstheorie. Die Vortragsauszüge der diesjährigen Tagung, die vom 13. bis 19. Juni stattfand, sind in dem vorliegenden Band zusammengefaßt. Die Themen lassen erkennen, daß es ein besonderes Anliegen der Tagungsleiter war, die Kluft zwischen abstrakter Mathematik und den Anwendungen verringern zu helfen. Approximationstheoretische Fragestellungen scheinen geeignet zu sein, hier neue Brü~ken zu schlagen. Der starke Zustrom ausländischer Mathe­ matiker, insbesondere aus Übersee, zeigt, daß diese Bestrebungen auch in an­ deren Ländern Resonanz finden. In zunehmendem Maße sind solche aus den (außer-und innermathematischen) Anwendungen herrührenden Fragestellungen zu behandeln, die sich nicht in klassische Approximationstheorie einordnen lassen. So wurde z. B. von Ver­ tretern der Nachrichtentechnik über in ihrem Bereich auftretende ungewöhnliche Approximationsprobleme berichtet. Andere Vorträge beschäftigten sich mit Approximationsfragen, die aus gewissen Aufgaben der angewandten Mathematik erwachsen (z. B. Behandlung von Differential-und Integralgleichungen). Zwei weitere Schwerpunkte bildeten die Beziehungen zur Optimierungstheorie, die insbesondere zu effektiven numerischen Verfahren führen, sowie Untersuchun­ gen über Spline-Approximationen. Professor Steckin aus Moskau war leider an der Teilnahme verhindert und hat statt dessen das hier abgedruckte Manuskript übersandt.

Im Oktober 1960 veranstaltete das Rheinisch-Westfälische Institut für Instrumen­ telle Mathematik gemeinsam mit dem Institut für Angewandte Mathematik der Universität Bonn ein Colloquium über die Theorie der Schaltkreise (combinational circuits) und Schaltwerke (sequential circuits). Mit dieser Publikation werden Auszüge und teilweise überarbeitete Vorträge vorgelegt. Im Gegensatz zum Ausland (insbesondere den U.S.A.) hat dieses junge Teil­ gebiet der Angewandten Mathematik in Deutschland bisher verhältnismässig wenig Aufmerksamkeit gefunden, wenn man die Zahl der deutschsprachigen Veröffentlichungen als Maßstab heranzieht. Dies ist um so bedauerlicher, da sich hier für den Mathematiker ein reizvolles Betätigungsfeld bietet, das nicht arm an ungelösten Problemen ist. Wegen dieser Situation in Deutschland wurde in Bonn der Versuch gemacht, Kontakte zu knüpfen und die Grundideen dieses Gebietes an einen grösseren Interessentenkreis heranzutragen. Diesem Ziel dient insbesondere auch die Ver­ öffentlichung der Vorträge. Die Zusammensetzung der einzelnen Beiträge ist naturgemäss heterogen. Neben bereits bekannten Resultaten (teilweise in anderer Darstellung) findet man auch neuere Ergebnisse, die ausserdem in ausführlicher Fassung in einschlägigen Zeitschriften erscheinen werden. Es ist beabsichtigt, weitere Colloquien dieser Art (in etwa jährlichem Abstand) abzuhalten und die Beiträge geschlossen zu veröffentlichen.

The "International Workshop on Multivariate Approximation and Interpolation" was held at the University of Duisburg, Germany, during August 14-18, 1989. It was the second workshop in aseries which started in 1986 at the University of Chile in Santiago with a previous conference on a similar subject (cf. Topics in Multivariate Approximation, C.K. Chui et al. (Eds.), Academic Press, New York, 1987). The conference was organized by an international organizing committee consisting of Charles Chui (USA), Werner Haußmann (Germany), Kurt Jetter (Germany), Larry Schumaker (USA), and Florencio Utreras (Chile). In addition, the local organizing committee included Hans-Bernd Knoop, Hauke Krüger, and Joachim Stöckler from the University of Duisburg. We would like to thank all of them for their constant support. We also acknowledge the efforts of Uta Dick, Sabine Häußler, and Stefanie Messal who did most of the secretarial work. It was our pleasure to see that the workshop brought together 75 participants from 18 countries. 28 leading scientists gave invited (research or survey) lectures, with 24 of them summarized in the papers included in this proceedings volume. The topics of these lectures gave a state-of-the-art overview of current research in Multivariate Approximation and Interpolation, and they reflected the rapid development of the area.

W. Höhn Ober die numerische Behandlung von Variationsproblemen mit natür­ lichen Randbedingungen in zwei Dimensionen. . . . . . . . 131 C. Johnson: On finite element methods for curved shells using Hat elements 147 F. Locher: Numerische Lösung linearer Differentialgleichungen mit Hilfe von Cebysev-Entwicklung . . . . . . . . . . . 155 K.

untersuchen wir vier Problemkreise: Partielle Differentialglei­ chungen, Parameteroptimierung, Funktionaloptimierung (optimale Steuerungen) und stochastische Vorgänge.

Der Band enthalt Manuskripte zu Vortragen, die auf einer von den Herausgebern geleiteten Tagung tiber Numerische Methoden der Approximationstheorie am Mathematischen Forschungsinstitut Ober wolfach in der Zeit vom 18. -24. Januar 1981 gehalten wurden. Das Spektrum der Vortrage reichte von der klassischen Approximations theorie tiber mehrdimensionale Approximationsverfahren bis hin zu praxisbezogenen Fragestellungen. Zu den zuerst genannten Gebieten gehorten z. B. die Verfeinerung von Fehlerabschatzungen bei der Polynominterpolation, Fragen zur Eindeutigkeit, Charakterisierung optimaler Interpolationsprozesse und Algorithmen zur rationalen Interpolation. Bei den weiteren genannten Gebieten spiegel ten zahlreiche Vortrage das steigende Interesse an der mehrdimensio nalen Interpolation, insbesondere mit verschiedenen Arten von Splines wider. Hier standen u. a. Probleme der Parameterschatzung in der Medizin und Flugtechnik, Fragen der Approximationstheorie bei der Konstruktion von Plottern und stabile Algorithmen beim Arbeiten mit mehrdimensionalen B-Splines im Mittelpunkt des Interesses. Die Tagung lieferte einen reprasentativen Ueberblick tiber die aktuellen Trends in der Approximationstheorie. Zum guten Erfolg der Tagung trug wie immer die hervorragende Be treuung durch die Mitarbeiter und Angestellten des Instituts so-' wie das verstandnisvolle Entgegenkommen des Institutsdirektors, Herrn Professor Dr. Barner, bei. Un serer besonderer Dank gilt dem Birkhauser Verlag ftir die wie stets sehr gute Ausstattung. Helmut Werner Lothar Collatz Gtinther Meinardus Hamburg Mannheim Bonn 7 INDEX Blatt, H. -P. Strenge Eindeutigkeitskonstanten und Fehlerabschatzungen bei linearer Tschebyscheff-Approximation 9 Bohmer, K. Polynom- und Spline-Interpolation (Ein Farbfilm) 26 Brannigan, M. A Multivariate Adaptive Data Fitting Algorithm 30 Brass, H. Zur numerischen Berechnung konjugierter Funktionen 43 Bultheel, A.

Am Mathematischen Forschungsinstitut Oberwolfach fand in der Zeit vom 14. bis 20. November 1971 eine Tagung über unter der Leitung der Unterzeichneten statt. Seit der vorangegangenen Tagung im Sommer 1967 ist es gelungen, weitere Problem klassen der numerischen Behandlung zugänglich zu machen. Trotzdem sind nach wie vor viele Fragen offen. In dem vielseitigen Vortragsprogramm wurde vor allem über Methoden bei verschiedenen Aufgabentypen (Transportprobleme, gemischt ganzzahlige Probleme, stochastische Optimierungsaufgaben, Kontrollprobleme usw.) bt!­ richtet. Besondere Beachtung fanden die Vorträge über Dualität und deren Bedeu­ tung für Existenz- und Stetigkeitsaussagen und für die numerische Einschlies­ sung des Optimal wertes. In einer Diskussionsstunde hatten die Tagungsteilnehmer Gelegenheit, auf offene Probleme hinzuweisen und Anregungen zu geben. Die wichtigsten Dis­ kussionspunkte waren: 1. Viele der bekannten Methoden für Optimierungsaufgaben, die ja häufig nicht von Numerikern entwickelt worden sind, mussten genauer als bisher auf ihre numerische Brauchbarkeit überprüft und evtl. verbessert werden. 2. Bei iterativen Verfahren ist häufig das Aufsuchen einer Ausgangsnäherung viel mühsamer als das Verfahren selbst. Bei der Entwicklung von nume­ rischen Methoden sollte man das beachten. 3. Für ganzzahlige Optimierungsaufgaben sind einige neue (asymptotische) Methoden bekanntgeworden. Trotzdem bleibt die typische Schwierigkeit, dass der Rechenaufwand nicht durch eine nur von der Dimension des Pro­ blems abhängende Schranke begrenzt ist.

Dieser Band bringt Manuskripte zu Vorträgen einer Tagung, die in Oberwolfach vom 3. 6. bis 9. 6. 1973 unter Leitung der Unterzeichner veranstaltet wurde. Die letzte Tagung über numerische Probleme der Approximationstheorie in Oberwolfach fand 1971 statt. Daher hatte die jetzige Veranstaltung das Ziel, den in der Zwischenzeit erreichten Fortschritt auf diesem Gebiet durch ausgewählte V orträge erkennen zu lassen. Die große Zahl der Vorträge sowie die Fülle der behandelten Themen zeigte die wachsende Bedeutung, die diesem Gebiet auch in der Zukunft für die Anwendungen zukommt und macht deutlich, daß Tagungen dieser Art künftig in kürzeren Zeitabständen stattfinden sollten. Hervorzuheben ist, daß neben approximationstheoretischen Vorträgen und solchen aus der Optimierung auch neue Fragestellungen aus der Praxis (vgl. etwa die Vorträge der Herren Kubik und Gutknecht) vorgetragen wurden, die z. T. noch einer exakten mathematischen Form bedürfen. Hieraus können sich fruchtbare Impulse sowohl für theoretische Untersuchungen als auch für die eng mit der Praxis verbundene wissenschaftliche Tätigkeit ergeben. Die 49 Teilnehmer, darunter aus Rumänien, Großbritannien, den USA, der Schweiz, den Niederlanden, Frankreich, Bulgarien, Kanada, Ungarn und Bel­ gien, konnten durch den regen Gedankenaustausch viele Anregungen für ihre wissenschaftliche Arbeit gewinnen. Unser besonderer Dank gilt dem Birkhäuser Verlag für die gute Ausstattung dieses Bandes und dem Leiter des Mathematischen Forschungsinstitutes Ober­ wolfach, Herrn Prof. Dr. M. Barner, und seinen Mitarbeitern, Frau Dipl.-Math.

Der vorliegende Band gibt hauptsächlich Vorträge wieder, die in der Zeit vom 23. bis 27. Februar 1976 auf einem am Mathematischen Forschungsinstitut Oberwolfach abgehaltenen Kolloquium über «Optimierung bei graphentheo­ retischen und ganzzahligen Problemen» gehalten wurden. Die Tagung war einem aktuellen und in neuerer Zeit in der Literatur viel behandelten Teilge­ biet der Optimierung gewidmet. Die graphen theoretischen und ganzzahligen Optimierungsprobleme sind, wie auch aus den 19 Vorträgen hervorging, für viele Anwendungen in Wirtschaft und Technik von Bedeutung, geben aber auch Anlass zu interessanten theoretischen Untersuchungen. Auch über Fortschritte auf dem Gebiet der numerischen Methoden konnte berichtet werden, vor allem im Zusammenhang mit der Komplexität von Algorithmen. So hoffen die Unterzeichner, dass die Tagung dazu beigetragen hat, den Kontakt zwischen mathematischer Theorie und Anwendungsgebieten wieder etwas stärker zu beleben. Die 42 Teilnehmer aus dem In-und Ausland, darunter eine grössere Gruppe aus den Niederlanden und einige eigens zu dieser Tagung aus Amerika angereiste Kollegen, haben in Vorträgen und Diskussionen viele wertvolle Informationen austauschen können. Der Institutsleitung gebührt für diese Gelegenheit der wissenschaftlichen Begegnung der Dank aller Teilnehmer. W. WETTERLING L. COLLATZ G. MEINARDUS (Siegen) (Enschede) (Hamburg) Inhaltsverzeichnis R.E. BURKARD - H. HAMACHER - U. ZIMMERMANN: Flussprobleme mit allgemeinen Kosten ........................... 9 L. COLLATZ: Graphen bei Ornamenten und Verzweigungsdiagrammen . . . . . . . . . . 23 . . B. DEJON: Bestimmung von r kürzesten Wegen in Netzwerken unter Nebenbed- gungen: Verfahren vom Hoffman-Pavley-Typ . . . . . . . . . . . . . . . . . 47 . . . . . R. HALIN:Systeme disjunkter unendlicher Wege in Graphen .................. 55 P.L. HAMMER: Pseudo-Boolean remarks on balanced graphs. . . . . . . . . . . . . . . . . . 69 . . . . .

Die Funktionalanalysis hat nunmehr fUr die Numerische Mathematik eine so grosse Bedeutung erlangt, dass es angebracht ist, sie als die grundlegende Diszi­ plin fUr die Numerische Mathematik anzusehen. Sie ermoglicht eine einheitliche Behandlung und Darstellung von Problemen, die in der klassischen Mathematik noch verschiedenen Gebieten angehoren. Es versteht sich von selbst, dass sich dabei die Numerische Mathematik und die Funktionalanalysis wechselseitig befruchtet haben. So war es auch das Ziel zweier Arbeitstagungen, den Zusammenhang der Funk­ tionalanalysis mit der Numerischen Mathematik, insbesondere der Behandlung von Differentialgleichungen und der Approximationstheorie zu verdeutlichen. Das Mathematische Forschungsinstitut in Oberwolfach hat in dankenswerter Weise den Rahmen fUr anregende Diskussionen in personlicher und herzlicher Atmosphare bereitgestellt. Die vorangehenden Tagungen (Juni 1964, Juni 1965, November 1965) hatten ein sehr gutes Echo gefunden. Daher fanden nun zwei weitere Tagungen statt: 20. bis 25. Juni 1966 tiber: Numerische Behandlung von Differentialgleichungen unter der Leitung der Herren COLLATZ und UNGER 13. bis 19. November 1966 tiber: Numerische Analysis, insbesondere Approximationstheorie unter der Leitung der Herren COLLATZ und MEINARDUS Wie schon die Titel der Tagungen andeuten, standen Probleme der Differential­ gleichungen und der Approximationstheorie im Vordergrund. Daneben wurde eine interessante Entwicklung sichtbar, die besonders fUr das numerische Rech­ nen auf elektronischen Rechenanlagen von grosser Wichtigkeit sein wird: die Intervallanalysis, insbesondere das Prinzip der Intervallarithmetik. Die Inter­ vallarithmetik ermoglicht eine Fehlererfassung unter Einschluss aller Rundungs­ fehler.

1m Zeitalter der Raumfahrt erscheint es notwendig, daB neben der 1nforma­ tionstheorie die junge Automatentheorie gepflegt wird. Die 1nformationstheo­ rie mit ihrem wahrscheinlichkeitstheoretischen Hintergrund ermoglicht die fehlerfreie Nachrichtenubertragung zum Raumfahrzeug und zurUck. Die Auto­ matentheorie schlieBlich kann in einem weiteren Stadium der Entwicklung dem Raumfahrzeug ein solches «Eigenleben» und eine solche «kunstliche 1ntel­ ligenz» verleihen, die notwendig sind, um dem Menschen in der Weite des Welt­ alls eine Uberlebenschance zu geben. Die gegenwartige Phase der Raumfahrt hat noch vomehmlich kontinuierlichen Charakter, gekennzeichnet durch bal­ listisch-stetige Bahnen, gelegentlich durch Eingriffe des Menschen modifiziert. Die nachste Phase wird moglicherweise neben groBeren Reaktionsgeschwindig­ keiten auch neuartige Steuerungsablaufe, ein gewisses «Lem»-Vermogen und Verhaltens-Schemata erfordem, die bisher noch unvollkommen erforscht sind. Die Notwendigkeit, Automatentheorie zu betreiben, ergibt sich allerdings nicht nur im Hinblick auf die Raumfahrt. Wir begegnen in unserer Welt auf Schritt und Tritt neuen Erscheinungen, neuen Geraten und neuen Systemen, fur deren Weiterentwicklung die Automatentheorie eine Voraussetzung sein durfte. Auch fur ein vertieftes Verstandnis der Funktionsweise im lebenden Organismus kann die Automatentheorie Arbeitshypothese und brauchbares Hilfsmittel sein.

Der vorliegende Band gibt hauptsächlich Vorträge wieder, die in der Zeit vom 25. bis 27. September 1974 auf einem an der Technischen Universität Claus­ thai abgehaltenen, von den Unterzeichneten geleiteten Kolloquium über «Finite Elemente und Differenzenverfahrem> gehalten wurden. Diese beiden Methoden sind wohl die z. Z. am meisten verwendeten numerischen Näherungsverfahren zur angenäherten Lösung von Anfangs­ und Randwertaufgaben bei gewöhnlichen und partiellen, linearen und nichtli­ nearen Differentialgleichungen. Die im Laufe der letzten 2 bis 2Y2 Jahrzehnte entwickelte Methode der finiten Elemente hat wegen ihrer großen Flexibilität und Anwendbarkeit auch bei sehr komplizierten Aufgaben besonders in den Anwendungsgebieten großen Anklang gefunden, und es werden z. B. bei Problemen der Kontinuumsmechanik auf Computern Probleme mit über 10 000 nichtlinearen Gleichungen numerisch bewältigt. Trotz der außeror­ dentlichen praktischen Erfolge sind erst in neuerer Zeit von mathematischer Seite aus Versuche unternommen worden, eine strenge Fehleranalyse durch­ zuführen; exakte Fehlerschranken für die auf dem Computer berechneten Näherungen lassen sich z. Z. nur für relativ einfache Probleme angeben. Einige der Vorträge berichten über derartige Möglichkeiten, deren weiterer Ausbau als wichtige Aufgabe für künftige mathematische Forschung erscheint, andere Vorträge über Weiterentwicklungen numerischer Methoden, über Konvergenzordnungen und über Vergleiche verschiedener Verfahren miteinander. Das Ziel der Tagung war, dazu beizutragen, die z. Z. auf dem Gebiete der numerischen Behandlung von Differentialgleichungen bestehende Diskrepanz zwischen Theorie und Praxis ein wenig zu verringern.

Im November 1967 fand im Mathematischen Forschungsinstitut Oberwolfach (Schwarzwald) eine weitere Tagung über Funktionalanalysis und Numerische Mathematik statt. Ebenso wie die vorangehenden Tagungen in den Jahren 1964, 1965 und 1966 erfreute sich auch diese Tagung eines guten Echos. Fachleute aus verschiedenen Nationen und aus den verschiedensten Gebieten der Funktionalanalysis und der Numerischen Mathematik und aufstrebende junge Mathematiker vereinte das Institut bei Vorträgen und Diskussionen. Besonders deutlich wurde wieder, dass sowohl tiefere Einsichten in die Rech­ nungsweise der Computer - man denke an die Methoden der Intervallarithme­ tik - als auch die Ausnutzung neuester Ergebnisse der abstrakten Funktional­ analysis für fruchtbare Forschungen in der Numerischen Mathematik unent­ behrlich sind. Dies war auch das Ergebnis einer ausführlichen Diskussion über Stellung und Aufgabe der Numerischen Mathematik. Die hier wiedergegebenen Vorträge aus den Gebieten der Approximations­ theorie, Differentialgleichungen, Intervallarithmetik, Iterationsverfahren und 1 der Optimierungstheorie vermitteln einen Eindruck von der Mannigfaltigkeit der Probleme der Numerischen Mathematik. Die Tagungsleiter danken allen Teilnehmern, die durch ihre Beiträge und ihr Interesse zum Erfolg der Tagung beigetragen haben. Ebenso danken sie dem Leiter des Mathematischen Forschungsinstitutes Oberwolfach, Herrn Prof. Dr. M. Barner, und seinen Mitarbeitern dafür, dass die Tagung aufgrund ihrer Gastfreundschaft und Hilfsbereitschaft den Teilnehmern in angenehmer Erinne­ rung bleiben wird. Schliesslich sei dem Birkhäuser Verlag der besondere Dank für die gute Aus­ stattung dieses Buches und die stete Förderung ausgesprochen.

Quadrature formulae are generally obtained substituting the integral to b b evaluate J f(x) dx with the integral J

. . . . . . .

Die Funktionalanalysis hat in neuerer Zeit immer starkere Bedeutung fUr die Numerische Mathematik erlangt, so daB sie heute schon als eine der grund­ legenden Disziplinen ftir die Numerische Mathematik angesehen werden kann. Es zeigte sich dabei, daB verschiedene Teile der Funktionalanalysis dabei wei­ ter ausgebaut und auf eine fUr die Anwendungen bequeme Form gebracht wer­ den muBten. Es war auch notig, neue Entwicklungen durchzuftihren. So hat die Numerische Mathematik auch zur Befruchtung der Funktionalanalysis und zur EinfUhrung weiterer funktionalanalytischer Begriffe geftihrt. Als ein Beispiel daftir seien die pseudometrischen Raume genannt. Der Pflege dieser Zusammenhange waren mehrere Arbeitstagungen ge­ widmet, fUr we1che das mathematische Forschungsinstitut in Oberwolfach in dankenswerter Weise den Rahmen bereitstellte. Die Teilnehmer werden die herzliche, personliche Atmosphare und die anregenden Diskussionen sicher in angenehmer Erinnerung behalten. Auf einer ersten, bereits sehr gut besuchten Tagung im Juni 1964 wurde beschlossen, dieses Gebiet weiter zu behandeln, und so fanden zwei weitere Tagungen statt: 22. bis 25. Juni 1965 tiber: Numerische Probleme in der Approximationstheorie unter Leitung der Herren Collatz und Meinardus 15. bis 20. November 1965 tiber: Funktionalanalytische Methoden in der Numerischen Mathematik unter Leitung der Herren Collatz und Unger.

Schulte von der Geschäftsstelle in Freiburg für alle redaktionelle Hilfe, ferner dem Birkhäuser Verlag für die wie stets sehr gute Ausstattung des Buches und alle Förderung.

Die vorliegende Broschtire wendet sich an spieltheoretisch interessierte Leser, die mit den grundlegenden Begriffen der Mengenlehre und mit mathematischen SchluB­ weisen vertraut sind. Sie hat eine besondere Klasse strategischer Spiele mit voll­ standiger Information zum Gegenstand, die - spieltheoretisch nicht ganz exak- haufig als "Spiele auf Graphen" bezeichnet werden und unter denen die sogenannten Nimmspiele die bekanntesten darstellen. Mit diesem Btichlein werden zwei Ziele verfolgt. Erstens und hauptsachlich sollen verschiedene Losungsbegriffe, und zwar vor allem Gleichgewichtssituationen, fUr diese Spiele untersucht werden. Zweitens solI der Leser anhand einer speziellen Spiel­ klasse mit einigen Fragestellungen der Spieltheorie vertraut gemacht werden. Ab­ gesehen von der Losung mehrerer konkreter Spiele werden die Ergebnisse theore­ tischer Art sein und sich von klassischen Aussagen zum selben Gegenstand vor­ wiegend darin unterscheiden, daB in den Spielen Partien unendlicher Lange auf­ treten dtirfen und Eigenschaften der verschiedenen Losungen - tiber die Frage nach der Existenz hinaus - im Mittelpunkt stehen. An mehreren entscheidenden Stellen wird an Uberlegungen von C. BERGE [1] angekntipft, und einige neue Aspekte werden hinzugefUgt. Die hier dargelegten Resultate stammen teils aus meiner Dissertation A [1] - bei dieser Gelegenheit mochte ich Herrn Prof. Dr. N. N. VOROB'EV und Herrn Dr. K. LOMMATZSCH fUr die dabei geleistete Betreuung meinen herzlichen Dank aussprechen -, teils aus spateren Untersuchungen, ftir die auch die Arbeit von J. SKOLE [1] interessante Impulse gab.