Прямые методы решения СЛАУ

Вычислительная практика. 2 курс

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

Преподаватель Толоконников И.Г.

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

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

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

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

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

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

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

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

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

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

(1)

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

, (2)

где

; ; .

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

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

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

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

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

.

Здесь индексы a, b, ..., w пробегают все возможные 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)^Т, который обращает каждое уравнение системы в тождество.

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

(3)

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

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

Методы решения СЛАУ

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

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

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

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

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

Прямые методы решения СЛАУ

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

Рассмотрим систему (1). Как отмечалось выше, если определитель этой системы не равен нулю, то будет иметь место единственное решение. Это необходимое и достаточное условие. Тогда по правилу Крамера

, (4)

где D_k – определитель, получающийся из D при замене элементов a_1k, a_2k, ..., a_nk k-го столбца (соответствующими) свободными членами b₁, b₂, ..., b_n из (1), или

,

где А_ik алгебраическое дополнение элемента a_ik в определителе D. Стоит существенная проблема вычисления определителей высоких порядков.

Метод обратных матриц

Дана система . Умножим левую и правую части этого выражения на А^–1:

; .

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

Метод Гаусса

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

Посредством первого уравнения системы (1) исключается х₁ из последующих уравнений. Далее посредством второго уравнения исключается х₂ из последующих уравнений и т.д. Этот процесс называется прямым ходом Гаусса. Исключение неизвестных повторяется до тех пор, пока в левой части последнего n-го уравнения не останется одно неизвестное х_n

a¢_nnx_n = b¢, (5)

где a¢_nn и b¢ – коэффициенты, полученные в результате линейных (эквивалентных) преобразований.

Прямой ход реализуется по формулам

а*_mi = a_mi – ;

b*_m = b_m – (6)

где m – номер уравнения, из которого исключается x_k;

k – номер неизвестного, которое исключается из оставшихся (n – k) уравнений, а также обозначает номер уравнения, с помощью которого исключается x_k;

i – номер столбца исходной матрицы;

a_kk – главный (ведущий) элемент матрицы.

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

Обратный ход метода Гаусса состоит в последовательном вычислении x_n, x_n–1, ..., x₁, начиная с (5) по алгоритму

x_n = b¢ / a¢_nn ; . (7)

Точность полученного решения оценивается посредством «невязки» (3). В векторе невязки (r₁, r₂, ... , r_n)^Т отыскивается максимальный элемент и сравнивается с заданной точностью e. Приемлемое решение будет, если r_max < e. В противном случае следует применить схему уточнения решения.

Уточнение корней

Полученные методом Гаусса приближенные значения корней можно уточнить.

Пусть для системы найдено приближенное решение , не удовлетворяющее по «невязке». Положим тогда . Для получения поправки d = (d₁, d₂, ..., d_n)^Т корня следует рассмотреть новую систему

или ,

где – невязка для исходной системы.

Таким образом, решая линейную систему с прежней матрицей А и новым свободным членом = (e₁, e₂, ..., e_n)^Т, получим поправки (d₁, d₂, ..., d_n).

Пример решения СЛАУ по методу Гаусса (с точностью до трех знаков). Нужно уточнить корни до 10^–4:

В результате = 4,67; = 7,62; = 9,05. Невязки равны = −0,02; = 0; = −0,01. Получено уточнение = −0,0039; = −0,0011; = −0,0025. Следовательно х₁ = 4,6661; х₂ = 7,6189; х₃ = 9,0475. Невязки будут d₁ = −2×10^–4; d₂ = −2×10^–4; d₃ = 0.