Gram-Schmidtの直交化

最初に

 直交化手法の 1 つであるGram-Schmidtの直交化は,ハウスホルダ変換に比べて高速であり, 処理が単純である.また,直交化を繰り返すことにより,誤差を最小限に抑えることが可能である.

定義式

  k 個の 1 次独立なベクトル a 1, a 2,・・・, a k から 1 つの正規直交系を作る.まず,

とし,

とおく.次に

とおく.以下,同様の操作を k 回繰り返すと,ベクトルu 1, u 2,・・・, u k はちょうど正規直交系をなす.

正規化しない場合

  単に直交系を作るだけなら,

というてもある.

プログラムリスト

上記の文字に対応していない場合があります.コメントを参照してください.


#define C 3			// column
#define R 3			// rank
#define gramschmidt_no 1	// 直交化を何回か繰り返して精度を上げる場合の回数
double factors[C * R]; //行列の定義

// factorsを直交化する.
BOOL CMatrix::GramSchmidt(double *NORM)
{
	register double len;
	register int i, j, k, cr, roll;
	cr=C*R;

	for(i = 0; i < R; i++){
		//ベクトルの長さを測定
		for(len = 0.0, j = i; j < cr; len += factors[j] * factors[j], j+=R);
		if(len == 0.0) return FALSE; //異常終了

		NORM[i] = len;						//2乗ノルムを計算
		for(len = 1.0/sqrt(len), j = i; j < cr; factors[j] *= len, j += R);	//単位ベクトル化

		for(roll = 0; roll < gramschmidt_no; roll++){		//直交化の回数
			//他のベクトルを直交化する
			for(k = 1; k < R - i; k++){
				//ベクトルiとkの内積を求める
				for(len = 0.0, j = i; j < cr; len += factors[j] * factors[j+k], j += R);
				//直交化
				for(j = i; j < cr; factors[j + k] -= len * factors[j], j += R);
			}
		}

		//内積の確認
		//for(k = 0;k < i; k++){
		//	double inner;
		//	for(inner = 0.0, j = 0; j < cr; inner += factors[j + i] * factors[j + k], j+=R);
		//	if(inner * inner > 1.0e-15) return FALSE; //許容誤差を超えるとエラー
		//}
	}

	return TRUE;
}

言語は一応C++です.(C言語も混ざっていますが).
バグがありましたら連絡してください.お願いします.

戻る
2002/4
by Hiroyuki Koga