Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis Zeilensummennorm

Beweis Zeilensummennorm

Universität / Fachhochschule

Matrizenrechnung

Tags: Matrixnorm, Zeilensummennorm

Mo007 aktiv_icon

16:24 Uhr, 30.04.2016

Hallo allerseits!

Ich stehe im Moment vor der Aufgabe, einen mir vorgegebenen mathematischen Beweis genau erläutern zu müssen. Da ich den Beweis aber nicht wirklich verstehe, hab ich damit ziemliche Probleme. Aber vielleicht hier zunächst die genaue Aufgabe:

Für

A = (a_{j k}) \in K^{n x n}

gilt:

∥ A ∥_{\infty} = max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣

(Zeilensummennorm). Formulieren Sie den Beweis dieser Identität ausführlicher aus. Formulieren Sie dazu die gegebenen Argumente in eigenen Worten und geben Sie insbesondere eine kurze Begründung für jedes auftretende Gleichheits-/Ungleichheitszeichen.

Und hier der vorgegebene Beweis:

Für

x \in K^{n}

gilt:

∥ A x ∥_{\infty} = max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ \leq max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣ ∣ x_{k} ∣ \leq (m a x_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣) ∥ x ∥_{\infty}

.

Und für den Nachweis der umgekehrten Abschätzung sei

j \in {1, 2, . . ., n}

beliebig aber fest. Für

x = (x_{k}) \in K^{n}

mit

