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

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

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

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

Ax=b

(1)

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

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

(2)

 

   

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

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

(3)

Умножая вектор х на матрицу A приводит к новому вектору

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

(4)

(5)

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

(6)

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

(7)

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

(8)

(9)

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

(10)

или

(11)

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

Если 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)¹⁰⁰=10^-100, что очень малое число и показывает близость к вырожденности в то время, как строки и столбцы матрицы ортогональны и, в действительности матрица далека от вырожденности. Если же применять cond, то получим

cond(A)=1.

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

(12)

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

(13)

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

(14)

имеем

(15)

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

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

(16)

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

(17)

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

 

Способы повышения обусловленности матриц при решении систем разностных уравнений в задачах идентификации параметров динамических объектов

%PDF-1.3 % 1 0 obj > endobj 4 0 obj /Title >> endobj 2 0 obj > endobj 3 0 obj > stream

Способы повышения обусловленности матриц при решении систем разностных уравнений в задачах идентификации параметров динамических объектов

Боловин Евгений Владимирович; Глазырин Александр Савельевич endstream endobj 5 0 obj > >> /Contents [13 0 R 14 0 R 15 0 R] /CropBox [0 0 595. 0 842.0] /Annots [16 0 R] >> endobj 6 0 obj > /Contents 19 0 R /CropBox [0 0 595.0 842.0] >> endobj 7 0 obj > /Contents 23 0 R /CropBox [0 0 595.0 842.0] >> endobj 8 0 obj > /Contents 26 0 R /CropBox [0 0 595.0 842.0] >> endobj 9 0 obj > /Contents 29 0 R /CropBox [0 0 595.0 842.0] >> endobj 10 0 obj > endobj 11 0 obj > endobj 12 0 obj > stream x

Что такое номер состояния матрицы? » Cleve’s Corner: Cleve Moler on Mathematics and Computing

Несколько вопросов в комментариях к недавним сообщениям в блоге побудили меня обсудить матричные числа условий.

В комментарии к моему посту о матрицах Гильберта читатель по имени Мишель спросил:

• Не могли бы вы прокомментировать, когда число обусловленности дает точную оценку ошибки в вычисляемой обратной величине и существует ли лучшая оценка?

А в комментарии к моему посту про четверную точность Марк спросил:

• У вас есть какое-нибудь представление о коэффициенте замедления. .. для решения больших линейных уравнений с крайне плохо обусловленными матрицами?

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

Содержание

• Номер условия для инверсии
• Нормы
• Линейные уравнения
• Пример
• Близкие к сингулярным
• Обратные
• Скорость

Число условий для инверсии

Сначала я должен отметить, что существует множество различных чисел условий и что, хотя спрашивающие, возможно, не осознавали этого, они спрашивали только об одном из них — о числе условий для инверсии. В общем случае число обусловленности относится не только к конкретной матрице, но и к решаемой задаче. Инвертируем ли мы матрицу, находим ее собственные значения или вычисляем экспоненту? Список можно продолжить. Матрица может быть плохо обусловлена ​​для обращения, в то время как проблема собственных значений хорошо обусловлена. Или наоборот.

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

Когда мы просто говорим, что матрица «плохо обусловлена», мы обычно думаем только о чувствительности ее инверсии, а не обо всех других числах обусловленности.

Нормы

Чтобы уточнить эти понятия, начнем с векторной нормы. В частности, евклидова норма 9{1/2}$$

Это расстояние «по прямой» в n -мерном пространстве.

Соответствующая норма матрицы $A$ измеряет, насколько отображение, индуцированное этой матрицей, может растягивать векторы.

$$M \ = \\|A\| \ = \ {\max {{\|Ax\|} \over {\|x\|}}}$$

Иногда также важно учитывать, насколько матрица может сжимать векторы.

$$m \ = \ {\min {{\|Ax\|} \over {\|x\|}}}$$

Обратная величина минимального растяжения является нормой обратной, поскольку 9{-1}\|$$

Если матрица вырожденная, то ее число обусловленности бесконечно.

Линейные уравнения

