Die Bedeutung der Normalit~it bei rationaler Tschebyscheff-Approximation

Von

H. Werner, Miinster

Mit 1 Textabbildung

(Eingegangen am 29. Juni 1966)

Zusammen[assung. In der vorliegenden Arbeit wird die Bedeutung der Normalitiit einer Funktion J (x) beziiglich der rationaler~ T-Approximation fiir die numerische Behandlung des Problems herausgearbeitet.

Unter Voraussetzung der Normalitgt yon ] (x) l~l~t sich zeigen, dab die TSCHEBV- sc~EF~-Approximierende T []] LiPseHI~Z-stetig von ] (x) abhgngt. Welter wird ein vollst~ndiger Beweis fiir die Konvergenz des REMEs-Algorithmus beim Start mit einer hinreichei~d guten NgherungslSsung gegeben. Die KOlxvergenz ist bei stetigeI~ ] (x) zumindest linear. Schliel~lich wird untersucht, wie stark sich die diskrete T-Ap- proximation yon J (x) (d. h. ApproximatioI1 auf einer im Intervall gegebenen endlichen Punktmenge) VOlX tier Approximation T [J] unterscheidet. Es werden qualitative Aussagen gewormen.

Summary. In this paper the significance of normality of a function ] (x) with regard to T-Approximation for the numerical treatment of the problem is set forth.

Assuming ] (x) to be Imrmal the LIPseHI~Z-COntinous dependence of the TSC~IEBu SC~E]~F-approximation T []] on ] (x) is shown. Under the same assumption a detailed proof of the convergence of the ~EMES Algorithmus for a sufficiently good initial approximation is provided. The convergence is at least linear. FirLally the discrete T-Approximation of ] (x) (approximation on a finite point set of the interval) is compared with T [J], There are qualitative results.

Einleitung I n der Analysis und der Angewandten Mathemat ik wendet man sich

heute mehr und mehr nichtlinearen Problemen zu. Man versucht allerdings racist, die Ergebnisse der nichtlinearen Aufgabe mit denen einer analogen linearen Aufgabe zu vergleichen.

I m vorliegenden Falle ist das lineare Problem. die Approximat ion mit linearen Kombina t ionen yon (n ~ 1) Funkt ionen eines TSCItEBYSCttEFF- Systems, im speziellen Fall mit Po lynomen veto Grade n.

Das nichtlineare Problem ist die Approximat ion mit rat ionalen Funk- tionen, bei denen (n-t- 1) Pa ramete r vorhanden sind. Ziel dieser Arbeit ist der Nachweis, dal~ die (lokale) Analogie zwischen Polynomapproxi - mat ion und rationaler Approximat ion bei einer festen stetigen Funk t ion f (x) genau dann besteht, wenn f (x) normal ist (Definition siehe unten),

I-I. W ~ E R : Die Bedeutung der Normalit/it bei Tschebyscheff-Approximation 35

sofern man von dem trivialen Falle absieht, dab f (x) selbst eine rat ionale Funk t ion ist, die sich exakt dureh die Approximat ionsfunkt ion darstellen l/iBt.

Die Analogie erstreckt sich sowohl auf das Stet igkeitsverhalten als auch auf die lokale Konvergenz des Remesalgori thmus und die Diskreti- sierungsfragen. Wenn die S/~tze ffir Polynome nicht besonders zur Gegen- iiberste]lung formuliert werden, so deshalb, weil sie als Spezialf/flle in den angegebenen S/itzen enthal ten sind.

1. Definitionen

Auf dem endlichen Interval l 1 : ~ [~, fl] sei w (x) eine stetige, positive Gewichtsfunktion. In C [a, fl], der Klasse der stetigen Funkt ionen auf I , werde durch

l{.f(x) !t: = m a x l f ( x ) �9 w (x)[ (1.1) [~,fl]

eine Norm eingefiihrt. Ohne Einsehr/~nkung darf zur Vereinfachung der Schreibweise fiir die

folgenden Uberlegungen angenommen werden, da6 max w ( x ) = 1 ist, so dab die kons tante Funk t ion 1 die Norm 1 hat.

Als Approximat ionsfunkt ionen werden die Polynome vom Grade l bzw. rationale Funkt ionen vom Z/ihlergrad l und Nennergrad r betrachtet . Diese werden abgekiirzt als Klasse ~t, ~ bezeichnet.

p (x) Jeder rat ionalen Funkt ion R (x) ~ q ~ e ~z, ,, wobei p (x) und q (x)

Polynome sind mitSp ~ l, 0 ~ ~q ~ r (dabei bezeichnet @ den Grad yon p, usw.), wird dureh d~, ,, [R] : ~ rain I1 -- 5p, r -- 5q] ~ 5s, wobei s gr6Bter. gemeinsamer Teiler yon p und q ist, eine ganze Zahl zugeordnet. Man nennt R nicht ausgeartet, wenn d~,, [R] ~ 0 ist. Alle anderen Funkt ionen R, die also bereits in ~,-~, +,-1 liegen, wenn man gekiirzt hat, nenn t man ausgeartet. Offenbar sind Polynome nicht ausgeartet. Bis auf einen Vorzeichenfaktor seien die eine rationale Funk t ion darstellenden Polynome p, q durch H q II ~ 1 normiert. Verschwindet q (x) in I nicht, so sei fiberdies q (x) > 0.

Man vergleiche ffir die Begriffsbildungen WER~n~ [1966]. Das T-Approximations-Problem besteht darin, zu vorgegebenem f eine

Funkt ion R ~ ~ ~l, r zu bestimmen, fiir welehe

ftir alle R e ~t, +. gilt.

Bezeichnungen ."

I I R ~ ~ < ( I R - - f E I

T . ~ I f ] : = R~

'7~, ~ [ f ] : = II R0 - - f II,

fiir beliebige rationale Funkt ionen R sei

( x ) : = f ( x ) - R ( x ) ,

(1.2)

( 5 . 3 )

(1.4)

3*

36 H. WnaNER:

( x ) : = ( f ( x ) - R (x)) w (x), (1 .5)

insbesondere 7 ~ (x): = ( f (x) - - R ~ (x)) �9 w (x) usw. Das A p p r o x i m a t i o n s p r o b l e m ist b e k a n n t l i e h 16sbar, die L 6 s u n g ist

e indeu t ig b e s t i m m t u n d charak te r i s i e r t d u r e h die E x i s t e n z einer A l t e r n a n t e zu f(x), d . h . einer Fo lge y o n n ' - t - 2 P u n k t e n xo . . . . , x~,+l ~ I , m i t n ' : = l -t- r - - dz, ~ [R~ ftir die gilt

xi < xi+l u n d sgn r] ~ (xi) = - - sgn r]0 (xi+l) ' (A 1)

I rj ~ (x~)l = I1 s~ (x) II, fiir i = 0, . . . , n ' @ 1. (A 2)

Gilt fiir die P u n k t e x~ n u r (A 1), abe r n ieh t n o t w e n d i g (A 2), so sp r i eh t m a n mi t STIEF]~T, [1959] v o n einer Referenz.

I f I

ji 1o 5 . . . . . . . . . . . . . . . . . . . . . . . . . .

-0,5

1 i ( x ) = x ~ - - -

2 '

beste Approximation in [-- 1, + 1] ist die • Alter~antenpunkte -- 1, 0, @ 1 (Ordinater~ angedeutet durch -- --

Beste Approximation auf dem cIureh (~)und • gekennzeiehneten :Raster . - )

I m Fa l l der P o l y n o m e /- ten Grades h a t m a n , wegen d~, o [R] = 0, fiir jede t~unkt ion y o n ~Rz, o ( m a n k a n n 1 als den N e n n e r nehmen) n ~- 2 = l -t- r -~ 2 A l t e r n a n t e n p u n k t e , n/~mlieh einen m e h r als P a r a m e t e r zur Verf i igung s tehen.

