Сингулярное разложение матриц. Помогите разобраться

[logout2d]

Доброго времени суток!
Мне нужно сделать SVD (сингулярное) разложение квадратной матрицы A.
$A = USV^t$
Размерность матрицы в моем случае может быть от 3х3 до 500х500.
С разложением матриц я столкнулся недавно.
Собственно само разложение на бумажке я научился делать, делаю так:
$B = A^t A$,
где $A^t$ - транспонированная матрица А.
строю уравнение $det(B - \lambda E) = 0$,
откуда получаю степенное уравнение вида $a _0 \lambda ^n + a _1 \lambda ^{n-1} + .... = 0
где n - размерность матрицы
Если матрица 2х2 то уравнение квадратное, 3х3 кубическое, и тд.
Корни которого являются собственными числами матрицы В.

Далее я нахожу собственные вектора следующим образом:
строю уравнение $det(B- \lambda E)v = 0$,
где $\lambda$ - это ранее найденное собственное число, $v$ - искомый собственный вектор.
Точно так же найдя все собственные векторы, из которых я строю матрицу U.
Матрица S получается из корней собственных чисел расположенных по диагонали.
Матрицу V можно получить или аналогично U, приняв $B = A A^t$
или по формуле: $V^t = S^{-1} U^t A$

Теперь вопросы ))
1) Я покопался в книжках на предмет какие существуют методы сингулярного разложения,
и обнаружил велокое множество методов определения собственных чисел, собственных векторов и
самих сингулярных разложений. Вопрос к какому из методом относится описанный мной метод?

2) Описанный мной метод очень плохо перекладывается в код, так как надо решать степенные уравнения,
часто очень большой степени, это итерационные методы типа бисекции, метод хорд и тд.
Для нахождения собственных векторов, получаются такие системы уравнений, которые невозможно решить
стандартным методом, например Гаусса или Крамера.
Например:
$- v _1 - 4v _2 = 0$
$- v _1 - 4v _2 = 0$
Гаусс дает ответ {0,0}, в то время ясно что ответ {-4, 1}!

В виду отсутствия времени для изучения всех методов, прибегаю к вашему опыту.
Посоветуйте пожалуйста какой метод лучше всего использовать для SVD разложения в компьютерных программах.
Отражения Хаусхолдера, метод Якоби, и тд. И кратко по шагам суть действий метода, если не затруднит ))

3) Объясните пожалуйста в чем отличия всех этих методов, я имею ввиду по скорости, точности,
критичности к размерности матриц. По существу в общем в чем различия?

4) Я уже накопал много литературы, но все равно посоветуйте пожалуйста где почитать,
может ваша книжка окажется более полной и понятной.

[jetyb]

Характеристический полином на практике для вычисления собственных чисел не употребляется. Матрицу приводят к диагональному виду вращениями (метод Якоби); приводят к трехдиагональному виду (отражениями), после чего с трехдиагональной матрицей выполняют QR-итерации до приведения к диагональной (что быстрее Якоби, но есть некоторое отступление по точности нахождения собственных значений); есть также методы, использующие лишь умножение матрицы на вектор (одновременные итерации, метод Ланцоша), но не преобразующие саму матрицу (что особенно удобно для очень больших, но разреженных матриц). Вычисление сингулярных чисел производится теми же алгоритмами. Почитайте Богачева.

[logout2d]

Спасибо за ответ. Стало чуточку ясней ))
А что конкретно за книги/труды "Богачева"?
Название, Авторы?

[jetyb]

http://lib.walla.ru/?id=17816

[logout2d]

Большое спасибо, изучу представленные материалы

[logout2d]

Доброго времени суток!
Вопрос такой:
Допустим я научился приводить матрицы к трехдиагональной форме, методом Хаусхолдера.
На самом деле я беру пример отсюда:
http://math.fullerton.edu/mathews/n2003/householder/HouseholderMod/Links/HouseholderMod_lnk_2.html
Но я думаю что смогу разобраться в этом методе Хаусхолдера.
Вопрос в другом! После получения трех диагональной матрицы, дальше что делать для получения собственных значений и собственных векторов?
В чем раздница между QR разложением и QR итерациями?
Я понял что дальше надо применять к трех диагональной матрице QR итерации, но что это такое? В чем их суть?
Почитал в учебликах, неосилил.
Обьясните пожалуйста по шагам как к полученной трех диагональной матрице применять QR итерации, и когда получаются собственные значения и собственные векторы?
(Это все мне надо для получения SVD)

