Inhaltsverzeichnis

Verzeichnis  der Abbildungen  v

Einleitung   vii

Danksagung  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  :x

1  Der Alternantensatz  1

1.1  Vereinbarungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  :1

1.2  Die Alternantenbedingung als hinreichende Bedingung : : : : : : :  :3

1.3  Der direkte Beweis : : : : : : : : : : : : : : : : : : : : : : : : : : :  :4

1.4  ,,Null in der konvexen H ulle" : : : : : : : : : : : : : : : : : : : : :  :6

1.4.1  Diskussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  11

1.5  Maximale lineare Funktionale : : : : : : : : : : : : : : : : : : : : : :  11

1.5.1  Approximation auf einer Punktmenge : : : : : : : : : : : : : :  12

1.5.2  Beweis des Alternantensatzes : : : : : : : : : : : : : : : : : :  14

1.5.3  Diskussion. Eine konstruktive A n wendung des Satzes von Kol-  

mogorov  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  17

1.6  Eine Anwendung des Lemmas von Zorn : : : : : : : : : : : : : : : : :  18

1.6.1  Eine minimale Menge, die die Bestapproximation bestimmt mi-  

nimale  Menge : : : : : : : : : : : : : : : : : : : : : : : : : : :  18

1.6.2  enth alt nur Abweichungspunkte von f p 0 : : : : : : : : :  20

1.6.3  Beweisschluu. Alternation : : : : : : : : : : : : : : : : : : : :  20

2  Vorl aufer des Alternantensatzes  23

2.1  Eulers Analyse des Delisle'schen Kartennetzentwurfs : : : : : : : : :  23

2.1.1  Die Delisle'sche Kartenprojektion : : : : : : : : : : : : : : : :  23

2.1.2  Die Methode : : : : : : : : : : : : : : : : : : : : : : : : : : :  25

2.1.3  Lagebestimmung der Punkte P und Q : : : : : : : : : : : : :  27

2.1.4  Minimierung des Projektionsfehlers : : : : : : : : : : : : : : :  28

2.1.5  Diskussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  30

2.2  Ein bestes Planetenmodell von Laplace : : : : : : : : : : : : : : : : :  31

2.2.1  Eine N aherungsformel zur Berechnung eines Ellipsenbogenst ucks  31

i

ii  INHALTSVERZEICHNIS  

2.2.1.1  Die Bogenl ange eines Ellipsenst ucks : : : : : : : : :  32

2.2.2  Das charakteristische Gleichungssystem : : : : : : : : : : : : :  33

2.2.3  Die Alternantenbedingung als hinreichende Bedingung : : : :  34

2.2.4  Die Alternantenbedingung als notwendige Bedingung : : : : :  35

2.2.5  Bestimmung der Maximalfehler : : : : : : : : : : : : : : : : :  37

2.2.5.1  Bestimmung des gr ooten Fehlers : : : : : : : : : : :  37

2.2.5.2  Bestimmung des kleinsten Fehlers : : : : : : : : : : :  39

2.2.5.3  Bestimmung der besten Ellipse : : : : : : : : : : : :  39

2.2.6  Anwendung auf Erdvermessungen : : : : : : : : : : : : : : : :  40

2.2.7  Diskussion. Ein diskretes Approximationsproblem : : : : : : :  42

3  Die Petersburger Mathematische Schule  43

3.1  Die Anst ooe zur Theorieentwicklung : : : : : : : : : : : : : : : : : : :  43

Ceby  sevs Auslandsreise : : : : : : : : : : : : : : : : : : : : : :  43

3.1.2  Die Poncelet'schen N aherungsformeln : : : : : : : : : : : : : :  45

3.1.3  Der Watt'sche Mechanismus : : : : : : : : : : : : : : : : : : :  46

Ceby  sev : : : : : : : : : : : : : : : : : : : :  47

3.2.1  Charakteristische Gleichungen : : : : : : : : : : : : : : : : : :  49

3.2.2  Ans atze f ur reell-analytische Funktionen : : : : : : : : : : : :  49

3.2.3  Das am wenigsten von Null abweichende Polynom (n 1)-ten  

Grades  mit vorgegebenem ersten Koeezienten : : : : : : : : :  51

3.2.3.1  Der Fall m 0: : : : : : : : : : : : : : : : : : : : :  52

3.2.4  Bemerkung. Alternanten : : : : : : : : : : : : : : : : : : : : :  53

3.3  Erste theoretische Ausarbeitungen : : : : : : : : : : : : : : : : : : : :  54

3.3.1  Problemstellung : : : : : : : : : : : : : : : : : : : : : : : : : :  55

3.3.2  Ein allgemeines notwendiges Kriterium : : : : : : : : : : : : :  55

3.3.3  Die Anzahl der Abweichungspunkte. Fallunterscheidungen : :  57

3.3.3.1  Polynomapproximation : : : : : : : : : : : : : : : : :  58

uber  Minima " : : : : : : : : : : :  59

Ceby  sevs : : : : : : : : : : : : :  61

3.4.1  Kein Beweis des Alternantensatzes : : : : : : : : : : : : : : :  62

