与给定向量形成正交基的矩阵

Question

一道线性代数题；

给定一个 k 变量标准化向量 u （即 u : ||u||_2=1） 如何构造 \Gamma_u，任意 k*(k-1) 单位向量矩阵，使得 (u,\Gamma_u) 形成 正交基 ?

我的意思是：从计算的角度来看： 你用什么算法来构造这样的矩阵？

提前致谢，

Answer 1

最简单的方法是应用 u_0 和 k-1 随机生成向量的 Gram Schmidt 正交化。如果在某个时刻 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，发生这种情况的概率可以忽略不计。

Answer 2

您可以使用 Householder 矩阵来执行此操作。参见
示例 http://en.wikipedia.org/wiki/Householder_reflection
和 http://en.wikipedia.org/wiki/QR_decomposition

人们可以找到一个 Householder 矩阵Q 使得 Q*u = e_1
（其中 e_k 是除了第 k 个位置上的 1 之外全为 0 的向量）
那么如果f_k = Q*e_k，则f_k形成正交基并且f_1 = u。
（因为 Q*Q = I，并且 Q 是正交的。）

所有这些关于矩阵的讨论可能会让例程看起来像是
会很昂贵，但事实并非如此。例如这个 C 函数，
给定长度为 1 的向量，返回具有所需基数的数组
按列顺序，即第 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;
}