Самарский А.А., Гулин А.В. Численные методы (1989), страница 14

К=б!аи ((п, (м, ..., 1 (3) По условию диагональные элементы матрицы 1. отличны от нуля, и, следова. тельно, разложение 1.=МК существует. Тогда А=МКУ, (4) где М и У вЂ” треугольные матрицы с единичной главной диагональю и К вЂ” диагональная матрица, имеющая обратную. Из условия А*=А получаем У'К'М'= -мки и К- М- У*К*=УМ*- . (5) Матрица, находящаяся в левой части равенства (5), является нижней треугольной, а в правой части — верхней треугольной. Поэтому из равенства (5) следует, что обе матрицы Ум'-' и К-'М вЂ” У*К* являются диагональными. Далее, поскольку матрица УМ'-' имеет единичную главную диагональ, она является единичной матрнцей, УМ -'=Е, т. е. У=м'. Отсюда и из (4) получаем разложение А МКМ'. (6) Представим матрицу К, определенную согласно (3) в виде произведения трех диагональных матриц: К )к(гР)К1'ь, где обозначено 1 К !н = б!аа (Р'1 (м 1, )'! !аз !, " ' У'! 1..

!1, У=б!аи [з!ип(и, з!ип!и,..., з!ип1 ). Тогда из (6) получим разложение (2), где 5=(К(чм' — верхняя треугольная матрица с положительнымв элементами на главной диагонали. 2. Пример. Если разложение (2) получено, то решение системы (1) сводится к последовательному решению двух систем уравнений с треугольными матрицами 5'Ру (Т) 5х=у. (8) Покажем на примере матриц второго порядка как можно получить разложение (2). Пусть А †действительн симметричная матрица А= ~~м 70 Будем искать 5 и Р в виде 5=~'" "'~, где каждое из чисел А„дд„может 5Н 5.Р5 11 5д 1515ч д д '= 1.""'.,1 быть либо +1, либо — 1.

Тогда 511515"11 5" йдд + 5, 11551 и из условия (2) получаем три уравнения: 51',5111 — — адд, 5115155111 —— адд, 5115(11 + 5555(55 = пдд. Из первого уравнения находим А,=з)дн а„, з„= 1'~а„[. Далее, если а„чьО, то з„=а„/(эиА,), и, наконец, В.д В.д зддд55 = авг 51Фдд т.

е. дддд = з(Ягд(адд — 5155(11) зы = 1/ ~ адд — зддд(дд [ . 3. Общие расчетные формулы. Получим разложение (2) в случае эрмитовой матрицы А произвольного порядка т. Если 5= [здд) и Р=б(ад[ддд, ..., 51„), то элемент матрицы Р5, имеющий индексы (1,1), равен (Р5)дд = ч~ ~Адздд = д(ддзц. 1=1 Кроме того, 5*= [5„), поэтому (5'Р5)ц = '~~~~ 511415ддь 1=1 где 5„— число, комплексно сопряженное з„. Из условия (2) получаем уравнения 'Я зддАдздд=аддь д',1=1,2,...,пд. (9) д=д Так как матрица А эрмитова, можно, не ограничивая общности, считать, что в системе (9) выполняется неравенство 1(1. Перепишем (9) в виде 5-1 пд ,'Я зддздФдд+ 51151Фдд+ ~ч~ зддзддд(дд = ац 1=1 д=ды и заметим, что 5„=0 для 1)д'.

Таким образом, получим систему уравнений Д-д зддздддддд + ~~ здда!гА! — вид д ~~ 1. (1О) д=д 71 В частности, при с'=1 получаем с-с ~ асс ( с( = а; — 'Я ~ зсс ~~с(сс, с с т. е. с-с с = а~ (а; — 21исА). с с Сс 1И зи = аи — 'Я 1зсс )Чсс ) (12) Далее, при с(1 из (10) получим с-с асс — ~ ~с сссссссс с=с зсс = (13) ссссСсс с-с зи= $/ аи — ч', зй, з„= р'асс, 1=2,3,...,т, (14) асс=асс/асс, 1=2,3,...,т, исс ,~~ сссссс 1=2,3,...,т, 1=2,3, ...,1 — 1. (16) зц = 5сс Подсчитаем сначала число умножений. Вычисления по формуле (14) требуют 'Я (с — 1) = 2 умножений.

Вычисления по формуле (16) при каждом фиксированном 1' требуют Ц вЂ” 2) (с — 1) 2 с=в По формулам (11) — (13) находятся рекуррентно все ненулевые элементы матриц В и 5. 4. Подсчет числа действий. Метод квадратного корня применяется обычно к системам с положительно определенной эрмитовой матрицей А. В этом случае из (6) следует положительность диагональных элементов матрицы К, и тем самым 0=Е в разложении (2).

Если предположить дополнительно, что А — действительная матрица, то из (11) — (13) получим следующие расчетные формулы: умножений, а всего здесь требуется Ц вЂ” 2) (! — 1) 1 ~, й(й 1) и(т — 1) (т — 2) )=а 2 2 '-" 6 умножений. Следовательно, общее число умножений т (а — 1) т (и — 1) (а — 2) и (иР— 1) 2 6 6 Число делений, необходимых для вычислений по формулазэ (14) — (16), совпадает с числом надднагональных элементов матрн- цы 5 н равно т(т — 1)/2.

Таким образом, общее число действий умножения н деленна, не- обходнмое для факторизации А=5'5, и (и~ — 1) т (т — !) т (а — 1) (и+ 4) иР + 6 2 6 6 Прн больших т это число примерно в два раза меньше числа умножений н делений в прямом ходе метода Гаусса. Такое сокра- щенне числа действий объясняется тем, что А — симметричная матрица. Заметим, что данный метод требует т операций нзвлече- ння корня. Если матрица А факторнзована в виде А=5'5, то обратный ход метода квадратного корня состоит в последовательном реше- ннн двух систем уравнений 5'у=(, 5х=у. Решения этих систем находятся по рекуррентным формулам 4-1 г! — ~~", ~ПУ) у!= ~ ', (=2,3,...,и, 5к (17) У! = !'!)Зм| У1 Х '1)х) 1=1» (=т — 1,и — 2,...,1, зк (18) Ха = уи/Зии.

Вычисления по каждой нз формул (17), (18) требуют т деленнй н О,бт(т — 1) умножений. Следовательно, всего для обратного хода требуется т(т+1) операций умножения н деления. Всего метод квадратного корня прн факторизации А=5"5 требует +1) + т (а — 1) (а+ 4) т (и'+ 9т+ 2) 6 6 операций умножения н деления н т операций извлечения квадратного корня. та й 6. Обусловленность систем линейных алгебраических уравнений 1. Устойчивость системы линейных алгебраических уравнений. При использовании численных методов для решения тех или иных математических задач необходимо различать свойства самой задачи и свойства вычислительного алгоритма, предназначенного для ее решения. Для каждой математической задачи принято рассматривать вопрос о ее корректности. Говорят, что задача поставлена корректно, если ее решение существует и единственно и если оно непрерывно зависит от входных данных.

Последнее свойство называется также устойчивостью относительно входных данных. Сфор. мулированное здесь общее и не очень четкое определение корректности должно уточняться при переходе к изучению конкретных классов математических задач. Так, хорошо известны определения и методы исследования корректности задачи Коши для систем обыкновенных дифференциальных уравнений, корректная постановка типичных задач математической физики. Корректность исходной математической задачи еще не гарантирует хороших свойств численного метода ее решения. Поэтому для корректно поставленных задач свойства численных методов должны изучаться особо. Отметим, что часто возникает необходимость численного решения некорректно поставленных задач. Этот круг вопросов подробно освещен в книге [381.

В настоящем параграфе вопросы корректности исходной задачи и численных алгоритмов ее решения рассматриваются на примере системы линейных алгебраических уравнений Ах=) (1) с квадратной матрицей А порядка гп. Хорошо известно, что для каждого тп-мерного вектора 1 решение х задачи (1) существует тогда и только тогда, когда бе1АчьО. В этом случае можно определить матрицу А-', обратную матрице А, и записать решение в виде (2) Для того чтобы убедиться в корректности задачи (1), необходимо еще установить непрерывную зависимость решения от входных данных. В связи с этим возникает по крайней мере два вопроса.

Первый: что считать входными данными задачи (1), и второй: в каком смысле следует понимать непрерывную зависимость? Ответ на первый вопрос очевиден: входными данными являются правая часть 1 и элементы ач, 1, 1'=1, 2,..., тп, матрицы А. Соответственно различают устойчивость по правой части (когда возмущается только правая часть 1, а матрица А остается неизменной) и коэффициектную устойчивость (когда возмущается только матрица А, а правая часть 1 остается неизменной).

Чтобы можно было говорить о непрерывной зависимости, необходимо ввести на множестве т-мерных векторов ту или иную мет- рику. Будем считать, что решение и правая часть задачи (1) принадлежат линейному пространству Н, состоящему из гп-мерных векторов (вещественных или комплексных — безразлично). Введем в Н норму 11 11; конкретный вид этой нормы сейчас не имеет значения, важно лишь, чтобы выполнялись все аксиомы нормы: !1х!1)0 для любого О+кенН, 11011=0; 1!ах!! = !«с111х11 для любого числа а и любого х~Н; 11х+у11 < 11х11+ 1!у!1 для любых х, уе:-.Н. Нормой матрицы А, подчиненной данной норме вектора, называется число !!А~= зпр (3) «Р»мн !1Х1 Из определений следует, что 1!Ах!!<!!А!1!!к!! для всех кеН, 11А+ В!! < !!А 11+ 1!В!!, 11АВ11 < ПА!1 1!В!! для любых матриц А, В; 11Е11 = =1, где Š— единичная матрица.

Наряду с основной системой уравнений (1) рассмотрим «возмущенную систему» Ах=7, (4) которая отличается от (1) правой частью. Будем предполагать пока, что в матрицу А возмущений не вносится. Нас интересует, насколько сильно может измениться решение х в результате изменения правой части. Обозначим бх=х — х, 6~=~ — 1. Говорят, что система (!) устойчива по правой части, если при любых 1, у справедлива оценка И 11<М,И111, (б) где М,)0 — постоянная, не зависящая от правых частей 1, у.