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

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

Не всегда малость невязки гарантирует малость погрешности найденного решения.

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

Но даже если невязка мала, вектор ошибки не обязательно мал:

Обусловленность – это внутреннее свойство матрицы A, не зависит от метода решения СЛАУ. Матрицы с большим числом обусловленности дают большие ошибки при решении систем. Логарифм числа обусловленности приближенно равен числу значащих цифр, теряемых в решении системы Ax=b.

Например, при e1»10 –7 , cond(A)»10 4 , относительная ошибка решения будет »10 –3 , т.е. рассчитывать можно на три верных разряда в решении.

Число cond(A) измеряет насколько близка к вырожденной матрица A и, что еще важнее, насколько чувствительно решение системы Ax=b к изменениям в A и b.

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

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

Þ ||Ax|| £ M∙||x||

Þ m∙||x|| £ ||Ax||

Отношение M/m и называют числом обусловленности матрицы A:

обозначение cond от английского слова conditioned – обусловленный.

Но – норма, согласованная с нормой x.

Обозначим образ оператора Ax за y: y=Ax. Тогда x=A –1 y. При x¹, y¹.

cond(A)= A||∙||A –1 ||. (6.11)

Покажем, что cond(A) измеряет чувствительность к погрешностям. Пусть правая часть уравнения Ax=b получила приращение («возмущение») Db, т.е. вместо истинного вектора b используется приближенный вектор b. Реакцией решения x на возмущение Db правой части будет вектор поправок Dx, т.е. x+Dx – решение уравнения

A(x+Dx)=b+Db.

Так как Ax=b, ADx=Db, откуда Dx= A –1 Db. Нормируем равенства и воспользуемся свойством нормы:

||b|| = ||Ax|| £ ||A||∙||x||,

||Dx|| = ||A –1 Db|| £ || A –1 ||∙||Db||,

где матричная норма согласована с векторной нормой. Перемножим два неравенства одинакового смысла:

||b||∙||Dx|| £ ||A||∙||x||∙|| A –1 ||∙||Db||,

Легко показать, что то же самое число cond(A) служит коэффициентом роста относительных погрешностей при неточном задании элементов матрицы A. А именно, если матрица A получила возмущение DA и x+Dx – решение возмущенной системы

Читайте также:  Linux как получить права root

(A+DA)(x+Dx)=b,

то справедливы неравенства

С более точным соотношением зависимости относительной погрешности решения dx от относительных погрешностей dA и db одновременно можно познакомиться в учебнике В.М.Вержбицкого «Основы численных методов», с. 30.

Основные свойства числа обусловленности:

1. Так как M ≥ m, cond(A) ≥ 1.

2. Умножение матрицы A на число не меняет числа обусловленности:

cond(с∙A) = cond(A).

3. Если D – диагональная матрица, то

Если мы рассмотрим матрицу

то cond(A) =1 и матрица идеально обусловлена, в то время как det(A) =10 –100 . Таким образом, этот пример демонстрирует, что малость определителя матрицы A является необходимым, но не достаточным условием плохой обусловленности системы.

Число обусловленности играет фундаментальную роль в анализе ошибок округления, совершаемых в ходе гауссова исключения. Пусть A и b заданы точно, x * – приближенное решение, полученное методом Гаусса в арифметике с плавающей точкой. Тогда

и , где c – обычно немного больше 1.

Основной результат в исследовании ошибок округления в гауссовом исключении принадлежит Дж.Х.Уилкинсону. Он доказал, что вычисленное решение x * точно удовлетворяет системе

где DAматрица, элементы которой имеют величину порядка ошибок округления в элементах матрица A. Тем самым все ошибки округления могут быть слиты воедино и рассматриваться как единственное возмущение, внесенное в матрицу A в момент записи в память компьютера, само же исключение осуществляется без ошибок. В этом смысле метод Гаусса – лучший алгоритм решения СЛАУ. Контроль качества вычислений может быть осуществлен по вектору невязок только для хорошо обусловленных систем

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10637 — | 8008 — или читать все.

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

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

Если матрица 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). Такие матрицы называют плохо обусловленными.

Читайте также:  Выбор из раскрывающегося списка в excel 2010

Для оченки обусловленности матрицы вычисляют число обусловленности матрицы (обозначается символом "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).

Рисунок. Иллюстрация СЛАУ с двумя неизвестными:

а – хорошо обусловленная; б – плохо обусловленная; в – вырожденная система уравнений.

Рисунок (а) соответствует случаю хорошо обусловленной системы уравнений. На рис. (в) представлен случай системы с вырожденной матрицей А ( det ( A )=0), здесь прямые, отвечающие каждому из уравнений, параллельны друг другу (уравнения линейно зависимы). Пример плохо обусловленной системы уравнений показан на рис. (б) – прямые, соответствующие двум уравнениям, почти параллельны.

Штриховые прямые на рис. (а) и (б) отвечают одному из уравнений, в котором немного изменены коэффициенты a ij или правая часть b j . Как видно, в случае хорошо обусловленной СЛАУ малые возмущения в величинах a ij и b i приводят к небольшим изменениям решения (точка пересечения прямых смещается незначительно). В случае плохо обусловленной системы уравнений малые изменения в коэффициентах ведут к большим изменениям в решении (точка пересечения прямых смещается сильно).

1. Хорошо обусловленная система (cond( A ) = 3):

Пусть при задании правой части второго уравнения ( b 2) допущена ошибка в 4-м знаке:

Как видно, здесь малые изменения в векторе свободных членов B приводят к небольшим изменениям в векторе решения x .

2. Плохо обусловленная система (cond( A ) » 3 × 10 5 ):

Пусть в правой части второго уравнения ( b 2) допущена ошибка в 5-м знаке:

В этом случае малые изменения в векторе B приводят к тому, что решение системы уравнений становится совершенно неузнаваемым!

Причина больших ошибок при решении второй системы становится ясна, если заметить, что уравнения в ней «почти» линейно зависимы (коэффициенты в уравнениях почти пропорциональны), т.е. прямые, отвечающие уравнениям, практически параллельны друг другу.

Отметим, что если при задании b 2 допущена ошибка только в 9-й значащей цифре ( b 2=255,000003), то полученное решение системы x 1=16,9985, x 2=0,0003 будет близко к точному решению.

Ссылка на основную публикацию
Adblock detector