Число обусловленности $\kappa(A)$ участвует в ответе на вопрос: Насколько изменение правой части системы одновременных линейных уравнений может повлиять на решение? Рассмотрим систему уравнений

$$A x \ = \ b$$

и вторую систему, полученную изменением правой части

$$A(x + \delta x) = b + \delta b$ $

Думайте о $\delta b$ как об ошибке в $b$, а $\delta x$ как о результирующей ошибке в $x$, хотя нам не нужно делать никаких предположений о том, что ошибки малы. Поскольку $A (\delta x) = \delta b$, определения $M$ и $m$ немедленно приводят к

$$\|b\| \leq M \|x\|$$

и

$$\|\delta b\| \geq m \|\delta x\|$

Следовательно, если $m \neq 0$,

$${\|\delta x\| \over \|x\|} \leq \kappa(A) {\|\delta b\| \над \|b\|}$$

Величина $\|\delta b\|/\|b\|$ представляет собой относительное изменение в правой части, а величина $\|\delta x\|/\|x\|$ равна в результате относительных изменений в растворе. Преимущество использования относительных изменений состоит в том, что они безразмерны — на них не влияют общие коэффициенты масштабирования.

Это неравенство показывает, что число обусловленности является коэффициентом увеличения относительной ошибки. Изменения в правой части могут вызвать изменения решения в $\kappa(A)$ раза больше.

Пример

Исследуем систему линейных уравнений, включающую

$$A=\left(\begin{array}{cc} 4.1 & 2.8 \\ 9.7 & 6.6 \end{array}\right)$$

Возьмем $b$ за первый столбец $A$, поэтому решение $Ax = b$ будет просто

$$x = \left(\begin{array}{c} 1 \\ 0 \end{array }\right)$$

Переключиться на MATLAB

 A = [4.1 2.8; 9,7 6,6]
  б = А (:, 1)
  х = А\б
 

 А =
    4.1000 2.8000
    9.7000 6.6000
б =
    4.1000
    9.7000
х =
    1.0000
   -0,0000
 

Теперь добавьте 0,01 к первому компоненту b.

 b2 = [4,11; 9.7]
 

 б2 =
    4.1100
    9.7000
 

Решение резко меняется.

 х2 = А\b2
 

 х2 =
    0,3400
    0,9700
 

Эта чувствительность решения x к изменениям в правой части b является отражением числа обусловленности.

 каппа = условный (А)
 

 каппа =
   1.6230e+03
 

Верхняя граница возможного изменения x указывает на изменения всех значащих цифр.

 каппа*норма(b-b2)/норма(b)
 

 и =
    1,5412
 

Фактическое изменение x в результате этого возмущения равно

 норма(х-х2)/норма(х)
 

 и =
    1.1732
 

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

Близко к сингулярности

Большое число обусловленности означает, что матрица близка к сингулярности. Сделаем небольшое изменение во второй строке A.

 A
  А2 = [4,1 2,8; 9,676 6,608]
 

 А =
    4.1000 2.8000
    9,7000 6,6000
А2 =
    4.1000 2.8000
    9,6760 6,6080
 

Результирующая матрица эффективно сингулярна. Если мы попытаемся вычислить его инверсию, мы получим предупреждающее сообщение.

 A2инв = инв(A2)
 

 Предупреждение. Матрица близка к единственной или плохо масштабируется. Результаты могут быть неточными.
RCOND = 1,988677e-17.
A2инв =
   1.0e+15 *
   -1,4812 0,6276
    2,1689 -0,9190
 

Величина RCOND в предупреждении является оценкой обратной величины номера условия. Использование обратного числа осталось со времен, когда у нас не было арифметики с плавающей запятой IEEE с Inf для представления переполнения и бесконечности. Для этого примера RCOND имеет порядок eps(1), а коэффициент масштабирования для A2inv означает, что его элементы бесполезны. Невозможно вычислить то, чего нет. 9{-1}\|}} \\ле \ \kappa(A) {{\|E\|} \over {\|A\|}}$$

Работа Джима Уилкинсона об ошибке округления при исключении Гаусса показала, что каждый столбец вычисляемой обратной функции является столбцом точной обратная матрица в пределах ошибки округления данной матрицы. Давайте немного схитрим и скажем, что inv(A) вычисляет точную обратную величину $A+E$, где $\|E\|$ имеет порядок ошибки округления по сравнению с $\|A\|$ .

