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