матрица, которая образует ортогональный базис с заданным вектором - PullRequest
Новая
       27

матрица, которая образует ортогональный базис с заданным вектором

2 голосов
/ 29 июня 2010

Вопрос линейной алгебры;

Учитывая заданный k-переменный нормированный вектор u (т. Е. U: || u || _2 = 1), как вы строите \ Gamma_u, любой произвольный k * (k-1) матрица единичных векторов такая, что (u, \ Gamma_u) образует ортогональный базис?

Я имею в виду: с вычислительной точки зрения: какой алгоритм вы используете для построения таких матриц?

Заранее спасибо,

Ответы [ 2 ]

4 голосов
/ 29 июня 2010

Наивным подходом будет применение ортогонализации по Граму Шмидту u_0 и 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 выбраны случайным образом.

2 голосов
/ 06 июля 2010

Вы можете использовать матрицы Домохозяина, чтобы сделать это.См., Например, http://en.wikipedia.org/wiki/Householder_reflection и http://en.wikipedia.org/wiki/QR_decomposition

. Можно найти матрицу домохозяина Q, так что Q*u = e_1 (где e_k - это вектор, равный 0, кроме 1 вk-е место) Тогда, если f_k = Q*e_k, f_k образуют ортогональный базис и f_1 = u.(Поскольку Q*Q = I, а Q ортогональна.)

Все эти разговоры о матрицах могут создать впечатление, что процедура будет дорогой, но это не так.Например, эта функция C, учитывая, что вектор длины 1 возвращает массив с требуемой базой в порядке столбцов, т.е. j-й компонент i-го вектора содержится в 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;
}
...