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