Ceby  sevs Sch ulern : : : : : : : : : : : : : : : :  64

3.5.1  Egor Ivanovi c Zolotarev : : : : : : : : : : : : : : : : : : : : :  65

3.5.2  Das fr uhe Werk von Andrej Andreevi c Markov : : : : : : : : :  65

Uber  eine Frage von D. I. Mendeleev. Ein Alternan-  

tensatz.  : : : : : : : : : : : : : : : : : : : : : : : : :  66

3.5.3  Vladimir Andreevi c M a r k ov : : : : : : : : : : : : : : : : : : :  68

3.5.3.1  Die Aufgabenstellung. Ein Hilfssatz : : : : : : : : : :  68

3.5.3.2  Ein Alternantensatz von V A Markov : : : : : : : :  71

INHALTSVERZEICHNIS iii

4  Die ersten Beweise des Alternantensatz  73

4.1  Blichfeldts Bemerkung : : : : : : : : : : : : : : : : : : : : : : : : : :  73

4.2  Kirchbergers Dissertation. Ein erster Beweis : : : : : : : : : : : : : :  74

4.2.1  R uckgrii auf  

Ceby  sev : : : : : : : : : : : : : : : : : : : : : :  74

4.2.2  Der Beweis des Alternantensatzes : : : : : : : : : : : : : : : :  75

4.2.3  Fast im Ziel : : : : : : : : : : : : : : : : : : : : : : : : : : : :  76

4.3  E. Borels Vorlesungen : : : : : : : : : : : : : : : : : : : : : : : : : :  77

4.3.1  Der Alternantensatz als Hilfssatz f ur den Eindeutigkeitssatz :  77

4.3.2  Bemerkung zu Borels Quellen : : : : : : : : : : : : : : : : : :  79

4.4  A. A. Markovs Vorlesungen : : : : : : : : : : : : : : : : : : : : : : :  79

4.5  Young f ullt die letzte L ucke : : : : : : : : : : : : : : : : : : : : : : :  81

A  Einige Briefe von P. L  

Ceby  sev  83

A.1  Beantragung einer Reise zur Londoner Maschinenausstellung : : : : :  83

A.2  Der Aufenthalt in Frankreich : : : : : : : : : : : : : : : : : : : : : : :  85

A.2.1  Beschr ankung des Forschungsprogramms : : : : : : : : : : : :  85

A.2.2  Rechenschaftsbericht uber die Dienstreise nach F rankreich : :  86

A.3  Der Aufenthalt in England : : : : : : : : : : : : : : : : : : : : : : : :  88

B  Der Beweis von A. A. Markov (1906)  91

Literaturverzeichnis   97

INHALTSVERZEICHNIS iv

Abbildungsverzeichnis   

1.1  Veranschaulichung des Alternantensatzes : : : : : : : : : : : : : : :  :2

1.2  Veranschaulichung des direkten Beweises : : : : : : : : : : : : : : :  :5

1.3  Eintausch v on : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  16

2.1  Schema der Delisle'schen Schnittkegelprojektion : : : : : : : : : : : :  24

2.2  Zur abstandstreuen Einteilung der Meridiane : : : : : : : : : : : : : :  25

Aquator  und Pol : : : : : : : : : : : : :  26

2.4  Konstruktion eines L angengrades : : : : : : : : : : : : : : : : : : : :  27

2.5  Breitenmessung auf der Erdoberr ache : : : : : : : : : : : : : : : : : :  31

3.1  Das vollst andige Watt'sche Parallelogramm : : : : : : : : : : : : : : :  44

3.2  Das verk urzte Watt'sche Parallelogramm : : : : : : : : : : : : : : : :  46

v

ABBILDUNGSVERZEICHNIS vi

Einleitung

Wenn wir uns die Aufgabe stellen, ein Bogenst uck durch ein Geradenst uck s o a nzun ahern, daa der Unterschied zwischen beiden Linien m oglichst klein wird, so werden wir die Gerade immer so zu legen versuchen, daa sowohl rechts als auch links von ihr die maximale Abweichung gleich wird. Beispielsweise k ame niemand auf die Idee, den Halbkreis durch eine Linie anzun ahern, die genau dem Durchmesser entlangl auft. Vielmehr wird man hier die Gerade in die Mitte zu legen versuchen. Genau diese Idee verwendet Euler Eul98], um eine m oglichst genaue Karte des russischen Reiches zu zeichnen: Er n ahert die Erdkugel so durch eine Ebene an, daa der Fehler am n ordlichsten Punkt, am s udlichsten Punkt und ,,irgendwo in der Mitte" gleich i s t . Nun k onnte man vermuten, daa die beste N aherung hier von der Lage dieses Punktes abh angt, jedoch nach dem Alternantensatz h angt vielmehr der Punkt von der Gr ooe des minimalen maximalen F ehlers ab, bzw. beide Werte korrespondieren miteinander. Der Satz, von dem in dieser Arbeit die Rede sein wird, verallgemeinert dieses im Falle von Gerade und Bogen noch sehr anschauliche Problem auf reellwertige stetige Funktionen, die durch P olynome, bzw. im noch allgemeineren Fall, auf Funktionen, die der Haar'schen Bedingung gen ugen, angen ahert werden. Nach diesem Satz wird die Minimall osung dieses Problems dadurch c harakterisiert, daa sie mindestens (n + 1);mal maximal von der anzun ahernden Funktion mit unterschiedlichem V orzeichen abweicht, wenn n die Anzahl der Parameter des Problems ist. Wir konzentrieren uns hier auf den Fall der Besten Approximation durch P olynome, da zum einen die Haar'sche Bedingung nicht z u w esentlich neuen Beweisen f uhrt, bzw. diese auch nicht schwerer macht, und zum anderen der historische Weg deutlicher aufzuzeigen ist. Die vorliegende Arbeit versucht n un, folgende Aufgaben zu l osen:

