cg-Verfahren: Abschätzung zeigen

25.05.2014, 13:05	mathNewton	Auf diesen Beitrag antworten »
Meine Frage: Hallo, ich sitze an einer Aufgabe an der ich leider nicht weiter weiß. Die Aufgabe lautet wie folgt: Gegeben sei ein lineares Gleichungssystem Ax=b mit einer symmetrischen positiv definiten Matrix $\begin{eqnarray} A\in\mathbb R^{N\times N} \end{eqnarray}$ und $\begin{eqnarray} x,b\in\mathbb R^{N} \end{eqnarray}$ . Über die Matrix A sei bekannt, dass die Eigenwerte im Intervall [7,28] liegen. Für das LGS Ax=b sollen so viele Iterationsschritte des cg-Verfahrens (ohne Vorkonditionierung) durchgeführt werden, dass die Abschätzung $\begin{eqnarray} \|x^{k}-x^{}\|_{A} < \epsilon \|x^{0}-x^{}\|_{A}, (0 < \epsilon <<1) \end{eqnarray}$ für die k-te Itererite erfüllt ist. Zeigen Sie, dass dies in exakter Arithmetik nach spätestens $\begin{eqnarray} k\geq \frac{log(2)-log(\epsilon)}{log(3)} \end{eqnarray}$ Schritten garantiert werden kann. So lautet die Aufgabe. Meine Ideen: Im Moment habe ich nicht wirklich eine Idee. Was ich gemacht habe ist mal die Ungleichung umzustellen zu $\begin{eqnarray} \frac{\|x^{k}-x^{}\|_{A}}{\|x^{0}-x^{}\|_{A}} < \epsilon \end{eqnarray}$ Darüber habe ich etwas nachgedacht in der Hoffnung mir würde etwas einfallen, jedoch ohne Erfolg. Ich würde mich freuen, wenn mir jemand dabei helfen könnte. Gruß mathNewton Zwei Beiträge zusammengefügt, damit Antwortzähler auf Null steht. Steffen Hi, ich denke an dieser Stelle könnte der folgende Satz hilfreich sein $\begin{eqnarray} \\|x_k-x\\|_A \le 2\left(\frac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\right)^k\\|x_{0}-x\\|_A \end{eqnarray}$ Die Kondition von A ist $\begin{eqnarray} \kappa(A) = \frac{\lambda_{max}}{\lambda_{min}} \end{eqnarray}$ bei symmetrischen und positiv definiten Matrizen. Leider weiß ich noch nicht inwiefern mir dies eine Hilfe in Bezug auf die Aufgabe sein könnte. Soll man vielleicht den Exponenten k abschätzen oder etwas anderes? Gruß mathNewton
27.05.2014, 10:57	Ändru	Auf diesen Beitrag antworten »
Hi, bist du denn schon auf die Idee eines Koeffzientenvergleichs gekommen (Deine Idee ist eigentlich genau das, nur etwas anders )? Du hast $\begin{eqnarray} \\| x_k - x \\|_{A} < \varepsilon \\| x_0 - x \\|_{A} \end{eqnarray}$ und $\begin{eqnarray} \\| x_k - x \\|_{A} \leq 2 { \left( \frac{\sqrt{k(A)} -1 }{\sqrt{k(A)} + 1} \right)}^k \\| x_0 - x \\|_{A} \end{eqnarray}$ und nun nimmst du einfach an (der Zugang ist einfach), dass gilt: $\begin{eqnarray} 2 { \left( \frac{\sqrt{k(A)} -1 }{\sqrt{k(A)} + 1} \right)}^k < \varepsilon \end{eqnarray}$ und dann kannst du dir ueberlegen, was dir das hilft, dass du weisst, dass die Eigenwerte in $\begin{eqnarray} [7, 28] \end{eqnarray}$ liegen (Satz von Gerschgorin). Das sollte dir etwas auf die Spruenge helfen. Zusatz: Du kannst dir auch/zusaetzlich die A-Priori-Fehlerabschätzung anschauen... das ist eigentlich der gleich Zugang. Gruesse

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »