Colin W. Cryer Numerik Partieller Dierentialgleichungen II Sommersemester awestfalische Wilhelms-Universitat Munster 1 Letzte Anderung am 2. Ok

Testo completo

(1)Colin W. Cryer. Numerik Partieller Dierentialgleichungen II Sommersemester1 1995. a Westfalische Wilhelms-Universitat Munster. 1. Letzte A nderung am 2. Oktober 1995.

(2)

(3) Inhaltsverzeichnis 1 Elliptische Gleichungen. 1.1 Denition elliptischer Gleichungen . . . . . . . . . . . . . . . . . 1.1.1 Skalare Gleichungen . . . . . . . . . . . . . . . . . . . . . 1.1.2 Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . 1.2 Randwertaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Der Rand @ . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Typische Randbedingungen . . . . . . . . . . . . . . . . . 1.3 Existenz und Eindeutigkeit der Losungen von Randwertaufgaben. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .. 1. 1 1 2 5 5 7 7 9. 2 Das Maximumprinzip. 11. 3 Finite Dierenzen. 19. 2.1 Die grundlegenden Satze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Existenz- und Eindeutigkeitsbeweise . . . . . . . . . . . . . . . . . . . . . 16. 3.1 3.2 3.3 3.4. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ein Modellproblem: das Dirichlet-Problem fur die Poisson- Gleichung Dierenzenoperatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . Finite Dierenzen: Fortsetzung . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Beispiel 1: Das Neumann Problem . . . . . . . . . . . . . . . . 3.4.2 Beispiel 2: Nichtquadratische Gitter . . . . . . . . . . . . . . . 3.4.3 Beispiel 3: Neumann Bedingungen auf gekrummten Randern . 3.4.4 Beispiel 4: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Das Maximumprinzip fur Dierenzengleichungen . . . . . . . . . . . . 3.6 Konvergenzbeweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 4 Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. . . . . . . . . . .. 4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Hilfsmittel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Das Jacobi-, Gau-Seidel-, SOR- und SSOR-Verfahren - eine Einleitung 4.3.1 Anwendung auf ein Modellproblem . . . . . . . . . . . . . . . . . 4.3.2 Das Jacobi-Verfahren oder Gesamtschrittverfahren . . . . . . . .. . . . . . . . . . . . . . . .. 19 22 25 28 30 32 33 34 34 40. 47. 47 48 53 53 55.

(4) iv. INHALTSVERZEICHNIS. 4.4 4.5 4.6 4.7 4.8 4.9. 4.3.3 Das Gau-Seidel-(Einzelschritt-) Verfahren 4.3.4 Das S.O.R.-Verfahren . . . . . . . . . . . . 4.3.5 Das SSOR-Verfahren . . . . . . . . . . . . . Allgemeine Konvergenzbetrachtungen . . . . . . . Die Gerschgorin Satze . . . . . . . . . . . . . . . . Das Gesamtschrittverfahren - das Modellproblem . Verallgemeinerungen . . . . . . . . . . . . . . . . . Nichtnegative Matrizen . . . . . . . . . . . . . . . Das SOR Verfahren . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. 5 Iterationsverfahren fur groe lineare Systeme: neue Verfahren. 56 57 57 58 64 67 71 72 74. 81. 6 Die Laplace- und Poisson-Gleichung: Methoden der Funktionentheorie 83 6.1 Zusammenhange mit der Funktionentheorie . . . . . . . . . . . . . . . . . 6.2 Transformation der Laplace-Gleichung (siehe z.B. Kantorowitsch und Krylow, S. 331) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Konforme Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Die Integralgleichung von Theodorsen . . . . . . . . . . . . . . . . . . . . 6.5 Das Schwarzsche Spiegelungsprinzip . . . . . . . . . . . . . . . . . . . . . 6.6 Die Formel von Christoel-Schwarz . . . . . . . . . . . . . . . . . . . . . . 6.6.1 Herleitung (siehe Kantorowitsch und Krylow, S. 475, und Nehari, S. 189) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.2 Die Parameterwerte des Christoel-Schwarzschen Integrals (siehe Kantorowitsch und Krylow, S. 477) . . . . . . . . . . . . . . . . . . 6.6.3 Die Christoel-Schwarz-Formel: Ein Beispiel . . . . . . . . . . . .. 7 Die Laplace-Gleichung: Integralgleichungen. 7.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Integralgleichungen fur die Laplace-Gleichung . . . . . 7.2.1 Die Integralgleichung fur eine Doppelschicht . . 7.2.2 Die Integralgleichung fur eine einfache Schicht 7.2.3 Anwendung der Greenschen Formel . . . . . . 7.3 Numerische Losung von Integralgleichungen . . . . . . 7.4 Anwendungen . . . . . . . . . . . . . . . . . . . . . . .. 8 Finite Elemente: Theoretische Vorbereitungen. 8.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . 8.2 Variationsgleichungen im Hilbertraum . . . . . . . . 8.3 Variationsungleichungen: Einleitung . . . . . . . . . 8.3.1 Diskretisierung der Variationsformulierungen 8.4 Variationsungleichungen im Hilbertraum . . . . . . .. . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. 83. 84 86 88 89 91 91 93 95. 99. 99 99 99 104 104 106 112. 115 115 117 125 130 132.

(5) INHALTSVERZEICHNIS 9 Sobolew-Raume 9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10. Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Lebesguesche Theorie . . . . . . . . . . . . . . . . . . . Topologische Raume . . . . . . . . . . . . . . . . . . . . . . Sobolev-Raume: Denition durch Vervollstandigung . . . . Sobolev-Raume: Denition mit Hilfe schwacher Ableitungen Das Verhaltnis zwischen W m:p() und H mp() . . . . . . . Zusammenhang mit absoluten stetigen Funktionen . . . . . Die Sobolewschen Einbettungssatze . . . . . . . . . . . . . . Der Spur Operator . . . . . . . . . . . . . . . . . . . . . . Die Poincaresche Ungleichung und ihre Anwendungen . . .. 10 Finite Elemente. v . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. 139. 139 139 145 148 149 152 154 154 154 154. 159. 10.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.2 Das Galerkin-Verfahren: Fehlerabschatzungen . . . . . . . . . . . . . . . . 159.

(6)

(7) Kapitel 1 Elliptische Gleichungen 1.1 Denition elliptischer Gleichungen 1.1.1 Skalare Gleichungen Denition 1.1 Sei. R. L=. ein Dierentialoperator fur x 2 6= 0 gilt. X jjk n.. R. x(L ) :=. Beispiel 1.1 Die Laplace-Gleichung in. a (x)@ . L heit elliptisch zu x, falls fur alle 2. X. jj=k n. a (x) 6= 0 :. ist elliptisch, da. n @2u X 2 i=1 @xi n X x(L ) = i2 :. Lu =. Beispiel 1.2 Die biharmonische Gleichung. R. i=1 in 2 ,. 4 4u @4u Lu = @@xu4 + 2 @x@2 @x + 2 @x4 1. 1. 2. 2. ist elliptisch, da. x (L ) = 14 + 21222 + 24 = (12 + 22)2 :. R. n,.

(8) 2. Elliptische Gleichungen. Beispiel 1.3 Die Minimal-Oberachengleichung (1 + u2y )uxx ; 2uxuy uxy + (1 + u2x)uyy = 0 ist elliptisch, da. x(L ) = (1 + u2y )12 ; 2uxuy 12 + (1 + u2x)22 = 12 + 22 + (1uy ; 2ux)2 Es ist manchmal wichtig, die Elliptizitatsbedingung genauer zu klassizieren. Fur Dierentialgleichungen der zweiten Ordnung ist die folgende Klassikation nutzlich:. Denition 1.2 Sei L=. X jj2. a (x)@ . R. ein Dierentialoperator zweiter Ordnung fur x 2 n . L heit gleichmaig elliptisch auf (uniformly elliptic), falls eine Konstante a > 0 existiert mit n n X X X 1 2 a i a (x) a i2 i=1 i=1 jj=2 fur alle x 2 .. Beispiel 1.4 Die Gleichung. R. xuxx + 2ux = 0 ist nicht gleichmaig elliptisch auf = (0 1) . 1.1.2 Gleichungssysteme. 1. Systeme von Dierentialgleichungen treten oft auf. Sie werden allerdings nur selten in der Literatur behandelt. Insbesondere werden Systeme hoherer Ordnung kaum in Lehrbuchern behandelt. Einige der wenigen Ausnahmen sind die Bucher von Miranda 1970, S. 275], Courant und Hilbert 1962, S. 577] und Hormander 1963, S. 267]. Sei. fur x 2 . R. u(x) = (u1(x) : : : uN (x))T f (x) = (f1(x) : : : fN (x))T n.. Sei Mij ein Dierentialoperator der Ordnung ij ..

(9) 1.1 Denition elliptischer Gleichungen. 3. Z Z. Sei. si 2 ti 2 1 i N mit. ij si + tj Mij 0 falls si + tj < 0 : Sei Mij (x ) das charakteristische Polynom von Mij und ( ij (x ) falls ij = si + tj M^ ij (x ) = M 0 falls < s + t ij. i. j. Das System N X j =1. Mij (x)uj = fi 1 i N. heit elliptisch im Sinne von Douglis und Nirenberg, falls es moglich ist, si und tj so zu wahlen, da. a^(x ) := det(M^ ij (x )) 6= 0 x 2 2 Sei. R. n. :. a(x ) := det(Mij (x )) r = Grad a R = Der maximale Grad der N! Terme von a bei der Entwicklung mit der Leibniz-Regel Es ist von Volevich bewiesen worden (Agmon, Douglis, Nirenberg 1964, S. 39]), da die folgenden Bedingungen fur die Elliptizitat notwendig und hinreichend sind: 1. r = R , 2. a~(x ) 6= 0 fur alle 6= 0, wo bei ~a der Hauptteil von a, d.h. der Teil vom Grade r, ist.. Beispiel 1.5 ux ; vyy = f1 uyy + uy + vxxx + vxy = f2.

(10) 4. Elliptische Gleichungen. Man setze. s1 = 0 s2 = 1 t1 = 1 t2 = 2 : Es folgt:. 2 ;. a = a~ = a^ = 2 3 = 4 + 4 r = 4 R = 4 : Beispiel 1.6 Cauchy-Riemann-Gleichungen] ux ; vy = 0 uy + vx = 0 Man setze s1 = s2 = 1 t1 = t2 = 0 . Es folgt: ;. â = = 2 + 2 :. Beispiel 1.7. a~ = a = a^ r=R = 2: uxx + uyy = 0 :. Setze. u1 := ux u2 := uy : Es gilt:. Man setze. @u1 + @u2 = 0 @x1 @x2 @u ; u = 0 @x1 1 @u ; u = 0 : @x2 2. s0 = 0 s1 = s2 = ;1 t0 = 2 t1 = t2 = 1 :.

(11) 1.2 Randwertaufgaben Es folgt:. 5 0 1 2 a^( ) = 1 ;1 0 = 12 + 22 0 ;1 2. a~ = a = a^ r=R = 2: In der Theorie von Agmon, Douglis und Nirenberg wird weiter vorausgesetzt:. R. Bedingung L: a~(x ) ist ein Polynom vom Grade 2m bezuglich . Sei ^ 2 n linear unabhangig. Das Polynom q( ) := a~(x + ^ ) hat genau n Nullstellen mit positivem. Imaginarteil.. Bemerkung 1.1 Sei das System elliptisch im Sinne von Douglis und Nirenberg und. n > 2. Dann ist die Bedingung L erfullt. (Siehe Agmon, Douglis, Nirenberg 1964, S. 39], Miranda 1970, S. 244].) Bemerkung 1.2 Sei n = 2. Es gebe eine Funktion (x) und ein > 0 mit Ref (x)â(x )g j j2r fur alle 2 n x 2 n 6= 0 wobei 2r die Ordnung des Dierentialoperators Mij ist. Dann ist die Bedingung L erfullt (siehe Miranda 1970, S. 245]).. R R. Literatur. Agmon, S., Douglis, A., Nirenberg, L.: Estimates near the boundary for solutions of. elliptic partial dierential equations satisfying general boundary conditions. II. Comm. Pure Appl. Math. 17, 35-92(1964).. Douglis, A., Nirenberg, L.: Interior estimates for elliptic systems of partial dierential equations. Comm. Pure Appl. Math. 8, 503-538(1955).. Hormander, L.: Linear Partial Dierential Operators. Berlin: Springer, 1963. Miranda, C.: Partial Dierential Equations of Elliptic Type. New York: Springer, 1970.. 1.2 Randwertaufgaben 1.2.1 Einfuhrung. Eine partielle Dierentialgleichung hat mehrere Losungen. In den Anwendungen werden Randbedingungen vorgeschrieben, die der Anwendung entsprechen und eine moglichst.

