Matroids Matheplanet Forum Index
Moderiert von Kleine_Meerjungfrau Monkfish epsilonkugel
Mathematik » Stochastik und Statistik » Funktion minimieren
Druckversion
Druckversion
Autor
Universität/Hochschule J Funktion minimieren
Phoensie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2020
Mitteilungen: 421
Herkunft: Muri AG, Schweiz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-05

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}             % Natürliche Zahlen \newcommand{\Z}{\mathbb{Z}}             % Ganze Zahlen \newcommand{\Q}{\mathbb{Q}}             % Rationale Zahlen \newcommand{\R}{\mathbb{R}}             % Reelle Zahlen \newcommand{\C}{\mathbb{C}}             % Komplexe Zahlen \newcommand{\ord}{\mathrm{ord}}         % Gruppenordnung \newcommand{\indep}{\perp \!\!\! \perp} % Stochastische Unabhängigkeit (Symbol) \renewcommand{\Re}{\operatorname{Re}}   % Realteil \renewcommand{\Im}{\operatorname{Im}}   % Imaginärteil \renewcommand{\d}{\operatorname{d}}     % Differential-d \)
Liebe Matheplanetarier

Aufgabe.
Seien $n \in \N^*$ und $x_1,\ldots,x_n \in \R$. Für welche $\theta \in \R$ wird die Funktion $q:\R \to \R+$,
\[q(\theta)=\sum_{i=1}^n |x_i - \theta|\] minimal?

Mein erster Gedanke ist es, mal den Fall zu betrachten, wo alle $x_i$ dasselbe Vorzeichen haben. Jedoch fehlt mir der Ansatz für mein $\theta$, denn $q$ ist aufgrund der vorkommenden Beträge nicht überall differenzierbar...
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2668
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-05

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname}\)
Hallo,

hast du dir bereits den Fall $n=2$ klar gemacht?

Zum Allgemeinen Fall: Wie ändert sich $q(\theta)$, wenn man $\theta$ ein kleines bisschen vergrößert bzw. verkleinert?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-03-05


Hallo,

ist $n$ gerade oder ungerade? Für ungerades $n$ gibt es genau eine Stelle, an der die Funktion ihr globales Minimum annimmt. Sie ist an dieser Stelle nicht differenzierbar.
Ist $n$ gerade, gibt es ein Intervall, in dem das globale Minimum angenommen wird.

[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Phoensie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2020
Mitteilungen: 421
Herkunft: Muri AG, Schweiz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-03-05

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}             % Natürliche Zahlen \newcommand{\Z}{\mathbb{Z}}             % Ganze Zahlen \newcommand{\Q}{\mathbb{Q}}             % Rationale Zahlen \newcommand{\R}{\mathbb{R}}             % Reelle Zahlen \newcommand{\C}{\mathbb{C}}             % Komplexe Zahlen \newcommand{\ord}{\mathrm{ord}}         % Gruppenordnung \newcommand{\indep}{\perp \!\!\! \perp} % Stochastische Unabhängigkeit (Symbol) \renewcommand{\Re}{\operatorname{Re}}   % Realteil \renewcommand{\Im}{\operatorname{Im}}   % Imaginärteil \renewcommand{\d}{\operatorname{d}}     % Differential-d \)
Falls $n=0$ ist, ist $q$ als leere Summe die Nullfunktion.
Falls $n=1$ ist, hat $q$ ein Minimum mit $q(x_1)=0$.
Allgemein ist $q$ nichtnegativ (als Summe von Beträgen) und stetig.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-03-05


Das stimmt zwar beides. Aber du sieht noch nicht so viel. Spannend wird es für größere $n$. Die Funktion ist stückweise affin. Wo ist ihre Steigung größer als Null, wo kleiner?
Betrachte vielleicht erst einmal ungerade $n$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 394
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-03-05


