Koeffizientenmatrix Spline Interpolation, Abschätzung

15.01.2010, 16:34

mhansen

Koeffizientenmatrix Spline Interpolation, Abschätzung

Hallo,

im Rahmen der Spline Interpolation (daher der Titel, auch wenn die Fragestellung an sich kaum etwas damit zu tun hat) soll ich zeigen das für folgende Matrix $\begin{eqnarray*} A \in \mathbb R^{n\times n} \end{eqnarray*}$ mit

$\begin{eqnarray*} A = \begin{pmatrix} 4 & 2 & \\ 1 & 4 & 1 \\ & \ddots & \ddots & \ddots \\ && 1 & 4 & 1 \\ &&& 2 & 4 \end{pmatrix} \end{eqnarray*}$

die Abschätzung $\begin{eqnarray*} \langle x, Ax \rangle_2 \geq \frac{3}{2} \| x \|^2_2 \end{eqnarray*}$ f.a. $\begin{eqnarray*} x \in \mathbb R^n \end{eqnarray*}$ gilt.

Mein erster Ansatz war eine vollständige Induktion, allerdings bekommt man im Schritt dann Probleme, da es nicht ohne Weiteres möglich ist die Induktionannahme anzuwenden. Man würde ja z.B versuchen die 2 4 der (n+1)ten Zeile "irgendwie" in die n-te Zeile zu tauschen, dabei geht dann aber der Rest ziemlich kaputt.

Mein nächster Ansatz war es einfach mal direkt abzuschätzen: Rechnet man das Skalarprodukt links mal etwas aus erhält man zunächst:

$\begin{eqnarray*} 4\sum\limits_{i=1}^n x^2_i + \sum\limits_{i=2}^{n-1} ( x_i x_{i-1} + x_i x_{i+1} ) + 2(x_1 x_2 + x_n x_{n-1}) \end{eqnarray*}$

Der Term ganz links ist schon bereits die quadrierte Norm * 4 und damit schon größer, der Rest macht mir allerdings Kopfschmerzen.

Ein Tipp wie man den Rest vielleicht weiter abschätzen könnte wäre hilfreich. Oder gibt es möglicherweise einen sehr viel eleganteren Weg das Ganze zu zeigen?

Viele Grüße
mhansen

15.01.2010, 22:34

tigerbine

Auf diesen Beitrag antworten »

RE: Koeffizientenmatrix Spline Interpolation, Abschätzung
Da es mehr eine Teilfrage der LinA ist, verschiebe ich. Dann finden sich auch mehr Helfer. Augenzwinkern

Ich kann leider nicht viel zur Lösung beitragen. Mir wäre als Gedanke nur zu gekommen, dass man mit den Gerschgorin-Kreisen sieht, dass A nur positive Eigenwerte hat. Zumden noch symmetrisch (Korrektur: Ist sie nicht. Post ignorieren. :-)). Es müsste eine Cholesky Zerlegung geben.

$\begin{eqnarray*} \langle x,Ax \rangle = x^TAx = x^TL^TLx = (Lx)^TLx = \langle Lx,Lx\rangle \end{eqnarray*}$

Ob und wie einen das weiter bringt weiß ich gerade nicht. Augenzwinkern

16.01.2010, 00:34

mhansen

Auf diesen Beitrag antworten »

Möglicherweise stehe ich gerade auf 'nem Schlauch, aber die ist doch nicht symmetrisch? Aber Zerlegen könnte vielleicht zu was führen, QR sollte ja auf jeden Fall drin sein. Mal morgen drüber schauen was dabei rumkommt.

Diese Gerschgorin-Kreise sind mir jetzt direkt kein Begriff (kurz mal bei wiki diagonal durchgelesen), ich vermute mal sowas ist nicht unbedingt Bestandteil der üblichen LA1+2 / Analysis 1+2 Grundvorlesungen oder? Denn "nur" diese setzt die Numerikvorlesung, aus der diese Aufgabe stammt voraus, daher denke ich mal derart "ausgeflippte Dinge" werden nicht als Lösungsweg angedacht gewesen sein

(Im Eingangspost ist btw trotz sorgfältiger Prüfung noch ein typo, in der letzten Formel sollte x_n-1 statt x_n+1 stehen)

Edit: Hab mich schon gewundert. Das x_0 ist auch falsch. Korrigiert! Gruß, Reksilat.

16.01.2010, 00:53

Reksilat

Auf diesen Beitrag antworten »

Es ist doch allgemein $\begin{eqnarray*} x_i^2+2x_{i}x_{i+1}+x_{i+1}^2\geq 0 \end{eqnarray*}$ . (Binomische Formel)
Damit solltest Du mit Deiner direkten Abschätzung ans Ziel kommen.

Gruß,
Reksilat.

16.01.2010, 09:31

tigerbine

Auf diesen Beitrag antworten »

Ups. Man kann sich so vieles schönreden. Und böse

dass ich mal wieder auf den maltab-befehl reingefallen bin, der sich einfach nur ein Dreieck anschaut und dann Symmetrie annimmt. Sorry. Ups