(12) 6. Elliptische Gleichungen. eindeutige Losung bestimmen sollen. Fur elliptische Gleichungen und Systeme gilt folgende Faustregel fur sachgemagestellte Randwertaufgaben: Auf jedem Punkt des Randes @ von sollten m Randbedingungen vorgeschrieben werden, wenn die Ordnung der Gleichung (des Systems) 2m ist. Das folgende Beispiel von Hadamard zeigt, da - wenn diese Faustregel verletzt wird das Randwertproblem evtl. schlechtgestellt sein kann: D C ( ). . A. B. (0 0). Abbildung 1.1: Das Beispiel von Hadamard. a) u = 0 (x y) 2 b) u = 0 auf AD c) u = 0 auf BC d) u = 0 auf AB. N. e) un = ;uy = ; k1s sin kx auf AB mit k s 2 . Eine Losung ist: +ky ; e;ky. u(x y) = ks1+1 sin kx e. : 2 Fur k grokann u beliebig growerden, obwohl alle Randwerte gleichmaig beschrankt sind..

(13) 1.2 Randwertaufgaben. 7. 1.2.2 Der Rand @ Der Rand @ mueinige Glattheitsbedingungen erfullen.. N. Typische Bedingungen sind:. R. 1. Der Rand @ ist C k mit 2 0 1] und k 2 0 , d.h. fur jedes x0 2 @ gibt es eine Kugel B = B (x0) und ein Homoomorphismus : B ! D n mit. RR. (a) (B \ ) n+ (b) (B \ @ ) @ (c). n +. 2 C k(B ) ;1 2 C k(D) . R R. wo. n +. = fx 2. n. : xn > 0g :. R. 2. @ erfullt eine gleichgradige innere Kegelbedingung, d.h. es gibt einen Kegel K n mit der Spitze 0 und ein r > 0, so da fur jedes x0 2 @ eine Kongruenz existiert mit. x0 + (Kr ) wo. Kr := fx 2 K : kxk < rg : (Siehe Abbildung 1.2.) 3. sei ein Polygongebiet.. 1.2.3 Typische Randbedingungen 1. Eine Gleichung zweiter Ordnung Sei. R. Lu =. X jj2. a(x)@ u. eine elliptische Gleichung zweiter Ordnung. Seien f f1 : : : vorgeschriebene Funktionen. Sei n . Es gibt drei kanonische Randwertaufgaben..

(14) 8. Elliptische Gleichungen Γ x0. Ψ( Kr). Ω Abbildung 1.2: Die Kegelbedingung. (a) 1. Randwertaufgabe. Lu = f x 2 u = f1 x 2 @ Dieses Problem heit auch Dirichlet-Problem. (b) 2. Randwertaufgabe. Lu = f x 2 n n 2u X X @u + c Lu = aik @x@ @x + bi @x i k i=1 i ik=1 Lu = f x 2 n X @u + f u = f x 2 @ aik

(15) k @x 2 3 i ik=1 wo

(16) = (

(17) 1 : : :

(18) n) der auere einheitsnormale n-Vektor auf @ ist. Ist f2 = 0, heit dieses Problem auch Neumann-Problem, sonst RobinProblem. (c) 3. Randwertaufgabe. Lu = f x 2 f4 @u @

(19) + f5u = f6 x 2 @ :. Dieses Problem heit auch gemischte Randwertaufgaben..

(20) 1.3 Existenz und Eindeutigkeit der Losungen von Randwertaufgaben. 9. 2. Eine Gleichung vierter Ordnung Die bekannteste Gleichung vierter Ordnung ist die biharmonische Gleichung: 4 4u @4u = 0 : Lu = @@xu4 + 2 @x@2 @y + 2 @y 4. Typische Randbedingungen sind: (a) Das (verallgemeinerte) Dirichlet-Problem. Lu = 0 x 2 u = f1 x 2 @ un = f2 x 2 @ 3. Gleichungssysteme Siehe z.B. Agmon, Douglis, Nirenberg 1964, S. 42]. 4. Existenz und Glattheit der Losungen der Randwertaufgaben Fur eine sachgemagestellte Randwertaufgabe fur elliptische Gleichungen gilt folgende Faustregel:. Die Losung u ist so glatt wie die Koe zienten der Gleichung, die Koe zienten der Randbedingungen und der Rand es erlauben. Weiter gilt:. Jede Anderung der Koe zienten der Gleichung oder der Randbedingungen fuhrt zu einer Anderung der Losung u in jedem Punkt x 2 .. 1.3 Existenz und Eindeutigkeit der Losungen von Randwertaufgaben Die Theorie von Randwertaufgaben benutzt mehrere Methoden, die die numerischen Methoden entweder anregen oder beeinussen: a) Funktionentheorie b) Variationsgleichungen c) Integralgleichungen.

(21) 10. Elliptische Gleichungen. d) Fixpunktmethoden e) Das Maximumprinzip Bekannte numerische Methoden sind: a) Dierenzenverfahren b) Finite Elemente c) Randelementmethoden d) Spektralmethoden e) Galerkinmethoden die oft mit a) Mehrgittermethoden b) Gebietszerlegungsmethoden c) Gebietstransformationen d) lokale Verfeinerung kombiniert werden. Wir werden mehrere dieser Methoden und Techniken kennenlernen..

(22) Kapitel 2 Das Maximumprinzip Fur elliptische Gleichungen zweiter Ordnung gilt ein Maximumprinzip, das auerordentlich nutzlich ist.. 2.1 Die grundlegenden Satze Sei. Mu :=. R. n X ik=1. n 2u X @u : + bi @x aik @x@ @x i k i=1 i. Wir setzen voraus: V1. . n. , ein beschranktes Gebiet.. V2. aik = aik (x) bi = bi (x) seien stetige Funktionen auf . V3. Es gebe > 0 mit V4. u 2 C 2() \ C (! ) .. n X ik=1. aik (x)ik . n X i=1. i2 2. R. n. :. Wir benutzen hier die Beweismethode von Courant und Hilbert, S. 326 .. Satz 2.1 :. u habe ein Maximum an der Stelle P 2 . Dann gilt: Mu(P ) 0 : Beweis: Wenn u ein Maximum an dem inneren Punkt P hat, dann sind alle ersten Ableitungen von u an der Stelle P gleich Null. Folglich:.

(23) 12. Das Maximumprinzip Mu(P ) =. n X ik=1. 2u aik (P ) @x@ @x. i. = Spur AB. k. mit. A = (aik ) 2 Mat (n! n) 2u B = @x@ @x (P ) 2 Mat (n n) : i k Es gibt eine orthogonale Matrix S mit SAS T = " = Diag ( i) : Dann gilt: Spur (AB ) = Spur (SABS T ) = Spur ("SBS T ) n X = iii i=1. mit. ii = (SBS T )ii : Gebe es i mit ii > 0, wurde die Bedingung verletzt, da u in P ein Maximum hat. Um dies einzusehen, setzt man = s mit. s := fsij : 1 j ng 2 Es gilt (Forster, II, Corollar 2, S. 59):. R. n. :. u(P + ) = u(P ) + h(grad u)(P ) i + 12 h B i + 0(k k2) = u(P ) + 12 2 hs B si + 0(2) = u(P ) + 12 2 ii + 0(2 ) . so da P kein lokales Maximum von u ist..

(24) 2.1 Die grundlegenden Satze. 13. Die Voraussetzung V3 hat zur Folge, da A positiv denit ist, so da die Eigenwerte i von A positiv sind. Es folgt. R. Mu(P ) =. n X i=1. iii 0 :. Lemma 2.1 (Hopf): Sei K . n. eine oene Kugel und P0 2 @K . Es gelte: Mu 0 x 2 K u(x) < u(P0) x 2 K :. Dann gilt:. du := lim inf u > 0 : dn p0 n p0. Beweis: (siehe Abbildung 2.1) 1 K P0. S 0. K* K Abbildung 2.1: Hilfskonstruktion fur den Beweis des Maximumprinzips. Sei K eine kleinere Kugel, K K mit P0 2 @K . Dann gilt: max u = u(P0) : K Wahle den Ursprung O als Mittelpunkt von K und setze.

(25) 14. Das Maximumprinzip r2 :=. n X i=1. x2i :. Sei r0 = jP0 ; Oj. Sei K1 eine Kugel mit Radius r1 < r0 und Mittelpunkt P0. Setze. S = K1 \ K @S = R1

(26) R2 h(x) := e;r2 ; e;r02 > 0 : Es gilt: 1. h > 0 x 2 K 2. h = 0 x 2 @K 3.. 2 3 n n X X Mh = e;r 44 2 aik xixk ; 2 (aii + bi xi)5 i=1 ik=1 " n n # X X 2 ; r 2 2 e 4 r ; 2 aii ; 2r bi 2. i=1. i=1. Wahle > 0 so, da M h > 0 x 2 S! . Sei > 0 und v := u + h. Auf R1 ist u < u(P0) und h beschrankt. Folglich gilt fur genugend kleines :. v(x) < u(P0) x 2 R1 : Jetzt betrachten wir die Funktion v auf S! . Es gilt:. Mv = Mu + Mh > 0 x 2 S : Es folgt aus Satz 3.1 max v = max v: @S S Aber.

(27) 2.1 Die grundlegenden Satze. 15. v(x) < u(P0) = v(P0) x 2 R1 v(x) = u(x) + h(x) = u(x) < u(P0) fur x 2 R2 nP0 : Folglich gilt: max v = max v = v(P0) = u(P0) : @S S Es folgt: Da. dv (P ) = lim v(P0) ; v(P ) 0 : dn 0 n!0 n. folgt. dh (P ) = ;2r e;r02 < 0 0 dn 0. du (P ) = dv (P ) ; dh (P ) > 0 : dn 0 dn 0 dn 0 Satz 2.2 (Starkes Maximumprinzip): Sei Mu 0 x 2 :. Es gebe P 2 mit max u = u(P ) : . Dann ist u(x) u(P ), d.h. u ist konstant. Beweis: Sei Mu 0 in . Falls u nicht konstant ist und es einen Punkt P 2 gibt mit M := max u = u(P ) dann gibt es eine oene Kugel K und einen Punkt P0 mit 1. K! 2. u(x) < u(P ) x 2 K 3. P0 2 @K mit u(P0) = u(P ).

(28) 16. Das Maximumprinzip. Um dies einzusehen, sind folgende U berlegungen notig:. R. 1. Je zwei Punkte in einem zusammenhangenden Gebiet n konnen mit einem Polygonzug ; verbunden werden (Hocking und Young, Satz 3-5, S. 108). 2. Sei P1 2 u(P1) < M . Sei ; ein Polygonzug, der P und P1 verbindet. 3. Es gilt:. d(; @ ) = > 0 : 4. Es gibt einen Punkt P2 2 ; mit. d(P2 @ ) > d(P2 M ) M := fx 2 : u(x) = M g : 5. Es gibt eine Kugel K~ mit Mittelpunkt P2 und Punkt P0 2 @ K~ , die die gewunschten Eigenschaften besitzen. Da u ein Maximum in P0 hat, ist grad u = 0, was der Tatsache widerspricht, da aus dem Hopfschen Lemma du (P ) > 0 : dn 0. 2.2 Existenz- und Eindeutigkeitsbeweise. R. Satz 2.3 : Sei operator. n. ein beschranktes Gebiet. Sei M der gleichmaig elliptische DierentialM=. n X ik=1. n 2u X @u : aik @x@ @x + bi @x i k i=1 i. Dann hat das Dirichletsche Randwertproblem: u 2 C 2 () \ C () Mu = f x 2 u = g x 2 @. hochstens eine Losung u..

