Метод главных элементов

На практике применяют множество ва­ри­ан­тов вы­чис­ли­тельных схем метода Гаусса. Например, при при­ве­дении мат­рицы к верхней тре­у­голь­ной фор­­ме вы­би­ра­ют на­и­боль­ший элемент (в­ строке или стол­бце), умень­шая вы­чис­ли­тель­­­­ную по­греш­­­ность за счет де­ле­ния на не са­мый ма­лень­кий эле­­мент. Та­кая вы­чис­ли­тель­ная схема на­зы­ва­ет­ся ме­­­то­­дом Га­­ус­са с выбо­ром ве­ду­щего элемента. Ес­ли же вы­би­­­рать при при­ведении мат­рицы са­мый боль­­шой (по мо­ду­лю) элемент из всех ос­­тав­ших­ся, то такая схе­ма бу­дет на­зы­ваться ме­то­дом Га­усса с вы­­бором глав­но­го эле­­мента. По­­след­няя схема от­но­сит­­ся к на­и­бо­лее по­­­пулярным. Глав­ное ее от­­личие от метода Гаусса сос­­то­ит в том, что при при­ведении мат­­рицы А к верх­ней (или ниж­ней) тре­угольной фор­­ме ее стро­ки и стол­б­­цы пе­ре­­став­­ля­ют так, чтобы на­и­боль­ший из всех ос­тав­­ших­ся эле­­­мен­­тов матрицы стал ве­дущим, и на него вы­пол­ня­ет­­ся де­ление. Ес­ли мат­ри­ца хоро­шо обу­с­лов­лена, то в ме­тоде Га­­усса с вы­бо­ром глав­­­но­го элемента по­греш­­нос­­ти ок­руг­ле­­ния не­ве­ли­­ки.

Формальные параметры процедуры. Входные: n (тип in­­te­ger) - целое положительное число, рав­ное по­­­рядку ис­­ходной системы; aa (тип real) - массив из nn дейс­т­ви­тель­ных чисел, содержащий мат­ри­цу ко­­эф­фи­циентов сис­те­мы (aa[1] = а₁₁; aa[2] = а₂₁; aa[3] = a₃₁; ...; aa[n]= a_n1; aa[n +1]= =a₁₂; aa[n + 2] = a₂₂; ...; aa[2*n] = а_n2; ...; aa[n*n] = а_nn); b (тип real) - мас­сив из n действительных чисел, со­дер­жа­щий стол­бец сво­бодных членов исходной системы (b[1] = =b₁; b[2] = b₂; ...; b[n] = b_n). Выходные: b (тип real) - мас­­сив из n действительных чисел (он же был вход­ным) при выходе из подпрограммы, со­дер­жа­щий ре­ше­ния ис­ход­ной системы (b[1]= x₁; b[2] = x₂; ...; b[n] = x_n); ks (тип in­­te­ger) - признак пра­виль­нос­ти ре­­ше­ния или код ошиб­ки: если ks = 0, то в ма­с­си­ве b со­дер­жится ре­­шение ис­ход­ной сис­те­мы; если ks = 1, то исход­ная сис­тема не име­ет ре­ше­ния (глав­ный опре­де­ли­тель ее равен нулю).

Решение систем линейных уравнений методом итераций

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

Условия и скорость сходимости процесса в боль­­­шей сте­пени зависят от свойств уравнений, т.е. от свойств мат­ри­цы системы и от выбора на­­чаль­ного при­бли­же­ния.

Пусть дана система линейных ал­геб­ра­и­чес­ких урав­не­ний (1) с неособенной матрицей. В ме­то­де простой ите­ра­ции если а_ii  0, то ис­ход­ная сис­тема мо­жет быть пре­об­ра­зо­вана к виду х_i = b_i + a_ij х_j , i  j, т.е. из каждого уравнения по­­сле­до­ва­тельно вы­ра­жа­ют х_i.

Здесь b_i = F_i / а_ii; a_ij = - а_ij / а_ii. Таким образом, в мат­рич­ном виде имеем Х = В + AХ. Полученную сис­­­­тему бу­дем решать методом по­сле­до­ва­тель­ных при­­ближений. За ну­левое приближение Х⁽⁰⁾ мож­но при­нять матрицу В: Х⁽⁰⁾= = B, и далее, под­ста­вив най­денные значения в исходную систему, по­лу­чим Х ⁽¹⁾ = В + A Х⁽⁰⁾ .

При бесконечном повторении этой вы­чис­ли­тель­­ной схемы имеем

,

где и будет искомое решение системы.

Условия сходимости итерационного процесса опре­­­де­ля­ются теоремами, которые приводятся на­ми без до­ка­за­тельств.

