4.1 QR分解の定義

$\R^n$ のベクトル列 $a_1$ , $\cdots$ , $a_n$ が1次独立であるとき、 Gram-Schmidt の直交化法、 つまり $k=1$ , $2$ , $\cdots$ , $n$ の順に

$$b_k:=a_k-\sum_{j=1}^{k-1} (a_k,q_j),\quad q_k:=\frac{b_k}{\Vert b_k\Vert}$$

と計算することで正規直交基底 $q_1$ , $\cdots$ , $q_n$ が作れる。

$A=:(a_1,\cdots,a_n)$ , $Q:=(q_1,\cdots,q_n)$ , $R:=(r_{ij})$ , $r_{jk}:=(a_k,q_j)$ とおくと、

$$A=Q R, \mbox{$Q$ は実直交行列} , \mbox{$R$ は対角成分が正である上三角行列}$$ (1)

と書ける。

この形の分解は一意的である。実際

$$A=Q_1 R_1=Q_2 R_2$$

とすると、左から ${Q_2}^{-1}={Q_2}^T$ , 右から ${R_1}^{-1}$ (これは対角成分が正の上三角行列である) をかけて、

$$Q_2^T Q_1=R_2 {R_1}^{-1}.$$

左辺は実直交行列の積として実直交行列 (長さを変えない変換だから) で、 右辺は対角成分が正の上三角行列の積として対角成分が正の上三角行列である。 簡単な計算で対角成分が正の上三角実直交行列は単位行列に他ならないことが分 かる。

以上をまとめて次の命題を得る。

(1) の形の分解を QR 分解と呼ぶ¹。

GramSchmidt の直交化による QR 分解

   1 % GramSchmidt.m --- GramSchmidt()
   2 
   3 % 使用例
   4 % n=3; a=rand(n,n);
   5 % [q r]=GramSchmidt(a)
   6 % a-q*r
   7 
   8 % A=(a1 a2 ...,an) の列ベクトルから正規直交基底
   9 % q1, q2,..., qn を並べた Q を求める。
  10 function [q, r] = GramSchmidt(A)
  11   [n n] = size(A);
  12   %
  13   q=zeros(n,n);
  14   r=zeros(n,n);
  15   for k=1:n
  16     b=A(:,k); % 第k列 a_k
  17     for j=1:k-1
  18       r(j,k)=q(:,j)'*A(:,k); % r_{jk} = a_k と q_j の内積
  19       b=b-r(j,k)*q(:,j);     % b_k = a_k-(a_k,q_j)q_j
  20     end
  21     r(k,k)=norm(b);  % r_{kk} = ||b_k||
  22     q(:,k)=b/r(k,k); % q_k = b / r_{kk}
  23   end

GramSchmidt.m の実行結果

   1 >> n=4;a=rand(n,n)     
   2 a =
   3     0.9827    0.1146    0.5668    0.9616
   4     0.8066    0.6649    0.8230    0.0589
   5     0.7036    0.3654    0.6739    0.3603
   6     0.4850    0.1400    0.9994    0.5485
   7 >> [q r]=GramSchmidt(a)
   8 q =
   9     0.6415   -0.6491   -0.3412   -0.2251
  10     0.5266    0.7307   -0.1256   -0.4160
  11     0.4593    0.1624   -0.0214    0.8730
  12     0.3166   -0.1355    0.9313   -0.1185
  13 r =
  14     1.5319    0.6358    1.4229    0.9870
  15          0    0.4517    0.2074   -0.5971
  16          0         0    0.6196    0.1676
  17          0         0         0    0.0086
  18 >> a-q*r
  19 ans =
  20    1.0e-15 *
  21          0         0         0    0.1110
  22          0         0         0   -0.0139
  23          0         0         0         0
  24     0.0555         0         0    0.1110
  25 >>