コンピュータ初級 (クラス2)

IT入門B2
ー連立一次方程式ー
授業内容
• 行列，ベクトルの表現法と行列の演算
• 連立一次方程式の解法
• ガウスの消去法
– 具体例
– 前進消去
– 後退代入
– ピボット選択
• 演習
行列，ベクトルの表現法
C言語で，行列やベクトルを表現するには？
• ベクトル：配列の利用
double x[N];
⇒ x[0]～x[N-1]のN個の要素を確保
• 行列：2次元配列の利用
double a[N][N];
⇒ a[0][0], a[0][1], … , a[0][N-1],
a[1][0], a[1][1], … , a[1][N-1],
……
a[N-1][0], a[N-1][1], … , a[N-1][N-1]
の(N×N)個の要素を確保
行列，ベクトルの表現
#include <stdio.h>
int main(void)
{
int i, j;
double x[3] = {-33.0, 9.0, 6.0};
double a[3][3] = {{2.0, 4.0, 6.0},
{3.0, 8.0, 7.0},
{5.0, 7.0, 21.0}};
printf("a = \n");
for (i=0; i<3; i++) {
for (j=0; j<3; j++) {
printf(" %.2f", a[i][j]);
}
printf("\n");
}
printf("x = \n");
for (i=0; i<3; i++) {
printf("%6.2f\n", x[i]);
}
return 0;
}
行列の演算
n×n行列 A と n次元ベクトル x の積を計算するプログラムを
作ってみよう．
計算結果を n次元ベクトル y に代入することにすると，
y  A x
これを具体的に記述すると，
 y0   a00
 y   a
 1    10
    
 y  a
 n 1   n 1, 0
a01
a11

an 1,1
 a0 n 1  x0 
 a1n 1  x1 



   
 an 1,n 1  xn 1 
ベクトル y の各成分は
yi  ai 0 x0  ai1x1   ai,n1xn1　(i  0, 1, , n 1)
と記述できる．
ベクトル y の計算
for(i = 0; i < n; i++){
yi の計算
}
各成分 yi の計算： yi  ai 0 x0  ai1x1   ai,n1xn1
各項 aij x j( j 0,1,…,n1)の総和を計算する．
成分 yi の計算
y[i] = 0.0;
for(j = 0; j < n; j++){
y[i] += a[i][j]*x[j];
}
y[i] += a[i][j]*x[j];
は
y[i] = y[i] + a[i][j]*x[j];
と同じ意味．
まとめると，行列 A とベクトル x の積 y を計算するプログラ
ムは以下のようにして実現できる：
ベクトル y の計算
for(i = 0; i < n; i++){
y[i] = 0.0;
for(j = 0; j < n; j++){
y[i] += a[i][j]*x[j];
}
}
演習
以下の行列 A とベクトル x の積（ A x ）を計算するプログラ
ムを作ってみよう：
2 4 6 
  33
A   3 8 7 , x   9 
 5 7 21
 6 




連立一次方程式の解法
• 直接解法
– ガウスの消去法
– LU分解法
…
• 反復解法
– ヤコビ法
– ガウス・ザイデル法
…
ガウスの消去法を用いて連立一次方程式の解を計算する
プログラムを作成しよう
ガウスの消去法
まず，具体例として3元連立方程式
2 x  4 y  6 z  6

3 x  8 y  7 z  15
5 x  7 y  21z  24

を解くことを考えよう．
[第1列消去]
2 x  4 y  6 z  6

3 x  8 y  7 z  15
5 x  7 y  21z  24

①
②
③
②，③からxを消去：
②①×3/2
2 x  4 y  6 z  6

0 x  2 y  2 z  6
5 x  7 y  21z  24

③①×5/2
2 x  4 y  6 z  6

0 x  2 y  2 z  6
0 x  3 y  6 z  9

①
②’
③
①
②’
③’
[第2列消去]
2 x  4 y  6 z  6

0 x  2 y  2 z  6
0 x  3 y  6 z  9

①
②’
③’
③’からyを消去：
③’②’×(-3/2)
2 x  4 y  6 z  6

0 x  2 y  2 z  6
0 x  0 y  3 z  18

①
②’
③”
各列の係数を順次消去していく：前進消去
2 x  4 y  6 z  6

0 x  2 y  2 z  6
0 x  0 y  3 z  18

①
②’
③”
③”から
z6
zの値を②’に代入し
y 9
y, zの値を①に代入し
x  33
求まった変数の値を順次代入しながら
解を計算する：後退代入
ガウスの消去法
前進消去と後退代入の組み合わせにより連立一次方程式の
解を求める手法
以下，連立一次方程式
a01  a0,n 1  x0   b0 
 a00


 