(29) 2.2 Existenz- und Eindeutigkeitsbeweise. 17. Beweis: Anwendung des Maximumprinzips.. Es ist moglich, einen einfachen Existenzsatz fur elliptische Gleichungen mit Hilfe des Maximumprinzips zu geben. Dies benutzt die Perronsche Methode von subharmonischen Funktionen. Wir verzichten auf den Beweis (siehe z.B. Gilbary und Trudinger 1977, S. 23]). Fur die Laplace Gleichung erhalt man z.B.:. R. Satz 2.4 Sei n ein beschranktes Gebiet, das die auere Kugelbedingung erfullt: Fur jedes x 2 @ gibt es eine Kugel KR (y) mit: 1. KR (y) = fx : jx ; yj < Rg , 2. K R (y) \ = fxg . Dann gibt es fur jedes g 2 C (@ ) eine Funktion u 2 C 2() \ C () mit 1. u = g auf @ 2. u = 0 in . Kurzlich sind diese Ideen erneut aufgenommen worden. Die sogenannten viskosen Losungen (\viscous solutions") ermoglichen es, Existenz- und Eindeutigkeitssatze fur viele nichtlineare partielle Dierentialgleichungen zweiter Ordnung zu beweisen. Siehe Crandall, Ishii, Lions 1992].. Literatur: Courant, R. und Hilbert, D.: Methods of Mathematical Physics II. Partial Dierential Equations. New York: Interscience, 1962.. Crandall, M.G., Ishii, H. und Lions, P.-L.: Users guide to viscosity solutions of second order partial dierential equations. Bull. Amer. Math. Soc. (New Series) 27 (1-67) 1992.. Gilbarg, D. und Trudinger, N.S.: Elliptic Partial Dierential Equations of Second Order. Springer, 1977.. Hocking, J.G. und Young, G.S.: Topology. Reading MA, Addison-Wesley, 1961. Protter, M.H. und Weinberger, H.F.: Maximum Principles in Dierential Equations. Englewood Clis, NJ, Prentice-Hall, 1967..

(30)

(31) Kapitel 3 Finite Dierenzen 3.1 Einleitung Das Dierenzenverfahren oder die Methode der niten Dierenzen wird seit 1908 zur Losung von Randwertaufgaben fur partielle Dierentialgleichungen benutzt. Sie verliert an Wichtigkeit im Vergleich zu neueren Methoden, wie Finiten Elementen, ist aber noch immer sehr nutzlich. Viele Ideen werden von Dierenzenverfahren auf die neueren Methoden ubertragen. Bahnbrechende Arbeiten wurden von Runge 1908], Richardson 1910] und Courant, Friedrichs und Lewy 1928] geleistet. Bekannte Standardwerke sind Forsythe und Wasow 1960], Collatz 1955]. Siehe auch Strikwerda 1989].. R. Sei n ein Gebiet mit Rand ; = @ , seien A und B Dierentialoperatoren. Eine allgemeine Randwertaufgabe fur eine elliptische Dierentialgleichung hat die Form: Bestimme u, so da. Au = f x 2 Bu = g x 2 ; :. (3.1) (3.2). Es ist zuerst notig, einige Erganzungen zu machen: a) Wichtig ist, die Voraussetzungen fur die Losung u anzugeben. Es wird meistens vorausgesetzt, da u in einem vorgeschriebenen Banachraum V liegt. Ebenfalls gilt: f 2 F. b) Der Operator A muals eine Abbildung zwischen den Banachraumen V und F deniert werden:. A : V ;! F :.

(32) 20. Finite Dierenzen c) Der Operator B und das Element g mussen auch sinnvoll deniert werden.. d) Die Randbedingungen werden oft als Teil der Denition von V betrachtet. Macht man dies, so munur die Gleichung. Au = f. (3.3). gelost werden.. A. V. Vh. qh. sh. ph. rh. F. Ah. Fh. Abbildung 3.1: Interne Approximation. V. _ ω. rh. W ph. Vh Abbildung 3.2: Externe Approximation. Die Gleichung Au = f wird durch eine Gleichung. Ahuh = fh approximiert, wobei. (3.4).

(33) 3.1 Einleitung. 21 Ah : Vh ;! Fh . fh 2 Fh und Vh und Fh geeignete endlich dimensionale Banachraume sind.. (3.5). Die Losung der Gleichung. Ahuh = fh erfordert ublicherweise die Losung eines Systems linearer oder nichtlinearer algebraischer Gleichungen. Danach muder Fehler zwischen u und uh abgeschatzt werden. Es gibt drei Moglichkeiten: 1. u und phuh in V zu vergleichen (interne Approximation, Abbildung 3.1), 2. !u und phuh in einem anderen Raum W zu vergleichen (externe Approximation, Abbildung 3.2), 3. rhu und uh in Vh zu vergleichen. Die Beschreibungen \intern" und \extern" deuten an, da die Approximation phuh innerhalb bzw. auerhalb des Losungsraums V liegt. Wichtig fur jede Fehlerabschatzung sind zwei Begrie: Eine Approximation Ahuh von Au heit konsistent, falls kAh rh u ; sh AukFh ;! 0 fur h ;! 0 :. (3.6). Eine Approximation Ah von A heit stabil, falls eine Konstante S > 0 existiert mit kvh kVh S kAhvh kFh fur alle vh 2 Vh :. Die folgenden Fragen werden anschlieend behandelt: 1. Wie werden die Abbildungen Ah konstruiert? 2. Existiert eine Losung uh der Gleichung Ahuh = fh? 3. Ist die Losung uh eindeutig? 4. Wie verhalt sich der Fehler uh ; rhu?. (3.7).

(34) 22. Finite Dierenzen. 3.2 Ein Modellproblem: das Dirichlet-Problem fur die Poisson- Gleichung Wir betrachten das folgende Problem: u = f (x y) 2 u = g (x y) 2 @ . (3.8) (3.9). wo das Einheitsquadrat ist, := f(x y) : 0 < x < 1 0 < y < 1g : Dieses Problem heit Dirichlet-Problem (wegen der Randbedingung (3.9)) fur die PoissonGleichung (3.8), siehe Abbildung 3.3. y. u=g. u=g. Δu = f. (1,1). u=g x. (0,0). u=g. Abbildung 3.3: Das Dirichlet-Problem fur die Poisson-Gleichung. Es wird eine Maschenweite h = 1=M gewahlt. Das Gebiet wird mit einem quadratischen Gitter uberzogen (siehe Abbildung 3.4). Die Gitterpunkt sind die Punkte: (xi yj ) 0 i M 0 j M . (3.10). wobei. xi = ih yj = jh. (3.11).

(35) 3.2 Ein Modellproblem: das Dirichlet-Problem fur die Poisson- Gleichung 23 j. 3 2 1 i 1. 2. 3. Abbildung 3.4: Das Gitter fur h = 1=4. Da die Randbedingungen Dirichlet-Bedingungen sind, ist es nur notig, die Werte von uh im Innern des Quadrats zu bestimmen, und wir denieren: h := f(xi yj ) : 1 i j M ; 1g ;h := f(xi yj ) : i 2 f0 M g oder j 2 f0 M gg Falls u 2 C 4 () und (x y) 2 h folgt:. mit. (3.12). hu(x y) := u(x + h y) + u(x ; h y) ; 2u(x y)] + + u(x y + h) + u(x y ; h) ; 2u(x y)] h4 u ( y) + u (x )] = h2u + 12 xxxx yyyy. 2 (x ; h x + h) 2 (y ; h y + h) : Somit erhalt man als Approximation zu den Gleichungen (3.8), (3.9):. (3.13). huh(xi yj ) = f (xi yj ) (xi yj ) 2 h uh(xi yj ) = g(xi yj ) (xi yj ) 2 ;h Fur dieses Modellproblem gilt:. (3.14) (3.15). V = C 4 () \ C () F = C 2 () Au = u. (3.16).

(36) 24. Finite Dierenzen. RR. (Ahuh)(xi yj ) := huh(xi yj ) N Y 1= N Vh := k=1. N := (M ; 1)2. R. (rh heit Injektionsoperator.). N. Fh := rh : C () ;! Fh (rhu)(xi yj ) := u(xi yj ) :. (3.17). Der Dierenzenoperator h lat sich wie in Abbildung 3.5 darstellen und heit deshalb das Funfpunkt-Stern oder Funfpunkt-Molekul.. 1 1. -4. 1. 1 Abbildung 3.5: Das Funfpunkt-Molekul. Ah ist die (M ; 1)2 (M ; 1)2-Blocktridiagonal-Matrix: 0 1 J I BB . . C BB I . . . . CCC Ah := B . . . . B@ CA . . IC I J 0 1 1 B . . CC I = IM ;1 = B . A @ 1 0 1 ; 4 1 BB CC BB 1 . . . . . . CC J = JM ;1 = B ... ... 1 C B@ CA 1 ;4.

(37) 3.3 Dierenzenoperatoren. 25. 3.3 Di erenzenoperatoren Es gibt ein Kalkul fur Dierenzenoperatoren, das oft nutzlich ist bei der Erstellung von Dierenzengleichungen.. R. Sei f 2 C 1(;1 +1) und h 2 . Wir fuhren folgende Operatoren ein:. Ef f (x) rf (x) Df (x) f (x) f (x). = = = = = =. f (x + h) f (x + h) ; f (x) f (x) ; f (x ; h) f 0(x) f h x + 12 h ; f x ; 12 h i 1 f x + 1h + f x ; 1h 2 2 2. Verschiebungsoperator Vorwartsdierenzenoperator Ruckwartsdierenzenoperator Dierentiationsoperator Zentraler Dierenzenoperator Mittelwertoperator. Die Operatoren sind linear, assoziativ und kommutativ. Sie bilden einen Ring. Es folgt, da der binomische Satz gilt: ! n X (P + Q)n = P k Qn;k nk : k=0 Aus der Taylor-Reihe. Ef (x) = f (x + h) =. 1 hk X Dk f (x) k ! k=0. folgt:. E = ehD :. (3.18). ehD = 1 + :. (3.19). Also ist. Logarithmiert man diese Gleichung, so erhalt man:. hD = `n(1 + ) 2. 3. = ; 2 + 3 . (3.20).

(38) 26. Finite Dierenzen. Man kann diese Gleichungen folgendermaen beweisen: Sei f (x) = eax. Dann gilt n n (;1)k k X k f (x) = X (;1) (eah ; 1)k f (x) : k=1 k k=1 k Fur jeah ; 1j < 1 folgt: 1 (;1)k X k f (x) = `n(1 + (eah ; 1))f (x) = aheax = hDf (x) : k k=1 Also gilt:. `n(1 + )f (x) = hDf (x) fur f (x) = eax und jeah ; 1j < 1.. (). Nun setzt man. 1 (ax)` X `=0 `! ein, entwickelt` die beiden Seiten von () nach Potenzen von a und vergleicht die Koe'zienten von a`! . Es folgt: ` (;1)k X ` k x` hDx = k=1 k d.h. (3.20) gilt fur alle Polynome.. eax =. Weitere Formeln sind:. = hD = = =. 1 2 sinh 2 hD ! ; 1 2 sinh 2 2 3 !3 !5 !7 1 1 1 3 1 1 3 5 1 2 42 ; 2 2 3 + 2 4 2 5 ; 2 4 6 2 7 5 3 + 35 ; 57 ; 24 640 7168 4 6 8 2 ; 12 + 90 ; 560 . (hD)2 = ;1=2 1 + 14 2 = 1 3 5 hD = ; 6 + 30.

(39) 3.3 Dierenzenoperatoren. 27. Diese Formeln werden in Bjorck und Dahlquist 1979, x7.6] und Norlund 1954] bewiesen. Man kann diese Formeln naturlich auch als Hilfsmittel betrachten, die es ermoglichen, Dierenzenapproximationen schnell herzuleiten, wobei die Richtigkeit nachher mit Hilfe von Taylor-Reihenentwicklungen bestatigt werden mu.. Beispiel 3.1. a). ux = Du = h1 `n(1 + )u " # 2u 1 = h u ; 2 1 ) ux(x) =: u(x) h = h1 u(x + h) ; u(x)] :. b) ux(x) =: h1 ru(x) = h1 u(x) ; u(x ; h)] : c). ux(x) = h2 sinh;1(=2)u(x) 1 ;1=2 2 ; 1 = h sinh (=2) 1 + 4 2 u(x) =: h2 2 u(x) = u(x + h) 2;h u(x ; h) : d). 2 uxx = h42 sinh;1 =2 u !2 3 4 = h2 2 ; 48 u !2 2 2 4 = h2 4 1 ; 24 u ! 2 2 = h2 1 ; 12 u :. Das bedeutet, da die Dierentialgleichung. u00 (x) = f (x) durch.