Мы точно не знаем $E$, но для матрицы размера n на n мы имеем оценку

norm(E) $\приблизительно \space$ n*eps(norm(A))

Итак, у нас есть простая оценка ошибки в вычисленном обратном значении относительно неизвестного точного обратного.

X = $\space$ точная инверсия A

Z = inv(A)

norm(Z — X)/norm(X) $\приблизительно$ n*eps*cond(A)

Для нашего 2 Пример — на 2 оценка относительной ошибки в вычисленном обратном значении равна

 2*eps*condest(A)
 

 и =
   9.9893e-13
 

Это говорит о том, что мы можем ожидать 12 или 13 (из 16) значащих цифр.

Уилкинсон должен был предположить, что каждая отдельная арифметическая операция с плавающей запятой вызывает максимальную ошибку округления. Но только часть операций вообще имеет какую-либо ошибку округления, и даже для них ошибки меньше максимально возможного. Так что эту оценку можно ожидать завышенной. Но более точная оценка невозможна.

Для нашего примера вычисленный обратный формат имеет длину

  Z = инв (А)
 

 З =
 -66.000000000000057 28.000000000000025
  97.000000000000085 -41.000000000000036
 

Оказывается, точная инверсия имеет целые числа, полученные

 X = round(Z)
 

 Х =
   -66 28
    97 -41
 

Мы можем сравнить фактическую относительную ошибку с оценкой.

 формат короткий
  норма(Z - X)/норма(X)
 

 и =
   8.7342э-16
 

Таким образом, мы имеем более 15 значащих цифр точности.

Скорость

93$.

Фактические числа в матрице (как правило) не влияют на время выполнения. Почти сингулярную матрицу можно инвертировать так же быстро, как и хорошо обусловленную. Ответ может быть не очень точным, если число обусловленности велико, но $\kappa(A)$ не играет роли в скорости.

Опубликовано с помощью MATLAB® R2017a

Калькулятор числа условий

Создано Rijk de Wet

Отзыв от Wojciech Sas, PhD и Стивена Вудинга

Последнее обновление: 03 октября 2022 г.

Содержание:

• Что такое номер состояния матрицы?
• Число обусловленности матрицы в линейной алгебре
• Как найти число обусловленности матрицы?
• Как пользоваться калькулятором номера состояния?
• Как найти число обусловленности матрицы? – Пример
• Часто задаваемые вопросы

Добро пожаловать в калькулятор номера состояния . Необходимо определить, является ли ваша задача линейной алгебры хорошо обусловленной или нестабильный ? Не приведут ли неправильные измерения или плохое округление к краху вашего матричного уравнения? Здесь мы покажем вам , что такое номер условия матрицы и , как найти номер условия любой матрицы, чтобы вы могли защитить себя от любых ошибок, которые могут закрасться.

Что такое номер состояния матрицы матрица?

Прежде чем мы сможем понять какой-либо результат, выдаваемый нашим калькулятором числа условий, давайте сначала определим матричное число условий и то, что оно представляет. Обычно мы обозначаем 9+\Vertcond(A)=∥A∥⋅∥A+∥. Это альтернативное определение по-прежнему будет давать огромных, почти бесконечных чисел состояния для необратимых матриц, тем самым по-прежнему соблюдая наше исходное определение.

Мы можем интерпретировать номер условия несколькими способами. Во-первых, cond(A)\text{cond}(A)cond(A) измеряет отношение максимального растяжения к максимальному сжатию в единичном векторе x⃗\vec{x}x (т.е. ∥x⃗∥=1\Vert\ vec{x}\Vert = 1∥x∥=1), когда на него умножается AAA. Таким образом, эквивалентное определение 9{-1} \end{выровнено}​cond(A)=∥x

∥=1max​∥x

∥∥Ax

∥​⋅(∥x

∥=1min​∥x

x

∥

∥ ​)−1​

