Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 15
Текст из файла (страница 15)
Оценка (5) выражает факт непрерывной зависимости решения от правой части, т. е. показывает, что 1!бх11-»О при 116111-~0. Наличие устойчивости очень важно при численном решении систем уравнений, поскольку почти никогда нельзя задать правую часть ) точно, на самом деле вместо вектора 1 задается какой-то близкий ему вектор у. Погрешность 61=у †возникает, например, в результате погрешностей округления. Легко показать, что если бе(А чьО, то система (1) устойчива по правой части.
Действительно, из (1) и (4) следует уравнение для погрешности А (бх) =61', откуда получаем бх=А '(61), !!бх!1 < !1А-'!1116111, (6) т. е, выполняется неравенство (5) с константой М,= 11А '11. Заметим, что чем ближе к нулю определитель матрицы А, тем больше постоянная М, и, следовательно, тем сильнее погрешность правой части может исказить искомое решение. 2. Число обусловленности. В оценку (5) входят абсолюгньш полрешности решения бх=х — х и правой части б~=~' — ). При решении системы (!) на ЭВМ с плавающей запятой более естественными характеристиками являются относительные погрешности Ю Н !!бхН НУН Нх1 Получим оценку, выражающую относительную погрешность решения через относительную погрешность правой части. Для этого используем неравенство !ф!(!!А!!!!х!!, (7) которое следует из (1). Перемножив (6) и (7), придем к требуемой оценке 1бхН Нб7 Н ~~МА ю (8) НхН ЦН где М =!!А-'!!!!А!!, (9) Число М„, входящее в эту оценку, называется числом обусловленности матрицы А и характеризует степень зависимости относительной погрешности решения от относительной погрешности правой части.
Матрицы с большим числом обусловленности М называются плохо обусловлеппьини матрицами. При численном решении систем с плохо обусловленными матрицами возможно сильное накопление погрешностей. Отметим следующие свойства числа обусловленности: 1'. М >1. 2'. М ) /Л „(А) !/!Л, (А) !, где Л „(А) и Л „(А) — соответственно наибольшее и наименьшее по модулю собственные числа матрицы А. 3 ° М хв ~ ~МхМв. Докажем свойство 2'. Число р(А) = !Л (А) ! называется спектральным радиусом матрицы А. Покажем сначала, что для любой нормы вектора подчиненная ей норма матрицы удовлетворяет неравенству р(А) (!!А!!. (10) Рассмотрим собственный вектор у матрицы А, отвечающий наибольшему по модулю собственному значению.
Справедливо равенство Ау=Л „(А)у, из которого следует, что !!Ау!! = ! Л (А) ! !!у!!. С другой стороны, !!Ау!!(!!А!!!!у!!, и, следовательно, !Л (А) ! < '(.!!АНН, т. е. получаем (10). Поскольку Я„(А) является максимальным по модулю собственным значением матрицы А-', для него выполняется неравенство !Л...(А) !- ~!!А- !!. 76 Отсюда и из (10) следует свойство 2'. Заметим, что правая часть неравенства 2' не зависит от выбора нормы.
Существуют нормы и матрицы, для которых 2' выполняется со знаком равенства. Пусть Н вЂ” вещественное пространство со скалярным произведением (у, о) = р; у ог к-г и нормой Ну Н = у'(у, у) . Тогда н о р м а с и м м е т р и ч н о й м а т р ицы А совпадает с ее спектральным радиусом: НА)) =р(А). (11) Действительно, пусть (и»)», — ортонормироианный базис собственных векторов матрипы А и хшН вЂ” любой вектор. Разлагая х по базису (и»), ио. лучив т м х=т' с»1»», НхНз=~ч~~ ~с» » з »=г н, далее, Ах= Х с»Л р», НА Нз= Х схЛ». Отсюда имеем НАхН»~рз(А) Нхйз, т. е.
НАН(р(А). Сопоставляя зто неравенство с (1О), получаем (11). Точно так же ЦА-'Н=р(А-') = /Ъ „(А) ~ ', и, следовательно, М. =НЪ (А) ~ДЛмы(А) ~ (12) для симметричной матрицы А и среднеквадратичной нормы вектор, НкН=Ч((, х). Свойство 1' следует непосредственно из 2', а свойство 3' — из аналогичного свойства матричных норм, НА ВН ( НА Н 1) ВН. 3. Полная оценка относительной погрешности. Предположим теперь, что в системе (1) возмущены как правая часть, так и коэффициенты. Рассмотрим наряду с (1) возмущенную систему Ах=у (13) и обозначим бА =Х вЂ” А, бх=х — х, 61'=Т вЂ” 1. Справедлива следующая теорема (см. 161).
Теор е м а 1. Пусть матрица А имеет обратную и пусть выполнено условие НбАН<НА- Н-. (14) Тогда матрица Я=А+бА имеет обратную и справедлива следую1цая оценка относительной погрешности: Н бхН мл гН 6А1 НВ/ Нх (15) нх-, (НбА11 '1 1Ан нгн ) ~'1НАН/ При доказательстве будет использована Лемма 1.
Пусть С вЂ” квадратная матрица, удовлетворяющая условию !!С!!~1 и Š— единичная матрица. Тогда существует мат- рица (Е+С)-', причем Н(Е+С) 'Нс 1 — ! сН (16) Дока э а тельство. Дли любого вектора х имеем Н (Е+С) хН = Нх+СхН Р НхН вЂ” НСхН > НхН вЂ” НСН НхН (1 — НСН) НхН бНхН, где б 1 — НСН~О. Поэтому однородное уравнение (Е+С)х =0 имеет только нулевое решение: если (Е+С)х-О, то 0>ОНхН и х=о. Поэтому в неравенстне Н(Е+С)хН~ОНхН (17) можем обозначить (Е+С)х у, х=(Е+С)-'у и переписать (17) в виде Ну(вэ >61(Е+С)-'уН.
Отсюда получим 1 1 Н(е+с) уН~ Ну( ' с Ну( следовательно, выполнено (16). Д о к а з а т е л ь с т в о теоремы 1. Докажем, что существует мат- рица, обратная матрице А+6А. Имеем Х=А+6А=А(Е+А '6А) =А(Е+С), где С=А '6А. По условию (14) имеем !!С!(=!(А '6А!!(!!А '(!!!6А!((1, (18) поэтому согласно лемме 1 существует (Е+С) ', а следовательно, и Х-'. Нам осталось получить оценку (15). Представим бх=х — х в виде бх=Х '7" — А '1 =Х '(Т вЂ” 1)+(Х-' — А-')1.
Согласно (1) имеем 7=Ах, поэтому бх= (Х-'А — Е)х+Х '6~. (19) Дальнейшие выкладки связаны с оценками норм матриц Х-'А — Е и Х-'. Обозначим 6 = Х-'А — Е (20) Имеем Ь=Х 'А — Е=(А-(-6А) 'А — Е=(А(Е+А 6А)) 'А — Е =(Е+С) ' — Е, С=А '6А, Ь=(Е+С) '(Š— (Е+С)) = — (Е+С) 'С. По лемме 1 получим 1,|< В < И..ЛИ (21) ! — НСН 1 — НА 'Н(ОАН так как (!С!!(!(А-'!(!!6А (!. Далее, Х '= (А+6А) '=(А(Е+А-'6А) )-'= (Е+С)-'А-' и !!А-1 !! Н А-'Н 1 — НА 'ННОАН Возвращаясь к (19), получим $бх$( ЦА 'ЦЦЬАЦЦ Ц + ЦА 'ЦЦЬ(Ц 1 — ЦА 'ЦЦЬАЦ ! — ЦА ~ЦЦЬАЦ и х Ц Ц ЬА Ц + Ц ЬЯ. Сделаем преобразование /!Щ='— /!7Ц= — ~цЦАхЦ("— ~ц!$А3Ц/х/!. 111 И ЦЛ Тогда получим неравенство которое совпадает с (15).
Теорема 1 доказана. 4. Влияние погрешностей округления при решении систем линейных алгебраических уравнений методом Гаусса. Метод Гаусса относится к прямым методам решения, поэтому он должен был бы давать точное решение задачи (1) за конечное число действий. Однако при задании на ЭВМ исходной информации (матрицы А, правой части 1) неизбежно вносятся погрешности округления. Поэтому при проведении вычислений на ЭВМ точное решение почти никогда не достигается. Результирующая погрешность вычислений тем больше, чем выше порядок матрицы. Кроме того, точность вычислений зависит и от вида матрицы.
Например, велика погрешность при решении систем уравнений с определителем, близким к нулю. Не надо думать, однако, что накопление погрешностей округления делает непригодным метод Гаусса или другие численные методы. Ведь обычно требуется знать решение не абсолютно точно, а лишь с какой-то степенью точности. Важно, чтобы результирующая погрешность вычислений находилась в пределах заданной точности. Для этого необходимо проводить анализ влияния погрешностей округления на точность алгоритма. Поскольку полное проведение такого анализа весьма трудоемко и выходит за рамки данной книги, ограничимся лишь основными сведениями. Подробное изложение этого круга вопросов можно найти в книге [6]. Для большинства вычислительных алгоритмов влияние погрешностей округления можно учесть, рассматривая возмущенную систему (13).
Считают, что решение системы (1), искаженное погрешностями округления, совпадает с точным решением некоторой системы (13). Иначе говоря, процесс решения системы (1) с учетом погрешностей округления эквивалентен точному решению некоторой возмущенной системы (13). Предположим для простоты, что правая часть 1 задается точно. Пусть в результате погрешностей округления вместо точного ре- 79 щения системы (1) получено точное решение возмущенной системы Хх =).
(22) В этом случае матрица 6А=Л вЂ” А называется матрицей эквивалентных возмущений. Каждому вычислительному алгоритму отвечает своя матрица эквивалентных возмущений. Если известна оценка нормы матрицы 6А, то погрешность, возникшую в результате погрешностей округления, можно оценить согласно (15), а именно Ц х — кЦ МА ))6А1 ЦхЦ Ц6АЦ ЦАЦ л ЦАЦ (23) Отсюда видно, что на точность решения влияют два фактора: число обусловленности матрицы А и эквивалентное возмущение Ц6АЦ/ЦАЦ. Чем больше числа М и Ц6А!1ДАЦ, тем меньше точность решения.
Подчеркнем, что число обусловленности не связано с каким-либо численным алгоритмом, а характеризует только свойства исходной системы (1). Величина эквивалентного возмущения определяется численным алгоритмом. Тем самым при рассмотрении конкретных алгоритмов необходимо получать оценки соответствующих эквивалентных возмущений. Так, в результате факторизации А =АУ по методу Гаусса решение системы (! ) сводится к решению двух систем Ту=1, У =у АЦ =0(гл 2-с) !1АЦ где т — порядок матрицы. Таким образом, накопление погрешностей округления при решении систем линейных алгебраических уравнений методом Гаусса 80 с треугольными матрицами. Погрешности округления приводят к тому, что вместо решения х системы Ух=у получаем решение х возмущенной системы (7х=у.
Точно так же вместо решения у системы Ц.у=1 получаем решение у системы Ту=1. Таким образом, можно считать, что вместо исходной системы (1) точно решается возмущенная система Хх=г, где Л=П~. Чтобы найти матрицу Л, надо выписать все формулы метода Гаусса, внести в них погрешности округления и получить тем самым матрицы Е и б'. Далее следует оценить норму матрицы 6А=ЛУ вЂ” ЕС. Опуская все эти весьма трудоемкие выкладки, приведем лишь окончательный результат (см. (6]). Пусть (†число разрядов мантиссы в двоичном представлении чисел на ЭВМ с плавающей запятой, так что относительная погрешность округления действительного числа есть величина порядка 2-'.
Тогда для эквивалентного возмущения метода Гаусса верна оценка на ЭВМ с плавающей запятой приводит к тому, что искомое решение определяется с относительной погрешностью =О(/Ил пг 2 ). ЦхЦ (24) Отметим, что для машины БЭСМ-6 число 2 ' равно приблизительно 1О-". Рассмотрим пример применения оценки (24). Пусть методом конечных раз. ностей решается краевая задача и"(х) = — 7(х), 0(х(1, и(0) =и(1) =О. (25) Введем равномерную сетку юа (ха=/Ь, ! О, 1, ..., Ь/, ЬЬ/= Ц н заменам (25) разиостной схемой второго порядка точности иг, — 2иг+ иг Ьл г = 1, 2, ..., Ь/ — 1, иа = ии — — О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