Bei r a t i ona l en F u n k t i o n e n k a n n die A n z a h l der A l t e r n a n t e n p u n k t e gleich oder sogar kle iner als die A n z a h l der v o r h a n d e n e n P a r a m e t e r sein. Dies ist eine wesent l iche A b w e i c h u n g y o n d e m Po lynomfa l l . Diese Ver- k le ine rung der A l t e r n a n t e ist aber als Sonderfa l l anzusehen , wie sich im fo lgenden zeigt. Ma n definier t desha lb :

Die Bedeutung der Normali~/i~ bei ra~ionaler Tschebyscheff-Approximation 37

Definition 1: Eine Funk t ion f (x)e C [a, fl] ist (1, r)-normal im Inter- vall I zum Gewicht w (x), wenn die T-Approximierende T~, r If] nicht ausgeartet ist, d, h. wenn d , r [T~,~ [ f ] ] -~ 0 ist. Die Menge der (l, r)- normalen Funkt ionen werde mit Nt, ~ bezeiehnet.

Die Normalit/~t h/ingt sehr wesentlieh yore Interval l ab. Eine gering- fiigige Verkiirzung des Interval ls kann yon der Nichtnormali t~t zur Nor- malit/it fiihren.

1 B e i s p i e l : Sei f ( x ) : - - - - x 2 - - w ( x ) : = 1. Im Interval l [ - - 1 , q- 1] 2 '

ist dann To, o If] ~ TI, 1 If] -~ 0. Denn es gibt 3 Al te rnantenpunkte -- 1, 0, + 1 und es ist di, 1 [0] -~-- 1

(vgl. Abb. 1). In [-- 1 - b ~ , + 1] ffir beliebig festes ~, 0 < ~ < 1 ist To, o[f]----0,

es gibt nur 2 A]ternantenpunkte , also ist T1, 1 If] :~ O und f in diesem Interval l normal.

Es sind verschiedene l~ormalitgtskriterien angegeben worden, so yon LoEB [1964] und MEIZqA]~DUS [19649], W]S~NER [1963]. Das besonders einfache hinreichende Kr i te r ium yon LoEB sei hier erwiihnt:

Normalit~itskriterium: Die Funkt ion f ( x ) ist in I dann (l, r)-normaI, wenn die Funkt ionen 1, x , x 2, . . . , x L~ , 1 �9 f (x ) , x �9 f (x) , . . . , x r-'~ �9 f (x ) ffir alle natfirlichen Zahlen d ~ r ein TSC~EBYSCI~EFF-System bilden.

Man zeigt leicht, dab folgende Definition mit der obigen i~quivalent ist.

Definition 2: Die Funk t ion f (x) ist in I genau dann (l, r)-normal, wenn

'q~,r [1] < ~-1, ,-1 [f] (1.6)

ist. (Fiir ~h,-1 [f] ist dabei ~ zu setzen). Den Vorschlag, yon dieser Definition auszugehen, machte gespr~ehs-

weise G. ~/[EINARDUS. Bei normalen Funkt ionen besteht jede Alternante aus n -~ 2 Punk ten

des Intervalles, welche der Gr61]e Bach angeordnet seien. Diese Punk te fassen wir zu Vektoren X : ---- (x0 . . . . . x~+l) zusammen.

Allgemein definieren wir

: = ( Y l Y - - (Yo . . . . , Y~+l) mi t reellen Yi und

~Y0 > Y l < . . . < Y~+~ ~f l} . (1.7)

Im Zusammenhang mit der ]3ildung des Differenzenquotienten

A n f : = ~ , ~ i f (x i ) (1.8) i=0

t re ten wiederholt die Koeffizienten

,~i : -~ I I ( x i - - xj) -1 (1.9)

auf. Ihre Vorzeichen sind dutch sgn 2i ~- (-- 1) "+i gegeben.

38 H. VCE~EI~ :

2. S t e t igke i t s e igenscha f t en

Ohne jede zusgtzliche Voraussetzung kann m~n die Stetigkeit yon ~lt, r fiir stetige Funkt ionen f (x) beweisen. Es gilt

Satz 2.1 :

l~Tz,~[f]--~]t,~[g][~l[f --gH ffir bel. f ,g~C[:c, fi]. (2.1)

Bewei8 :

~][ f ] -= ] ! T [ f ] - - f ; ~ l •11T [g] -- f [L < i ! T [ g ] - - g [ L + H g - f i L - =

= ~ ] [ g ] + I lg-- f l [ und wegen der Symmetr ie in f u n d g folgt die Behauptung. (Die Indizes l, r sind hier und des 5fteren bei den folgendea Beweisen unterdriickt.)

Setzt man Norm~litgt voraus, so erhglt man foigende einfaehe Konse- quenzen :

Lemma 2,1: Sei f (x) e Nz, ~ und R e ~t, ~ mit II f -- R II < ~?~-1, ~-1 [f]. Dann ist R nieht ausgeartet , d .h . dr, ~ [ R ] - - 0 .

Beweis: klar.

Als unmit te lbare Folgerung ergibt sich

Lemma 2.2: Is t f (x) ~ N~, ~ und gilt

1 ] ! f - g II < - ~ (71~-1, r--1 [f] -- ~]~, ,-[f]), (2.2)

so ist g (x) ebenfalls (/, r)-normal.

Beweis: Mit dem Satz 2.1 ist

