[reginil_y 0]

 

Привет уважаемые форумчане,

 

У меня есть такой вопрос: Есть некая комплексная матрица V размером (Nx3). Я создаю Эрмитовую матрицу G=V^H*V (размер NxN). H обозначает conjugate transpose. Мне нужно выразить собственный вектор матрицы G соответствующий максимальному собственному значению. Может кто знает книгу где выведено уже готовое выражение для соответствующей задачи или может это есть в какой нибудь статье на IEE.

 

с уважением

[Xenia 45]

У меня есть такой вопрос: Есть некая комплексная матрица V размером (Nx3). Я создаю Эрмитовую матрицу G=V^H*V (размер NxN). H обозначает conjugate transpose. Мне нужно выразить собственный вектор матрицы G соответствующий максимальному собственному значению. Может кто знает книгу где выведено уже готовое выражение для соответствующей задачи или может это есть в какой нибудь статье на IEEE.

А что вам мешает решать задачу в лоб? Вычислите G, а потом найдите у нее главный собственный вектор. Благо алгоримы для нахождения собственных векторов и значений эрмитовых матриц можно найти в любом справочнике по матричным вычислениям.

 

Хотя, если бы я решала эту задачу, то скорее всего получила другую эрмитову матрицу, F=V*V^H размером 3x3, нашла у нее главный собственный вектор, а потом умножила его на исходную матрицу V, получив в результате то, что вам надо :). Этот путь вычислительно эффективен, благодаря малой размерности F. А из короткого собственного вектора всегда можно получить длинный, умножением на саму матрицу.

[reginil_y 0]

Хотя, если бы я решала эту задачу, то скорее всего получила другую эрмитову матрицу, F=V*V^H размером 3x3, нашла у нее главный собственный вектор, а потом умножила его на исходную матрицу V, получив в результате то, что вам надо :). Этот путь вычислительно эффективен, благодаря малой размерности F. А из короткого собственного вектора всегда можно получить длинный, умножением на саму матрицу.

 

100 балов!!!

Дело в том, что в лоб решать было бы не то что бы сложно... просто невозможно. Так как все в параметрах и для каждого собственного значения пришлось бы искать детерминанту матрицы размером NxN. Да еще и в добавок нужно подставить этот вектор в выражение, которое совсем не маленькое а потом еще и делать производную по параметрам которые будут присутствовать в данном векторе .А вот сделать как вы сказали это намного элегантней. Большое спасибо!

 

P.S. Для того чтоб воспользоваться вашим решением необходимо знать что собственные значения отличные от нуля матриц V*V^(H) и V^(H)*V одинаковы. Это к счастью я знал. А вот как потом удлиннить вектор, догадаться не смог

Изменено 3 апреля, 2012 пользователем reginil_y

[Xenia 45]

Дело в том, что в лоб решать было бы не то что бы сложно... просто невозможно. Так как все в параметрах и для каждого собственного значения пришлось бы искать детерминанту матрицы размером NxN.

По нынешним временам никто через детеминанты эту задачу не решает - QL метод рулит.

 

А вот как потом удлиннить вектор, догадаться не смог.

Уточнение. Умножением короткого СВ на исходную матрицу получается не совсем длинный СВ, а его произведение на соответствующее ему собственное значение. Формально это не мешает ему называться собственным вектором, но все-таки желательно нормировать его на единицу, тем самым, избавляясь от сомножителя.

[reginil_y 0]

По нынешним временам никто через детеминанты эту задачу не решает - QL метод рулит.

 

 

Уточнение. Умножением короткого СВ на исходную матрицу получается не совсем длинный СВ, а его произведение на соответствующее ему собственное значение. Формально это не мешает ему называться собственным вектором, но все-таки желательно нормировать его на единицу, тем самым, избавляясь от сомножителя.

 

Может я действительно что то пропустил,но...

Допустим F=V^H*V - матрица 3на3

