Методы Зейделя и простой итерации

Методы решения систем линейных алгебраических уравнений

Методы решения систем линейных алгебраических уравнений подразделяются на прямые, являющиеся точными, и итерационные, которые являются приближёнными. Прямые методы базируются на исполнении не бесконечного количества арифметических действий. В качестве примера таких методов можно привести метод обратной матрицы, метод Гаусса, метод Гаусса-Жордана, метод прогонки для трех диагональных матриц и так далее. Сущность итерационных методов состоит в том, чтобы путём последовательных приближений найти решение системы с требуемой точностью. Наиболее распространёнными итерационными методами считаются метод простых итераций и метод Зейделя. Они фактически являются эквивалентными, но конечно имеют и отличия.

Статья: Методы Зейделя и простой итерации

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

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

В итерационных методах обычно присутствуют следующие основные этапы:

1. Приведение исходной системы вида $ ¯A * ¯x = ¯b $ к итерационной форме.
2. Осуществление проверки условия сходимости.
3. Реализация решения системы выбранным методом.

Метод простых итераций

Для систем общего вида должно выполняться тождество m = n, где m — это число уравнений в системе, а n — это количество неизвестных.

То есть, нет смысла в решении не доопределенных (m меньше n) и переопределенных (m больше n) систем уравнений, так как их можно свести за счёт элементарных алгебраических преобразований к нормальным (m=n) системам линейных уравнений. Иначе говоря, когда присутствует «ненормальная» система уравнений, то перед началом использования метода простых итераций, следует преобразовать её в нормальную.

Систему линейных уравнений можно записать в матричной форме, где:

• A является матрицей коэффициентов.
• b является вектором свободных членов.
• x является вектором неизвестных.

В качестве примера рассмотрим следующую систему:

Рисунок 1. Система уравнений. Автор24 — интернет-биржа студенческих работ

Представим её в матричной форме:

Рисунок 2. Система уравнений в матричной форме. Автор24 — интернет-биржа студенческих работ

Первый этап итерационного метода заключается в преобразовании исходной системы, то есть матрицы А и вектора b в итерационную форму, где С и d являются итерационными формами исходных данных.

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

$c_{ij} = -a_{ij} / a_{ii}$ $D_i = b_i / a_{ii}$ где i, j = 1,2,3…

Необходимо заметить, что диагональные компоненты новой матрицы обнуляются, хотя должны быть равны -1. В результате для рассматриваемой системы получается:

Рисунок 3. Матрица. Автор24 — интернет-биржа студенческих работ

Если выполнять преобразование исходной системы к итерационной форме, то она не удовлетворит условию сходимости:

Рисунок 4. Формула. Автор24 — интернет-биржа студенческих работ

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

Очевидно, что в рассматриваемом примере третий элемент третьей строки по модулю больше других. Его следует оставить неизменным. Необходимо поменять местами первую и вторую строки, а далее умножить строку, ставшую первой, на минус единицу и сложить её с новой второй строкой. В результате получится:

Рисунок 5. Матрица. Автор24 — интернет-биржа студенческих работ

Теперь при подстановке в формулы итерационная форма получится верной и второй этап, то есть проверка условия сходимости, может быть успешно пройден. Если же система не проходит эту проверку, то приближения не будут сходиться к реальному решению, и ответ получен не будет. Если же условие сходимости исполняется, то стратегия метода простых итераций может быть применена и можно переходить к третьему этапу. В конечном счете будет получена система линейных алгебраических уравнений в итерационной форме:

Рисунок 6. Система линейных уравнений. Автор24 — интернет-биржа студенческих работ

Здесь $x_1, x_2, x_3$ являются приближениями, которые получаются на текущем шаге итерации за счет приближений, найденных на предыдущей итерации - $x^0_1, x^0_2, x^0_3$.

Итерационный процесс по методу простых итераций продолжается до тех пор, пока вектор приближений не придёт к необходимой точности, то есть, пока не исполнится условие выхода:

$Max|x_i – x^0_i|$ ∠ $ε$

Здесь ε является требуемой точностью.

Метод Зейделя

Как уже отмечалось выше, метод простых итераций и метод Зейделя, по своей сути, являются идентичными. Разница заключается в том, что в методе Зейделя вычисление вектора приближений на текущей итерации выполняется с применением данных, которые были получены ни только на предыдущей, но и на исполняемой итерации. Это означает, что элемент x1 определяется через x2 и x3, величины которых были рассчитаны на предыдущей итерации, а последующий элемент x2 уже рассчитывается на основании x1, найденного именно на текущей итерации, и x3, вычисленного на предыдущей. Иначе говоря, данные в методе Зейделя для определения вектора X используются в процессе расчётов по мере их вычисления. А в методе простых итераций применяются данные, которые были получены именно на предыдущей итерации.

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

Ниже представлена программная реализация метода Зейделя:

Procedure Zeidel(C:array of array of real;d:array of real;n:integer);

var i,j:Integer;

X0:array of real;

delta:real;

E:array of real;

promX:array of real;

begin

SetLength(X0,n);

SetLength(X,n);

Setlength(E,n);

Setlength(promX,n);

X0:=Copy(d);

promX:=Copy(d);

X:=Copy(d);

repeat

begin

for i:=0 To n-1 Do

begin

X[i]:=0;

for j:=0 To n-1 Do

begin

X[i]:=X[i]+C[i,j]*promX[j];

end;

X[i]:=X[i]+d[i];

promX:=Copy(X);

E[i]:=Abs(X[i]-X0[i]);

end;

delta:=E[0];

for i:=1 To n-1 Do

begin

if delta∠E[i] then delta:=E[i];

end;

X0:=Copy(X);

end;

Until delta∠=0.000001;

writeln('решение системы равно вектору:');

For i:=0 To n-1 Do

begin

Writeln(X[i]);

end;

end;