В чистой математике матрица либо обратима, либо нет. Но, как второй способ интерпретации числа обусловленности, cond(A)\text{cond}(A)cond(A) является мерой того, насколько обратим AAA. Поскольку cond(A)\text{cond}(A)cond(A) увеличивается , AAA становится ближе к тому, чтобы быть необратимым .

Третье и наиболее важное использование чисел обусловленности — линейная алгебра . Давайте посмотрим, почему ниже!

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

Когда у нас есть система линейных уравнений A⋅x⃗=b⃗A\cdot\vec{x} = \vec{b}A⋅x=b, число обусловленности приобретает особый смысл. cond(A)\text{cond}(A)cond(A) теперь становится скоростью, с которой решение x⃗\vec{x}x изменится на по отношению к изменению b⃗\vec{b}b. По этой причине мы можем назвать cond(A)\text{cond}(A)cond(A) задачу коэффициент увеличения ошибки . Изменения в b⃗\vec{b}b обычно происходят из-за ошибок, допущенных при формулировании задачи , таких как выполнение ошибочных измерений или ошибок округления .

Итак, предположим, что закралась какая-то ошибка , и значения, содержащиеся в b⃗\vec{b}b, немного неверны . Насколько далеко от истины наше вновь найденное решение x⃗\vec{x}x, зависит от cond(A)\text{cond}(A)cond(A):

• Если номер условия матрицы AAA равен большой , x⃗\vec{x}x уязвим для ошибок . Таким образом, ошибка в x⃗\vec{x}x, возникающая из-за ошибки в b⃗\vec{b}b, будет большой .

• Обратно, если cond(A)\text{cond}(A)cond(A) является маленьким , x⃗\vec{x}x будет хорошо защищенным от разумных ошибок в b⃗\vec{b}b , поэтому его ошибка будет маленькой .

Мы можем математически переформулировать это соотношение. С δb⃗\delta\vec{b}δb, представляющим ошибку в b⃗\vec{b}b, и δx⃗\delta\vec{x}δx, результирующим изменением x⃗\vec{x}x, мы можем связать относительные ошибки ∥ δb⃗∥ / ∥b⃗∥\Vert \delta\vec{b}\Vert \ /\ \Vert \vec{b}\Vert ∥δb∥ / ∥b∥ и ∥δx⃗∥ / ∥x⃗∥\Vert \delta\vec {x}\Vert \ /\ \Vert \vec{x}\Vert ∥δx∥ / ∥x∥ с:

∥δx⃗∥∥x⃗∥≤cond(A)⋅∥δb⃗∥∥b⃗∥\footnotesize \ гидроразрыв { \Верт\дельта\век{х}\Верт }{ \Верт \vec{x}\Верт } \ле \text{условие}(A) \cdot \ гидроразрыв { \Верт\дельта\vec{b}\Верт }{ \Верт \vec{b}\Верт }∥x

∥∥δx

∥​≤cond(A)⋅∥b

∥∥δb

∥​

как относительная ошибка b⃗\vec{b}b , масштабированная числом условия .

Как найти число обусловленности матрицы? 9{-1}\Верт ∥A−1∥. Крайне важно использовать одну и ту же норму, выбранную выше, во всех наших расчетах.

Умножьте нормы , чтобы найти cond(A)\text{cond}(A)cond(A).

Как пользоваться калькулятором номера состояния?

Здорово знать, как рассчитать число условий матрицы, но иногда вам просто нужен ответ немедленно, чтобы сэкономить время. Вот тут-то и пригодится наш калькулятор числа условий матрицы . Вот как это использовать:

1. Выберите размерность вашей матрицы . Мы поддерживаем матрицы 2×22\times22×2 и 3×33×33×3.

2. Введите вашу матрицу построчно. Не стесняйтесь обращаться к символическому представлению вверху.

3. Выберите норму матрицы или оставьте выбранную по умолчанию норму матрицы 2.

4. Найти cond(A)\text{cond}(A)cond(A) внизу нашего матричного калькулятора номера состояния.

Как найти число обусловленности матрицы? – Пример

Чтобы закрепить полученные знания, давайте рассмотрим пример . Предположим, у нас есть линейная система A⋅x⃗=b⃗A\cdot \vec{x} = \vec{b}A⋅x=b с:

