Число обусловленности матрицы как найти
Перейти к содержимому

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

  • автор:

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

1 норма матрицы представляет из себя максимальное из чисел, полученных при сложении всех элементов каждого столбца, взятых по модулю. Не путайте со сложением матриц!

Р ассмотрим на примере: пусть дана матрица размера 3х2. В первом столбце стоят элементы: 8, 3, 8. Все элементы положительные. Найдем их сумму: 8+3+8=19. В втором столбце стоят элементы: 8, -2, -8. Два элемента — отрицательные, поэтому при сложении этих чисел, необходимо подставлять модуль этих чисел (т.е. без знаков «минус»). Найдем их сумму: 8+2+8=18. Максимальное из этих двух чисел — это 19. Значит первая норма матрицы равна 19.

2 норма матрицы представляет из себя квадратный корень из суммы квадратов всех элементов матрицы. А это значит мы возводим в квадрат все элементы матрицы, затем складываем полученные значения и из результата извлекаем квадратный корень.

В нашем случае, 2 норма матрицы получилась равна квадратному корню из 269. На схеме, я приближенно извлекла квадратный корень из 269 и в результате получила приблизительно около 16,401. Хотя более правильно не извлекать корень.

3 норма матрицы представляет из себя максимальное из чисел, полученных при сложении всех элементов каждой строки, взятых по модулю.

В нашем примере: в первой строке стоят элементы: 8, 8. Все элементы положительные. Найдем их сумму: 8+8=16. В второй строке стоят элементы: 3, -2. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 3+2=5. В третьей строке стоят элементы 8, и -8. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 8+8=16. Максимальное из этих трех чисел — это 16. Значит третья норма матрицы равна 16.

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

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

В Matlab используется следующие функции поиска нормы:

Пусть А —матрица. Тогда n=norm(A) эквивалентно п=погп(А,2) и возвращает вторую норму, т. е. самое большое сингулярное число А. Функция n=norm(A, 1) возвращает первую норму, т. е. самую большую из сумм абсолютных значений элементов матрицы по столбцам. Норма неопределенности n=norm(A, inf) возвращает самую большую из сумм абсолютных значений элементов матрицы по рядам. Норма Фробениуса (Frobenius) norm(A, ‘fro’) = sqrt(sum(diag(A’A))).

Числа обусловленности матрицы определяют чувствительность решения системы линейных уравнений к погрешностям исходных данных. Следующие функции позволяют найти числа обусловленности матриц.

cond(X) — возвращает число обусловленности, основанное на второй норме, то есть отношение самого большого сингулярного числа X к самому малому. Значение cond(X), близкое к 1, указывает на хорошо обусловленную матрицу;

с = cond(X,p) — возвращает число обусловленности матрицы, основанное на р-норме: norm(X,p)*norm(inv(X),p), где р определяет способ расчета:

р=1 — число обусловленности матрицы, основанное на первой норме;

р=2 — число обусловленности матрицы, основанное на второй норме;

p= ‘fro’ — число обусловленности матрицы, основанное на норме Фробе-ниуса (Frobenius);

р=’inf’ — число обусловленности матрицы, основанное на норме неопределенности.

с = cond(X) — возвращает число обусловленности матрицы, основанное на второй норме.

condeig(A) — возвращает вектор чисел обусловленности для собственных значений А. Эти числа обусловленности — обратные величины косинусов углов между левыми и правыми собственными векторами;

[V.D.s] = condeig(A) — эквивалентно [V,D] = eig(A): s = condeig(A);.

Большие числа обусловленности означают, что матрица А близка к матрице с кратными собственными значениями.

rcond(A) — возвращает обратную величину обусловленности матрицы А по первой норме, используя оценивающий обусловленность метод LAPACK. Если А — хорошо обусловленная матрица, то rcond(A) около 1.00, если плохо обусловленная, то около 0.00. По сравнению с cond функция rcond реализует более эффективный в плане затрат машинного времени, но менее достоверный метод оценки обусловленности матрицы.

Число обусловленности матрицы

