Наименьшее собственное значение без обратного

11

Предположим, что ARn×n - симметричная положительно определенная матрица. A достаточно большой, чтобы решить дорого Ax=b.

Существует ли итерационный алгоритм для наименьшего собственного значения A , который не включает инвертирование A в каждой итерации?

То есть мне нужно было бы использовать итерационный алгоритм, такой как сопряженные градиенты, для решения Ax=b , поэтому многократное применение A1 кажется дорогим «внутренним циклом». Мне нужен только один собственный вектор.

Благодаря!

Джастин Соломон
источник
1
Вы пробовали использовать разложение Холецкого? Вы должны были бы разложить A на LLT где L - треугольная матрица. Как только у вас есть факторизация (вы делаете это только один раз), вы можете использовать ее на каждой итерации, чтобы очень быстро решить систему путем обратной и прямой подстановки.
Хуан М. Белло-Ривас
Является ли A разреженной матрицей?
Толга Бирдал
есть некоторая блочная структура, но я бы предпочел не связываться с ней, если мне не нужно - поэтому я искал «безматричные методы». Я думаю, что алгоритм "LOBPCG" обещает! @Juan, факторизация Холецкого все еще довольно дорога. A
Джастин Соломон
Если вы используете matlab или octave, используйте eigs-routine. Это итеративный метод. Есть варианты, чтобы указать, какое собственное значение вы хотите, например, наименьшее действительное .
sebastian_g
Я понимаю и действительно использую Eigs в Matlab. Но если указать параметры , такие как «см» в eigs, то он требует инверсии вместо А . Посмотрите таблицу в документации: mathworks.com/help/matlab/ref/eigs.htmlAA
Джастин Соломон

Ответы:

13
  1. Вычислите собственное значение наибольшей величины из A (скажем, с ).λmaxAeigs('lm')

  2. Затем вычислить величину наибольшей (отрицательный) собственное значение λ т а х из М = А - λ м х I (опять же , с помощью стандартного вызова ).λ^maxM=AλmaxIeigs('lm')

  3. Заметим , что λ т х + λ макс = λ м I п ( А ) . Причина, по которой это верно, объясняется здесь .λ^max+λmax=λmin(A)

  4. Найдите свой собственный вектор , решив .( A - λ m i n I ) v = 0v(AλminI)v=0

GoHokies
источник