I] T [g] - - f [I <~7[g]-[- I l f - -g < 7 1 [ f J + 2 H f - g H < ~Iz-~,~-~[f],

so dab die Behaup tung aus Lemm~ 2.1 folgt. Die Menge der normalen Funkt ionen, so deuten CHE~NEu und LOEB [1964]

dieses Ergebnis, ist in C [m, fl] often. Sie beweisen augerdem, dag die Menge der normalen Funkt ionen in C [m, fl] dicht ist, indem sie zeigen, dab man jede nicht normale Funkt ion beliebig genau durch normale Funkt ionen approximieren kann.

Fiir die nachfolgenden Bet rachtungen ist es bequem, eine Bezeiehnung fiir die Menge derjenigen rat ionalen Funkt ionen zu h~ben, die ,frost" TSCHmBYSCHmFF-Approximierende sind.

Definition 2,1: Es sei ~j~ [ f J : = { R / R e ~ z , ~, i l f - - R iL ~c} .

Bei W E ~ [1962] war die Menge der zugehSrigen Koeffizienten mit M~ bezeichnet worden, wobei noeh eine Normierungsbedingung zugrunde- gelegt wurde, d~ die rationale Funk t ion die Koeffizienten nicht eindeutig best immt. Dem Hilfssatz 7.2 der genannten Arbeit en tn immt man

Lemma 2.3: S e i f (x) e N~, ~. Zu beliebigem ~ > 0 existiert c > ~ , ~ [f], so dag J] R 1 - - R ~ I} ~ ~ fiir beliebige Funkt ionen R1, R~ ~ ~ gilt.

Die Bedeutung der Normalit/~t bei rationaler Tschebyscheff-Approximation 39

Diesem Lemma kommt durchaus praktische Bedeutung zu, denn es besagt in qualitativer Form, dab zwei ,gute' Approximationen R1 und R~ yon f, d. h. zwei rationale Funktionen, die sieh yon f nur um wenig mehr als ~,~, r [f] unterscheiden, auch voneinander nicht sehr verschieden sind.

Man kann sich durch Beispiele leicht davon fiberzeugen, dab die Aussage des Lemmas nieht mehr richtig ist, wenn f (x) nicht normal ist.

Man mag schlie61ieh insbesondere nach dem Falle fragen, dal3 R1 und R2 die T-Approximationen zweier nur wenig verschiedener Funktionen aus C [~, fl] sind.

Diese Situation wird beherrscht yon

Satz 2.2: Sei f (x) ~ 2V~, r u 91t, ~. In diesem und nur in diesem Falle h//ngt Tt, 1. If] an der Stelle f stetig im Sinne der Norm des Raumes C [~, #] yon f (x ) ab.

Der Beweis dieses Satzes geht zuriiek auf Beitr//ge yon MA~RLY- WITZGALL [1960], CIliarY-LOEB [1964] und W ~ R [1964]. Aul~erdem verallgemeinerten CHE~r165 [1965] und CtIE~u [1967] dieses Resultat. Es soll hier nur ein Beweis ffir eine quantitative Versch//rfung einer Teilaussage des Satzes 2.2 gegeben werden. Vorauszuschicken sind zwei Lemmata:

Lemma 2.4: Sei f (x) ~ Nt, ~ und ~ < ~-~, ~-1 [f]. Dann existiert k(c) > 0 , so dab Iq(x) l>~k(c)" ]lqII ffir alle Nenner q(x) gilt, die zu Funktionen R ~ g2~ gehSren.

Beweis: Gemt~ft der in 1. getroffenen Vereinbarung sei die Darstellung

der im folgenden auftretenden rationalen Funktionen R = ~P so gew//hit, q

dal~ II q 11 = 1. GehSren die Funktionen R zu Yk~, so sind sie gleiehm//l~ig beschrt~nkt und es folgt IIP I[ <~ K (c), eine nur yon c abht~ngige Schranke. Angenommen, das Lemma sei falseh. Dann kann man eine Folge rationaler

Funktionen R~ = P ~ aus g2~ finden, fiir die qi

lira rain Iqi (x ) [= 0. (2.3) i ---~ s o

Man darf naeh eventueller Auswahi einer Teilfolge annehmen, dal3 Pi (x) und qi (x) gleiehm/~13ig konvergieren, die Grenzfunktionen mSgen p (x) und q(x) heiBen. Wegen ][q~(x) l l= 1, ist ]lq(x) l l = l , also q ( x ) ~ o , andererseits besitzt q (x) aufgrund der gleichm/~13igen Konvergenz und (2.3) in I mindestens eine Nullstelle.

In allen Punkten x ~ I, wo q (x) 4= 0, gilt wegen der gleiehm//Bigen Konvergenz

I P (~) [ q(~) f (x) - w ( x ) ~ < c .

Daraus folgt, dal3 alle Singularit~ten yon p (x)/q (x) in I hebbar sind und insbesondere, dai3 p (x) und q (x) eine gemeinsame Nullstelle haben. I)er Quotient p (x)/q (x) repriisentiert also eine ausgeartete Funktion in ~ . Unter den fiber c gemachten Voraussetzungen ist dies ein Widerspruch zu Lemma 2.1.

40 H. WEENEE:

Bemerkung: Man kann k (c) kons t rukt iv beschreiben durch

lc (c): ~- inf (minlq (x)[) (2.4) q x e I

p (x) for jedes q (x) mit ]1 q ![ --~ 1, zu dem ein p (x) existiert, so daL~ - q ~ - ~ ~ .

Bei I~r165 [1960], S. 144--145, findet man, mit anderem Beweis, das

Lemma 2.5: Es sei X ein fester Vektor yon ~ . Dann gibt es eine Zahl m, abh~ngig yon den Komponen ten xi, mit folgender Eigenschaft : Is t P (x) irgendein Po lynom n-ten Grades und gilt

P ( x i ) . ( - - 1) ~ + z ~ 0 fiir i = 0 . . . . . n + 1, (2.5)

so bes teht dis Absch~itzung

I1 P (x) II ~< m �9 z. ( 2 . 6 )

Beweis: Durch Anwenden des (n + 1)-ten Differenzenquotienten auf P (x) erh~lt man

n+l

O = d(~+l) P = ~ ~ p , Pi : = P (xi), analog Pi, qi usw. i=0

Daraus folgt

i 4= j i : ~ j

fiir j = 0, 1 . . . . , n- l - 1. (2.7)

Man erhiflt also fiir I P (xj) 1 eine Schranke der Form m l . z , wobei m~ nur yon der Lage der P u n k t e x~ abh~ngt. Da P (x) dureh Interpola t ion

n §

nach LAGRANGE in der Form P (x) -- ~ w i (x) �9 P (xi) mit den bekannten i=1

dureh wi (xj)== 6~j (KRoNEOKER-Symbol) definierten Polynomen w i (x) darstel lbar ist, so folgt die Behauptung.

Es l~l~t sich nun leieht die L~escHiTzstetigkeit der rutionMen T-Ap- proximat ion T~, r [f] beweisen.

Satz 2.3: Is t f (x)E N~, ~, so gibt es MI , so dal~

II T~,r If] - - Tz,~ [g] [I < My �9 I I f - - g I! fiir alle g e C [~, fi] (2.8) giltL

Beweis: (Fiir den SpeziMfall der Po lynome sei auf I~CE [1964] ver- 1

wiesen.) Man w~hle eine feste Zahl ~ mit 0 ( ~ < ~ (~]~_~, ~_~[f]-- ~]~, ~[f]).

Es sei nun g ~ C [~, fi] eine beliebige Funkt ion. Dann werden 2 Fs unter- schieden.

1 Fi i r verMlgemeiner te ra t ionale F u n k t i o n e n vergleiche m a n ~uch C~r,~EY [1965].

Die Bedeutung der Normalit/it bei rat, ionaler Tschebyscheff-Approximation 41

a) [ r f - - g H ~ 0. Dann gilt

T [f] -- T [g] ]l ~<~7[ f ]+ I ] f - - g l i q - ~ 7 [ g ] , also

~< 2 (~7 [f] + N f - - g I[) 1lath Satz 2.1

~ < 2 { ~ / ] § " I f f - -g l l .

b) ! ] f - - g I] < d. Daraus folgt nach Satz 2.1, daft die Funkt ion T [g] i n 9X~ m i t c : = ~7 If] + 2 d enthal ten ist. Nach Lemma 2.1 ist g also normal.

8 Setzt man T [f] = p~ sowie T [9] = t - und normiert in der angegebenen q Weise, so gilt q (x) >~ k (c), t (x) ~> k (c) in I nach L e m m a 2.4. Es sei X Alternante yon f u n d T [f]. Ferner sei etwa e (Xo) = f (x0) -- T [f] (x0) > 0. Dann gilt ~7i: = wi " ei = (-- 1) i �9 *7 If] ffir i - 0 . . . . . n -+ 1. Setzt man weiter ~ (x) : - : f (x) -- T [g] (x), so ist mit Satz 2.1

(-- 1) ' . $,.w, ~<ll~(x) l] ~<r][g]~- ] l f - g l l ~<~7[f]+211f--g[I -

- - ( - - 1 ) i " Wi " Ei ~- 2 [ I f - - g [I, (2 .9 )

also

0 ~ ( - - 1) ~ w~ (~ -- ~,) + 2 I I f - - g II. (2.10)

]s t v = rain w (x), so folgt aus der letzten Ungleichung I

0 ~< (-- 1) ~ �9 (qi 8i - - P i t i ) @ 2 �9 V - 3 �9 I l l - - ~ ]l fiir i = O, . . . , n -~ 1.

Wendet man auf das Polynom q (x) . s ( x ) - - p (x) . t (x) Lemma 2.5 an, so folgt

w ( x ) . ] q ( x ) . s ( x ) - - p ( x ) . t ( x ) i < ~ m . I I f - -g l ] . (2.11) Wegen

