Teorie aproximace

V matematice , teorie aproximace týká toho, jak funkce lze aproximovat pomocí jednodušších funkcí , dávat kvantitativní charakterizaci těchto chyb zavedených těchto aproximací.

Problematický

Problém aproximace vznikl velmi brzy v geometrii u trigonometrických funkcí : jedná se o funkce, jejichž vlastnosti známe (parita, derivovatelnost, hodnoty v konkrétních bodech), ale které nejsou vyjádřeny z d ' operací, které lze provádět ručně ( čtyři operace ). To vedlo ke konceptu sériového vývoje . Byli jsme tedy schopni vytvořit trigonometrické tabulky , pak s podobným přístupem logaritmické tabulky a obecně tabulky pro funkce běžně používané ve vědě, jako je druhá odmocnina .

Obzvláště zajímavým problémem je aproximace funkcí jinými definovanými pouze ze základních počítačových operací , jako je sčítání a násobení, aby se vytvořily knihovny matematických funkcí, které zase produkují hodnoty, které se co nejvíce blíží teoretickým hodnotám . Toto se nazývá polynomiální nebo racionální aproximace (tj. Racionálními funkcemi ).

Cílem je poskytnout co přesné přiblížení jak je to možné z dané reálné funkce, tak, aby poskytovaly co nejpřesnější možné hodnoty, k přesnému blízko k pohyblivou řádovou čárkou aritmetiky jednoho počítače . Tohoto cíle je dosaženo použitím polynomu vysokého stupně a / nebo zmenšením domény, nad kterou musí polynom aproximovat funkci. Redukci domény lze často provést, i když to vyžaduje složení dalších afinních funkcí , aby byla funkce aproximována. Moderní matematické knihovny často zmenšují doménu rozdělením na několik malých segmentů a na každém segmentu používají polynom nízkého stupně.

Jakmile je vybrána doména a stupeň polynomu, je zvolen samotný polynom, aby se minimalizovala chyba v nejhorším případě. Jinými slovy, je-li $f$ skutečná funkce a $P$ polynom, který se musí přiblížit $f$ , musíme minimalizovat horní mez funkce v doméně. Pro "vhodnou" funkci je optimální polynom stupně $N$ charakterizován chybovou křivkou, jejíž hodnota osciluje mezi $+$ $ε$ a $-$ $ε$ a která mění znaménko $N$ $+$ 1krát, což znamená chybu v nejhorších případech $ε$ . Je možné sestrojit funkce $f,$ pro které tato vlastnost neplatí, ale v praxi je to obecně pravda. ${\ displaystyle | Pf |}$

Chyba mezi optimálním polynomem stupně 4 a přirozeným logaritmem $ln$ (červeně) a mezi Čebyševovou aproximací $ln$ (modře) v intervalu [2, 4]. Vertikální krok je 10 −5 . Maximální chyba pro optimální polynom je 6,07 × 10 −5 .
Chyba mezi optimálním polynomem stupně 4 a exponenciálním $e$ (červeně) a mezi Čebyševovou aproximací a $exp$ (modře) v intervalu [-1,1]. Vertikální krok je 10 −4 . Maximální chyba pro optimální polynom je 5,47 × 10 −4 .

V každém případě je počet extrémů $N + 2,$ tj. 6. Dva extrémy jsou konce segmentu. Křivky červené, pro optimální polynom, jsou „rovné“, to znamená, že přesně oscilují mezi $+ ε$ a $- ε$ . Pokud polynom stupně $N$ vede k chybové funkci, která osciluje mezi extrémy $N +$ 2krát, pak je tento polynom optimální.

Aproximace polynomy

Státy

Nechť $f$ je spojitá funkce v uzavřeném reálném intervalu $[ a , b ]$ . Nechť $P$ je polynom stupně $n$ .

Zaznamenáváme chybu aproximace mezi $P$ a $f$ . ${\ displaystyle \ varepsilon = Pf}$

Pokud existuje a tak ${\ displaystyle a \ leq x_ {0} <x_ {1} <\ cdots <x_ {n + 1} \ leq b}$ ${\ displaystyle s \ in \ {- 1, \; 1 \}}$

{\ displaystyle \ forall i \ in \ {0, \ ldots, n + 1 \}, \ varepsilon (x_ {i}) = (- 1) ^ {i} s \ | Pf \ | _ {\ infty}}

pak $P$ je optimální aproximační polynom $f$ z polynomů stupně menšího nebo rovného $n$ ve smyslu sup normy na $[ a , b ]$ :

