線性代數問題;與給定向量形成正交基的矩陣
給定的k變量賦範向量u(即U:|| ||Ü_2 = 1) 你如何構建\ Gamma_u,任意K *(K-1)的單位向量,使得矩陣 ( u,\ Gamma_u)構成一個 正交基?
我的意思是:從計算機立場的角度來看: 你用什麼算法來構造這樣的矩陣?
由於提前,
線性代數問題;與給定向量形成正交基的矩陣
給定的k變量賦範向量u(即U:|| ||Ü_2 = 1) 你如何構建\ Gamma_u,任意K *(K-1)的單位向量,使得矩陣 ( u,\ Gamma_u)構成一個 正交基?
我的意思是:從計算機立場的角度來看: 你用什麼算法來構造這樣的矩陣?
由於提前,
樸素方法將是應用U_0的革蘭氏施密特orthogonalisation,並且k-1隨機生成的向量。如果某些時候GS算法產生一個零向量,那麼你就有一個線性依賴關係,在這種情況下再次隨機地選擇向量。
然而,這種方法是不穩定的,矢量表示中的小數值誤差被放大。然而,存在這個算法的穩定變:
設a_1 = u, a_2,...a_k
被隨機地選擇向量
for i = 1 to k do
vi = ai
end for
for i = 1 to k do
rii = |vi|
qi = vi/rii
for j = i + 1 to k do
rij =<qi,vj>
vj =vj −rij*qi
end for
end for
所得矢量v1,...vk
將是您矩陣的列,與v1 = u
。如果某點vj
變爲零,請選擇一個新的矢量aj
並重新開始。請注意,如果向量a2,...,ak是隨機選擇的,則發生這種情況的概率可以忽略不計。
您可以使用Householder矩陣來做到這一點。參見 例如http://en.wikipedia.org/wiki/Householder_reflection 和http://en.wikipedia.org/wiki/QR_decomposition
人們可以找到一個的Householder矩陣Q
使得Q*u = e_1
(其中e_k
是,除了是全0從1中的第k個位置的向量) 然後,如果f_k = Q*e_k
,所述f_k
形成正交基和f_1 = u
。 (由於Q*Q = I
,Q是正交。)
所有這些談話矩陣可能會使它似乎是例行 將是昂貴的,但事實並非如此。例如,給定長度爲1的向量的該C函數 以列順序返回具有所需基礎 的數組,即,第i個向量的第j個分量保持在b [j + dim * i]
double* make_basis(int dim, const double* v)
{
double* B = calloc(dim*dim, sizeof * B);
double* h = calloc(dim, sizeof *h);
double f, s, d;
int i, j;
/* compute Householder vector and factor */
memcpy(h, v, dim*sizeof *h);
s = (v[0] > 0.0) ? 1.0 : -1.0;
h[0] += s;
f = s/(s+v[0]);
/* compute basis */
memcpy(B, v, dim * sizeof *v); /* first one is v */
/* others by applying Householder matrix */
for(i=1; i<dim; ++i)
{ d = f*h[i];
for(j=0; j<dim; ++j)
{ B[dim*i+j] = (i==j) - d*h[j];
}
}
free(h);
return B;
}
謝謝:我回去家試試吧,讓你知道, 最好。 – user189035 2010-06-29 11:41:11
而不是隨機基地開始,你可以。 1)檢查起始向量是規範庫中的一個倍數。 2)如果是,則選擇規範庫中的其他n-1個向量。 3)如果不是,檢查臨牀基地的任何n-1載體。 ///沒有選擇錯誤基地的概率。 – 2010-06-29 16:15:17
@belisarius,你仍然可能以線性依賴結束。考慮微不足道的情況u =(1,1,0),e1 =(1,0,0),e2 =(0,1,0),e3 =(0,0,1),那麼u不是任何一個線性倍數,但選擇e1和e2作爲另外兩個矢量將導致線性組合。一般而言,檢測線性組合並不便宜,所以用新的隨機向量重新啓動Gram-schmidt方法可能更便宜,因爲這是罕見事件 – 2010-06-29 17:05:06