A=[3.70.97.81.9]\footnotesize А = \begin{bmatrix} 3,7 и 0,9 \\ 7,8 и 1,9\\ \end{bmatrix}A=[3.77.8​0.91.9​]

и

b⃗=[7.415.6]\footnotesize \vec{b} = \begin{bmatrix} 7.4\ 15,6\\ \end{bmatrix}b 9{-1}\cdot\vec{b} \\ &= \begin{bmatrix} 2 \\ 0 \end{bmatrix} \end{split}x

​=A−1⋅b

=[20​]​

Теперь давайте посмотрим, что произойдет, если мы добавим небольшую ошибку , равную 0,010,010,01, к первому элементу b⃗\ vec{b}b, чтобы сформировать b⃗err\vec{b}_\text{err}berr​.

b⃗err=[7.4115.6]\размер сноски \vec{b}_\text{ошибка} = \begin{bmatrix} 7.41\ 15,6\\ \end{bmatrix}b

err​=[7. 4115.6​]

Расчет x⃗err\vec{x}_\text{err}xerr​ в A⋅x⃗err=b⃗errA\cdot\vec{x}_\text {err} = \vec{b}_\text{err}A⋅xerr​=berr​, получаем: 9{-1}\cdot\vec{b}_\text{ошибка} \\ &= \begin{bmatrix} 3.9 \\ -7.8 \end{bmatrix} \\ \end{split}x

err​=A−1⋅b

err​=[3.9−7.8​]​

Существует огромная разница между x⃗\vec{x}x и x⃗err\vec{ х}_\текст{ошибка}ксерр​! Как вы уже могли догадаться, это потому, что AAA имеет большой номер состояния . На самом деле cond(A)=7 895\text{cond}(A) = 7\ 895cond(A)=7 895. Вы можете проверить этот результат в нашем калькуляторе норм матриц!

Интересно отметить, что отношение между нашими относительными ошибками и нашим числом условий соблюдается:

∥δx⃗∥ / ∥x⃗∥=4,014∥δb⃗∥ / ∥b⃗∥=0,00058cond(A)×∥δb⃗∥ / ∥b⃗∥=4,573\footnotesize \начать{разделить} \Vert \delta\vec{x}\Vert \ /\ \Vert \vec{x}\Vert &= 4.014 \\ \Vert \delta\vec{b}\Vert \ /\ \Vert \vec{b}\Vert &= 0. 00058 \\ \text{cond}(A) \times \Vert \delta\vec{b}\Vert \ /\ \Vert \vec{b}\Vert &= 4,573 \ end {split} ∥Δx

∥/∥x

∥∥ΔB

∥/∥B

∥cond (a) × ∥ΔB

∥/∥B

∥ = 4,014 = 0,00058 = 4,5733333

∥ = 4,014 = 0,00058 = 4,573.​

4,573≤4,0144,573 \le 4,0144,573≤4,014 и, следовательно, относительная ошибка нашего решения не превышает относительная ошибка задачи , увеличенная числом условий ААА.

Часто задаваемые вопросы

Что такое номер условия матрицы идентичности?

Число обусловленности единичной матрицы любого размера равно 1 . Поскольку единичная матрица оставляет нетронутым любой вектор, на который она умножается, она не увеличивает ошибку в b . Следовательно, интуитивно понятно, что единичная матрица имеет число обусловленности 1.

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

Каково число обусловленности диагональной матрицы?

Число обусловленности диагональной матрицы D равно отношению между наибольшим и наименьшим элементами на ее диагонали , т. е. cond(D) = max(D _ii ) / min(D _ii ). Важно отметить, что это верно только при использовании матрицы 2-норма для вычисления cond(D). Во многом это связано с тем, что диагональные элементы D являются его собственными значениями.

Может ли число обусловленности матрицы равняться нулю?

Нет. Если cond(A) = 0, то cond(A)×‖δb⃗‖/‖b⃗‖ = 0 и, следовательно, ‖δx⃗‖/‖x⃗‖ ≤ 0. Следовательно, номер условия 0 будет означать, что матрица удаляет любую ошибку , что невозможно.