Теорема 1. Для того, чтобы по­сле­до­ва­тель­ность при­бли­­жений Х⁽ⁿ⁾ сходилась, до­ста­точ­но, что­бы все соб­ст­вен­ные значения матрицы A были по мо­ду­лю меньше еди­ни­цы: | _i | < 1, i = 1, 2, ..., n.

Теорема 2. Если требовать, чтобы по­сле­до­ва­тель­ность Х⁽ⁿ⁾ сходилась к при любом на­чаль­ном при­бли­же­­­нии Х⁽⁰⁾ , то условие те­о­ре­мы 1 яв­ля­ет­ся не­об­хо­ди­мым.

Применение теорем 1 и 2 требует знания всех соб­­­ст­вен­ных значений матрицы A, нахождение ко­­то­рых яв­ля­ет­ся очень не простой за­да­чей. По­э­то­му на прак­ти­ке огра­ни­чи­ва­ются бо­лее прос­той те­о­ре­мой, дающей до­статочные ус­ло­­вия схо­димости.

Теорема 3. Если для системы Х = В + AХ в­ы­пол­­­няется хотя бы одно из условий :

_;

_,

то итерационный процесс сходится к един­ствен­но­­му ре­ше­­нию этой системы независимо от вы­бо­ра на­чаль­но­го при­ближения.

Для многих приложений важно знать, какой яв­­ля­ет­ся ско­рость сходимости про­цес­са, и оценить по­­греш­ность по­лу­ченного ре­ше­ния.

Теорема 4. Если какая-либо норма мат­ри­цы A, со­гла­со­­ванная с рассматриваемой нормой век­то­ра Х, меньше еди­­ницы, то верна следующая оцен­­ка по­греш­нос­ти при­бли­жения в методе прос­той итерации:

_.

Формальные параметры процедуры. Входные: А (тип real) - матрица, составленная из коэф­фи­ци­ен­тов при Х преобразованного уравнения; В (тип real) - мат­ри­­ца, сос­тав­лен­ная из свободных членов; N (тип integer) - раз­мер­ность мат­риц А (N  N) и В(N); IK (тип integer) - пре­дель­но воз­мож­ное количество итераций (введено для то­го, что­бы в слу­чае рас­­хож­дения процесса выйти из под­про­грам­мы. Обы­ч­­но решение достигается за 3-6 ите­ра­ций); ЕРS (тип real) - за­дан­ная погрешность ре­шения. Вы­ходные: Х (тип real) - матрица, в ко­торой на­хо­дится ре­ше­­ние сис­темы.

Решение систем линейных уравнений методом Зейделя

Этот метод относится к итерационным, имеет бо­­­лее бы­струю сходимость по сравнению с ме­то­дом простых ите­раций .

Метод Зейделя применяют в двух расчетных схе­­мах. Рассмотрим каноническую форму (для схе­­­мы ите­раций). Пусть система приведена к ви­ду Х = Вх + b. В схеме про­с­той итерации сле­ду­ю­щее при­бли­же­ние Х^{(k +1)} находит­ся пу­тем под­ста­нов­­ки пре­ды­ду­ще­го приближения Х^(k) в правую часть выражения X^{(k +1)} = B X ^(k) + b.

Для удобства рассуждений полагаем, что ле­­­вые час­ти уравнений содержат х_i (элементы матрицы X^{(k +1)}) с воз­­рас­та­­ю­щи­ми но­ме­рами, т.е. сначала х₁, затем х₂, х₃, ..., х_n. Тог­да ре­ше­ние системы уравнений Х = Вх + b на оче­ред­ной (k +1) итерации будет имет вид

, (1.6)

т.е. каждое очередное найденное приближение х_i^{(k +1)} сразу же используется для определения . Ус­ло­вия схо­ди­мос­ти для итерационного ме­тода Зей­де­ля дают те же тео­ре­мы, что и в ме­то­де простых ите­ра­ций.

Вторая форма метода Зейделя требует пред­ва­ри­­тель­но­го приведения системы (1) к ви­ду, ког­да все ди­а­го­наль­ные элементы отличны от ну­­ля. Ес­ли раз­ло­жить мат­ри­цу А на сумму двух мат­­риц R + С, где R - ниж­няя ди­а­го­наль­ная мат­ри­­ца, а С - верх­няя с нулями на главной ди­а­­го­на­­ли, то систему (1) можно за­пи­сать как

Ax = (R + C)x = R x^{(k +1)} + C x^(k) = B

или x^{(k +1)} = R ^-1B - R ^-1C x^(k)

и тог­да становится ясно, что метод Зейделя в ка­но­ни­чес­кой форме равносилен методу простой ите­ра­ции, при­ме­не­н­ному к системе

X = R ^-1B - R ^-1C X.

Формальные параметры процедуры такие же, как и в методе итераций.