Дается очень интуитивное представление о важной характеристике квадратной матрицы, существенной для решения систем линейных уравнений с этой матрицей.

Пример. Система линейных уравнений $ AX =\mathcal B $ при

$$ A=\left(\begin -2 & 2 \\ 19 & -18 \end \right), \ B= \left(\begin 1 \\ 2 \end \right),\ X= \left(\begin x_1 \\ x_2 \end \right), $$ имеет решение $ X_0= [11.0, 11.5]^ $. При небольшом возмущении столбца правых частей $ \mathcal B= [1.0,2.1]^ $ решение меняется в пределах того же возмущения: $ X= [11.1, 11.6]^ $. Но вот при $ \mathcal B= [1.1,2.0]^ $ решение изменится более существенно: $ X= [11.9, 12.45]^ $. Обнаруженный эффект принципиально важен для численных методов решения систем линейных уравнений: с какой точностью следует производить вычисления?

Для выяснения причины этого эффекта будем искать геометрическое место точек плоскости $ \mathbb R^2 $, удовлетворяющих неравенству $$ (-2 x_1 +2x_2-1)^2+(19x_1 -18 x_2-2)^2 \le \varepsilon^2 \iff $$ $$ \iff (AX-\mathcal B)^(AX-\mathcal B) \le \varepsilon^2 $$ при различных значениях $ \varepsilon $, в частности, при $ \varepsilon = 0.1 $. Очевидным решением является внутренность эллипса с центром в точке $ X_0 $. Этот эллипс оказывается очень «сплюснутым»: так, при $ \varepsilon = 0.1 $, его полуоси равны $ \approx 1.31624 $ и $ \approx 0.00380 $. При любом выборе $ X $ внутри эллипса погрешность столбца $ \widetilde<\mathcal B>= AX $ относительно столбца $ \mathcal B $ не превосходит $ \varepsilon $. Однако при одной и той же величине погрешности в столбце $ \mathcal B $ соответствующие решения системы могут меняться как очень немного, так и значительным образом.

Известно, что форма эллипса, заданного неявным алгебраическим уравнением второго порядка, определяется только мономами второго порядка. В разбираемом примере — элементами матрицы $$ A^ A = \left(\begin 365 & -346 \\ -346 & 328 \end \right) \, . $$ Полуоси определяются через посредство собственных чисел этой матрицы. Именно, $$ \lambda_1\approx 0.00577, \lambda_2 \approx 692.99422 $$ и длины полуосей равны $ 1/ \sqrt <\lambda_1>$ и $ 1/ \sqrt <\lambda_2>$. В геометрии величина отношения длин малой полуоси к большой называется коэффициентом сжатия эллипса или эллиптичностью. А в алгебре обратная величина, т.е. $$ \sqrt <\lambda_2/\lambda_1>\approx 346.49711 $$ носит другое название. ♦

Для матрицв $ A \in \mathbb R^ $ обозначим $ \sigma_ $ ее максимальное сингулярное число, а $ \sigma_ $ — минимальное. При $ \sigma_ \ne 0 $ величина $$ \operatorname (A)= \sigma_/\sigma_ $$ называется числом обусловленности матрицы 1) $ A $. Очевидно, $ \operatorname (A) \ge 1 $. При $ \operatorname (A) $ близком к $ 1 $ матрица называется хорошо обусловленной, при $ \operatorname (A) \gg 1 $ матрица $ A $ называется плохо обусловленной 2) .

Только что введенное определение завязано на метрику пространства $ \mathbb R^n $, которая выше предполагалась евклидовой. В пространствах векторов и матриц близость можно определять различными способами, и этот формализм вводится посредством понятия нормы. Соответственно, и число обусловленности вводится в зависимости от формул, задающих нормы 3) . В интернете можно найти доказательство следующего универсального результата $$ \operatorname (A)=\|A\| \cdot \|A^\| \ , $$ который, с практической точки зрения, абсолютно бесполезен. (Если воможно точно вычислить матрицу $ A^ $, зачем вычислять число обусловленности?)

