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

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

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

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

Содержание     1 Описание алгоритма     2 Подпрограммы     3 Пример     4 Manual entries

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

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

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

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

1. вычисление 1-нормы (или inf-нормы) матрицы A итеративным алгоритмом за время O(N ²)
2. получение нижней границы нормы матрицы A ^-1 итеративным алгоритмом за время O(N ²)
3. получение оценки - произведения двух норм. Общая трудоемкость: 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, в то время как обусловленность матрицы полиномов Чебышева растет значительно медленнее.

Manual entries

C++		rcond subpackage
C#		rcond subpackage

This article is intended for personal use only.

Скачать ALGLIB