Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя (стр. 2 из 3)

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов a_ij^(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент a_ikjk^(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: x_jn, x_jn–1, …, x_j1.

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

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

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x = Bx + c.

Здесь B – квадратная матрица с элементами b_ij (i, j = 1, 2, …, n), c – вектор-столбец с элементами c_ij(i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

. . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x₁:

x₁ = a₁₁^–1 (b₁ – a₁₂x₂ – a₁₃x₃ – … – a_1nx_n),

из второго уравнения – неизвестное x₂:

x₂ = a₂₁^–1 (b₂ – a₂₂x₂ – a₂₃x₃ – … – a_2nx_n),

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

x₁ = b₁₂x₂ + b₁₃x₃ + … + b_1,n–1x_n–1 + b_1nx_n+ c₁ ,

x₂ = b₂₁x₁ + b₂₃x₃ + … + b_2,n–1x_n–1 + b_2nx_n+ c₂ ,

x₃ = b₃₁x₁ + b₃₂x₂ + … + b_3,n–1x_n–1 + b_3nx_n+ c₃ ,

. . . . . . . . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_n,n–1x_n–1 + c_n ,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

b_ij = –a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j ≠ i)

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

1.2.1. Описание метода. Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b₁₂ b₁₃ … b_1n

b₂₁ 0 0 … 0 0 0 b₂₃ … b_2n

B₁ = b₃₁ b₃₂ 0 … 0 , B₂ = 0 0 0 … b_3n

. . . . . . . . . . . . . .

b_n1 b_n2 b_n3 … 0 0 0 0 … 0

Заметим, что B = B₁+ B₂ и поэтому решение x исходной системы удовлетворяет равенству

x = B₁x + B₂ x + c .

Выберем начальное приближение x⁽⁰⁾ = [x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾]^T. Подставляя его в правую часть равенства при верхней треугольной матрице B₂и вычисляя полученное выражение, находим первое приближение

x⁽¹⁾ = B₁x⁽⁰⁾ + B₂x⁽¹⁾

Подставляя приближение x⁽¹⁾, получим

x⁽²⁾ = B₁x⁽¹⁾ + B₂x⁽²⁾

Продолжая этот процесс далее, получим последовательность x⁽⁰⁾, x⁽¹⁾, …, x⁽ⁿ⁾, … приближений к вычисляемых по формуле

x^(k+1) = B₁^(k+1) + B₂^(k) + c

или в развернутой форме записи

x₁^(k+1) = b₁₂x₂^(k) + b₁₃x₂^(k) + … + b_1nx_n^(k) + c₁ ,

x₂^(k+1) = b₂₁x₁^(k+1) + b₂₃x₃^(k) + … + b_2nx_n^(k) + c₂ ,

x₃^(k+1) = b₃₁x₁^(k+1) + b₃₂x₂^(k+1) + … + b_3nx_n^(k) + c₃ ,

. . . . . . . . . . . . . . . . . . . . . . . . . .

x_n^(k+1) = b_n1x₁^(k+1) + b_n2x₂^(k+1) + b_n3x₃^(k+1) + … + c_n .

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

x_i^(k+1) = x_i^(k) – a_ii^–1(∑_j=1^i–1a_ijx_j^(k+1) + ∑_j=1ⁿa_ijx_i^(k) – b_i).

Тогда достаточным условием сходимоти метода Зейделя будет

∑_{j=1, j≠i} ⁿ | a_ij | < | a_ii |

(условие доминированния диагонали).

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

1.3. Сравнение прямых и итерационных методов

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

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

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

2. Практическая часть

2.1 Программа решения систем линейных уравнений по методу Гаусса

2.1.1. Постановка задачи. Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁ ,
a₂₁x₂ + a₂₂x₂ + … + a_2nx_n = b₂ ,
. . . . . . . . . . . . .

a_n1x₁ + a_n2x₂ + … + a_nnx_n = b_n

для n ≤ 10 по методу Гаусса.

2.1.2. Тестовый пример.

3,2x₁ + 5,4x₂ + 4,2x₃ + 2,2x₄ = 2,6 ,

2,1x₁ + 3,2x₂ + 3,1x₃ + 1,1x₄ = 4,8 ,

1,2x₁ + 0,4x₂ – 0,8x₃ – 0,8x₄ = 3,6 ,

4,7x₁ + 10,4x₂ + 9,7x₃ + 9,7x₄ = –8,4 ,

x₁ = 5, x₂ = –4, x₃ = 3, x₄ = –2.

2.1.3. Описание алгоритма. В данной программе реализован метод Гаусса со схемой частичного выбора.

В переменную n вводится порядок матрицы системы. С помощью вспомогательной процедуры ReadSystem в двумерный массив a и одномерный массив b вводится c клавиатуры расширенная матрица системы, после чего оба массива и переменная n передаются функции Gauss. В фукции Gauss для каждого k-го шага вычислений выполняется поиск максимального элемента в k-м столбце матрицы начинаяя с k-й строки. Номер строки, содержащей максимальный элемент сохраняеется в переменной l. В том случае если максимальный элемент находится не в k-й строке, строки с номерами k и l меняются местами. Если же все эти элементы равны нулю, то происходит прекращение выполнения функции Gauss c результатом false. После выбора строки выполняется преобразование матрицы по методу Гаусса. Далее вычисляется решение системы и помещается в массив x. Полученное решение выводится на экран при помощи вспомогательной процедуры WriteX.

2.1.4. Листинг программы и результаты работы