- •§ 3. Методы решения систем линейных и нелинейных уравнений
- •§3. Методы решения систем линейных и нелинейных уравнений
- •3.1. Метод исключения гаусса для систем линейных уравнений
- •3.2. Метод главных элементов
- •3.3. Решение систем нелинейных уравнений методом ньютона
- •3.4. Решение систем линейных уравнений методом квадратного корня
- •3.5. Решение систем линейных уравнений методом итераций
- •3.6. Решение систем линейных уравнений методом зейделя
- •§4. Алгебра матриц
- •4.1. Вычисление собственныхвекторов и собственных значений матриц по методу крылова
3.5. Решение систем линейных уравнений методом итераций
Итерационные методы решения систем линейных уравнений дают возможность вычислить решение системы как предел бесконечной последовательности промежуточных решений. Причемкаждое последующее решение в случае сходимостиитерационного процесса считается более точным. В этих методах, в отличие от точных(см. п. 3.1 - 3.4), ошибки в начальном приближении и последующих вычислениях компенсируются, т.е. итерационные методы (в случае сходимости) позволяют получить решение более точное, чем прямые. Поэтому итерационные методы относят ксамоисправляющимся.
Условия и скорость сходимости процесса в большей степени зависят от свойств уравнений, т.е. от свойствматрицы системы и от выбора начального приближения.
Пусть дана система линейных алгебраических уравнений (1.22) с неособенной матрицей. В методепростой итерации еслиаii № 0,то исходная система может быть преобразована к видухi = bi + aij хj , i № j, т.е. из каждого уравнения последовательно выражаютхi.
Здесь bi = Fi / аii; aij = - аij / аii. Таким образом, в матричном виде имеемХ = В + AХ.Полученную систему будем решатьметодом последовательных приближений. За нулевое приближениеХ(0) можно принять матрицуВ:Х(0)= = B, и далее, подставив найденные значения в исходную систему, получимХ (1) = В + A Х(0) .
При бесконечном повторении этой вычислительной схемы имеем
,
гдеи будет искомое решение системы.
Условия сходимости итерационного процесса определяются теоремами, которые приводятся нами без доказательств.
Теорема 1.Для того, чтобы последовательность приближений Х(n) сходилась, достаточно, чтобы все собственные значения матрицы A были по модулю меньше единицы: | li | < 1, i =1, 2, ..., n.
Теорема 2. Если требовать, чтобы последовательность Х(n) сходилась к при любом начальном приближении Х(0) , то условие теоремы 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:
Х1 = 0.08Х1 + 0.05Х2 + 0.11Х3 + 0.08Х4 + 2.15
Х2 = 0.05Х1 + 0.13Х2 + 0.27Х3 + 0.28Х4 + 0.44
Х3 = 0.11Х1 + 0.27Х2 + 0.28Х3 + 0.06Х4 + 0.83
Х4 = 0.08Х1 + 0.18Х2 + 0.06Х3 + 0.12Х4 + 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 :РЕШЕНИЕ |