Общие сведения о линейных уравнениях

Самое простое уравнение — это линейное уравнение с од­ной переменной вида:

. (3.1)

Обобщением таких уравнений является линейное уравнение с несколькими переменными вида:

. (3.2)

Многие задачи сводятся к решению конечного множества уравнений вида (3.2), то есть системы линейных уравнений. В общем виде система n линейных уравнений с n переменными , записывается как совокупность числовых равенств:

(3.3)

Коэффициенты a_ij системы для их упорядочения снабжаются двумя индексами, причем индекс соответствует номеру строки, а - номеру столбца (). Тогда свободный член запишется в виде , а переменная - . Будем далее считать, что упорядоченные наборы чисел берутся из множества действительных чисел . Решением системы (3.3) уравнений с переменными называют упорядоченную совокупность чисел . являющуюся решением каждого из уравнений, входящих в систему. Ясно, что эта совокупность чисел при подстановке ее в систему (3.3) вместо обращает каждое уравнение системы в истинное числовое равенство. Таким образом, множество решений системы является пересечением множеств решений, входящих в систему уравнений.

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

(3.4)

и трех линейных уравнений с тремя переменными:

(3.5)

Решением системы (3.4) является упорядоченная пара чисел , а решением системы (3.5) — упорядоченная тройка чисел .

Известно, что исследование и нахождение решения для систем (3.4) и (3.5) не представляют особых трудностей. Но задачи практического содержания сводятся к исследованию и решению систем линейных уравнений, содержащих десятки, сотни и даже тысячи переменных. Число элементарных операций при решении линейных систем с n переменными пропорционально примерно , поэтому решение таких задач стало возможным только с появлением быстродействующих ЭВМ.

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

Методы решения систем линейных уравнений можно разделить на две группы: точные и итерационные (приближенные) методы.

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

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

Метод Гаусса

Пусть дана система n линейных уравнений с n переменными:

Коэффициенты при переменных будем рассматривать как элементы двумерного массива , а свободные члены - как элементы одномерного массива . Решение разместим в одномерном массиве . Коэффициенты а_ij и свободные члены будем рассматривать как элементы расширенной матрицы

.

Предписываемые методом Гаусса преобразования будем выполнять над элементами расширенной матрицы. Опишем формально алгоритм решения линейной системы методом Гаусса без выбора главного элемента.

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

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

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

4. Элементы -й строки делим на и в результате получаем:

На этом закончился прямой ход метода Гаусса.

5. Выполняем обратный ход метода Гаусса: в ( )-ю строку последней матрицы подставляем значение и находим значение , затем последовательно находим по формулам:

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

Значения переменных присваиваются элементам массива свободных членов .

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

Метод вращения является разновидностью метода Гаусса. Он обладает повышенной устойчивостью к «провалам» промежуточных вычислений. Этот метод обеспечивает приведение исходной системы к системе с верхней треугольной матрицей (см. литературу).

Правило Крамера

Правило Крамера рассмотрим на примере двух линейных уравнений с двумя переменными:

(3.6)

хотя оно применимо и для решения системы n линейных уравнений с n переменными, но с увеличением n требует большого объема вычислительной работы.

Умножим первое уравнение системы (3.6) на коэффициент а₂₂, а второе — на — a₁₂ и полученные уравнения сложим. Тогда имеем:

Если , то получаем значение переменной

Аналогично, умножая первое уравнение системы (3.6) на - , второе - на и складывая их, получаем:

Введем обозначения:

;

;

.

Следовательно, — определитель матрицы коэффициентов системы (3.6). Определитель получается из определителя , если коэффициенты системы (3.6) при (первый столбец матрицы ) заменить свободными членами

;

Определитель — если заменить коэффициенты системы (3.6) при (второй столбец матрицы ) свободными членами.

Определитель называется главным определителем системы (3.6), а определители и — вспомогательными.

Если главный определитель , то матрица называется неособенной, в противном случае - особенной.

Таким образом, если главный определитель системы уравнений (3.6) , то система имеет единственное решение, определяемое формулами

(3.7)

Формулы (3.7) называются формулами Крамера.

Нахождение решения линейной системы (3.6) по формулам (3.7) называется правилом Крамера, который одним из первых пришел к понятию определителя и доказал сформулированное выше предложение.

Справедливы также следующие два предложения:

1. Если главный определитель системы (3.6) , но хотя бы один из вспомогательных определителей или отличен от нуля, то система (3.6) не имеет решений (система несовместна).

2. Если все три определителя , и системы (3.6) равны нулю, но среди коэффициентов есть хотя бы один, отличный от нуля, то система (3.6) имеет бесконечное множество решений.

Легко дать геометрическое истолкование этим предложениям. Поскольку каждому уравнению системы (3.6) в плоскости соответствует некоторая прямая, то система (3.6) имеет единственное решение, если прямые имеют одну общую точку; не имеет решений, если прямые параллельны; и имеет бесконечное множество решений, если прямые сливаются.

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

,

а по схеме единственного деления метода Гаусса:

.

Для сравнения объема вычислительной работы по этим двум алгоритмам подсчитаем количество операций:

Таблица 3.1 - Количество операций для методов

	по Крамеру	по Гауссу
при
при	360*106

Поэтому все современные ЭВМ имеют стандартные подпрограммы, реализующие различные модификации метода Гаусса.