Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alex Semenyaka                       2:461/64       24 Nov 2002  18:11:01
 To : sl@sl.spb.su
 Subject : Помогите тупому ...
 -------------------------------------------------------------------------------- 
 
 
 [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. Hабор А,В,С,итд - "наиболее мерзкий"
  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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Помогите тупому ...   Stanislav Latishko    20 Nov 2002 00:27:34 
 Помогите тупому ...   Max Alekseyev   20 Nov 2002 22:25:32 
 Re: Помогите тупому ...   Stanislav Latishko    21 Nov 2002 15:31:29 
 Помогите тупому ...   Alex Semenyaka   24 Nov 2002 18:11:01 
 Помогите тупому ...   Nickita A Startcev   22 Nov 2002 17:42:56 
 Помогите тупому ...   Roman Kukushkin   22 Nov 2002 21:16:56 
Архивное /ru.algorithms/14433de10d29.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional