Median soll Minimum sein < stoch. Analysis < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen sie, dass der Median [mm] c=\mu [/mm] den folgenden Ausdruck minimiert
[mm] A(c)=\sum_{i=1}^{n}|c-x_i|
[/mm]
|
Hallo,
hab schon vieles probiert um zu zeigen, dass der Median den obigen Ausdruck minimiert. Ableiten funktioniert wird zu kompliziert, da A(c) nicht überall differenzierbar. Habs ansonsten noch versucht zu zeigen dass die Diffenrenz [mm] A(c\neq\mu)-A(c=\mu)\geq [/mm] 0
Wäre super, wenn mir da jemand helfen könnte!
Danke im Voraus,
Lorenz
|
|
| |
|
> Zeigen sie, dass der Median [mm]c=\mu[/mm] den folgenden Ausdruck
> minimiert
> [mm]A(c)=\sum_{i=1}^{n}|c-x_i|[/mm]
>
> Hallo,
>
> hab schon vieles probiert um zu zeigen, dass der Median den
> obigen Ausdruck minimiert. Ableiten funktioniert wird zu
> kompliziert, da A(c) nicht überall differenzierbar. Habs
> ansonsten noch versucht zu zeigen dass die Diffenrenz
> [mm]A(c\neq\mu)-A(c=\mu)\geq[/mm] 0
Hallo Lorenz,
hier könnte ein Vorgehen im Sinne eines Induktionsbeweises
funktionieren.
Im Falle n=1 ist der Fall klar: um [mm] |x_1-c| [/mm] zu minimieren,
muss man natürlich [mm] c=x_1 [/mm] setzen, dann wird [mm] |x_1-c|=0
[/mm]
und damit minimal. Auch der Median ist in diesem Fall gleich [mm] x_1.
[/mm]
Auch den Fall n=2 kann man sich leicht klar machen. (***)
Idee für den Induktionsschritt:
Hat man eine Liste von mehr als 2 Elementen, so gibt
es darin ein grösstes Element o mit [mm] o\ge \mu [/mm] und ein
kleinstes Element u mit [mm] u\le \mu. [/mm] Entfernt man diese
beiden Elemente, so verringert sich die Summe [mm] A(\mu),
[/mm]
oder sie bleibt (nur dann wenn ohnehin schon alle
verbliebenen Elemente gleich gross sind) konstant.
Der Median der neuen Liste (nachdem o und u entfernt
worden sind) ist gleich dem vorherigen.
(wie daraus ein hieb- und stichfester Beweis werden soll,
ist mir zwar noch nicht ganz klar)
LG al-Chwarizmi
(***) $ [mm] \red{c=\mu} [/mm] $ ist dann zwar (wenn [mm] $\red{x_1\not= x_2)}$ [/mm] nicht das
einzige c, für welches A(c) minimal wird
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:19 So 12.10.2008 | | Autor: | luis52 |
Wir koennen o.E.d.A. annehmen, dass die Werte geordnet sind:
[mm] $x_1\le x_2\le\cdots\le x_n$. [/mm] Gesucht ist der Wert $a$, der die Funktion
[mm] $L(z):=\sum_{i=1}^n|x_i-z|$
[/mm]
minimiert, so dass also gilt [mm] $L(a)\le [/mm] L(z)$ fuer alle [mm] $z\in\IR$.
[/mm]
Sei zunaechst $n$ gerade, also $n=2m$. Es gilt
$L(z) = [mm] \sum_{i=1}^m(|x_i-z|+|x_{n+1-i}-z|) [/mm] =: [mm] \sum_{i=1}^mb_i(z)$
[/mm]
Mit [mm] $a_i:=x_{n+1-i}-x_i$ [/mm] gilt
[mm] $b_i(z)=\left\{\begin{array}{ll}
a_i+2(x_i-z) & z
Wir koennen sagen:
1) [mm] $b_i$ [/mm] faellt streng monoton in [mm] $(-\infty,x_i]$.
[/mm]
2) [mm] $b_i$ [/mm] ist konstant [mm] $=a_i$ [/mm] in [mm] $(x_i,x_{n+1-i}]$.
[/mm]
3) [mm] $b_i$ [/mm] steigt streng monoton in [mm] $(x_{n+1-i},+\infty)$.
[/mm]
Mithin minimiert jeder Wert $a$ aus [mm] $[x_m,x_{m+1}]$ [/mm] *alle* Funktionen [mm] $b_i$ [/mm] und somit $L(z)$.
Ist $n=2m+1$ ungerade, so sei
$L(z)= [mm] \underbrace{\sum_{i=1}^m\lrbs{|x_i-z|+|x_{n+1-i}-z|}}_{A(z)}+ \underbrace{|x_{m+1}-z|}_{B(z)}$
[/mm]
Jedes [mm] $a\in[x_m,x_{m+2}]$ [/mm] minimiert $A(z)$, aber nur [mm] $x_{m+1}\in[x_m,x_{m+2}]$ [/mm] minimiert $B(z)$. Mithin ist dann [mm] $a=x_{m+1}$.
[/mm]
In jedem Fall minimiert [mm] $a=x_{0.5}$ [/mm] den Wert $L(z)$.
vg Luis
|
|
|
| |
|
Ich stelle mir die Elemente der Liste vor als eine Menge
von Schlittenhunden, die längs eines geradlinigen Weges
ruhen. Ein Hund an der Stelle x ist durch eine Leine der
Länge |x-c| mit dem Centrum C an der Stelle c verbunden.
Wo muss das Centrum sein, damit die Summe A der Leinen-
längen minimal wird ?
Sind links und rechts von C gleichviele Hunde, so kann A
nicht verkleinert werden: von C aus gehen ja gleichviele
Leinen nach rechts und nach links ab. Eine kleine Veränderung
von c bringt also nichts, denn was wir vielleicht rechts
gewinnen, verlieren wir links, und umgekehrt. Schieben
wir C an einem der nächstliegenden Hunde vorbei, nimmt
A aber zu, weil wir auf der einen Seite mehr zusätzliche
Leinenlänge brauchen, als wir auf der anderen Seite ein-
sparen.
Wenn die Anzahl der Listenelemente, die grösser als c sind,
jene die kleiner als c sind, übertrifft, so kann man A verklei-
nern, indem man c bis zum nächstgrösseren Wert vergrössert,
der in der Liste vorkommt, und umgekehrt.
Insgesamt kann man also A stets verkleinern, solange c grösser
als das kleinste Listenelement, das grösser oder gleich dem Median
ist, ist, und ebenso, falls c kleiner als das grösste Listenelement ist,
das kleiner oder gleich dem Median ist.
Damit wird klar, dass c grösser oder gleich dem grössten
Element, welches kleiner oder gleich dem Median ist, und
kleiner oder gleich dem kleinsten Element, welches grösser
oder gleich dem Median ist, sein muss. Alles klar ? 
|
|
|
| |
|
Hallo Al-Chwarizmi,
herzlichen Dank für Deine schnelle Reaktion! Den Induktionsbeweis fand ich ehrlich gesagt ein bisschen haarig, aber das mit den Hundeleinen hab ich gut verstanden. Danke für Deine Hilfe!
Hallo luis52,
Danke für Deine ausführliche und sehr trickreiche, elegante Lösung. Hab zwar nen Stündchen gebraucht ums komplett nachvollziehen zu können, aber hat sich gelohnt!
Lieben Gruß,
Lorenz
|
|
|
| |
|
> Hallo Al-Chwarizmi,
> herzlichen Dank für Deine schnelle Reaktion! Den
> Induktionsbeweis fand ich ehrlich gesagt ein bisschen
> haarig, aber das mit den Hundeleinen hab ich gut
> verstanden. Danke für Deine Hilfe!
vielleicht war der Induktionsbeweis wirklich so haarig
wie ein Husky - war auch nur eine lausige vorläufige Idee
|
|
|
|