x_{k} = {\binom{∣ a_{j k} ∣ / a_{j k}, a_{j k} \neq 0}{1, s o n s t}

(k = 1, 2, . . ., n)

gilt dann

∥ x ∥_{\infty} = 1

und somit:

∥ A ∥_{\infty} \geq ∥ A x ∥_{\infty} \geq ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ = \sum_{k = 1}^{n} ∣ a_{j k} ∣

, da

a_{j k} x_{k} = ∣ a_{j k} ∣

. Aufgrund der freien Wahl des Indexes

j = {1, 2, . . ., n}

in der letzten Abschätzung folgt die Darstellung für

∥ A ∥_{\infty}

.

Tja, so richtig viele Ideen habe ich zu der Aufgabe ehrlich gesagt noch nicht aber ich versuch mal meine paar Gedanken aufzuschreiben:

Die gegebenen Argumente sind A als nxn-Matrix, j als Zeilenindex, k als Spaltenindex und x als Vektor. Der ganze Beweis ist nach dem Prinzip

a < b

und

a > b

folgt

a = b

. Aber die ganzen (Un-)Gleichheiten, zumindest in der ersten Abschätzung, sind mir leider überhaupt nicht klar und ich wäre da wirklich für jede Hilfe dankbar.

Vielen Dank im Voraus und schöne Grüße

Mo

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

pwmeyer aktiv_icon

16:45 Uhr, 30.04.2016

Hallo,

wenn Du so allgemein fragst, sollen wir Dir hier die Hausaufgabe erledigen?

Versuch doch mal, etwas selbst zu machen. Die erste Abschätzung bezieht sich auf den Absolutbetrag einer Summe. Hast Du da nicht vielleicht eine Idee?

Gruß pwm

Mo007 aktiv_icon

21:56 Uhr, 30.04.2016

Hallo pwm,

erstmal Danke für deine Antwort. Ich erwarte nicht, dass ihr meine Aufgaben löst aber ich erhoffe mir irgendwelche Tipps und Anregungen und dafür ist dieses Forum doch wohl gedacht. Ich steh halt mit solchen Abschätzungen absolut auf dem Kriegsfuß und weiß mir da gerade nicht zu helfen. Egal, zurück zum eigentlichen Thema:

Beim Absolutbetrag einer Summe fällt mir die Dreiecksungleichung ein aber ehrlich gesagt sehe ich die in diesem Zusammenhang einfach nicht. In dem Ausdruck

max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣

sind

a_{j k}

und

x_{k}

doch multiplikativ verknüpft. Wieso darf ich das dann trotzdem so auseinander ziehen? Ich kenne für Summen nur die Ungleichung

∣ \sum_{k = 1}^{n} x_{k} ∣ \leq \sum_{k = 1}^{n} ∣ x_{k} ∣

. Aber das ist (zumindest aus meiner Sicht) ja irgendwie nicht das gleiche wie in dem Beweis.

Ich bin mir auch nicht sicher, ob ich die erste Gleichung überhaupt richtig verstanden hab. Vielleicht sollten wir da erstmal anfangen? Ich weiß, dass für induzierte Matrixnormen allgemein gilt:

∥ A ∥ = max_{0 \neq x \in K^{n}} \frac{∥ A x ∥}{∥ x ∥} = max_{0 \neq x \in K^{n}, ∥ x ∥ = 1} ∥ A x ∥

. Daraus ergibt sich ja schon mal, dass in dem Ausdruck

max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣

das

x_{k}

auftaucht. Aber wie kommt man von da zu dem Betrag der Summe? Das leuchtet mir nicht ein. Es muss aber wohl irgendwas damit zu tun haben, dass diese Matrixnorm durch eine Vektornorm induziert ist, oder?

Was die Abschätzung in die andere Richtung angeht, hab ich mir bisher folgendes zusammen gereimt:

∥ A ∥_{\infty} \geq ∥ A x ∥_{\infty}

-> Hier gilt nach meinen obigen Überlegungen eigentlich nur

" = "

falls

0 \neq x \in K^{n}

und

∥ x ∥ = 1

gilt. Wenn aber z. B.

0 = x \in K^{n}

, dann gilt natürlich

∥ A ∥_{\infty} > ∥ A x ∥_{\infty}

, also insgesamt

∥ A ∥_{\infty} \geq ∥ A x ∥_{\infty}

∥ A x ∥_{\infty} \geq ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣

-> Dies folgt direkt aus der in der

\leq

-Abschätzung verwendeten Identität

∥ A x ∥_{\infty} = max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣

, denn

max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ \geq ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣

gilt offensichtlich.

∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ = \sum_{k = 1}^{n} ∣ a_{j k} ∣

-> Aus der Definition von

x_{k}

folgt hier

∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ = ∣ \sum_{k = 1}^{n} a_{j k} ∣

. Und weil ja allgemein für Summen die Ungleichung

∣ \sum_{k = 1}^{n} x_{k} ∣ \leq \sum_{k = 1}^{n} ∣ x_{k} ∣

gilt, folgt direkt

∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ = ∣ \sum_{k = 1}^{n} a_{j k} ∣ = \sum_{k = 1}^{n} ∣ a_{j k} ∣

.

Ist das soweit richtig?

Schöne Grüße

Mo

pwmeyer aktiv_icon

11:46 Uhr, 01.05.2016

Hallo,

"Aber wie kommt man von da zu dem Betrag der Summe? Das leuchtet mir nicht ein." Das ist doch mal eine konkrete Frage.

Zu berechnen ist

{| | A x | |}_{\infty}

. y:=Ax ist ein Vektor mit den Komponenten

y_{j} = \sum_{k = 1}^{n} a_{j, k} \cdot x_{k}

Also ist

{| | A \cdot x | |}_{\infty} = max_{j = 1 . . n} | y_{j} | = = max_{j = 1 . . n} | \sum_{k = 1}^{n} a_{j, k} \cdot x_{k} |

und mit der Dreiecksungleichung:

| \sum_{k = 1}^{n} a_{j, k} \cdot x_{k} | \leq \sum_{k = 1}^{n} | a_{j, k} \cdot x_{k} |

Gruß pwm

Mo007 aktiv_icon

16:32 Uhr, 01.05.2016

Hallo pwm,

mal schauen, ob ich deine Antwort richtig verstanden hab: Man setzt

y = A x

und dann wird statt

∥ A x ∥_{\infty}

einfach

∥ y ∥_{\infty}

betrachtet und da

y

ja ein Vektor ist, kann man die Definition der Unendlichnorm für Vektoren anwenden. Dann schätzt man mit Hilfe der Dreiecksungleichung wie folgt ab:

max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ \leq max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} x_{k} ∣

. Hierauf lässt sich nun noch die Rechenregel für Beträge

∣ a b ∣ = ∣ a ∣ ∣ b ∣

anwenden und man erhält so

max_{j = 1, . . ., n} ∣ \sum_{k = 1}^{n} a_{j k} x_{k} ∣ \leq max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣ ∣ x_{k} ∣

.

Ok, ich denke bis hierhin hab ich es jetzt verstanden. Auf die Idee

y = A x

