ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

 

Общие сведения

 

К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы - алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.

 

Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А - матрица. (1)

 

A = {a_ij}i, j = 1…n

B = {b_i}x = {x_i}

 

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

 

x_k = Cx_k-1 + D

 

x_k → x*, где х* - решение заданной системы.

В конечном варианте система будет имееть вид:

 

x₁=c₁₁x₁+c₁₂x₂+c₁₃x₃+…c_1nx_n+d₁

x₂=c₂₁x₁+c₂₂x₂+c₂₃x₃+…c_2nx_n+d₁

x₃=c₃₁x₁+c₃₂x₂+c₃₃x₃+…c_1nx_n+d₃

_{…………………………………………. .}

x_n=c_n1x₁+c_n2x₂+c_n3x₃+…c_nnx_n+d_n

 

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

 

, или .

 

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

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

 

x₁₌a₁₁^-1 (c₁-a₁₂x₂ - a₁₃x₃-… - a_1nx_n)

x₂₌a₂₂^-1 (c₂-a₂₁x₂ - a₂₃x₃-… - a_2nx_n)

………………………. .

x_n=a_nn^-1 (c_n-a_n1x₂ - a_n3x₃-… - a_n-1nx_n-1)

В результате получим систему:

x₁₌0+ c₁₂x₂+ c₁₃x₃-…+ c_1n-1x_n-1+ c_1nx_n+d₁

x₂₌ c₂₁x₂+0 +c₂₃x₃+…+ c_2n-1x_n-1+ c_2nx_n+d₂

_{………………………………………………………. .}

x_n= c_n1x₁+ c_n2x₂ +c_n3x₃+…+ c_nn-1x_n-1+ 0+d_n

 

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

 

с_ij=-a_ij/a_ii, d_i=c_i/a_ii (i,j=1,2,3…n, i<>j)

 

Итерационный процесс продолжается до тех пор, пока значения х₁ ^(k), х₂ ^(k), х₃ ^(k) не станут близкими с заданной погрешностью к значениям х₁ ^(k-1), х₂ ^(k-1), х₃ ^(k-1).

 

Решение СЛАУ методом простых итераций

 

Решить СЛАУ методом простых итераций с точностью .

 

 

Для удобства преобразуем систему к виду:

 

 

Условие сходимости:

 

,

 

Принимаем приближение на 0-ом шаге:

 

,

,

 

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

 

 

Смотрим не выполняется ли условие остановки итерационного процесса:

 

:

 

На 2-м шаге выполняем следующее:

 

 

Смотрим не выполняется ли условие остановки итерационного процесса

 

:

 

На 3-м шаге выполняем следующее:

 

 

Смотрим не выполняется ли условие остановки итерационного процесса

 

:

 

На 4-м шаге выполняем следующее:

 

 

Смотрим не выполняется ли условие остановки итерационного процесса

 

:

 

На 5-м шаге выполняем следующее:

 

 

Смотрим не выполняется ли условие остановки итерационного процесса:

 

:

 

На 6-м шаге выполняем следующее:

 

 

Смотрим не выполняется ли условие остановки итерационного процесса:

 

:

 

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].

 

 

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

 

Описание метода

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

 

………………………………………….

 

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

 

, либо