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

+ сах) + ... + с, х =у,„ а(')х + ... + а(1)х(+ ... +а(1)х =ф, а„„х,+... +а (х;+ ... +а х (1) (1) (1) Н1) Здесь обозначено а(( =ау — сиа(„(( =?( — у,а(„(, /=2, 3, „т. (5) (1) Нв Матрица системы (5) имеет вид (1! (1) о а ... а Матрицы такой структуры принято обозначать так аде крестиками обозначены ненулевые элементы. В системе (5) неизвестное х, содержится только в первом уравнении, поэтому в дальнейшем достаточно иметь дело с укороченной системой уравнений а„ха+ ... + амх(+ ... +а, х (1) (1) (1) с(1) (л а,х+ ...

+а (х+ ... +а„х„=? (1) (О (1) (О Тем самым мы осуществили первый шаг метода Гаусса. Если .а(",) ~ О, то из системы (?) совершенно аналогично можно исключить неизвестное х, и прийти к системе, эквивалентной (2) и имеющей матрицу следующей структуры: ( х х ... х о ) х ... х о о х ... х о о х ... х При этом первое уравнение системы (5) остается без изменения. ва Исключая таким же образом неизвестные х„х„..., х, придем окончательно к системе уравнений вида х1 + с]»х» + ... + с)щхь1 — У1~ х,+ ... +с, х„=у„ (8) х,+с,, х =у и =у, эквивалентной исходной системе (2). Матрица этой системы 1 с]» ...

с, с, О 1 ... с, , с, (9) О О ... 1 с 1 содержит нули всюду ниже главной диагонали. Матрицы таког(ь вида называются верхними треугольными матрицами. Нижней треугольной называется такая матрица, у которой равны нулю все. элементы, расположенные выше главной диагонали.

Получение системы (8) составляет прямой ход 'метода Гаусса. Обратный ход заключается в нахождении неизвестных х„х„..., х„ из системы (8). Поскольку матрица системы имеет треугольный вид, можно последовательно, начиная с х„, найти все неизвестные. Действительно, х„=у„, х,=у„,— с, х„и т. д. Общие формульп обратного хода имеют вид х(=у( — ',Р сухь 1=а] — 1, ..., 1, х .=у . (10) /=1М 2. Расчетные формулы.

При реализации на ЭВМ прямого хода метода Гаусса нет необходимости действовать с переменными х„х„..., х„. Достаточно указать алгоритм, согласно которому исходная матрица А преобразуется к треугольному виду (9), и указать соответствующее преобразование правых частей системы. Получим эти общие формулы. Пусть осуществлены первые й — 1 шагов, т. е. уже исключены переменные х„х„..., х„,. Тогда имеем систему х, +с]»х,+ ... +сых»+ ... +с, х =у„ х, + ... + с»]х»+ ... +с, х =у„ х», + сь 1,»х»+ ... + с»,,.х = у» „ (1 1) а»» х» + ... + а» х = 1» (»-1) (»-1) (»-1] а» х»+ ...

+а их„=Г(„ (»-1) (»-1]»-1] Рассмотрим й-е уравнение этой системы а»» х»+ ... +а» х а-0 (с о (»-)) (»-о а»( см =,—, а»» с(» 1) (» "'=:,) . а»»" 1=й+1, й+2, ..., т, Далее, умножим уравнение (12) на а(" > н вычтем полученное соотношение нз (-го уравнения системы (11), где >=й+1, й+2, ..., т. )В результате последняя группа уравнений системы (11) примет вид Х» + С»л+»Х»»( + ... + С»тХт = Р»~ (») , , (М ,(») а»+ь»+,х»+( т .

+ а»„,„х„= ('»»(, (») (») Н») а»„х»+,+ ... +а х =(', где а(",>=а('-') — аа»-ос»п 1, 1'=й+ 1, й+ 2, ..., т, Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по следующему правилу: а('>=а»;, й,1=1, 2, ..., т, а( с»(= "(, 1=й+1, й+2, ...,т, й=1,2, ...,(и, (13) а»» (»-1) а("> = а('-') — а(' ос»( (> и м м >, 1=й+1, й+2, ..., т, й=1, 2, ..., т — 1. (14) Вычисление правых частей системы (8) осуществляется по фор- мулам 1» ') 1»е=1», у»= », й=1, 2, ..., т, (»-1) а»» Г( =1(( — а(» У», 1=й+1, й+2, ..., т.

(1б) (1б) Коэффициенты са и правые части уа 1=1, 2,..., т, 1=1+1, 1+2, зз и предположим, что а(»»» о-йО. Поделив обе части этого уравнения на а»(ь»'>, получим Х»+ С»»+~Х»+(+ ... + С»тхт =ум (12) где ..., и1, хранятся в памяти ЭВМ и используются при осуществлении обратного хода по формулам (10). Основным ограничением метода является предположение о вт) том, что все элементы аы, на которые проводится деление, отличны от нуля.

Число а~~~о называется ведущим элементом на й-м шаге исключения. Даже если какой-то ведущий элемент не равен нулю, а просто близок к нему, в процессе вычислений может происходить сильное накопление погрешностей. Выход из этой ситуации состоит в том, что в качестве ведущего элемента выбирается не аГ! ", а другое число (т. е. на й-м шаге исключается не х„ а другое переменное хь (ФФ). Наиболее последовательно такая стратегия выбора ведущих элементов осуществлена в методе Гаусса с выбором главного элемента (см.

$3). 3. Подсчет числа действий. Подсчитаем число арифметических действий, необходимых для решения системы (2) с помощью метода Гаусса. Поскольку выполнение операций умножения и деления на ЭВМ требует гораздо больше времени, чем выполнение сложения и вычитания, ограничимся подсчетом числа умножений и делений. Читатель по аналогии может самостоятельно найти требуемое число действий сложения и вычитания. 1. Вычисление коэффициентов см, 1=1, 2, ..., т, (=й+1, й+2, ..., т, по формулам (13) требует т '~ (гл — я)=1+2+ ... +(т — 1) = 2 а т делений.

2. Вычисление всех коэффициентов аи) по формулам (14) требует т 1 ,~ е э+ 2а+ + э (т — 1) т(2т — 1) 6 «=ь умножений. Таким образом, вычисление ненулевых элементов сч треугольной матрицы С требует т (т — 1) (т — 1) т (2т — 1) (иР— 1) т 2 6 3 операций умножения и деления. При больших л! это число действий равно приблизительно лг'/3. 3. Вычисление правых частей у, по формулам (15) требует и делений, а нахождение )!и) по формулам (16) т (т — 1) а=1 2 63 умножений.

Следовательно, вычисление правых частей преобразованной системы (8) требует т(т — 1) а(а+ Ц (н+ 2 2 действий умножения и деления. В итоге для осуществления прямого хода метода Гаусса необходимо выполнить (тп — 0 т т (т+ 1) и (т+ 1) (2т -1- 1) 3 2 6 действий, из которых основное число действий (порядка т'/3) приходится на вычисление элементов матрицы С.

4. Для осуществления обратного хода метода Гаусса по формулам (10) требуется т-1 ~~~~ (л! — () = 2 8=1 умножений. Итак, для реализации метода Гаусса требуется выполнить и (т+!) (2а+ 1) т (т — !) а (тп-)- За — 1) б 2 3 действий умножения и деления. Подчеркнем, что основное время расчета затрачивается на осуществление прямого хода. Д л я больших гп число действий умножения и деления в методе Гаусса близко к тз/3.

Это означает, что на вычисление одного неизвестного тратится в среднем гп'/3 действий. По затратам времени и необходимой машинной памяти метод Гаусса пригоден для решения систем уравнений (2) общего вида с числом неизвестных т порядка 100. 2 2. Условия применимости метода Гаусса 1. Связь метода Гаусса с разложением матрицы на множители. В предыдущем параграфе было показано, что метод Гаусса преобразует исходную систему уравнений Ах=/ (1) в эквивалентную систему Сх= у, (2) где С в верхняя треугольная матрица с единицами на главной диагонали.

Выясним теперь, как связаны между собой векторы правых частей / и у. Для этого обратимся к формулам (16) из $1, из которых последовательно получим /~=пну„ /,=аау,+а(',!уа ... и вообще /!=ЬпУ,+ЬвУ,'+... +Ь„Уь /=1, 2, ..., лз, (3) И где йн — числовые коэффициенты, причем йя — — аит'>. Соотношения (3) можно записать в матричном виде Г=Ву, (4) где  — нижняя треугольная матрица с элементами а~'-и, =1, 2, ..., гп, (а<',~=ам) на главной диагонали.

Напомним, что основное допущение при формулировке метода Гаусса состояло в том, что все ац-я~О. Поэтому на диагонали матрицы В стоят ненуле- В вые элементы, и, следовательно, матрица В имеет обратную. Подставляя в уравнение (2) выражение для у в виде у=В 7, приходим к уравнению Сх= В-'Г, или, что то же самое, к уравнению ВСх=Г. Сопоставляя (5) с уравнением (1), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы А в произведение А=ВС, где  — нижняя треугольная матрица с ненулевыми элементами на главной диагонали и С вЂ” верхняя треугольная матрица с единичной главной диагональю. Теперь мы имеем право трактовать метод Гаусса следующим образом. Пусть заданы матрицы А и вектор Г, Сначала проводится разложение А в произведение двух треугольных матриц, А=ВС.

Затем последовательно решаются две системы уравнений Ву=Г, (6) Сх=у (7) с треугольными матрицами, откуда и находится искомый вектор х. Разложение А=ВС соответствует прямому ходу метода Гаусса, а решение системы (6) — (7) — обратному ходу. Заметим, что в алгоритме, изложенном в 2 1, разложение А=ВС и решение системы (6) проводится одновременно. Далее, следуя стандартным обозначениям, нижние треугольные матрицы будем обозначать буквой Ь (от английского!ожег — нижний) и верхние треугольные — буквой У (от английского пррег— верхний). 2. Теорема об Ш-разложении.

Обозначим через Л> угловой минор порядка 1 матрицы А, т. е. Л,=ам, Л,=де(~ " м~, ..., Л =бе(А. Гав а„1 ии ивь Теоретическое обоснование возможности разложения матрицы в произведение двух треугольных матриц содержит следующая Теорема 1 (теорема об Ш-разложении). Пусть есе угловые миноры матрицы А отличны от нуля, Л~чьб, 1=1, 2, ..., т.