книги / Основы математического моделирования и численные методы

Л к -1)

т? 4 = -тЛЬк-г\)г i = k+ !»

акк

Коэффициенты на промежуточном к-м шаге будут выглядеть следующим образом:

г = к+ 1 ,..., n;j = к,

Индекс к = 1, п - 1, при к = п - 1 исключается (п - 1)-й эле­ мент.

Окончательно преобразованная треугольная система уравнений примет вид

Дц* 1 +al2x2+... +alnxn =fy;

а2гх2+..Ла'2пхп =Ъ'2\

а^п 1)х

пп п

Индексы i,j, к имеют следующий смысл: к - номер уравнения, которое вычитается из остальных (номер неизвестного, которое ис­ ключается из оставшихся (п - к) уравнений); / —номер уравнения, из которого в данный момент исключается неизвестное; j - номер столбца.

Для определения значений неизвестных выполняется обратная подстановка:

а:

А("-2) _Л"~2)х

XJ =

j - n - 2 .....1 .

4.4.2. Метод прогонки

Метод прогонки относится к прямым методам решения систем линейных алгебраических уравнений и является модификацией ме­ тода исключения Гаусса для частного случая разряженных систем. К таким системам принято причислять системы уравнений с трех­ диагональной матрицей. Эти системы зачастую применяются при решении широкого круга инженерных задач, в том числе и в техно­ логии кабельного производства. Особенное распространение такие системы получили при численном решении краевых задач в диффе­ ренциальной постановке.

Запишем систему уравнений в виде +С] * 2 =</,;

а2х1+ Ь2х2+ с2х3 —d2;

а3х2 + Ь3х3 +с3х4 = d3;

<

ап-1*и- 2 +Ьп-\Хп-1 +Сп-\Хп =4-15

апХп-\ "t" К х„ —dn.

В ней на главной диагонали матрицы расположены элементы Ъх,Ъ2,...,Ьп, над ней - элементы с,,с2 ,...,с„_1} под ней - а2,а3,...,ап.

При этом обычно bj ФО

bx Cj

üj b2 с2 аъ Ъг сг

Ьп

Рассматриваемый метод состоит из двух этапов - прямой про­ гонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратной прогонки метода Гаусса). На первом этапе каждое

i = 2 ,...,w —1 .

Этап обратной прогонки состоит в последовательном определе­ нии неизвестных х, . Сперва, как и в методе Гаусса, вычисляется хп,

для чего рассматривается уравнение (4.19) и последнее уравнение системы:

а пХп- 1 + Ь пХ» ХП-1 ~ А п -\ХП В „ -\ •

Система (4.23) может быть решена методом последовательных приближений. За нулевое приближение принимается любое произ­ вольное значение. Обычно для этого используется столбец свобод­ ных членов:

х(0) = р .

Следующее приближение реализуется путем подстановки зна­ чений х(0) в правую часть уравнений системы (4.23). В матричной форме первое приближение выражается как:

х(1)=Р + ах(0\ второе приближение определяется через первое:

х(2) = Р + ах(1),

по аналогии

х(А+1) =P + axw

В случае, когда последовательность приближений х(0\ х (1),...

имеет предел

х = lim х(*>,

к-*°°

он будет являться решением системы (4.23), а следовательно, и сис­ темы (4.22).

Формулы последовательных приближений в развернутом виде можно записать следующим образом:

(4.24)

(а„ = 0 ; / = 1,...,и; А:= 0 ,1,...).

Метод последовательных приближений, определяемый систе­ мой (4.24), принято называть методом итераций. Принято считать, что итерационный процесс сходится хорошо (т.е. число приближе­ ний, необходимых для получения корней системы (4.22) с заданной точностью, невелико), если элементы матрицы а по абсолютной величине малы. Иными словами, для успешного применения про­ цесса итерации модули диагональных элементов системы (4.22) должны быть много больше модулей недиагональных коэффициен­ тов этой системы. Величины свободных членов системы (4.22) на сходимость итерационного процесса влияния не оказывают.

4.5.2. Метод Гаусса - Зейделя

Рассмотрим систему линейных алгебраических уравнений с тремя неизвестными:

'аихх+апх2+апхг =Ъ{,

■j a2 i*i +а22х2 + а2гхъ = Ъ2;

<*г\х\ + а22х2+ #33X3 = Ь3.

Вынесем в левую часть каждого уравнения диагональное неиз­ вестное:

*3 =~ ( Ъг ~ аг\х\ ~ а22х2)-

“зз

JC] — ^ ( 4 + ^ 2 JC3 ) ,

xf1)=A(4 + 0 - 0 ) = l;

<jd^ = —( 9 - l - 2 0 ) = 4/3;

6

^ 1) = I ( 2 + l + 2-4/3) = 17/15

и Т.Д.

Истинное решение, к которому стремится итерационный про­ цесс (дг, =1, JC2 =1, JC3 =1), будет получено на 5-6-й итерации.

В случае системы п уравнений к-е приближение к истинному решению будет иметь вид

Рассмотрим сходимость данного метода. Дана система двух ли­ нейных уравнений

Из уравнений (4.27) и (4.28) получим

Дс« = _ ^ 1 Ду ^ ) 5

ап

ду * ) = _ “21.д*(*>

а 22

Из последних уравнений следует

Ду(*) = - 5 & д>,(*-1)

а11а 22

Аналогично

апа22

Продолжая, можно получить

Отсюда следует, что итерационный процесс для метода ГауссаЗейделя сходится, если приближение для к-й итерации станет суще­ ственно отличаться от первого приближения. Это возможно только при соблюдении условия

а 12а 21 < 1,

а \ \ а 22

т.е. диагональные члены должны доминировать над остальными. 4.6. Сравнение методов

Метод исключения хорош тем, что он конечен и теоретически с его помощью возможно реализовать любую невырожденную сис­ тему линейных алгебраических уравнений. Итерационный метод Гаусса - Зейделя сходится только для специальных систем уравне­ ний. Однако если итерационный метод сходится, то применение его предпочтительнее:

1. Время вычислений «я2 на одну итерацию, в то время как для метода исключения время пропорционально я3 Если решение по­ лучено менее чем за я итераций, то для итерационного метода об­ щие временные затраты будут меньше.

2. Ошибки округления для итерационного метода меньше.

3. Большие системы уравнений невозможно точно решить с помощью прямых методов.