{\ displaystyle P = \ operatorname {arg} \ min _ {Q \ in \ mathbb {R} _ {n} [X]} \ | fS \ | _ {\ infty, [a, b]}}

Demonstrace

Začněme tím, že to ukážeme v grafu. Pojďme pózovat . Předpokládejme, že jde o polynom stupně, který má výše uvedené vlastnosti v tom smyslu, že osciluje mezi extrémy střídavých znaků, od do . $N = 4$ $P$ $ne$ ${\ displaystyle Pf}$ $n + 2$ ${\ displaystyle + \ varepsilon}$ ${\ displaystyle - \ varepsilon}$

Chybová funkce může vypadat jako červený graf:

{\ displaystyle Pf}

${\ displaystyle Pf}$ dosáhl extrémů (z nichž dva jsou na končetinách), které mají stejnou velikost v absolutní hodnotě umístěné v 6 intervalech na grafu výše. $n + 2$

Nechť je nyní aproximační polynom optimálního stupně . To znamená, že extrémy její chybové funkce musí mít absolutní hodnotu striktně menší než , aby byly umístěny striktně uvnitř grafu chyby pro . $Q$ $ne$ $\ varepsilon$ $P$

Chybová funkce pro může mít grafické znázornění připomínající modrý graf výše. To znamená, že musí oscilovat mezi přísně kladnými a přísně zápornými nenulovými čísly celkem . Ale rovná se, což je polynom stupně . Musí mít alespoň kořeny umístěné mezi různými body, ve kterých polynomiální funkce přebírá nenulové hodnoty. V integrálním kruhu však nenulový polynom stupně nemůže mít více kořenů. Totéž je tedy identicky nula, to znamená . $Q$ ${\ displaystyle (Pf) - (Qf)}$ ${\ displaystyle N + 2}$ ${\ displaystyle (Pf) - (Qf)}$ ${\ displaystyle PQ}$ $ne$ $n + 1$ $ne$ $ne$ ${\ displaystyle PQ}$ $P = Q$

Čebyševova aproximace

Je možné získat polynomy velmi blízké optimálnímu polynomu rozšířením dané funkce o Čebyševovy polynomy a následným snížením expanze do určité míry. Tento proces je podobný rozšíření Fourierovy řady funkcí ve Fourierově analýze , ale místo obvyklých trigonometrických funkcí používá Čebyševovy polynomy .

Vypočítáme koeficienty v Čebyševově expanzi funkce $f$ :

{\ displaystyle f (x) \ simeq \ sum _ {n = 0} ^ {\ infty} c_ {n} T_ {n} (x)}

z nichž ponecháme pouze prvních $N$ členů řady, což dává polynom stupně $N$ blížící se funkci $f$ .

Důvod, proč je tento polynom téměř optimální, je ten, že u funkcí připouštějících expanzi v celočíselných řadách, jejichž řada má rychlou konvergenci, je chyba způsobená expanzí po $N$ termínech přibližně stejná jako termín bezprostředně následující za řezem. To znamená, že první člen těsně po řezu dominuje součtu všech následujících termínů nazývaných zbytek série. Tento výsledek zůstává, pokud je expanze provedena pomocí Čebyševových polynomů. Pokud je Čebyševova expanze přerušena po $T N$ , pak bude chyba blízká termínu v $T N + 1$ . Čebyševovy polynomy mají tu vlastnost, že mají reprezentativní křivku „na úrovni“, která osciluje mezi +1 a -1 v intervalu [-1,1]. $T n + 1$ a $n + 2$ extrémy . To znamená, že chyba mezi $f$ a jeho Čebyševovou aproximací k členu v $T n$ je funkce mající $n + 2$ extrémy, jejichž maxima (respektive minima) jsou stejná, a je tedy blízká optimálnímu polynomu stupně $n$ .

V grafických příkladech výše vidíme, že chybová funkce zobrazená modře je někdy lepší (pokud zůstane níže) než funkce zobrazená červeně, ale v určitých intervalech horší, což znamená, že to není zcela optimální polynom. Tento rozdíl je relativně méně důležitý pro exponenciální funkci , jejíž celá řada konverguje velmi rychle, než pro logaritmickou funkci .

Čebyševovy systémy

Tato část a následující vycházejí hlavně z děl Cheneyho a Powella.

Je možné zobecnit charakterizaci „nejlepší aproximace“ s prostory aproximačních funkcí, které nejsou polynomy, ale standardními funkcemi. Takové rodiny funkcí však musí mít určité dobré vlastnosti, které polynomy mají. Mluvíme pak o „zobecněných polynomech“. Tyto „polynomy“ budou mít základní funkce (které považujeme za příjemné) jako monomily, které splňují Haarovy podmínky.