Еще одно замечание касается числовых эквивалентов выражений «близко к 1» и «значительно превышает 1». Понятно, что эти выражения субъективны и зависят от требований к точности представлений исходных данных и вычислений в конкретно решаемой задаче. Принято считать $ \operatorname (A)\le 10 $ хорошим числом, а $ \operatorname (A)\ge 1000 $ — плохим числом. Но это всё — условности.

Пример. Матрица Вандермонда

$$ V= \left(\begin 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2^2 & 2^3 & 2^4 \\ 1 & 3 & 3^2 & 3^3 & 3^4\\ 1 & 4 & 4^2 & 4^3 & 4^4\\ 1 & 5 & 5^2 & 5^3 &5^4 \end \right) $$ может считаться плохо обусловленной: $ \operatorname (V) \approx 26169 $.

Пример. Матрица Гильберта

$$ \mathfrak H_4= \left[\frac \right]_^4 = \left( \begin 1 & 1/2 & 1/3 & 1/4 \\ 1/2 & 1/3 & 1/4 & 1/5 \\ 1/3 & 1/4 & 1/5 & 1/6 \\ 1/4 & 1/5 & 1/6 & 1/7 \end \right) $$ плохо обусловлена: $ \operatorname (\mathfrak H_4) \approx 15513 $.

Если матрица $ A $ близка к вырожденной, то ее минимальное сингулярное число близко к нулю. Как правило (т.е. для случайно выбранных матриц) максимальное сингулярное число будет существенно отличаться от $ 0_<> $. Поэтому утверждение «матрица, близкая к вырожденной, будет и плохо обусловленной» имеет вероятностную справедливость. Но контрпримеры типа $$ A= \left(\begin 0.0001 & 0 \\ 0 & 0.0001 \end \right) $$ следует «держать в уме».

(англ.) condition number
(англ.) well- and ill- conditioned

Причем нормы в пространстве векторов и в пространстве матриц должны быть аккуратно между собой согласованы — см. понятие индуцированной нормы

Число обусловленности матрицы

Число обусловленности матрицы показывает насколько матрица близка к матрице неполного ранга (для квадратных матриц — к вырожденности).

Рассмотрим систему линейных уравнений

Если матрица A вырожденная, то для некоторых b решение x не существует, а для других b оно будет неединственным. Следовательно, если A почти вырожденная, то можно ожидать, что малые изменения в A и b вызовут очень большие изменения в x. Если же взять в качестве A единичную матрицу, то решение системы (1) будет x=b. Следовательно, если A близка к единичной матрице, то малые изменения в A и b должны влеч за собой малые изменения в x.

Рассмотрим это на численном примере

Как видно из Рис. 1, векторы строки матрицы Aи линейно зависимы. Следовательно существует нуль-пространство N(A) ортогональное к и . Так как b∈R(A), имеем множество решений ,,. . Если же взять , то b∉R(A) и, следовательно, система линейных уравнений не имеет решения. Далее, изменим в (2) вектор строку матрицы A. Пусть . Тогда система (2) имеет единственное решение . Получили, что малое изменение в A или b совешенно меняет решение системы (2). Такие матрицы называют плохо обусловленными.

Для оченки обусловленности матрицы вычисляют число обусловленности матрицы (обозначается символом «cond»). Для вычисления числа обусловленности введем понятия нормы для векторов x. В качестве нормы возмем l-норму вектора:

Умножая вектор х на матрицу A приводит к новому вектору Ax, норма которого может слишком отличаться от нормы вектора x. Эта чувствительность матрицы A мы хотим измерять. Максимальное и минимальное изменение Ax при изменении можно задать следующими числами:

Отношение Q/q называется числом обусловленности матрицы A:

В системе (1) изменим b на Δb. Тогда имеем:

Из (1) и (7) следует A·Δx=Δb. Тогда, учитывая (4) и (5) получим следующие неравенства:

Следовательно при q≠0 имеем:

При относительном изменении правой части , относительная ошибка может составить .