(40) 28. Finite Dierenzen 1 2 ; 1 4 u = f i i h2 12. oder. 1 ; 1 u + 4 u ; 5 u + 4 u ; 1 u = f i h2 12 i;2 3 i;1 2 i 3 i+1 12 i+2 approximiert werden kann. Diese Approximation ist zwar genauer als die Standardapproximation, hat aber mehrere Nachteile: Verlust der Positivitat( 5-Diagonalmatrizen( usw. Im allgemeinen besteht das Dierenzenverfahren daraus, da alle partiellen Ableitungen in einer partiellen Dierentialgleichung durch Dierenzen ersetzt werden. Es gibt oft mehrere Moglichkeiten, unter denen eine Auswahl getroen werden mu.. 3.4 Finite Di erenzen: Fortsetzung Das Dierenzenverfahren fur das Problem. Au = f in . (3.21). Bu = g auf @ . R. besteht aus den folgenden Schritten: a). wird mit einem regelmaigen Gitter Gh uberzogen. h := Gh \ heit die Menge der inneren Gitterpunkte. Am Rand werden weitere Punkte ausgewahlt, die meistens die Schnittpunkte von Gitterlinien und @ sind. Die Menge dieser Punkte sind die Randgitterpunkte. Sie wird mit ;h bezeichnet. Siehe Abbildung 3.6. Der Raum von Gitterfunktionen n. R. Vh := C 0(h

(41) ;h ) ist die Menge aller reellen Funktionen, die auf h

(42) ;h deniert sind. Die Bezeichnung C 0 deutet an, da die Funktionen stetig sind, was in diesem Fall keine Einschrankung ist, da h

(43) ;h eine diskrete Menge ist. b) Sei N = Nh die Dimension von Vh,.

(44) 3.4 Finite Dierenzen: Fortsetzung. 29 innere Gitterpunkte. Ωh. Randgitterpunkte Γh. Abbildung 3.6: Die Gitterpunktmengen. Nh = jhj + j;hj : Ein System von Nh Gleichungen,. Ah(vh) = fh Ah : Vh ;! Fh fh := sf 2 Fh. (3.22). wird so konstruiert, da die Restriktion von u auf h. uh := rhu. (3.23). das System (3.22) mit geringem Fehler erfullt:. Ah(uh) ; fh = 0(hm) :. (3.24). Das Gleichungssystem (3.22) wird so konstruiert, da jedem Gitterpunkt P 2 h

(45) ;h eine Gleichung APh (vh) = fh(P ) zugeordnet wird: 1. Fur P 2 h entsteht diese Gleichung dadurch, da in der Gleichung (Au)(P ) = f (P ) die partiellen Ableitungen durch Dierenzen ersetzt werden. 2. Fur P 2 ;h werden auch partielle Ableitungen durch Dierenzen approximiert, wobei allerdings sehr viele Moglichkeiten berucksichtigt werden mussen..

(46) 30. Finite Dierenzen. 3.4.1 Beispiel 1: Das Neumann Problem u = 0 in . @u = g auf ; @n Sei u 2 C 2(G) und ; glatt. Es folgt aus dem Gauschen Integralsatz, da Z Z Z @u 0 = div grad u dx = @n ds = g ds : ; ;. (3.25). Das Problem (3.25) ist deshalb nur sinnvoll, wenn g die folgende Bedingung erfullt:. Z. g ds = 0 :. ;. (3.26). Wird diese Bedingung erfullt und erfullt u die Gleichung (3.25), dann ist v := u + const. auch eine Losung von (3.25). Wir betrachten jetzt das Neumann Problem (3.25) fur das Rechteck = (0 1)2 mit h = 1=2 (Abbildung 3.7). 7. 8. 9. 4. 5. 6. 1. 2. 3. 5’. Abbildung 3.7: Das Neumann Problem auf einem Rechteck. Fur den Randgitterpunkt P6 gelten folgende U berlegungen: Ware P6 ein innerer Punkt mit Nachbarn P3 P5 P50 und P9 (siehe Abbildung 3.7), dann wurde gelten: u5 + u 0 + u9 + u3 ; 4u6 =: u(P6) = 0 : 5. @u = g kann durch die Gleichung Die Randbedingung @n 6. u05 ; u5 = g 6 2h.

(47) 3.4 Finite Dierenzen: Fortsetzung. 31. approximiert werden. Elimination von u5 fuhrt zu der Gleichung 2u5 + u9 + u3 ; 4u6 = ;2hg6 die selbstverstandlich auch durch eine Taylorreihenentwicklung uberpruft werden kann. Entsprechende U berlegungen bei den ubrigen Randgitterpunkten liefert folgendes Gleichungssystem:. Ahvh = fh mit. vh = (v1 : : : v9 )T. 0 1 ; 4 2 0 2 0 0 0 0 0 BB C BB 1 ;4 1 0 2 0 0 0 0 CCC BB 0 2 ;4 0 0 2 0 0 0 CC BB 1 0 0 ;4 2 0 1 0 0 CC B C Ah = B BB 0 1 0 1 ;4 1 0 1 0 CCC BB 0 0 1 0 2 ;4 0 0 1 CC BB 0 0 0 2 0 0 ;4 2 0 CC BB C @ 0 0 0 0 2 0 1 ;4 1 CA 0 0 0 0 0 2 0 2 ;4 T fh = ;2h g1(x) + g1(y) g2 g3(x) + g3(y) g4 0 g6 g7(x) + g7(y) g8 g9(x) + g9(y) wobei die Terme g1(x) + g1(y) dadurch entstehen, da an Eckpunkten zwei auere Normale existieren. Die Matrix Ah ist, wie zu erwarten, singular: die Zeilensummen sind null. Dieses Beispiel zeigt, wie leicht es ist, Dierenzengleichungen fur Probleme zu erstellen, fur die Existenzsatze nicht sofort vorhanden sind..

(48) 32. Finite Dierenzen. 3.4.2 Beispiel 2: Nichtquadratische Gitter Es ist oft zweckmaig, nichtquadratische Gitter zu benutzen: 1. Sei = 0 a] 0 b], wobei a=b eine irrationale Zahl sei. Dann gibt es keine Maschenweite h mit. N. a = mh b = nh m n 2 : 2. Sei ' : 0 1] ;! 0 1] '(0) = 1 '(1) = 0, ' monoton fallend. Das Gebiet = f(x y) : 0 x 1 0 y '(x)g wird in Abbildung 3.8 gezeigt. (0,1). Γ3 Γ1. Γ2. (1,0). Abbildung 3.8: Ein nichtquadratisches Gitter. Es werden zuerst die Randgitterpunkte auf ;3 gewahlt (siehe Abbildung 3.8), dann ergibt sich ein geeignetes Gitter. In einem allgemeinen Gitterpunkt (xi yj ) erhalt man z.B. mit der Schreibweise von Abbildung 3.9: 1 ui+1j ; uij ; uij ; ui;1j 2 h2 s1 s3 s1 + s3 = uxx(xi yj ) ; Rij 2 2 3 s1 + s1 2 Rij = (s3 ;3 s1)h uxxx(xi yj ) ; s3 ; s12 h uxxxx( yj ) xj ; s3h < < xj + s1h :.

(49) 3.4 Finite Dierenzen: Fortsetzung. 33 (i,j+1). s2 h s3 h 3. (i,j). s1 h (i+1,j). (i-1,j). s4 h. (i,j-1). Abbildung 3.9: Ein allgemeiner Gitterpunkt. Falls jsk j 1 1 k 4 M3 := sup juxxxj M4 := sup juxxxxj gilt . 1 1 h2M jRij j hM3 + 3 12 4 Siehe z.B. Forsythe und Wasow 1960, S. 188].. 3.4.3 Beispiel 3: Neumann Bedingungen auf gekrummten Randern. 4. 2. 3. n. 1. Abbildung 3.10: Approximation von Neumann Bedingungen. Die Normalenableitung am Punkt P4 in Abbildung 3.10 kann folgendermaen approximiert werden:.

(50) 34. Finite Dierenzen @u (P ) =: u4 ; u~3 @n 4 jP4 ; P3j. wobei. u~3 = u1 jP3 ;jPP2 j;+Pu2jjP1 ; P3j : 1. 2. 3.4.4 Beispiel 4: Die Minimaloberachengleichung (1 + u2y )uxx ; 2uxuy uxy + (1 + u2y )uxx = 0 kann folgendermaen auf einem quadratischen Gitter (Abbildung 3.11) approximiert werden: 7. 3. 6. 4. 1. 2. 8. 5. 9. Abbildung 3.11: Nachbarpunkte fur die Minimalober achengleichung. ux uy uxx uyy uxy. =: =: = = =. (u2 ; u4)=2h (u3 ; u5)=2h (u2 + u4 ; 2u1)=h2 (u3 + u5 ; 2u1)=h2 (u6 + u8 ; u7 ; u9)=4h2 :. 3.5 Das Maximumprinzip fur Di erenzengleichungen Das Maximumprinzip fur elliptische partielle Dierentialgleichungen lat sich auf Dierenzengleichungen ubertragen..

(51) 3.5 Das Maximumprinzip fur Dierenzengleichungen. 35. Sei Gh ein Gitter und S Gh. Ein linearer Dierenzenoperator `, z.B. h, kann folgendermaen geschrieben werden: (ù)(P ) =. X Q2S. A(P Q)u(Q) :. (3.27). Man sagt, der Dierenzenoperator ` sei nichtnegativ an der Stelle P 2 S , falls (ù)(P ) =. X Q2S. A(P Q)u(Q) . A(P P ) < 0 A(P Q) 0 fur P 6= Q . (3.28) (3.29). und. X Q6=P. jA(P Q)j jA(P P )j :. (3.30). Man setzt (ù)(P ) =. X Q2S. B (P Q)u(Q) + f (P )u(P ). = (mu)(P ) + f (P )u(P ). (3.31). mit. X Q2S. B (P Q) = 0 :. (3.32). In diesem Absatz wird stets angenommen, da m nichtnegativ ist, d.h.. B (P P ) < 0 B (P Q) 0 Q 6= P X B (P Q) = ;B (P P ) :. Q6=P. (3.33) (3.34) (3.35). Die Menge der Nachbarn von P 2 Gh bzgl. ` wird durch N (P ) := fQ 2 Gh : A(P Q) 6= 0 Q 6= P g. (3.36).

(52) 36. Finite Dierenzen. bezeichnet. Ist R eine Teilmenge von S , wird @R, der Rand von R bzgl. `, erklart durch. @R := fQ 2 S ; R : A(P Q) 6= 0 fur mindestens einen Punkt P 2 Rg. (3.37). R := R

(53) @R : Eine Menge R Gh heit zusammenhangend bzgl. `, falls es fur jedes Paar P Q 2 R eine endliche Folge P1 : : : Pr gibt mit: P1 = P Pr = Q A(Pj Pj+1) 6= 0 1 j r ; 1 : Sei H = H (S ) die Menge aller Gitterfunktionen auf S .. (3.38). Es gilt (mv)(P ) = = =. X Q2S. X. Q6=P. X. Q6=P. B (P Q)v(Q) B (P Q)v(Q) ; v(P )] + v(P ) B (P Q)v(Q) ; v(P )]. X Q2S. B (P Q). (3.39). Man sagt, da v 2 H ein lokales Maximum/Minimum bzgl. ` an der Stelle P hat, falls. v(Q) v(P ) fur Q 2 N (P ) bzw. v(Q) v(P ) fur Q 2 N (P ) : Lemma 3.1 v 2 H habe ein lokales Maximum an der Stelle P . Dann gilt (mv)(P ) 0.. Beweis:. (mv)(P ) =. X Q6=P. 0. wegen (3.40) und (3.39).. B (P Q)v(Q) ; v(P )]. (3.40).

