Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 11
Текст из файла (страница 11)
+а,,„х„, =1„ (2) а~1х1 + атрх2 + ° ° + аглтхт = ),л. Метод Гаусса решения системы (2) состоит в последовательном исключении неизвестных х„х„..., х„нз этой системы. Предположим, что а„~О. Поделив первое уравнение на аэь получим х,+с„х,+" +с, х =у„ (3) где а~ с„= —, 1=2,, т, а„ у1 = ац лое число е>0 (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка !',х'"' — х!!(а. (2) Число итераций а=а(е), которое необходимо провести для получения заданной точности е (т. е, для выполнения оценки (2)), для многих методов можно найти нз теоретических рассмотрений.
Качество различных итерационных процессов можно сравнивать по необходимому числу итераций п(е). К решению систем линейных алгебраических уравнений сводится подавляюшее большинство задач вычислительной математики. В настояшее время предложено колоссальное количество алгоритмов решения задач линейной алгебры (см. (8, 35)), большинство из которых рассчитано на матрицы А специального вида (трехднагональные, симметричные, ленточные, большие разреженные матрицы).
Прямые методы, которые рассматриваются в гл. 1, не предполагают, что матрица А имеет какой-либо специальный вид. На практике они применяются для матриц умеренного порядка (порядка ста). Итерационные методы, рассмотренные в гл. 2, можно применять и для матриц высокого порядка, однако их сходимость ие очень быстрая. Более совершенные прямые н итерационные методы, учитывающие структуру матрицы, излагаются в части И| Рассмотрим теперь оставшиеся уравнения системы (2): а1,х, + а„х, +... + а,„х =(„1'= 2, 3,..., т.
(4) Умножнм (3) на а„ и вычтем полученное уравнение из (чго уравнения системы (4), 1=2, ..., т. В результате получим следующую систему уравнений: Х1+ С(1Х1+ ... + С)(Х(+ ... + С)с1хс1 =Д), а(1)х + ... +а(чх;+ ... + а(')х =ф), (5) а,х,+ ... +а,„;х;+ ... +а х„=)„,. и) (1) (о ш :Здесь обозначено (1) с~)! а(( =ап — С„а 1, (( =(1( — у~а„, (,!'=2, 3, ..., ГЛ, (6) Матрица системы (5) имеет вид ! С,с ... С, (1) (О О с ... с„, (1) (11 О а ... а Матрицы такой структуры принято обозначать так где крестиками обозначены ненулевые элементы.
В системе (5) неизвестное х, содержится только в первом уравнении, поэтому в дальнейшем достаточно иметь дело с укороченной системой уравнений (1) (1) (1) И1) а„х, + ... + а„х;+ ... + а, х О! О) О) 10) а,х,+ ... +а„;х)+ ... +а„„,х,„=!' Тем самым мы осуществили первый шаг метода Гаусса. Если ,а(',) ~ О, то из системы (7) совершенно аналогично можно исключить неизвестное х, и прийти к системе, эквивалентной (2) и имеющей матрицу следующей структуры: ! х х о ! х ...
х О О Х ... Х О О х ... х 'При этом первое уравнение системы (5) остается без изменения. ВО Исключая таким же образом неизвестные х„х,, ..., х, придем окончательно к системе уравнений вида х, + с)»х»+ ... + с, х =у„ х,+ ... +с,„,х,„=у„ (8) х,+с,, х =ум„ хь=улн эквивалентной исходной системе (2). Матрица этой системы 1 с»» ~,~п-~ ~ил О 1 ... с , с (9) о о ... ) с о о ... о 2. Расчетные формулы.
При реализации на ЭВМ прямого хода метода Гаусса нет необходимости действовать с переменными х„х,, ..., х . Достаточно указать алгоритм, согласно которому исходная матрица А преобразуется к треугольному виду (9), и указать соответствующее преобразование правых частей системы. Получим эти общие формулы. Пусть осуществлены первые й — 1 шагов, т. е.
уже исключены переменные х„х,, ..., х„,. Тогда имеем систему х) +с„х, + ... +с,»х»+ ... + с,„,х„, =у„ х» + ... + смх» + ... + С»гихл ум х),+с»,»х»+ , . + с» ь х =у» „ (! !) )»-и (»-и ... + а» х., = !» а»» х» + )»-1) )»-и (»-1) и»-») ат» х»+ .. ° + ат и хщ =/м в) содержит нули всюду ниже главной диагонали. Матрицы такого вида называются верхними треугольными матрицами.
Нижней треугольной называется такая матрица, у которой равны нулю все элементы, расположенные выше главной диагонали. Получение системы (8) составляет прямой ход метода Гаусса. Обратнь)й ход заключается в нахождении неизвестных х„х„..., х„, из системы (8). Поскольку матрица системы имеет треугольный вид, можно последовательно, начиная с х, найти все неизвестные. Действительно, х =у, х„, =у,— с, х„и т.
д. Общие формул»и обратного хода имеют вид ~и х;=у; — '~" сихь (=и) — ), „1, х .=у„. (1О) )'=) ь1 Рассмотрим й-е уравнение этой системы >»-н >» — и >»-и а»» х»+ ... +а»,. х„=)» а'» "> »> с»! = —, и-О ' а»» с>»-о !» У» = —— а»»" 1=я+1, й+2, ..., и>, Далее, умножим уравнение (!2) на а',." '> и вычтем полученное соотношение из 1-го уравнения системы (11), где >=й+1, й+2,..., >и. В результате последняя группа уравнений системы (1!) примет вид х»+ с»,»»х»>.>+ ... +с» х„=у», >»> ~ >»> им а»„,»„хы,+ ... + а»>о х >»> ~ > >»> и»> а,„,>„,х»„+ ..., а„„„х,.=>' а>»>=а!»ла> — а!" '>с»> >, у=й+1, й+ 2, ..., и>, !'>и = )>' " — а'„» оу», 1=й+1, й+ 2, ..., и>.
Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по следующему правилу: пи> а»! й ! 1 2 и> с»>= —, !'=й+ 1, й+2,, и>, й=1,2, ..., и>, (13) (» — и а»> а!',> = ай-о — а>»-пс». »» 1»»и >, ! = й+ 1, й+ 2, ..., т, а = 1, 2, ..., и> — 1. (14) Вычисление правых частей системы (8) осуществляется по фор- мулам .>» — о !»~=! У = —, й=1,2, ..., т, и-и а»» >'! = 6 "— а!» оУм >'=й+1, й+2, ..., и>. (15) Коэффициенты си и пРавые части Уь 1=1, 2,..., и>, 1=>+1, >+2, 62 и предположим, что а»>» о4=0. Поделив обе части этого уравнения на о>»»-'>, получим х,+с»»>-,хм~>+ ° ..
+си и =Ум (12) где ..., 1н, хранятся в памяти ЭВМ и используются при осуществлении обратного хода по формулам (10). Основным ограничением метода является предположение о том, что все элементы аьч, на которые проводится деление, отв-и личны от пуля. Число ай ') называется ведущи.а элементом на Й-м шаге исключения. Даже если какой-то ведущий элемент не равен нулю, а просто близок к нему, в процессе вычислений может происходить сильное накопление погрешностей.
Выход из этой ситуации состоит в том, что в качестве ведущего элемента выбирается не в-о ам, а другое число (т. е. на Й-м шаге исключается не х„а другое переменное хь (~Й). Наиболее последовательно такая стратегия выбора ведущих элементов осуществлена в методе Гаусса с выбором главного элемента (см. 2 3). 3.
Подсчет числа действий. Подсчитаем число арифметических действий, необходимых для решения системы (2) с помощью метода Гаусса. Поскольку выполнение операций умножения и деления на ЭВМ требует гораздо больше времени, чем выполнение сложения н вычитания, ограничимся подсчетом числа умножений и делений. Читатель по аналогии может самостоятельно найти требуемое число действий сложения и вычитания. 1. Вычисление коэффициентов сн, Й=1, 2, ..., т, (=Й+1, Й+2,..., т, по формулам (13) требует ~~ (т — Й) = 1+ 2+ ... + (т — 1) =— 2 «=г делений. 2. Вычисление всех коэффициентов а5) по формулам (14) требует О3-1 (т — Й)' = 1' + 2' + ...
+ (т — 1)' = 6 я=1 умножений. Таким образом, вычисление ненулевых элементов с» треугольной матрицы С требует (пп — 1) м т (и — 1) (т — 1) т (2т — 1) + 6 3 операций умножения и деления. При больших т это число действий равно приблизительно т'/3. 3. Вычисление правых частей д, по формулам (15) требует т делений, а нахождение ((тн по формулам (16) Х( — Й)=' " 2 х=г 53 умножений. Следовательно, вычисление правых частей преобразованной системы (8) требует аз+ т(ж — 1) м (е+ 1) й 2 2 действий умножения и деления.
В итоге для осуществления прямого хода метода Гаусса необходимо выполнить (ин — 1) и и (ж+ 1) ж (м+ 1) (2ч!+ 1) 3 2 6 действий, нз которых основное число действий (порядка т'13) приходится на вычисление элементов матрицы С. 4. Для осуществления обратного хода метода Гаусса по формулам (10) требуется Л1-1 '~~~ (!и — () = 2 умножений. Итак, для реализации метода Гаусса требуется выполнить т (т+ 1) (2т+ 1) т (т — !) т (т'+ Зж — 1) б 2 3 действий умножения и деления.
Подчеркнем, что основное время расчета затрачивается на осуществление прямого хода. Д л я больших т число действий умножения и деления в м ет од е Гаусса близко к т')3. Это означает, что на вычисление одного неизвестного тратится в среднем гп'/3 действий. По затратам времени н необходимой машинной памяти метод Гаусса пригоден для решения систем уравнений (2) общего вида с числом неизвестных и! порядка 100. й 2. Условии применимости метода Гаусса 1, Связь метода Гаусса с разложением матрицы иа множители. В предыдущем параграфе было показано, что метод Гаусса преобразует исходную систему уравнений А.=1 (1) в эквивалентную систему Сх=у, (2) где С вЂ” верхняя треугольная матрица с единицами на главной диагонали.
Выясним теперь, как связаны между собой векторы правых частей 1' и у. Для этого обратимся к формулаМ (16) из $1, из которых последовательно получим (г = '!нУ! )з = !!и У! + Ц",'Ум ° ° ° н вообще 15 Ь у+Ь уг+ ° ° ° +Ь у, (3) 1=1,2, ..., пт, где бн — числовые коэффициенты, причем би —— асстсс.
Соотношения (3) можно записать в матричном виде )=Ву, (4) где  — нижняя треугольная матрица с элементами ас.';то, 1= =1, 2, ..., т, (ас',с=а„) на главной диагонали. Напомним, что основное допущение при формулировке метода Гаусса состояло в том, что все асстсс ~ О. Поэтому на диагонали матрицы В стоят ненулесс вые элементы, и, следовательно, матрица В имеет обратную. Подставляя в уравнение (2) выражение для у в виде у=В-'7, приходим к уравнению Сх= В-'7, или, что то же самое, к уравнению ВСх =1. (6) Сопоставляя (5) с уравнением (1), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы А в произведение А=ВС, где  — нижняя треугольная матрица с ненулевыми элементами на главной диагонали и С вЂ” верхняя треугольная матрица с единичной главной диагональю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
