Реферат: Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

Заметим, что 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 ^{(n )} , … приближений к вычисляемых по формуле

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

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

x₁ ^{(k +1)} = b ₁₂ x ₂ ^{(k )} + b ₁₃ x ₂ ^{(k )} + … + b _1n x_n ^{(k )} + c ₁ ,

x₂ ^{(k +1)} = b ₂₁ x ₁ ^{(k +1)} + b ₂₃ x ₃ ^{(k )} + … + b _2n x_n ^{(k )} + c ₂ ,

x₃ ^{(k +1)} = b ₃₁ x ₁ ^{(k +1)} + b ₃₂ x ₂ ^{(k +1)} + … + b _3n x_n ^{(k )} + c ₃ ,

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

x_n ^{(k +1)} = b_{n 1} x ₁ ^{(k +1)} + b_{n 2} x ₂ ^{(k +1)} + b_{n 3} x ₃ ^{(k +1)} + … + c_n .

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

x_i ^{(k +1)} = x _i ^{(k )} – a_ii ^–1 (∑_{j =1} ^{i –1} a_ij x_j ^{(k +1)} + ∑_{j =1} ⁿ a_ij x_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 _1n x_n = b ₁ ,
a ₂₁ x ₂ + a ₂₂ x ₂ + … + a _2n x_n = b ₂ ,
. . . . . . . . . . . . .

a_{n 1} x ₁ + a_{n 2} x ₂ + … + a_nn x_n = b_n