Вычисление определителя методом исключения Гаусса

3.4 Вычисление определителя методом исключения Гаусса

Из курса линейной алгебры известно, что определитель треугольной матрицы равен произведению диагональных элементов. В результате метода исключений Гаусса система линейных уравнений (3.2) с квадратной матрицей A приводится к эквивалентной ей системе (3.8) с треугольной матрицей A_n. Поэтому

det A = (–1)^s det A_n,

где s – число перестановок строк, (s = 0, если использовался метод Гаусса по схеме единственного деления).Таким образом,

det A = (–1)^s a₁₁ aa …a  (3.17)

Итак, для вычисления определителя det A необходимо выполнить процедуру прямого хода в методе Гаусса для системы уравнений Ax = 0, затем найти произведение главных элементов, стоящих на диагонали треугольной матрицы и умножить это произведение на (–1)^s, где s – число перестановок строк.

Пример 3.3.

Вычислим определитель det A =

2.0 1.0 0.1 1.0

0.4 0.5 4.0 8.5

0.3 1.0 1.0 5.2

1.0 0.2 2.5 1.0

Данный определитель совпадает с определителем системы, рассмотренной в примере 3.1. Он равен произведению диагональных элементов треугольной матрицы (3.13):

det A = 2.0 × 0.30 × 16.425 × 1.12 = 11.0376.

Если же обратиться к примеру 3.2, то, учитывая, что была одна перестановка строк, т.е. s = 1, получим:

det A = (–1) × 2.0 × (–1.15) × 4.28478 × 1.11998 = 11.0375.

3.5 Вычисление обратной матрицы методом исключения Гаусса

Обратной матрицей к матрице A называется матрица A^-1, для которой выполнено соотношение:

A A^-1 = E, (3.18)

где E – единичная матрица:

1 0 0 … 0 

0 1 0 … 0

E = 0 0 1 … 0 . (3.19)

0 0 0 … 1

Квадратная матрица A называется невырожденной, если det A ¹ 0. Всякая невырожденная матрица имеет обратную матрицу.

Вычисление обратной матрицы можно свести к рассмотренной выше задаче решения системы уравнений.

Пусть A – квадратная невырожденная матрица порядка n:

a₁₁ a₁₂ a₁₃ … a_1n

a₂₁ a₂₂ a₂₃ … a_2n

A = a₃₁ a₃₂ a₃₃ … a_3n  

a_n1 a_n2 a_n3 … a_nn

и A^-1 – ееобратная матрица:

x₁₁ x₁₂ x₁₃ … x_1n

x₂₁ x₂₂ x₂₃ … x_2n

A^-1 =  x₃₁ x₃₂ x₃₃ … x_3n  

x_n1 x_n2 x_n3 … x_nn

Используя соотношения (3.18), (3. 19) и правило умножения матриц, получим систему из n² уравнений с n² переменными x_ij, i, j = 1, 2, …, n. Чтобы получить первый столбец матрицы E, нужно почленно умножить каждую строку матрицы A на первый столбец матрицы A^-1 и приравнять полученное произведение соответствующему элементу первого столбца матрицы E. В результате получим систему уравнений:

a₁₁x₁₁ + a₁₂ x₂₁ + a₁₃x₃₁ + … + a_1nx_n1 = 1

a₂₁x₁₁ + a₂₂ x₂₁ + a₂₃x₃₁ + … + a_2nx_n1 = 0

a₃₁x₁₁ + a₃₂ x₂₁ + a₃₃x₃₁ + … + a_3nx_n1 = 0 (3.20)

a_n1x₁₁ + a_n2 x₂₁ + a_n3x₃₁ + … + a_nnx_n1 = 0

Аналогично, чтобы получить второй столбец матрицы E, нужно почленно умножить каждую строку матрицы A на второй столбец матрицы A^-1 и приравнять полученное произведение соответствующему элементу второго столбца матрицы E. В результате получим систему уравнений:

a₁₁x₁₂ + a₁₂ x₂₂ + a₁₃x₃₂ + … + a_1nx_n2 = 0

a₂₁x₁₂ + a₂₂ x₂₂ + a₂₃x₃₂ + … + a_2nx_n2 = 1

a₃₁x₁₂ + a₃₂ x₂₂ + a₃₃x₃₂ + … + a_3nx_n2 = 0 (3.21)

a_n1x₁₂ + a_n2 x₂₂ + a_n3x₃₂ + … + a_nnx_n2 = 0

и т. д.

Всего таким образом получим n систем по n уравнений в каждой системе, причем все эти системы имеют одну и ту же матрицу A и отличаются только свободными членами. Приведение матрицы A к треугольной по формулам (3.7) делается при этом только один раз. Затем по последней из формул (3.7) преобразуются все правые части, и для каждой правой части делается обратный ход.

Пример 3.4.

Вычислим обратную матрицу A^-1 для матрицы

A = 1.8 –3.8 0.7 –3.7

0.7 2.1 –2.6 –2.8

7.3 8.1 1.7 –4.9