l I T [ f ] - - T[g]l] ~<max{q(~( . t ) (x ) ] s ( x ) . q ( x ) - - p ( x ) . t ( x ) l (2.12)

~<k(c) - z . m . H f - g l l

ist also auch in diesem Falle die behauptete Abschgtzung nachgewiesen.

Das Maximum der beiden Faktoren 2 (1 + ~7 ~1~7) und k (c) - 2 . m gibt t J

einen Koeffizienten M s.

3. Lokale Konvergenz des Remes-Algorithmus Der bekannte R~MEs-Algorithmus ffir Polynome (siehe etwa M~I~CAR-

DVS [1964], S. 98ff., oder W E R ~ R [1966], 21, 22), ist yon verschiedenen Autoren auf rationale Funkt ionen iibertragen worden, WET~ERLI~O [ 1961], W E ~ I ~ [1961], HART und FRASER [1962] und STOER [1964]. Es wird angenommen, daft der Leser mi t dem Verfahren als solchem ver t raut ist.

Daft bei der Anwendung Schwierigkeiten auftreten k6nnen, ist bekannt . Man kann zu rat ionalen Funkt ionen kommen, die im Approximations- intervall Pole haben, man kann auf entar te te Funkt ionen stoften, so dab nicht geniigend viele Punk te ffir den Ausgleich vorhanden sind.

42 H. WERNEB:

Andererseits wird man Konvergenz vermuten, wenn Mle wghrend der Iteration auftretenden rationalen Funktionen in einem Bereich ~ liegen, in dem keine Funktion entarten kann.

RALSTON [1965] teilte einen Satz mit, wonaeh die Konvergenz des gEMEs-Algorithmus far normMe Funktionen gewghrleistet ist, wenn man mit einer hinreichend guten Approximation beginnt. Der Beweis yon RALSTOn ist sehwer naehzuvollziehen, da im Beweis seines Lemma 2 gewisse Fglle nieht berfieksiehtigt sind. Es sell deshalb hier ein vollstgndiger Beweis mit den ffir rationale Approximationen bekannten an~lytisehen Hilfsmitteln angegeben werden. Die Konvergenz erweist sieh ohne zusgtzliehe Voraussetzungen als (mindestens) linear. Unter Differenzierbarkeitsvoraus- setzungen fiber f (x) und w (x) war bereits friiher (vgl. WERN~ [1962]) quadratisehe Konvergenz bewiesen worden. Dabei war es nieht einmM notwendig, die Abweiehungsgleiehung exakt zu 15sen. Man konnte sieh vielmehr auf die dureh das N~WTO~sehe Verfahren gegebene Lineari- sierung besehr/~nken.

Gegeben sei die stetige Funktion f ( x ) ~ N~, T. Bezeiehne ~ die Menge der Alternanten X = (x 0 . . . . . x~+0, n = l@ r, die f ( x ) besitze. Die Menge ~ ist abgesehlossen. Y bezeichne in dieser Untersuehung stets einen Vektor yon ~. Den Abstand zweier Vektoren Y, Z yon ~3 definiere man durch II Y -- Z II: = max ly~ - zjl. Dann sei

i

0(d): : { Y I Y e ~ 3 , ? X e ~ m it I ! X - - Y I I < 0}. (3.1)

0ber d wird spgter noeh verfiigt. T (x) : = T~, r [f] (x) ist voraussetzungs- gemi/g eine nieht ausgeartete Funktion yon }R~, r.

Bei jedem Schritt des g~M~s-Algorithmus hat man eine diskrete stetige T-Approximierende zu ermitteln. Mit den in WER~Ea [1966] benutzten Bezeichnungen ist folgende Aufgabe zu 15sen.

Zu gegebenem Y = (Y0, . . . , Y,.~+I)~ ~3 ist ,~ (Y) und R (x)e 9l~, ,~ so zu bestimmen, daft

( - 1)~ fiir j = 0 , 1 . . . . , n-E- i (3.2) R j = f j + ~ l ( g ) . g , g~:-- ~ ,

Rj: = R (yj) usw.

gilt und dab R (x) in [Y0, Y~+~] keinen Pol besitzt. Die Zahl V (Y) migt, yore Vorzeiehen abgesehen, die gewichtete Ab-

weiehung zwisehen R und f in den Punkten der l~eferenz Y. Sie genfigt der dureh

~5 (~], y) = det (A + ~ �9 B) =- 0 (3.3)

mit den (r ~- 1-reihigen, quadratisehen, symmetrisehen Matrizen

A : ~- ((ctik)), B : = ((bi~)), aik : = /]n~l (yi+~ . f ) , bi~: = A~+~ (y~+~ . g)

gegebenen Abweiehungsgleiehung. Ffir Y~ ~ nimmt I,~ (Y)I sein Maximum ~'h,~ If] an. Es kann sein,

dab es X ~ ~ gibt, ffir die ~ (X) posit ivist (ihre Menge sei Ee) und andere X mit negativem V (X) (2~-= ~ - ~+). Man denke etwa, daft n ~-3

Die Bedeutung der Normalitgt, bei rat ionaler Tsohebysoheff-Approximation 43

Punk te mit den Eigensehaften A 1 und A 2 yon 1. existieren, bei Weg- lassen des ersten bzw. letzten Punktes erhglt man ein X aus ~+, ein zweites aUS ~--.

Zu ~ (Y) bes t immt sich aus (3.2) die Funkt ion R(x). Fiir Y-= X erhglt man T (x). Die Funkt ion ~b (~], Y) ist ein Polynom in ~. Die Wurzel ,7 (X) yon (3.3) ist einfaeh, da T (x) nieht ausgeartet ist (WEI~lgER [1963], Satz 2.3).

Also ist ~ ~ ('~' y) " . O. ~r/ / Y = x

Die Koeffizienten des Polynoms sind stetige Funkt ionen yon Y, wie man der angegebenen Form der aik und b~k entnimmt.

Naeh einem Satz fiber implizite Funkt ionen existiert f f r jedes feste X e ~ und ein hinreiehend kleines 6x > 0 eine stetige AuflSsungsfunkt ion. 77 (Y) der Gleiehung (3.3) fiir [I Y -- X [] < 6x. Naeh dem HEINE-BoREL- sehen 1)berdeekungssatz, angewendet auf ~, kann man also ein 6 so finden, daft die AuflSsung in der Menge 0 (6) stetig und eindeutig ist. Die Auf- 15sung von (3.2) lglR sich nach W]~RNER [1963] auf die LSsung des Eigen- wertproblems, naeh der Bereehnung yon ~2 (Y) also auf die LSsung eines homogenen Gleiehungssystems bzw. eine rationale Interpolat ion

( A - ~ , 7 . B) b = 0, b = (3.4)

zurfiekf~hren.

Die b 0 . . . . . b r sind bis auf einen Normierungsfaktor die Koeffizienten des Nenners q (x) yon R (x), q (x) = (b 0 q- bl x q- . . . q- br x r) �9 const.

Da q (x) ffir Y = X, d .h . fiir die T-Approximierende in I nicht ver- schwindet, kann man aus Stetigkeitsgriinden 6 so klein gew//hlt annehmen, daft ffir jedes Y e 0 (6) das aus (3.4) resultierende Polynom q (x) in I nicht verschwindet und dab es sogar eine Kons tan te z > 0 gibt, mit der fiir jeden solchen Nenner q (x) in I die Ungleichung q (x) >~ ~ gilt (11 q II =- 1).

Diese l~Tberlegungen lassen sich zusammenfassen zu

Lemma 3.1: Sei f ( , ) e Nz, ,.. Dann gibt es eine Umgebung 0 (6) yon in ~ , so dab ftir jede Referenz Y e 0 (6) das stetige, diskrete T-Approxi-

mationsproblem 15sbar ist und die resultierende Approximat ionsfunkt ion R (x) nieht ausgeartet ist. Der Nenner q (x) jeder solchen rat ionalen Funk t ion R (x) genfigt im Interval l I din" Ungleichung q (x) ~> x mit yon Y und R unabhgngigem, positivem ~.

Es ist nun das Verhalten yon 7 7 (Y) ffir nicht in 0 (~) liegende Punk te Y e !~ zu studieren. Allgemeiner werden di~ Werte der Fehlerfunkt ion bei Vorgabe einer beliebigen rationalen Funk t ion R (x) an den Stellen betraehtet , die durch die Komponen ten yj eines Vektors Y e ~ gegeben sind, genauer gesagt sell ~ j : = (Rj--fj)/g~ diskutiert werden. Es wird also jetzt da rauf verzichtet, daft die ~]j alle gleich sind.