Haarovy podmínky

Rodina funkcí intervalu v splňuje Haarovy podmínky tehdy a jen tehdy ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \}}$ $[a, b]$ $\ mathbb {R}$

Všechny funkce jsou spojité. $g_ {i}$
Funkce splňují následující ekvivalentní podmínky: G1,...,Gne{\ displaystyle g_ {1}, \ tečky, g_ {n}} ${\ displaystyle g_ {1}, \ tečky, g_ {n}}$
1. Pro všechny odlišné ${\ displaystyle x_ {1}, \ tečky, x_ {n} \ v [a, b]}$ ${\ displaystyle \ left | {\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} ( x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right | \ neq 0}$
2. Pro všechny odlišné, pro všechny existuje jedinečná n-tice , která funkci splňuje ${\ displaystyle x_ {1}, \ tečky, x_ {n} \ v [a, b]}$ ${\ displaystyle y_ {1}, \ tečky, y_ {n}}$ ${\ displaystyle (\ alpha _ {1}, \ tečky, \ alpha _ {n})}$ ${\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}$ ${\ displaystyle \ forall i \ in \ {1, \ tečky, n \} \ quad f (x_ {i}) = y_ {i}}$
3. Funkce jsou lineárně nezávislé a je to jedinečná funkce formy, která má přísně více kořenů ${\ displaystyle g_ {1}, \ tečky, g_ {n}}$ ${\ displaystyle x \ mapsto 0}$ ${\ displaystyle x \ mapsto \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x)}$ $n-1$ $[a, b]$

Konečná rodina funkcí vyhovujících Haarovým podmínkám se nazývá Čebyševův systém. Je zřejmé, že monomály se zmenšeným stupněm tvoří Čebyševův systém: polynomy jsou spojité, podmínka 2.1 je determinant Vandermonde , podmínka 2.2 je charakterizace interpolačního polynomu a podmínka 2.3 je skutečnost, že polynom stálého stupně nemůže mít více kořenů než jeho stupeň. ${\ displaystyle g_ {1}, \ tečky, g_ {n} \ v {\ mathcal {C}} ([a, b])}$ ${\ displaystyle \ {1, X, \ tečky X ^ {n-1} \}}$

Můžeme také říci, subprostorový z kót splňuje podmínky Haar tehdy a jen tehdy, pokud jeho základy jsou Čebyševovy systémy. $E$ ${\ displaystyle {\ mathcal {C}} ([a, b])}$ $ne$

Rovnocennost charakterizací

Důkaz rovnocennosti bodů 2.1, 2.2 a 2.3 bude proveden kruhovými implikacemi.

2,1 ⇒ 2,2 Zvažte odlišné a . Hypotézou 2.1 si všimneme zejména toho, že matice ${\ displaystyle x_ {1}, \ tečky, x_ {n} \ v [a, b]}$ ${\ displaystyle y_ {1}, \ tečky, y_ {n} \ in \ mathbb {R}}$

{\ displaystyle M: ​​= \ left ({\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right)}

je invertibilní. Existuje tedy jedinečné řešení rovnice Nebo tato poslední rovnice odpovídá . Přijde tedy existence a jedinečnost n-tice tak, že interpoluje $y$ $i$ v $x$ $i$ . ${\ displaystyle M \ cdot (a_ {1}, \ tečky, a_ {n}) ^ {T} = (y_ {1}, \ tečky, y_ {n}) ^ {T}}$ ${\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ sum _ {j = 1} ^ {n} a_ {j} g_ {j} (x_ {i}) = y_ {i }}$ ${\ displaystyle (\ alpha _ {1}, \ tečky, \ alpha _ {n})}$ ${\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}$

2.2 ⇒ 2.3 Nulová funkce má jasně striktně více než $n$ $- 1$ kořenů mezi $a$ a $b$ , protože je má nekonečno. Pojďme nyní mít $n$ odlišných kořenů, jak je uvedeno . Funkce null a $f$ se v těchto bodech shodují. Vlastností 2.2 tedy máme $f$ $= 0$ . Z toho dále vyplývá, že $g$ $i$ jsou lineárně nezávislé, pokud by neexistovalo dvojí psaní funkce null, což předpoklad 2.2 zakazuje. ${\ displaystyle x \ mapsto 0}$ ${\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}$ $x_ {1}, \ tečky, x_ {n}$

2,3 ⇒ 2,1 Nechte se odlišit. Předpokládejme, že matice není invertibilní. Pak jsou jeho sloupce lineárně závislé, a proto existuje takový . Pak jsou kořeny, které jsou tedy nulové vlastností 2.3. Vždy se touto vlastností, vyplývá podle nezávislost $g$ $i$ , že což je absurdní. Matice je tedy invertibilní a její determinant je proto nenulový. ${\ displaystyle x_ {1}, \ tečky, x_ {n} \ v [a, b]}$ ${\ displaystyle M: = \ left ({\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right)}$ ${\ displaystyle \ alpha _ {1}, \ tečky, \ alpha _ {n}}$ ${\ displaystyle \ forall j \ in \ {1, \ dots, n \} \ quad \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x_ {j}) = 0 }$ $x_ {1}, \ tečky, x_ {n}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}$ ${\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ alpha _ {i} = 0}$

