Operatornorm (3)

22.12.2008, 01:07

tigerbine

Operatornorm (3)

Nun das ganze umgekehrt (wieder mit äquivalenter Definition)

$\begin{eqnarray*} \| A\|_{\infty \to 1}=\sup_{\|x\|_\infty=1}\|Ax\|_{1} \end{eqnarray*}$

nun soll man zeigen, dass es für eine nxm Matrix ein $\begin{eqnarray*} x\in \{-1,1\} \end{eqnarray*}$ gibt, so dass gilt:

$\begin{eqnarray*} \| A\|_{\infty \to 1}=\|Ax\|_{1} \end{eqnarray*}$

Jemand eine Idee?

22.12.2008, 18:36

Reksilat

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Ich nehme an, dass Du $\begin{eqnarray*} x\in \{1,-1\}^m \end{eqnarray*}$ meinst. (Alle Einträge sind $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ und somit $\begin{eqnarray*} \|x\|_\infty=1 \end{eqnarray*}$ ).

Erster Teil:
$\begin{eqnarray*} \|A\|_{\infty\to 1}\geq \|Ax\|_1 \end{eqnarray*}$ sieht man wieder ganz gut.

Achtung! Der zweite Teil funktioniert so nicht, weiter unten findet sich eine (hoffentlich) korrekte Version.
Zweiter Teil: Es ist
$\begin{eqnarray*} \|A\|_{\infty\to 1}=\sum_{i=1}^{n}\left|\sum_{j=1}^{m}a_{ij}x_j\right|=\|Ax\|_1 \end{eqnarray*}$
für einen geeigneren Vektor $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} \|x\|_\infty=1 \end{eqnarray*}$ . Zu zeigen bleibt, dass $\begin{eqnarray*} |x_j|=1 \end{eqnarray*}$ für alle $\begin{eqnarray*} j=1,\ldots ,m \end{eqnarray*}$ gilt

Nun müssen wir nur noch geeignet bezeichnen und dazu betrachten wir für alle i den Ausdruck $\begin{eqnarray*} \sum_{j=1}^{m}a_{ij}x_j \end{eqnarray*}$ .
Ist dieser größer oder gleich Null, dann setzen wir $\begin{eqnarray*} \tilde{a}_{ij}=a_{ij} \end{eqnarray*}$ und andernfalls $\begin{eqnarray*} \tilde{a}_{ij}=-a_{ij} \end{eqnarray*}$ .

Damit ist
$\begin{eqnarray*} \|A\|_{\infty\to 1}=\sum_{i=1}^{n}\sum_{j=1}^{m}\tilde{a}_{ij}x_j \end{eqnarray*}$

Jetzt kann man die Summationszeichen vertauschen, die $\begin{eqnarray*} x_j \end{eqnarray*}$ herausziehen und man sieht, dass immer $\begin{eqnarray*} |x_i|=1 \end{eqnarray*}$ sein muss. (Andernfalls kann man $\begin{eqnarray*} x_i \end{eqnarray*}$ so verändern, dass der Gesamtwert größer oder zumindest nicht kleiner wird.)
Anmerkung: Kann man eben nicht, da die Konstruktion der $\begin{eqnarray*} \tilde{a}_{ij} \end{eqnarray*}$ ja auch von den $\begin{eqnarray*} x_i \end{eqnarray*}$ abhängt.

22.12.2008, 23:39

tigerbine

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Kannst du mir hier nochmal mit einem Licht entgegen kommen? So ganz verstehe ich deine Beweisidee nicht.

Im Vergleich zur (2) findet man hier nicht eine andere Darstellung der Operatornorm, sondern sucht ein spezielles x, für das dann die Gleichheit gilt. Dieses x hängt von der Matrix A ab.

Da für $\begin{eqnarray*} x \in \{-1,1\}^m \end{eqnarray*}$ gilt $\begin{eqnarray*} \| x\|_\infty=1 \end{eqnarray*}$ folgt $\begin{eqnarray*} \sup_{\|x\|_\infty =1}\|Ax\|_1\geq \|Ax\|_1 \end{eqnarray*}$

Nun soll man ein x konstruieren, für das Gleichheit gilt, oder? Das hat aber nicht zur Folge, dass i.A. Gleichheit gilt, oder?

23.12.2008, 00:24

