Главная > Математика > Вычислительные методы для инженеров
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 5.4. Обусловленность задачи решения системы линейных алгебраических уравнений

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

может быть как хорошо, так и плохо обусловленной.

Исследование обусловленности задачи начнем со случая, когда элементы матрицы А считаются заданными точно, а вектор-столбец правой части — приближенно.

Лемма 5.1. Для погрешности приближенного решения системы (5.18) справедлива оценка

где невязка, отвечающая х.

Для доказательства достаточно взять норму левой и правой частей равенства (5.3) и воспользоваться свойством (5.10).

Теорема 5.1. Пусть точное решение системы в которой правая часть является приближением к Тогда верны следующие оценки абсолютной и относительной погрешностей:

где

В рассматриваемом случае и неравенство (5.19) принимает вид (5.20). Разделив теперь обе части неравенства (5.20) на и записав его в виде

приходим к оценке (5.21).

Замечание 1. Величина для задачи (5.18) играет роль абсолютного числа обусловленности (см. § 3.2). Замечание 2. Величина называется естественным числом обусловленности. Она зависит от конкретного решения х и характеризует коэффициент возможного возрастания относительной погрешности этого решения, вызванного погрешностью задания правой части. Это означает, что для задачи вычисления решения х системы (5.18) играет роль относительного числа обусловленности (см. § 3.2).

Замечание 3. Полученные в теореме 5.1 оценки точны в том смысле, что для системы с произвольной невырожденной матрицей А и любой заданной правой частью найдется сколь угодно близкий к 6 приближенно заданный вектор для которого неравенства (5.20) и (5.21) превращаются в равенства.

Вычислим максимальное значение естественного числа обусловленности, используя определение (5.4) нормы матрицы:

Полученную величину принято называть стандартным числом обусловленности (или просто числом обусловленности матрицы А и обозначать через или Таким образом,

Сформулируем важное следствие из теоремы 5.1. Следствие. В условиях теоремы 5.1 справедлива оценка

Для ее доказательства достаточно воспользоваться оценкой (5.21) и заметить, что в силу определения (5.22) верно неравенство

Замечание. Оценка (5.24) точна в том смысле, что для системы (5.18) с произвольной невырожденной матрицей А найдутся правая часть (и отвечающее этой правой части решение и сколь угодно близкий к приближенно заданный вектор такие, что неравенство (5.24) превращается в равенство.

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

Отметим следующие свойства числа обусловленности.

1°. Для единичной матрицы

Пользуясь тем, что (см. пример 5.3), получим

2°. Справедливо неравенство

Из равенства свойства 4° норм матриц и равенства следует, что

3°. Число обусловленности матрицы А не меняется при умножении матрицы на произвольное число

Заметим, что Поэтому

Замечание. Пользуясь приведенной в § 5.2 геометрической интерпретацией норм матриц (см. формулы (5.15) и (5.16)), число обусловленности можно интерпретировать как отношение

максимального коэффициента растяжения векторов под действием матрицы А к минимальному коэффициенту:

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

Пример 5.4. Вычислим для матрицы

Сначала найдем обратную матрицу

Тогда и 378. Если входные данные для системы уравнений с матрицей (5.25) содержат относительную погрешность порядка то систему можно расценить как плохо обусловленную.

Пример 5.5. Рассмотрим систему уравнений

с матрицей (5.25). Ее решением является . Правая часть системы известна в лучшем случае с точностью до 0.005, если считать, что числа 2.51 и 2.41 получены округлением "истинных" значений при вводе в память трехзначной десятичной ЭВМ. Как влияет погрешность во входных данных такого уровня на погрешность решения? Возмутим каждую из компонент вектора правой части на величину 0.005, взяв Решением системы, отвечающим является теперь х и . Таким образом, решение оказалось полностью искаженным. Относительная погрешность задания правой части привела к относительной погрешности решения . Следовательно, погрешность возросла примерно в 237 раз.

Можно ли ввести в правую часть системы (5.26) такую погрешность, чтобы получить существенно большее, чем 237, значение коэффициента роста ошибки? Вычислим естественное число обусловленности, являющееся максимальным значением рассматриваемого коэффициента, отвечающим решению

и получим

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

Можно дать следующую геометрическую интерпретацию рассмотренного примера. Каждому уравнению системы (5.26) соответствует прямая на плоскости По коэффициентам при и в этих уравнениях видно, что прямые почти параллельны. Так как вблизи точки пересечения прямые почти сливаются, то даже незначительная погрешность в задании положения этих прямых существенно меняет положение точки пересечения (рис. 5.2).

Пример 5.6. Традиционным примером очень плохо обусловленной матрицы является матрица Гильберта — матрица И с элементами

Из табл. 5.1, заимствованной из [87], видно, что для матрицы И даже сравнительно невысокого порядка число обусловленности оказывается чрезвычайно большим.

Таблица 5.1 (см. скан)

Рис. 5.2

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

Теорема 5.2. Пусть точное решение системы с приближенно заданной матрицей А. Тогда верна следующая оценка относительной погрешности:

В данном случае невязка имеет вид Применяя неравенство (5.19), получим цепочку неравенств

Следствие. В условиях теоремы 5.2 справедливо приближенное неравенство

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

Замечание 2. Распространенным является представление о том, что по величине определителя матрицы А можно судить о степени близости системы уравнений к вырожденной или об обусловленности системы. Для того чтобы убедиться в ошибочности этого мнения, умножим каждое из уравнений системы (5.1) на постоянную Ясно, что такое преобразование никак не меняет решение системы и его чувствительность к малым относительным ошибкам в данных. Однако определитель умножается на число и поэтому с помощью выбора а может быть сделан как угодно большим или малым. Подчеркнем, что число обусловленности при таком преобразовании системы не меняется в силу свойства 3°.

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

обусловленности с точностью до порядка. С эффективными методами, дающими оценки величин можно познакомиться в [67], [86].

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

<< Предыдущий параграф Следующий параграф >>
Оглавление