|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 26 Jul 2001 23:11:19
To : All
Subject : Re: Linear (In)Dependence
--------------------------------------------------------------------------------
"Sergey Kviat" <madkroz@i.am> wrote in message
news:9jpjmo$1g2c$1@ddt.demos.su...
> А теперь мне понравилась идея, предложенная Serge Kanilo, но, если я не
> ошибаюсь, есть в ней глюк:
Идея не моя. Если глюки есть - то мои :)
> SK>2) Отрогонализируем V к векторам U
> SK>for i=1,M-1
> SK> V=V-U_i*(V*U_i)/(U_i*U_i)
> SK>end
> 1. Ортогонализировать надо не V к векторам U, а вектора U к вектору V,
т.е.:
> for i=1,M-1
> U[i]=U[i]-V*(V*U_i)/(V*V)
> end
Это что в лоб, что по лбу. С точностью до обозначения. В одном случае
мы явно выбрасываем из одного вектора компоненты других, а потом переходим к
следующему. В другом случае, постепенно выбрасываем из
всех векторов компоненту выбранного, а потом выбираем следующий
и продолжаем.
Запиши это (первый и второй пункты) как два вложенных цикла и можешь
переставлять из местами сколько хочешь :).
for i=1,M
for j=1,M
if j!=i
U[i]=U[i]-U[j]*(U[j]*U[i])/(U[j]*U[j]) или
U[j]=U[j]-U[i]*(U[i]*U[j])/(U[i]*U[i])
end
end
end
Естественно, здесь совершенно нет оптимизации вычислений,
которая достаточно очевидна.
> 2. Далее выбираем новый вектор V из U_i, и повторяем пункт 1 (причём,
> разумеется, предыдущий вектор V уже можно не изменять).
> 3. Если какой-то вектор обратился в 0, то он линейно зависим.
> Hедостатки - использование плавающей точки даже, если координаты векторов
> целочисленные.
Это не недостаток, поскольку явно предназначенно для плавающей точки.
Для целочисленных векторов можно переписать как
U=U*(V*V) -V*(V*U),
но это годится только для малого количества векторов (M=6-10 если
повезет), т.к. числа будут расти со страшной скоростью, а искать общий
делитель или использовать длинную арифметику будет скорее всего
накладнее плавающей точки.
Можно также построить таблицы U[i]U[j] и
U[i]U[j]/sqrt((U[i]U[i])*(U[j]U[j]))
и начинать с наиболее близко-лежащих векторов и вычитать наиболее
короткие. Тоже небольшие дополнительные расходы, но сразу
отлавливаются сопряженные вектора и рост чисел более управляем.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