1. Die verschiedenen modernen Beweise zu analysieren und zu vergleichen

2. Beispielhaft Problemstellungen aus dem 18. Jahrhundert aufzuzeigen, die noch vor der Entwicklung einer Theorie schon das Alternationsprinzip zur Bestimmung von N aherungsl osungen verwendeten

3. Den Weg von konkreten Problemen zur Bildung einer einheitlichen Theorie der Besten Approximation zu umreiien, wie er von P. L . Ceby sev und seinen

Sch ulern beschritten wurde, um weitere Probleme l osen zu k onnen

vii

EINLEITUNG viii

4. Die ersten Beweise des Alternantensatzes vorzustellen

Selbstverst andlich ist dabei von besonderem Interesse, wer den Alternantensatz zuerst bewiesen hat oder mindestens die Alternationseigenschaft als solche erkannt und formuliert hat. In der Literatur sind die verschiedensten Antworten zu nden.

Ceby sev

habe den Satz bewiesen Enzy, Bd. 5, S. 845], A. A. Gusak Gus72] behauptet zumindest, daa er die Alternation der Abweichungspunkte der Fehlerfunktion an Spezialf allen zumindest bemerkt hat und versucht dies an einem Beispiel zu belegen. Ein weiterer russischer Kommentator, V. L. Gon carov Gon45] behauptet nun das Gegen-Ceby sevs zu diesem Punkt vorliegt.

Um dies etwas zu entwirren, versuchte der Autor in St. Petersburg, also vor Ort, diese Frage zu kl aren. Ceby sevs angeht,

uberhaupt nicht nach ging, weil sie f ur ihn nicht i n teressant g e n ug war. Sicher hat er Alternanteneigenschaft, wenn auch vielleicht n ur in Ceby sev'schen

Polynoms anschauen), aber explizit erw ahnt hat er sie nie. Wir versuchen in Kapitel 3 genauer zu begr unden, warum dies so war und f ugen ein wenig anekdotenhaft an, daa es daf ur sogar wissenschaftspolitische Gr unde gab. Ceby sevs auuerordentlich w i c htig, und sein Werk nimmt auch in dieser Arbeit breiten Raum ein. Wir werden dann sehen, daa er einen Satz beweist, der als entscheidendes Hilfsmittel f ur den Alternantensatz bei Kirchberger fungiert. Kirchberger ist der erste, der einen Beweis ndet, der aber noch einen wichtigen Fall ausschlieet. So d urfen bei ihm nur endlich viele Abweichungspunkte vorkommen, oder, wenn unendlich v i e l e v orliegen, so muu die Fehlerfunktion auf ganzen Intervallen ihren maximalen Wert annehmen.

Historisch gab es zwei Wege, den Alternantensatz zu beweisen, die sich in der Ceby sevs Arbeit

,,Sur les question des minima ...]" (1857) zum ersten Beweis von Kirchberger in seiner Dissertation ,,Ueber Tchebyschefsche Ann aherungsmethoden" (1902), der zweite Weg Uber eine Frage von D. I. Mendeleev"

(1890) und die erste Erw ahnung einer Alternation in Blichfeldts ,,Note on the Functions ...] which in a Given Interval Diier the Least Possible Value from Zero" (1901) zu den Beweisen von Borel in den ,,Lee cons sur les Functions de Variables R eelles" uber Funktionen, die am wenigsten

von Null abweichen" (russisch, 1906) und schlieelich v on J. W. Young in ,,General Theory of Approximation by F unctions ...]" (1907). Der erste Weg f uhrt jedoch n ur, wie oben bemerkt, zu einer eingeschr ankten Version des Satzes, und auch Markovs Beweis ist unvollst andig, da er implizit eine Endlichkeitsbedingung f ur die Anzahl der

ix

Abweichungspunkte vorgibt. Da auch Borel noch eine kleine L ucke liee, liegt erst mit der Arbeit von Young ein kompletter Beweis vor.

Interessant ist, daa der letzte, l angere Weg zu dem konstruktiveren und anschaulicheren Beweis f uhrt. Da es sich bei den beiden letzten Texten um Vorlesungen handelt, kann das Publikationsdatum erheblich v on dem Erstellungsdatum abweichen. Da Markov Borels Arbeit nicht erw ahnt, wohl aber Blichfeldts Bemerkung, kann man vermuten, daa er in der Tat jene Arbeit nicht k annte. Deshalb wurden in dieser Arbeit beide Texte in diesem Sinne gleichrangig behandelt. Der Markov'sche Beweis des (einubersetzt, da er in keiner geschr ankten) Alternantensatzes wird im Anhang w ortlich Sprache auuer der russischen erschienen ist.

