Итеративный алгоритм оценки числа обусловленности

Описанный ниже алгоритм оценивает число обусловленности в 1-норме или ∞-норме. Основной сложностью при получении числа обусловленности является оценка нормы матрицы A ^-1, поскольку норму матрицы A легко получить. Эта программа использует итеративный алгоритм, позволяющий оценить снизу норму матрицы, заданной неявным способом - через умножение вектора на матрицу.

Умножение вектора x на матрицу A ^-1 эквивалентно решению системы линейных уравнений Ay = x. Если известно LU-разложение матрицы A, то для решения системы требуется только O(N ²) операций. При этом следует учитывать, что использовать обычный алгоритм решения системы линейных уравнений можно, но нежелательно - если матрица системы очень близка к вырожденной, в ходе решения может возникнуть переполнение, поэтому для решения используется специально разработанный для этого алгоритм, гарантированно не приводящий к переполнению, но несколько более медленный.

Недостатком итеративного алгоритма является то, что он позволяет получить не само число обусловленности, а лишь его оценку снизу, причем довольно-таки грубую. Обычно оценка меньше самого числа обусловленности лишь на 5-10 процентов, но бывают случаи, когда они отличаются очень значительно (в численных экспериментах оценка в среднем была меньше числа обусловленности на 8%, максимум - на 87%). Обычно когда оценка какой-то величины в десять раз меньше самой величины, эту оценку нельзя назвать точной. Тем не менее, даже такая оценка бывает достаточной.

Рассмотрим конкретный пример. Пусть число обусловленности матрицы A составило 10 ⁴. Это обозначает, что при точности представления вещественных чисел 10 ^-15 система линейных уравнений будет решена с точностью до 11-ого знака после запятой. Теперь предположим, что наша оценка числа обусловленности крайне неточна - отклоняется на 90% - и равна всего лишь 10 ³. Это обозначает, что мы будем ожидать решения системы уравнений с более высокой точностью - до 12-ого знака после запятой. Разница не такая уж и большая, поскольку обычно важен лишь порядок погрешности, а не её точная величина. В среднем же случае 10% разницы составляют менее одного десятичного знака и могут быть проигнорированы.

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