Помогите тупому ...

From

Alex Semenyaka (2:461/64)

To

sl@sl.spb.su

Date

2002-11-24T17:11:01Z

Area

RU.ALGORITHMS

Hello Stanislav!

[19 Nov 02 23:27], Stanislav Latishko (2:5030/949) -> All:

 SL>   Чего-то я отупел совсем :( Задачка элементарная, как решать -
 SL> не соображаю :( Имеется набор 60-мерных векторов A, B, C, ... и вектор

Мож, я чего не понимаю, но, кажется, тут примерно так:

1) Ортогонализуем набор A,B,C... (дял удобства лучше, наверное, сразу ортонормировать). Выкидываем линейно зависимые векторы (один фиг от них никакой пользы).
2) Проецируем X на каждый полученный вектор
3) Остаток (обзовем его V) у тебя ортогонален любому вектору в исходном наборе, так что минимизировать его, наверное, уже не получится. Скажем, если |V| = sqrt(V^2), то для ненулевого W, ортогонального V, имеем

|V+W| = sqrt(V^2 + 2VW + W^2) = sqrt(V^2 + W^2) > sqrt(V^2) = |V|

то есть "домешав" к V любую ненулевую комбинацию векторов своего небора A,B,C... ты добъешься только роста |V|.

Дальше из проекции, полученной в пункте 2), получаешь исходные вектора нужным (см. ниже) способом. Сложность - O(n^3), n - число векторов в исходной системе.

Если бы исходная система была хотя бы независимой - было бы все однозначно. Увы:

 SL> считая этой дельты) - от 1 до 3. Набор А,В,С,итд - "наиболее мерзкий"
 SL> - в том смысле, что в нем могут быть и "перепендикулярные" пары, а
 SL> могут быть и такие как C=k3*D+k4*E ... Т.е. единственность решения,
 SL> вообще говоря, совсем не очевидна... Ок, формализовать можно так:

- при неоднозначном наборе решение будет достоверно неединственным. При этом

 SL> ищем все решения, для которых |delta| меньше любого из слагаемых.

Тогда бери ортогонализацию по Левдину, а набор A, B, C... усортируй сначала по уменьшению. Тогда в 0 будут обращаться более короткие вектора. Составь набор исходных векторов, которые не обнулились при этой процедуре. Соответственно, сравнивай потом |V| с самым коротким вектором в этом наборе. IMHO, лучшего не добъешься: уменьшить |V| ты не можешь, векторы ты взял по построению самые длинные. Окажется "шум" больше, чем какой-то из векторов - сорри, таковы были исходные данные.


                                                     SY, Alex
--- IMHO в последней инстанции
 * Origin: Show must go on... and off. (2:461/64)