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

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

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₁₁-¹ (b₁ — a₁₂x₂ — a₁₃x₃ — … — a_1nx_n),.

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

x₂ = a₂₁-¹ (b₂ — a₂₂x₂ — a₂₃x₃ — … — a_2nx_n),.

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

x₁ = b₁₂x₂ +b₁₃x₃ + … +b_1,n-₁x_n-₁ +b_1nx_n+ c₁,.

x₂ = b₂₁x₁ +b₂₃x₃ + … +b_2,n-₁x_n-₁ +b_2nx_n+ c₂,.

x₃ = b₃₁x₁ +b₃₂x₂ + … +b_3,n-₁x_n-₁ +b_3nx_n+ c₃,.

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

x_n = b_n1x₁ +b_n2x₂ + b_n3x₃ +… +b_{n, n}-₁x_n-₁ +c_n,.

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

b_ij = -a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j? i).

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

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

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_1,

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

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

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

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-¹(?_j=1ⁱ-¹ a_ijx_j^(k+1) + ?_j=1ⁿ a_ijx_i^(k) — b_i).

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

• ?_{j=1, j? i} ⁿ | a_ij | < | a_ii |
• (условие доминрованния диагонали).

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

Метод Рунге-Кутта

Метод позволяет решать системы обыкновенных дифференциальных уравнений первого порядка следующего вида:

которые имеют решение:

где t — независимая переменная (например, время); X, Y и т. д. — искомые функции (зависимые от t переменные). Функции f, g и т. д. — заданы. Также предполагаются заданными и начальные условия, т. е. значения искомых функций в начальный момент.

Одно дифференциальное уравнение — частный случай системы с одним элементом. Поэтому, далее речь пойдет для определенности о системе уравнений. Метод Рунге-Кутта заключается в рекуррентном применении следующих формул:

Где.

Метод может быть полезен и для решения дифференциальных уравнений высшего (второго и т. д.) порядка, т.к. они могут быть представлены системой дифференциальных уравнений первого порядка [2].