[Numerik I] - Übung 5 *

Neue Frage »

12.01.2009, 01:04

tigerbine

Auf diesen Beitrag antworten »

Aufgaben - Teil 5

Newton-Verfahren
Vereinfachtes Newton-Verfahren
Newton Verfahren für Gleichungssysteme
Spektralradius und Matrixnorm
Eigenwerte einer symmetrischen Tridiagonalmatrix

12.01.2009, 01:15

tigerbine

Auf diesen Beitrag antworten »

5.1 Newton-Verfahren
Als Funktion wählt man nach der Methode von Heron:

$\begin{eqnarray*} f(x)=x^2-2 \end{eqnarray*}$

Es ergibt sich somit die Newtoniteration:

$\begin{eqnarray*} x_{k+1}=x_k - \frac{x^2-2}{2x} \end{eqnarray*}$

Der Startwert lautet

$\begin{eqnarray*} x_0=1.4 \end{eqnarray*}$

Mit den Taschenrechner ergibt sich dann:

$\begin{eqnarray*} x_1=1.4 - \frac{1.96-2}{2.8} = 1.414285714 \end{eqnarray*}$

$\begin{eqnarray*} x_2=1.414285714 - \frac{2.000204082-2}{2.828571429} = 1.414213564 \end{eqnarray*}$

$\begin{eqnarray*} \sqrt{2}-x_2=-0.000000001 \end{eqnarray*}$

12.01.2009, 01:17

tigerbine

Auf diesen Beitrag antworten »

5.2 Vereinfachtes Newton-Verfahren
Damit das Newton-Verfahren im Mehrdimensionalen durchführbar ist, darf die JacobiMatrix in der Lösung x* nicht singulär sein. Das entspricht der Forderung im Eindimensionalen, dass die erste Ableitung von f in x* nicht verschwindet. Aus Stetigkeitsgründen gab es dann auch eine Umgebung, in der f' ebenfalls von Null verschieden ist.

Können wir dies auf das Mehrdimensionale übertragen? Gibt es also eine Umgebung von x*, so dass J(x) dort regulär ist? Wir werden dazu das Banach-Lemma (oder Störungs-Lemma) benötigen.

Wählen wir nun x nun nahe genug bei x*, so können wir auf Grund der Stetigkeit folgende Abschätzung formulieren.

$\begin{eqnarray*} \|J(x^*)-J(x)\| \leq \frac{1}{2~\|J(x^*)^{-1}\|} \end{eqnarray*}$

Dieses formen wir nun um und nutzen zu unteren Abschätzung noch die Dreiecksungleichung für Normen:

$\begin{eqnarray*} \|\underbrace{I- J(x^*)^{-1}J(x)}_{:=-B}\|\leq \|J(x^*)^{-1}\|\cdot \|J(x^*)-J(x)\| \leq \frac{1}{2} \end{eqnarray*}$ (*)

Somit sind die Voraussetzung für das Lemma erfüllt, denn die Normen von B und (-B) sind gleich. J ist also in einer Umgebung von x* regulär. Nun wollen wir zeigen, dass es dann auch eine Konstant c>0 gibt, so dass für alle x in dieser Umgebung gilt:

$\begin{eqnarray*} \|J(x)^{-1}\| < c \end{eqnarray*}$

Wieder benötigen wir das Lemma und mit der dort vorhandenen Abschätzung:

$\begin{eqnarray*} \|(I+B)^{-1}\| \leq \frac{1}{1-\|B\|} \end{eqnarray*}$

$\begin{eqnarray*} \|(I-(-B))^{-1}\| \leq \frac{1}{1-\|B\|} \end{eqnarray*}$

$\begin{eqnarray*} \|(I-(-B))^{-1}\| \leq \frac{1}{1-\|I- J(x^*)^{-1}J(x)\|} \end{eqnarray*}$

$\begin{eqnarray*} \|(I-(-B))^{-1}\|\cdot \|J(x^*)^{-1}\|\leq \frac{\|J(x^*)^{-1}\|}{1-\|I- J(x^*)^{-1}J(x)\|} \end{eqnarray*}$

Nun ist das gewünschte nur noch zwei Schritte entfernt. Gilt doch

$\begin{eqnarray*} (I-(-B))^{-1} = (J(x^*)^{-1}J(x))^{-1} = J(x^*)J(x)^{-1} \end{eqnarray*}$