Neben diesen historisch gewachsenen Beweisen werden im ersten Kapitel noch zwei Beweise analysiert, von denen der erste auf der Konstruktion von maximalen Punktfunktionalen und dem Hahn-Banach'schen Satz Mei64] s o wie dem Satz von Kolmogorov, der andere lediglich auf dem Lemma von Zorn beruht Bro94].

Danksagung

Das Kernst uck d e r v orliegenden Arbeit bilden die mathematikhistorischen Ausarbeitungen zur Petersburger Schule. Aus diesem Grunde verbrachte ich elf Monate in uber den Stand der Forschung zu unterrich-St. Petersburg, um mich an Ort und Stelle

ten. Dies w are nicht m oglich gewesen ohne die Unterst utzung des Heimatbetreuers, Herrn Prof. Dr. B. Brosowski, der meine Bewerbung f ur ein Auslandsstipendium beim Deutschen Akademischen Austauschdienst vorantrieb.

Auch v or Ort war ich auf Hilfe angewiesen, und in diesem Sinne danke i c h den ur Herren Professoren Garal'd Isidorovi c Natanson und Vasilij Nikolaevi c Malozemov f ur mehrere fachlich sehr interessante Gespr ache und f ur die Vermittlung an die Bibliothek der St. Petersburger Abteilung des Steklov-Instituts.

Last not least bin ich Herrn Dipl.-Math. Peter Bauer zu grooem Dank verppichtet, da er mehrere Abende geopfert hat, mich d u r c h die verschlungenen Pfade des T E X-Programms zu leiten. Auch die Implementation des kyrillischen Zeichensatzes ist sein Verdienst. G. Steeens

Slova blagodarnosti

Suwestvenno$ i qast~~ predlooenno$ i raboty vlllts matematiko-istoriqeskie izyskanii po Peterburgsko$ i m a t ematiqesko$ i xkole. Po to$ i priqine provel odinnadcat~ mescev v S-Peterburge, qtoby tam oznako- mit~s s rezul~tatami issledovanii. Bez pomowi moego Frankfurtskogo

EINLEITUNG x

nauqnogo rukovoditell, prof. d-r. Bruno Brozovski, podderravxego moe pretendovanie na stipendii za granicu u Nemecko$ i Sluuby dll Akademiqeskogo Obmena (DAAD), togo ne bylo by vozmoono. I t am mne neobhodima byla pomow~, i pootomu iskrenno blagodarr gg. professorov Garal~da Isidoroviqa Natansona i Vasilii Nikolaeviqa Malozemova za podderrku, a osobenno g. Natal~~ Sergeevnu Ermolaevu za oqen~, s toqko$ i zrenii istorii matematiki, interesnye razgovory i posredniqestvo dll raboty v biblioteke LOMI imeni Steklova. V zakllqenii hoqu vyrazit~ svoo blagodarnost~ g. P e t eru Baueru, kotory$ i v t eqenie neskol~kih veqerov uspel provesti menn qerez zakal-

dovannye tropy redaktora T E X, ^{napr., realizacii kirillicy.} G. X t effens

Kapitel 1

Der Alternantensatz

1.1 Vereinbarungen

Ceby sev -Approximation, und zwar die Approximation einer reellwertigen stetigen Funktion durch P olynome vorgegebenen Grades.

Deenition 1.1.1 (Beste Approximation, Minimall osung)

Seien aa b 2 IR f 2 (C((aa b] IR) k:k 1 ) I P n sei der Raum der Polynome vom Grade n: Die Gr ooe kp ; fk E n (f) : = inf p2IPn

heiit beste Approximation f ur f bez uglich IP n : Eine Funktion p 0 2 IP n mit kp 0 ; fk = E n (f)

heiit Minimall osung f ur f bez uglich IP n :

Wenn nichts anderes vorausgesetzt wird, gelten diese Vereinbarungen. Ceby sev-Approximation spielt der

Alternantensatz, da er die Minimall osung des Problems p 0 durch eine Eigenschaft der Extremal- oder Abweichungspunkte der Fehlerfunktion p 0 ; f charakterisiert.

Deenition 1.1.2 (Abweichungspunkt)

Sei r eine stetige reellwertige Funktion. x 2 IR heiit Abweichungspunkt von r genau dann, wenn jr(x)j = krk 1 :

Pluspunkte nennen wir Abweichungspunkte x von r f ur die gilt:

r(x) = krk 1

1

KAPITEL 1. DER ALTERNANTENSATZ 2

Abbildung 1.1: Veranschaulichung des Alternantensatzes: Graph einer Fehler-

und analog nennen wir Abweichungspunkte x von r Minuspunkte, wenn gilt:

r(x) = ;krk 1 :

Nun k onnen wir den Alternantensatz formulieren:

Satz 1.1.3 (Alternantensatz)

p 0 ist Minimall osung f ur f bez uglich IP n