Reksilat

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Bei Punkt zwei muss man anmerken, dass das Supremum auch wirklich angenommen wird, da $\begin{eqnarray*} \|\cdot\|_1 \end{eqnarray*}$ stetig und $\begin{eqnarray*} \{x;\|x\|_\infty=1\} \end{eqnarray*}$ kompakt ist. Nun nimmt man einen Vektor $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} \|x\|_\infty=1 \end{eqnarray*}$ , für den $\begin{eqnarray*} \|Ax\|_1 \end{eqnarray*}$ maximal wird und zeigt, dass alle Einträge betragsmäßig 1 sind. Korrekt wird das bei mir dann aber auch nicht behandelt, wie ich gerade sehe, da die $\begin{eqnarray*} \tilde{a}_{ij} \end{eqnarray*}$ ja auch von den $\begin{eqnarray*} x_j \end{eqnarray*}$ abhängen. Ich werde mir das noch mal anschauen und dann morgen von mir hören lassen; hoffentlich mit einem besseren Beweis.

gn8.

23.12.2008, 00:27

tigerbine

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Ok, bis morgen Wink

23.12.2008, 10:31

Reksilat

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Also entweder ist meine Denkstube durch Zwiebelmangel eingerostet, oder es ist wirklich ein recht unangenehme Aufgabe. Die Grundidee ist eigentlich auch gar nicht so kompliziert, das ganze aufzuschreiben schon eher.

Sei $\begin{eqnarray*} z:=\|A\|_{\infty\to 1} \end{eqnarray*}$ , dann wird, wie oben erwähnt, dieser Wert auch angenommen. Es gibt also einen Vektor $\begin{eqnarray*} x \end{eqnarray*}$ , mit $\begin{eqnarray*} \|x\|_\infty =1 \end{eqnarray*}$ und $\begin{eqnarray*} \|Ax\|_1=z \end{eqnarray*}$ .
Setze $\begin{eqnarray*} y=(y_1,\ldots,y_n)^t:=Ax \end{eqnarray*}$ , also $\begin{eqnarray*} y_i=\sum_{j=1}^{m}a_{ij}x_j \end{eqnarray*}$

Wir wollen zeigen, dass $\begin{eqnarray*} |x_j|=1 \end{eqnarray*}$ für alle $\begin{eqnarray*} j \end{eqnarray*}$ gilt und nehmen deshalb oBdA an, dass $\begin{eqnarray*} |x_1|<1 \end{eqnarray*}$ ist.
Setze $\begin{eqnarray*} \tilde{x}(\alpha):=(x_1+\alpha ,x_2,\ldots ,x_m)^t \end{eqnarray*}$ , für $\begin{eqnarray*} \alpha \in \mathbb{R} \end{eqnarray*}$ . Ist $\begin{eqnarray*} \alpha \end{eqnarray*}$ genügend klein, dann ist auch $\begin{eqnarray*} \|\tilde{x}(\alpha)\|_\infty=1 \end{eqnarray*}$ . Damit erhalten wir
$\begin{eqnarray*} \|A\tilde{x}(\alpha )\|_1=\sum_{i=1}^n\left| \sum_{j=1}^m a_{ij}x_j+a_{i1}\alpha \right| =\sum_{i=1}^n \left| y_i +a_{i1}\alpha\right|\quad (1) \end{eqnarray*}$

Zu zeigen ist, dass es ein $\begin{eqnarray*} \alpha\neq 0 \end{eqnarray*}$ gibt, mit $\begin{eqnarray*} \|A\tilde{x}(\alpha)\|_1>\|Ax\|_1=\sum|y_i| \end{eqnarray*}$ . Das ist dann unser Widerspruch.

Die einzelnen Summanden in (1) können wir als Funktionen in $\begin{eqnarray*} \alpha \end{eqnarray*}$ auffassen und diese sind dann einfach nur Betragsfunktionen, von denen wir wissen wie sie aussehen. Es gibt zwei Fälle:

Fall a): $\begin{eqnarray*} y_i=0 \end{eqnarray*}$
Dannn erreicht die Funktion $\begin{eqnarray*} |y_i+a_{i1}\alpha| \end{eqnarray*}$ in $\begin{eqnarray*} \alpha=0 \end{eqnarray*}$ gerade ihr Minimum und für jeden anderen Wert wird dieser Ausdruck größer.