Příklady

Můžeme uvést dva příklady Čebyševových systémů:

Pokud jsou dva na dva odlišné, pak tvoří systém Čebyšev na libovolném kompaktním intervalu . ${\ displaystyle \ lambda _ {1}, \ tečky, \ lambda _ {n}}$ ${\ displaystyle \ {\ mathrm {e} ^ {\ lambda _ {1} x}, \ tečky, \ mathrm {e} ^ {\ lambda _ {n} x} \}}$ $\ mathbb {R}$
Pokud jsou dva na dva odlišné a pozitivní, pak tvoří systém Čebyšev zapnutý pro kompaktní interval . ${\ displaystyle \ lambda _ {1}, \ tečky, \ lambda _ {n}}$ ${\ displaystyle \ {x ^ {\ lambda _ {1}}, \ tečky, x ^ {\ lambda _ {n}} \}}$ $\ mathbb {R}$

Alternační věta

Čebyševovy systémy umožňují charakterizovat nejlepší aproximace spojitých funkcí jako zobecněné polynomy sestavené z funkcí zmíněného systému.

Státy

Zvažte systém Čebyšev. Nechť je spojitá funkce. Dovolit být zobecněný polynom nad Čebyševovým systémem a aproximační chyba. Pak je nejlepší jednotný aproximace , která je , právě tehdy, když existuje taková, že i ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}$ ${\ displaystyle f \ in {\ mathcal {C}} ([a, b])}$ ${\ displaystyle p ^ {*} = \ součet _ {i = 1} ^ {n} \ alpha _ {i} ^ {*} g_ {i}}$ ${\ displaystyle r ^ {*} = fp ^ {*}}$ ${\ displaystyle p ^ {*}}$ $F$ ${\ displaystyle \ | r ^ {*} \ | _ {\ infty} = \ min _ {p \ in {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})} {\ | fp \ | _ {\ infty}}}$ ${\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}$ ${\ displaystyle r (x_ {i}) = (- 1) ^ {i} r (x_ {0})}$ ${\ displaystyle r (x_ {0}) = \ pm \ | r \ | _ {\ infty}}$

Poznámka

Je zajímavé si povšimnout, že pokud uvažovaný Čebyševův systém je kanonickým základem, pak je toto tvrzení přesně takové jako věta v případě polynomů. ${\ displaystyle \ mathbb {R} _ {n-1} [X]}$

Důkaz alternační věty

Věta o charakterizaci

První věcí, kterou musíte udělat, je charakterizovat nejlepší aproximace pomocí zobecněných polynomů. Můžeme začít tím, že ukážeme, že stačí, aby počátek prostoru byl v určité konvexní obálce. U systému Čebyšev si povšimneme . ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \}}$ ${\ displaystyle {\ hat {x}} = (g_ {1} (x), \ tečky, g_ {n} (x)) ^ {T}}$

Zvažte systém Čebyšev. Nechť je spojitá funkce. Dovolit být zobecněný polynom nad Čebyševovým systémem a aproximační chyba. Pak $r$ je minimální normy právě tehdy, když 0 je v konvexním trupu . ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}$ ${\ displaystyle f \ in {\ mathcal {C}} ([a, b])}$ ${\ displaystyle p = \ sum _ {i = 1} ^ {n} \ alpha _ {i} ^ {*} g_ {i}}$ ${\ displaystyle r = fp}$ ${\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \}}$

Demonstrace Dostatečný stav

