§ 2. Метод исключения

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

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

Рассмотрим ряд схем, осуществляющих метод исключения на примере системы четырех уравнений с четырьмя неизвестными:

Каждой схеме мы припишем то или иное название. Правда, эти названия не являются общепринятыми.

1. Схема Гаусса с выбором главного элемента.

Если вычисления производятся не с помощью автоматических вычислительных машин, то удобно нашу систему записать в следующую схему:

(см. скан)

В первом столбце мы записываем номера уравнений. Значение второго столбца будет ясно дальше. 3-й, 4-й, 5-й и 6-й столбцы содержат коэффициенты уравнений, а 7-й столбец — свободные члены. Последний столбец содержит суммы коэффициентов и свободных членов данной строки.

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

(см. скан)

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

(см. скан)

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

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

проверку и переходим к следующему шагу. Так продолжаем до тех пор, пока у нас не останется одна строка. В нашем примере будем иметь:

(см. скан)

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

Матрица новой системы треугольная. Решение такой системы не встретит затруднений. Находим:

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

Контроль обратного хода осуществляется с помощью столбца Если в окончательной системе заменить на то должны получить вместо величины Проверка полученных результатов может быть сделана также путем подстановки их в исходную систему уравнений. В нашем случае получим последовательно в левых частях равенства: 1,54711; 1,64712; 1,74710; 1,84711. Как мы видим,

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

Смысл выбора главного элемента состоит в том, чтобы сделать возможно меньшими и тем самым уменьшить вычислительную погрешность.

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

операций умножения и деления. Для обратного хода потребуется

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

операций умножения и деления.