1.9 –4.3 –4.3 –4.7

По формулам (3.7) за три шага прямого хода преобразуем матрицу Aв треугольную матрицу

1.8 –3.8 0.7 –3.7

0 3.57778 –2.87222 –1.36111

0 0 17.73577 19.04992

0 0 0 5.40155

Далее, применим процедуру обратного хода четыре раза для столбцов свободных членов, преобразованных по формулам (3.7) из столбцов единичной матрицы:

1 0 0  0

0 1 0 0

0 , 0 , 1 , 0

0 0 0 1

Каждый раз будем получать столбцы матрицы A^-1. Опустив промежуточные вычисления, приведем окончательный вид матрицы A^-1:

–0.21121 –0.46003 0.16248 0.26956

–0.03533 0.16873 0.01573 –0.08920

0.23030 0.04607 –0.00944 –0.19885 .

–0.29316 –0.38837 0.06128 0.18513

3.6 Метод простой итерации Якоби

Метод Гаусса обладает довольно сложной вычислительной схемой. Кроме того, при вычислениях накапливается ошибка округления, что может привести к недостаточно точному результату. Рассмотрим метод простой итерации Якоби, свободный от этих недостатков, хотя требующий приведения исходной системы уравнений к специальному виду.

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

Ax = b (3.22)

с квадратной невырожденной матрицей A привести к виду

x = Bx + c, (3.23)

где B – квадратная невырожденная матрица с элементами b_ij, i, j = 1, 2, …, n, x – вектор-столбец неизвестных x_i, c – вектор-столбец с элементами c_i, i = 1, 2, …, n.

Существуют различные способы приведения системы (3.22) к виду (3.23). Рассмотрим самый простой. Представим систему (3.22) в развернутом виде:

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂ x₂ + a₂₃x₃ + … + a_2nx_n = b₂

a₃₁x₁ + a₃₂ x₂ + a₃₃x₃ + … + a_3nx_n = b₃ (3.24)

a_n1x₁ + a_n2 x₂ + a_n3x₃ + … + a_nnx_n = b_n

Из первого уравнения системы (3.24) выразим неизвестную 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-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₃  (3.25)

.

x_n=  b_n1x₁ + b_n2 x₂ + b_n3x₃ + b_n,n-1x_n-1 + c_n

Матричная запись системы (3.25) имеет вид (3.23). На главной диагонали матрицы B находятся нулевые элементы, а остальные элементы вычисляются по формулам:

b_ij = , c_i = , i, j = 1,2, …n, i j. (3.26)

Очевидно, что диагональные элементы матрицы A должны быть отличны от нуля.

Выберем произвольно начальное приближение Обычно в качестве первого приближения берут x= c_i или x= 0. Подставим начальное приближение в правую часть (3.25). Вычисляя левые части, получим значения x, x, …, x. Продолжая этот процесс дальше, получим последовательность приближений, причем (k + 1)-е приближение строится следующим образом:

x = b₁₂ x + b₁₃ x + … + b_1,n-1 x + b_1n x + c₁

x = b₂₁ x₁ + b₂₃ x + … + b_2,n-1 x + b_2n x + c₂

x= b₃₁ x + b₃₂ x + … + b_3,n-1 x +b_3n x   + c₃ … (3.27)

x=  b_n1x + b_n2 x + b_n3 x  + b_n,n-1 x  + c._n

Система (3.27) представляет собой расчетные формулы метода простой итерации Якоби.

Сходимость метода простой итерации. Известно следующее достаточное условие сходимости метода простой итерации Якоби.

Если элементы матрицы A удовлетворяют условию:

|a_ii| > , i = 1, 2, …, n. (3.28)

то итерационная последовательность x^k сходится к точному решению x^*.

Условие (3.28) называют условием преобладания диагональных элементов матрицы A, так как оно означает, что модуль диагонального элемента i-ой строки больше суммы модулей остальных элементов этой строки, i = 1, 2, …, n.

Необходимо помнить, что условие сходимости (3.28) является лишь достаточным. Его выполнение гарантирует сходимость метода простых итераций, но его невыполнение, вообще говоря, не означает, что метод расходится.

Справедлива следующая апостериорная оценка погрешности:

max|x - x| £ max|x– x|, i = 1, 2, …, n, (3.29)

где b = max |b_ij| i, j = 1, 2, …, n.

Правую часть оценки (3.29) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.29) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

max|x– x| < e, i = 1, 2, …, n. (3.30)

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

max|x– x| < e₁, i = 1, 2, …, n. (3.31)

где e_{1 =} e_.

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

max|x– x| < e, i = 1, 2, …, n. (3.32)

В других случаях использование критерия (3.32) неправомерно и может привести к преждевременному окончанию итерационного процесса.

Пример 3.5.

Применим метод простой итерации Якоби для решения системы уравнений

20.9x₁ + 1.2x₂ + 2.1x₃ + 0.9x₄ = 21.70

1.2x₁ + 21.2x₂ +  1.5x₃ +  2.5x₄ = 27.46

