Задачи вычислительной линейной алгебры

К задачам, решаемым численно, относятся:

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

\[ \mathbf{A x}=\mathrm{f} \]

• Вычисление определителей и обратных матриц

\[\operatorname{det} \mathbf{A}, \quad \mathbf{B}=\mathbf{A}^{-1}\]

• Вычисление собственных и сингулярных чисел и векторов

На практике разные вычислительные задачи приводят к необходимости решать линейные системы уравнений. С этой задачи и начнём.

В этом семинаре цель - понять, какие СЛАУ можно решать хорошо, а с какими возникнут трудности вне зависимости от метода решения. Также разберём базовые методы решения СЛАУ.

Задача СЛАУ

Найти решение системы из \(n\) линейных уравнений с \(n\) неизвестными

\[\begin{split} \left\{\begin{array}{c} a_{11} \cdot x_1+a_{12} \cdot x_2+\cdots+a_{1 n} \cdot x_n=f_1 \\ a_{21} \cdot x_1+a_{22} \cdot x_2+\cdots+a_{2 n} \cdot x_n=f_2 \\ \vdots \\ a_{n 1} \cdot x_1+a_{n 2} \cdot x_2+\cdots+a_{n n} \cdot x_n=f_n \end{array}\right. \end{split}\]

для краткости записанной в матричной форме

\[A x=f\]

Существование и единственность решения этой системы гарантируется при \(\operatorname{det} \mathbf{A} \neq 0\).

Примечание - практическая неприменимость аналитических методов

Конечно, алгоритм её решения в общем случае математически можно явно задать методом поиска обратной, что крайне сложно, или методом Крамера. Однако в нём требуется явный расчёт определителей матриц \(\Delta=\sum_{i_1, i_2, \ldots, i_n}(-1)^{P\left(i_1, i_2, \ldots, i_n\right)} a_{1 i_1} a_{2 i_2} \cdots a_{n i_n}\), которые считать крайне затратно. Фактически, сложность метода Крамера имеет асимптотику \(\mathcal{O}(n \cdot n !)\), что сужает его применимость до матриц размера \(n \lesssim 10\).

Прежде чем мы перейдём к непосредственным методам решения СЛАУ, отметим важной свойство данной задачи - СЛАУ может иметь критическую чувствительность к погрешностям коэффициентов.

Влияние неустранимой погрешности на плохо-обусловленные системы.

Проиллюстрируем её на простом примере. Пусть решается система

\[\begin{split} \left(\begin{array}{cc} 10 & 9 \\ 9 & 8 \end{array}\right)\left(\begin{array}{l} x_1 \\ x_2 \end{array}\right)=\left(\begin{array}{l} 19 . \\ 17 . \end{array}\right) \end{split}\]

причем матрица известна точно, а правая часть с погрешностью не более 3%. Отметим, что определитель матрицы \(\operatorname{det} \mathbf{A}=10 \cdot 8-9^2=-1 \neq 0\). С точки зрения линейной алгебры, проблем при решении данной системы не должно быть.

Посмотрим, на какую точность можно рассчитывать при решении системы. Для этого возьмём несколько векторов \(f\) (рис. слева), отличающихся от правой части не более, чем на 3%, и построим все возможные решения СЛАУ для них (рис. справа).

Задача оказалась плохо обусловленной. Сравнительно небольшие возмущения системы уравнений привели к существенным отклонениям в решении.

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

• Каким-то образом перейти к хорошо обусловленной эквивалентной системе.

• Повысить точность определения коэффициентов СЛАУ и правой части.

Плохо обусловленные системы являются обобщением понятия вырожденных систем. Системы «близкие» к вырожденным скорее всего будут плохо обусловлены.

По-хорошему нам нужен критерий «хорошести» матрицы \(A\) и столбца свободных членов \(f\), чтобы мы могли оценить, насколько вообще решение будет иметь смысл. Для этого нам понадобятся вспомнить матричные и векторные нормы.