(54) 3.5 Das Maximumprinzip fur Dierenzengleichungen. 37. Satz 3.1 (Das Maximumprinzip) Sei R eine zusammenhangende Teilmenge von S.. 1. Falls mv 0 in R und v ein Maximum auf R in einem Punkt P 2 R annimmt, dann ist v konstant auf R. 2. Sei f 0 und `v 0 in R, v nehme sein Maximum auf R in einem inneren Punkt an, und dieses Maximum sei positiv. Dann ist v konstant auf R. 3. Sei f 0 und `v 0 in R und @R 6= . Dann gilt v maxf0 max vg @R. 4. Sei mv 0 in R und das Maximum von v auf R in einem Punkt P0 2 @R erreicht. Dann ist entweder v konstant oder v(P0) ; v(P ) > 0 fur P 2 R. 5. Sei f 0 und `v 0 in R und sei das Maximum von v auf R in einem Punkt P0 2 @R erreicht. Ist das Maximum positiv, dann ist entweder v konstant oder v(P0) ; v(P ) > 0 fur P 2 R.. Beweis von 1: Sei P 2 R mit. v(P ) = = max v : R. Da v an der Stelle das Maximum erreicht, folgt aus Lemma 3.1, da (mv)(P ) 0. Es angenommen, da mv(P ) 0. Es folgt mv(P ) = 0, d.h. (mv)(P ) = P wurde Q6=P B (P Q)v (Q) ; v (P )] = 0. Folglich gilt. v(Q) = v(P ) = Q 2 N (P ) : Aber R ist `-zusammenhangend, so da v(Q) = fur alle Q 2 R.. Beweis von 2: Sei P 2 R und v(P ) = = maxR v > 0. Es folgt - wie in dem Beweis von 1 - da mv(P ) 0. Es wurde vorausgesetzt, da `v(P ) 0. Es ergibt sich. mv(P ) = `v(P ) ; f (P )v(P ) 0 so da mv(P ) = 0. Wie bei dem Beweis von 1 folgt jetzt, da v(Q) = fur Q 2 R..

(55) 38. Finite Dierenzen. Beweis von 3: 3 ist nur eine andere Formulierung von 2.. Beweis von 4 und 5: Sofort einzusehen.. Satz 3.2 Sei R eine `-zusammenhangende Teilmenge von S und @R 6= . Sei ` nichtnegativ auf R. Die Funktionen und g haben Denitionsbereiche R bzw. @R. Dann hat das Problem `v = g in R. (3.41). v = auf @R. eine eindeutige Losung v 2 H (R).. Beweis:. Nach Voraussetzung gilt. `v(P ) = mv(P ) + f (P )v(P ) mit f 0. Das Problem (3.41) ist auch ein Problem in linearer Algebra: es gibt M = jRj Gleichungen fur die M Unbekannten v(P ) P 2 R. Es folgt, da v existiert, falls v eindeutig ist, d.h. falls V 0 die einzige Losung des folgenden Problems ist:. `V = 0 in R V = 0 auf @R Aber mit Hilfe des Satzes 3.1 sehen wir, da max V maxf0 0g = 0 R max (;V ) maxf0 0g = 0 R. so da V 0 wie benotigt.. .

(56) 3.5 Das Maximumprinzip fur Dierenzengleichungen. 39. Satz 3.3 Sei R eine `-zusammenhangende Teilmenge S mit @R 6= .Sei ` nichtnegativ auf R. Sei 2 H (R) mit. ` 1 in R 0 auf R. (3.42). Sei M = max : @R. (3.43). max jv(P )j max jv (P )j + M max j`v j @R R. (3.44). w = v max j`v j : R. (3.45). Dann gilt fur alle v 2 H :. Beweis:. R. Sei. Man rechnet nach, da. `w; 0 `w+ in R : Folglich (siehe Satz 3.1):. w+ maxf0 max w+ g @R w; minf0 min w g in R @R ;. Aus (3.45) und (3.46) mit Hilfe von (3.42) und (3.43) schliet man:. Genauso folgt:. v w+ max jw+ j @R max jv j + M max j`v j : @R R. v w; ; max jw;j ;max jv j + M max j`v j] : @R @R R Damit ist der Satz bewiesen.. (3.46).

(57) 40. Finite Dierenzen. 3.6 Konvergenzbeweise Sei ein beschranktes Gebiet und Lu := auxx + 2buxy + cuyy + dux + euy + qu fur (x y ) 2 . gleichmaig elliptisch mit q 0. Sei a b c d e q 2 C (). Sei h = fh0 h1 : : : g, wo hk+1 < hk und hk ! 0 fur k ! 1. Fur h 2 h sei Sh und `h ein Dierenzenoperator auf Rh Sh. Sei im weiteren `h nichtnegativ, Rh `h-zusammenhangend, @Rh 6= und @Rh @ . f`h Rh hg heit eine gleichmaig konsistente Approximation zu L bezuglich C (N ) (), wenn fur alle u 2 C (N ) (). lim max j`hrhu ; shLuj = 0 h!0 R h2h. h. f`h Rh hg heit eine gleichmaig konsistente Approximation der Ordnung k zu L bezuglich C (N ) (), wenn fur alle u 2 C (N ) (). max j`hrh u ; sh Luj Khk ( mit K von h unabhangig : R h. Beispiel 3.2 Wenn `h und h = Rh wie in Absatz 4.2, konstruiert werden, dann ist f`h Rh hg gleichmaig konsistent der Ordnung 2 bezuglich C (4) (). Lemma 3.2 Sei f`h Rh hg eine gleichmaig konsistente Approximation zu L. Dann existiert eine Gitterfunktion , so da fur h 2 h, h genugend klein, 0 `h 1 in Rh :. Beweis: Sei := ex2 , wo > 0 eine Konstante ist. Dann ist 0. Auch L = ex2 a2 + d + q ] :. Man wahle , so da L 2 in :. Es folgt fur h klein jshL ; `h rj 1 in Rh :.

(58) 3.6 Konvergenzbeweise. 41. Satz 3.4 Sei f`h Rh hg eine gleichmaig konsistente Approximation zu L bezuglich C (N ) ().. Sei u 2 C (N ) () mit Lu = g in (). u = auf @ :. Sei vh die Losung der Dierenzengleichungen, deren Existenz und Eindeutigkeit durch Satz 3.2 gewahrleistet ist `hvh = g in Rh vh = auf @Rh :. Dann gilt lim max jvh(P ) ; u(P )j = 0 :. h!0 Rh. Sei zusatzlich f`h Rh hg eine gleichmaig konsistente Approximation der Ordnung k zu L bezuglich C (N ) (R), dann gilt max jvh(P ) ; u(P )j = O(hk ) : Rh. Beweis:. Sei wh := vh ; rhu. Aus Lemma 3.2 und Satz 3.3 folgt: max jwhj max jwhj + M max j`hwh j R @R Rh. h. h. mit M = max@ . Da wh = 0 auf @Rh und `hvh = g = Lu in Rh, folgt max jwhj M max j`hrh u ; Luj : R Rh. h. Der Satz folgt sofort. Satz 3.4 stammt von Gerschgorin 1930]. Ein Nachteil dieses Satzes ist, da vorausgesetzt wird, da der Dierenzenoperator `h den Dierentialoperator L mit der gleichen Genauigkeit uberall in Rh approximiert. Es wurde zuerst von Wasow bemerkt, da die Ordnung des Fehlers ungeandert ist, wenn `h L mit weniger Genauigkeit in der Gegend von @ approximiert. Diese Ideen werden jetzt fur die Laplace-Gleichung erklart:.

(59) 42. Finite Dierenzen uxx + uyy = 0 in u = auf @ . Sei Gh ein Gitter mit der Maschenweite h und Rh = Gh \ . Sei. wh := rhu ; vh der Fehler, wo vh die Losung der noch anzugebenden Dierenzengleichungen ist. Sei. Rh = Rh0

(60) Rh00 wo. Rh0 = Menge der \regularen" inneren Punkte Rh00 = Menge der \nicht-regularen" inneren Punkte d.h. Punkte mit mindestens einem Randpunkt als Nachbar. (Siehe Abbildung 3.12.) reguläre innere Punkte irreguläre innere Punkte Randgitterpunkte. Abbildung 3.12: Regulare und nicht-regulare Punkte. Zuerst betrachten wir Rh0 . Ist P 2 Rh0 , benutzen wir die ubliche Funfpunkt-Formel: vh(P1) + vh(P2) + vh(P3) + vh(P4) ; 4vh(P ) = 0 h2 mit einem Fehler 0(h2). Folglich - siehe den Beweis von Satz 3.4 - gilt: kwh kR0h kwhk@R0h + K 0 h2 :.

(61) 3.6 Konvergenzbeweise. 43 P2 h2 P3. h3. P. h1. P1. h4. P4. Abbildung 3.13: Die Nachbarn eines nicht-regularen Punktes P 2 Rh00. Aber @Rh0 Rh00

(62) @ und wh(P ) = 0 fur p 2 @R @ , so da kwhkR0h kwhkR00h + K 0 h2 :. (). Jetzt betrachten wir Rh00 . Ist P 2 Rh00 , benutzen wir die Formel (siehe Abbildung 3.13).. A1 vh(P1) + A2 vh(P2) + A3vh(P3) + A4vh(P4) ; A0vh(P0) = 0 A1 = h (h 2+ h ) A3 = h (h 2+ h ) 1 1 3 3 1 3 2 2 A2 = h (h + h ) A4 = h (h + h ) 2 2 4 4 2 4 4 X A0 = Ai i=1. mit einem Fehler 0(h). jwh j erreiche das Maximum in Rh00 an der Stelle P0 . Dann gilt 4 X 2 h A0 jwh(P0)j i=1. h2Ai jwh(Pi)j + K 00 h3 . Es ist leicht einzusehen, da 1. h2 Ai 1 2. h2 Ai 2, wenn hi = h. 3. Ist hi < h, dann ist Pi 2 @Rh und wh(Pi) = 0..

(63) 44. Finite Dierenzen. Sei. I 0 := fij1 i 4 Pi 2 Rh0 g I 00 := fij1 i 4 Pi 2 Rh00 g I 000 := fij1 i 4 Pi 2 @Rh g P0 2 Rh00 , so da P0 mindestens einen Randpunkt als Nachbarn hat und I 000 nicht leer ist. Dann ergibt sich. h2 A0jwh(P0)j kwhkR0h h2 so da. X I0. Ai + kwhkR00h. X I 00. Aih2 + K 00 h3. 0 1 X @h2A0 ; h2 AiA kwhkR00 X h2 AikwhkR0 + K 00 h3 : h h I 00. Da. h2 A0 ;. X I 00. h2Ai =. I0. X i2I 000. h2Ai +. X i2I 0. h2 Ai 1 +. X I0. h2 Ai . folgt 00 3 a K h + kwkR00h kwkR0h a+1 a+1. mit. a :=. X I0. h2Ai :. Aber 0 a 6, so da. 6 () 7 Wir kombinieren die Ungleichungen () und (): 6 kwkR0h K 0 h2 + kwkR0h + K 00 h3 7 so da kwkR00h kwkR0h + K 00 h3. kwkR0h 7K 0 h2 + K 00 h3 ] kwkR00h 6K 0 h2 + K 00 h3 ] + K 00 h3 :.

