В. 2 системы линейных алгебраических уравнений (СЛАУ)

СЛАУ используются во многих областях науки и техники и являются наиболее часто встречающимся типом задач вычислительной математики [1-7]. В общем виде СЛАУ из уравнений с неизвестными записывается в вид

(1)

Здесь - неизвестный вектор решения, - заданный вектор в мерном пространстве комплексных векторов, а

-

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

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

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

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

Для характеристики обусловленности задачи вводят, так называемое, число обусловленности . Для задачи решения СЛАУ в качестве числа обусловленности можно принять

Это число характеризует качество решения СЛАУ. Если оно много больше размера матрицы, то задача решения СЛАУ плохо обусловлена и следует ожидать сильного влияния ошибок округления в исходных данных и в процессе решения задачи на результат. Численное значение зависит от вида используемой нормы, но при этом для разных норм порядок числа примерно один и тот же. Свойства числа обусловленности для нормальной матрицы:

, где , а , −собственные числа матрицы ;

;

;

;

Для диагональной матрицы ;

Для единичной матрицы .

Докажем свойство 1.

Пусть -собственная пара матрицы . Тогда - собственная пара матрицы .

Действительно, по определению и . Далее

Таким образом, , и

;

Как известно для нормальной матрицы и второй подчиненной нормы . Отсюда и следует свойство 1.

Пусть решение СЛАУ получено с относительной ошибкой . Тогда для нее справедлива оценка:

Здесь - машинная константа – наименьшее число, которое при прибавлении к единице ещё изменяет её значение в машинном представлении. Отметим, что оценка справедлива для малых ошибок в заданной матрице

Введём понятие невязки решения:

Невязка связана с погрешностью решения , где гипотетическое точное решение, следующим образом

то есть .

Заметим, что малость невязки , не гарантирует малость ошибки в решении, наоборот же верно. Так, для невязки выполняется соотношение

в то время как для справедливо:

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

Существуют два основных класса методов и алгоритмов для решения СЛАУ – прямые и итерационные. Прямые методы характеризуются тем, что при абсолютной точности вычислений (на гипотетической бесконечноразрядной ЭВМ) точное решение СЛАУ может быть получено с помощью конечного числа арифметических операций. Итерационные методы характеризуются тем, что даже при абсолютной точности вычислений за конечное число арифметических операций может быть получено, как правило, лишь приближенное решение системы, хотя возможно и как угодно близкое к точному. Однако при реальных вычислениях на ЭВМ указанное различие теряет свой смысл, и для многих задач итерационные методы оказываются более предпочтительными, чем прямые в силу отсутствия накопления ошибок для сходящегося итерационного процесса и возможности приблизиться к решению с заданной точностью.

Рассмотрим сначала прямые методы. Наиболее известным является метод Гаусса, и многие распространенные методы являются, как правило, его модификацией.