2010-06-29 73 views
2

線性代數問題;與給定向量形成正交基的矩陣

給定的k變量賦範向量u(即U:|| ||Ü_2 = 1) 你如何構建\ Gamma_u,任意K *(K-1)的單位向量,使得矩陣 ( u,\ Gamma_u)構成一個 正交基?

我的意思是:從計算機立場的角度來看: 你用什麼算法來構造這樣的矩陣?

由於提前,

回答

4

樸素方法將是應用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是隨機選擇的,則發生這種情況的概率可以忽略不計。

+0

謝謝:我回去家試試吧,讓你知道, 最好。 – user189035 2010-06-29 11:41:11

+0

而不是隨機基地開始,你可以。 1)檢查起始向量是規範庫中的一個倍數。 2)如果是,則選擇規範庫中的其他n-1個向量。 3)如果不是,檢查臨牀基地的任何n-1載體。 ///沒有選擇錯誤基地的概率。 – 2010-06-29 16:15:17

+0

@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

2

您可以使用Householder矩陣來做到這一點。參見 例如http://en.wikipedia.org/wiki/Householder_reflectionhttp://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; 
}