Бабенко - Основы численного анализа (947491), страница 98
Текст из файла (страница 98)
нужно знать ее обратную матрицу. Некоторый выход из поло- жения находят в том, что производится так называемое рривновсп1ива- ние мпшриц по строкам нли по столбцам, когда с помощью умножения матрицы на диагональную добиваются, чтобы нормы строк (столбцов) стали примерно одинаковыми; например, в норме ~ . ~ требуют, чтобы 6 < п1вх а, ) < 1, где б — основание системы с плавающей запятой. 1йь<ь В таком случае матрица называется равновесной пс строкаск Если ана- логичное неравенство выполняется по столбцам, то матрица называется равновесной по столбиа и, а если она равновесна по строкам и столбцам, то она называется равновесной. Заметим, что единой равновесной фор- мы матрицы не существует, в чем убеждают нас простейшие примеры.
Неудачное уравновешивание может сильно изменить число обусловлен- ности и прямой ход исключения, Например, если матрица Л имеет вид 477 'Э 3. Игперогеиоггггое уточнение реигения в то время как при уравновешивании по строкам получим матрицу - а1,п- 1 а1п а„„1 е Шеы С= Ва ап1 Сап 1„1 ап 11 а„п если ДлЯ элементов агн выполнены УсловиЯ Ь"'1 < ~агэ~ < 1. Этот пРИ- мер показывает, что для процедуры масштабирования вряд ли можно найти универсальный алгоритм.
Однако в существующих стандартных программах решения систем линейных уравнений процедура масштабирования строк широко применяется. 2. Линейные системы с плохо обусловленными матрицами. При решении таких систем решение получается со значительными погрешностями из-за накопления погрешностей округления.
Если х - — вектор, полученный в результате решения на ЭВМ системы (2.1), то, поло- жив найдем, что вектор т, называемый вектором невязки, вовсе не равен нулю при условии, что он «вычислен точно». Последнее выражение означает следующее: мы имеем машинное представление матрицы А и векторов х, Ь и, рассматривая затем элементы матриць1 и векторов как величины В системе с ДВОЙНОЙ тОчнОстью, Вычисляем неВязку' т, использу51 арифметику двойной точности. Таким обраэомг получим истинное представление о величине невязки. Если х точное решение системы (2.1), то Ь = Ах, и из (1) следует. что х — х=-А 'т. '1г = — ~~' егпо:1+ Ьо. = — ~амхобоэ откуда г, <ВА .~х(, (2) Но для плохо обусловленных матриц, несмотря на, леалость невязкиг мы можем получить, что векторы х и х значительно отличаются друг от друга. Вот поэтому и возникает потребность в уточнении приближенного решения, полученного методом Гаусса.
Как это делается, мы увидим ниже, а сейчас рассмотрим вопрос о возможных значениях невяэки. Минимальеюе значение нормы вектора невяэки, возможно, получается при подстановке в уравнение (1) округленных значений точного решения, Пусть х = (х1,, х„)' точное решение системы (1)г х, = 1, 2, ..., п,) машинное представление компонент вектора х. Тогда, принимая во внимание разъяснения, сделанные в ~ 2 гл. 1, имеем х = Х (1+ б ), Гдс до~ < = = Ь1 15г2; НаПОМНИМ, Чта 6 —. ОСНОВапнс СИСТЕМЫ счисления, а 1 число разрядов.
Тогда 478 Глава 3, Теория игиераций и методы решения некотории задач Выше мы получили разложение (2.20); если это необходимо, будем считать, что оно имеет место для матрицы с переставленньпш строками. Запишем это разложение в виде А =. ХП, где Х нижняя треугольная матрица, а П верхняя. Последняя формула справедлива в предположении, что матрицы Ь и П вычислены точно. Если 1.
и У получены в процессе прямого хода, то ясно, что 077 = А+ 6", где е матрица, возникающая из-за погрепшостей округления. Система (2.1) заменяется уравнением ЕПх =- Ь., которое можно записать в виде двух уравнений Лу=Ь., бек=у с треугольными матрицами. Рассмотрим, как влияют погрешности округления на решения этих уравнеяий. Пусть х. у решеяия последних уравнений, полученных на ЭВМ, т.е. ТалУ=Ь, П; х=1э, где символ,д означает, что матрица применяется к вектору, но все операции осуществляются в системе с плавающей запятой (см. з 2 гл. 1).
Предложение 1. Пусть х —. решение второго уравнения (3'). Тогда (У + бУ)х = у, где бУ вЂ” верхняя треугольная матрииа, для элеменягов которой бие: имеют место оценки био/ < 'ац ~!(у+ 1 — 1)(1+ Ь), у = э+ 1, г+ 2, ..., п, !бии/ < 'а„'" !2(1+6)». 1= п — 1, и,— 2, ..., 1, бп „~ < 'а~"„~1!(1- 6) г. Доказательство. Решение второго уравнения (о') производится по формулам (2.18), в которых нужно пололеить г = п и все арифметические операции заменить соответствующими операциями ЭВМ.
Таким образом, Х, = 'ба,,'„"' Сч Хи 3 Ет, „~ СО Х„1 З... ОЗ а,л Э Э Хе, Э йс уе1 бб азе Применяя формулу (1.2.14) к сумме в скобках. за исключением послед( — П него слагаемого, а затем прибавляя у„и деля на а„, получим (е — П 1е — П хо(1 + ее) а*~ — зги — 1(1 ьи — 1) ... — а~е 1хе гэ (1 + е, еэз) + у,| (а~;'<4 (1 + б) (1 -Ь б)1 где »ьь г =В,л ~(п+1 — з — 1)(1+6)г, !В,л, ~, '<1, ! —..01,...,п — г — 1, ~б!<г, ,'б!< . (4) 479 53. Итераггиоггггое гугточнеггие решения Отметим, что первый сомножитель 1+ б получен за счет прибавления у„ а второй 1-Ь б' за счет деления на а~; ~.
Отсюда а,' (1 — 'е,)к —.у,, э.—...п — 1,п — 2,...,1, (5) ег„= (1+ б)(1+б') .-1 =-2(1 ' Н)В„ге. Кроме того,:заметим, что ла = уь З а„„=. (у„гга 1(1 л б ), ги-гг г го — ггг а и, следовахельно, а „х„(1+с„н) =.. у„, где 億— -- Вп„(1+5) (множитель гп — 11 1 Ь мы добавили для единообразия). Таким образом, вектор к является точным решением системы с треугольной матрицей: (ЬГ+бЦ к = у., где биг — элементы матрицы б!Г имеют вид би,.
= а,.' ~ и (г = г, б — 11 г+ 1, ..., .пч г =- и, п — 1,..., 1). Используя соотношения (4), (5), получим неравенства для элементов матрицы б!Г, П Предложение 2. Г!усть у -- реигение первого уравнен я (3). 7огда у является решением уравнения (! + бй) у = Ь, где б!..— ниэюнзя треугольная матрица, для элементов которой о1о имеют место оцен~б( -'- гу' < (г+ 1 — г)(1+ Б)е, г = 1, 2, .... й (6) Доказлтнльство. Оно анагюгично доказательству предложения 1.
Прежде матрица Г, обозначалась через ЛХ"; структура матрицы ЛХ была установлена в ~ 2, и мы показали, что ее элемент в позиции (г, у) равен тьо если 1 < у < г, причем тн — -- 1. Поэтому уз — Ьг сб гпгг с' уг '- гггг2 ':-' уз с' ° ° гз тгл — 1 ~' уз- г . Применяя к последним ь — 1 слагаемым формулу (1г2.14) и делая очевидные преобразования, получим, что б1, = и, -,, г = 1, 2, ..., г, где е, = В, (г — 1 — Я(1+ й) . Учитывая, что тор < 1, получим неравенства (6), сз Аналогичные, но несколько более громозлкие рассуждения (которые мы не будем приводить) позволяют доказать следующее Предложение 3 [110).
Пусть матрицы Е, (Г вычислены методом исключения с выбором главного элемента в системе с гглавающей занятой. Тогда Лбг = Л+ 8, где б* = (е, ) — матрица, возникающая в результате округления. Для элементов этой матрицы имеют лгесто оценки (7) ,'еггч < нешгг где и = гпах~аг' ~; аг, = 27' — 1, если 1 < у < г — 1; ог,, = 2(г — 1), если г<7<п. 480 Глава д, Теория итераций и методы решетом иекоторыт задач Незавершенность оценки состоит в том, что она содержит неизвестную величину зе = шах~оно(. Различного рода оценки, полученные для этой величины, довольно грубы, и не следует ими пользоваться. С другой стороны, прн решении задачи на, ЭВМ мы всегда сможем определить константу м, и, следовательно, мохгно произвести апостериорный анализ точности решения.
Парадокс состоит в том, что оценки величин ~а~ О дают верхнюю гранину, быстро растущую с и, а в то же время для плохо обусловленных матриц величины 'а, ', скорее всего будут малы, если 1 = п, т .= н, Мы в опенке (7) оставим величину зе в надежде, что появятся хорошие правильные по порядку оценки величин ~а, Применим полученные резулыаты к численному решению системы (2.1). Это решение получается с помощью системы (3). Поэтому (Н бН)т =- у, (Š— бб)у = Ь, (Т,) < ~,,17( < нзе,;бЦ < (1+6)е[ +2~я, еп(п+ 1) (бб( < (1 — , '6)е., !б'~, < зеп п(н -' 1) 2 Поэтому бА! .
< зе(1+ 6)фР—, п(п(в+ 1) + 2)1+ )бб~~, ~бО~ 61ы ограничимся рассмотрением системы, порядок которых и» 1 удо- влетворяет неравенству п-.2 (146) [п(н — 1)-41 <4 и+! (8) Учитывая последнее неравенство, окончательно получим бА < м(1 6) е (нз + Зпт). Дадим применение полученных результатов к вопросу об итерационном уточнении реопения системы (2.1). Прежде всего отметим, что е = бАш, и поэтому г~, < н(146)е(аз+За ) т„. (10) Заметим,что 6 некоторая малая константа, которая определяется из неравенства пв < 26(1 —,6) (см.
предложение 2 з 2 гл. 1). Учитывая условие (8), наложенное на и, мы можем положить 6 = 0,01. Е<ши зеДА не откуда (б+ бЦ(17+ бе7)т = Ь. Раскрывая скобки и учитывая предложение 3, получим (Л+ бА)л = Ь, где бЛ = бр+ (бТ)17+ б(ббг) + (бТ)(бс1). Подчеркнем, что матрица бА зависит от вектора Ь, но оценка ее нормы зависит лишь от матрицы А. Заметим, что имеют место очевидные неравенства йз. Итероггиог*ггое утаочнение решения очень велико, то поучительно сравнить оценки (2) и (10). Нужно учесть, что невязка в формуле (2) возникла в результате округления точного решения. Поэтому представляется, что оценка (10) не очень груба. Опипкм, как производится итерационное уточнение.
Пусть л~ приближенное решение, пазученное из уравнений (3'). Определим повязку т' — -- — Аи' + Ь, используя арифметику двойной точности. Обозначим через с решение 1 системы (3') при условии, что Ь = г~. В результате получим новое приближенное значение решения в,т + сот Далее все вычисления повторяются, и мы получим итерационный про- цесс; таким образом, гв'=и .р~' . т" = — Аяо+Ь, АЯЬ йй~'=г, и' '=и +~', и=1,2, Совершенно ясно, что этот процесс сходиться не может, так как и векторы, компоненты которых принадлежат системе чисел с шгввающей запятой. Кроме того, .с некоторого момента начнут сквзыватыя погрешности округления при вычислении невязки г'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
