![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Модифицированный метод Гаусса
В данном случае помимо соблюдения требования akk ¹ 0 при реализации формул (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 (e=0, 001)
Блок 1. Ввод исходных данных: n – порядок системы, A – матрица коэффициентов при неизвестных, b – вектор свободных членов. Блок 2. I-й цикл прямого хода (для k, изменяющегося от 1 до предпоследнего значения, т.е. до n –1) обеспечивает исключение из главной диагонали матрицы А элемента akk =0 благодаря поиску максимального элемента akk в текущем столбце, осуществляемому в блоках 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 11 = 2 < a 21 = 4 из (*) Блок 6 p = 2 Блок 4 m = 2+1 = 3 Блок 5 a 21 = 4 < a 31 = 6 из (*) Блок 6 p = 3 Выход из цикла II и вход в цикл III, блоки 7¸ 10 выполняют перестановку строк матрицы А поэлементно Блок 7 j = 1 (j от 1 до 3) Блок 8 r = a 11 = 2 из (*) Блок 9 a 11 = a 31 = 6 Блок 10 a 31 = r Блок 7 j = 2 Блок 8 r = a 12 = 1 Блок 9 a 12 = a 32 = 5 Блок 10 a 32 = r = 1 Блок 7 j = 3 и по аналогии r = a 13; a 13 = a 33; a 33 = r = − 1. Выход из цикла III и вход в Блок 11 и далее 12¸ 13 выполняют аналогичную перестановку значений свободных членов r = b 1 = 1; b 1 = b 3 = 14; b 3 = r = 1. Вход в цикл IV с измененной системой
для пересчета b 2 вектора m = k +1 = 1+1 = 2 до n = 3 c = amk / akk = a 21 / a 11 = 4/6 из (**) b 2 = b 2 – c b 1 = 6 – 4/6 × 14 = − 20/6 из (**) Вход во вложенный цикл V для пересчета второй строки i = 1 (i от 1 до 3); a 21 = a 21 – с × a 11 = 4 – 4/6 × 6 = 0; i = 2; a 22 = a 22 – с × a 12 = 6 – 4/6 × 5 = 16/6; i = 3; a 23 = a 23 – с × a 13 = 2 – 4/6 × 8 = − 20/6. Выход из цикла V и вход в цикл IV m = 3; c = a 31 / a 11 = 2/6. Вход в Блок 16 b 3 = b 3 – c b 1 = 1 – 2/6 × 14 = − 22/6. Выход из цикла IV и вход в цикл V и вход в Блок 17 i = 1 (i от 1 до 3); a 31 = a 31 – с × a 11 = 2 – 2/6 × 6 = 0; i = 2; a 32 = a 32 – с × a 12 = 1 – 2/6 × 5 = − 4/6; i = 3; a 33 = a 33 – с × a 13 = − 1 – 2/6 × 8 = − 22/6. Выход из цикла V с преобразованной системой
и вход по линии А в цикл I k = 2; p = k = 2; m = k +1 = 3; вход в Блок 5 | a 22 | < | a 32 | = | 16/6 | > | 4/6 | из (***). Выход из цикла II и вход в цикл III j = 2 (j от 2 до 3); r = akj = a 22 = 16/6; a 22 = a 22; a 22 = r = 16/6; из (***) j = 3; r = a 23 = − 20/6; a 23 = a 23; a 23 = r = − 20/6; из (***) В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-ой и 3-ей строк не выполняется. Выход из цикла III и вход в цикл I в Блок 11 r = b 2; b 2 = b 2; b 2 = r = − 20/6. Свободный член b 2 остается на своем месте. Вход в цикл IV m = k +1 = 2+1 = 3; c = amk / akk = a 32 / a 22 = (–4/6) / (16/6); из (***) b 3 = b 3 – c b 2 = − 22/6 – (–1/4) × (–20/6) = − 27/6 из (***) Выход из цикла IV и вход в цикл V i = 2 (i от 2 до 3); a 32 = a 32 – с × a 22 = − 4/6 – (–1/4) × 16/6 = 0; i = 3; a 33 = a 33 – с × a 23 = − 22/6 – (–1/4) × (–20/6) = − 27/6. Выход из цикла V и выход из цикла I. Обратный ход метода Гаусса В Блоках 19¸ 24 реализуются формулы (7). В Блоке 19 из последнего уравнения находится значение xn (n = 3) x 3 = bn / ann = b 3 / a 33 = (–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 + aki × xi = 0 + a 23 × x 3 = − 20/6 × 1 = − 20/6. Выход из цикла VII на Блок 24 в цикл VI: k = 2; x 2 = (bk – s)/ ann = (b 2 – s)/ a 22 = (–20/6 +20/6)/ a 22 = 0. Далее по аналогии k = k –1 = 2–1 = 1; s = 0; i = k + 1 = 2; s = 0 + a 12 × x 2 = 5 × 0 = 0; i = k + 1 = 3; s = 0 + a 13 × x 3 = 8 × 1 = 8; x 1 = (b 1 – s)/ a 11 = (14 – 8) / 6 = 1. Выход из последнего цикла VII. В Блоке 25 (цикл опущен) выполняется вывод на экран полученного решения СЛАУ – вектора
|