Методика вычисления матрицы методом Зейделя

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

A∙X=B

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

X=B∙X+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 были ненулевыми.

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

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 .

n

i-1

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

j=1

j=1

X_i^(k+1) =X_i^(k) – a_ii^–1(∑a_ijx_j^(k+1) + ∑ a_ijx_i^(k) – b_i).

n

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

j=1

∑ | a­_ij | < | a­_ii |

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

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

Ручной счет

Исходные данные

i
Xi	-0,9	-0,3	0,1	0,5	1,0
Yi	-0,3	0,1	0,0	0,2	0,7

Ѱ₁(X)=1, Ѱ ₂(X)=X, Ѱ ₃(X)=3X²-1

Система нормальных уравнений

Ѱ(X_i)=C­_1­* Ѱ­_1­(X)+C­_2­* Ѱ­­_2­(X)+ C_3­* Ѱ­_3­­­(X)

Ѱ(X­_i­)=C­_1­*1+C­_2­*X+C­_3­*(3*X²-1)

max

y`=0( min и max – точки экстремумы)

Условие минимума

(1)

(2)

0,848= (3)