im Intervall aa b] eine Punktmenge x 1 < x 2 < < x n+2 von Abweichungspunkten von p 0 ; f existiert, die abwechselnd Plus- bzw. Minuspunkte sind, f ur die also gilt:

j(p 0 ; f)(x i )j = kp 0 ; fk i = 1 : : : : n + 2

Eine Menge von Abweichungspunkten, die die Eigenschaft 1.1 besitzen, wird auch Ceby sev'sche) Alternante genannt. Die Abbildung 1.1 zeigt eine solche Alternante. Interessant bei der Betrachtung verschiedener Beweise des Alternantensatzes ist im wesentlichen nur der Aspekt, daa die Alternanteneigenschaft notwendig f ur die Mi-Ceb57],

die jedoch erst 50 Jahre sp ater zum Beweis reifte ((Kir02] und Bli01]). Zun achst zeigen wir aber, daa die Alternanteneigenschaft die Minimall osung schon zu bestimmen vermag.

1.2. DIE ALTERNANTENBEDINGUNG ALS HINREICHENDE BEDINGUNG 3

1.2 Die Alternantenbedingung als hinreichende

Bedingung

Direkt aus der Polynome n;ten Grades charakterisierenden Eigenschaft, nur h ochstens n Nullstellen zu besitzen, folgt, daa die Aussage des Alternantensatzes hinreichend f ur die Minimall osung des besten Ceby sev - Approximationproblems ist.

Beweis:

Wir setzen die Alternantenbedingung f ur n + 2 A b weichungspunkte x 1 < x 2 < < x n+2 von p 0 ; f voraus. Setzen wir nun jp 0 (x) ; f(x)j A := max x2aab]

so gilt laut Deenition der Best-Approximation E n (f) :

A E n (f):

Es bleibt zu zeigen, daa A und E n (f) denselben Wert haben. Hierzu sei q 0 die Minimall osung an f:Die Gleichung

p 0 (x i ) ; q 0 (x i ) = fp 0 (x i ) ; f(x i )g ; f q 0 (x i ) ; f(x i )g i = 1 : : : n + 2

in den Abweichungspunkten zeigt, daa die Vorzeichen der Diierenzen p 0 (x i ) ; q 0 (x i ) mit denen der Diierenzen p 0 (x i ) ; f(x i ) b e z ubereinstimmen. Da die Abweichungspunkte eine Alternante von n + 2 Elementen bilden, andert sich das Vorzeichen der Diierenz p 0 ; q 0 also mindestens n + 1 ; mal, damit hat das Polynom n;ten Grades p 0 ;q 0 mindestens n+1 Nullstellen, also verschwindet es identisch, d.h.

und p 0 ist eine Minimall osung an f:

2

Genau in dieser Form ist der Beweis bei I. P. Natanson Nat55, S. 31] und E. Borel

Bor05] zu nden. Dasselbe Argument v erwendeten auch K i r c hberger Kir02], A. A. Markov (AMar06] und Anhang B) und J. W. Young You07]. Bei Meinardus ndet diese recht einfache Tatsache nur in dem Satz, daa die Minimall osung durch die Alternanteneigenschaft eindeutig bestimmt wird, Erw ahnung Mei64, S. 21]. Cheney

Che66] geht einen anderen Weg, da er bei dem Beweis seines Charakterisierungssatz ubern achsten Abschnitt.

KAPITEL 1. DER ALTERNANTENSATZ 4

1.3 Der direkte Beweis

Der nun folgende direkte Beweis, der besonders in seiner Anschaulichkeit besticht, wurde von I. P. Natanson Nat55, Kap. 2, S. 27-31] formuliert. Er beruht a u f Uberlegungen, die schon H. F. Blichfeldt Bli01] aufstellte, und wurde von E. Borel Bor05] zuerst formuliert.

Als Vorbereitung des Alternantensatzes gilt folgendes einfaches Lemma:

Lemma 1.3.1 Ist p 0 Minimall osung von f bez uglich IP n so existieren ein Pluspunkt und ein Minuspunkt von p 0 ; f:

Der Beweis beruht auf einem Verschiebungsargument. Da p 0 ;f stetig in aa b] ist, nimmt diese Funktion auf dem Kompaktum aa b] ihr Minimum, e t wa i n ^ x an. G abe

es nun keinen Minuspunkt, dann w are p 0 (^ x) ; f(^ x) > ;E n und wir k onnten die Fehlerfunktion p 0 ;f etwa um den Wert 1 2 (E n +p 0 (^ x);f(^ x)) nach u n ten verschieben 2 und erhielten so eine bessere Approximation an f:

Der nun folgende Beweis des Alternantensatzes beruht auf einer Verallgemeinerung dieses Arguments. Bestimmt wird ein Polynom das die Fehlerfunktion p 0 ; f in den Abweichungspunkten vermindert und auuerhalb gewisser Umgebungen nicht zu groo wird. Ein solches Polynom kann immer gefunden werden, da nach dem Weierstraa'schen Approximationssatz

n!1 E n = 0 lim

gilt. Die Crux muu also beim Grad von liegen. Wir werden sehen, daa die Anzahl der vorliegenden alternierenden Abweichungspunkte dar uber entscheidet. Ist diese kleiner als n + 1 so ist p 0 ; eine bessere L osung. Im Falle des Lemmas war konstant.