16.01.2010, 15:46

mhansen

Auf diesen Beitrag antworten »

Mal schauen:

$\begin{eqnarray*} 4 \sum\limits_{i=1}^n x^2_i + 2(x_1 x_2 + x_{n-1} x_n) + \sum\limits_{i=2}^{n-1} x_i x_{i-1} + x_i x_{i+1} \end{eqnarray*}$

da könnte ich jetzt aus der hinteren Summe ersten und letzten Summanden in den zweiten Term reinpacken und jeweils innerhalb der Summe den hinteren i-ten mit dem vorderen i+1-ten zusammenfassen, wäre:

$\begin{eqnarray*} 4 \sum\limits_{i=1}^n x^2_i + 3(x_1 x_2 + x_{n-1} x_n) + 2 \sum\limits_{i=2}^{n-1} x_i x_{i+1} \end{eqnarray*}$

Jetzt von der rechten Seite durch 3/2 teilen und den mittleren Term (da steht jetzt passend schon die 2 vor) mit - rüber und als binomische Formel umschreiben

$\begin{eqnarray*} \frac{8}{3} \sum\limits_{i=1}^n x^2_i +\frac{4}{3} \sum\limits_{i=2}^{n-1} x_i x_{i+1} \geq (x_1 - x_2)^2 + (x_{n-1} - x_n)^2 + \sum\limits_{i=2}^{n-1} x_i^2 \end{eqnarray*}$

Soweit noch richtig oder? (Also zumindest nicht verrechnet)

Die Quadrate rechts passen ja schon halbwegs zu den gemischten Termen links, nur die Vorfaktoren sind nicht passend für die binomische Formel, würde man das noch hinbekommen hätte man ja schon sowas wie "irgendwas >= 0". Alternativ würde ja schon reichen wenn es eine Abschätzung für die einzelnen gemischten Terme gegen ihre Quadrate gibt oder sowas.

Sieht da jemand wie man weiter kommen könnte oder bin ich auf dem komplett falschen Dampfer? :-)

16.01.2010, 16:34

Reksilat

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} 4 \sum\limits_{i=1}^n x^2_i + 3(x_1 x_2 + x_{n-1} x_n) + 2 \sum\limits_{i=2}^{n-1} x_i x_{i+1} \end{eqnarray*}$

Das sieht schon mal gut aus, aber danach wird es unübersichtlich. Du musst Dich von den Summenformeln wohl etwas verabschieden und das etwas ausführlicher aufschreiben und passend zusammenfassen. Ich habe die binomische Formel auch genau so hingeschrieben, wie sie benötigt wird.
Versuche einfach zu zeigen, dass:
$\begin{eqnarray*} \frac{5}{2} \sum\limits_{i=1}^n x^2_i + 3(x_1 x_2 + x_{n-1} x_n) + 2 \sum\limits_{i=2}^{n-1} x_i x_{i+1}\geq 0 \end{eqnarray*}$ ist

17.01.2010, 19:47

mhansen

Auf diesen Beitrag antworten »

Ich vermute ich habs jetzt mit dem obigen Hinweis verwirrt

die vorderen Quadrate auseinander ziehen zu sowas wie:

$\begin{eqnarray*} \frac{1}{2} \sum\limits_{i=1}^n x_i^2 + \sum\limits_{i=1}^n x_i^2 + \sum\limits_{i=1}^n x_i^2 \end{eqnarray*}$

Damit bekommt man die Summe hinten mit den gemischten Termen jeweils zu binomischen Formeln, ein paar Quadrate verbraucht man nicht, mit denen kann man den mittleren Term dann noch wegdiskutieren, am Ende hat man auf jeden Fall nur noch jede Menge Quadrate die dann >= erfüllen.

Ist das zirka was du meintest Reksilat?

17.01.2010, 19:49

Reksilat

Auf diesen Beitrag antworten »

Ja, so funktioniert's! Freude

20.01.2010, 16:39

mhansen

Auf diesen Beitrag antworten »

Abschließend würde ich jetzt gerne aus der pos. Definitheit noch Regularität folgern (mein Hiwi möchte es gern explizit haben :o )

Reicht es jetzt zu sagen wegen <x,Ax> > 0 gilt Ax = 0 gdw. x = 0 und damit Kern (A) nur den Nullvektor enthält? Damit hätte man per Dimensionssatz dann das der Bildraum die volle Dimension hat, A also vollen Rang und damit bijektiv (was schon äquivalent zu regulär ist)? Oder fehlt da noch irgendwo ein Argument?

TiA
mhansen

20.01.2010, 16:45

Reksilat

Auf diesen Beitrag antworten »

Passt schon. Ist $\begin{eqnarray*} \langle Ax,x\rangle>0 \end{eqnarray*}$ so muss schließlich insbesondere $\begin{eqnarray*} Ax\neq 0 \end{eqnarray*}$ sein.

Gruß,
Reksilat.

Neue Frage »

Antworten »

Koeffizientenmatrix Spline Interpolation, Abschätzung

Verwandte Themen