zu setzen, wäre ich allerdings nicht selbst gekommen. Vielen Dank für diese Erklärung! Ich versuch mal weiter zu machen:

Im nächsten Schritt der Abschätzung wurde

∥ x ∥_{\infty}

aus der Summe raus gezogen, da ja

x

ein Vektor ist und für diesen ja

∥ x ∥_{\infty} = max_{k = 1, . . ., n} ∣ x_{k} ∣

gilt. Was ich hier aber nicht verstehe ist, warum

a_{j, k}

und

x_{k}

voneinander getrennt werden können. Allgemein gilt doch

\sum_{k = 1}^{n} a_{k} x_{k} \neq \sum_{k = 1}^{n} a_{k} * \sum_{k = 1}^{n} x_{k}

. Aber wir setzen ja hier nicht gleich, sondern schätzen ab. Ist genau das der Trick? Also so in der Art:

max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j, k} ∣ ∣ x_{k} ∣ \leq max_{j = 1, . . ., n} (\sum_{k = 1}^{n} ∣ a_{j, k} ∣ * \sum_{k = 1}^{n} ∣ x_{k} ∣)

???

Aber woher weiß ich denn, dass

max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j, k} ∣ ∣ x_{k} ∣ \leq max_{j = 1, . . ., n} (\sum_{k = 1}^{n} ∣ a_{j, k} ∣ * \sum_{k = 1}^{n} ∣ x_{k} ∣)

auch wirklich gilt? Könnte es nicht auch umgekehrt sein? Und außerdem stört ja dann noch das Summenzeichen bei

∣ x_{k} ∣

... :-(

Oder kann ich hier

∣ x_{k} ∣

einfach als Konstante betrachten und aus der Summe raus ziehen, weil es ja um das Maximum von

∣ x_{k} ∣

geht?

Schöne Grüße

Mo

Mo007 aktiv_icon

17:06 Uhr, 01.05.2016

Moment mal... Ich habe glaube ich meinen Denkfehler gerade selbst erkannt. Hier wird ja nur über den Index j maximiert und gar nicht über k!

Also der Ausdruck

\sum_{k = 1}^{n} ∣ a_{j k} ∣ ∣ x_{k} ∣

steht ja dafür, dass die Beträge der Matrixeinträge

a_{j, k}

aus der jeweiligen Zeile j mit dem Betrag des Eintrags k aus dem Vektor x multipliziert werden und hierüber wird dann jeweils die Summe gebildet. Aus diesen einzelnen Summen wird dann das Maximum gesucht, also

max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣ ∣ x_{k} ∣

.

Wenn ich jetzt aber erst die Beträge der Matrixeinträge aufsummiere, aus diesen Summen das Maxium suche und anschließend nochmal mit

max_{k = 1, . . ., n} ∣ x_{k} ∣ = ∥ x_{k} ∥_{\infty}

multipliziere, muss ja

max_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣ ∣ x_{k} ∣ \leq (m a x_{j = 1, . . ., n} \sum_{k = 1}^{n} ∣ a_{j k} ∣) ∥ x ∥_{\infty}

gelten, denn ich multipliziere hier ja dann ausschließlich mit

max_{k = 1, . . ., n} ∣ x_{k} ∣

statt nur mit

∣ x_{k} ∣

.

Habe ich das jetzt richtig verstanden?

Schöne Grüße

Mo

pwmeyer aktiv_icon

19:15 Uhr, 01.05.2016

Hallo,

ich würde es so formulieren. Ween der Definition von

{| | . | |}_{\infty}

gilt für jedes

k : | x_{k} | \leq {| | x | |}_{\infty},

also

\sum_{k = 1}^{n} | a_{j k} | | x_{k} | \leq \sum_{k = 1}^{n} | a_{j k} | {| | x | |}_{\infty} = (\sum_{k = 1}^{n} | a_{j k} |) {| | x | |}_{\infty}

Gruß pwm

Mo007 aktiv_icon

20:58 Uhr, 01.05.2016

Hallo pwm,

ok, das hab ich jetzt verstanden. Du hast es halt nur nochmal schön sauber formuliert. :-)

Jetzt nochmal zu der Abschätzung in die andere Richtung. Waren meine Gedankengänge dazu richtig oder hab ich da noch irgendwo einen Denkfehler drin? Unsicher bin ich mir z. B. was die letzte Gleichheit angeht:

Ich hatte erst gedacht, dass man