[ Pobierz całość w formacie PDF ]

"b1 "b0
= c2 + s c3, = p c3
"s "s
Daher die Jacobi-Matrix:
ëø öø
ëø öø
"b0 "b0
ìø ÷ø
ìø p c3 c2
÷ø
ìø ÷ø
"s "p ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
J(s, p) = = ìø ÷ø
ìø ÷ø
íøc + s c3 c3øø
íø øø
"b1 "b1
2
"s "p
Algorithmus 3.6.1 (von Bairstow).
48 Polynome
n
Gegeben: Koeffizientenvektor (a0, . . . , an) " n+1 von pn(x) = akxk,
k=0
Näherung ¾ an eine komplexe Nullstelle x" von pn, µ > 0.
Gesucht: Näherungen ¾k, ¾k an x", x" mit |¾k - x"|
Start: s0 := 2 Re ¾, p0 := - |¾|2,
Iteration: Für k = 0, 1, 2, . . . :
ëø öø
ìø pk c3 k c2 k÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
J(sk, pk) =
íø øø
c2 k + sk c3 k c3 k
c2 k = c2(sk, pk), c3 k = c3(sk, pk) . . .
µk b0(sk,pk)
Sei (µk, ´k) Lösung von J(sk, pk) =
´k b1(sk,pk)
s2
sk+1
sk+1 = sk + µk
k+1
und Ò! ¾k+1, ¾k+1 = ± i -pk+1 -
pk+1 = pk + ´k
2 4
Wenn n · |¾k+1 - ¾k|
49
KAPITEL 4
Direkte Lösung von linearen
Gleichungssystemen
A x = b A : m × n-Matrix b : ein m-Tupel
a11 x1 + · · · + a1n xn - b1 = 0
a21 x1 + · · · + a2n xn - b2 = 0
. .
. .
. .
am1 x1 + · · · + amn xn - bm = 0
Beispiel. y (x) + y(x) = f (x), x " [0, 1]. Randbedingungen: y(0) = y(1) = 0. Numerische Lösung mit
Diskretisierung von [1, 0].
1
xk = k · h, 0 d" k d" N, h =
N
0 h 2h 3h 4h 1
Abbildung 4.1: Einteilung
Ziel: Finde y1, . . . , yN-1 so, daß yk H" y(xk), k = 1, . . . , N - 1 y0 = 0, yN = 0
y(x + h) - 2y(x) + y(x - h)
y (x) H"
h2
y (xk) + y(xk) = f (xk), k = 1, . . . , N - 1. Näherungsweise
yk+1 - 2xk + yk-1
+ yk = f (xk), k = 1, . . . , N - 1
h2
ëø-2 + h2 1 0 · öø
ëø öø ëø öø
ìø ÷ø
ìø ÷ø y1 f (x1)
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
1 -2 + h2 1 · ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø · ·
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ÷ø
ìø 0 1 · ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
Ò! · · = h2 ìø ·
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø ÷ø
ìø ÷ø ìø ÷ø
ìø . ÷ø
ìø ÷ø ìø ÷ø
ìø . ÷ø
ìø · ÷ø ìø · ÷ø
ìø ÷ø
. ìø ÷ø ìø ÷ø
ìø · 1 ÷ø
íø øø íø øø
ìø ÷ø
íø øø
· . . . . . 1 -2 + h2 yN-1 f (xN-1)
50 Direkte Lösung von linearen Gleichungssystemen
4.1 Das Gaußsche Eliminationsverfahren
Definition 4.1.1. Eine Matrix der Gestalt
ëø öø
1 · ·
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø . ÷ø
ìø . ÷ø
ìø ÷ø
.
ìø · · ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø 1 · · ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
. . . . . . . . . 0 . . . . . . . . . 1 . . . . . . . . .
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
. . die Nullen sind in der i-ten und k-
.
ìø ÷ø
ìø . . . ÷ø
Pik =
ìø ÷ø
.
. .
ìø ÷ø
ìø ÷ø ten Zeile
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø . . . . . . . . . 1 . . . . . . . . . 0 . . . . . . . . . ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· · 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
.
ìø ÷ø
ìø . ÷ø
ìø . ÷ø
· ·
ìø ÷ø
ìø ÷ø
íø øø
· · 1
heißt Permutationsmatrix.
Bemerkung.
ëø x1 öø
ìø ÷ø
ìø ÷ø
.
ìø ÷ø
ìø . ÷ø
ìø ÷ø
ëø x1 öø .
ìø ÷ø
ìø ÷ø
ìø ÷ø
· xi-1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· xk ÷ø
ìø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø · ÷ø xi+1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· ìø ÷ø
ìø ÷ø
ìø ÷ø
.
ìø ÷ø
ìø ÷ø
ìø ÷ø
Pik ìø · ÷ø = . Vertauschung von i-ter und k-ter Komponente
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· .
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
xk-1
· ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø · ÷ø xi
ìø ÷ø
íø øø
ìø ÷ø
ìø
· xk+1 ÷ø
ìø ÷ø
ìø ÷ø
xn ìø ÷ø
ìø ÷ø
.
ìø ÷ø
íø . øø
.
xn
(x1, . . . , xn) Pik = (x1, . . . , xi-1, xk, xi+1, . . . , xk-1, xi, xk+1, . . . , xn)
Pik Pik = E (Einheitsmatrix)
Definition 4.1.2. Eine Matrix des Typs Li " n×n
ëø öø
1 0
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø 0 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· 0 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
Li =
ìø ÷ø
· li+1,i 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø . ÷ø
.
ìø ÷ø
ìø . . ÷ø
ìø . ÷ø
· .
ìø ÷ø
ìø ÷ø
íø øø
0 · · · ln i . . . . . 1
heißt elementare untere Dreiecksmatrix.
Bemerkung.
ëø öø
1 0
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø 0 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø · 0 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
L-1 =
ìø ÷ø
i · -li+1,i 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø . ÷ø
.
ìø ÷ø
ìø . . ÷ø
ìø . ÷ø
· .
ìø ÷ø
ìø ÷ø
íø øø
0 · · · -ln i . . . . . 1
Satz 4.1.1. Jede untere Dreiecksmatrix mit normierter Diagonale, aber
ëø öø
1 0
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
l21 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
L = ìø ÷ø
.
ìø . ÷ø
ìø . . ÷ø
ìø ÷ø
.
ìø . ÷ø
ìø ÷ø
íø øø
ln1 1
4.1 Das Gaußsche Eliminationsverfahren 51
läßt sich als Produkt von elementaren unteren Dreiecksmatrizen schreiben L = L1 L2 · · · Ln-1 mit
ëø öø
1 0
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø 0 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø · 0 1 ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
Li = i = 1, . . . , n - 1
ìø ÷ø
· li+1,i 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø . ÷ø
.
ìø ÷ø
ìø . . ÷ø
ìø . ÷ø
· .
ìø ÷ø
ìø ÷ø
íø øø
0 · · · ln i . . . . . 1
Beweis.
ëø öø
1 0
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
.
ìø ÷ø
ìø ÷ø
ìø . ÷ø
l21 .
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
ìø ÷ø
· 1
ìø ÷ø
ìø ÷ø
ìø ÷ø
L1 · · · Lk =
ìø ÷ø
ìø ÷ø [ Pobierz caÅ‚ość w formacie PDF ]