 \(\begingroup\)
Mein Artikel Approximationstheorie Teil 1 vom 13.03.2005 findet mit diesem Beitrag seine Fortsetzung. Wie bereits angekündigt werden diesmal hauptsächlich beste Näherungen behandelt. Ich werde versuchen die einzelnen Sätze und Definitionen so gut es geht mit Beispielen zu illustrieren, sodaß dieser vergleichsweise trockenere Part meines Dreiteilers über Approximationstheorie etwas aufgelockert wird.
Im Folgen wird (V, norm(.)) einen normierten Vektorraum bezeichnen.
Sei T \subsetequal\ V eine Teilmenge eines normierten Vektorraumes V. Klarerweise werden wir für eine "beste Näherung" u^~ \el\ T an v \el\ V verlangen dass gilt:
\forall u \el\ T : norm(v-u^~)<=norm(v-u)
Unter dem Begriff "Proximum" werden wir in Zukunft eine "beste Näherung" verstehen.
Daher unsere erste Definition:
\black\double\frame
(Definition:)__
Sei T eine Teilmenge eines normierten Vektorraumes (V, norm(.))
u^~ \el\ T heißt Proximum an v \el\ V :<=> norm(v-u^~)= inf(u\el\T, norm(v-u))
Die Zahl E_T(v):=inf(u\el\T,norm(v-u)) heißt der Minimalabstand des Elementes v zur Teilmenge T
\frameoff
Eine kleine Bemerkung sei hier angebracht: Der triviale Fall v\el\T ist nicht ausgeschlossen => u^~:=v, norm(v-u^~)=0
Ein kleines, sehr anschauliches Beispiel:
Sei V=\IR^2 mit der euklidischen Norm und T die Einheitskugel. v=(5,5) \el\ V
\geo
x(0,7)
y(0,7)
punkt(0,0,e,hide)
pen(2)
kreis(e,3,T,nolabel)
punkt(5,5,v)
punkt(2.121,2.121,u~)
pen(1)
strecke(v,u~,,nolabel)
punkt(7,3,h)
strecke(v,h,,nolabel)
punkt(4,0.121,n,nolabel)
strecke(n,u~,,nolabel)
Pen(2)
pfeil(n,h,,nolabel)
pfeil(h,n,E_T(v))
f(T,beige)
\geooff
geoprint()
Nun stellt sich für den Mathematiker klarerweise sofort die Frage: Existiert denn so ein Proximum immer?
Diese Frage muss im allgemeinen mit Nein beantwortet werden. Zur Illustration ein typisches Gegenbeispiel:
V=(C[0,1], norm(.)_\inf), T=menge(u\el\V | u(x)=e^(\gamma*x), \gamma>0), v=f(x)=1/2
Nehmen wir an \exists \gamma^~ : u^~=e^(\gamma^~*x)
das heißt also es gilt: E_T(v)=norm(e^(\gamma^~*x)-1/2)_\inf=e^\gamma^~-1/2
wegen \gamma^~>0 gilt \exists \gamma^- : \gamma^~>\gamma^->0
=> e^\gamma^--1/2Da wir gesehen haben dass Proxima nicht existieren müssen, fragen wir uns natürlich sofort nach Bedingungen die uns deren Existenz garantieren. Hierzu führen wir den Begriff der Minimalfolge ein.
\black\double\frame
(Definition:)__
Sei (V, norm(.)) ein normierter Vektorraum und T eine Teilmenge von V.
Sei ( u_\nue ) eine Folge in T, dh u_\nue \el\ T \forall \nue \el\ \IN
( u_\nue ) heißt Minimalfolge in T für v \el\ V <=> lim(\nue->\inf,norm(v-u_\nue))=E_T(v)
\frameoff
Mit der Definition von E_T(v) folgt, dass falls T!={} => \forall v \el\ V \exists Minimalfolge
In folgendem Beispiel sieht man was leider auch passieren kann: Die Minimalfolge konvergiert gegen kein Element \el\ T
Sei V=(C[0,1], norm(.)_\inf), T=menge(u\el\C[0,1] | u(0)=0}, v=f(x)=1 \el\ V
Zuerst zeigen wir dass (u_\nue (t)):=t^\nue eine Minimalfolge ist:
E_T(v)=inf(u\el\T,norm(1-u)_\inf)= inf(u\el\T,max(x\el\[0 1],abs(1-u(x))))=1
lim(\nue->\inf,norm(1-t^\nue))_\inf=norm(1-lim(\nue->\inf,t^\nue))_\inf=norm(1-\tau(t))_\nue
\tau(t)=fdef(1,t=1;0,0<=t<1)
=max(t\el\[0 1],abs(1-\tau(t)))=1
Daraus folgt also dass t^\nue eine Minimalfolge ist. \tau(t) ist jedoch, wie man sofort sieht, nicht \el\ C[0,1]
Folgendes wichtiges Lemma wird uns Klarheit über die Bedingungen für die Existenz des Proximums verschaffen:
\blue\double\frame
(Lemma2:)__
Sei (V, norm(.)) ein normierter Vektorraum und T eine Teilmenge von V, dann gilt:
u \el\ T ist ein Häufungspunkt einer Minimalfolge ( u_\nue ) in T für v \el\ V => u ist Proximum in T an v
\frameoff
Beweis: Sei u \el\ T ein Häufungspunkt von ( u_\nue ), das heißt es existiert eine Teilfolge ( u_\nue_\mue ) die gegen u konvergiert.
\forall \epsilon \exists N' \forall \mue > N' : norm(u-u_\nue_\mue)< \epsilon
Da ( u_\nue ) eine Minimalfolge ist folgt weiters:
\forall \epsilon \exists N'' \forall \mue > N'' : norm(norm(v-u_\nue_\mue)-E_T(v))< \epsilon
Sei N:=max{N',N''}, sei \mue>N => norm(u-u_\nue_\mue)< \epsilon \and norm(norm(v-u_\nue_\mue)-E_T(v))< \epsilon
Mit Hilfe der Dreiecksungleichung kann man weiter schließen:
norm(v-u)<=norm(v-u_\nue_\mue)+norm(u_\nue_\mue-u)<=\epsilon+E_T(v)+\epsilon
Da \epsilon beliebig war folgt: norm(v-u)<=E_T(v)
Durch die Definition von E_T(v) ergibt sich aber auch E_T(v)<=norm(v-u) woraus man erhält, dass E_T(v)=norm(v-u) und somit dass u ein Proximum ist.
Wie nun unschwer einzusehen ist wird uns also die Kompaktheit den Weg zum Proximum öffnen:
\red\double\frame
(Satz:)__
Sei (V, norm(.)) ein normierter Vektorraum und T eine kompakte Teilmenge von V, dann gilt: \forall v \el\ V \exists u^~ \el\ T : u^~ ist Proximum an v
\frameoff
Beweis: Sei ( u_\nue ) eine Minimalfolge in T für v \el\ V. Da nun T kompakt ist existiert eine konvergente Teilfolge ( u_\nue_\mue ) von ( u_\nue ) mit einem Häufungspunkt u^~ in T. Daraus folgt mit Lemma2 dass u^~ ein Proximum ist.
In diesem Abschnitt wird uns die Eindeutigkeit eines Proximums beschäftigen. Gleich zum Einstieg ein Beispiel in dem das Proximum nicht eindeutig ist:
Sei V=\IR^2 mit der euklidischen Norm und T:=menge(x:=(x_1 ,x_2)\el\ \IR^2 | norm(x)<=1 \and \not(x_1>1 \and x_2>2))
\geo
xachse(-4,4)
yachse(-4,4)
pen(2)
param(phi,90,360,1,deg2rad)
kurve(3*cos(phi),3*sin(phi),)
punkt(3,3,v)
punkt(0,3,u_1)
punkt(3,0,u_2)
pen(1)
pfeil(u_1,v,E_T(v))
pfeil(u_2,v,,nolabel)
pfeil(v,u_2,E_T(V))
pfeil(v,u_1,,nolabel)
\geooff
geoprint()
Für die weiteren Betrachtungen sind folgende Definitonen unentbehrlich:
\black\double\frame
(Definition:)__
Sei M eine Teilmenge eines Vektorraumes V, dann gilt:
M heißt konvex :<=> \forall x,y \el\ M : [x,y] \subset M
[x,y]:=menge((1-\lambda)*x+\lambda*y | 0<=\lambda<=1)
\frameoff
In Worten bedeutet diese Definiton so viel wie: Mit zwei beliebigen Punkten der Menge liegt auch deren Verbindungsstrecke in der Menge
Im Folgenden bezeichne \pd M den Rand von M. Eine stärkere Forderung als Konvexität ist:
\black\double\frame
(Definition:)__
Es sei V ein lokalkonvexer topologischer Vektorraum und M \subset V eine abgeschlossene und konvexe Teilmenge, dann gilt:
M heißt streng konvex :<=> \pd M enthält keine Strecke
\frameoff
Im Folgenden bezeichne T^° das Innere von T. Nachstehenden Satz werden wir mit Vorteil verwenden können:
\red\double\frame
(Satz:)__
Es sei T eine Teilmenge eines topologischen Vektorraumes V und T sei konvex, dann gilt:
\pd T enthält keine Strecke <=> \forall x,y \el\ T, x!=y : (1-\lambda)*x+\lambda*y \el\ T^°
\frameoff
Beweis:
Ich erlaube mir ohne Beweis zu verwenden:
(A) Sei T eine Teilmenge eines Vektorraumes V und T ist konvex => T^° ist konvex
(B) Accessibility Lemma: Sei T eine Teilmenge eines Vektorraumes V und T ist konvex => x\el\T^° \and y\el\ \pd T => (x,y) \subset T^°
wobei (x,y):=menge(0<\lambda<1 | (1-\lambda)x+\lambda*y)
(=>)
Es sei also T streng konvex.
1. Fall: x\el\ T^°, y\el\T^° => da T konvex ist, so ist auch T^° konvex und somit muss die Verbindungslinie (x,y) \subset T^° sein
2. Fall: x\el\ T^°, y\el\ \pd T => Unter Verwendung des Accessibility Lemmas ist die Verbindungslinie (x,y) \subset T^°
3. Fall: x,y \el\ \pd T => da der Rand keine Strecke enthält \exists \lambda : z_\lambda:=(1-\lambda)*x+\lambda*y \el\ T^°
Unter Verwendung des Accessibility Lemma folgt sofort (x,z_\lambda) \el\ T^° und (z_\lambda, y) \el\ T^°, da auch z_\lambda \el\ T^° folgt somit dass (x,y) \el\ T^°
(<=)
gelte \forall x,y \el\ T, x!=y : (1-\lambda)*x+\lambda*y \el\ T^° ,0<\lambda<1
Angenommen \pd T würde eine Strecke [x,y] x!=y enthalten:
[x,y] \el\ \pd T => [x,y] \el\ T => (x,y) \el\ T => (x,y) \el\ T^° was ein Widerspruch zu [x,y]\el\ \pd T ist
Nun endlich sind wir da wo wir hin wollten:
\red\double\frame
(Satz:)__
Sei (V, norm(.)) ein normierter Vektorraum und T eine kompakte, streng konvexe Teilmenge von V, dann existiert eindeutig ein Proximum in T an v für alle v \el\ V.
\frameoff
Beweis:
Durch die kompaktheit von T ist uns die Existenz eines Proximums gesichert. Seien nun (u_1)^~ und (u_2)^~ Proxima an v \el\ V mit (u_1)^~!=(u_2)^~
norm(1/2*((u_1)^~+(u_2)^~)-v)=norm(1/2*((u_1)^~-v)+1/2*((u_2)^~-v))
<=1/2*norm((u_1)^~-v)+1/2*norm((u_2)^~-v)=1/2*E_T(v)+1/2*E_T(v)=E_T(v)
da E_T(v):=inf(u\el\T,norm(u-v)) folgt norm(1/2*((u_1)^~+(u_2)^~)-v)=E_T(v) und somit ist 1/2*((u_1)^~+(u_2)^~) ebenfalls Proximum
Da T streng konvex ist folgt mit obigem Satz: 1/2*((u_1)^~+(u_2)^~) \el\ T^°
\exists \lambda^^ \el\ ]0,1[ : u^~:=(1-\lambda^^)*1/2*((u_1)^~+(u_2)^~)+\lambda^^*v \el\ T
Damit gilt:
\align
norm(u^~-v)=norm((1-\lambda^^)*1/2*((u_1)^~+(u_2)^~)+\lambda^^*v-v)
=(1-\lambda^^)*norm(1/2*((u_1)^~+(u_2)^~)-v)
=(1-\lambda^^)*E_T(v)
norm(u^~-v) (u_1)^~=(u_2)^~
Für manche Anwendungen kann es wichtig sein dass T nicht nur Teilmenge sondern ein endlich-dimensionaler Teilraum von V ist.
\blue\double\frame
(Lemma3:)__
Sei (V, norm(.)) ein normierter Vektorraum und T ein endlich-dimensionaler Teilraum, dann gilt:
Jede Minimalfolge in T ist beschränkt
\frameoff
Beweis:
Es sei ( u_\nue ) eine Minimalfolge in T für v\el\V, dh es gilt laut Defintion der Minimalfolgen:
\forall \epsilon \exists N_\epsilon \forall \nue>N : norm(norm(u_\nue-v)-E_T(v))< \epsilon
Sei \epsilon beliebig:
dh also: \forall \nue > N : E_T(v)<=norm(u_\nue-v) \forall \nue : norm(u_\nue)<=K
Auf dem Fuß folgt der nächste wichtige Satz:
\red\double\frame
(Satz:)__
Sei T ein endlichdimensionaler linearer Teilraum des normierten Vektorraumes (V, norm(.)) dann gilt:
\forall v\el\V \exists u^~\el\T : u^~ ist Proximum an v in T
\frameoff
Beweis:
Nach Lemma3 sind Minimalfolgen für v\el\V in T beschränkt. Jede beschränkte, unendliche Folge hat einen Häufungspunkt, nennen wir ihn u^~. Da T ein endlich-dimensionaler linearer Teilraum eines normierten Vektorraumes ist so ist er als topologischer Vektorraum also abgeschlossen, dh u^~\el\T. Das bedeutet mit Lemma2 dass u^~ Proximum an v ist.
Eine Verschärfung der Normiertheit ist:
\black\double\frame
(Definition:)__
Sei V eine normierter Vektorraum mit der Norm norm(.), dann gilt:
norm(.) heißt eine strenge Norm :<=>
\forall f,g \el\ V [ norm(f+g)=norm(f)+norm(g) => \exists \lambda : g=\lambda*f ]
\frameoff
Bemerkung: man kann sofort folgern dass \lambda>0 sein muss.
Beweis:
norm(f+g)=norm(f)+norm(g)
norm(f+\lambda*f)=norm(f)+norm(\lambda*f)
abs(1+\lambda)*norm(f)=(1-abs(\lambda))*norm(f)
f!=0 => abs(1+\lambda)=1+abs(\lambda)
=>\lambda>0
\red\double\frame
(Satz:)__
Sei V ein streng normierter Vektorraum =>
Das Proximum an v\el\V in einem beliebigen endlich-dimensionalen Teilraum T ist eindeutig bestimmt
\frameoff
Beweis:
Seien (u_1)^~ und (u_2)^~ Proxima an v\el\V
Den Trivialfall v\el\T schließen wir hier natürlich aus denn dann wäre ja u^~ eindeutig! also:
norm(v-1/2*((u_1)^~+(u_2)^~))<=1/2*norm(v-(u_1)^~)+1/2*norm(v-(u_2)^~)=2*1/2*E_T(v)=E_T(v)
durch die Definition von E_T(v) folgt auch E_T(v)<=norm(v-1/2*((u_1)^~+(u_2)^~)) und somit also:
norm(v-1/2*((u_1)^~+(u_2)^~))=E_T(v)
dadurch gilt in obiger Ungleichung aber die Gleichheit:
norm(v-1/2*((u_1)^~+(u_2)^~))=1/2*norm(v-(u_1)^~)+1/2*norm(v-(u_2)^~)
1/2*norm((v-(u_1)^~)+(v-(u_2)^~))=1/2*norm(v-(u_1)^~)+1/2*norm(v-(u_2)^~)
norm((v-(u_1)^~)+(v-(u_2)^~))=norm(v-(u_1)^~)+norm(v-(u_2)^~)
daraus folgt wegen der strengen Normiertheit:
\exists \lambda >0 : v-(u_1)^~=\lambda*(v-(u_2)^~)
(1-\lambda)*v=(u_1)^~-\lambda*(u_2)^~
Da v aber nicht aus T war und T ein Vektorraum ist folgt v!=0 und v kann keine Linearkombination von Elementen aus T sein
=> 1-\lambda=0 => \lambda=1 => (u_1)^~=(u_2)^~
\black\double\frame
(Defintion:)__
Ein normierter Vektorraum X heißt streng konvex, wenn die Einheitskugel streng konvex ist.
\frameoff
Beispiel: (\IR^2, norm(.)_2) ist streng konvex
(\IR^2, norm(.)_1) ist nicht streng konvex, norm(x)_1=norm(( x_1 , x_2) )=abs(x_1)+abs(x_2)
Im \IR^n sind alle Normen äquivalent, die strenge Konvexität kann jedoch verloren gehen, ist also keine Invariante.
\red\double\frame
(Satz:)__
Sei X ein normierter Raum
X ist streng konvex <=> norm(x)=norm(y)=1 \and x!=y => norm(1/2*(x+y))<1
\frameoff
Beweis:
(<=) ist anschaulich klar, der Rand der Einheitskugel kann niemals eine Strecke enthalten wenn für alle x,y mit norm(x)=norm(y) der Mittelpunkt von x+y im Inneren der Einheitskugel liegt.
(=>) Sei X streng konvex, dh also die Einheitskugel ist streng konvex, so gilt wenn (x,y) die offene Strecke zwischen x und y ist:
\forall x,y norm(x)=norm(y)=1, x!=y \exists z \el\ (x,y) : norm(z)<1
Fall 1: 1/2*(x+y) \el\ (x,z)
\exists \lambda \el\ ]0,1[ : (1-\lambda)*x+\lambda*z=1/2*(x+y)
norm(1/2*(x+y))<=(1-\lambda)*norm(x)+\lambda*norm(z)<1-\lambda+\lambda=1
Fall 2: 1/2*(x+y) \el\ (z,y)
\exists \lambda \el\ ]0,1[ : (1-\lambda)*z+\lambda*y=1/2*(x+y)
norm(1/2*(x+y))<=(1-\lambda)*norm(z)+\lambda*norm(y)<1-\lambda+\lambda=1
Und noch ein Satz der uns zu einer anschaulichen Darstellung der Eindeutigkeit des Proximums führen wird:
\red\double\frame
(Satz:)__
Sei X ein normierter Vektorraum:
X ist streng normiert <=> X ist streng konvex
\frameoff
Beweis:
(=>)
x,y \el\ X, x!=y
Es seien norm(x)=norm(y)=1
Da die Einheitskugel konvex ist gilt: norm(1/2*(x+y))<=1
Angenommen norm(1/2*(x+y))=1
1/2*norm(x+y)=1=1/2*norm(x)+1/2*norm(y)
norm(x+y)=norm(x)+norm(y)
wegen der strengen Normiertheit folgt \exists \lambda >0 x=\lambda*y
norm(x)=\lambda*norm(y)=>1=\lambda*1=>\lambda=1=>x=y und somit ein Widerspruch zur Annahme. Das heißt also es muss folgen norm(1/2*(x+y))<1 also X streng konvex
(<=)
Es sei X streng konvex und es gelte norm(x+y)=norm(x)+norm(y) für beliebiges x,y
Sei oBdA norm(y)>=norm(x)!=0
norm(x/norm(x)+y/norm(y))=norm((x/norm(x)+y/norm(x))-(y/norm(x)-y/norm(y)))
>=norm(x/norm(x)+y/norm(x))-norm(y/norm(x)-y/norm(y))=norm(x+y)/norm(x)-abs(1/norm(x)-1/norm(y))*norm(y)
=(norm(x)+norm(y))/norm(x)-(1/norm(x)-1/norm(y))*norm(y)=norm(x)/norm(x)+norm(y)/norm(x)-norm(y)/norm(x)+norm(y)/norm(y)=2
also insgesamt: 1/2*norm(x/norm(x)+y/norm(y))>=1
da X aber streng konvex sein muss folgt also \not(x/norm(x)=y/norm(y)=1 \and x/norm(x)!=y/norm(y)), also x/norm(x)=y/norm(y)!=1 \or x/norm(x)=y/norm(y). Da aber x/norm(x)=y/norm(y) immer =1 ist muss x/norm(x)=y/norm(y) sein.
Damit folgt x=norm(x)/norm(y)*y. für \lambda:=norm(x)/norm(y)>0 folgt x=\lambda*y
Somit ergibt sich insgesamt
\black\double\frame
(Corollar:)__
Sei V ein normierter Vektorraum.
Wenn die Einheitskugel von V keine Strecke enthält ist das Proximum u^~ aus einem beliebigen endlich-dimensionalen Teilraum T an v\el\V eindeutig bestimmt.
\frameoff
Ich finde, dass es viel anschaulicher wie dieser Satz unser Problem charakterisiert, nicht mehr geht. So kann man in vielen Fällen schon durch bloßes aufzeichnen/betrachten der Einheitskugel sagen ob ein Proximum eindeutig sein wird oder nicht.
Zum Abschluß noch ein kleines Beispiel: Sei V=\IR^3, x:=(x_1 ,x_2 ,x_3) und die Norm folgendermaßen norm(.):=norm(x)=max(i,abs(x_i))
Die Einheitskugel ist somit der Würfel mit den Eckpunkten (1,-1,1),(1,-1,-1),(1,1,1)(1,1,-1),(-1,1,1),(-1,1,-1),(-1,-1,1) und (-1,-1,-1). Dass diese Einheitskugel Strecken enthält ist klar, somit wird das Approximationsproblem nicht eindeutig gelöst werden können: Sei zB T=span<(1;0;0),(0;1;0)> also die x-y-Ebene, ein zweidimensionaler Teilraum von V. Nehmen wir beispielsweise für v=(3;3;2)\el\ \IR^3.
Wenn u^~ Proximum ist so muss norm(v-u^~)=min((\alpha_1, \alpha_2),norm(v-(\alpha_1*(1;0;0)+\alpha_2*(0;1;0))) sein.
norm(v-(\alpha_1*(1;0;0)+\alpha_2*(0;1;0)))=norm((3-\alpha_1;3-\alpha_2;2))=max{ abs(3-\alpha_1), abs(3-\alpha_2),2}
Das Minimum dieser Menge über \alpha_1 ,\alpha_2 wird angenommen wenn abs(3-\alpha_1)<=2 und abs(3-\alpha_2)<=2 ist, also für 1<=\alpha_(1,2)<=5
Somit ist E_T(v)=2 und die Proxima sind aus der Menge menge(x\el\V | x=(\alpha_1 ;\alpha_2 ; 0), 1<=\alpha_(1,2)<=5)
Nun sind wir schon wieder am Ende unserer Etappe quer durch die Approximationstheorie. Leider ist es mir nicht gelungen den angekündigten Alternantensatz zu beweisen - ich muss ihn in den nächsten Teil verschieben, da ich hier so viele neue Definitionen erläutern musste. Ich hoffe auch dieser Teil erfreut ein paar Leser und macht Lust auf mehr.
Viele liebe Grüße
tack
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