Postupujme kontraposivně a předpokládejme, že to není minimální. Pak je možné najít zobecněný polynom, který splňuje lepší aproximační chybu. Jinými slovy, existují například . ${\ displaystyle \ | r \ | _ {\ infty}}$ ${\ displaystyle d = (d_ {1}, \ tečky, d_ {n})}$ ${\ displaystyle \ left \ | \ sum _ {i = 1} ^ {n} (\ alpha _ {i} ^ {*} - d_ {i}) g_ {i} \ right \ | _ {\ infty} < \ | r \ | _ {\ infty}}$

Pojďme pózovat . Takže za všechno, co máme ${\ displaystyle X = \ {x \ v [a, b] \ | \ | r (x) | = \ | r \ | _ {\ infty} \}}$ $x \ v X$

{\ displaystyle \ left | r (x) - \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq \ left \ | r- \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} \ right \ | _ {\ infty} = \ left \ | \ sum _ {i = 1} ^ {n} (\ alpha _ {i} ^ { *} - d_ {i}) g_ {i} \ right \ | _ {\ infty} <\ | r \ | _ {\ infty} = | r (x) |}

Vyrovnáním členů nerovnosti

{\ displaystyle \ left (r (x) - \ součet _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} <r (x) ^ {2} }

Poté vývojem

{\ displaystyle 2r (x) \ součet _ {i = 1} ^ {n} d_ {i} g_ {i} (x)> \ left (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2}}

{\ displaystyle \ langle d, r (x) {\ hat {x}} \ rangle = r (x) \ součet _ {i = 1} ^ {n} d_ {i} g_ {i} (x)> 0 }

Nyní tedy jde o to ukázat, že 0 není v konvexní obálce , což je podmnožina , a my pak dokážeme kontrapozici. Předpokládejme tedy opak. Existuje a takové, že a . Tak ${\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ v X \}}$ $\ mathbb {R} ^ {n}$ $x_1, \ dots, x_n \ v X$ ${\ displaystyle a_ {1}, \ tečky a_ {n} \ v [0,1]}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} r (x_ {i}) {\ hat {x_ {i}}} = 0}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} = 1}$

{\ displaystyle 0 = \ left \ langle {d, 0} \ right \ rangle = \ left \ langle {d, \ sum _ {i = 1} ^ {n} a_ {i} r (x_ {i}) { \ hat {x_ {i}}}} \ right \ rangle = \ sum _ {i = 1} ^ {n} a_ {i} \ langle {d, r (x_ {i}) {\ hat {x_ {i }}}} \ rangle> 0}

To je samozřejmě absurdní, CQFD.

Požadovaný stav

Rovněž postupujeme kontrapozicí. Předpokládejme tedy, že 0 není v konvexní obálce $C$ množiny . $C$ je uzavřeno, protože se jedná o konvexní obálku. Je omezený, protože „je. Ve skutečnosti $r$ a $g$ $i$ jsou spojité a $X$ je obsaženo v omezeném intervalu. $C$ je proto uzavřeno ohraničené v konečné dimenzi (obsažené v ), je tedy kompaktní. Tak dosahuje minima na $C$ , řekněme v . Zejména . Buď svévolné a buď . Konvexitou . Pak ${\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \} = \ {r (x) {\ hat {x}} \ | \ x \ v X \}}$ ${\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \}}$ $\ mathbb {R} ^ {n}$ $\ | \ cdot \ | _ {2}$ ${\ displaystyle d \ v C}$ ${\ displaystyle d \ neq 0}$ ${\ displaystyle u \ v C}$ $\ lambda \ v [0,1]$ ${\ displaystyle \ lambda u + (1- \ lambda) d \ v C}$

{\ displaystyle {\ begin {zarovnáno} \ | {\ lambda u + (1- \ lambda) d} \ | _ {2} ^ {2} & \ geq & \ | {d} \ | _ {2} ^ {2} \\\ | {\ lambda u + (1- \ lambda) d} \ | _ {2} ^ {2} - \ | {d} \ | _ {2} ^ {2} & \ geq & 0 \\ \ lambda ^ {2} \ | {ud} \ | _ {2} ^ {2} +2 \ lambda \ langle {ud, d} \ rangle & \ geq & 0 \ end {zarovnáno}}}

