2. Численные методы решения системы линейных уравнений

2.1. Постановка задачи

Рассмотрим систему линейных алгебраических уравнений: , где матрица m×m, - искомый вектор, - заданный вектор. Будем предполагать, что определитель матрицы отличен от нуля, т.е. решение системы существует.

Методы численного решения системы делятся на две группы: прямые методы («точные») и итерационные методы. Прямыми методами называются методы, позволяющие получить решение системы за конечное число арифметических операций. К этим методам относятся метод Крамера, метод Гаусса, LU-метод и т.д. Итерационные методы (методы последовательных приближений) состоят в том, что решение системы находится как предел последовательных приближений при , где - номер итерации. При использовании методов итерации обычно задается некоторое малое число и вычисления проводятся до тех пор, пока не будет выполнена оценка . К этим методам относятся метод Зейделя, Якоби, метод верхних релаксаций и т.д.

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

В нашем случае необходимо решить следующую систему линейных алгебраических уравнений.

2.2. Метод Гаусса

Запишем систему в развернутом виде:

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

где , , .

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

Описанная процедура называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при условии, что все , не равны нулю.

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

,

Эта процедура получила название обратный ход метода Гаусса.

Метод Гаусса может быть легко реализован на компьютере. При выполнении вычислений, как правило, не интересуют промежуточные значения матрицы . Поэтому численная реализация метода сводится к преобразованию элементов массива размерности (×()), где столбец содержит элементы правой части системы.

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

Один из основных недостатков метода Гаусса связан с тем, что при его реализации накапливается вычислительная погрешность. Для больших систем порядка число действий умножений и делений близко к .

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

Существует метод Гаусса с выбором главного элемента по всей матрице. В этом случае переставляются не только строки, но и столбцы . Использование модификаций метода Гаусса приводит к усложнению алгоритма увеличению числа операций и соответственно к росту времени счета.

Алгоритм Гауссовских преобразований с выбором главного элемента по всей матрице:

1. Выберем ведущий элемент в какой-либо строке (для простоты расчетов лучше, если он будет равен 1).

2. Разделим ведущую строчку на ведущий элемент.

3. Обнулим элементы ведущего столбца

4. Остальные элементы пересчитаем по правилу прямоугольника

Столбец-контроль используется для контроля правильности вычислений. В первой таблице в нем собираются суммы по строкам. Пересчитывается, он также как и все остальные элементы. Если после пересчета в нем все равно остались суммы по строкам, значит, вычисления были проведены верно.

Рисунок 13 – Реализация алгоритма методом Жордана-Гаусса

Опишем механизм создания листа Excel с реализацией метода Гаусса.

На лист Excel занесем значения на начальной итерации. При столбцах х1, х2, х3 запишем основную матрицу системы. В столбце bзапишем столбец свободных коэффициентов. В столбцах «пересчитанная сумма» и «сумма» (они пока не отличаются способом расчета) автосуммируем все значения по строкам исходной матрицы.

На следующих итерациях «пересчитанная сумма» будет пересчитываться так же, как и все остальные элементы, а в «сумме» по-прежнему будут автосуммы по строкам. Если значения в 2 этих столбцах будут равны, значит, вычисления проведены верно.

Приведем пример пересчета элемента 1 (ячейка B3)

В ячейку D3 будет записано значение 43.

Чтобы эффективно использовать формулы Excel, создавая их только один раз, и затем копируя их, будем использовать абсолютные и относительные адреса ячеек. Если в адресе ячейки проставить знаки $ перед строкой или перед столбцом, то имя столбца или номер строки не будут смещаться в направлении копирования при копировании. Используем это свойство для создания рабочих формул Excel. Для перехода между относительными и абсолютными адресами ячеек используем клавишу F4.

Рисунок 14 – Рабочие формулы реализации метода Жордана-Гаусса

Если ведущий элемент не равен 1, то при пересчете возникают дробные значения, поэтому выделим ячейки, содержащие дробные значения и в меню Формат, команда Ячейки выберем вкладку Число и применим Дробный форма. Выберем тип «Дробями до двух цифр» поскольку именно столько цифр было в ведущем элементе, на который делились элементы (в нашем случае ведущий элемент на первой итерации был равен 43).

Рисунок 15 –установка дробного формата.

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

Фактически, на последней итерации получаем точное решение.

Жордано-Гауссовские преобразования избавляют от необходимости ведения обратного хода Гаусса.