Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

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

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

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

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

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

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

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

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

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

Пример

Сравним числа обусловленности двух матриц, имеющих отношение к полиномиальной интерполяции: матрицы Вандермонда и матрицы базисных полиномов Чебышева. В качестве набора узлов, порождаюшего матрицы, мы выберем равномерную сетку на отрезке (-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

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.