Fall b): $\begin{eqnarray*} y_i\neq 0 \end{eqnarray*}$
In einer $\begin{eqnarray*} \varepsilon \end{eqnarray*}$ -Umgebung um $\begin{eqnarray*} \alpha=0 \end{eqnarray*}$ ist die Betragsfunktion linear, also entweder $\begin{eqnarray*} |y_i+a_{i1}\alpha|=y_i+a_{i1}\alpha \end{eqnarray*}$ oder $\begin{eqnarray*} |y_i+a_{i1}\alpha|=-y_i-a_{i1}\alpha \end{eqnarray*}$ für $\begin{eqnarray*} |\alpha|<\varepsilon_i \end{eqnarray*}$ .
Nun können wir aber über alle Funktionen, die Fall b) erfüllen summieren und erhalten wieder eine lineare Funktion, jedenfalls in einer $\begin{eqnarray*} \varepsilon \end{eqnarray*}$ -Umgebung um $\begin{eqnarray*} \alpha=0 \end{eqnarray*}$ , wobei das $\begin{eqnarray*} \varepsilon \end{eqnarray*}$ hier so klein gewählt ist, dass alle Funktionen über die wir summieren noch linear sind.

$\begin{eqnarray*} \sum_{i,\text{ Fall b)}}|y_i+a_{ij}\alpha|=p+q\cdot\alpha \end{eqnarray*}$ für $\begin{eqnarray*} |\alpha|<\varepsilon \end{eqnarray*}$

Ist diese lineare Funktion nun wachsend, wählen wir $\begin{eqnarray*} \alpha\in(0,\varepsilon) \end{eqnarray*}$ andernfalls $\begin{eqnarray*} \alpha\in (-\varepsilon,0) \end{eqnarray*}$ und jeweils wird $\begin{eqnarray*} \|A\tilde{x}(\alpha)\|_1>\|Ax\|_1 \end{eqnarray*}$ . Ein Widerspruch.

Tritt nur Fall a) auf, dann muss A die Nullmatrix sein.

Das hier war auch meine erste Idee, aber ich hatte die Hoffnung, dass sich das eleganter erledigen lässt. Bessere Vorschläge werden interessiert entgegengenommen.

11.01.2009, 01:36

tigerbine

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Also einfach ist die bestimmt nicht. Hab hier was vorliegen, was ich bis hier noch verstehe. Ist aber nicht mir entsprungen und auf die Idee so anzusetzen wäre ich auch nicht gekommen. Ähnelt das deiner Idee? Wink

Nun noch eine Frage, die gleich zeigt, wie sehr mir hier noch der durchblick fehlt. Könntest du diese Operatornorm mal für eine Beispielmatrix vorrechnen? Denn so richtig ist mir wohl noch nicht klar, wass durch die Darstellung der rechten Seite gewonnen wurde. Ups

Zitat:

Hier ist nicht wie bei den anderen Aufgaben zu dem Thema klar, wie sie am Ende zu berechnen sein wird. Es ist nur bekannt, dass es einen Vektor x gibt, dessen Einträge betragsmäßig 1 sind, so dass Gleichheit mit einer Vektornorm (Betragssummennorm).

Zunächst betrachtet man einmal die rechte Seite der Gleichung und definiert die Funktion

$\begin{eqnarray*} f:~[-1,1]^m \to \mathbb R,~\quad x \to \sum_{i=1}^n \begin{vmatrix}Ax \end{vmatrix} = \sum_{i=1}^n \begin{vmatrix} \sum_{k=1}^m a_{ik}x_k \end{vmatrix} \end{eqnarray*}$

Nun betrachten wir eine weitere Funktion. Dazu seinen $\begin{eqnarray*} x,y \in [-1,1]^m \end{eqnarray*}$ .

$\begin{eqnarray*} \varphi: ~[0,1] \to \mathbb R,~\quad \lambda \to f\Bigl(\lambda x + (1-\lambda)y\Bigr) \end{eqnarray*}$

Schauen wir uns diese Funktion etwas genauer an. Es ist

