Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 27
Текст из файла (страница 27)
Все ненулевые элементы такой матрицы расположены на в = 21 + 1 ближайших к главной диагоналях матрицы; число в принято Рис. Ы называть шириной ленин. Схематически ленточная матрица представлена на рис. 5,1. Частным случаем ленточной матрицы при в = 3 является трехдиагональная матрица. Ясно, что в случае в < ш ленточная матрица является разреженной.
1 5.4. Обусловленность задачи решения системы линейных алгебраических уравнений Оказывается, что решения различных систем линейных алгебраических уравнений обладают разной чувствительностью к погрешностям входных данных. Так же как и другие задачи (см. ~ 3.2), задача вычисления решения х системы уравнений (5.18) может быть как хорошо, так и плохо обусловленной. Исследование обусловленности задачи начнем со случая, когда элементы матрицы А считаются заданными точно, а вектор-столбец правой части — приближенно.
Л е и м а 5.1. Для погрешности приближеннозо решения сиспьеим (5.18) справедлива оценка 1я1 Ь(х') < ~А '~- ~т~, (5.19) Ь(х*) <~ и сь(Ь*), б(х*) ~ и б (Ь*), (5.20) (5.21) где ил — $А '1, и = $А '1 ° $ Ь$/$х~. а В рассматриваемом случае г = Ь вЂ” Ах* = Ь вЂ” Ь* и неравенство (5.19) принимает вид (5.20). Разделив теперь обе части неравенства (5,20) на ~~х~[ и записав его в виде приходим к оценке (5.21). И 3 а м е ч а н и е 1.
Величина иа — 1А '~ для задачи (5.18) играет роль абсолютного числа обусловленности (см. ~ 3.2). 3 а м е ч а н и е 2. Величина иб — — иб(х) = ~А ~~ ~)Ь|~/~х~ называет- ся естественным числом обусловленности. Она зависит от конкретного решения х и характеризует коэффициент возможного возрастания относительной погрешности этого решения, вызванного погрешностью задания правой части. Это означает, что и~(х) для задачи вычисления решения х системы (5.18) играет роль относительного числа обусловленности (см. ~ 3.2). 3 а и е ч а н и е 3. Полученные в теореме 5.1 оценки точны в том смысле, что для системы Ах = Ь с произвольной невырожденной матрицей А и любой заданной правой частью Ь 1 0 найдется сколь угодно близкий к Ь приближенно заданный вектор Ь* ~ Ь, для которого неравенства (5.20) и (5.21) превращаются в равенства. Вычислим максимальное значение естественного числа обусловленности, используя определение (5.4) нормы матрицы: гпах иб(х) = гпах = 'гА 1г ° ~А~.
~!А '~) ° ~!Ах!~ хФО хФО (5.22) 132 где г = Ь вЂ” Ах" — невязка, отвечающая х*. Для доказательства достаточно взять норму левой и правой частей равенства (5.3) и воспользоваться свойством (5.10). Т е о р е м а 5 1. Пусть х~ — точное решение системы Ах~ = Ь*, в которой правая часть Ь* является приближением к Ь. Тогда верны следующие оггенки абсолютной и относительной погрешностей: Полученную величину принято называть стандартнылг числолг обус- ловленности (или просто числом обусловленности) матрицы А и обоз- начать через р(А) или сопй(А). Таким образом, и (А) = сопс)(А) = ~А '~ ° ~А~. (5.23) Сформулируем важное следствие из теоремы 5.1. С л е д с т в и е.
В условиях теорелгы 5.1 справедлива оценха Ь(х') <с а(А) ° Ь(Ь*) (5.24) Для ее доказательства достаточно воспользоваться оценкой (5.21) и заметить, что в силу определения (5.22) верно неравенство и~<сопс1(А). 3 а м е ч а н и е. Оценка (5.24) точна в том смысле, что для системы (5.18) с произвольной невырожденной матрицей А найдутся правая часть о Х О (и отвечающее этой правой части решение х) и сколь угодно близкий к Ь приближенно заданный вектор $' ~ 6 такие, что неравенство (5.24) превращается в равенство.
Величина сопй(А) является широко используемой количественной мерой обусловленности системы Ах = 6. В частности, систему и матрицу А принято называть плохо обусловленнылги> если сопй(А) > 1, В силу оценки (5.24) и последнего замечания для такой системы существуют решения, обладающие чрезвычайно высокой чувствительностью к малым погрешностям задания входного данного о. Тем не менее заметим, что не для всякого решения х коэффициент о~(х) роста отно- 3 а м е ч а н и е.
Пользуясь приведенной в 3 5.2 геометрической интерпретацией норм матриц А и А ' (см. формулы (5.15) и (5,16)), число обусловленности можно интерпретировать как отношение 133 сительной ошибки достигает значений, близких к максимально возможному значению сопй(А). Отметим следующие свойства числа обусловленности. 1о. Для единичной лгатрицы сопй(Е) = 1. и Пользуясь тем, что Е' = Е и ~~Е~ = 1 (см. пример 5.3), получим а(Е) = ~Е ~ 1Ц = 1.
° 2о. Справедливо неравенство сопс1(А) ~~ 1. п Из равенства Е = А А 1, свойства 4о норм матриц и равенства ~Е$ = 1 следует, что 1 = $Е1 ~ ~$А г~ ° ~А~ = сопс1(А). ° Зс. Число обусловленности лгатрицы А не лгеняепгся при улгножении лгатрицы на произвольное число а 1 О. и Заметим, что (аА) г= а гА г. Поэтому соЫ(сгА) = ~~аА~ ° ~(аА) г~= = ( а~ ° ~А~ ) а) г~А г)~ = сопс1(А).И максимального коэффициента растяжения векторов под действием матрицы А к минимальному коэффициенту: сопд(А) = Ь „/Ь;„, Величина сопй(А) зависит, вообще говоря, от выбора нормы векторов в пространстве Ла. Фактически это есть зависимость максимального коэффициента роста ошибки от способа измерения величины входных данных и решения.
В частности, выбору нормы 1л1, (1 < р 4 м) отвечает сопйг(А) = ~А 1~р ~А~'р. Пример 5.4. Вычислим сош1 (А) для матрицы 1.03 0.991 0.991 0.943 (5.25) Сначала найдем обратную матрицу -87.4 91.8 1 91.8 -95.4 ~ ' Тогда сош1 (А)= 1А~ ° 1А1~ и 2.021 187.2 в 378. Если входные данные для системы уравнений с матрицей (5.25) содержат относительную погрешность порядка 0.1 — 1%, то систему можно расценить как плохо обусловленную. Пример 5.5.
Рассмотрим систему уравнений 1.03х1 + 0.991тг — 2.51, О. 991а1 + 0.943,тг = 2.41 (5.26) с матрицей (5.25). Ее решением является х1 и 1.981, гг м 0,4735. Правая часть системы известна в лучшем случае с точностью до 0.005, если считать, что числа 2.51 и 2.41 получены округлением "истинных" значений при вводе в память трехзначной десятичной ЭВМ. Как влияег погрешность во входных данных такого уровня на погрешность решения? Возмутим каждую из компонент вектора правой части Ь = (2.51, 2.41)т на величину 0.005, взяв Ь~ = = (2.505, 2.415)т.
Решением системы, отвечающим Ь', является теперь г' м ю 2.877, г* ~ — 0.4629. Таким образом, решение оказалось полностью искажен- ным. Относительная погрешность задания правой части Я Ь «) = ~ Ь вЂ” Ь*1„/~ Ц = 0.005/2.51 и 0.2% привела к относительной погрешности решения 6(л*) = ~ л — а*1 /~ х~ в 0.9364/1.981 ~ 47.3%. Следовательно, погрешность возросла примерно в 237 раз.
Можно ли ввести в правую часть системы (5.26) такую погрешность, чтобы получить существенно большее, чем 237, значение коэффициента роста ошибки. Вычислим естественное число обусловленности, являющееся максималь- 7 ным значением рассматриваемого коэффициента, отвечающим решению т и н (1.981, 0.4735)т и получим иб(к) = ~А 11 ~Ц„/~х~ н 187.2 2.51/1.981 н 237.
Таким образом, на поставленный вопрос следует ответить отрицательно. Можно дать следующую геометрическую интерпретацию рассмотренного примера. Каждому уравнению системы (5.26) соответствует прямая на плоскости Ох1вх. По х, коэффициентам при х1 и хх в этих уравнениях видно, что прямые почти параллельны. Так как вблизи точки пересечения прямые почти сливаются, то даже незначительная погрешность в задании положения этих прямых существенно меняет положение к, точки пересечения (рис. 5.2).
Пример 5.6. Традиционным примером очень плохо обусловленной матрицы является матрица Гильберта| — матрица Я с Рис. в,х элементами Щ~ = 1/(1+ х' — 1). Из табл. 5.1, заимствовалной из [87~, видно, что для матрицы Н даже сравнительно невысокого порядка число обусловленности оказывается чрезвычайно большим. Таблица 51 Порядок матрицы 2 3 4 5 . 6 7 8 9 10 Гильберта Приближенное значение числа 2 101 5 10х 2 104 5 ° 10ь 2 107 5.10в 2 101о 5 10п 2 10ы обусловленности До сих пор мы- предполагали, что матрица А задана точно. Однако на практике это часто не так. Как выясняется, введенная выше величина сопс1(А) характеризует также и чувствительность решений системы к малым погрешностям задания элементов матрицы А. В подтверждение сказанного приведем следующий результат. Т е о р е м а 5.2.
Пусть к* — точное решение систелхи А,к~ = Ь с приближенно заданной матрицей А,. Твхда верна следующая оценка относительной нохреихности: 1 Давид Гильберт (1862 — 1943) — немецкий математик, исследования котоРого оказали большое влияние на развитие современной математики. 135 6'(х') 4 сопс$(А) 6(А,), (5.27) 6*(х*) = ~х — х'~/~~х*~~ < ~А '~ ~(А, — А)х*~/~х*~~ ( ~ 1А '~~ ° 1А, — А~ ° '1х*~~/~х'~ = сопс1(А) *6(А,).
° С л е д с т в и е. В условиях теоремы 5.2 справедливо прибдиженнов неравенстпво 6 (х*) < сопс1(А) 6(А,). (5.28) 3 а м е ч а н и е 1. В случае, когда с погрешностью заданы как правая часть системы, так и матрица (т. е. х* является решением системы А,х* = Ь*), причем сопй(А) ° 6(А,) < 1, можно доказать справедливость неравенства 6 (х*) < сопс1(А) (6 (Ь') + 6 (А,)). 3 а м е ч а н и е 2. Распространенным является представление о том, что по величине определителя матрицы А можно судить о степени близости системы уравнений к вырожденной или об обусловленности системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
