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

В данном случае помимо соблюдения требования 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).

Метод прогонки

Данный метод также является модификацией метода Гаусса для частного случая разреженных систем – систем с матрицей трехдиагонального типа (краевая задача ДУ).

Каноническая форма их записи

a_ix_i–1 + b_ix_i + c_ix_i+1 = d_i; i= ; a₁ = c_n = 0, (9)

или в развернутом виде

b₁x₁ + c₁x₂ = d₁;

a₂x₁ + b₂x₂ + c₂x₃ = d₂;

a₃x₂ + b₃x₃ + c₃x₄ = d₃;

. . . (10)

a_n–1x_n–2 + b_n–1x_n–1 + c_n–1x_n = d_n–1;

a_nx_n–1 + b_nx_n = d_n .

При этом, как правило, все коэффициенты b_i ¹ 0.

Метод реализуется в два этапа – прямой и обратный ходы.

Прямой ход. Каждое неизвестное x_i выражается через x_i+1

x_i = A_i × x_i+1+ B_i для i = 1,2, ..., n–1, (11)

посредством прогоночных коэффициентов A_i и B_i. Определим алгоритм их вычисления.

Из первого уравнения системы (10) находим x₁

.

Из уравнения (11) при i=1: x₁= A₁× x₂+ B₁ . Следовательно

. (12)

Из второго уравнения системы (10) определяем x₂ через x₃, подставляя найденное значение x₁

а₂( A₁ x₂+ B₁) + b₂ x₂ + c₂ x₃ = d₂ ,

откуда

; (12*)

и согласно (11) при i = 2: x₂= A₂× x₃+ B₂ , следовательно

, где е₂= а₂× А₁+ b₂ .

Ориентируясь на соотношения индексов при коэффициентах (12) и (12*) можно получить эти соотношения для общего случая

, где е_i = а_i × А_i–1+ b_i (i=2,3, ..., n–1) . (13)

Обратный ход. Из последнего уравнения системы (10) с использованием (11) при i = n–1

. (14)

Далее посредством (11) и прогоночных коэффициентов (12), (13) последовательно вычисляем x_n–1, x_n–2, ..., x₁.

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

| b_i | ³ | a_i | + | c_i | , (15)

или хотя бы для одного b_i имеет место строгое неравенство (15), деление на «0» исключается и система имеет единственное решение.

Заметим, что условие (15) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем (10) метод прогонки может быть устойчивым и при несоблюдении условия (15).

Схема алгоритма метода прогонки может иметь вид, представленный на рис. 2.2.

Рис. 2.2. Блок-схема метода прогонки