2. Метод исключения Гаусса.

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

или короче

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

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

если

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

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

Запишем общие формулы процесса. Пусть проведено исключение коэффициентов из столбца.

Тогда остались такие уравнения с ненулевыми элементами ниже главной диагонали:

Умножим k-ю строку на число

и вычтем из строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

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

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

Треугольная система (6) легко решается обратным ходом по формулам (2), в которых всем коэффициентам надо приписать вверху (в скобках) индекс строки.

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

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

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

Для контроля расчета полезно найти невязки.

(7)

Если они велики, то это означает грубую ошибку в расчете (ошибка в программе, сбой ЭВМ). Если они малы, а система хорошо обусловлена, то решение найдено достаточно аккуратно. Правда, для плохо обусловленных систем малость невязок не гарантирует хорошей точности решения.

Метод Гаусса с выбором главного элемента надежен, прост и наиболее выгоден для линейных систем общего вида с плотно заполненной матрицей. Он требует примерно ячеек в оперативной памяти ЭВМ, так что на БЭСМ-4 можно решать системы до 60 порядка. При вычислениях производится арифметических действий; из них половина сложений, половина умножений и делений.