Модифицированный метод Гаусса

В данном случае помимо соблюдения требования a_kk ¹ 0 при реализации формул (6) накладываются дополнительные требования, чтобы ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы имел максимальное по модулю значение. Это также достигается перестановкой строк матрицы.

Пример. В качестве иллюстрации преимущества модифицированного метода Гаусса, рассмотрим систему третьего порядка:

(а)

Прямой ход метода Гаусса

Исключаем х ₁ из второго и третьего уравнений. Для этого первое уравнение умножаем на 0, 3 и складываем со вторым, а затем умножаем первое уравнение на (–0, 5) и складываем с третьим. В результате получаем

(б)

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

Умножая второе уравнение на 25, и складывая с третьим, получим

(в)

Обратный ход метода Гаусса

Выполняем вычисления, начиная с последнего уравнения в полученной системе:

Подставляя полученное решение [0; –1; 1] в исходную систему, убеждаемся в его истинности.

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

(г)

Прямой ход метода для системы (г) повторим по аналогичной технологии с исходной системой (а).

(д)

После исключения х ₂ третье уравнение примет вид (остальные – без изменения)

15005 х ₃ = 15004. (е)

Выполняя обратный ход, получим

Очевидно, что полученные решения [0; –1; 1] и [–0, 35; –1, 4; 0, 99993] различны. Причиной этого является малая величина ведущего элемента во втором уравнении преобразования в (д). Чтобы это исключить, переставим в (д) вторую и третью строки

º (ж)

Для данной системы после исключения х ₂ из третьего уравнения, оно примет следующий вид

6, 002 х ₃ = 6, 002. (з)

В данном случае, выполняя обратный ход

мы получим решение системы (г) [0; –1; 1], которое в точности совпадает с решением исходной системы.

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

Рассмотрим блок-схему модифицированного метода Гаусса (рис. 2.1).

Рис. 2.1. Блок-схема модифицированного метода Гаусса

Проведем анализ предложенной схемы на примере системы n =3 (e=0, 001)

(8)

; . (*)

Блок 1. Ввод исходных данных: n – порядок системы, A – матрица коэффициентов при неизвестных, b – вектор свободных членов.

Блок 2. I-й цикл прямого хода (для k, изменяющегося от 1 до предпоследнего значения, т.е. до n –1) обеспечивает исключение из главной диагонали матрицы А элемента a_kk =0 благодаря поиску максимального элемента a_kk в текущем столбце, осуществляемому в блоках 3¸ 6 с помощью цикла II.

Далее с помощью цикла III в блоках 7¸ 13 выполняется перестановка текущей строки и строки с максимальным элементом в k -ом столбце (ее номер р).

Затем реализуются расчеты по формулам (6) прямого хода Гаусса в блоках циклов IV и V.

Проведем поблочный анализ в среде рассмотренных циклов I¸ V на примере (8).

Блок 3 p = k = 1

Вход в цикл II

Блок 4 m = k +1 = 2 до n = 3

Блок 5 a ₁₁ = 2 < a ₂₁ = 4 из (*)

Блок 6 p = 2

Блок 4 m = 2+1 = 3

Блок 5 a ₂₁ = 4 < a ₃₁ = 6 из (*)

Блок 6 p = 3

Выход из цикла II и вход в цикл III, блоки 7¸ 10 выполняют перестановку строк матрицы А поэлементно

Блок 7 j = 1 (j от 1 до 3)

Блок 8 r = a ₁₁ = 2 из (*)

Блок 9 a ₁₁ = a ₃₁ = 6

Блок 10 a ₃₁ = r

Блок 7 j = 2

Блок 8 r = a ₁₂ = 1

Блок 9 a ₁₂ = a ₃₂ = 5

Блок 10 a ₃₂ = r = 1

Блок 7 j = 3 и по аналогии r = a ₁₃; a ₁₃ = a ₃₃; a ₃₃ = r = − 1.

Выход из цикла III и вход в Блок 11 и далее 12¸ 13 выполняют аналогичную перестановку значений свободных членов

r = b ₁ = 1; b ₁ = b ₃ = 14; b ₃ = r = 1.

Вход в цикл IV с измененной системой

; ; (**)

для пересчета b ₂ вектора

m = k +1 = 1+1 = 2 до n = 3

c = a_mk / a_kk = a ₂₁ / a ₁₁ = 4/6 из (**)