Pro dostatečně malé je však tato nerovnost porušena . Takže . Takže pro všechny , . $X$ je uzavřený obsažený v $C$ , takže je také kompaktní. Pro plynulost $r$ i $g$ $i$ , připouští minimální . Za to, co musíme udělat . Poznámka . Poté budeme hledat takové , které budou uzavřeny. Pojďme nyní pózovat . Podle definice . Pokud jde o ostatní, $Y$ je stále kompaktní. Nechť $R je$ tedy maximum $|$ $r$ $|$ na $Y$ . Pokud ne, pak máme maximum, pak spokojeni , což je absurdní. Takže pokud , $\ lambda$ ${\ displaystyle \ langle {ud, d} \ rangle <0}$ ${\ displaystyle \ langle {ud, d} \ rangle \ geq 0}$ ${\ displaystyle u \ v C}$ ${\ displaystyle \ langle {u, d} \ rangle = \ langle {ud, d} \ rangle + \ | {d} \ | _ {2} ^ {2} \ geq \ | {d} \ | _ {2 } ^ {2}> 0}$ ${\ displaystyle \ {\ langle {d, r (x) {\ hat {x}}} \ rangle \ | \ x \ v X \}}$ $\ epsilon$ $\ epsilon> 0$ ${\ displaystyle d = (d_ {1}, \ tečky, d_ {n}) ^ {T}}$ $\ mu> 0$ ${\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}$ ${\ displaystyle Y = \ left \ {x \ in [a, b]] \ | \ \ langle {d, r (x) {\ hat {x}}} \ rangle \ leq {\ frac {\ epsilon} { 2}} \ doprava \}}$ ${\ displaystyle Y \ cap X = \ emptyset}$ ${\ displaystyle R <\ | {r} \ | _ {\ infty}}$ $y \ v Y.$ ${\ displaystyle y \ v X}$ ${\ displaystyle x \ v Y}$

{\ displaystyle \ forall x \ in Y, \, \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq | r (x) | + \ mu \ left | \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq R + \ mu \ left \ | {\ součet _ {i = 1} ^ {n} d_ {i} g_ {i}} \ doprava \ | _ {\ infty}}

Pokud teď tedy ${\ displaystyle x \ notin Y}$

{\ displaystyle {\ begin {zarovnáno} \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | ^ {2} & = & r (x) ^ {2} -2 \ mu \ sum _ {i = 1} ^ {n} d_ {i} r (x) g_ {i} (x) + \ mu ^ {2} \ vlevo (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} -2 \ mu \ langle {d, r (x) {\ hat {x}}} \ rangle + \ mu ^ {2} \ left (\ sum _ {i = 1} ^ {n} d_ { i} g_ {i} (x) \ right) ^ {2} \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} -2 \ mu {\ frac {\ epsilon} { 2}} + \ mu ^ {2} \ left (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} & {\ textrm {car} } \ x \ notin Y \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} + \ mu \ left (- \ epsilon + \ mu \ left \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ doprava \ | _ {\ infty} ^ {2} \ doprava) \ end {zarovnáno}}}

Takže pro , máme ${\ displaystyle 0 <\ mu <\ min \ left ({\ frac {\ | {r} \ | _ {\ infty} -R} {2 \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ | _ {\ infty}}}, {\ frac {\ epsilon} {2 \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} } \ | _ {\ infty} ^ {2}}} \ vpravo)}$

{\ displaystyle {\ begin {zarovnáno} \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | & <& {\ frac {\ | {r} \ | _ {\ infty} + R} {2}} & \ quad {\ textrm {pour}} \ x \ v Y \\\ vlevo | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | ^ {2} & <& \ | {r} \ | _ {\ infty} ^ {2} - {\ frac {\ mu \ epsilon} {2}} & \ quad {\ textrm {pour}} \ x \ notin Y \ end {zarovnáno}}}

Tedy ,, a proto není minimální. ${\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}$ $r$

Alternativní lemma

Existuje souvislost mezi skutečností, že 0 je v konvexní obálce a že existuje střídání znamének.

Zvažte systém Čebyšev. Nechť a být konstanty ne . Pak 0 je v konvexním trupu if a pouze pokud pro máme . ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}$ ${\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}$ ${\ displaystyle \ lambda _ {0}, \ tečky, \ lambda _ {n} \ in \ mathbb {R} ^ {*}}$ ${\ displaystyle \ {\ lambda _ {i} {\ hat {x_ {i}}} \ | \ i \ v \ {1, \ tečky, n \} \}}$ ${\ displaystyle i \ in \ {1, \ tečky, n \}}$ ${\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}$

Důkaz lemmatu

Začněme pro determinant ${\ displaystyle x_ {1} <\ cdots <x_ {n}}$

{\ displaystyle D (x_ {1}, \ dots, x_ {n}) = \ left | {\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1 }) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right |}

Ukážeme, že všechny tyto determinanty jsou přísně pozitivní nebo všechny přísně negativní. Nejprve jsou nenulové, protože systém vyhovuje Haarovým podmínkám. Předpokládejme, že to je pro a my ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \}}$ ${\ displaystyle x_ {1} <\ cdots <x_ {n}}$ ${\ displaystyle y_ {1} <\ cdot <y_ {n}}$

