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

 

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

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

.                                 (7.6.16)

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

Если  «не очень велико», то будем говорить, что система хорошо обусловлена, если  «велико» – то система плохо обусловлена. Из (7.6.16) видно, что в плохо обусловленной задаче малым погрешностям исходных данных отвечают большие погрешности в решении.

Пусть система линейных алгебраических уравнений задана в виде:

,                               (7.6.17)

где  – невырожденная вещественная матрица.

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

,                    (7.6.18)

где  и  – максимальное и минимальное собственные значения матрицы . Таким образом, обусловленность системы (7.6.17) зависит от величины отношения .

Замечание. Если мартица  симмитрическая, то собственные значения матрицы  равны квадратам собственных значений матрицы А, т.е.

,                         (7.6.19)

где  соответственно максимальное и минимальное собственные значения матрицы .

Пусть  – величина невязки (результат подстановки найденного решения в исходную систему), т.е.

.                       (7.6.20)

Если (7.6.20) переписать в виде:

,                        (7.6.21)

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

                          (7.6.22)

и

,                         (7.6.23)

где  – погрешность вычисления обратной матрицы.

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

,                      (7.6.24)

то система хорошо обусловлена, если

,                           (7.6.25)

то система плохо обусловлена. Здесь  – вектор, являющийся -ой вектор-строкой матрицы .

Для проверки обусловленности системы и матрицы  можно использовать число обусловленности матрицы :

.                              (7.6.26)

Из (7.6.26) следует, что если матрица  близка к особенной, то число  будет велико, и матрица  будет плохо обусловленной, если  мало, то матрица  будет хорошо обусловленной. Как правило, система с плохо обусловленной матрицей будет плохо обусловленной системой и наоборот.

Значение числа  зависит от выбора нормы матрицы . Если  – вещественная матрица и используется третье определение нормы, то

.          (7.6.27)

Ввиду важности понятия обусловленности систем и матриц приведем численный пример.

 

Пример плохо обусловленной системы

Пусть дана система

,

где

, .

Точное решение системы: .

Точное значение обратной матрицы:

.

Если внести погрешность  только в один элемент  матрицы , то значение обратной матрицы будет равно

.

Решение системы также изменится и будет равно:

.

Если внести погрешность  в вектор свободных членов, т.е. , то решение системы будет следующим:

.

Собственные числа матрицы  равны: 5.468; 0.057; 3.08; 32.398, а отношение максимального собственного значения к минимальному есть 568.386. Число обусловленности матрицы , вычисленное по третьей норме, приблизительно равно 580.

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

Приведенные результаты получены в системе MathCAD, которая осуществляет все вычисления с 15 знаками после запятой, т.е. погрешность округления не оказала влияния на результат.

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

Метод Гаусса

 

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

Рассмотрим схему единственного деления. Систему  представим в виде:

      (7.6.28)

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

,           (7.6.29)

где

.

Исключим  из остальных уравнений системы. Для этого умножим (7.6.29) последовательно на  и вычтем из второго, третьего и т.д. последнего уравнения системы. Преобразованные уравнения будут иметь вид:

        (7.6.30)

где .

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

В результате придем к одной из двух ситуаций.

1. После  шагов преобразований получим систему вида:

         (7.6.31)

Решение полученной системы осуществляется снизу вверх следующим образом:

              (7.6.32)

2. После шага преобразований  система приняла вид:

      (7.6.33)

Тогда, если среди элементов  есть отличные от нуля, то система (7.6.28) не имеет решения, если все , , то система имеет бесчисленное множество решений (неизвестные  могут принимать любые значения, а  выражаются через них).

Приведение системы к виду (7.6.31) называется прямым ходом метода Гаусса, а нахождение ее решения (7.5.32) – обратным. Заметим, что на каждом шаге прямого хода метода Гаусса выбирается уравнение и неизвестное, подлежащие исключению из прочих уравнений. Это равносильно выбору коэффициента для очередного шага преобразований. Этот коэффициент называется ведущим и он должен быть отличным от нуля. Во избежание большой потери точности рекомендуется осуществлять такую перестановку уравнений, чтобы ведущий коэффициент являлся либо максимальным по модулю коэффициентом во всей системе, либо максимальным по модулю коэффициентом в выбранном уравнении. Такая процедура называется методом Гаусса с выбором главного элемента.

Метод Гаусса применим к вычислению определителей и обратных матриц. Так, значение определителя  матрицы  равно произведению ведущих коэффициентов:

                 (7.6.34)

а вычисление обратной матрицы осуществляется одновременным решением  систем:

,                     (7.6.35)

где  – единичный вектор (вектор, у которого все элементы, кроме -го, равны нулю, а -ый равен единице),  – -ый столбец матрицы . Невозможность вычисления обратной матрицы проявляется в невозможности решения какой-либо системы из (7.5.35).

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: