4.4. Решение системы линейных уравнений

В процессе решения системы нелинейных уравнений (4.3.1) на каждой итерации требуется решать систему линейных алгебраических уравнений

для неизвестных величин . Если вернуться к системе уравнений (4.3.3), то из нее система (4.4.1) получена путем обозначения через через — через b. Для удобства записи системы уравнений коэффициенты представим в виде квадратной матрицы А, неизвестные и правые части b представим в виде матриц-столбцов . В матричной записи система линейных уравнений (4.4.1) имеет вид

(4.4.2)

Система (4.4.1) имеет единственное решение, если определитель матрицы А отличен от нуля. Существует много методов решения системы уравнений (4.4.1). Некоторые методы рассчитаны на матрицы А специального вида (трехдиагональные, симметричные, разреженные). При выполнении операций над геометрическими объектами матрица А имеет общий вид. Все методы решения систем линейных алгебраических уравнений условно можно разделить на две группы: прямые методы и итерационные методы. В прямых методах решение находится за конечное число арифметических действий. В итерационных методах решение находится как предел последовательных приближений искомых функций . Как правило, прямые методы быстрее и с большей надежностью дают решение системы, но итерационные методы требуют во много раз меньше памяти во время вычислений. Эти обстоятельства играют главную роль при выборе метода решения.

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

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

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

которая получена из единичной матрицы Е перестановкой в ней 1-й и строк. В процессе решения системы уравнений будут меняться местами строки матрицы. В конце процесса исключения неизвестных матрица А будет раз умножена на элементарные матрицы перестановки, т. е. фактически мы будем работать не с матрицей А, а с матрицей , где Р — произведение элементарных матриц перестановки. У матриц перестановки в каждой строке и каждом столбце только один элемент отличен от нуля и равен единице. Элементарные матрицы перестановки определяются в процессе исключения неизвестных. Для упрощения записи через в дальнейшем будем обозначать коэффициенты матрицы , а через А в дальнейшем будем обозначать матрицу . Другими словами, будем считать, что нам заранее известен способ перестановки уравнений системы (4.4.1), позволяющий избежать появление нулевых элементов на диагонали матрицы в процессе исключения неизвестных. Умножение произвольной матрицы на элементарную матрицу перестановки изменяет знак определителя матрицы, сохраняя значение определителя.

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

(4.4.3)

где

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

где

Таким образом, от системы (4.4.1) мы перейдем к эквивалентной ей системе уравнений

в которой только первое уравнение содержит неизвестную

Если бы из остальных уравнений удалось найти , то неизвестная определилась бы равенством . Матрицу системы уравнений (4.4.5) обозначим через Рассмотрим систему уравнений (4.4.5) без первого уравнения. Она аналогична системе (4.4.1), только содержит на одно уравнение меньше и меньше на одну неизвестную величину

(4.4.6)

С системой (4.4.6) поступим аналогично тому, как мы от системы (4.4.1) перешли к системе (4.4.5). В результате придем к системе уравнений

(4.4.7)

где

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

которая эквивалентна исходной системе (4.4.1). Таким образом, мы перешли от системы уравнений (4.4.2) к системе

(4.4.9)

Матрица U системы (4.4.8) содержит нули под главной диагональю и поэтому называется верхней треугольной матрицей.

На главной диагонали этой матрицы стоят единицы. Коэффициенты матрицы вычисляются строка за строкой

Алгоритм вычисления коэффициентов матрицы U по коэффициентам матрицы А выражается формулами

(4.4.10)

к которым нужно добавить поиск максимального коэффициента и перестановку уравнений. Будем считать, что перестановка уравнений на каждом шаге выполняется описанным выше способом. Алгоритм вычисления правой части у по коэффициентам матрицы А и b выражается формулами

(4.4.11)

Процесс перехода от системы (4.4.1) к системе (4.4.8) называется прямым ходом метода Гаусса. Обратным ходом метода Гаусса называется процесс определения неизвестных из системы (4.4.8). Это легко сделать, определяя последовательно, начиная с последнего неизвестного и используя соотношение

(4.4.12)

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

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

Перепишем систему, переставив местами 1-е и неизвестное во всех уравнениях:

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

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

Метод разложения матрицы.

Систему линейных алгебраических уравнений (4.4.1) можно решить методом разложения матрицы А в произведение верхней треугольной матрицы U и нижней треугольной матрицы L. Предположим, что имеет место разложение

(4.4.14)

тогда система (4.4.2) примет вид

(4.4.15)

и ее можно заменить двумя уравнениями

(4.4.16)

Из уравнения (4.4.16) с нижней треугольной матрицей L прямой подстановкой, начиная с первого элемента, легко находится матрица-столбец у, а из уравнения (4.4.17) с верхней треугольной матрицей U подстановкой, начиная с последнего элемента, легко находится матрица-столбец неизвестных Вычисления выполняются по формулам

(4.4.18)

Остается только получить разложение (4.4.14).

Фактически при выполнении исключения неизвестных в методе Гаусса неявно выполняется разложение матрицы А в произведение нижней треугольной матрицы L и верхней треугольной матрицы U.

Матрицу U мы получаем в явном виде с помощью формул (4.4.10); из этих же формул можно в явном виде получить матрицу L. Переход от системы уравнений (4.4.1) к эквивалентной ее системе (4.4.5) в матричном виде можно представить как умножение уравнения (4.4.2) слева на матрицу

(4.4.20)

где матрица имеет коэффициенты

Переход от системы уравнений (4.4.5) к эквивалентной ее системе (4.4.7) в матричном виде можно представить как умножение уравнения (4.4.20) слева на матрицу