Beweis (Alternantensatz) :

Wir zerlegen das Intervall in Teilst ucke, in denen die Variation von p 0 ; f den Wert ubersteigt, d.h. wir bestimmen Punkte a = u 0 < u 1 < < u s;1 < u s = bb 2 E n nicht ¹ mit

^u i xxyu i+1 jp 0 (x) ; f(x) ; (p 0 (y) ; f(y))j < 1

2 E n 8i = 0 : : : : s ; 1: max

Nun betrachten wir diejenigen Teilst ucke, in denen Abweichungspunkte liegen und nehmen o.B.d.A. an, daa der erste Abweichungspunkt ein Pluspunkt sei. Diese Extremalsegmente bezeichnen wir mit d 1 : : : d N wobei jedes d j die Gestalt

d j = = u ^s j u ^s j +1 ] mit 0 s j s ; 1

hat und die d j entsprechend aufsteigend angeordnet sind. Wir halten fest, daa die d j paarweise elementfremd sind, da f ur sie die allgemeine Konstruktionsbedingung

1.3. DER DIREKTE BEWEIS 5

d 1 d 3 ^- d 4

E n

Abbildung 1.2: Veranschaulichung der Konstruktion des direkten Beweises des Alternantensatzes. Hier sind k 1 = 1 k 2 = 2 k 3 = 4 und k 4 = 5 :

bez uglich der Variation der Fehlerfunktion gilt. Nun sehen wir, daa wir uns die d j in einer Art alternierenden Sequenz aufgeteilt vorstellen k onnen:

d 1 : : : d ^k 1 : enthalten Pluspunkte

Damit reicht zu zeigen:

m n + 2 :

Nun wollen wir das gesuchte Polynom 0 bestimmen, f ur das gelten soll:

kp 0 ; 0 ; fk < kp 0 ; fk:

Hierzu w ahlen wir zwischen den Extremalsegmenten liegende Punkte z 1 : : : z m konkret:

maxd ^k i < z i < mind ^k i+1 8i = 1 : : : : m ; 1

und deenieren

Die Abbildung 1.2 veranschaulicht diese Konstruktion. Wir stellen zwei wichtige Eigenschaften von fest:

KAPITEL 1. DER ALTERNANTENSATZ 6

Alle Nullstellen von liegen auuerhalb der Extremalsegmente

In den Extremalsegmenten haben und p 0 ; f gleiches Vorzeichen

Das heiit, daa nur noch eine geeignete Konstante 2 IR zu nden ist, die die Variation von steuert, um die gesuchte Funktion 0 := zu bestimmen, die die Approximation verbessert. Hierzu m ussen zwei Forderungen erf ullt werden:

1. Um die Variation in den Extremalsegmenten gering zu halten:

< E n

2kk :

2. Um die Variation auuerhalb der Extremalsegmente zu vermindern:

< 1

kk (E n ; max jp 0 (x) ; f(x)j):

6 9i:x2d i

Diese Wahl bewirkt in der Tat, daa

kp 0 ; 0 ; fk < kp 0 ; fk

gilt.

Ist nun aber m = 1 + grad n + 1 so ist p 0 ; 0 eine bessere L osung, p 0 kann im Widerspruch zur Annahme dann nicht Minimall osung sein. Daher gilt:

was zu beweisen war.

2

1.4 ,,Null in der konvexen H ulle"

uber ein die Minimall osung charakterisierendes Kriterium bewiesen. Zur Verdeutlichung sei der Alternantensatz wie folgt fornuliert:

Satz 1.4.1 (AlternantensatzzChe66]) f sei eine auf aa b] stetige und reellwertige Funktion und c 0 : : : c n reelle Zahlen. Dann sind aquivalent:

P n

1. p 0 := c ^{i i} ist auf aa b] Minimall osung f ur fbez uglich IP n (1.3) i=0

1.4. ,,NULL IN DER KONVEXEN H ULLE" 7

2. r := f ; p 0 hat mindestens n + 2 alternierende Abweichungspunkte (1.4) 8 9 0 1

1 > > > > < > > > > =

3. 0 2 con

Aquivalenz von Aussage 1.3 und Aussage 1.4 beschreibt den klas-

Ceby sev

-Approximation durch die dritte Aussage. Cheney sagt in den Anmerkungen zu Kapitel 3 von Che66], daa sie auf den Ausf uhrungen Kirchbergers ((Kir02]) beruht. In der Tat beruhen sie aber auf einem Satz, den schon P. L . Ceby sev selbst formuliert und bewiesen hat uck.

Wir beweisen zun achst (1:3) , (1:5). Dazu ben otigen wir folgendes Lemma:

uber lineare Ungleichungen ((Che66], S. 19)) Lemma 1.4.2 (Satz Sei U IR ⁿ kompakt. Dann gilt:

0 6 2 con(U) , 9z 2 IR ⁿ so daa 8u 2 U : < u z >> 0

Beweis: Die Aussage ) 00 des Lemmas ist ein Spezialfall des Trennungssatzes f ur konvexe Mengen: Sowohl f0g als auch con(U) s i n d k onvex und abgeschlossen, da U kompakt ist. Nach dem Trennungssatz existiert somit eine stetige lineare Abbildung : I R ! IR mit (f0g) \ (conU) = :

