Численные методы решения систем линейных алгебраических уравнений (стр. 4 из 5)

(9)

Естественно требовать, чтобы объем вычислений для решения .системы By_k+1 = F_kбыл меньше, чем объем вычислений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности z_h = у_к — и, т. е. разностью между решением уравнения (7) и точным решением и исходной системы линейных алгебраических уравнений. Подстановка y_k = z_k+uв (2) приводит к однородному уравнению для погрешности:

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

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

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

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

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

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).

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

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

.

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

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

,

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

,

,

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

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

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

:

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

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

:

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

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

:

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

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

:

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

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

:

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

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

:

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

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

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

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

вычисляются по формулам:

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

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

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

, либо