$\begin{eqnarray*} f\Bigl(\lambda x + (1-\lambda)y\Bigr) &&= \sum_{i=0}^n \begin{vmatrix} \sum_{k=1}^m a_{ik}(\lambda x_k + (1-\lambda)y_k) \end{vmatrix} \\&& = \sum_{i=0}^n \begin{vmatrix} \lambda \sum_{k=1}^m a_{ik}(x_k +y_k) + \sum_{k=1}^m a_{ik}x_k \end{vmatrix} \\&& = \sum_{i=0}^n \begin{vmatrix} \lambda a_i + b_i \end{vmatrix},~a_i,b_i \in \mathbb R \end{eqnarray*}$

Somit handelt es sich um die Summe von "linearen" Funktionen auf dem kompakten Intervall [0,1]. Die Summe stetiger Funktionen ist stetig und es gibt ein globales Maximum für ein $\begin{eqnarray*} \lambda ^* \in [0,1] \end{eqnarray*}$ . Nun nehmen wir an, dass gilt $\begin{eqnarray*} \lambda ^* \in (0,1) \end{eqnarray*}$ und führen dies zum Widerspruch.

Aufgrund der "linearen" Gestalt ist $\begin{eqnarray*} \varphi \end{eqnarray*}$ im Maximum nicht differenzierbar.

11.01.2009, 14:11

Reksilat

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Ist etwa die gleiche Idee, es geht darum, dass der Ausdruck eine Summe von Betragsfunktionen ist und diese sind lokal immer wachsend oder fallend.

Beispiel:
$\begin{eqnarray*} A= \begin{pmatrix} 1&3&0\\-2&2&0\\-5&+1&0\end{pmatrix} \end{eqnarray*}$
---------------------------------
Wir beginnen mit einem beliebigen Vektor, hier: $\begin{eqnarray*} x=(1/2,1/2,1/2) \end{eqnarray*}$
Dann ist $\begin{eqnarray*} \|Ax\|_1=2+0+2=4 \end{eqnarray*}$

Wir wollen zeigen, dass man alle Einträge des Vektors betragsmäßig auf 1 bringen kann, während sich dabei die Norm von $\begin{eqnarray*} Ax \end{eqnarray*}$ erhöht.

Setze $\begin{eqnarray*} \tilde{x}=\begin{pmatrix}1/2+\varepsilon \\ 1/2\\ 1/2\end{pmatrix} \end{eqnarray*}$
mit $\begin{eqnarray*} -3/2\leq \varepsilon\leq 1/2 \end{eqnarray*}$ , damit $\begin{eqnarray*} \|\tilde{x}\|_\infty\leq 1 \end{eqnarray*}$

Dann ist $\begin{eqnarray*} \|A\tilde{x}\|_1=|2+\varepsilon|+|-2\varepsilon|+|-2-5\varepsilon| \end{eqnarray*}$

Für alle $\begin{eqnarray*} -2/5\leq\varepsilon\leq 1/2 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} \|A\tilde{x}\|_1=2+\varepsilon+|2\varepsilon|+2+5\varepsilon \end{eqnarray*}$
und diese Funktion nimmt ihr Maximum in $\begin{eqnarray*} \varepsilon=1/2 \end{eqnarray*}$ an.

---------------------------------

Wir setzten $\begin{eqnarray*} x=(1,1/2,1/2) \end{eqnarray*}$ (also $\begin{eqnarray*} \|Ax\|_1=8 \end{eqnarray*}$ ) und fahren mit der zweiten Komponente fort:

Setze $\begin{eqnarray*} \tilde{x}=\begin{pmatrix}1\\1/2+\varepsilon \\ 1/2\end{pmatrix} \end{eqnarray*}$

mit $\begin{eqnarray*} -3/2\leq \varepsilon\leq 1/2 \end{eqnarray*}$ , damit $\begin{eqnarray*} \|\tilde{x}\|_\infty\leq 1 \end{eqnarray*}$

Dann ist $\begin{eqnarray*} \|A\tilde{x}\|_1=|5/2+3\varepsilon|+|-1+2\varepsilon|+|-9/2+\varepsilon| \end{eqnarray*}$

Für alle $\begin{eqnarray*} -5/6\leq\varepsilon\leq 1/2 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} \|A\tilde{x}\|_1=5/2+3\varepsilon+1-2\varepsilon+9/2-\varepsilon=8 \end{eqnarray*}$
Diese Funktion ist unabhängig von $\begin{eqnarray*} \varepsilon \end{eqnarray*}$ und wir können unter den gegebenen Restriktionen $\begin{eqnarray*} \varepsilon=1/2 \end{eqnarray*}$ wählen.