b ₂ = b ₂ – c b ₁ = 6 – 4/6 × 14 = − 20/6 из (**)

Вход во вложенный цикл V для пересчета второй строки

i = 1 (i от 1 до 3); a ₂₁ = a ₂₁ – с × a ₁₁ = 4 – 4/6 × 6 = 0;

i = 2; a ₂₂ = a ₂₂ – с × a ₁₂ = 6 – 4/6 × 5 = 16/6;

i = 3; a ₂₃ = a ₂₃ – с × a ₁₃ = 2 – 4/6 × 8 = − 20/6.

Выход из цикла V и вход в цикл IV

m = 3; c = a ₃₁ / a ₁₁ = 2/6.

Вход в Блок 16

b ₃ = b ₃ – c b ₁ = 1 – 2/6 × 14 = − 22/6.

Выход из цикла IV и вход в цикл V и вход в Блок 17

i = 1 (i от 1 до 3); a ₃₁ = a ₃₁ – с × a ₁₁ = 2 – 2/6 × 6 = 0;

i = 2; a ₃₂ = a ₃₂ – с × a ₁₂ = 1 – 2/6 × 5 = − 4/6;

i = 3; a ₃₃ = a ₃₃ – с × a ₁₃ = − 1 – 2/6 × 8 = − 22/6.

Выход из цикла V с преобразованной системой

; ; (***)

и вход по линии А в цикл I

k = 2; p = k = 2; m = k +1 = 3; вход в Блок 5

| a ₂₂ | < | a ₃₂ | = | 16/6 | > | 4/6 | из (***).

Выход из цикла II и вход в цикл III

j = 2 (j от 2 до 3);

r = a_kj = a ₂₂ = 16/6; a ₂₂ = a ₂₂; a ₂₂ = r = 16/6; из (***)

j = 3;

r = a ₂₃ = − 20/6; a ₂₃ = a ₂₃; a ₂₃ = r = − 20/6; из (***)

В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-ой и 3-ей строк не выполняется.

Выход из цикла III и вход в цикл I в Блок 11

r = b ₂; b ₂ = b ₂; b ₂ = r = − 20/6.

Свободный член b ₂ остается на своем месте.

Вход в цикл IV

m = k +1 = 2+1 = 3;

c = a_mk / a_kk = a ₃₂ / a ₂₂ = (–4/6) / (16/6); из (***)

b ₃ = b ₃ – c b ₂ = − 22/6 – (–1/4) × (–20/6) = − 27/6 из (***)

Выход из цикла IV и вход в цикл V

i = 2 (i от 2 до 3); a ₃₂ = a ₃₂ – с × a ₂₂ = − 4/6 – (–1/4) × 16/6 = 0;

i = 3; a ₃₃ = a ₃₃ – с × a ₂₃ = − 22/6 – (–1/4) × (–20/6) = − 27/6.

Выход из цикла V и выход из цикла I.

Обратный ход метода Гаусса

В Блоках 19¸ 24 реализуются формулы (7).

В Блоке 19 из последнего уравнения находится значение x_n (n = 3)

x ₃ = b_n / a_nn = b ₃ / a ₃₃ = (–27/6) / (–27/6) = 1.

Вход в цикл VI (Блок 20), в котором значение переменной цикла k изменяется от n –1 до 1 с шагом (–1)

Блок 21 s = 0

Вход в цикл VII (Блок 22)

i = k +1 = 2+1 = 3; n = 3; s = s + a_ki × x_i = 0 + a ₂₃ × x ₃ = − 20/6 × 1 = − 20/6.

Выход из цикла VII на Блок 24 в цикл VI:

k = 2; x ₂ = (b_k – s)/ a_nn = (b ₂ – s)/ a ₂₂ = (–20/6 +20/6)/ a ₂₂ = 0.

Далее по аналогии

k = k –1 = 2–1 = 1;

s = 0;

i = k + 1 = 2; s = 0 + a ₁₂ × x ₂ = 5 × 0 = 0;

i = k + 1 = 3; s = 0 + a ₁₃ × x ₃ = 8 × 1 = 8;

x ₁ = (b ₁ – s)/ a ₁₁ = (14 – 8) / 6 = 1.

Выход из последнего цикла VII.

В Блоке 25 (цикл опущен) выполняется вывод на экран полученного решения СЛАУ – вектора т.е. x_i, i =1,..., n. В нашем случае (1; 0; 1).