[GrandMaster]

logout2d в сообщении #264597 писал(а):

Далее я нахожу собственные вектора следующим образом:
строю уравнение $det(B- \lambda E)v = 0$,
где $\lambda$ - это ранее найденное собственное число, $v$ - искомый собственный вектор.
Точно так же найдя все собственные векторы, из которых я строю матрицу U.
Матрица S получается из корней собственных чисел расположенных по диагонали.
Матрицу V можно получить или аналогично U, приняв $B = A A^t$
или по формуле: $V^t = S^{-1} U^t A$

А как ты из собственных векторов строишь матрицу U???

-- Пн май 03, 2010 18:36:00 --

logout2d

Цитата:

Точно так же найдя все собственные векторы, из которых я строю матрицу U.
Матрица S получается из корней собственных чисел расположенных по диагонали.
Матрицу V можно получить или аналогично U, приняв $B = A A^t$
или по формуле: $V^t = S^{-1} U^t A$

Привет. Можешь объяснить как получаешь из собственных векторов сингулярные вектора(U)???.
Я использую алгоритм ALGLIB-a но собственные вектора получаются почти такими как должен получиться U, но в другой последовательности столбцов. Я думал что собственные вектора матрицы AtA это и есть сингулярный вектор U для матрицы А. Но вот такая хрень получается почему то((( Если я не прав, то что надо сделать с собственными векторами чтобы получить U?

[ewert]

logout2d в сообщении #264983 писал(а):

В чем раздница между QR разложением и QR итерациями?

Раздница принципиальна.

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

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

Грубо говоря, между этими процедурами нет решительно ничего общего.

[мат-ламер]

По поводу сингулярного разложения можно посмотреть Алберта "Регрессия, псевдоинверсия и рекуррентное оценивание". Как вычислять с.значения и векторы можно посмотреть Уилкинсона или Воеводина. Но лучше не париться со всем этим, а взять МатЛаб и воспользоваться готовыми алгоритмами.

[paha]

logout2d в сообщении #264597 писал(а):

Например:
$- v _1 - 4v _2 = 0$
$- v _1 - 4v _2 = 0$
Гаусс дает ответ {0,0}, в то время ясно что ответ {-4, 1}!

Гаусс дает ответ ровно $\{-4c;c\}$

[GrandMaster]

программу пишу на делфи, программа большая, но в ней надо использовать сингулярное разложение, так что маткад не катит. Так кто нибудь может обьяснить в чем различие между собственными векторами матрицы AT*A и сингулярными векторами матрицы А ???

[logout2d]

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

-- Пн май 24, 2010 16:17:23 --

paha в сообщении #315267 писал(а):

logout2d в сообщении #264597 писал(а):

Например:
$- v _1 - 4v _2 = 0$
$- v _1 - 4v _2 = 0$
Гаусс дает ответ {0,0}, в то время ясно что ответ {-4, 1}!

Гаусс дает ответ ровно $\{-4c;c\}$

(Не оскорбление) Я не знаю как у вас Гаусс дает {-4,1}, у меня он дает {0,0} и при этом он решает СЛАУ правильно! Значит метод работает!
Если он у вас дает собственные значения то зачем тогда все эти танцы с бубном для их поиска?
Я наверное что-то не понимаю разъясните пожалуйста как он у вас реализован.

[paha]

может быть у Вас другой Гаусс... однофамилец?

[Maslov]

(Оффтоп)

logout2d в сообщении #323455 писал(а):

Я просто решил заюзать готовую реализацию алгоритма, дабы в инете они есть, а к его пониманию решил вернуться позже.

В данном контексте больше подходит не "дабы", а "ибо" :) "Дабы" означает "для того чтобы".

[logout2d]

У меня "Решение СЛАУ методом Гаусса", а у вас какой Гаусс?
В инете полно сайтов предоставляющих "онлайн" решение по этому методу, вот например один:
[url]http://www.webmath.ru/web/prog13_2.php?koef[1][1]=-1&koef[1][2]=-4&koef[1][3]=0&koef[2][1]=-1&koef[2][2]=-4&koef[2][3]=0&chislo_ur=2&schet=1&chislo_ur=2[/url]

(Оффтоп)

Про "ибо" учту