44 H. W E ~ :

Lemma 3.2: Sei f e N~,,.. Zu jedem positiven b gibt es eine positive Zahl K < ~h,r[f] , SO dab aus Y ~ 2 , R~{R~,~, polfrei in [Y0, Y~+I] und min~Tj >~K oder max~b ~ < - - K folgt Y ~ 0 ( 8 ) .

i Anders formuliert :

sup rain (R (yj) -- f (y~)) �9 w (yj) (-- 1) j ~< g < ~h, ~ [f] Y , R j

mit YE~3, Y~.0(b) , Re{R~,~, R stetig in [Y0, Y~+I]. Analoges gilt fiir die Maxima.

Zusatz: Gibt es zu Y ~ 2 , Y ~ 0 ( d ) ein ~(Y) und eine in [Y0, Y,~+I] stetige, diskrete T-Approximation, so ist !7.1 (Y) I ~ K.

Dieser Zusatz ist eine unmit te lbare Konsequenz yon Lemma 3.2, denn im Falle der diskreten T-Approximation sind alle ,]j gleich.

Bewei8 yon Lemma 3.2." Die Punkte , in denen If (x) -- T (x) l �9 w (x) -- = r]~, ~ [f] ist, lassen sich zu endlieh vielen abgeschlossenen Mengen I i yon I zusammenfassen, so dab fiir Mle x ~ I j der Ausdruek (f (x) -- T (x)) gleiehes Vorzeiehen hat und aul~erdem far Mle x e 1~. und y e Ij+l mit j = 1 . . . . , Z - 1 die Relat ion x < y besteht.

Die endlieh vielen I j haben untereinander einen positiven Abstand, er sei grSfJer als 3 8. Mit 0j (6) seien alle Punk te x von I bezeichnet, deren Abstand yon IJ kleiner als ~ is t . Es bleibt eine abgeschlossene Restmenge yon dem Interval l I iibrig, wenn man I - <3 0~ (~) bildet, sie sei mi t 00 (~) bezeiehnet. (Im folgenden darf j also yon 0 his Z laufen.)

Es gibt nun eine endliehe Anzahl yon Kombinat ionen yon (n + 2) Indizes (J0 . . . . . J~+l), so dag jede Menge von n + 2 Punk ten x k e I1~, k = j0, �9 . . , j,~+l mit J0 < �9 �9 �9 < J ,+l sine Alternante X bestimmt. Eine solehe Menge von n + 2 Indizes heil~e Alternantenindexmenge.

Die Komponenten Yk eines Vektors Y aus 0 (8) liegen in Mengen 0j~ (b), k = 0, . . . , n + 1, v o n d e r Art, dal~ (Jo, �9 �9 -, J,,+l) eine Alternanten- indexmenge ist.

Ein Vektor Y, der nicht in 0 (8) liegt, zeiehnet sich daduroh aus, dal~ seine Komponenten in Mengen 0J0 (6), . . . , 0j~+l (6) liegen, ftir welche

(j0, . . . , J,,+l) keine Alternantenindexmenge ist. Sei fortan J : = (J0 . . . . . J~+l) eine Nieht-Alternantenindexmenge.

~]//j sei die Abschliel~ung der Vereinigungsmenge der 0~o . . . . . 0 j ~ + . Dureh diese Absehliel]ung werden keine Extrem~ der (durch (1.5) definierten) Fehlerkurve zur Vereinigungsmenge hinzu genommen.

T (x) ist nieht ausgeartet und approximiert f (x) anf 1 mit der Giite 'It, ~ If]. Auf M j ist aber T (x) keine beste Approximation yon f (x), da es dort keine Alternante gibt. Also kann eine rationale Funkt ion R(a) ~{Rz,~ konstruier t werden (vgl. etw~ ACI~IESER [1963], S. 55ff.), welehe f in M j besser approximiert als T (x) und wie T (x) in g~nz I stetig ist.

Sei K j = max lR(J) (x) -- f (x)! �9 w (x), dann gilt naeh Konst rukt ion M j

K j < W,~ [f].

Die Bedeubung der Norm~litii~ bei r~tion~ler Tschebyscheff-Approximation 45

Dann ha t K : ~ max K j (genommen fiber die endlieh vielen Nicht- Al te rnanten indexmengen) die in L e m m a 3.2 angegebenen Eigensehaften. I s t n~mlieh Y ~ 0 (5), so bes t immen die K o m p o n e n t e n y~ e 0j~ (5) eine

Nich t -Al te rnanten indexmenge J . Sei R (x) die be t rach te te ra t ionale Funkt ion , stetig in [Yo, Y.+~]. Mit der oben zur Indexmenge J kons t ru ier ten ra t ionalen Funk t ion R(J) (x) gilt

(R (Yk) -- R(J) (Yk))/gk ~-- (R (Yk) -- fk) /g~ -- (R(J) (Y~) -- f~)/gk >~ >~ (R (Yk) -- f~)/gk -- K j ffir k = 0, . . . , n ~- 1. (3.4)

Da die Differenz R ( x ) - R(J) (x) nicht in allen P u n k t e n y~ das Vor- zeichen ( - - 1 ) k besitzen kann, so gibt es wenigstens ein k, fiir welches die linke Seite yon (3.4) nicht p o s i t i v i s t , for dieses ]C gilt

~ ~ (R (Yk) --fi~)/gk ~ K j <~ K, (3.5)

analog zeigt ma n die Exis tenz eines m mit ~/~ _> -- K j , was zu zeigen war.

Lemma 3.3: Gegeben sei Y c ~ und R (x)~ 91z, ~ stetig in [Yo, Y~+~]. Is t Vk : ~ (R (Yk) --fk)/g~r ~ K fiir ]C -- 0, . . . , n -~ 1 erffillt und gibt es eine diskrete, in [Y0, Y~+~] stetige T-Approx imat ion beziiglich der lgefe- renz Y, so gilt ffir die result ierende Abweichung ~7 (Y) ebenfalls ~] (Y) ~ K. (Das entspreehende gilt fiir ~1~ ~ -- K.)

Beweis : trivial.

Le m ma 3.4: Sei R ( x ) - - p(x) und q(x) >~z > 0 . Gibt es fiir jede q (x) Referenz Y mit m i n c e ~ K > 0 bzw. max~/~ ~ - - K < 0 eine diskrete, stetige T-Approximierende, deren Nenner auch der eben genannten Un- gleichung genfigt, und gilt fiir jede derar t ige Referenz y~.+~ - - yj ~ ~ > 0, so ist

II R - - f II ~ ~ , ~ I f ] -~ (3 .6)

~- (n -~ 1) �9 (fl - ~)~+1 . ~ -2 . 5 - . - 2 . ( m i n w (x)) -3 �9 { w , ~ I f ] - K } .

Beweis: Die Fehler funkt ion (R (x) -- f (x)) w (x) nehme in z e I d e m Bet rage naeh das Maximum II R - - f II an. Dann kann man naeh dem bekann ten STInF~Lsehen Austausehalgor i thmus durch Erse tzen eines Yk aus Y, der I ndex sei ]co, eine neue Referenz Z ---- (% . . . . . zk+l) gewinnen. Fiir diese Referenz gilt dann ebenfalls rain ~ ~ K bzw. m ax Vk ~ -- K und der Abs tand z~+~ -- z~ der K o m p o n e n t e n yon Z ist nieht kleiner als 5. Naeh Voraussetzung ist s tet iger diskreter T-Ausgleich mSglich, das Er-

gebnis sei s(x) _ S (x). Nach Voraussetzung ist t (x) ~ z. Sei e twa t (x) (Z) > 0, sonst k6nnte man - - f (x) s ta r t f (x) approximieren.

Bildet man bezfiglich Z den (n-]- 1)-ten Differenzquot ienten

