Über Alternationskriterien in der Geschichte der Besten Chebyshev-Approximation

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 2.3 L angen- und Breitengrade an

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

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. So wird in der russischen Mathematischen Enzyklop adie behauptet, P. L .

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-

teil, n amlich daa uberhaupt keine Bemerkung 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. Leider muute die Beantwortung der Frage, was die Person P. L . Ceby sevs angeht,

negativ ausfallen, krasser, wir m ussen Gon carov r e c ht geben, daa n amlich Ceby sev dieser Frage in der Tat 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 Spezialf allen, gekannt (man muu sich n ur einmal den Graphen eines 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.

Dennoch ist der Beitrag 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 wich-

tigen 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

zeitlichen Abfolge uberschnitten haben. Der erste f uhrt direkt von Ceby sevs Arbeit ,,Sur les question des minima ...]" (1857) zum ersten Beweis von Kirchberger in seiner

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 die Unterst utzung und auch besonders Frau Natal'ja Sergeevna Ermolaeva 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-istomit~s s rezul~tatami issledovanii. Bez pomowi moego Frankfurtskogo riqeskie izyskanii po Peterburgsko$ i m a t ematiqesko$ i xkole. Po to$ i

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 zakaldovannye tropy redaktora T E X, ^{napr., realizacii kirillicy.} G. X t effens

Kapitel 1

Der Alternantensatz

1.1 Vereinbarungen

In der vorliegenden Arbeit betrachten wir einen Spezialfall der besten 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: p2IPn Die Gr ooe E n (f) : = inf

kp ; fk 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.

Eine zentrale Rolle in der Theorie der besten 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

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

jr(x)j = krk 1 :

KAPITEL 1. DER ALTERNANTENSATZ 2

;

p 0 ; f Abbildung 1.1: Veranschaulichung des Alternantensatzes: Graph einer Fehler-

funktion mit 5 Abweichungspunkten

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)

() 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 (p 0 ; f)(x i ) = (;1)(p 0 ; f)(x i+1 ) i = 1 : : : n + 1 :

(1.1) 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 Minimall osung ist. Schon P. L . Ceby sev hat hierf ur wichtige Vorarbeit geleistet

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 ) uglich aller Abweichungspunkte mit denen der Diierenzen p 0 (x i ) ; f(x i ) b e z ubereinhat das Polynom n;ten Grades p 0 ;q 0 mindestens n+1 Nullstellen, also verschwindet stimmen. 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

es identisch, d.h.

und p 0 ist eine Minimall osung an f:

2 p 0 q 0

E. Borel Genau in dieser Form ist der Beweis bei I. P. Natanson Nat55, S. 31] und 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

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 Uberle-gungen, 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

6

; ;

p 0 ; f 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 :

d ^k m;1 +1 : : : d km : enthalten Abw.punkte

mit Vorzeichen (;1) m;1

(1.2)

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 kon-

und deenieren

^m;1 Y i=1

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:

m n + 2

was zu beweisen war.

2

1.4 ,,Null in der konvexen H ulle" In Che66, Kap. 3] wird der Alternantensatz uber ein die Minimall osung charakteri-

sierendes Kriterium bewiesen. Zur Verdeutlichung sei der Alternantensatz wie folgt 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: 1. p 0 :=

fornuliert: i=0 P n

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 > > > > < B B B B @ C C C C A x

3. 0 2 con r(x) x Abweichungspunkt von r > > > > = . . . > > > > : x n

> > > > (1.5)

Die behauptete Aquivalenz von Aussage 1.3 und Aussage 1.4 beschreibt den klas-

Ceby sev sischen Alternantensatz. Interessant ist die Charakterisierung der besten

-Approximation durch die dritte Aussage. Cheney sagt in den Anmerkungen zu Ka-pitel 3 von Che66], daa sie auf den Ausf uhrungen Kirchbergers ((Kir02]) beruht. In

Ceby sev selbst formuliert

der Tat beruhen sie aber auf einem Satz, den schon P. L . Ceb57]. Wir kommen darauf noch z u r uck. und bewiesen hat

uber lineare Ungleichungen ((Che66], S. 19))

Lemma 1.4.2 (Satz Wir beweisen zun achst (1:3) , (1:5). Dazu ben otigen wir folgendes Lemma: kompakt. Dann gilt: konvexe Mengen: Sowohl f0g als auch con(U) s i n d k onvex und abgeschlossen, da U Sei U IR n

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 kompakt ist. Nach dem Trennungssatz existiert somit eine stetige lineare Abbildung

Die andere Beweisrichtung ,,(" ist einfach. Ist n amlich 0 2 con(U), so existieren

Da alle linearen Abbildungen im endlichdimensionalen Hilbertraum IR ⁿ als Skalar: I R ! IR mit

X (f0g) \ (conU) = : produkte geschrieben werden k onnen, ist dieser Teil bewiesen.

0 =

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

^{m m} Damit gilt f ur beliebiges z 2 IR ⁿ :

0 =

i u i u i 2 U:

X

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

k (c i ; d i ) ⁱ ; fj < krk: ^{1 i=0} 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]: 2

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 > > > > < > > > > = B B B B @ C C C C A x ⁱ 0 2 con i i = 0 : : : n + 1 . . . > > > > : > > > > x n i

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

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

1 x 1 x ^{n 1} V x 1 : : : x n+1 ] : = . . . . . . . . . . . .

:

1 x n+1 x ^{n n+1} Diese Determinante ist unter dem Namen Vandermond'sche Determinante bekannt

und verschwindet nicht f

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

i i ~ x i = 0 i=0

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 i r(x i )~ x i k n + 1 : 0 = i=0

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

Beim Beweis des Alternantensatzes

uber den Charakterisierungssatz (1.3 , 1.5) f allt

auf, daa die in den urspr unglichen Formulierungen (( Ceb57] und Kir02]) vorkommenden Aussagen 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 Im indirekten Beweis der Charakterisierungssatzes wurde nur anhand von Eigenin ihren Beweisen explizit bzw. implizit machen.

schaften der Abweichungspunkte eine bessere L osung konstruiert, ein Prinzip, das ebenfalls auf Ceb57]) zur uckgeht. Ceby sev ((

Die Alternationseigenschaft wird auf eine Eigenschaft der Vandermond'schen De-

terminante und damit auf die grundlegende algebraische Eigenschaft der Polynome zur uckgef uhrt, nur eine begrenzte, von der Gradzahl abh angende Anzahl von Null-

stellen zu haben. 1.5 Maximale lineare Funktionale

speziell konstruierten linearen Punktfunktionals L 2 B (Caa b]IR): Dieses wird

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 . . . . . . . . . . . .

x 1 x 2 x

B B B B @

x ⁿ 1 x ⁿ 2 x

C C C C A kLk = ⁿ⁺² X vom Rang n + 1 ist. F ur dieses Funktional gilt wie f ur alle Punktfunktionale ² : =1

j j

(1.11)

somit impliziert 1.9: ⁿ⁺² X

=1 j j = 1 zusammen mit der Forderung 1.10 erreichen wir also die Eindeutigkeit des linearen

Funktionals.

verschwindet:

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

(1.12) 1.5.1 Approximation auf einer Punktmenge

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

(1.13)