2.1x₁ + 1.5x₂ + 19.8x₃ + 1.3x₄ = 28.76 (3.33)

0.9x₁ + 2.5x₂ + 1.3x₃ + 32.1x₄ = 49.72

Заметим, что метод простой итерации сходится, т. к. выполняется условие преобладания диагональных элементов (3.28):

|20.9| > |1.2 + 2.1 + 0.9|,

|21.2| > |1.2| + |1.5| + |2.5|,

|19.8| > |2.1| + |1.5| + |1.3|,

|32.1| > |0.9| + |2.5| + |1.3|.

Пусть требуемая точность e = 10^-3. Вычисления будем проводить с четырьмя знаками после десятичной точки.

Приведем систему к виду (3.25):

x₁  = – 0.0574x₂  – 0.1005x₃  – 0.0431x₄ + 1.0383

x₂  = –0.0566x₁ – 0.0708x₃ – 0.1179x₄ + 1.2953

x₃  = –0.1061x₁ – 0.0758x₂  –  0.0657x₄ + 1.4525 (3.34)

x₄  = –0.0280x₁ – 0.0779x₂ – 0.0405x₃ + 1.5489

Величина b = max |b_ij|, i, j = 1, 2, 3,4 равна 0.1179, т. е. выполняется условие b £ , и можно пользоваться критерием окончания итерационного процесса (3.32).

В качестве начального приближения возьмем элементы столбца свободных членов:

x = 1.0383, x = 1.2953, x = 1.4525, x = 1.5489. (3.35)

Вычисления будем вести до тех пор, пока все величины |x– x|, i = 1, 2, 3, 4, а следовательно, и max|x– x| не станут меньше e = 10^-3.

Последовательно вычисляем:

при k = 1

x   = – 0.0574x  – 0.1005x – 0.0431x + 1.0383 = 0.7512

x  = –0.0566x – 0.0708x – 0.1179x + 1.2953 = 0.9511

x  = –0.1061x – 0.0758 x – 0.0657x + 1.4525 = 1.1423

x = –0.0280x – 0.0779x – 0.0405x + 1.5489 = 1.3601

при k = 2

x= 0.8106, x= 1.0118,  x= 1.2117, x= 1.4077.

при k = 3

x= 0.7978, x= 0.9977, x= 1.1975, x= 1.3983.

при k = 4

x= 0.8004, x= 1.0005, x= 1.2005, x = 1.4003.

Вычисляем модули разностей значений xпри k = 3 и k = 4:

| x– x| = 0.026, | x– x| = 0.028, | x– x| = 0.0030, | x– x| = 0.0020.

Так как все они больше заданной точности e = 10^-3, продолжаем итерации.

При k = 5

x= 0.7999, x= 0.9999, x= 1.1999, x = 1.3999.

Вычисляем модули разностей значений xпри k = 4 и k = 5:

| x– x| = 0.0005, | x– x| = 0.0006, | x – x| = 0.0006, | x– x| = 0.0004.

Все они меньше заданной точности e = 10^-3, поэтому итерации заканчиваем. Приближенным решением системы являются следующие значения:

x₁  0.7999, x₂  0.9999, x₃  1.1999, x₄  1.3999.

Для сравнения приведем точные значения переменных:

x₁ = 0.8, x₂ = 1.0, x₃ = 1.2, x₄ = 1.4.

Похожие работы

Лекции по вычислительной математике

Скачать

10356

0

0

... . Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции. Введем некоторые термины. Пусть имеется некоторая чис- ловая матрица. Привести строку этой матрицы означает выде-лить в строке минимальный элемент (его называют константой приведения) ...

Основные задачи вычислительной математики

Скачать

7721

1

1

... если  - предельная абсолютная погрешность приближённого числа , то  (1.2) отсюда следует, что  (1.3) Значение предельной абсолютной погрешности, обычно, подбирается интуитивно по смыслу задачи. Пример 2: Определить предельную абсолютную погрешность числа , заменяющего число , точное значение которого нам неизвестно. Так как мы знаем, что , ...

Выдающиеся личности в истории вычислительной техники. Августа Ада Лавлейс

Скачать

37333

0

0

... удивили меня…, хоть речь идёт обо мне самой. Они действительно написаны прекрасным стилем, который превосходит стиль самого очерка" /2/. 2.3. Рождение первенца и критическое перенапряжение Августа Ада Лавлейс работает с большим напряжением. В письмах к Бэббиджу она неоднократно жалуется на утомление, болезни, плохое самочувствие. Наконец, 6 августа Бэббидж отсылает Аде свои последние замечания ...

Роль женщин в развитии вычислительной техники

Скачать

54819

0

0

... в Украине, бывшем Советском Союзе и за рубежом научная школа теоретического программирования. В 2001-м году ее не стало... Но не только в научном плане велика роль женщин в развитии вычислительной техники. Со временем образуется огромное количество различных фирм по разработке и продаже программного и аппаратного обеспечения. Следовательно, разыгрываются человеческие трагедии капиталистического ...