Mit der Dreiecksregel folgt:

$\begin{eqnarray*} \|J(x)^{-1}\| \leq \frac{\|J(x^*)^{-1}\|}{1-\|I- J(x^*)^{-1}J(x)\|} \end{eqnarray*}$

Nun hatten wir am Anfang die Umgebung so gewählt, dass (*) gilt. Somit liegt der Nenner rechts in [0.5,1] und wir erhalten:

$\begin{eqnarray*} \|J(x)^{-1}\| \leq 2 \|J(x^*)^{-1} \| =:c \end{eqnarray*}$

Damit ist Verfahren wohldefiniert. Es muss nun noch die Konvergenz untersucht werden. Dies wird hier nicht ausgeführt.

12.01.2009, 01:18

tigerbine

Auf diesen Beitrag antworten »

5.3 Newton Verfahren für LGS
Der bekannte Spezialfall ist n=1. Dann handelt es sich um eine Polynomfunktion ersten Grades und es ergibt sich

$\begin{eqnarray*} x_1=x_0-\frac{ax_0+b}{a} = -\frac{b}{a} \end{eqnarray*}$

Und man hat die Lösung bereits im ersten Schritt erhalten. Gilt dies nun auch für Affine Lineare Funktionen?

$\begin{eqnarray*} f:~\mathbb R^n \to \mathbb R^n \end{eqnarray*}$

$\begin{eqnarray*} f(x):=Ax-b \end{eqnarray*}$

Die Ableitung bildet hier die Jacobimatrix, also die Matrix der partiellen Ableitungen. Die Division wird durch die Invertierung der Matrix ersetzt. Wir erhalten (Iteration im Gegensatz zum Vektoreintrag im Exponenten dargestellt )

$\begin{eqnarray*} x^{(k+1)} = x^{(k)} - \Bigl(J(x^{(k)})\Bigr)^{-1}f(x^{(k)}) \end{eqnarray*}$

Bestimmen wir zunächst die Jacobi-Matrix:

Zitat:

$\begin{eqnarray*} J(x):=\frac{\partial f_i}{\partial x_j} =\begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \ldots & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \ldots & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \ldots & \frac{\partial f_n}{\partial x_n}\end{pmatrix} \end{eqnarray*}$

Wie lauten hier die Funktionen $\begin{eqnarray*} f_i \end{eqnarray*}$ ?

$\begin{eqnarray*} f_i(x)=\Bigl(\sum_{k=1}^n a_{ik}x_k\Bigr) -b_i \end{eqnarray*}$

$\begin{eqnarray*} \frac{\partial f_i}{\partial x_j} = a_{ij} \end{eqnarray*}$

Somit gilt:

$\begin{eqnarray*} J(x)=A \end{eqnarray*}$

Und der erste Newtonschritt:

$\begin{eqnarray*} x^{(1)} = x^{(0)} - A^{-1}(Ax^{(0)}-b) = x^{(0)}-x^{(0)}+A^{-1}b=A^{-1}b \end{eqnarray*}$

was die offensichtliche Lösung des Ausgangsproblems bereits im ersten Iterationsschritt darstellt. Das ist zwar theoretisch schön, hilft uns im Grunde bei dem Ausgangsproblem nicht weiter, da gerade das schwierige die Bestimmung einer Inversen Matrix ist.

12.01.2009, 01:18

tigerbine

Auf diesen Beitrag antworten »

5.4 Spektralradius und Matrixnorm
Es sei nun $\begin{eqnarray*} \lambda \end{eqnarray*}$ ein Eigenwert von A mit zugehörigem Eigenvektor v. So gilt:

$\begin{eqnarray*} Av = \lambda v \end{eqnarray*}$

Wenden wir nun die gegebene Vektornorm darauf an, so erhalten wir.

$\begin{eqnarray*} \|Av\| = \|\lambda v\| \end{eqnarray*}$

$\begin{eqnarray*} \|Av\| = |\lambda| \cdot \| v\| \end{eqnarray*}$

Aus der Veträglichkeit mit der Matrixnorm ergibt sich:

$\begin{eqnarray*} \|A\|_M \|v\| \geq |\lambda| \cdot \| v\| \end{eqnarray*}$

Somit folgt aus

