Итеративный алгоритм оценки 1-нормы матрицы, заданной в неявной форме

Если матрица A задана в явной форме, т.е. набором своих элементов, то её 1-норма может быть вычислена по определению - как максимум суммы модулей элементов, расположенных в одном столбце. Однако, в ряде случаев требуется оценить норму матрицы, заданной в неявной форме, когда нам недоступна сама матрица, но доступна операция умножения матрицы на вектор.

Такая задача может возникнуть при нахождении нормы матрицы, заданной LU-разложением A = LU. Формирование матрицы A требует O(N ³) операций, в то время, как умножение на неё вектора - только O(N ²). Другой ситуацией, в которой может возникнуть такая задача, является оценка нормы матрицы, обратной к матрице A - для формирования матрицы A ^-1 в явной форме также требуется O(N ³) операций, но для умножения на неё (т.е. для решения системы линейных уравнений Ay = x) только O(N ²) операций, если нам известно LU-разложение матрицы A.

Принцип работы итерационного алгоритма

Общая идея итерационного алгоритма, приведенного здесь, проста - надо взять произвольный стартовый вектор x₀ , и осуществлять серию умножений этого вектора на матрицу A:

x₁ = Ax₀
x₂ = Ax₁
x₃ = Ax₂
...

Если Ax₀ ≠ 0, то приведенный алгоритм позволит после некоторого числа итераций оценить снизу норму матрицы A, как отношение норм x_i+1 и x_i . Хотя реализованный здесь алгоритм несколько сложнее, в его основе лежит та же простая идея.