(64) 3.6 Konvergenzbeweise. 45. D.h. kwhk = 0(h2). Diese Ideen konnen naturlich fur allgemeinere Operatoren `h angewandt werden. Eine solche Verallgemeinerung bendet sich in Forsythe und Wasow 1960].. Literatur: Bjorck, A. und Dahlquist, G.: Numerische Methoden. Oldenbourg, Munchen, 1979. Collatz, L.: Numerische Behandlung von Dierentialgleichungen, 2. Auage. Springer, 1955.. Courant, R., Friedrichs, K., Lewy, H.: U ber die partiellen Dierenzengleichungen der. mathematischen Physik. Math.Ann. 100, 32-74 (1928).. Forsythe, G.E., Wasow, W.R.: Finite Dierence Methods for Partial Dierential Equations. John Wiley, 1960.. Gerschgorin, S.: Fehlerabschatzung fur das Dierenzenverfahren zur Losung partieller Dierentialgleichungen. Z. Angew. Math. Mech. 10, 373-382 (1930).. Gromann, Ch., Roos, H.-G.: Numerik partieller Dierentialgleichungen. Teubner, 1992.. Hackbusch, W.: Theorie und Numerik elliptischer Dierentialgleichungen. Teubner, 1986.. Norlund, N.E.: Vorlesungen uber Dierenzenrechnungen. Chelsea, New York, 1954.. Neudruck eines Buches aus den zwanziger Jahren.]. Richardson, L.F.: The approximate arithmetical solution by nite dierences of physical. problems involving dierential equations with an application to the stresses in a masonry dam. Phil. Trans. Roy. Soc. London A 210 (308-357), 1911.. Runge, C.: U ber eine Methode, die partielle Dierentialgleichung u = Constans numerisch zu integrieren. Z. Math. u. Phys. 56 (225-232), 1908.. Strikwerda, J.C.: Finite Dierence Schemes and Partial Dierential Equations. Wadsworth and Brooks/Cole, 1989..

(65)

(66) Kapitel 4 Iterationsverfahren zur Losung groer linearer Gleichungssysteme: klassische Verfahren 4.1 Einleitung Im vorherigen Kapitel sind Randwertaufgaben fur elliptische partielle Dierentialgleichungen durch nite Dierenzen approximiert worden. Das Problem. Au = f auf u = g auf @ . (4.1). wurde dadurch durch das Problem. Ahuh = fh. (4.2). Ah : Vh ! Fh. (4.3). approximiert, wobei. und Vh und Fh endlichdimensionale Banachraume sind. Alle anderen numerischen Methoden zur Approximation der Gleichung (4.1) fuhren ebenfalls zu einer Gleichung der Gestalt (4.2). Die Gleichung (4.2) hat mehrere Eigenschaften: 1. Die Dimension N des Raumes Vh kann sehr grosein, z.B. N = 106..

(67) 48. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. 2. Wird die Gleichung (4.2) als eine Matrixgleichung betrachtet, dann ist die Matrix Ah oft dunnbesetzt, symmetrisch, positiv- denit und diagonal dominant. (Dies gilt insbesondere fur das Modellproblem u = f .) Es gilt, diese Eigenschaften von Ah auszunutzen. Zur Losung der Gleichung (4.2) konnen entweder iterative oder direkte Methoden angewandt werden. In diesem Abschnitt werden iterative Methoden diskutiert. Die folgenden Themen werden behandelt: Das Jacobi Verfahren Das Gau-Seidel Verfahren Mehrgittermethoden Das konjugierte Gradientenverfahren. 4.2 Hilfsmittel Die folgenden Begrie und Satze werden spater benotigt (siehe Numerik I):. Denition 4.1 Sind i 1 i ` , die Eigenwerte von A 2 M (n n) , so nennt man (A) := 1max j j i` i. den Spektralradius von A . Denition 4.2 Eine Matrix J 2 M (r r) heit Jordanmatrix zum Eigenwert , wenn 1 0. 1 O CC BB 1 C B J=B . . . 1 CC B@ A O. Satz 4.1 (Jordansche Normalform) Sei A 2 M (n n). Es gibt eine regulare Matrix S 2 M (n n) , so da gilt 0 1 J 1 BB J CC 2 B C ; 1 SAS = J = B . . . CC B@ A J` wobei fur 1 r ` Jr 2 Mat(nr nr ) eine Jordanmatrix ist, 0 1. 1 O r BB CC r 1 B C Jr = B . . . 1 CC B@ A O r.

(68) 4.2 Hilfsmittel. 49. Beweis: Siehe Fischer, Lineare Algebra, Anhang B. Die charakteristischen Polynome pr ( ) = det(Jr ; I ) = ( r ; )nr heien die Elementarteiler von A .. Satz 4.2 Fur alle Eigenwerte von A gilt j j lub(A) := sup x6=0. kAxk kxk. fur jede Vektornorm k k. Beweis: Sei ( v) ein Eigenpaar von A , d.h. Av = v mit v 6= 0 . Dann folgt j j kv k = kAv k kAk kv k :. Satz 4.3. mit. a) Zu jeder Matrix A und jedem > 0 existiert eine Vektornorm k k^ lub(A)^ = kAk^ (A) + :. b) Hat jeder Eigenwert von A mit der Eigenschaft j j = (A) nur lineare Elementarteiler, so existiert sogar eine Vektornorm k k^ mit kAk^ := lub(A)^ = (A) :. Beweis von a): Sei SAS ;1 = J , wo J in Jordannormalform ist, J = diag(J1 : : : J`) , 0J 1 1 B CC ... J =B @ A J`. 0 BB r 1 1 O r Jr = B BB ... 1 @ O r. 1 CC CC CA. Sei C () := C := diag(C1 : : : C`) mit. Cr = Cr () = diag(1 : : : nr ;1 ) 2 Mat(nr nr ) :.

(69) 50. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Es folgt. C ;1JC = diag(C1;1J1C1 : : : C`;1J`C`) . mit. 0 BB r O r Cr;1Jr Cr = B BB ... @ O r. Es folgt sofort, da. 1 CC CC CA. kC ;1 JC k1 (A) + . so da gilt. kTAT ;1k1 (A) + . mit. T := C ;1 S :. D.h. (siehe Hilfssatz) Beweis von b): Fur. kAk^ := kTAT ;1 k1 (A) + :. < (A) ; j max j j j< (A) r. setze. (. r. < (A) Dr = CrI() jj rjj = (A) r D = diag(D1 : : : D`) :. Dann gilt:. kD;1 JDk1 = (A) :. Hilfssatz: Sei k k eine Vektornorm und T 2 Mat(n n) eine regulare Matrix. Dann ist k k^ , kxk^ := kTxk. eine Vektornorm und lub(A)^ = kTAT ;1k fur alle A 2 Mat(n n) : Beweis: k k^ ist eine Vektornorm, da die drei notwendigen Voraussetzungen oensichtlich erfullt sind..

(70) 4.2 Hilfsmittel. 51. Es gilt fur A 2 Mat(n n) , k^ lub(A)^ = sup kkAx x6=0 xk^ ;1 y k^ = sup kkAT y6=0 T ;1y k^ ;1 y k = sup kTAT ky k y6=0 ; 1 = kTAT k. Satz 4.4 Sei A 2 Mat(n n) . Der Limes existiert und ist gleich (A) .. R(A) := klim kAk k1=k !1. Beweis: Sei. Rk := kAk k1=k und ( x) ein Eigenpaar von A . Dann gilt: " k #1=k Rk kAkxkxk = j j so da. Rk (A) : () Sei nun > 0 beliebig. Es folgt aus Satz 4.3, da es eine Norm k k

(71) gibt mit kAk

(72) (A) + : Alle Normen auf dem n sind aquivalent, es gibt deshalb eine Konstante m = m() mit 1 kxk kxk mkxk :

(73) m Es folgt " # kAk xk 1=k Rk = sup kxk x6=0 " 2 kAk xk #1=k m

(74) sup k x k x6=0

(75) 2 =k k = m kA k

(76) ]1=k m2=k kAk

(77) m2=k ((A) + ) (). R.

(78) 52. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Fur alle m > 0 gilt. lim m2=k = 1 : Der Satz folgt deshalb sofort aus den Ungleichungen (*) und (**). k!1. Bemerkung 4.1 Es folgt aus diesem Satz, da der Spektralradius (A) nicht nur die. Konvergenz des Verfahrens xk+1 = Ax + b, sondern auch dessen asymptotische Konvergenzgeschwindigkeit bestimmt.. Bemerkung 4.2. a) (A) kAk. b) (A) < 1 und (B ) < 1 impliziert i.a. nicht (AB ) < 1 . Beispiel 4.1 a) ! 1k 1 )k;1 ! 1 = 2 100 ( ) 100 k ( A = 0 1=2 Ak = 02 ( 1 )k 2 2. b). . A = 10=2 100 1=2. . !. . =2 0 B = 1100 1=2. 4 + 1=4 50 AB = 10 50 1=4. !. !. (A) = (B ) = 1=2 (AB ) > 1 : Genauere Information uber die Potenzen Am einer Matrix A erhalt man aus der Jordanschen Normalform.. Satz 4.5 A sei eine n n-Matrix mit (A) > 0 . Dann gilt: kAm k

(79). . ! m (A)]m;(p;1) m ;! 1 p;1. wo p die grote Ordnung aller Jordanscher Blockmatrizen J von A mit (J ) = (A) und

(80) eine positive Konstante ist. Beweis: Siehe Varga, Matrix Iterative Analysis, S. 65..

(81) 4.3 Das Jacobi-, Gau-Seidel-, SOR- und SSOR-Verfahren - eine Einleitung 53 Beispiel 4.2. . !. 1 A= 0 m m;1 !. m m A = 0 m :. 4.3 Das Jacobi-, Gau-Seidel-, SOR- und SSORVerfahren - eine Einleitung In diesem Abschnitt werden vier wichtige Iterationsverfahren zur Losung des Gleichungssystems Ax = b (4.4) vorgestellt. Im nachsten Abschnitt wird die Konvergenz dieser Verfahren untersucht.. 4.3.1 Anwendung auf ein Modellproblem Als Beispiel nehmen wir 0 1 0 1 0 1 4 0 ;1 ;1 2 BB 0 4 ;1 ;1 CC BB 2 CC BB 11 CC A=B B@ ;1 ;1 4 0 CCA b = BB@ 2 CCA x = BB@ 1 CCA ;1 ;1 0 4 2 1 Die Randwertaufgabe. (4.5). u = 0 in u = 1 auf @ := (0 1) (0 1) werde unter Anwendung des Funfpunktsterns mit Schrittweite h = 13 approximiert. Die Numerierung der Knoten sei dabei wie in Abbildung 4.1a) . Es ergibt sich nach Elimination der vorgeschriebenen Randwerte:. Ahuh = fh. 0 1 4 ;1 ;1 0 BB ;1 4 0 ;1 CC Ah := B B@ ;1 0 4 ;1 CCA 0 ;1 ;1 4.

(82) 54. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren (1,1). (1,1). 3. 4. 4. 2. 1. 2. 1. 3. (0,0). (0,0) a) Natürliche Numerierung. b) Schachbrettnumerieung. Abbildung 4.1: Mogliche Numerierungen. 0 1 0 1 g(h 0) + g(0 h) BB g(2h 0) + g(1 h) CC BB 22 CC fh = B B@ g(h 1) + g(0 2h) CCA = BB@ 2 CCA g(2h 1) + g(1 2h) 2 0u 1 011 BB u1 CC BB 1 CC 2 uh = B B@ u3 CCA = BB@ 1 CCA u4 1 Ah uh und fh werden naturlich durch die Numerierung der Gitterpunkte beeinut. Eine A nderung der Numerierung fuhrt dazu, da Ah uh und fh durch A~ h u~h und f~h ersetzt werden, wobei A~ h = P T AhP u~h = P T uh f~h = P T fh und P eine Permutationsmatrix ist. Fur die Numerierung in Abbildung 4.1b) gilt:. 0 4 0 ;1 ;1 1 B 0 4 ;1 ;1 CC BB C f~ = f u~ = u ~Ah = B @ ;1 ;1 4 0 CA h h h ;1 ;1 0 4 mit. 0 BB 10 P =B B@ 0 0. 0 0 1 0. 0 0 0 1. 1 0 CC 1C 0C A 0. (4.6).

(83) 4.3 Das Jacobi-, Gau-Seidel-, SOR- und SSOR-Verfahren - eine Einleitung 55 Bei allen drei Verfahren wird A als Dierenz von zwei Matrizen M und N dargestellt,. A=M ;N . (4.7). wobei gilt: 1. M sei regular 2. M sei \leicht invertierbar", d.h. die Gleichung My = c sei fur beliebiges c leicht zu losen. Das Gleichungssystem (4.4) kann dann in der Gestalt. Mx = b + Nx oder. x = M ;1 b + M ;1 Nx geschrieben werden. Es liegt deshalb nahe, das Iterationsverfahren x(k+1) = Bx(k) + d k 0 zu benutzen mit. B := M ;1 N d := M ;1 b : Es ist manchmal sinnvoll, die folgende Zerlegung von A zu benutzen:. A D L R. = = = =. D ; L ; R mit diag(A) linke Dreiecksmatrix rechte Dreiecksmatrix. 4.3.2 Das Jacobi-Verfahren oder Gesamtschrittverfahren Zur Losung von wird die Zerlegung. Ax = b A = M ;N M := D = diag(A) N := D ; A = L + R. benutzt. Es folgt. x(k+1) = Bx(k) + d. (4.8).