{\ displaystyle D (x_ {1}, \ tečky, x_ {n}) <0 <D (y_ {1}, \ tečky, y_ {n})}

. Pak podle věty o mezilehlých hodnotách aplikovaných na máme existenci takových , která je nemožná Haarovými podmínkami. Všechny tyto determinanty tedy mají stejné znaménko.

{\ displaystyle \ lambda \ mapsto D (\ lambda x_ {1} + (1- \ lambda) y_ {1}, \ tečky, \ lambda x_ {n} + (1- \ lambda) y_ {n})}

\ lambda \ v [0,1]

{\ displaystyle D (\ lambda x_ {1} + (1- \ lambda) y_ {1}, \ tečky, \ lambda x_ {n} + (1- \ lambda) y_ {n}) = 0}

Proto je 0 v konvexní obálce if a only if there such such that and . Pokud ano . Podle Haarových podmínek však tvoří základ prostoru, a proto jsou všechny nulové, což není proto, že jejich součet se rovná 1. Proto . Podobně pro každý $i$ , . Zejména . Vyřešením tohoto lineárního systému podle Cramerových pravidel máme ${\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}$ ${\ displaystyle \ alpha _ {0}, \ tečky, \ alpha _ {n} \ v [0,1]}$ ${\ displaystyle 0 = \ součet _ {i = 0} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}}}$ ${\ displaystyle \ sum _ {i = 0} ^ {n} \ alpha _ {i} = 1}$ ${\ displaystyle \ alpha _ {0} = 0}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}} = 0}$ ${\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}$ $\ mathbb {R} ^ {n}$ $\ alpha_i$ ${\ displaystyle \ alpha _ {0} \ neq 0}$ ${\ displaystyle \ alpha _ {i} \ neq 0}$ ${\ displaystyle {\ hat {x_ {0}}} = \ součet _ {i = 1} ^ {n} {\ frac {- \ lambda _ {i} \ alpha _ {i}} {\ lambda _ {0 } \ alpha _ {0}}} {\ hat {x_ {i}}}}$

{\ displaystyle {\ frac {- \ lambda _ {i} \ alpha _ {i}} {\ lambda _ {0} \ alpha _ {0}}} = {\ frac {D (x_ {1}, \ tečky , x_ {i-1}, x_ {0}, x_ {i + 1}, \ dots, x_ {n})} {D (x_ {1}, \ dots, x_ {n})}} = {\ frac {(-1) ^ {i-1} D (x_ {0}, \ dots, x_ {i-1}, x_ {i + 1}, \ dots, x_ {n})} {D (x_ { 1}, \ tečky, x_ {n})}}}

Pak,

{\ displaystyle {\ frac {\ lambda _ {i}} {\ lambda _ {0}}} = {\ frac {(-1) ^ {i} D (x_ {0}, \ tečky, x_ {i- 1}, x_ {i + 1}, \ dots, x_ {n}) \ alpha _ {0}} {D (x_ {1}, \ dots, x_ {n}) \ alpha _ {i}}}}

Všechny determinanty jsou stejného znaménka, jsou přísně pozitivní. Takže , to znamená, že se střídají ve znamení, ani to, že za všechno , (protože nejsou nula). $\ alpha_i$ ${\ displaystyle {\ textrm {sgn}} \ lambda _ {i} = (- 1) ^ {i} {\ textrm {sgn}} \ lambda _ {0}}$ $\ lambda _ {i}$ ${\ displaystyle i \ in \ {1, \ tečky, n \}}$ ${\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}$

Důkaz alternační věty

Teď použijeme teorém a lemma, které jsme dříve prokázali, abychom dokázali alternační teorém. Bereme notace prohlášení.

Máme, že $p *$ je nejlepší aproximace $f$ pro jednotnou normu právě tehdy, když $r *$ má minimální jednotnou normu. Podle věty o charakterizaci je to pravda právě tehdy, když 0 je v konvexním trupu . Existuje tedy as tím , že to porušuje Haarovy podmínky, pokud k < n . Takže máme . I když to znamená opětovné indexování, vezmeme je ve vzestupném pořadí . Podle Haarových podmínek, jako v lemmatu, jsou všechny nenulové. Proto použijeme lemma a střídání znaménka. Jelikož jsou kladná, střídají se znamení. Tím se tedy uzavírá důkaz. ${\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ v X \}}$ ${\ displaystyle x_ {0}, \ dots, x_ {k} \ v X}$ ${\ displaystyle \ alpha _ {0}, \ dots \ alpha _ {k} \ v [0,1]}$ $k \ leq n$ ${\ displaystyle 0 = \ součet _ {i = 1} ^ {k} \ alpha _ {i} r (x_ {i}) {\ hat {x_ {i}}}}$ $k = n$ $x_ {i}$ ${\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}$ ${\ displaystyle \ alpha _ {i} r (x_ {i})}$ $\ alpha_i$ ${\ displaystyle r (x_ {i})}$