$\begin{eqnarray*} \|A\|_M \geq |\lambda| \end{eqnarray*}$

schließlich die Behauptung:

$\begin{eqnarray*} \rho(A) \leq \|A\|_M \end{eqnarray*}$

12.01.2009, 01:20

tigerbine

Auf diesen Beitrag antworten »

5.5 Eigenwerte einer symmetrischen Tridiagonalmatrix
Um die Eigenwerte bestimmen können, benötigen wir das charakteristische Polynom. Dieses ist wie folgt definiert (je nach Literatur !)

$\begin{eqnarray*} \chi_n(A_n)=\det(A_n-I_nx) \end{eqnarray*}$

Im folgenden wollen wir eine Rekursionsformel für den speziellen Fall einer symmetrischen Tridiagonalmatrix nachweisen. Die Erläuterungen/Bezeichnungen weichen hier nun je nach Literatur ab, vgl. dazu G. Opfer - Numerische Mathematik für Einsteiger und G. Fischer - Lineare Algebra), die Idee ist jedoch immer gleich.

Definieren wir uns nun die Startpolynome:

$\begin{eqnarray*} p_0(x)=0 \end{eqnarray*}$

$\begin{eqnarray*} p_1(x)=(a_1-x)=\chi_1(A_1) \end{eqnarray*}$

Für n=2 erhalten wir:

$\begin{eqnarray*} \chi_2(A_2)=\begin{vmatrix}a_1-x & b_2 \\ b_2 & a_2-x \end{vmatrix} \end{eqnarray*}$

Entwickelt man die Determinante nach der letzten Zeile, so ergibt sich:

$\begin{eqnarray*} \chi_2(A_2) &&=(-1)^{2+2}\cdot (a_2-x) \cdot |a_1-x| + (-1)^(1+2)\cdot b_2 \cdot |b_2|\\ &&=(a_2-x) \cdot (a_1-x) -b_2^2 \cdot 1\\ && =(a_2-x)p_1-b^2\cdot p_0 \\&&=p_2(x) \end{eqnarray*}$

Man erkennt also die gewünschte Rekursionsformel. Nun beweisen wir das für allgemeines n nach dem gleichen Prinzip. Der Induktionsanfang ist gemacht. Sei nun die Formel richtig für (i-1), so folgt wenn man erneut nach der letzten Spalte entwickelt unter erneuter Entwicklung nach der letzen Spalte die Behauptung. Veranschaulicht für n=4:

$\begin{eqnarray*} \begin{vmatrix}a_1-x & b_2 &0 \\ b_2 & a_2-x & b_3 \\ 0&0&b_4 \end{vmatrix} =(-1)^{3+3} b_4 \cdot \begin{vmatrix}a_1-x & b_2 \\ b_2 & a_2-x\end{vmatrix} + (-1)^{2+3} \cdot \begin{vmatrix}a_1-x & b_2 \\ 0 & 0\end{vmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \chi(A_i) &&= (-1)^{i+i}(a_i-x) \det(A_{i-1}-I_{i-1}x) + (-1)^{(i+(i-1))} b_{i} \cdot \Bigl((-1)^{(i-1)+(i-1) } \cdot b_{i} \cdot \det(A_{i-2}-I_{i-2}x) + 0\Bigr) \\&& = (a_i-x)\cdot \chi(A_{i-1})-b_i^2\cdot \chi(A_{i-2}) \\&&=(a_i-x)\cdot p_{i-1}(x)-b_i^2\cdot p_{i-2}(x) \end{eqnarray*}$

Da die Matrix symmetrisch ist, hat sie nur reelle Eigenwerte, somit hat $\begin{eqnarray*} p_n \end{eqnarray*}$ nur reelle Nullstellen. Diese könnten wir nun mit den Newton Verfahren approximieren.

$\begin{eqnarray*} x_{k+1}=x_k-\frac{p_n(x)}{p_n'(x)} \end{eqnarray*}$

Für eine Startwertsuche bemühen wir die vorherige Aufgabe, die uns den Spektralradius abschätzen lässt.

31.01.2009, 00:06

tigerbine

Auf diesen Beitrag antworten »

Hier geht es weiter: [Numerik I] - Übung 6 *

Neue Frage »

Antworten »

[Numerik I] - Übung 5 *

Verwandte Themen