Embed Size (px)
DESCRIPTION
Gaußscher Algorithmus. Aufgabenstellung. Lösen Sie das lineare Gleichungssystem AX=B !. Gegeben: Dimension N ( int N; ) Koeffizienten A ij für i=0,...,N-1 und j=0,...,N-1 ( double [][] A = new double [N][N]; ) rechte Seite B i für i=0,...,N-1 - PowerPoint PPT Presentation
Citation preview
Gaußscher Algorithmus
Lösen Sie das lineare Gleichungssystem AX=B !
Aufgabenstellung
i
N
jjij BXA
1
0
1,...,0für Ni
Gegeben:Dimension N
( int N; )Koeffizienten Aij für i=0,...,N-1 und j=0,...,N-1
( double [][] A = new double [N][N]; )rechte Seite Bi für i=0,...,N-1
( double [] B = new double [N]; )
Gesucht:Existenz : Gibt es eine Lösung?Einzigkeit : Wenn es eine Lösung gibt, ist es die einzige Lösung?Lösung bzw. Lösungsmenge
Matrixschreibweise:
1,11,10,1
1,11,10,1
1,01,00,0
..
....
....
..
..
NNNN
N
N
AAA
AAA
AAA
A
1
1
0
.
.
NB
B
B
B
1
1
0
.
.
NX
X
X
X
Gaußscher Algorithmus Für die erste Gleichung gilt:
011,011,000,0 ... BXAXAXA NN
11,011,0000,0 ... NN XAXABXA
10,0
1,01
0,0
1,0
0,0
00 ...
NN XA
AX
A
A
A
BX
X[0]=B[0];for (int j=1; j<N; j++){
X[0] -= A[0][j]*X[j];}X[0] /= A[0][0];
10,0
1,01
0,0
1,0
0,0
00 ...
NN XA
AX
A
A
A
BX
0,0
11,011,000
...
A
XAXABX NN
0,0
1
1,00
0 A
XAB
X
N
jjj
X0 in den anderen (k=1,2,...,N-1) Gleichungen ersetzen:
kNNkkNN
k BXAXAXA
AX
A
A
A
BA
11,11,1
0,0
1,01
0,0
1,0
0,0
00, ......
0,0
00,1
0,0
1,00,1,1
0,0
1,00,1, ...
A
BABX
A
AAAX
A
AAA kkN
NkNkkk
Die Gleichungen hängen nur noch von X1, X2, ... , XN-1 ab. Die Dimension des Gleichungssystems ist also um 1 erniedrigt.Algorithmus kann „in place“ durchgeführt werden, d.h. die Felder A und B können wiederverwendet werden.
for (int k=1; k<N; k++){
for (int j=1; j<N; j++){
A[k][j] -= A[k][0]*A[0][j]/A[0][0];}
}for (int k=1; k<N; k++){
B[k] -= A[k][0]*B[0]/A[0][0];}
0,0
,00,,, A
AAAA jkjkjk für k=1,...,N-1 und j=1,...,N-1
0,0
00, A
BABB kkk für k=1,...,N-1
Koeffizienten und rechte Seiten des reduzierten Gleichungssystems
1
1
0
1
1
0
1,1,11,1
1,,1,
1,1,11,1
1,0,01,00,0
0
0
0
N
k
N
j
NNjNN
Nkjkk
Nj
Nj
B
B
B
B
X
X
X
X
AAA
AAA
AAA
AAAA
Nach der Anwendung eines Schrittes des Gaußschen Verfahrensentsteht folgendes Gleichungssystem (mit modifizierten Koeffizientenund rechten Seiten):
Dieses Gleichungssystem und das ursprüngliche sind lösungsäquivalent.Voraussetzung :
00,0 A
1
0
1
0
1,1,1,1
1,,,
1,,,
1,0,0,00,0
0
0
0
N
k
i
N
j
i
NNjNiN
Nkjkik
Nijiii
Nji
B
B
B
B
X
X
X
X
AAA
AAA
AAA
AAAA
Nach der Anwendung von i Schritten des Gauß-Jordan Verfahrensentsteht folgendes Gleichungssystem:
Dieses Gleichungssystem und das ursprüngliche sind lösungsäquivalent.Voraussetzung :
0,,0,0 1,11,10,0 iiAAA
Für die i-te Gleichung gilt:
iNNiiiiiii BXAXAXA 11,11,, ...
11,11,, ... NNiiiiiiii XAXABXA
1,
1,1
,
1,
,
...
N
ii
Nii
ii
ii
ii
ii X
A
AX
A
A
A
BX
X[i]=B[i];for (int j=i+1; j<N; j++){
X[i] -= A[i][j]*X[j];}X[i] /= A[i][i];
1,
1,1
,
1,
,
...
N
ii
Nii
ii
ii
ii
ii X
A
AX
A
A
A
BX
ii
NNiiiiii A
XAXABX
,
11,11, ...
ii
N
ijjjii
i A
XAB
X,
1
1,
Xi in den anderen (k=i+1,2,...,N-1) Gleichungen ersetzen:
kNNkiikNii
Nii
ii
ii
ii
iik BXAXAX
A
AX
A
A
A
BA
11,11,1
,
1,1
,
1,
,, ......
ii
iikkN
ii
NiikNki
ii
iiikik A
BABX
A
AAAX
A
AAA
,,1
,
1,,1,1
,
1,,1, ...
Die Gleichungen hängen nur noch von Xi+1, Xi+2, ... , XN-1 ab.
for (int k=i+1; k<N; k++){
for (int j=i+1; j<N; j++){
A[k][j] -= A[k][i]*A[i][j]/A[i][i];}
}for (int k=i+1; k<N; k++){
B[k] -= A[k][i]*B[i]/A[i][i];}
ii
jiikjkjk A
AAAA
,
,,,, für k=i+1,...,N-1 und j=i+1,...,N-1
ii
iikkk A
BABB
,, für k=i+1,...,N-1
Koeffizienten und rechte Seiten des reduzierten Gleichungssystems
1
0
1
0
1,1
1,,
1,,,
1,0,0,00,0
000
00
0
N
k
i
N
j
i
NN
Nkjk
Nijiii
Nji
B
B
B
B
X
X
X
X
A
AA
AAA
AAAA
Nach der Anwendung von N-1 Schritten des Gaußschen Verfahrensentsteht folgendes Gleichungssystem:
Dieses Gleichungssystem und das ursprüngliche sind lösungsäquivalent.Voraussetzung :
0,,0,0 2,21,10,0 NNAAA
Es bleibt die Gleichung :
1,1
11
111,1
NN
NN
NNNN
A
BX
BXA
X[N-1]=B[N-1]/A[N-1][N-1];
for (int i=0; i<N-1; i++){
for (int k=i+1; k<N; k++){
for (int j=i+1; j<N; j++){
A[k][j] -= A[k][i]*A[i][j]/A[i][i];}B[k] -= A[k][i]*B[i]/A[i][i];
}}X[N-1]=B[N-1]/A[N-1][N-1];for (int i=N-2; i>=0; i--){
X[i]=B[i];for (int j=i+1; j<N; j++){
X[i] -= A[i][j]*X[j];}X[i] /= A[i][i];
}
for (int i=0; i<N-1; i++){
for (int k=i+1; k<N; k++){
for (int j=i+1; j<N; j++){
A[k][j] -= A[k][i]*A[i][j]/A[i][i];}B[k] -= A[k][i]*B[i]/A[i][i];
}}for (int i=N-1; i>=0; i--){
X[i]=B[i];for (int j=i+1; j<N; j++){
X[i] -= A[i][j]*X[j];}X[i] /= A[i][i];
}
Problem:Ai,i muss immer verschieden von Null sein!Z.B.:
1
1
1
010
001
100
3
2
1
X
X
X
Das System ist eindeutig lösbar X1 = X2 = X3 = 1.Der Algorithmus funktioniert aber nicht, da A0,0 = 0.Man braucht nur die Gleichungen umzusortieren und derAlgorithmus funktioniert.
1
1
1
100
010
001
3
2
1
X
X
X
double maxa = Math.abs(A[i][i]);int imaxa = i;for (int k=i+1; k<N; k++){
if ( Math.abs(A[k][i])>maxa ){
maxa = Math.abs(A[k][i]); imaxa = k;
}}if (i != imaxa){
double [] Ah = A[i];A[i]=A[imaxa];A[imaxa]=Ah;double h = B[i];B[i]=B[imaxa];B[imaxa]=h;
}
