КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Решение систем линейных уравнений методом Гаусса
Метод Гаусса является точным методом. Он позволяет получить решение системы за конечное число арифметических действий. В основе метода лежит идея последовательного исключения неизвестных. Метод состоит из двух этапов. На первом этапе (прямой ход) система при помощи последовательного исключения неизвестных приводится к треугольному виду. На втором этапе (обратный ход) из системы треугольного вида последовательно, в обратном порядке, начиная c n-го уравнения, находятся неизвестные системы.
В качестве примера возьмем систему 4 порядка. (9.1) Прямой ход. На первом шаге прямого хода (к=1) находим x1 из первого уравнения системы (9.1).
- ведущий элемент первой строки.
Если , то (9.2)
Обозначим: (9.3)
Подставляя (9.3) в (9.2), получим (9.4) где Подставляем (9.4) во 2, 3 и 4 уравнение системы (9.1), получим: Обозначив коэффициенты при неизвестных полученной системы через , а свободные члены через перепишем полученную систему: (9.5) где Таким образом, в результате выполнения первого шага прямого хода исходная система (9.1) n-го порядка преобразована к совокупности уравнения (9.4) и системы линейных уравнений (9.5), порядок которой равен n-1.
На втором шаге прямого хода (к=2) из первого уравнения системы (9.5) находим x2.
-ведущий элемент первой строки системы (9.5).
Если , то из первого уравнения системы (9.5) имеем: (9.6) где Подставив выражение (9.6) во второе и третье уравнения системы (9.5), получим новую систему линейных уравнений, порядок которой равен n-2. (9.7)
где
Таким образом, в результате выполнения второго шага прямого хода исходная система (9.1) преобразована к совокупности уравнений (9.4), (9.6) и системы линейных уравнений (9.7),порядок которой равен n-2.
На третьем шаге прямого хода (к=3) из системы (9.7) находим x3.
- ведущий элемент системы (9.7).
Если , то из первого уравнения системы (9.7) имеем: (9.8) где
Подставив выражение (9.8) для x3 во второе уравнение системы (9.7) получим: (9.9) где
На последнем шаге прямого хода, если то из уравнения (9.9) имеем: (9.10) где (9.11)
В результате выполнения всех шагов прямого хода исходная система (9.1) приводится к системе треугольного вида, полученной объединением уравнений (9.4), (9.6), (9.8), (9.10): (9.12)
При построении алгоритма прямого хода вычисление организуем в цикле по шагам, т.е. .
Последний n-й шаг прямого хода выведем из цикла т.к. здесь реализуется только одно вычисление (9.13)
В процессе выполнения всех шагов прямого хода все преобразования коэффициентов и свободных членов проводим по полученным ранее рекуррентным формулам: (9.14) где
– номер шага прямого хода,
- номер уравнения систем (9.5), (9.7)
.
В процессе обратного хода из системы (9.12) неизвестные находятся в обратном порядке. Значение корня х4 находят из последнего уравнения системы (9.12). Далее х4 используется для отыскания корня х3 из 3-го уравнения, далее х3 и х4 используются отыскания х2 из 2-го уравнения системы (9.12), и, наконец, х2, х3 и х4 используются для отыскания х1 из 1-го уравнения системы (9.12).
Все вычисления обратного хода проводим в цикле по i, где по рекуррентным формулам: xi= bi.
Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующим недостатком: если ведущий элемент akk какой-либо строки окажется равным нулю, то этот метод формально непригоден, хотя система может иметь единственное решение. Из этих соображений в схеме алгоритма добавлен поиск ненулевого ведущего элемента.
На рисунке 9.1 представлена укрупнённая схема алгоритма (блок-схема) метода Гаусса. На рисунках 9.2 - 9.6 представлены алгоритмы отдельных блоков метода.
Рис. 9.1. Укрупнённая схема алгоритма (блок-схема) метода Гаусса
Блок 2. С помощью двух вложенных циклов с управляющими переменными i=1,n и j=1,k организуем ввод коэффициентов ai,j и свободных членов bi исходной системы. Для того, чтобы в дальнейшем можно было выполнить в блоке 9 проверку результата, в алгоритме предусмотрено сохранение значений ai,j и bi исходной системы с помощью переприсвоений: cij=aij и di=bi
Рис. 9.2.
Блок 3. Организуем цикл по k, внутри которого производится вычисление по всем шагам прямого хода. Последний п-й шаг прямого хода выводим из цикла.
Блок 4. На каждом шаге прямого хода выполняем поиск ненулевого ведущего элемента.
Рис. 9.3.
Поиск ненулевого ведущего элемента ведётся в следующем порядке:
а) На каждом k-ом шаге прямого хода ведущий элемент каждой строки сравнивается с нулём;
б) Если в k-ой строке имеется нулевой ведущий элемент, то в k-ом столбце в цикле осуществляется поиск ненулевого элемента.
в) Если в какой-то строке kn такой ненулевой элемент найден, то строки kn и k поэлементно, в цикле по k1=(k+1),n, меняем местами. Для перестановки элементов используется рабочая переменная R.
г) Если ненулевой ведущий элемент не найден, то коду ошибки kо присваиваем значение 1 и расчёт прекращается.
Блок 5 - шаг прямого хода. На каждом шаге прямого хода проводим исключение неизвестных путём преобразования коэффициентов и свободных членов системы по полученным ранее рекуррентным формулам.
Рис. 9.4.
Блок 6. В этом блоке выведем из цикла по k последний шаг прямого хода, т.к. на этом шаге не нужны преобразования коэффициентов и свободных членов, а реализуется только одно вычисление
xn=bn/an,n
Блок 7 - обратный ход. В процессе обратного хода метода Гаусса из системы треугольного вида последовательно в обратном порядке в цикле по i=(n-1),1,-1 находим неизвестные системы по рекуррентной формуле
bi= bi – xj.ai,j, i=(n-1),1, j=(n+1),n.
При этом в цикле по j=(i+1),n использован приём последовательного вычитания xj.ai,j из bi,после чего вводится переприсвоение bi =хi.
Рис. 9.5.
Блок 9 - проверка результата. В этом блоке подставляя значения полученных неизвестных в исходную систему и используя сохранённые значения коэффициентов системы ci,j и свободных членов di, проводим проверку решения задачи по формуле
Если корни системы найдены, то Fi – это число, близкое к нулю.
Блок 9 в алгоритме метода Гаусса рекомендуется использовать только в процессе отладки метода.
В дальнейшем, при использовании метода Гаусса при решении различных прикладных задач, особенно в тех случаях, когда метод Гаусса используется внутри другого метода, блок 9 можно опустить, а в блоке 2 при вводе данных исходные значения коэффициентов системы и её свободных членов можно не сохранять.
Рис. 9.6.
Дата добавления: 2014-01-14; Просмотров: 448; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |