Folien Verbesserungsvorschläge

Bachelor Algorithmik kontinuierlicher Systeme
21

Foliensatz 15 Seite 19 und 25: Jacobi Verfahren Algorithmus

  1. Das sind zwei verschiedene Algorithmen:
    Auf Seite 1 ist die Initialisierung von xnew innerhalb der Schleife. Das kann eigentlich nicht stimmen weil man nach jeder Schleife die alten Werte mit 0en ueberschreibt.

  2. Auf Seite 19 sollte denke ich noch am Ende der while Schleife noch ein

x = x_new

stehen, sonst beginnt man nach jedem Jacobi-Schritt wieder mit dem Startvektor.
Ausserdem sollte am Ende des Codes

return x

stehen, da x_new in der Schleife definiert wird und soweit ich weiss geht das programmier-technisch normalerweise nicht.

MfG
caal

22

18_quadratur-v1.pdf, Folie 16: da wo (b-a)\sum_{i=0}^n w_i^{(n)} f(x_i) steht. Der Faktor (b-a) ist da zu viel, wenn man einmal von dem Term vor dem ‘=’ nachrechnet. (Also klar, der kommt bei n=0,1,2,3,4 zwar vor, dann sind die Gewichte jedoch auch nicht mehr \int_a^b L_i(x) dx, sondern diese verrechnet und ausgeklammert.)

23

15_iterativeverfahrenvektor-v3.pdf und Klausur, F. 31: Positive Definitheit (<x, Ax> > 0 für alle x != 0) <=> Alle EW > 0 gilt nicht im Allgemeinen, sofern die Matrix nicht symmetrisch ist.

Andere Unis fordern auch stets die symmetrische positive Definitheit für die Konvergenz des Gauss-Seidel-Verfahrens:

Dazu ein Gegenbeispiel für die Aussage “pos. Def. <=> Alle EW > 0” von mir :wink:

A = [[ 2089. 1613. 6531.] [ 2533. 4663. 2444.] [ 1590. 1104. 6563.]]

A hat nur die strikt positiven Eigenwerte [ 9526.76561706 223.45474687 3564.77963608 ], jedoch ist A nicht positiv definit. Es gilt: A positiv definit <=> 1/2 (A + A^T) positiv definit*. Die Eigenwerte von 1/2 (A + A^T) sind jedoch: [ 10185.39895563 -485.20390052 3614.80494489 ]. Damit ist 1/2 (A + A^T) nicht symmetrisch positiv definit, es existiert also ein x, sodass <x, 1/2 (A + A^T)x> = <x, Ax> < 0.

*) zumindest für reelle A, x leicht einsehbar: <x, 1/2(A + A^T)x> = 1/2 (<x, Ax> + <x, A^Tx>) = 1/2 (<x, Ax> + <Ax, x>) = <x, Ax>.

Ich weiß nicht, was in der SS 2017 Klausur bei 6d) als Antwort gefordert war, jedoch war die gegebene Matrix mit strikt positiven Eigenwerten nicht symmetrisch. Ergo konnte man erstmal keine Aussage über ihre positive Definitheit und damit die Konvergenz mit Gauss-Seidel treffen. (Ich habe selbst die anderen Kriterien auch in der Klausur durchgerechnet und kam auf keinen grünen Zweig: Die Matrix war weder stark noch schwach diagonaldominant und der Spektralradius war > 1.)

Python-Code:

[code=python]import numpy as np
import random

random.seed(0)
np.random.seed(0)

for i in range(0, 1000):
# Make it a nice matrix
A = np.random.rand(3,3) * 10000
A = A.round(0)

symm_A = 0.5 * (A + A.T)

eigvals_A = np.linalg.eigvals(A)
eigvals_symm_A = np.linalg.eigvals(symm_A)
if (np.all(eigvals_A > 0)) and (not np.all(eigvals_symm_A > 0)):
	print("COUNTEREXAMPLE FOUND")
	print("Eigenvalues of A: " + str(np.linalg.eigvals(A)))
	print("Eigenvalues of 1/2 (A + A^T): " + str(eigvals_symm_A))
	print(A)
	break[/code]

Ausgabe mit Python 3.5.3:

[quote]COUNTEREXAMPLE FOUND
Eigenvalues of A: [ 9526.76561706 223.45474687 3564.77963608]
Eigenvalues of 1/2 (A + A^T): [ 10185.39895563 -485.20390052 3614.80494489]
[[ 2089. 1613. 6531.]
[ 2533. 4663. 2444.]
[ 1590. 1104. 6563.]][/quote]

1 „Gefällt mir“
24

@Marcel,
Bei 6d) wollte man denke ich sowas haben, wie: alle EV > 0 + Matrix diagonalisierbar => positive definit

Du kannst auch das einfachere Beispiel betrachten: A = np.array([[1,-3] , [0,1]])
Du hast den doppelten Eigenwert 1, aber np.dot(v, v @ A) < 0 für v = np.array([[1],[1]]) => Matrix nicht positiv definit

EDIT: Auf Nachfrage: Die Diagonalisierbarkeit folgt aus: EV alle verschieden + Matrix ist obere Dreiecksmatrix.
EDIT2: Annahme: Matrix war normal.