Алгорифмы решения линейных уравнений

15. Будем интересоваться лишь прямыми методами решения линейных уравнений. Все алгорифмы, которые мы используем, основаны на следующем преобразовании. Если решение системы

где А есть -матрица, то оно будет также решением системы

где любая -матрица. Однако если квадратная и невырожденная, то любое решение (15.2) является решением (15.1), и наоборот. Далее, если также невырожденная и у есть решение

то есть решение (15.1) (ср. гл. 1, § 15). Некоторые из наших алгорифмов будут основаны на использовании этого последнего результата, причем в качестве берется матрица перестановок (гл. 1, § 40 (ii)).

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

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

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

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

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

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

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

Очевидно, что столбец матрицы равен

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