(This is a German survey paper on "Numerical methods for high dimensional problems
and the curse of dimension".)
Aus der Einleitung:
Viele hochdimensionale Probleme sind schwierig,
der Rechenaufwand der naheliegenden Verfahren wächst exponentiell
mit der Dimension.
Wir fragen nach der Güte von optimalen Verfahren und bemerken bereits hier,
dass dies nur Sinn macht in Bezug auf vorgegebene Funktionenklassen.
Gewisse hochdimensionale Probleme sind prinzipiell schwierig,
der Rechenaufwand von optimalen Verfahren wächst exponentiell
mit der Dimension.
Folgende Fragen werden diskutiert:
Was ist ein hochdimensionales Problem und warum sind solche Probleme wichtig?
Was ist ein numerisches Verfahren? Können wir Aussagen über alle
numerischen Verfahren machen? Was ist ein optimales Verfahren?
Wie beweist man untere Schranken für beliebige numerische Verfahren?
Wir werden Probleme kennenlernen, für die man exponentielle untere Schranken
beweisen kann und andere, für die es polynomiale Algorithmen gibt.
Ein solcher Existenzbeweis für polynomiale Algorithmen kann allerdings abstrakt oder
konstruktiv sein, so dass wir drei verschiedene Situationen unterscheiden:
Probleme, die dem Fluch der Dimension unterliegen (exponentielle untere Schranken)
Probleme, die dem Fluch der Dimension nicht unterliegen (Existenz von
polynomialen Algorithmen)
Probleme, die dem Fluch der Dimension nicht unterliegen (Konstruktion von
polynomialen Algorithmen).
Jahresbericht der DMV, erscheint.