\(\endgroup\)
\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}             % Natürliche Zahlen \newcommand{\Z}{\mathbb{Z}}             % Ganze Zahlen \newcommand{\Q}{\mathbb{Q}}             % Rationale Zahlen \newcommand{\R}{\mathbb{R}}             % Reelle Zahlen \newcommand{\C}{\mathbb{C}}             % Komplexe Zahlen \newcommand{\ord}{\mathrm{ord}}         % Gruppenordnung \newcommand{\indep}{\perp \!\!\! \perp} % Stochastische Unabhängigkeit (Symbol) \renewcommand{\Re}{\operatorname{Re}}   % Realteil \renewcommand{\Im}{\operatorname{Im}}   % Imaginärteil \renewcommand{\d}{\operatorname{d}}     % Differential-d \)2021-03-05 15:41 - Phoensie im Themenstart schreibt:
Jedoch fehlt mir der Ansatz für mein $\theta$, denn $q$ ist aufgrund der vorkommenden Beträge nicht überall differenzierbar...
\(\endgroup\)

Nur so als Fun-Fact am Rande (vielleicht kommt das in einer Deiner Vertiefungsvorlesungen ja später mal vor): Trotz der nicht vorhandenen klassischen Differenzierbarkeit ist es möglich, diese Aufgabe ähnlich wie in der Schule nach Kochrezept durch "Nullsetzen" der Ableitung zu lösen. Dazu kann man das sogenannte Subdifferential (eine Mengenwertige Ableitung) betrachten, siehe
de.wikipedia.org/wiki/Subdifferential#Beispiel

Ich nehme \(x_1<\ldots<x_n\) an. Definiert man für \(\theta\in\mathbb{R}\) die Zahlen \(n_<:=\#\{i\in\{1,\ldots,n\}\,|\,x_i<\theta\}\) und \(n_>:=\#\{i\in\{1,\ldots,n\}\,|\,x_i>\theta\}\), so sollte denke ich \(\partial q(\theta)=\{n_<-n_>\}\) für \(\theta\neq x_i\) und \(\partial q(x_i)=[n_<-n_>-1,n_<-n_>+1]\) sein.


Die Bedingung \(0\in\partial q(\theta)\) ist für \(\theta\neq x_i\) genau dann erfüllt, wenn \(n_>=n_<=\frac{n}{2}\), was für ungerade \(n\) unmöglich ist und für gerade \(n\) die Punkte \(\theta\in(x_{\frac{n}{2}},x_{\frac{n}{2}+1})\) liefert.

Die Bedingung \(0\in\partial q(x_i)\) ist für ungerade \(n\) genau dann erfüllt, wenn \(n_>=n_<=\frac{n-1}{2}\) ist, was \(\theta=x_{\frac{n+1}{2}}\) bedeutet. Für gerade \(n\) ist dies genau dann erfüllt, wenn \(n_>=\frac{n}{2}-1\) und \(n_<=\frac{n}{2}\) ist (was \(\theta=x_{\frac{n}{2}+1}\) bedeutet) oder wenn \(n_>=\frac{n}{2}\) und \(n_<=\frac{n}{2}-1\) ist (was \(\theta=x_{\frac{n}{2}}\) bedeutet).

Zusammenfassend erhält man die Minimalstellen \([x_{\frac{n}{2}},x_{\frac{n}{2}+1}]\) für gerade \(n\) und \(\{x_{\frac{n+1}{2}}\}\) für ungerade \(n\).


Das geht in diesem konkreten Fall natürlich auch einfacher ohne Subdifferentiale.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Phoensie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2020
Mitteilungen: 421
Herkunft: Muri AG, Schweiz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-03-05

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}             % Natürliche Zahlen \newcommand{\Z}{\mathbb{Z}}             % Ganze Zahlen \newcommand{\Q}{\mathbb{Q}}             % Rationale Zahlen \newcommand{\R}{\mathbb{R}}             % Reelle Zahlen \newcommand{\C}{\mathbb{C}}             % Komplexe Zahlen \newcommand{\ord}{\mathrm{ord}}         % Gruppenordnung \newcommand{\indep}{\perp \!\!\! \perp} % Stochastische Unabhängigkeit (Symbol) \renewcommand{\Re}{\operatorname{Re}}   % Realteil \renewcommand{\Im}{\operatorname{Im}}   % Imaginärteil \renewcommand{\d}{\operatorname{d}}     % Differential-d \)
Ich danke euch allen für die ausführlichen Tipps. Nach einigem Erforschen der Funktion mit dem Grafikrechner desmos.com hab' ich "gesehen", was ihr mir sagen wolltet (und Sonnenschein96 bereits plusminus ausgeführt hat).

