| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск максимального собственного числа матрицы |
| Автор: tab 17.7.2010, 21:05 |
| Требуется найти максимальное собственное число квадратной симметрической матрицы N x N и соответствующий ему собственный вектор за кратчайшее время. Собственно вопрос стоит так - можно ли их(число и вектор) найти за линейное(O(N)) время? Или хотя бы аппроксимировать. Если да - то как, если нет - то почему? |
| Автор: maxim1000 18.7.2010, 10:25 |
| у матрицы N^2 (ну, из-за симметричности можно считать N(N+1)/2, но для порядка это неважно) элементов, так что хотя бы для того, чтобы на каждый из них посмотреть, нужно выполнить O(N^2) операций |
| Автор: W4FhLF 18.7.2010, 11:52 |
| За линейное время можно найти только если у тебя трёхдиагональная матрица, к такой сразу можно применять QR или QL разложения. А чтобы свести симметричную к трёхдиагональной нужно O(n^2) Или за линейное время можно аппроксимировать наибольшее/наименьшее собственное значение если есть приближение собственного вектора матрицы или наоборот, собственный вектор если есть приближение собственного значения. Для этого используются Inverse iteration или Rayleigh quotient iteration. |
| Автор: esperanto 18.7.2010, 20:08 | ||
Не только. Но это не суть. |
| Автор: tab 18.7.2010, 21:19 |
| Ок. Понятно. Спасибо. Тема закрыта. |