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

5.1. Постановка задачи

Рассматривается система n линейных алгебраических уравнений (сокращенно - СЛАУ) с n неизвестными

(5.1)

где a_ij - заданные коэффициенты, b_i - известные свободные члены. Требуется решить СЛАУ (1), то есть, найти такие значения , которые при подстановке их в уравнения (5.1), обращали бы их в тождества.

СЛАУ (1) удобно записывать в символической форме

(5.2)

или в символической матричной форме:

, (5.3)

где матрицы имеют следующий вид:

, , . (5.4)

Далее будем предполагать, что и, т.о., СЛАУ (1) имеет решение и оно единственно.

5.2. Корректность задачи

Задача поставлена корректно, если:

1. решение задачи существует;

2. оно единственно,

3. решение непрерывно зависит от входных данных.

Входные данные задачи (5.1) () задаются с погрешностью и тогда вместо (5.1) в действительности будет решаться задача

. (5.5)

Рассмотрим два частных случая:

1. . Тогда из (5.3), (5.5) следует

; (5.6)

2. . Тогда из (5.5) следует

. (5.7)

В формулах, связывающих относительные погрешности решения с относительными погрешностями задания правых частей (5.6) и коэффициентов матрицы (5.7), фигурирует множитель

, (5.8)

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

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

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

Прямые методы имеют следующие отличительные особенности:

1. их погрешность равна нулю;

2. решение гарантируется после предопределенного количества вычислительных операций;

3. требуется заранее вычисленная матрица A.

Итерационные методы имеют следующие отличительные особенности:

1. их погрешность отлична от нуля;

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

3. при вычислениях, как правило, последовательно используются отдельные уравнения и не обязательно заранее вычислять всю матрицу A.

4. алгоритм очень прост.

5.4. Метод Гаусса (схема единственного деления)

Идея метода состоит в приведении заданной СЛАУ к СЛАУ с треугольной матрицей (прямой ход) с последующим ее решением (обратный ход).

Прямой ход заключается в исключении поддиагональных слагаемых и начинается с того, что первое (ведущее) уравнение СЛАУ (5.1) делится на т.н. ведущий коэффициент a₁₁= a_11,0:

. (5.9)

Затем каждое из уравнений делится на коэффициент, находящийся под ведущим (a_i1) и от него вычитается ведущее уравнение (9). Получается СЛАУ, состоящая из уравнения (9) и уравнений без первого столбца вида

(5.10)

Теперь ведущим выбирается второе уравнение СЛАУ, а ведущим коэффициентом - a_22,1. После деления ведущего уравнения на ведущий коэффициент получаем

. (5.11)

Затем каждое из уравнений делится на коэффициент, находящийся под ведущим (a_i1) и от него вычитается ведущее уравнение (5.11). Получается СЛАУ, состоящая из уравнений (5.9), (5.11) и уравнений без первых двух столбцов вида

(5.12)

Последовательное повторение этих операций приводит СЛАУ к виду

(5.13)

Обратный ход - это решение СЛАУ (13), начиная с последнего уравнения.

Всего производится приблизительно 2/3n³ арифметических действий (около половины из них - сложения, столько же умножений и n делений).

Вычисление определителя матрицы A использует результаты прямого хода:

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

Вычисление определителя этим методом отличается тем, что перемена местами строк определителя изменяет его знак на противоположный:

(5.15)

Здесь p - количество перемен местами уравнений на этапе прямого хода.