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

Число обусловленности квадратной матрицы A определяется, как

k(A) = ||A||·||A^-1||

Число обусловленности имеет следующее значение: если машинная точность, с которой совершаются все операции с вещественными числами, равна ε, то при решении системы линейных уравнений Ax = b результат будет получен с относительной погрешностью порядка ε·k(A). Хотя число обусловленности матрицы зависит от выбора нормы, если матрица хорошо обусловлена, то её число обусловленности будет мало при любом выборе нормы, а если она плохо обусловлена, то её число обусловленности будет велико при любом выборе нормы. Таким образом, обычно норму выбирают исходя из соображений удобства. На практике наиболее широко используют 1-норму, 2-норму и ∞-норму, задающиеся формулами:

Содержание

    Описание алгоритма
    Подпрограммы
    Пример
    Manual entries

Описание алгоритма

Если матрица A задана непосредственно, алгоритм оценки числа обусловленности имеет вид:

вычисление 1-нормы (или inf-нормы) матрицы A прямым алгоритмом за время O(N²)
построение треугольной факторизации матрицы A за время O(N³)
получение нижней границы нормы матрицы A^-1, используя итеративный алгоритм с трудоемкостью O(N²)
получение оценки - произведения двух норм. Общая трудоемкость: O(N³)

Если матрица A задана своей треугольной факторизацией (LU-разложением или разложением Холецкого), то нам нет необходимости осуществлять шаг (2). Однако на шаге (1) мы уже не можем использовать прямой алгоритм - для него требуется знание матрицы A, а не её факторизации. Поэтому используется следующий алгоритм:

вычисление 1-нормы (или inf-нормы) матрицы A итеративным алгоритмом за время O(N²)
получение нижней границы нормы матрицы A^-1 итеративным алгоритмом за время O(N²)
получение оценки - произведения двух норм. Общая трудоемкость: O(N²)

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

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

Подпрограммы

Пакет ALGLIB содержит ряд подпрограмм, оценивающих число обусловленности матриц различных типов:

RMatrixRCond1
RMatrixRCondInf
CMatrixRCond1
CMatrixRCondInf
SPDMatrixRCond
HPDMatrixRCond
RMatrixLURCond1
RMatrixLURCondInf
CMatrixLURCond1
CMatrixLURCondInf
SPDMatrixCholeskyRCond
HPDMatrixCholeskyRCond

Имя подпрограммы определяется задачей, которую она решает, и имеет вид MatrixTypeMatrix[DecompositionType]RCond[NormType].

MatrixType определяет тип матрицы и может быть R (вещественная матрица общего вида), C (комплексная матрица общего вида), SPD (вещественная симметричная положительно определенная) или HPD (комплексная Эрмитова положительно определенная)
Если в подпрограмму передается сама матрица, то DecompositionType не указывается. Если же в подпрограмму передается треугольная факторизация матрицы, то к имени добавляется название факторизации (LU для матриц общего вида, Cholesky - для симметричных/Эрмитовых положительно определенных матриц)
Имя подпрограммы завершается указанием нормы, используемой для оценки числа обусловленности: 1 - для 1-нормы, Inf - для ∞-нормы. Для симметричных/Эрмитовых матриц эти нормы совпадают, поэтому имена подпрограмм, работающих с такими матрицами, не содержат указаний на тип нормы.

Пример

Сравним числа обусловленности двух матриц, имеющих отношение к полиномиальной интерполяции: матрицы Вандермонда и матрицы базисных полиномов Чебышева. В качестве набора узлов, порождаюшего матрицы, мы выберем равномерную сетку на отрезке (-1,+1). Сгенерировав матрицы для различных N и оценив числа обусловленности, мы получим:

                 CONDITION NUMBERS
OF VANDERMONDE AND CHEBYSHEV INTERPOLATION MATRICES

    VANDERMONDE   CHEBYSHEV
  N      1-norm      1-norm
  2         2,0         2,0
  3         3,7         3,0
  4        18,0         4,0
  5        50,0         5,0
  6       159,4         6,0
  7       455,0         7,0
  8      1460,5         8,0
  9      4250,0         9,0
 10     13625,2        10,0
 11     40145,3        11,0
 12    128360,3        12,2
 13    381433,0        22,6
 14   1216286,9       122,8

Можно видеть, что обусловленность матрицы Вандермонда очень сильно ухудшается с ростом N, в то время как обусловленность матрицы полиномов Чебышева растет значительно медленнее.