Тогда должно выполнаться: (V^H*V)*h=lam*h, где h СВ, а lam СЗ матрицы F соответственно

Обозначим y=V*h

отсюда V^H*y=lam*h

Умножим обе части на V: (V*V^H)*y=lam*(V*h)

Отсюда получаем: G*y=lam*y.

Тоесть y и есть искомый СВ. Хотя интуиция подсказывает что нормировать было бы не лишним.

 

А что такое QL? Потому что даже для матрицы 3на3 мне расчеты показываются слишком длинными.

 

 

[Xenia 45]

А что такое QL? Потому что даже для матрицы 3на3 мне расчеты показываются слишком длинными.

А они и не могут быть короткими :).

 

QL - это итерационный метод, основанный на разложении тридиагональной матрицы на произведение ортогональной Q и нижней трегольной L. На самом же деле эти сомножители не вычисляются, а имеет место хитрая последовательность однообразных процедур, когда с тридиагональной матрицы "сдирают кожу" :), при этом ее поддиагональ с верхнего края "обтёсывается" после каждого прохода преобразований по цепочке сверху вниз. Итерации сходятся замечательно - в среднем требуется не более 2-х итераций на каждое собственное значение. Но сам процесс вычислений муторный и малопонятный :).

 

Да, еще позабыла сказать, что первой стадией является приведение матрицы к тридиагональному виду, а дальше алгоритм работает лишь с парой диагоналей - главной диагональю и ее соседкой (поддиагональю). Соседка с другой стороны в вычислениях не участвует, т.к. триагональная матрица, получаемая из эрмитовой всегда симметрична, а QL-алгоритм тем и хорош, что своими итерациями эту симметричность не нарушает.

 

Например, посмотрите здесь: http://num-anal.srcc.msu.ru/lib_na/cat/ae/aeh1c.htm

[reginil_y 0]

Например, посмотрите здесь: http://num-anal.srcc.msu.ru/lib_na/cat/ae/aeh1c.htm

 

Спасибо за ресурс,

Дело все в том что у меня есть два варианта. Или прийти к конкретному математическому выражению или же использовать программу и прийти к численному результату. Для численного я обычно использую Матлаб.

[Xenia 45]

Спасибо за ресурс,

Дело все в том что у меня есть два варианта. Или прийти к конкретному математическому выражению или же использовать программу и прийти к численному результату. Для численного я обычно использую Матлаб.

Не думаю, что это такой уж хороший ресурс. Там хороши только описания, но не сами тексты программ. Лучше всего, на мой взгляд, старый добрый Eispack (это проект такой "древний" матричных функций на FORTRANе), а еще лучше алгоритмы этих функций на ALGOLе из Справочника Уилкинсона-Райнша, которые послужили прототипом для проекта Eispack. Первоисточник мне нравится больше, поскольку код на ALGOLе очень легко переписывается на C, чего нельзя сказать про FORTRAN. А автоматический перевод с FORTRANа на C при помощи ретранслятора f2c вызывает у меня слёзы :), т.к. напрочь убивает понимание алгоритма.

 

Вас, я полагаю, вся эта кухня интересует много меньше, чем решение вашей конкретной задачи, поэтому я вам капать на мозги больше не стану :), а ограничусь исключительно практическим советом. Суть его с том, что комплексная эрмитова матрица после приведения ее к тридиагональной форме становиться действительной! Всегда! Т.е. и главная диагональ тридиагональной матрицы, и две ее симметричные соседки (нижняя и верхняя поддиагонали) не содержат мнимых членов. Доказательств этого удивительного явления не знаю, но знаю алгоритм (htridi), который это делает.

На FORTRANе тут:

http://www.netlib.org/eispack/htridi.f

Дурацкий автоматический перевод на C тут:

http://www.koders.com/cpp/fidD3E4B58F2614D...6B45.aspx?s=des

Этот алгоритм запихивает обе найденные диагонали в вектора d и e, а на месте исходной матрицы строит базис матрицы поворота (она понадобится для получения собственных векторов).