Da alle linearen Abbildungen im endlichdimensionalen Hilbertraum IR ⁿ als Skalarprodukte geschrieben werden k onnen, ist dieser Teil bewiesen. Die andere Beweisrichtung ,,(" ist einfach. Ist n amlich 0 2 con(U), so existieren

1 : : : m 2 IR i 0 und P i = 1 so daa

X m

i u i u i 2 U: 0 = i=1

Damit gilt f ur beliebiges z 2 IR ⁿ :

X m

i < u i z>: 0 = i=1

Da alle 1 : : : m nichtnegativ sind, existiert ein Index k 2 f 1 : : : : m g so daa

< u k z> > 0 u k 2 U:

2

KAPITEL 1. DER ALTERNANTENSATZ 8

Nun beweisen wir die Aquivalenz der Aussagen 1.3 und 1.5.

Beweis:

Zur Abk urzung deeniere ~ x := (x : : : x ⁿ ), x 2 aa b]

U := confr(x)~ x j x Abweichungspunkt von rg:

Mit diesen Vereinbarungen ist zu zeigen:

p 0 Minimall osung f ur f () 0 2 con(U):

Zur weiteren Abk urzung deenieren wir X 0 := fx 2 aa b]jx Abweichungspunkt von rg. Wir halten zun achst fest, daa X 0 als beschr anktes und stetiges Urbild der Menge f;krk krkg kompakt ist.

Wir beginnen nun mit dem Beweis, und zwar zeigen wir zuerst die Notwendigkeit der Aussage 1.3.

Annahme: krk nicht minimal. Dann existiert ein d 2 IR ⁿ⁺¹ mit:

X n

F ur x 2 X 0 gilt damit

X

r(x) ; d i x ⁱ ] ² < r(x)] 2

und schlieelich

h X d i x i;1 i ² =2 > 0: X

d i x ^i;1 > r(x) < d ~ x > = r(x)

Da X 0 kompakt ist, ist auch U kompakt und das Lemma anwendbar, also gilt: 0 6 2 con(U):

Nun zeigen wir, daa 1.3 auch hinreichend f ur 1.5 ist: Annahme: 0 6 2 con(U): Nach dem Lemma existiert ein d 2 IR ⁿ⁺¹ mit

r(x) < d ~ x > > 0 x 2 X 0 :

Wegen der Kompaktheit von X 0 gilt nun:

" := minfr(x) < d ~ x > jx 2 X 0 g

existiert und ist positiv. Wir deenieren nun

: x 2 X j r(x) < d ~ x > "

1.4. ,,NULL IN DER KONVEXEN H ULLE" 9

Es gilt dann: X 1 abgeschlossen, X 1 \ X 0 = : Damit existiert

E := supfr(x)jx 2 X 1 g

und es gilt: E < krk. W ahle nun mit

!

krk ; E "

Damit l aat sich die N aherung an f noch v erbessern, denn mit dieser Vereinbarung gilt:

X

r(x) ; d i x ⁱ ] ² < krk ² (1.6)

f ur alle x 2 aa b]:

Nun wollen wir beweisen, daa diese Charakterisierung der besten Approximation auch n o t wendig und hinreichend f ur die Alternantenbedingung ist. Dies ist die Besonderheit des Zugangs von Cheney. Daf ur ben otigen wir folgendes Lemma:

Lemma 1.4.3 (((Che66], S. 74))

Seien a x 0 < x 1 < : : : < x n+1 b und 1 : : : : : n+1 6 = 0 : Dann sind aquivalent: 8 9 0 1

1 > > > > < > > > > =

0 2 con

Die Vorzeichen der i alternieren ( i i;1 < 0 8i = 1 : : : : n )

Beweis: Wir nehmen wieder ~ x := (1 x : : : x ⁿ ) und deenieren

1 x 1 x ⁿ 1

Diese Determinante ist unter dem Namen Vandermond'sche Determinante bekannt

d.h. f ur a x 1 <: : : n+1 b gilt nochmehr, n amlich d a V x 1 : : : : x n+1 ] i h r Vorzeichen nicht andert. Existierte im Gegenteil a y 1 <: : : y n+1 bb so daa beispielsweise

V x 1 : : : x n+1 ] < 0 < V y 1 : : : y n+1 ]

KAPITEL 1. DER ALTERNANTENSATZ 10

so g abe es wegen der Stetigkeit der Determinante ein 2 (0 1) mit

V x 1 + ( 1 ; )y 1 : : : : : x n+1 + ( 1 ; )y n+1 ] = 0 :

Damit aber m ussen zwei Zeilen der Determinante gleich sein, d.h.

9ii j 2 f 1 : : : : n + 1 g i 6 = j : x i + ( 1 ; )y i = x j + ( 1 ; )y j :

Damit gilt im Widerspruch zur Annahme

x i ; x j = ;(y i ; y j ):

