4. Модифицированный метод Гаусса
В данном случае помимо соблюдения требования akk0 при реализации формул (6) накладываются дополнительные требования, чтобы ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы имел максимальное по модулю значение. Это также достигается перестановкой строк матрицы.
Пример. В качестве иллюстрации преимущества модифицированного метода Гаусса, рассмотрим систему третьего порядка:
Прямой ход метода Гаусса
Исключаем х1из второго и третьего уравнений. Для этого первое уравнение умножаем на 0,3 и складываем со вторым, а затем умножаем первое уравнение на (–0,5) и складываем с третьим. В результате получаем
Замена второго уравнения третьим не производится, т.к. вычисления выполняются в рамках точной арифметики.
Умножая второе уравнение на 25, и складывая с третьим, получим
Обратный ход метода Гаусса
Выполняем вычисления, начиная с последнего уравнения в полученной системе:
Подставляя полученное решение [0; –1; 1] в исходную систему, убеждаемся в его истинности.
Теперь изменим коэффициенты системы таким образом, чтобы сохранить прежнее решение, но при вычислении будем использовать округления в рамках арифметики с плавающей точкой сохраняя пять разрядов. Этому будет соответствовать следующая система
Прямой ход метода для системы (г) повторим по аналогичной технологии с исходной системой (а).
После исключения х2третье уравнение примет вид (остальные – без изменения)
15005 х3= 15004. (е)
Выполняя обратный ход, получим
Очевидно, что полученные решения [0; –1; 1] и [–0,35; –1,4; 0,99993] различны. Причиной этого является малая величина ведущего элемента во втором уравнении преобразования в (д). Чтобы это исключить, переставим в (д) вторую и третью строки
Для данной системы после исключения х2из третьего уравнения, оно примет следующий вид
6,002 х3= 6,002. (з)
В данном случае, выполняя обратный ход
мы получим решение системы (г) [0; –1; 1], которое в точности совпадает с решением исходной системы.
Решая систему (г) мы использовали модифицированный метод Гаусса, в котором на диагонали должен был находиться максимальный в текущем столбце элемент.
Рассмотрим блок-схему модифицированного метода Гаусса (рис. 2.1).
Рис. 2.1. Блок-схема модифицированного метода Гаусса
Проведем анализ предложенной схемы на примере системы n=3 (=0,001)
Блок 1. Ввод исходных данных:n– порядок системы,A– матрица коэффициентов при неизвестных,b– вектор свободных членов.
Блок 2.I-й цикл прямого хода (дляk, изменяющегося от 1 до предпоследнего значения, т.е. доn–1) обеспечивает исключение из главной диагонали матрицыАэлементаakk=0 благодаря поиску максимального элементаakkв текущем столбце, осуществляемому в блоках 36 с помощью циклаII.
Далее с помощью цикла IIIв блоках 713 выполняется перестановка текущей строки и строки с максимальным элементом вk-ом столбце (ее номерр).
Затем реализуются расчеты по формулам (6) прямого хода Гаусса в блоках циклов IVиV.
Проведем поблочный анализ в среде рассмотренных циклов IVна примере (8).
Блок3p =k = 1
Блок4m =k+1 = 2 доn = 3
Блок6p= 2
Блок4m= 2+1 = 3
Блок6p= 3
Выход из цикла IIи вход в циклIII, блоки 710 выполняют перестановку строк матрицыАпоэлементно
Блок7j= 1 (jот 1 до 3)
Блок 8 r = a11 = 2 из (*)
Блок 9 a11 = a31 = 6
Блок 10 a31 = r
Блок 7 j = 2
Блок 8 r = a12 = 1
Блок 9 a12 = a32 = 5
Блок 10 a32 = r = 1
Блок7j= 3 и по аналогииr=a13;a13=a33;a33=r= −1.
Выход из цикла IIIи вход вБлок11 и далее 1213 выполняют аналогичную перестановку значений свободных членов
Вход в цикл IVс измененной системой
для пересчета b2вектора
m=k+1 = 1+1 = 2 доn= 3
c = amk / akk = a21 / a11 = 4/6 из (**)
Вход во вложенный цикл Vдля пересчета второй строки
i = 1 (i от 1 до 3); a21 = a21 – с a11 = 4 – 4/6 6 = 0;
i = 2; a22 = a22 – с a12 = 6 – 4/6 5 = 16/6;
i = 3; a23 = a23 – с a13 = 2 – 4/6 8 = −20/6.
Выход из цикла Vи вход в циклIV
Вход в Блок16
Выход из цикла IVи вход в циклVи вход вБлок17
i = 1 (i от 1 до 3); a31 = a31 – с a11 = 2 – 2/6 6 = 0;
i = 2; a32 = a32 – с a12 = 1 – 2/6 5 = −4/6;
i = 3; a33 = a33 – с a13 = −1 – 2/6 8 = −22/6.
Выход из цикла Vс преобразованной системой
и вход по линии Ав циклI
k = 2;p =k = 2;m =k+1 = 3; вход вБлок5
Выход из цикла IIи вход в циклIII
j = 2 (j от 2 до 3);
r = akj = a22 = 16/6; a22 = a22 ; a22 = r = 16/6; из (***)
В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-ой и 3-ей строк не выполняется.
Выход из цикла IIIи вход в циклIвБлок11
Свободный член b2остается на своем месте.
m=k+1 = 2+1 = 3;
c = amk / akk = a32 / a22 = (–4/6) / (16/6); из (***)
Выход из цикла IVи вход в циклV
i = 2 (i от 2 до 3); a32 = a32 – с a22 = −4/6 – (–1/4) 16/6 = 0;
Выход из цикла Vи выход из циклаI.
Обратный ход метода Гаусса
В Блоках1924 реализуются формулы (7).
В Блоке19 из последнего уравнения находится значениеxn(n= 3)
Вход в цикл VI(Блок20), в котором значение переменной циклаkизменяется отn–1 до 1 с шагом (–1)
Вход в цикл VII(Блок22)
i = k+1 = 2+1 = 3; n = 3; s = s + aki xi = 0 + a23 x3 = −20/6 1 = −20/6.
Выход из цикла VIIнаБлок24 в циклVI:
k = 2; x2 = (bk – s)/ ann = (b2 – s)/ a22 = (–20/6 +20/6)/ a22 = 0.
Далее по аналогии
k=k–1 = 2–1 = 1;
i = k + 1 = 2; s = 0 + a12 x2 = 5 0 = 0;
i = k + 1 = 3; s = 0 + a13 x3 = 8 1 = 8;
Выход из последнего цикла VII.
В Блоке25 (цикл опущен) выполняется вывод на экран полученного решения СЛАУ – вектора т.е.xi,i=1, . n. В нашем случае (1; 0; 1).
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.