(84) 56. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. mit. Es folgt weiter:. d = D;1b B = D;1(D ; A) = D;1(L + U ) = I ; D;1 A :. Dx(k+1) + (A ; D)x(k) = b : Dies ist die Gleichung, der die Bezeichnung \Gesamtschrittverfahren" zugrunde liegt. Die Matrix B = I ; D;1A wird oft als Jacobi-Matrix bezeichnet.. Beispiel 4.3 Wir betrachten das Modellproblem Ax = b mit A = A~ h b = f~h x = u~h. aus (4.6). Dann gilt fur das Jacobi-Verfahren 0 1 0 0 1=4 1=4 BB 0 0 1=4 1=4 CC B=B B@ 1=4 1=4 0 0 CCA : 1=4 1=4 0 0 Mit x(0) = (0 0 0 0)T gilt: x(1) = (0 5 0 5 0 5 0 5)T x(2) = (0 75 0 75 0 75 0 75)T x(10) = (0 999023 0 999023 0 999023 0 999023)T ... x(20) = (0 9999 0 9999 0 9999 0 9999)T Bemerkung 4.3 Bei Verwendung der Numerierung wie in Abbildung 4.1a) erhalt man folgende Jacobimatrix: 0 0 1=4 1=4 0 1 BB 1=4 0 0 1=4 CC B=B B@ 1=4 0 0 1=4 CCA 0 1=4 1=4 0. 4.3.3 Das Gau -Seidel-(Einzelschritt-) Verfahren M = D;L N = R B = G := (D ; L);1R (D ; L)xk+1 ; Rx(k) = b.

(85) 4.3 Das Jacobi-, Gau-Seidel-, SOR- und SSOR-Verfahren - eine Einleitung 57 Beispiel 4.4 Mit x(0) x(1) x(2) x(10). = = = =. (0 0 0 0)T gilt: (0 5 0 5 0 75 0 75)T (0 875 0 875 0 9375 0 9375)T (0 99998 0 99998 0 99999 0 99999)T. 4.3.4 Das S.O.R.-Verfahren ! 2 (0 2) M = !1 D ; L N = 1 ;! ! D + R B (!) = L! := (D ; !L);1((1 ; !)D + !R) (D ; !L)x(k+1) ; ((1 ; !)D + !R)x(k) = c. Beispiel 4.5 Mit x(0) ! (1) x x(10). = = = =. (0 0 0 0)T 1 5 gilt: (0 75 0 75 1 3125 1 3125)T (0 99882 0 99882 1 00002 1 00002)T :. Mit. x(0) ! x(1) x(7). = = = =. (0 0 0 0)T 1 0718 gilt: (0 535898 0 535898 0 823085 0 823085)T (1 0000 1 0000 1 0000 1 0000)T. 4.3.5 Das SSOR-Verfahren Dieses Verfahren besteht aus der Zusammenfassung eines Vorwarts- und eines RuckwartsSOR-Verfahrens..

(86) 58. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren ! 2 (0 2) Mv = !1 D ; L Nv = 1 ;! ! D + R Mr = !1 D ; R Nr = 1 ;! ! D + L S (!) = Mr;1 Nr Mv;1 Nv d = Mr;1 b + Br Mv;1 b. Der groe Vorteile des SSOR-Verfahrens ist, da S (!) ahnlich zu einer symmetrischen Matrix ist, wenn A symmetrisch ist, so da dann die Eigenwerte von S (!) reell sind. Mit. x(0) = (0 0 0 0)T ! = 1 5 gilt: (1) x = (0 86719 0 86719 0 65625 0 65625) x(10) = (0 99995 0 99995 0 99918 0 99918). 4.4 Allgemeine Konvergenzbetrachtungen Denition 4.3 Das Iterationsverfahren xk+1 = Bxk + d B = M ;1 N d = M ;1 b. zur Losung des Gleichungssystems Ax (M ; N )x = b heit konvergent, falls fur alle Startvektoren x(0) und Vektoren b die Folge fx(k) g gegen die exakte Losung x = A;1b konvergiert. Wir konnen jetzt notwendige und hinreichende Bedingungen fur Konvergenz herleiten. Der folgende Satz ist sowohl eine Erweiterung (da eine hinreichende Bedingung.

(87) 4.4 Allgemeine Konvergenzbetrachtungen. 59. gegeben wird) als auch eine Spezialisierung (da nur lineare Abbildungen betrachtet werden) des Banachschen Fixpunktsatzes.. Satz 4.6 Das Iterationsverfahren x(k+1) = Bx(k) + d. (). ist genau dann konvergent, wenn (B ) < 1 : Beweis: a) Sei (*) konvergent. Fur jedes d konvergiert die Folge x(0) := 0 x(k+1) = Bx(k) + d . Sei x := klim x(k) : !1 Es gilt x = Bx + d , so da die Gleichung. y = By + d. R R. fur jedes d eine Losung hat. D.h. die Abbildung F := I ; B ,. F:. n. ;!. n. ist surjektiv und deshalb bijektiv (Fischer, S. 86). Fur den Fehler f (k) := x ; x(k) gilt:. f (k+1) = Bf (k) : Wahle x(0) so, da f (0) = v , wobei f vg ein Eigenpaar fur B ist:. x(0) := 0 d := (I ; B )v Es folgt: und daher j j < 1 .. N. f (k) = k v k 2 . b) Sei umgekehrt (B ) < 1 . Es folgt aus Satz 4.3 (x2.2), da eine Norm existiert mit kB k < 1 . Es folgt, da die Abbildung g(u) := Bu + d kontrahierend ist. Man benutzt jetzt den Banachschen Fixpunktsatz..

(88) 60. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Eine einfache aber oft nutzliche notwendige Bedingung fur die Konvergenz des Gesamtschrittverfahrens wird jetzt hergeleitet.. Denition 4.4 Die Matrix A 2 Mat(n n) erfullt das starke Zeilensummenkriterium falls. jaii j >. n X j =1 j 6=i. jaij j 1 i n :. Satz 4.7 Die Matrix A erfulle das starke Zeilensummenkriterium. Dann konvergiert das Gesamtschrittverfahren. Beweis: Es gilt fur die Jacobi-Matrix B = (bij ) , n n X X jbij j = jaij j=jaiij < 1 1 i n j =1. j =1 j 6=i. bii = 0 1 i n Es gibt jetzt zwei einfache Methoden, um zu zeigen, da (B ) < 1. Methode 1: Wegen (*) gilt:. (). (B ) < kB k1 < 1 :. Methode 2: Sei f vg ein Eigenpaar von B . Wahle k , so da jvk j = kv k1 = max jvj j j. und betrachte die k-te Gleichung des Gleichungssystems v = Bv : n X j vk j = jbij j jvj j j =1. kv k1. < kvk1. n X j =1. jbij j. Es folgt, da j j < 1 .. Satz 4.8 Sei A 2 Mat(n n), A regular und L! die zugehorige SOR-Iterationsmatrix.. Dann gilt:. (L! ) j! ; 1j :.

(89) 4.4 Allgemeine Konvergenzbetrachtungen. 61. Beweis:. L! = (D ; !L);1((1 ; !)D + !R) : Es folgt:. (D ; !L)L! = (1 ; !)D + !R :. Weiter gilt: det(D) det(L! ) = = = = det(L! ) =. det(D ; !L) det(L! ) det((D ; !L)L! ) det((1 ; !)D + !R) (1 ; !)n det(D) so da (1 ; !)n :. Das Produkt der evtl. vielfaltigen Eigenwerte von L! ist gleich dem konstanten Term von det( I ; L! ) : n Y i = det(;L! ) = (! ; 1)n : i=1. Bemerkung 4.4 Es folgt aus Satz 4.8, da das SOR-Verfahren nur fur ! 2 (0 2) konvergent ist.. Satz 4.9 (Ostrowski-Reich). Sei A = D ;E ;E eine n n hermitesche Matrix, D eine positiv denite hermitesche Matrix, D ; !E nichtsingular fur 0 ! 2 . Sei L! = (D ; !E );1((1 ; !)D + !E ) :. a) Wenn A positiv denit ist und ! 2 (0 2), dann ist (L! ) < 1. b) Falls E eine linke untere Dreiecksmatrix und D eine Diagonalmatrix ist, gilt auch die Umkehrung. Beweis: Zuerst wird eine Hilfsgleichung hergeleitet. Die Fehler em := x ; xm erfullen die Gleichungen:. em+1 = L! em (D ; !E )em+1 = (!E + (1 ; !)D)em. (4.9) (4.10). m := em ; em+1 m 0 :. (4.11). Sei.

(90) 62. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Aus (4.10) folgt (D ; !E )m = (D ; !E ) ; (!E + (1 ; !)D)]em = !Aem (4.12) und !Aem+1 = !(D ; E ; E )em+1 = (! ; 1)D ; !E ]em+1 + (D ; !E )em+1 = (1 ; !)D + !E ](em ; em+1 ) = (1 ; !)Dm + !E m : (4.13) Werden Gleichungen (4.12) und (4.13) mit m bzw. m+1 multipliziert, wobei jeweils die konjugierte Transposition bedeutet, dann folgt, da S1 := em D ; !E ]m = !em Aem und (4.14) S2 := em+1 (1 ; !)D + !E ]m = !em+1 Aem+1 (4.15) Sei S := S1 ; S2 : (4.16) Es gilt: S = em D ; !E ]m ; em+1 (1 ; !)D + !E ]m = em D ; !E ]m ; (em ; m )(1 ; !)D + !E ]m = m (1 ; !)D + !E ]m + em !D ; !E ; !E ]m (4.17) m m m m = (1 ; !)D + !E ] + e !A = m (1 ; !)D + !E ]m + m !Aem : Mit Hilfe der Gleichung (4.12) folgt: S = m f(1 ; !)D + !E ] + D ; !E ]gm = (2 ; !)mDm : (4.18) Aus (4.14), (4.15), (4.16) und (4.18) folgt: (2 ; !)mDm = !fem Aem ; em+1 Aem+1 g : (4.19) Diese Gleichung ist der Schlussel zum Konvergenzbeweis, da daraus folgt, da unter bestimmten Voraussetzungen die Zielfunktion em Aem monoton fallend ist. Wahle ein Eigenpaar ( v) von L! und setze e0 = v . Dann folgt aus (4.19): e1 = L! e0 = e0 0 = (1 ; )e0 (2 ; !)j1 ; j2e0 De0 = !(1 ; j j2)e0 Ae0 : Wir konnen jetzt den Beweis durchfuhren.. (4.20) (4.21) (4.22).

(91) 4.4 Allgemeine Konvergenzbetrachtungen. 63. a) Sei A positiv denit und ! 2 (0 2) . Die Matrix D ist positiv denit. Wegen e0 = v 6= 0 gilt e0De0 > 0 . Es folgt aus (4.22), da entweder = 1 oder 1;j j2 > 0 . Ware = 1 , dann folgte aus (4.21), da 0 = 0 und folglich aus (4.12), da e0 Ae0 = 0 , was der Annahme e0 = v 6= 0 widerspricht. Es gilt deshalb. j j < 1 :. Da einen beliebigen Eigenwert darstellt, ist (B ) < 1 . b) Sei nun (L! ) < 1, E eine untere Dreiecksmatrix und D eine Diagonalmatrix. Dann konvergiert die Folge fxk g fur jedes x0 , so da em ! 0 fur m ! 1 . Es ist bekannt aus Satz 4.8, da j! ; 1j (L! ) < 1 . d.h. ! 2 (0 2). Es gilt, da ! 6= 0,. A = !1 (D ; !E )(I ; L! ) so da A regular ist. Ware A nicht positiv denit, hatte A mindestens einen negativen Eigenwert mit Eigenvektor v. Setze e0 := v. Es gelte:. e0 Ae0 < 0 : Es wurde dann aus (4.19) folgen, da. em+1 Aem+1 em Aem e0 Ae0 < 0 was der Konvergenz der Folge fem g gegen Null widerspricht. Zusammenfassend mugelten:. ! 2 (0 2) A positiv denit :.

