Требуется найти максимальное собственное число квадратной симметрической матрицы N x N и соответствующий ему собственный вектор за кратчайшее время. Собственно вопрос стоит так - можно ли их(число и вектор) найти за линейное(O(N)) время? Или хотя бы аппроксимировать. Если да - то как, если нет - то почему?

у матрицы N^2 (ну, из-за симметричности можно считать N(N+1)/2, но для порядка это неважно) элементов, так что хотя бы для того, чтобы на каждый из них посмотреть, нужно выполнить O(N^2) операций

За линейное время можно найти только если у тебя трёхдиагональная матрица, к такой сразу можно применять QR или QL разложения. А чтобы свести симметричную к трёхдиагональной нужно O(n^2)

Или за линейное время можно аппроксимировать наибольшее/наименьшее собственное значение если есть приближение собственного вектора матрицы или наоборот, собственный вектор если есть приближение собственного значения. Для этого используются Inverse iteration или Rayleigh quotient iteration. 

Это сообщение отредактировал(а) W4FhLF - 18.7.2010, 11:53

Не только.

Но это не суть.

Ок. Понятно. Спасибо. Тема закрыта.