Как приблизить число условий большой матрицы?

Как мне аппроксимировать число условий большой матрицы , если является комбинацией преобразований Фурье (неоднородных или равномерных), конечных разностей и диагональных матриц ?$G$$G$$F$$R$$S$

Матрицы очень большие и не хранятся в памяти и доступны только как функции.

В частности, у меня есть следующая матрица:

$G_\mu=S^HF^HFS+\mu R^HR$

Я хочу исследовать связь между и условным числом .$\mu$$k(G_\mu)$

Я полагаю, нужен какой-то итерационный подход? Оптимально было бы наличие некоторого кода MATLAB.

MATLAB имеет несколько «точную» функции для этого, condи rcond, причем последний возвращает обратное число обусловленности. Приближенная функция Matlab condestболее подробно описана ниже.

Часто оценки числа условий генерируются как побочные продукты решения линейной системы для матрицы, так что вы могли бы иметь возможность сопоставить оценки числа условий с другой работой, которую вам необходимо выполнить в любом случае. Смотрите здесь для краткого описания того, как вычисляются оценки. Также в документации Sandia Labs AztecOO отмечается (см. Раздел 3.1), что дополнительные оценки числа условий можно получить из итерационных решателей (используя сгенерированную трехдиагональную матрицу Ланцоша с градиентами сопряжения или сгенерированную матрицу Гессенбурга с перезагруженным GMRES).

Поскольку ваши матрицы «очень большие» и «доступны только как функции», логическим подходом будет метод, который использует метод сопряженного градиента или вариант.

В недавней статье arXiv.org нестационарные экстремальные аппроксимации собственных значений в итерационных решениях линейных систем и оценок относительной ошибки предлагается такой подход и имеется несколько ссылок на более раннюю литературу.

Теперь, когда я смотрю, у этого форума есть несколько тесно связанных предыдущих Вопросов (не все с Ответами, но проверьте Комментарии):

Оценить экстремальные собственные значения с помощью компьютерной графики

Оценка номеров условий для очень больших матриц

Самый быстрый алгоритм для вычисления числа условий большой матрицы в Matlab / Octave

Поскольку доступность кода MATLAB была частью Вопроса, вот некоторая информация о condestвстроенной функции, которая оценивает число 1-нормального условия . Идея Хагера (1984) с записью и расширениями 2010 года здесь явно вычислить (найти максимальную 1-норму столбца) и оценить градиентным методом. См. Также СОСТОЯНИЕ Джона Буркардта , библиотека MATLAB (доступны другие языки) «для вычисления или оценки числа условий матрицы».$\|A\|_1 \|A^{-1}\|_1$$\|A\|_1$$\|A^{-1}\|_1$

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

Несмотря на то, что мы нацелены на не SPD (и даже не квадратные) случаи, эта недавняя статья arXiv.org, Надежная итеративная оценка числа условий , дает хороший обзор наименьшей проблемы оценки собственных значений и многообещающей линии атаки подпространством Крылова. метод (LSQR), который составляет сопряженные градиенты в случае SPD.