Um stoffmässig in meiner Stufe zu bleiben schlage ich folgenden Pseudoalgorithmus vor, um die Aufgabe zu lösen. Er ist noch nicht formalisiert, aber gibt -- so glaube ich -- mal die Idee wieder:

Schritt 1
Bestimme die Parität von $n$ (gerade/ungerade) und nummeriere die $x_i$ in aufsteigender Reihenfolge ($x_1 \leq ... \leq x_n$).

Schritt 2
$q$ ist im klassischen Sinne an den Stellen $x_i$ nicht differenzierbar (da dort immer jeweils ein Betragssummand verschwindet). Dazwischen, also in den offenen Intervallen $(x_i,x_{i+1})$ kann eine Ableitung ausgewertet werden. Hierbei bestimmt die Position des betrachteten Arguments $\theta$ die Steigung der Funktion massgeblich.

Schritt 3
Für $\theta < x_1$ ist $q$ monoton fallend, für $\theta > x_n$ monoton wachsend. dazwischen ist $q$ eine stückweise affine Funktion.

Schritt 4: Fallunterscheidung.
Falls $n$ gerade ist, dann sind für $\theta \in (x_{\frac{n}{2}},x_{\frac{n}{2}+1})$ genau in der Hälfte der Summanden von $q$ negative Zahlen in den Beträgen vorhanden, deren Auswertung dann ihr Vorzeichen kehrt und beim anschliessenden Ableiten der Funktion die positiven Vorzeichen "verschluckt", weshalb $q'(\theta)=0$ herauskommt für diese $\theta$.

Falls $n$ ungerade ist, dann gilt mit analoger Argumentation (Zählen der Anzahl Beträge, deren Auswertung das Vorzeichen der Zahl darin umkehrt), dass $q'(\theta) = -1$ für $\theta \in (x_{\frac{n-1}{2}},x_{\frac{n+1}{2}})$ gilt, und ebenso $q'(\theta)=1$ für $\theta \in (x_{\frac{n+1}{2}},x_{\frac{n+3}{2}})$ ist. Für $\theta<x_{\frac{n+1}{2}}$ ist $q$ monoton fallend, für $\theta>x_{\frac{n+1}{2}}$ ist die Funktion monoton wachsend. Somit ist $x_{\frac{n+1}{2}}$ das einzige (und somit globale) Minimum von $q$; jedoch ist $q$ nicht differenzierbar in diesem Punkt.

Was denkt ihr zu dieser Überlegung?

LG Phoensie😄
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2668
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-03-05

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname}\)
Ein paar Details fehlen noch:
- Die Menge der Minimalstellen ist abgeschlossen, da $q$ stetig ist. Im Fall von geradem $n$ hast du aber eine offene Menge angegeben.

- Wenn die $x_i$ nicht paarweise verschieden sind, musst du auch noch ein bisschen nachbessern.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Phoensie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2020
Mitteilungen: 421
Herkunft: Muri AG, Schweiz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2021-03-06


In Ordnung, Nuramon; danke für den Hinweis. Deinen ersten Punkt werde ich ausbessern können, indem ich das offene durch das geschlossene Intervall ersetze (Nachrechnen zeigt, dass am Rand die Werte mit dem Inneren übereinstimmen).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Phoensie hat die Antworten auf ihre/seine Frage gesehen.
Phoensie hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]