0 -~ zl "+~ (p �9 t - - ' q �9 s) : ~) ,~ �9 q~ �9 t~ (R~ -- S~) (3.7)

= ( - Z ] [ �9 �9 - v ( z ) ) ,

zieht den Term mit dem Index k ~ ]c o heraus, beaehte t w ( x ) . q (x) Ilql] : 1, w(x) . t ( x ) ~ H t I l = 1 und berficksichtigt ~I(Z) ~]g ,~[ f ] ,

46 H. WERNER:

so finder man

(H R - - f II -- 7~, ~[/]) �9 (fi -- ~)-~-* �9 ~2~<~1~kl �9 wk -I �9 qk �9 t~ (7 (Z) -- ~ ) /c q: k ,

~< 6 - ' - 1 �9 (rain w (z)) -s �9 (n 4- 1) , {'~z, ,~ [f] -- K}, (3.8)

wie behaupte t wurde. Nach diesen Vorbereitungen kann in wenigen Schrit ten gezeigt werden,

dab der REMES-Algorithmus bei hinreichend guter Ausgangsngherung R ffir jede Funkt ion f (x) e Art, ~ konvergiert.

Sei 2~ die Alternantenmenge von f (x) bei Approximationen in ~ , ~. Zungchst werde 6~ gleich einem Drittel des Minimalabstandes der im

Beweis yon L e m m a 3.2 eingefiihrten Mengen Ij, j > 0, gesetzt und nach Lemma 3.1 ein (3 ~ 6~ gewghlt. Gleichzeitig erhglt man damit die Nenner- schranke z. Lemma 3.2 en tn immt man die Kons tan te K.

Nun sei R(~ (x) eine Ausgangsngherung zur T-Approximation, die in einer Referenz y(o) die Ungleichungen

7j(0) : = (Rj(0) - - L ) / g ~ > K oder ~ -- K (3.9)

erfiillt. Naeh Lemma 3.2 liegt y(o) in 0 (6). Naeh der Best immung yon 6 ~< d~

gilt fiir den Abstand y}~l--yj(~ die untere Sehranke 6. Lemma 3.1 garant ier t die M6gliehkeit des diskreten stetigen T-Ausgleichs fiir die Referenz y(o), naeh Lemma 3.3 ist [7 (Y(~ ~>K und man erhglt eine neue Approximation RO) (z). Die Maxima und Minima yon (Ro) - - f ) �9 w ergeben eine neue Referenz yo) , die zugeh6rigen Abweiehungen r/j(1) geniigen (3.9). Dami t sind ffir RO)(z) und y(x) die gleiehen Voraus- setzungen wie fiir die Ausgangsn/iherung und y(o) gegeben und die I tera t ion kann jedenfalls unbesehr/~nkt oft ausgeffihrt werden. Man erhglt eine Folge y(k).

Welter folgt aus Lemma 3.3, dag I)?(Y(k))l monoton wgehst. Da It/(Y(~))I ~< ~,,~ [f] = ~ (X), so konvergiert die Folge der i7 (Y(~))I.

Um die Konvergenz der R(k) (x) gegen T (x) zu beweisen, verfghrt man wie bei der Aufstellung yon (3.8). Star t R werde R(~) (x) eingesetzt. Tauscht man simultan aus und nicht nu t eine Stiitzstelle, so kann ~ (Y) nur vergrSBert werden. Man erhglt