---------------------------------

Wir setzten $\begin{eqnarray*} x=(1,1,1/2) \end{eqnarray*}$ (also $\begin{eqnarray*} \|Ax\|_1=8 \end{eqnarray*}$ ) und fahren mit der dritten Komponente fort:

Wir man leicht sieht, ist es egal, wie wir die dritte Komponente wählen und somit ist z.B. $\begin{eqnarray*} x=(1,1,-1) \end{eqnarray*}$ ein Vektor, für den $\begin{eqnarray*} \|Ax\|_1\geq\|Ax_0\|_1 \end{eqnarray*}$ , mit $\begin{eqnarray*} x_0=(1/2,1/2,1/2) \end{eqnarray*}$ gilt und dessen Einträge alle betragsmäßig 1 sind.

Ausrechnen kann man diese Norm prinzipiell ja ganz leicht, da man nur $\begin{eqnarray*} \|Ax\|_1 \end{eqnarray*}$ für alle Vektoren $\begin{eqnarray*} x\in\{-1,1\}^n \end{eqnarray*}$ untersuchen muss.
Ich hoffe ich konnte Dir damit helfen. smile

Achtung: Das Verfahren ist nicht konstruktiv, es erläutert nur die Vorgehensweise beim obigen Beweis. Für $\begin{eqnarray*} x=(1,-1,1) \end{eqnarray*}$ wird der Wert $\begin{eqnarray*} \|Ax\|_1 \end{eqnarray*}$ beispielsweise noch größer als 8.

11.01.2009, 14:15

tigerbine

Auf diesen Beitrag antworten »

Ich sage schon mal danke, kann es aber erst heute Abend lesen. Wünsche Dir einen schönen Sonntag Wink

11.01.2009, 19:01

tigerbine

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Wie kommt man auf die Idee? Weil gilt:

$\begin{eqnarray*} \|A\|_{\infty \to 1} = \sup_{x \neq 0} \frac{\|A\|_1}{\|x\|_1} = \sup_{\|x\|_\infty=1} \|Ax\|_1 \end{eqnarray*}$

Somit wissen wir wegen $\begin{eqnarray*} \|x\|_\infty=1 \end{eqnarray*}$ , dass die Einträge von x in [-1,1] liegen und mindestens einer von 0 verschieden ist und den Betrag 1 hat.

Für die weitere Argumentation ist hier dein Zahlenbeispiel gut. Freude

Zitat:

Ausrechnen kann man diese Norm prinzipiell ja ganz leicht, da man nur $\begin{eqnarray*} \|Ax\|_1 \end{eqnarray*}$ für alle Vektoren $\begin{eqnarray*} x\in\{-1,1\}^n \end{eqnarray*}$ untersuchen muss.

Ok, den Gedanken hatte auch ich. War mir halt nicht sicher.

Wink

11.01.2009, 19:47

Reksilat

Auf diesen Beitrag antworten »

RE: Operatornorm (3)
Also letztlich geht man ja davon aus, dass $\begin{eqnarray*} x \end{eqnarray*}$ einer der Vektoren ist, für den $\begin{eqnarray*} \|A\|_{\infty\to 1}=\|Ax\|_1 \end{eqnarray*}$ gilt und zeigt, dass man dann diesen auch so wählen kann, dass alle Einträge betragsmäßig 1 sind, da sich mit der angegebenen Konstruktionsvorschrift der Wert $\begin{eqnarray*} \|Ax\|_1 \end{eqnarray*}$ nur vergrößert oder gleich bleibt.

Mein Beispiel ist übrigens keine Konstruktion des optimalen Werts, da wir ja von einem beliebigen Vektor ausgegangen sind. Es soll nur das Prinzip veranschaulichen.

Dass der erhaltene Vektor nicht optimal ist, sieht man, wenn man z.B. den Vektor $\begin{eqnarray*} x=(-1,1,1) \end{eqnarray*}$ betrachtet. (Muss ich auch oben noch ändern)

Neue Frage »

Antworten »

Operatornorm (3)

Verwandte Themen