А дальше с комплексными числами можно распрощаться и вычислять собственные значения и вектора тридиагональной матрицы с учетом состовшегося поворота). Т.е. далее задача сводится к действительному случаю:

http://www.netlib.org/eispack/tql2.f

 

Кстати, на каком языке пишете вы? Ведь если вы используете MatLab, то тот бы решил вашу задачу в лоб одной командой. Я бы могла с вами поделиться и своим кодом для решения таких задач, только он вряд ли вам подойдет из-за того, что я храню комплексные матрицы в особом виде - не в виде массива комплексных структур, а в виде двух отдельных массивов для реальных и мнимых ее составляющих. А кроме того активно пользуюсь ассеблерными функциями для ускорений вычислений (главным образом, для вычисления скалярного произведения пары векторов и гивенсовских вращений матрицы), из-за чего код становится непереносимым и трудно понимаемым для тех, кто его не писал. :)

[reginil_y 0]

Кстати, на каком языке пишете вы? Ведь если вы используете MatLab, то тот бы решил вашу задачу в лоб одной командой. Я бы могла с вами поделиться и своим кодом для решения таких задач, только он вряд ли вам подойдет из-за того, что я храню комплексные матрицы в особом виде - не в виде массива комплексных структур, а в виде двух отдельных массивов для реальных и мнимых ее составляющих. А кроме того активно пользуюсь ассеблерными функциями для ускорений вычислений (главным образом, для вычисления скалярного произведения пары векторов и гивенсовских вращений матрицы), из-за чего код становится непереносимым и трудно понимаемым для тех, кто его не писал. :)

 

В процессе писания работы по навигационным алгоритмам я столкнулся со следующей задачей: Нужно было привести к максимуму следующее выражение (h^H)Qh по h. то есть вопрос состоял в том, какой h нужно взять чтоб привести это выражение к максимуму. Оказывается что из всех существующих на свете векторов, подходящий h, это СВ матрицы Q который соответствует максимальному СЗ Q. Но этого оказалось мало. Передо мной была поставлена следующая задача ( к стати, Q это та самая эрмитовая матрица о которой я писал в самом начале. Более того, в нее вмонтированы коорденаты приемника которые мне нужно будет в последствии оценить, по этому не совсем хорошо решать такую задачу численно. Нужно иметь четкое мат. выражение). Выразить h через СВ Q, и подставить его обратно и таким образом получить новое выражение которое будет зависеть только от коорденат приемника. Это все делается для того чтоб построить сокращенный CR. Как известно размер матрица Фишера равен количеству неизвестных параметров, по этому после процедуры подстановки у меня вместо N+6 параметров будет всего 2. Но за это прийдется платить тем что мат выражение будет громоздкое. Статью по сокращенному CR я прикрепляю к этому сообщению. Там должно быть и выражение подходящее для моей задачи но я его пока немогу увидеть. А в следствии того что с принцыпом я разобрался то пытаюсь вывести собственное. Для начала попытаюсь решить чесленно (ведь поиск приемника идет на заранее определенной площади) а потом уже если руководитель потребует то буду решать аналитически. Как видите для меня было главное не код а мудрое решение искать CB матрицы 3на3 вместо NнаN. Потому и написал "100 баллов!!!" :) А все остальное дело техники :)

 

P.S Очень полезно было услышать о тридиагональной форме эрмитовой матрицы. На сколько я помню этого нет даже в wiki

00312159.pdf

Изменено 4 апреля, 2012 пользователем reginil_y

[iiv 29]

Есть некая комплексная матрица V размером (Nx3). Я создаю Эрмитовую матрицу G=V^H*V (размер NxN). H обозначает conjugate transpose. Мне нужно выразить собственный вектор матрицы G соответствующий максимальному собственному значению.

 

