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

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

(1.3)

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

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

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

Наряду с системой уравнений (1.3) рассмотрим возмущенную задачу

(1.4)

где . , – возмущения элементов матрицы и вектора правой части задачи, а – разность между решениями возмущенной и исходной задачи. Задача считается устойчивой, если ее решение непрерывно зависит от возмущений входных данных. Условие устойчивости может быть сформулировано в виде оценки возмущения решения задачи от возмущения входных данных:

, (1.5)

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