ГЛАВА 2. ЗАДАЧИ ЛИНЕЙНОЙ АЛГЕБРЫ

2.1. Метод Гаусса с выбором главного элемента для решения СЛАУ

В линейной алгебре рассматриваются четыре класса основных задач: решение систем линейных алгебраических уравнений (СЛАУ), вычисление определителей, нахождение обратных матриц, определение собственных значений и собственных векторов матриц. Все эти задачи имеют важное прикладное значение при решении различных проблем науки и техники. Кроме того, задачи линейной алгебры являются вспомогательными при реализации многих алгоритмов вычислительной математики, математической физики, обработки результатов экспериментальных исследований. Необходимо решить СЛАУ

где неизвестные величины; заданные элементы расширенной матрицы системы уравнений.

Для решения СЛАУ применяют в основном два класса методов: прямые и итерационные. Прямые методы являются универсальными и применяются для решения систем сравнительно невысокого порядка [1]. Итерационные методы выгодно использовать для СЛАУ высокого порядка со слабо заполненными матрицами.

Метод Гаусса относится к прямым методам. Алгоритм метода состоит из двух этапов. Первый этап называется прямым ходом метода и заключается в последовательном исключении неизвестных из уравнений, начиная с

Из первого уравнения системы (2.1) выражаем неизвестное

что возможно при в противном случае надо осуществить перестановку уравнений системы. Согласно формуле (2.2) необходимо каждый элемент первой строки расширенной матрицы СЛАУ поделить на диагональный элемент

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

В результате исключения первого неизвестного из всех уравнений все элементы первого столбца преобразований матрицы будут равны нулю, кроме

Неизвестное выразим из второго уравнения системы и исключим из остальных уравнений и т.д. В результате получим СЛАУ с верхней треугольной матрицей, у которой все элементы ниже главной диагонали равны нулю.

Запишем выражения для неизвестных и преобразования эелементов расширенной матрицы системы, которые обобщают формулы (2.2) - (2.4):

Второй этап решения СЛАУ называется обратным ходом метода Гаусса и состоит в последовательном определении неизвестных по первой формуле (2.5), начиная с неизвестного и заканчивая

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

Количество арифметических операций в методе Гаусса связано с размерностью системы и примерно равно [1]. Контроль полученных решений можно провести путем их подстановки в исходную СЛАУ и вычисления невязок разностей между правыми и левыми частями уравнений:

При малой погрешности решений величины будут близки к нулю.

Рис. 2.1. Блок-схема программы решения СЛАУ методом Гаусса

Программу решения СЛАУ методом Гаусса составим из трех блоков (рис. 2.1). В блоке 0 (основная программа) задаем порядок системы и обращаемся к блоку 1, в котором определяются элементы расширенной матрицы СЛАУ. Затем обращаемся к блоку 2, где реализована программа метода Гаусса. После этого выводим на дисплей результаты решения СЛАУ либо сообщение о том, что решения не существует в случае вырожденной матрицы

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

Блок 2 представляет собой программу метода Гаусса, которая состоит из программы прямого и обратного ходов. В процессе прямого хода осуществляется перестановка строк матрицы с целью выбора главных элементов столбцов.

В программе прямой ход занимает строки 200-320, обратный ход - 330-390, выбор главных элементов - 220-270. Цикл в строке 280 реализует выполнение второй формулы (2.5), двойной цикл в строках 290-310 - третьей формулы (2.5). При этом для экономии времени выполнения алгоритмов преобразования проводим только с теми элементами верхней треугольной матрицы, которые будут отличными от нуля.

В программе несколько иначе реализован обратный ход из-за того, что на Фортране любой цикл выполняется, по крайней мере, один раз.

Особенностью программы на языке Паскаль является введение новых типов переменных МАТ и VEC для матрицы А и вектора результатов X. Такое введение необходимо потому, что переменные являются формальными и фактическими параметрами процедур.

Для контроля и отладки программ решим систему уравнений

в результате получим

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

(см. скан)

(см. скан)

(см. скан)

(см. скан)