Zur eigentlichen Behauptung des Lemmas stellen wir fest, daa der Ursprung dann und nur dann in der konvexen H ulle der Menge f i ~ x i ji = 0 : : : : n + 1 g liegt, wenn die Gleichung ⁿ⁺¹ X

eine nichttriviale L osung ( 0 : : : n+1 ) besitzt, deren Komponenten positiv sind (Anderenfalls w aren n + 1 V ektoren schon linear abh angig). Die obige Summe ist dann gerade die Konvexkombination des Ursprungs. Aufgel ost nach ~ x 0 erhalten wir (alle i 6 = 0 nach V oraussetzung):

ⁿ⁺¹ X ; i i

Nach der Cramerschen Regel haben wir dann f ur ein beliebiges i:

; i ⁱ = V x 1 : : : x i;1 x 0 x i+1 : : : x n+1 ] 0 0 V x 0 : : : x n+1 ]

Nach i ; 1 Spaltenvertauschungen erhalten die beiden Determinaten nach der obigen Bemerkung das gleiche Vorzeichen. Jede dieser Spaltenvertauschungen ver andert aber das Vorzeichen der Determinante, damit erhalten wir, da alle i positiv sind,

sign( ; ⁱ 0 ) = ( ;1) ^i;1 , a l s o

sign( i ) = (;1) ⁱ sign( 0 ):

Nun k onnen wir die verbleibende Aquivalenz 1.4 , 1.5 unseres Satzes leicht b e - weisen:

1.5. MAXIMALE LINEARE FUNKTIONALE 11

Beweis: Liegt n amlich der Ursprung in der konvexen H ulle von fr(x)~ xjr(x) = krkg, s o l aat er sich n a c h dem Satz von Carath eodory (s. z.B. Che66], S. 17) als konvexe Linearkombination von h ochstens n + 2 Elementen dieser Menge darstellen, d.h.

X k

Da die x i paarweise veschieden sind, gilt: k n + 1, also ist k = n + 1. Denken wir uns die x 0 : : : x n+1 aufsteigend angeordnet, so gilt die Alternationseigenschaft nach dem letzten Lemma. Damit ist der Satz bewiesen.

2

1.4.1 Diskussion

uber den Charakterisierungssatz (1.3 , 1.5) f allt

Ceb57] und Kir02]) vorkommen-

uber die Anzahl der Koeezienten der Konvexkombination (bzw. fr uher: des linearen Gleichungssystems) verschwunden sind, so daa wir zur Bestimmung der Anzahl der minimal vorhandenen Abweichungspunkte den Satz von Carath eodory ben otigen. Damit wird aber auch die Endlichkeitsbeschr ankung umgangen, die beide in ihren Beweisen explizit bzw. implizit machen.

Im indirekten Beweis der Charakterisierungssatzes wurde nur anhand von Eigenschaften der Abweichungspunkte eine bessere L osung konstruiert, ein Prinzip, das Ceby sev (( Ceb57]) zur uckgeht.

Die Alternationseigenschaft wird auf eine Eigenschaft der Vandermond'schen Determinante und damit auf die grundlegende algebraische Eigenschaft der Polynome zur uckgef uhrt, nur eine begrenzte, von der Gradzahl abh angende Anzahl von Nullstellen zu haben.

1.5 Maximale lineare Funktionale

G. Meinardus zeigt in Mei64, x 3.2] einen Beweis des Alternantensatzes mithilfe eines

uber

die Abweichungspunkte a x 1 <: : : n+2 b der Minimall osung p 0 wie folgt deeniert:

ⁿ⁺² X

KAPITEL 1. DER ALTERNANTENSATZ 12

kLk = 1 sowie (1.9)

Durch die Bedingung 1.8 sind die bis auf einen gemeinsamen Faktor eindeutig bestimmt, da die Matrix dieses Gleichungssystems, 0 1

1 1 1

B B B B @

vom Rang n + 1 ist. F ur dieses Funktional gilt wie f ur alle Punktfunktionale ² :

ⁿ⁺² X

kLk = j j (1.11) =1

somit impliziert 1.9:

ⁿ⁺² X

=1

zusammen mit der Forderung 1.10 erreichen wir also die Eindeutigkeit des linearen Funktionals.

Von besonderer Bedeutung ist folgender Zusammenhang zwischen diesem Funktional und dem Wert der Bestapproximation E n (f): Es gilt n amlich, da L auf IP ⁿ verschwindet:

jL(f ; p 0 )j + jL(p 0 )j j k Lkkf ; p 0 k = E n (f) damit

1.5.1 Approximation auf einer Punktmenge

Wir deenieren wie oben ein lineares Funktional auf einer Punktmenge f 1 : : : n+2 g g aa b] und ordnen ihm durch die folgenden Gleichungen ein Polynom q 2 IP n zu:

q( ) + sign = f( ) = 1 : : : : n + 2 : (1.13)

Da n + 1 Koeezienten q bestimmen, werden q und die Gr ooe durch dieses Gleichungssystem eindeutig deeniert. Dieses Polynom minimiert den Approximationsfehler auf der Punktmenge 1 : : : : : n+2 :

² s. z.B. KA84, S. 177 f.]