(92) 64. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. 4.5 Die Gerschgorin Satze Gerschgorin1 hat einige Satze bewiesen, die manchmal bei der Abschatzung von Eigenwerten sehr nutzlich sind.. C. Satz 4.10 (Gerschgorin) Die Vereinigung aller Kreisscheiben Ki := f 2 j j ; aiij . n X k=1 k6=i. jaij jg. enthalt alle Eigenwerte der n n-Matrix A = (aik ). Ist die Vereinigung M1 = Ski=1 Ki disjunkt von der Vereinigung M2 der ubrigen Kreise, so enthalt M1 genau k Eigenwerte von A und M2 genau n ; k Eigenwerte. Beweis: Stoer und Bulirsch II, S. 77 und 78. Fur das Modellproblem 1 haben die vier Gerschgorin Kreise alle den Mittelpunkt (0 0) und den Radius 21 , so da (J ) 12 . Dieses Beispiel ist aber eine Ausnahme, weil keine echten inneren Gitterpunkte existieren. Sobald alle funf Gitterpunkte eines Sterns innere Gitterpunkte sind, liefert Satz 4.10 nur die Abschatzung (J ) 1, was die Konvergenz des Gesamtschrittverfahrens nicht garantiert. Es ist deshalb notwendig, einige weitere Begrie einzufuhren. Eine n n-Matrix A heit unzerlegbar (irreduzibel), falls es keine Permutationsmatrix P gibt, so da P T AP die Gestalt "~ ~ # 12 T P AP = A011 A A~ 22 besitzt, wo A~ 11 eine p p-Matrix, A~ 22 eine q q-Matrix mit p + q = n p > 0 q > 0 ist. Die Unzerlegbarkeit einer Matrix A kann man haug leicht mit Hilfe des der Matrix A zugeordneten (gerichteten) Graphen G(A) prufen. Wenn A eine n n-Matrix ist, so besteht G(A) aus n Knoten P1 : : : Pn, und es gibt eine gerichtete Kante Pi ! Pj in G(A) genau dann, wenn aij 6= 0. Z.B. ist der Graph von 2 3 1 2 0 6 7 A = 64 ;1 1 0 75 3 0 1 Gerschgorin, S.: U ber die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk SSSR Ser.Mat. 7, 749-754 (1931) 1.

(93) 4.5 Die Gerschgorin Satze. 65 3. 1 2. Abbildung 4.2: Der Graph G(A). in Abbildung 4.2 dargestellt.. A ist genau dann unzerlegbar, wenn der Graph G(A) in dem Sinne zusammenhangend ist, da es fur jedes Knotenpaar (Pi Pj ) in G(A) einen gerichteten Weg von Pi nach Pj gibt. Die Matrix A ist also genau dann unzerlegbar, wenn es fur jedes i j mit 1 i j n eine Folge i0i1 im gibt mit. i0 = i im = j aik ik+1 6= 0 fur 0 k < m.. Behauptung 4.1 Die Matrix Ah entstehe durch die Benutzung des Funfpunktesystems. auf dem Gitter Gh. Dann ist die Matrix Ah genau dann unzerlegbar, wenn Gh zusammenhangend ist.. C. Satz 4.11 A 2 Mat(n n ) sei unzerlegbar. Sei Eigenwert von A, 2 @K , wobei K die Vereinigung aller Gerschgorin Kreisscheiben ist. Dann gilt: 2 @Ki 1 i n : Beweis: Sei ( x) ein Eigenpaar von A mit 2 @K . O.E. gibt es r mit jxr j = 1 jxi j 1 i n :.

(94) 66. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Aus. Ax = x folgt. n X i=1. arixi = xr. und jarr ; j . X j =1 j 6=r. X j =1 j 6=r. jarj j jxj j jarj j. = Radius von Kr also 2 Kr . Die Voraussetzung, da 2 @K , fuhrt dazu, da 2 @Kr und jarj j 6= 0 ) jxj j = 1 1 j n :. Da A unzerlegbar ist, gibt es ein p = 6 r mit arp 6= 0, so da jxpj = 1. Durch Wiederholung ergibt sich: jxi j = 1 fur 1 i n . und 2 @Ki , fur 1 i n. Durch Anwendung von Satz 4.11 erhalt man:. Satz 4.12 (Schwaches Zeilensummenkriterium) Falls A unzerlegbar ist und jaii j . X k6=i. jaik j fur alle i = 1 2 : : : n . aber jai0 0 j > Pk6=i0 jai0 k j fur mindestens ein i0 gilt, dann konvergiert das Gesamtschrittverfahren.. Bemerkung 4.5 Die Jacobi Matrix J ist symmetrisch. Falls J zerlegbar ist, konnen die einzelnen Untermatrizen J1 : : : Jk getrennt betrachtet werden.. Satz 4.13 Das Gesamtschrittverfahren konvergiert fur die Funfpunkt- Dierenzenapproximation zur Losung des Dirichlet Problems fur die Laplace Gleichung. Beweis: Siehe Bemerkung oben..

(95) 4.6 Das Gesamtschrittverfahren - das Modellproblem. 67. 4.6 Das Gesamtschrittverfahren - das Modellproblem Es wurde im letzten Abschnitt bewiesen, da das Gesamtschrittverfahren fur das Dirichlet Problem konvergiert. Es stellt sich aber heraus, da die Konvergenzgeschwindigkeit viel zu wunschen ubrig lat, wie das folgende Modellproblem zeigt.. Beispiel 4.6 Zu betrachten ist das Problem: ;u = f (x y ) in . u = 0 auf @ . wobei := (0 1) (0 1) f 2 C () : Mit der Maschenweite. h = N 1+ 1. entsteht das Dierenzengleichungssystem. Ahvh = fh wobei Ah eine Blocktridiagonalmatrix ist: 0 BB H BB C 1 Ah = h2 B BB BB @. R. H C 2 Mat(N N ):. C = ;IN = ;I .. C H ... O. ... ... .... O ... H C. 1 CC CC CC CC CC A H. 0 1 4 ;1 B CC ... O B B CC ; 1 4 B B CC ... ... ... H=B B CC B . B . O . 4 ;1 C @ A ;1 4.

(96) 68. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. Die entsprechende Jacobi Matrix B ist: 0 BB F BB I 1 B= 4B BB BB @. 0 BB 0 BB 1 F =B BB BB @. R. I F ... O 1 0 ... O. R. ... ... .... ... ... .... 1 CC CC CC CC I C A F. O ... F I O ... 0 1. 1 CC CC CC ( CC 1C A 0. mit B 2 Mat(M M ), F 2 Mat(N N ), M := N 2 . Das Eigenwertproblem. Bv = v ist aquivalent zum Gleichungssystem: 1 v + v + v + v ] = v 1 i j N ij 4 ij+1 ij;1 i+1j i;1j wobei. vij := 0 fur i = 0 i = N + 1 j = 0 j = N + 1 : Der Ansatz. vijk` = sin(khi) sin(`hj ) fuhrt zu dem Eigenwert:. k` = 21 cos kh + cos `h] !2 !2 kh `h = 1 ; sin 2 ; sin 2 : Die N 2 Vektoren vk` sind linear unabhangig und bilden eine Basis des (B ) = 1 ; 2 sin2 h 2 = cos h :. R. N2 .. Weiter gilt:.

(97) 4.6 Das Gesamtschrittverfahren - das Modellproblem. 69. Wird das Gesamtschrittverfahren zur Losung des Gleichungssystems. Ahvh = fh benutzt, dann folgt mit Hilfe von Satz 4.13 aus dem vorigen Abschnitt, da 2 (k) 31=k k v ; v k h 5 = (B ) sup lim sup 4 h(0) vh0 6=vh k!1 kvh ; vh k d.h. im Durchschnitt und fur allgemeine Anfangsdaten vh(0) wird der Fehler kvh(k) ; vh(0) k mit dem Faktor (B ) pro Iteration multipliziert. Damit sich der Fehler um einen Faktor 1=e verringert, werden im Durchschnitt m Iterationen benotigt, wobei (B )]m = 1=e m = ;1= ln((B )) =: 22h2 :. Fur groes N (kleines h) sind deshalb sehr viele Iterationen notig. Der durchschnittliche Rechenaufwand, um den Fehler um einen Faktor 1=e zu reduzieren, ist 2 2 8 O 2 h2 Multiplikationen + O 2h2 3 Additionen = O 2 N 2 Operationen : Die vorherigen U berlegungen konnen von einem anderen Gesichtspunkt aus betrachtet werden. Fur die Gleichung. Ahvh = fh ist das Gesamtschrittverfahren. Dvk+1 + (Ah ; D)vk = fh oder. vk+1 = Bvk + D;1fh mit Die Fehler. 2 D := h12 diag(;4) B = I ; h4 Ah :. ek := vh ; vk.

(98) 70. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren. erfullen die Gleichung. ek+1 = Bek : Seien nun ( i wi) 1 i M , M Eigenpaare von B mit j 1j j 2j : : : j M j. Der Fehler e0 lat sich folgendermaen darstellen:. e0 =. M X i=1. ai wi . so da. ek =. M X i=1. ai ki wi :. Es folgt - wie bei der Vektoriteration - da der Fehler fur groes k sich etwa wie a1 k1 w1 verhalt,. ek a1 k1 w1 : Die asymptotische Konvergenzgeschwindigkeit wird deshalb durch j 1 j = (B ). bestimmt. Fur kleines k dagegen ist im allgemeinen die Konvergenzgeschwindigkeit etwas besser, da die Fehlerkomponente a2 w2 : : : aM wM sich schneller abbauen lat. Gerade diese Eigenschaft wird bei Mehrgitterverfahren genutzt. Weiter gilt:. 1 = cos h = 1 ; 2 sin2 h 2 w1 = vij11 = sin(hi) sin(hj ) so da w1 eine nichtnegative Gitterfunktion ist. Zusammenfassend gelten die folgenden Aussagen fur das Modellproblem, aber auch fur allgemeinere nichtnegative Dierenzenapproximationen: 1. Das Jacobi-Verfahren konvergiert. 2. (B ) 1 ; h21, mit 1 > 0..

(99) 4.7 Verallgemeinerungen. 71. 3. Der Fehler nach k Schritten. ek = vh ; vh(k) lat sich gut durch. ek constant (B )k w1 approximieren, wobei w1 > 0 eine \glatte" Gitterfunktion ist. 4. Die Anzahl der Iterationen, die benotigt werden, um den Fehler durchschnittlich um einen Faktor 1=e zu verringern, ist:. m = ;1= ln((B )) h21 : 1. 4.7 Verallgemeinerungen Die Aussagen im letzten Abschnitt fur das Modellproblem sind richtungsweisend fur allgemeine Probleme. Die Tatsache, da (B ) 1 fur die Jacobi Matrix B gilt, lat sich folgendermaen erklaren: Die Eigenwerte und Eigenfunktionen u einer schwingenden Membran mit Oberache erfullen die Bedingungen u = u in u = 0 auf @ : Bekanntlich gibt es unendlich viele Eigenpaare fi uig mit 0 < 1 2 : : : . Weiter gilt: i ! 1 fur i ! 1 ( Spanfuig = L2() und fuig ist eine orthogonale Basis fur L2 (). (Michlin 1978, S. 372]( Garabedian 1964, Chapter 11]( Dunford und Schwartz 1963, S. 1743].) Das diskrete Eigenwertproblem. Ahwh = hwh ist eine Approximation fur das Membranproblem. Man erwartet, da die Eigenwerte (hi) die Eigenwerte (i) approximieren sollen, d.h..

(100) 72. Iterationsverfahren fur groe lineare Systeme: klassische Verfahren (hi) (i) :. Es folgt, da B = I ; h42 Ah, da. i = 1 ; h4 (hi) h2 1 ; (i) : 4 2. Fur das Rechteck = (0 1)2 ist. N. = (k2 + `2 )2 und u = sin(kx) sin(`y). fur k ` 2 ein Eigenpaar fur die schwingende Membran. Es folgt was das exakte Ergebnis gut widerspiegelt.. 1 1 ; h 4 (12 + 12 ) = 1 ; h 2 2 2. 2 2. (B ) = 1 ; 2 sin2 h 2. Die Berechnung der Eigenwerte von Ah ist eine interessante Aufgabe. Siehe z.B. Cullum und Willoughby 1985].. 4.8 Nichtnegative Matrizen Fur das Modellbeispiel ist A = D ; L ; R und B = L + R, wobei B nichtnegativ und unzerlegbar ist. Es gibt eine schone Theorie der nichtnegativen Matrizen, die viele Anwendungen hat und leider hier nur kurz aufgegrien werden kann. (Siehe: Varga 1962], Berman und Plemmons 1979], Seneta 1973], Minc 1988], Windisch 1989].) Folgender schoner Satz von Perron und Frobenius wurde zwischen 1907 und 1912 bewiesen:. Satz 4.14 (Perron, Frobenius) Sei A eine n n unzerlegbare Matrix, die nichtnegativ ist, d.h. die nichtnegative Komponenten hat. Dann gilt:.