Jedinečnost nejlepší aproximace

Dosud jsme charakterizovali, jaké je nejlepší přiblížení. Nyní ukážeme, že nejlepší aproximace existuje a je jedinečná.

Státy

Zvažte systém Čebyšev. Nechť je spojitá funkce. Pak je tu jedinečná nejlepší aproximace v . ${\ displaystyle \ {g_ {1}, \ tečky, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}$ ${\ displaystyle f \ in {\ mathcal {C}} ([a, b])}$ $F$ ${\ displaystyle {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})}$

Demonstrace

Začněme s jedinečností. Takže předpokládám, že i jsou nejlepší aproximace k . Takže to máme a tento standard je minimální. Zlato pak máme . Takže je ještě lepší přiblížení. Nechť je dána alternační větou pro . Předpokládejme to . Alespoň jeden z nich tedy nestojí za to , řekněme, i když to znamená přejmenování atd . My máme $p$ $q$ $F$ ${\ displaystyle \ | {fp} \ | _ {\ infty} = \ | {fq} \ | _ {\ infty}}$ ${\ displaystyle \ left \ | {f - {\ frac {p + q} {2}}} \ right \ | _ {\ infty} \ leq \ | {fp} \ | _ {\ infty}}$ ${\ displaystyle r = {\ frac {p + q} {2}}}$ ${\ displaystyle x_ {0} <\ cdots <x_ {n}}$ $r$ ${\ Displaystyle p (x_ {i}) \ neq q (x_ {i})}$ ${\ displaystyle r (x_ {i})}$ ${\ displaystyle q (x_ {i})}$ ${\ displaystyle | f (x_ {i}) - q (x_ {i}) | <\ | {fr} \ | _ {\ infty}}$

${\ displaystyle \ | {en} \ | _ {\ infty} = | f (x_ {i}) - r (x_ {i}) | \ leq {\ frac {1} {2}} | f (x_ { i}) - p (x_ {i}) | + {\ frac {1} {2}} | f (x_ {i}) - q (x_ {i}) | <\ | {fr} \ | _ { \ infty}}$ . To je nesmysl. Takže . Takže s výraznými nulami. Podle Haarových podmínek tedy zjistíme, že je identicky nulový, a tedy to . Máme tedy jedinečnost. ${\ displaystyle r (x_ {i}) = p (x_ {i}) = q (x_ {i})}$ ${\ displaystyle pq}$ $n + 1$ $p = q$

Pojďme nyní k demonstraci existence. Zvažte . Tato sada je jasně uzavřená a omezená. Je to neprázdné, protože funkce null je in a je konečné dimenze. Takže je kompaktní. Tím, že je nepřetržitě zapnuto , tam dosáhne minima, řekněme v . Nyní, pokud je nejlepší aproximace pak trojúhelníkovou nerovností. Takže . Takže je mnohem lepší aproximace pro . ${\ displaystyle F = \ {p \ in {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n}) \ | \ \ | {p} \ | _ {\ infty} \ leq 2 \ | {f} \ | _ {\ infty} \}}$ $F$ ${\ displaystyle {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})}$ $F$ ${\ displaystyle p \ mapsto \ | {fp} \ | _ {\ infty}}$ $F$ ${\ displaystyle p ^ {*}}$ $p$ $F$ ${\ displaystyle \ | {p} \ | _ {\ infty} - \ | {f} \ | _ {\ infty} \ leq \ | {fp} \ | _ {\ infty} \ leq \ | {f} \ | _ {\ infty}}$ ${\ displaystyle p \ in F}$ ${\ displaystyle p ^ {*}}$ $F$

Podívejte se také

Tento článek je částečně nebo zcela převzat z článku s názvem „ Teorie aproximace / Demonstrace “ (viz seznam autorů ) .

Zdroje

(in) CHENEY EW, Úvod do teorie aproximace ,1966
(in) POWEL MJD, teorie a metody aproximace, Univetrsity Cambridge Press,devatenáct osmdesát jedna