a11  a1,n 1  x1   b1 
 a10

 







 


 

a
 x   b 
a

a
n

1
,
0
n

1
,
1
n

1
,
n

1

 n 1   n 1 
の解を計算するプログラムを作成することを目標とする．
前進消去のプログラムでの実現
 a00 x0  a01 x1    a0,n1 xn1  b0
 a10 x0  a11 x1    a1,n1 xn1  b1



an1,0 x0  an1,1 x1    an1,n1 xn1  bk
に対し，第0列消去，第1列消去，… と繰り返し，
同じ解を持つ以下の方程式へと変形する：
a00 x0  a01 x1    a0,n 1 xn 1  b0

a11 x1    a1,n 1 xn 1  b1





an 2,n 2 xn 2  an  2,n 1 xn 1  bn 2


an 1,n 1 xn 1  bn 1
前進消去のプログラムでの実現
 a00 x0  a01 x1    a0,n1 xn1  b0
 a10 x0  a11 x1    a1,n1 xn1  b1



an1,0 x0  an1,1 x1    an1,n1 xn1  bk
に対し，第k列消去を，k  0, 1, 2, … , (n2) について
繰り返し行えばよい．
前進消去
for(k=0; k<=n-2; k++){
第k列消去
}
前進消去のプログラムでの実現
[第k列消去]
a00 x0  a01 x1  a02 x2    a0,n 1 xn 1  b0
a11 x1  a12 x2    a1,n 1 xn 1  b1

akk xk  ak ,k 1 xk 1    ak ,n 1 xn 1  bk
ak 1,k xk  ak 1,k 1 xk 1    ak 1,n 1 xn 1  bk 1

an 1,k xk  an 1,k 1 xk 1    an 1,n 1 xn 1  bn 1
akk xk  ak ,k 1 xk 1    ak ,n 1 xn 1  bk
ak 1,k 1 xk 1    ak 1,n 1 xn 1  bk 1

an 1,k 1 xk 1    an 1,n 1 xn 1  bn 1
[第k列消去]
akk xk  ak ,k 1 xk 1    ak ,n 1 xn 1  bk
ak 1,k xk  ak 1,k 1 xk 1    ak 1,n 1 xn 1  bk 1

an 1,k xk  an 1,k 1 xk 1    an 1,n 1 xn 1  bn 1
(k  1)式 
(n  1)式 
ak 1,k
akk

an 1,k
akk

 (k )式 



 (k )式 

(k )
(k  1)

(n  1)
aik
(i )式 
 (k )式
akk
(k  1  i  n 1)


aik 
aik 
aik
 ai ,k 1  ak ,k 1 
 xk 1     ai ,n 1  ak ,n 1 
 xn 1  bi  bk 
akk 
akk 
akk


[第k列消去]
(k  1  i  n 1)


aik 
aik 
aik
 ai ,k 1  ak ,k 1 
 xk 1     ai ,n 1  ak ,n 1 
 xn 1  bi  bk 
akk 
akk
kk 
a













ai ,k 1
ai ,n 1
bi
第k列消去
for (i=k+1; i<=n-1; i++) {
r = a[i][k]/a[k][k];
for (j=k+1; j<=n-1; j++) {
a[i][j] = a[i][j] – a[k][j]*r;
}
b[i] = b[i] – b[k]*r;
}
後退代入のプログラムでの実現
 a00






a01 
a11 

a0,n2
a1,n2

an  2 , n  2
a0,n 1  x0   b0 

a1,n1  x1   b1 

 

       
an2,n 1  xn2   bn2 
an1,n1  xn1   bn1 
an 1,n 1 xn 1  bn 1  xn 1 
第(n1)行:
第(n2)行: an  2,n  2 xn  2  an  2,n 1 xn 1  bn  2  xn  2 
第 i 行: aii xi 
n 1
 aij x j  bi  xi 
j i 1
bi 
bn 1
an 1,n 1
bn  2  an  2,n 1 xn 1
an  2 , n  2
n 1
a x
j i 1
aii
ij
j
(i  n  1, n  2,,1,0)
後退代入のプログラムでの実現
bi 
xi 
n 1
a x
j i 1
aii
ij
j
(i  n  1, n  2,,1,0)
for (i=n-1; i>=0; i--) {
考えてみよう
}
演習
ガウスの消去法を実現するプログラムを完成させて，下記の
連立一次方程式の解を計算してみよう：
Ax  b,
ただし
 4 12 8 4 
 4 
 1 7 18 9 
 5 
, b  
.
A
 2 9 20 20
  25
 3 11 15 14 
  18 





Download Report