Если q=0, то cond(A)=+∞, т.е. матрица неполного ранга (вырожденная). Чем больше cond(A), тем ближе матрица A к неполному рангу (к вырожденности). Чем ближе матрица к единичной матрице, тем больше cond(A) близка к 1 и , следовательно, матрица далека от неполного ранга (далека от вырожденности).

Свойства числа обусловленности матрицы:

обусловленность матрицы

  1. cond(A)>=1 (т.к. Q>=q).
  2. cond(P)=1, где P-матрица перестановок или единичная матрица.
  3. cond(λA)=cond(A), где λ скаляр.
  4. , где D диагональная матрица.

Свойства 3 и 4 показывают, что cond(A) является лучшей критерией оценки вырожденности квадратных матриц, чем определитель. Действительно, если взять в качестве матрицы A квадратную диагональную матрицу 100×100 с элементами 0.1 на главной диагонали, то det(A)=(0.1) 100 =10 -100 , что очень малое число и показывает близость к вырожденности в то время, как строки и столбцы матрицы ортогональны и, в действительности матрица далека от вырожденности. Если же применять cond, то получим cond(A)=1.

Следующий пример иллюстрирует понятие числа обусловленности матрицы. Рассмотрим систему линейных уравнений (1), где

Тогда решением системы линейных уравнений будет . Если же правую заменить на , решением системы будет . Обозначим Δb=b-b1 и Δx=x-x1. Тогда

Из (13) видно, что очень малое изменение в b, совершенно изменил решение x. Так как

Неравенство (15) показывает что матрица A плохо обусловлена, т.е. близка к вырожденности. С помощью экспериментальных вычислений мы обнаружили плохую обусловленность матрицы A. А как, на самом деле, вычислить число обусловленности матрицы. В выражении (4) Q называется нормой матрицы и ее можно вычислить с помощью следующего вырaжения:

где aj — j-ый столбец матрицы A. Оказывается, что 1/q является нормой обратной к A (если существует) матрицы A -1 : . Тогда

Вы можете вычислить обусловленность матрицы используя матричный онлайн калькулятор. Для этого вычислите обратную к матрице A, вычислите нормы для матриц A и A -1 и, используя выражение (17), вычислите cond(A).

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

Найдите след, ранг, обобщенное обращение, нормы и числа обусловленности квадратной матрицы.

Щелкните для копирования этого выражения

След, ранг и обобщенное обращение матрицы

1. Используйте функцию tr , чтобы найти след, т. е. сумму диагональных элементов M .

Щелкните для копирования этого выражения

2. Используйте функцию rank , чтобы найти ранг вещественной матрицы M .

Щелкните для копирования этого выражения

3. Используйте функцию geninv , чтобы найти обобщенное обращение матрицы M .

Щелкните для копирования этого выражения

Различные нормы матрицы

1. Найдите норму L1 матрицы M и сравните результат с результатом функции norm1 .

Норма L1 — это максимальное значение абсолютных сумм столбцов (максимум по j= 0, 1, 2).

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

2. Используйте функцию norm2 , чтобы найти норму L2 матрицы M .

Щелкните для копирования этого выражения

3. Используйте функцию norme , чтобы найти евклидову норму M .

Евклидова норма матрицы определяется аналогично евклидовой норме вектора:

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

4. Найдите бесконечную норму M и сравните результат с результатом функции normi .

Бесконечная норма — это максимальное значение абсолютных сумм строк (максимум по i=0, 1, 2)

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

Щелкните для копирования этого выражения

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

Число обусловленности матрицы — это произведение двух норм матрицы. Оно показывает чувствительность решения системы линейных уравнений к ошибкам во входном векторе:

Щелкните для копирования этого выражения

1. Используйте функцию cond1 , чтобы найти число обусловленности L1 матрицы M .

Щелкните для копирования этого выражения

2. Используйте функцию cond2 , чтобы найти число обусловленности L2 матрицы M .

Щелкните для копирования этого выражения

3. Используйте функцию conde , чтобы найти евклидово число обусловленности матрицы M .

Щелкните для копирования этого выражения

4. Используйте функцию condi , чтобы найти бесконечное число обусловленности матрицы M .

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *