Теоретическая часть. Решение систем линейных уравнений методом Гаусса и методом Гаусса-Зейделя

Решение систем линейных уравнений методом Гаусса и методом Гаусса-Зейделя.

Лабораторная работа №3

Цель работы: Составить программу решения системы линейных уравнений вида

а11x1+a12x2+a13x3=b1

a21x1+a22x2+a23x3=b2

a31x1+a32x2+a33x3=b3

а) методом Гаусса

б) методом Гаусса-Зейделя

Метод Гаусса прост и широко применим для решения систем линейных уравнений. Рассмотрим систему уравнений (рис. 1).

рис. 1. Метод Гаусса решение систем линейных уравнений. Система уравнений.

Суть работы алгоритма очень проста. Она заключается в последовательности удаления элементов. Умножаем элементы первой строки на элемент A21, а элементы второй строки на элемент A11. Вычитая из первой строки вторую, получим следующее уравнение 0x1+(A21*A12-A11*A22)x2 +(A21*A13-A11*A23)x3+...+(A21*A1n-A11*A2n)xn=A21*b1-A11*b2 второй строки. Обнулив переменную x1 во второй строке, аналогично делаем в третьей 0x1+(A31*A12-A11*A32)x2+(A31*A13-A11*A33)x3+...+(A31*A1n-A11*A3n)xn=A31*b1-A11*b3. Для n-ой строки 0x1+(An1*A12-A11*An2)x2+(An1*A13-A11*An3)x3+...+(An1*A1n-A11*Ann)xn=An1*b1-A11*bn. Заменим выражение (A21*A12-A11*A22) на A22^(1),(A21*A13-A11*A23) на A23^(1),(A21*A1n-A11*A2n) на A2n^(1), (A21*b1-A11*b2) на b2^(1) и т.д. (рис. 2).

рис. 2. Решение систем уравнений метод Гаусса «прямой ход». Удаление переменной x1.

После преобразования системы (рис. 1) переменная x1 осталась только в первом уравнении (рис 2). На втором шаге проделываем аналогичные операции. Умножаем элементы второй строки на элемент A32^1, а элементы третьей строки на элемент A22^1. Вычитая из второй строки третью, получим следующее уравнение 0x2+(A32^1*A23^1-A22^1*A33^1)x3+(A32^1*A24^1-A22^1*A34^1)x3+...+(A32^1*A2n^1-A22^1*A3n^1)x3=A32^1*b2^1- A22^1*b3^1 третьей строки. Удалив переменную x2 из всех уравнений кроме второго, мы получим следующую систему уравнений (рис. 3).

рис. 3. Решение систем уравнений метод Гаусса «прямой ход». Удаление переменной x2.

Продолжаем данный процесс (n-1) раз. В результате получим треугольную матрицу (рис. 4). Данное преобразование называется «прямой ход».

рис. 4. Решение систем уравнений метод Гаусса «прямой ход». Треугольный вид системы уравнений.

Используя треугольную систему уравнений (рис. 4), легко получаем значения неизвестных x, начиная с последнего уравнения (рис. 5). Данный процесс называется «обратный ход» решения систем уравнений методом Гаусса.

рис. 5 Решение системы уравнений метод Гаусса «обратный ход».

Метод Гаусса-Зейделя

Данный метод является одним из самых распространенных итерационных методов решения СЛАУ, поскольку он отличается простотой и легкостью программирования. Рассмотрим его суть. Допустим, диагональные коэффициенты исходной матрицы { a_ij }отличны от нуля (в противном случае можно переставить местами уравнения исходной системы). Представим исходную систему (2.1) в следующем виде:

(2.5)

Если теперь задать для неизвестных их начальные приближенные значения, то система (2.5) позволяет вычислить более точные значения неизвестных на первом шаге (на первой итерации):

(2.6)

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

(2.7)

и так далее.

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

i = 1, 2, …, n; k = 1, 2, …

(2.8)

Итерационный процесс продолжается до тех пор, пока все значения x_i^(k), не станут достаточно близкими к x_i^(k-1). Близость этих значений можно охарактеризовать максимальной абсолютной величиной их разности . Тогда при заданной точности вычислений  > 0 критерий окончания итерационного процесса можно записать в виде:

(2.9)

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

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

,

(2.10)

При этом хотя бы для одного уравнения неравенство (2.10) должно выполняться строго.

Дата добавления: 2014-01-15