(!1 R('~) - - f l l - ~ , ~ [ f ] ) �9 (~ - - ~ ) - '~ -~ �9 z.~ ~< &'~-~ �9 (n + 1 ) .

m a x ( w -a (x)) �9 { i'] (Y(~:+l)) 1 - - [7 (Y(~)) [ }. (3.10)

Die rechte Seite strebt gegen Null. Also konvergiert [I R(~")--f II gegen rh, ~ [f]. Nach Lemma 2..3 folgt daraus die gleichm/iBige Konvergenz von R(~) (x) gegen T (x).

Damit ist der folgende Sachverhalt bewiesen:

Konvergenzsatz: Geht man beim rationMen REMEs-Algorithmus zur Bes t immung der T-Approximation yon f (x) yon einer Referenz aus, die hinreichend nahe bei einer Alternante liegt (oder yon einer hinreiehend

Die Bedeutung der Normalit~t bei rationaler Tschebyscheff-Approximation 47

guten Ausgangsn/iherung, die eine derartige Referenz bestimmt), so kon- vergiert der Proze$.

Zweifellos w/ire es wiinschenswert, einen kOrzeren Beweis zu geben. Die Komplikationen stammen jedoch vor allen Dingen yon der Tatsache her, dab man fiber die Alternantenmenge .~ sehr wenig Information hat. Der Beweis wird wesentlich einfacher, wenn man weiB, dab es zu f (x) eine eindeutig bestimmte Alternante gibt.

Die lineare Konvergenz yon IV (Y(~))I gegen ~h,r[f] kann man leicht mit Hilfe von (3.7) folgern, wenn man far R und S zwei aufeinander- folgende N/iherungen R(") und R(~+ ~) der T-Approximierenden eintr/igt.

Wie bei Polynomen (vgl. WhalER [1966]) findet man

W , ~ [ / ] - tv(Y('))I ~ 1 [ f l _ ~ ) n + 2 "minwa(x)"

4. Diskret is ierung zur Berechnung der T-Approximierenden

Bei der Berechnung der T-Approximierenden wird man in vielen F/illen nicht das ganze Intervall numerisch erfassen k6nnen, sondern gezwungen sein, mit einer diskreten Punktmenge zu arbeiten. Bei rationaler Approxi- mation sind dabei gewisse Gefahren erkennbar.

Approximiert man etwa auf [ - -1 , ~-1] eine Funktion f (x), die in 1

0 < 6 ~ l x l ~ 1 mit x~- fibereinstimmt und auf dem fehlenden StOck

stetig erg/inzt ist, mit Funktionen aus ,~o,2 und w/ihlt man das Raster M 1

so, dab es keinen Punkt mit lx I < 5 enth/ilt, so w/ire ~ - die beste L6sung

auf M. Zweifellos ist dies wegen des Poles bei x - 0 keine gute Approxi- mation yon f (x) im ganzen Intervall. Au$erdem sieht man, dab es in diesem Falle keine L6sung des diskreten T-Approximationsproblems auf dem Raster M geben wird, die gleichzeitig im ganzen Intervall [-- 1, ~- 1 ] stetig ist.

Die Aufgabe ~ i , ein R o zu bestimmen, for welches

,max ] R o - f l ~ m a x i R - - f l fiir alle in I stetigen R E ~ z , r gilt, M M

braucht nicht 16sbar zu sein. Diese Schwierigkeit kann indes fiir normale Funktionen nur bei zu grobem Raster eintreten.

Zun/ichst gelingt es uns nachzuweisen, dab eine positive Schranke c5 o for die Rasterweite existiert, die sicherstellt, dab man die Nenner der diskreten Approximationen unter Kontrolle halten kann.

Definition 4.1 : Ein Raster M i s t feiner als 6, wenn in jeclem Teilintervall der L/inge c~ von I wenigstens ein Rasterpunkt liegt.

Mit dieser Definition und Hf (x) HM: = suplf (x) �9 w (x) l gilt x e M

Lemma 4,1: Sei f (x) ~N~, r. Dann gibt es zu jedem c < ~z-1, ~-~ [f] ein c~, so dab for jedes Raster M, feiner als c~, und for jede Funktion

48 H.~u

R = p~ + {Rz mit [I R -- , f IIM ~ C gilt q .,9"

1 ~lq(x)! > ~ �9 liq I1" k(c) fiir alle x e I ,

mit der aus Lemma 2.4 ermittelten Zahl k (c).

Beweis: Man kann sich wieder auf die Betraehtung soleher Darstel- lungen der rationalen Funktionen besehrgnken, die dureh H q I] = 1 normiert sind. Diese 5[enner sind Polynome hSchstens r-ten Grades und wegen der gleiehmgltigen Beschrgnktheit gleiehgradig stetig. Man kann also 81 so bestimmen, dal~ fiir jeden derartigen Nenner q (x) die Schwankung

1 in einem Intervall der Lgnge ~1 hSehstens ~ k (c) betr/igt.

Es geniigt nun ein ~ ~< ~l zu finden, dab fiir jedes Raster M, feiner als 8, auf M selbst die Ungleiehung

3 [q (x)! > 4

gewghrleistet ist. Angenommen, es ggbe kein solches 8. Dann hgtte man eine Nullfolge ~,~, zugehSrige Raster M mund rationale Funktionen R,~ (x), sowie xm E M~ (m = 1, 2, 3 . . . . ) mit folgenden Eigenschaften:

a) M,~ ist feiner als ~,~.

b) II f -- Rm !IM,~ <~ c. 3

B i n - - Il l[ = l, l q A x , , ) ! < . k (c).

Man kann aus den Folgen p .... qm (wegen der gleichmgl~igen Besehrgnkt- heir dieser Polynome) auf I gleiehmgl~ig konvergente Teilfolgen mit den Grenzfunktionen p (x), q (x) herausziehen. Es konvergieren, gegebenenfalls naeh erneuter Auswahl, aueh die Punkte x m + x0. Wir diirfen annehmen, die Folgen selbst seien bereits konvergent.

Wegen a) ist jeder Punkt y e I Grenzwert einer Folge von Punkten y,, mit y~ ~ M+,~ (m = 1, 2 . . . . ).

Mit b) folgt daraus wegen der gleichmgBigen Konvergenz der Polynome p,~: (x), q~ (x) gegen p (x), q (x) die Absehs

w(x) lq (x ) . f ( z ) - p ( x ) l <~ c . lq(x) l u n d ferner IIq(x) l l= 1.

Es sind zwei F/ille zu unterseheiden:

1. I q(x)] > 0 i n ' I . Dann liegt R ( x ) - - p(x) in ~)~ und es gilt q (x) ]q (xo) l>~ k (c), im Widerspruch zu der aus a), b) und c) folgenden Aus-

3 sage l q (x0) I <~ ~- te (c).

2. Es gibt Nullstellen yon q (x) in 1. Dann lassen sieh p (x) und q (x) so oft durch gemeinsame Faktoren kfirzen, bis schlie61ich zwei teilerfremde Polynome fibrig bleiben, die eine zu ~ gehSrende ausgeartete rationale Funktion darstellen. Dies ist nach Wahl yon c unmSglieh.

Die Bedeu~ung der NormaliViit bei r a t i ona l e r T s c h e b y s c h e f f - A p p r o x i m a t i o n 49

Damit ist die obige Annahme widerlegt. Es mul3 also ein ~ mit den gesuchten Eigenschaften geben.

Definiert man den Stetigkeitsmodul einer stetigen Funktion f (x) in I durch

~o (h) : = sup If (x) -- f (Y) I fat, x, y ~ I, Ix - - Y l ~< h,

so gilt

Lemma 4.2:

Voraussetzungen :

1. S e i f (x) ~ Nt, ~ und babe ebenso wie w (x) einen durch co (h) majori- sierten Stetigkeitsmodul.

2. Gem/tB Lemma 4.1 werde 5 zu c < ~?~-1, ~-1 [f] gew/thlt, es sei auBer- dem kleiner als der 2 (l ~- 1)te Tell der Intervallitnge ( f l - ~).

Behauptung:

Dann liiftt sich fiir alle rationalen Funktionen yon ~z,~ mit II R - - f ]l~+ ~< c, wobei M ein beliebiges Raster feiner als ~ sein darf, eine gleichmi~l~ige Majorante g2 (h) fiir die Stetigkeitsmoduln angeben mit der Eigenschaft .(2 (h) --~ 0 fiir h -+ 0.

Beweis :

Ist M feiner als b, so gilt nach Lemma 4.1 fiir die Nenner aller der genannten Ungleichung geniigenden rationalen Funktionen R in I eine

Abseh/~tzung ] q (x) l ~> 1 k (c). Naeh der obigen zus/itzlichen Bestimmung

enth/ilt M aul3erdem l q-1 Punkte, die vonein~nder wenigstens um [ f l - ~]/(2 l + 2) entfernt sind. Man erh/~lt damit die MSglichkeit einer gleichmgftigen Absch/~tzung fiir die Z/~hlerpolynome der zul/~ssigen ratio- nalen Funktionen aus II R -- f IIM ~ c, da II q II --- 1. Also sind die ratio- nalen Funktionen gleichgradig stetig. Dies ist mit der obigen Behauptung gleichbedeutend und beweist das Lemma.

Mit Hilfe dieser Lemmata erhglt man leicht folgende Aussage, die einen bei Rich [1964] fiir Polynome ausgesproebenen Satz verallgemeinert.

S a t z 4 . 1 :

Voraussetzungen :

1. Sei f (x)~ N~, ~. Die Funktionen f (x) und w (x) m5gen durch co (h) majorisierte Stetigkeitsmoduln haben.

2. Zu c < ~?z-l,r-1 If] werde ~0 gem/tit Lemma 4.1 und Lemma 4.2 gew/ihlt.

3. Y2 (h) sei die in Lemma 4.2 konstruierte Majorante fiir den Stetig- keitsmodul einer jeden rationalen Funktion R (x)~ ~t, ~, die der Un- gleiehung IL f - R [[M ~ C mit M feiner als 6 o geniigt.

Computing 2/1 4

50 H . W ~ N E a :

B e h a u p t u n g :

Z u j e d e m R a s t e r M feiner als 5 ~< 5 0 g ib t es eine bes te A p p r o x i m i e - r ende R M a u f M y o n f (x) u n d es gil t

]1 R M - - T z , ~ [f] I[ ~ K �9 (~ (5) § ~9 (5))

m i t e inem n u r y o n f (x)~ l, r , lc (c), d e m I n t e r v a l l I u n d w (x) a b h s K oe f f i z i en t en K .

B e w e i s :

Zun/~chst is t die E x i s t e n z der A p p r o x i m i e r e n d e n RM a u f M zu s ichern. Ste l l t m a n das E x t r e m a l p r o b l e m ~ i , so is t T~, ~ [ f ] eine zul/~ssige Ver- g le ichs funkt ion . M a n b r a u c h t also n u r R e ~ , ~ m i t I[ R - - f JIM ~< V~, ~ [f] zu b e t r a c h t e n . N a c h L e m m a 4.1 l iegen die N e n n e r dieser r a t i o n a l e n F u n k - t i onen zwischen p o s i t i v e n Grenzen . E s is t de sha lb o h n e Schwier igke i t fiir dieses y o n endl ich v ie len P a r a m e t e r n abh/ /ngige P r o b l e m mSglich, die E x i s t e n z y o n RM als G r e n z e l e m e n t e iner Minim~lfo lge zu zeigeD.

M a n k a n n n u n f a s t wie im Fa l l e y o n P o l y n o m e n wei te r fo lgern . Sei n s x ein be l ieb iger P u n k t aus I . Es soll die Di f fe renz v o n R M (x)

u n d f ( x ) abgesch / i t z t werden . (Es we rde R (x) s t a r t RM (x) geschr ieben . ) H a t das R a s t e r M die F e i n h e i t 5, so g ib t es e inen R a s t e r p u n k t y , dessen

A b s t a n d y o n x k le iner als 5 ist. M a n erh/ i l t u n t e r t~enu tzung der L e m m ~ t a u n d V o r a u s s e t z u n g e n

w ( x ) I f (x) - - R (x) I ~<

~< w (x ) I f (x) - f (y)[ -~ w (x) lR (x) - - R (y)[ § l w (x) - - w (Y) I �9

�9 If (Y) - - R (y) i § w (y) If (y) - - R (y) [

m (5) -t- ~9 (5) § o) (5) �9 ~ , r [f] §

-]- W,~ [ f ] A ~- W, ~ [f] ,

wenYl

A : = (1 + ~ , ~ [f]) �9 (o) (5) + Q (5))

gese tz t wird. M a n w e n d e t diese U n g l e i c h u n g a u f (n + 2) A l t e r n g n t e n - p u n k t e x 0 . . . . , x~+ 1 an, in d e n e n

�9 ( - - 1) ~ . w (x~) �9 ( f ( x i ) - - T [f] (x~)) = )h,~ [f]

m i t y o n i u n a b h i i n g i g e m ~ ~ + 1 oder - - 1 gilt.

E s fo lg t

�9 ( - - 1) * �9 w (x~) ( T [ f ] (xi) - - R (x~)) =- ~ ( - - 1) ~ . w (x~) ( f ( x~ ) - - R (x~)) - -

- - a �9 ( - - 1) I w (x,) �9 ( f (xi) - - T [f] (xi))

<~ A + W,r [ f ] - - V,, , [ f] = A.

N i m m t m a n an, d a b T [f] (x) - - '~ (x) p (x) t(x) u n d R ( x ) - - q(x) ' so e rh~l t

Die Bedeutung d.er Normalit/~t bei rat ionaler Tschebyscheff-Approximation 51

man aus der letzten Absch/itzung

( - - l ) i " (8 (X i ) " q (X i ) - - t (X i ) �9 p ( X i ) ) ~ A �9 I[ q II ~ l i t I] 1 w(x~)~ ~ ~ ~ ' A

ffir i = 0, . . . , n ~ - 1.

Nach L e m m a 2.5 gilt demnach mit einer nur yon den x~ abhgngenden Zahl m

und

2 1 ' . ( l + ~ h , I f ] ) " I} R (x) T [ f ] (x)I] ~ - ~ Q ~ - �9 m �9 ~ T r

�9 (~ (6) ~- .O (8)) ffir 6 ~ 80,

wie behaupte t wurde.

Man darf auf Grund dieses Satzes beim praktischen Rechnen also das Interval l durch ein Raster M ersetzen. Is t das Raster rein genug, so unterseheiden sich T~, r If] u n d RM (x) nur wenig, falls f (x) normal ist. Leider ist es nicht leicht, eine numerische Aussage fiber 6o zu erhalten.

Immerh in kann man a posteriori nach Berechnung eines RM (x) prfifen, w i e w e l t I I f ( x ) - - R u (X)[I den Wer t II f (x) - - RM (x)IIM fiberschreitet. Zwischen beiden liegt ~h, r If], und darauf kommt es in den Anwendungen meist an.

Dag die Normali t~t ffir den vorangegangenen Satz wesentlich ist, zeigt wieder das Beispiel von 1.

1 Es werde f (x) : x 2 -- ~- in [-- 1, ~ 1] mi t w (x) = 1 durch gebrochen-

lineare Funkt ionen approximiert . Die beste Approximation ist offenbar R (x) = 0.

Nun wi/hle man ein 8 mit ~1 > 6 > 0 und approximiere zun//chst in [-- 1 + d, 1] die Funk t ion f (x). Sie ist dort normal und die Approximation ha t ffir alle 6 quali tat iv die in der Figur 1 angegebene Gestalt. Es sind 4 Al ternantenpunkte vorhanden. Durch Hinzunahme weiterer Punkte in (-- 1 @ 8, 1) kann man daraus ein Raster der Feinhei t d herstellen. Ffir 6 - + 0 streben die Werte der Approximat ionen RM (1) im Punkte x = 1 gegen -~ 1, wiihrend T~, ~ If] in diesen, wie in allen anderen Punkten , den Wef t Null besitzt. Die diskreten Approximationen RM konvergieren also nicht gegen T1, 1 If]. Es strebt aber immerhin IIf - - RM [1 ffir 6 --~ 0

1 gegen U1,1 [f] -- 2"

Die Aussagen dieses Abschnit ts lassen sich weitgehend auf verM1- gemeinerte rationale Funkt ionen iibertragen, vgl. W~R~ER [1967].

Literatur

[1953] AC~a~ES]~R, N. I. : Vorlesungen fiber Approximationstheorie. Akademie-Verlag Berlin (1953). Englische Auflage: Theory of Approximation. Frederick Ungar Publishing Co, New York (1956).

4*

52 I-~. WEt'~NER: Die Bedeutung der Normali ta t bei Tsehebyscheff-Approximation

[1965] CHENEY, E.W.: Approximation by generalized rational functions. Page I01--ii0 in Approximation of functions ed. by H. L. GA~BEDIAN, Amster- dam Elsevier Publ. Co. (1965).

[1964] CHE~rEY~ E . W . and H. L. LOEB: Gerteralized Rat ional Approximations, J. Siam, Numer. Anal. 1, 11--25 (1964).

[1966] C~E~EY~ E. W. and H. L. LOEB: On the Continuity of Rat ional Approxi- mat ion Operators. Arch. Rational Mech. Anal. 21, 391--401 (1966).

[1962] I-IA~:, J. F. and W. F~ASE~: On the computation of rational approximations to continuous functions. Comm. ACM 5, 401--403 (1962).

[1964] LOEB, H. L.: Rational Chebyshev approximation. Notices AMS 1 l, S. 335 (1964).

[1960] MAEttLY, H. J. und Ch. WITZCALL: Tsehebyscheff-Approximationen in kleinen Intervallen. I. Approximation durch Polynome. Num. Math. 2~ 142 -- 150 (1960).

[1964] MEI~AI~I)~s, G.: Approximation von Ftmktionen und ihre numerisehe Be- handlung. Springer Verlag, Berlin-Gdttingen-Heidelberg (1964).

[1964a] MEI~AI~DI:S, G.: Pr ivate Mitteilung (1964). [1965] RALSToN, A.: Rational Chebyshev-Approximation b y Remes-Algorithms.

Num. Math. 7~ 322--330 (1965). [1964] RICE, J . R . : The Approximation of Functiolls. Vol. I -- Linear Theory.

Addison Wesley Publishing Company, Reading Massachusetts-Pale Alto- London (1964).

[1959] STIE~EL, E.: i3ber diskrete und lineare Tschebyscheff.Approximationen. Num. Math. L 1--28 (1959).

[1964] S~OEI~, J. : A direct method for Chebyshev approximation by rat ional time- tions. J. ACM 11~ 59--69 (1964).

[1961] W ~ E ~ , H . : Bemerkungen zur Tsehebyscheffschen Approximation mit rat ionalen Funktionen. ZAMM 4L T 67--68 (1961).

[1962] WER~Ea, H. : Die konstruktive Ermit t lung der Tschebyseheff-Approxi- mierenden im Bereich der rationalen Funktionen. Arch. Rational Mech. Anal. 11, 368--384 (1962).

[1963] W E ~ E R , H. : Rationale Tsehebyscheff-Approximation, Eigenwerttheorie und DiffererLzenrechnung. Arch. Rat ional Mech. Anal. 13, 330--347 (1963).

[1964] WEI~NER, n . " Oil the rational Tschebyscheff-Operator. Math. Zeitschr. 86, 317--326 (1964).

[1966] WE~NE~,H.: Vorlesung fiber Approximationstheorie. Lecture Notes in Mathematics, Bd. 14, Springer Verlag, Berlin-Heidelberg-New York, (1966).

[1967] W E ~ E R , H. : I)iskretisierung bei Tschebyseheff-Approximation mit verall- gemeinerten rationalen Funktionen. Erscheint demn~chst.

[1961] WE~E~r , I~G,W. : Zur Anwendung des Newtonsehen Verfahrens bei der numerisehen Behandlung der Tschebyseheff-Approximation. ZAMM 41, T 68, (1961).

Pro/. Dr. Helmut Werner 46 Mi~nster i. W., Besselweg 8