собственные векторы этой матрицы будут равны сингулярным векторам Вашей исходной матрицы V. Один вызов lapack-acml с названием dgesvd полностью решит Вашу задачу. Лапак можно вытащить бесплатно и официально в исходниках, и не только для фортрана, но и С, хотя если точность и скорость работы Вас не волнует, а компилить-ставить лапак - лениво, будет проще поступить, как Вам уже Xenia ответила через 3х3 матрицу.

[reginil_y 0]

собственные векторы этой матрицы будут равны сингулярным векторам Вашей исходной матрицы V. Один вызов lapack-acml с названием dgesvd полностью решит Вашу задачу. Лапак можно вытащить бесплатно и официально в исходниках, и не только для фортрана, но и С, хотя если точность и скорость работы Вас не волнует, а компилить-ставить лапак - лениво, будет проще поступить, как Вам уже Xenia ответила через 3х3 матрицу.

 

Спасибо за отклик но мне наверно нужно будет решить эту задачу аналитически. Я кое что тут набросал на power point ... Есть ли возможность определить кокой из собственных значений будет максимальным?

a1.ppt

[andrewn 0]

мне наверно нужно будет решить эту задачу аналитически

На этом скорбном пути вас ожидает некоторое нетривиальное количество печальных открытий. Начнём с того, что нет аналитической формулы отыскания корней уравнения степени > 3. Хотя у вас матрица Q ранга 3 и даже если вы её строите шестимерной, её характеристическое (вековое) уравнение сводится к кубическому - трёхкратный корень, равный нулю. Кубическое уравнение можно решить аналитически, используя формулы Кардано. Выглядят они вполне научно, но несколько громоздко и заранее не скажешь, исходя из элементов V, который из трёх ненулевых корней самый большой и как (хотя понятно как = det(Q - lambda*I)) он зависит от элементов V.

 

Дальше неприятностей ещё больше. Для собственных векторов вообще неизвестна конечная аналитическая процедура их построения. Её просто нет. Следовательно, крутим ортогональными матрицами до посинения, т.е. до диагонализации исходной матрицы Q, или её трёхдиагонального двойника, полученного серией отражений Хаусхолдера. Но бесконечный процесс никогда не кончится и уж точно никакой аналитичности решению не придаст.

 

Мораль: не пытайтесь доказать что выражению (V*h)^H*(V*h), оно же h^H*Q*h доставляет максимум собственный вектор, соответствующий максимальному собственному значению Q. Всё украдено, т.е. доказано до нас лет за двести и ныне это известно каждому первокурснику.

 

Максимальное собственное число Q вам знать не нужно, оно в вычислениях не участвует (хотя полезно посмотреть, как себя ведёт спектр - что бы представлять, как хорошо разделены максимальное и следующее за ним собственные числа, и оценить шансы прямой итерации), поэтому проще всего сосредоточиться на вычислении собственного вектора, соответствующий максимальному по модулю собственному значению. Естественно, численно. Используя простой метод прямой итерации:

 

Выберем h случайным образом. Сосчитаем h' = Q*h и примем новый h = h'/||h'||, т.е. отнормируем итерацию на евклидову норму. Продолжаем до тех пор, пока соседние итерации не совпадут с заранее заданной вычислительной точностью. Это и есть искомый собственный вектор. Понятно, что чем дальше лямбда_1 от лямбда_2, тем лучше сходятся итерации, хотя, конечно, даже о квадратичной сходимости речи нет. Понятно, что это тоже бесконечный процесс, но так как он обрезается по достижении некоторого количества верных цифр, то его можно сосчитать.

 

 

 

[reginil_y 0]

AndrewN , Спасибо (запоздалое) за отклик. Пожалуй вы правы по поводу того что в параметрах невозможно сказать какое С.З. будет максимальным, по этому скорее всего прийдется вычислять численно.

А вот по поводу серьезных познаний первокурсников я очень сильно сомневаюсь. Первокурсник первокурснику рознь... и эта реальность не зависит от того когда была доказана та или инная теорема или утверждение

 

С уважением

 

Изменено 29 апреля, 2012 пользователем reginil_y