Решение систем линейных алгебраических уравнений. Метод исключения Жордана и его модификация, страница 2

a_k,k^(k-1)x_k + … + a_k,n^(k-1)x_n = c_k^(k-1),

…

a_n_,_k⁽^k-1)x_k + … + a_n_,_n⁽^k-1)x_n = c_n⁽^k-1);

Предположим, что a_k_,_k⁽^k-1) не равен 0. Поделив k-е уравнение последней системы на a_k_,_k⁽^k-1) , перепишем его в виде:

x_k +a_k_,_k+1⁽^k)x_k₊₁ + … + a_k_,_n⁽^k1)x_n = c_k⁽^k),

где a_k_,_j⁽^k)= a_k_,_j⁽^k-1)/ a_k_,_k⁽^k-1) , j = k + 1,…,n, c_k⁽^k)= c_k⁽^k-1)/ a_kk⁽^k-1) . (3)

Умножим это уравнение на a_i_,_k⁽^k-1) и вычтем его из i-го уравнения системы (2), i = 1,…,n. В результате система (2) примет вид:

x₁ + a_1k+1^(k)x_k + … + a_1n^(k)x_n = c₁^(k),

x₂ + a_2,k+1^(k)x_k + … + a_2n^(k)x_n = c₂^(k),

^.._. …

x_k-1 + a_k-1,k+1^(k)x_k+1 + … + a_k-1,n^(k)x_n = c_k-1^(k), (4)

x_k+ a_k,k+1^(k)x_k+1 + … + a_k,n^(k)x_n = c_k^(k),

a_k+1,k+1^(k)x_k+1 + … + a_k+1,n^(k-1)x_n = c_k+1^(k),

…

a_n,k^(k)x_k + … + a_n,n^(k)x_n = c_n^(k);

где a_i,j^(k) = a_i,j^(k-1) - a_i,k^(k-1) a_k,j^(k) , i = 1,…,n, i не равен k, j = k + 1 ,…, n,

c_i^(k) = c_i^(k-1) - a_i,k^(k-1) c_k^(k) , i = 1,…,n, i не равен k. (5)

Выражения (3) и (5) являются формулами перехода от системы (2) к системе (4). После приведения вычислений по формулам (3) и (5) при k=1,…,n матрица станет единичной матрицей. Следовательно, правая часть системы содержит искомое решение: x_i = c_i⁽ⁿ⁾, i=1,…,n.

Метод Жордана осуществим тогда, когда все главные угловые миноры матрицы A отличны от нуля.

Проведём оценку количества арифметических операций в методе Жордана.

1. На вычисление a_kj⁽^k) при j = k+1,…,n, k=1,…,n по формулам (4) требуется ∑_k=1ⁿ(n-k) = n(n-1)/2 = O(n²) (n→ ∞) операций деления.

2. На вычисление a_ij⁽^k) при i=1,…,n, i ≠ k, j = k+1,…,n, k=1,…,n по формулам (6) требуется ∑_k=1ⁿ(n-k) = (n-k)(n-1) = (n-1)²n/2 = n³/2 + O(n²) (n→ ∞) операций умножения и столько же операций вычитания.

3. На вычисление c_k⁽^k) при k=1,…,n по формулам (4) требуется n операций деления.

4. На вычисление b_i⁽^k) при i=1,…,n, i ≠ k, k=1,…,n по формулам (6) требуется ∑_k=1ⁿ(n-1) = n(n-1) = O(n²) (n→ ∞) операций умножения и столько же операций вычитания.

Таким образом, метод Жордана требует O(n²) + n³/2 + O(n²) = n³/2 + O(n²) (n→ ∞) мультипликативных операций и столько же аддитивных операций. Всего: n³ + O(n²) (n→∞) арифметических операций. Метод Гаусса требует n³/3 + O(n²) (n→ ∞) мультипликативных операций и столько же аддитивных операций. Всего: (2/3)n³ + O(n²) (n→∞) арифметических операций. Таким образом, по трудоёмкости (по числу арифметических операций) метод Гаусса является более экономным, чем метод Жордана.

1 2 3 4

Скачать файл