Comments 28
Было бы здорово в начале статьи привести пару примеров, где собственно эти собственные числа и векторы применяются. В чем их практический смысл. Чтобы у человека в первый раз их встречающего сформировалась более плотная ассоциация, и ему было проще вспомнить про вашу статью. В остальном, спасибо за материал.
Чтобы избежать проблем с неуникальными максимальными значениями, можно сделать матрицу симметричной
Например, единичную?
Шансов, что в матрице со случайными элементами получается одинаковые вещественные собственные числа - очень мало
Ну вопрос не в этом. Я просто отметил, что симметричная матрица не обязательно имеет разные собственные числа.
А теперь серьёзный вопрос (я ищу ответ, и я его не знаю): если у меня есть положительноопределённая симметричная разреженная (большая, из разряда 100k x 100k) матрица, как мне найти её собственный вектор, соответствующий наименьшему ненулевому собственному числу, не прибегая к обратному степенному методу? Очень не хочется мне разложение Холецкого считать...
как мне найти её собственный вектор, соответствующий наименьшему ненулевому собственному числу, не прибегая к обратному степенному методу?
У Вас уже были какие-то подозрения на возможные решения этой задачи? Вопрос важный, присоединяюсь к нему, спасибо.
Могу пока что посоветовать посмотреть вот это https://en.wikipedia.org/wiki/LOBPCG
Cпасибо, посмотрю!
Можно я буду использовать комментарии для собственных заметок по теме? :)
Копи-паста просто для того, чтобы я потом искал по этим ключевым словам:
Since the Fiedler vector is associated with the smallest non-zero eigenvalue of a sparse matrix, calculating it with most common eigensolvers will be both inaccurate and inefficient. Using the default solver in R or Matlab will not yield usable results as these solvers focus on providing the eigenvectors associated with the largest eigenvalues. For best results you must use a sparse solver that can be specifically targeted to find a few eigenvectors at the low end of the spectrum. We precompute the Fiedler vectors using a smoothed aggregation preconditioner from pyAMG with scipy.sparse.linalg.lobpcg as in this example. This computation takes seconds on graphs with thousands of nodes.
Наверно вы уже видели, наткнулся на Википедии на статью со списком разложений: https://ru.m.wikipedia.org/wiki/Разложение_матрицы
Опечатка ''оно же вековое'
1) Не знаю, что и куда вы скопировали: на всякий случай я перепроверил и опять получил верный результат
2)Нужно из матрицы A "вычитать" все предшествующие собственные значения, то есть для 3-го надо отнять и первое и второе
3)Не нужно быть "профессиональным математиком", что б разобраться с этим методом, нужно только найти в себе концентрацию и усидчивость
4) Если вы внимательно всё прочли - там написано, что для нахождения всех собственных значений - это не лучший метод
Кстати, я же не изобретатель этого алгоритма - действительно думаете, что вот в стольких местах он упомянут - и не работает?
На самом деле вопрос в статье уже раскрыт, но давайте я ещё раз скажу:
1) если корень кратный, но ему соответсвует только 1 собственный вектор - алгоритм нормально сойдётся вот пример из статьи матрица 
с собственным уравнением (1-x)^2 = 0, т.е. собственное число имеет кратность два, но ему соответсвует только один собственный вектор
2) если корень имеет кратность больше одного и ему соответсвует хотя бы 2 собственных вектора - алгоритм не сойдётся - пример единичная матрица 
, также из статьи. Да пример очень простой, но не надо заблуждаться: из рассмотрения теории там не будет схождения и в более общем случае
если корень имеет кратность больше одного и ему соответствует хотя бы 2 собственных вектора - алгоритм не сойдётся
Но ведь тогда собственному значению соответствует целое собственное подпространство (минимум двухмерное), и выбор конкретных собственных векторов не уникальный — годится любой ортонормальный базис подпространства. Разве степенной алгоритм не будет (в теории) всегда сходиться к одному из векторов из этого подпространства, который годится как собственный вектор? Конечно, предельный вектор будет в принципе зависеть от исходного вектора. Кроме того, ограниченная точность машинных вычислений может испортить картину (из-за этого и проверка кратности может ломаться).
Степенной алгоритм сходится за счёт того, что при постоянном умножении на матрицу, компонента вектора, соответсвующая наибольшему собственному значению начинает доминировать над остальными, а если будет два таких вектора то они будут равноправно доминировать - в итоге алгоритм сойдется не к собственному вектору.
Да, если максимальному (по модулю) собственному значению соответствуют как минимум два собственных вектора, то проекции исходного вектора на них при повышении степени растягиваются одинаково быстро, и быстрее всех остальных. (Пока допустим, что количество собственных векторов соответствует кратности этого собственного значения; на комбинацию множественных собственных векторов с жордановыми клетками, вроде 
, можно попробовать обобщить потом.)
Тогда давайте рассмотрим подпространство, построенное на базисе тех собственных векторов для наибольшего собственного значения. Вроде бы несложно понять, что (в теории) доминирующе-одинаково растягивается вся проекция исходного вектора в это собственное подпространство (т.к. её компоненты в ортонормальном базисе растягиваются одинаково). Эта проекция тоже является собственным вектором (по определению), хотя она, конечно, зависит от исходного вектора.
Ну или можем вернуться конкретно к вашему простейшему примеру с единичной матрицей. На каждой итерации степенного алгоритма имеем исходный вектор, без изменений — идеальная, мгновенная сходимость. Кроме того, у единичной матрицы любой вектор собственный с собственным значением 1 по определению. В итоге алгоритм сходится к одному из собственных векторов с максимальным по модулю собственным значением, проблема только в том, что результат не уникальный и зависит от исходного вектора.
Вообще говоря, вы правы, мне следовало ваш первый комментарий повнимательнее почитать. Получается, что например для симметричных матриц алгоритм можно применять без всяких опасений...он найдёт 1 собственный вектор из подпространства собственных векторов, отвечающих максимальному значению..и само это собственное значение.
В поиске собственных значений (матриц)