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

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

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

Пусть дана система линейных ал­геб­ра­и­чес­ких урав­не­ний (1.22) с неособенной матрицей. В ме­то­депростой ите­ра­ции еслиа_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 были по мо­ду­лю меньше еди­ни­цы: | l_i | < 1, i =1, 2, ..., n.

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

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

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

_;

_,

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

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

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

_.

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

Так, можно предложить к использованию сле­ду­­ю­щую удобную и достаточно эффективную про­­це­дуру, взятую из БСП БЭСМ для транслятора ALFA. Перевод на языкPASCALвыполнен ав­то­ра­ми.

procedure ITER (n, ik :integer; eps : real;

a : mas1; b : mas; var x : mas);

var x1 : mas; s : real; i, j, k : integer;

begin x1 := b;

x := x1; k := 0;

repeat s := 0.0;

Inc(k);

for i := 1 to n do

begin

for j := 1 to n do x[i] := a[i,j]*x1[j] + b[j];

s := s + abs (x[i]-x1[i]);

end;

s := s / n; x1 := x;

until (s<eps) and (k>ik);

end.

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

Для примера методом простых итераций ре­­шена система 4´4 линейных уравнений с точ­ностью до 0.0001:

Х₁ = 0.08Х₁ + 0.05Х₂ + 0.11Х₃ + 0.08Х₄ + 2.15

Х₂ = 0.05Х₁ + 0.13Х₂ + 0.27Х₃ + 0.28Х₄ + 0.44

Х₃ = 0.11Х₁ + 0.27Х₂ + 0.28Х₃ + 0.06Х₄ + 0.83

Х₄ = 0.08Х₁ + 0.18Х₂ + 0.06Х₃ + 0.12Х₄ + 1.16

Результаты вычислений представлены в табл. 1.16.

Таблица 1.16

X[1]	X[2]	X[3]	X[4]	№ итерации
2.150000	0.440000	0.830000	1.160000	iter = 0
1.252800	1.484800	1.229600	1.299200	iter = 1
1.263936	1.523776	1.237952	1.315904	iter = 2
1.265272	1.528453	1.238954	1.317908	iter = 3
1.265433	1.529014	1.239075	1.318149	iter = 4
1.265452	1.529082	1.239089	1.318178	iter = 5
1.265454	1.529090	1.239091	1.318181	iter = 6
1.265455	1.529091	1.239091	1.318182	iter = 7
1.265455 1.529091 1.239091 1.318182 :РЕШЕНИЕ