Раздел 2. Решение систем линейных алгебраических уравнений

2.1. Основные понятия и определения

Системы линейных алгебраических уравнений (СЛАУ) являются важной математической моделью линейной алгебры. На их базе ставятся такие практические математические задачи, как:

– непосредственное решение линейных систем;

– вычисление определителей матриц;

– вычисление элементов обратных матриц;

– определение собственных значений и собственных векторов матриц.

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

Вторая и третья задачи являются также и компонентами технологии решения самих линейных систем.

Обычно СЛАУ n-го порядка записывается в виде

или в развернутой форме

(1)

или в векторной форме

, (2)

где

; ; .

В соотношениях (2):

А называется основной матрицей системы с n² элементами;

= (x₁, x₂, ... , x_n)^Т – вектор-столбец неизвестных;

= (b₁, b₂, ... , b_n)^Т – вектор-столбец свободных членов.

Определителем (детерминантом – det) матрицы А n-го порядка называется число D (det A), равное

.

Здесь индексы , , ...,  пробегают все возможные n! перестановок номеров 1, 2, ..., n; k – число инверсий в данной перестановке.

Первоначальным при решении СЛАУ (1) является анализ вида исходной матрицы А и вектора-столбца свободных членов в (2).

Если все свободные члены равны нулю, т.е. = 0, то система называется однородной. Если же  0, или хотя бы одно b_i  0 ( ), то система (2) называется неоднородной.

Квадратная матрица А называется невырожденной, или неособенной, если ее определитель |A|  0. При этом система (1) имеет единственное решение.

При |A| = 0 матрица А называется вырожденной, или особенной, а система (1) не имеет решения, либо имеет бесконечное множество решений.

Если |A|  0 система (1) называется плохо обусловленной, т.е. решение очень чувствительно к изменению коэффициентов системы.

В ряде случаев получаются системы уравнений с матрицами специальных видов: диагональные, трехдиагональные (частный случай ленточных), симметричные (а_ij = a_ji), единичные (частный случай диагональной), треугольные и др.

Решение системы (2) заключается в отыскании вектора-столбца = (x₁, x₂, ... , x_n)^Т, который обращает каждое уравнение системы в тождество.

Существуют две величины, характеризующие степень отклонения полученного решения от точного, которые появляются в связи с округлением и ограниченностью разрядной сетки ЭВМ, – погрешность  и «невязка» r:

(3)

где – вектор решения. Как правило, значения вектора – неизвестны.

Доказано, что если   0, то и r = 0. Обратное утверждение не всегда верно. Однако если система не плохо обусловлена, для оценки точности решения используют невязку r.

2.2. Методы решения слау

Методы решения СЛАУ делятся на две группы:

– прямые (точные) методы;

– итерационные (приближенные) методы.

К прямым методам относятся такие методы, которые, в предположении, что вычисления ведутся без округлений, позволяют получить точные значения неизвестных. Они просты, универсальны и используются для широкого класса систем. Однако они не применимы к системам больших порядков (n < 200) и к плохо обусловленным системам из-за возникновения больших погрешностей. К ним можно отнести: правило Крамера, методы обратных матриц, Гаусса, прогонки, квадратного корня и др.

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