(4.4.21)

где матрица имеет коэффициенты

На шаге исключения метода Гаусса система уравнений, полученная на предыдущем шаге, умножается на матрицу

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

(4.4.23)

где

(4.4.24)

Таким образом, мы получили, что , откуда следует, что

(4.4.25)

Матрица типа (4.4.22) называется элементарной нижней треугольной матрицей. Обратная к (4.4.22) матрица также является элементарной нижней треугольной матрицей и имеет вид

(4.4.26)

Произведение элементарных нижних треугольных матриц (4.4.26) и есть нижняя треугольная матрица, которая присутствует в разложении (4.4.14):

(4.4.27)

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

(4.4.28)

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

где По условию , следовательно,

Пусть существует разложение (4.4.14) матриц порядка; докажем, что аналогичное разложение существует для матриц порядка. Для этого представим матрицу порядка в виде

где через обозначена матрица порядка, Согласно предположению индукции , где — нижняя треугольная матрица порядка, — верхняя треугольная матрица порядка с единичной диагональю. Будем искать разложение матрицы А к в виде

где — неизвестные пока матрицы. Выполнив умножение в (4.4.29), придем к уравнениям

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

(4.4.30)

Равенство (4.4.32) представляет собой продолжение равенств (4.4.30) для Так как значение к не было определено, то формулы являются формулами для вычисления элементов нижней треугольной матрицы L и верхней треугольной матрицы U разложения квадратной матрицы. Метод решения системы линейных алгебраических уравнений путем разложения матрицы системы на нижнюю треугольную и верхнюю треугольную матрицы часто называют методом Холесского. Коэффициент не может быть равен нулю. Это следует из того, что и

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

Формулы (4.4.29)-(4.4.32) доказывают, что любую квадратную матрицу А, все угловые миноры которой отличны от нуля, можно разложить в произведение нижней треугольной матрицы L и верхней треугольной матрицы U с единицами на главной диагонали. Такое разложение единственно. Единственность разложения можно доказать методом от противного.

Метод Якоби.

Одним из итерационных методов решения системы линейных алгебраических уравнений (4.4.1) является метод Якоби. Выразим из каждого уравнения системы одну из неизвестных величин . Например, из уравнения выразим неизвестную и перепишем систему в виде

(4.4.33)

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

(4.4.34)

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

(4.4.35)

Для n-мерного вектора, компонентами которого являются неизвестные на приближении, введем обозначение . Через D обозначим диагональную матрицу, ненулевые элементы которой равны диагональным элементам матрицы А. Через С обозначим нижнюю треугольную матрицу, ненулевые элементы которой равны элементам матрицы А, стоящим под главной диагональю матрицы А. Через R обозначим верхнюю треугольную матрицу, ненулевые элементы которой равны элементам матрицы А, стоящим над главной диагональю матрицы А. Эти матрицы имеют вид

Через b обозначим вектор правой части: . В принятых обозначениях уравнение (4.4.2) будет записано следующим образом:

В методе Якоби это уравнение заменяется уравнением Итерационный процесс метода Якоби в матричной записи с использованием принятых обозначений имеет вид

(4.4.36)

Итерационный процесс метода Якоби сходится, если норма матрицы меньше единицы

Это соответствует требованию преобладания диагональных элементов матрицы А

Метод Зейделя.

Другим итерационным методом решения системы линейных алгебраических уравнений (4.4.1) является метод Зейделя. Метод Зейделя представляет собой некоторую модификацию метода Якоби, которая состоит в том, что при вычислении на приближении неизвестной учитываются уже вычисленные приближения неизвестных , а остальные неизвестные берутся для приближения

(4.4.38)

Уравнения (4.4.38) решаются последовательно, начиная с первого. К моменту вычислешт из уравнения приближения неизвестной приближения неизвестных уже вычислены из предыдущих уравнений. Развернутая запись уравнений системы имеет вид

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

В методе Зейделя уравнение (4.4.2) заменяется уравнением . В матричной записи итерационный процесс метода Зейделя имеет вид

(4.4.39)

Итерационный процесс метода Зейделя сходится, если норма матрицы меньше единицы

Эхо неравенство также приводит к требованию преобладания диагональных элементов в матрице А, т. е. методы Якоби и Зейделя для сходимости предъявляют одинаковые требования к коэффициентам системы уравнений

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

Метод релаксации.

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

(4.4.40)

Следующее приближение первой неизвестной найдем из равенства нулю максимальной невязки, т. е. из уравнения

где k — номер уравнения с максимальной по модулю невязкой. Затем вычислим невязки при полученной неизвестной

и найдем следующее приближение второй неизвестной из равенства нулю максимальной невязки

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

Метод невязок.

Рассмотрим еще один итерационный метод решения систем линейных алгебраических уравнений. Он относится к итерационным нелинейным методам. В этом методе новое приближение искомых функций связывается с предыдущим приближением искомых функций рекуррентным соотношением

(4.4.41)

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

В матричной записи с использованием обозначений для неизвестных и коррекцией на итерации соотношение (4.4.41) имеет вид

(4.4.42)

Рассмотрим матрицу-столбец невязок уравнений системы , с компонентами — Невязки уравнений системы на соседних итерациях связаны соотношением

Будем рассматривать неизвестные коррекции и невязки уравнений как векторы n-мерного пространства. Скалярный множитель найдем из условия минимума длины вектора невязки (4.4.43). Для этого умножим -мерный вектор скалярно на себя, продифференцируем это произведение по и приравняем производную нулю, в результате получим

Отсюда

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

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