Задача решения СЛАУ¶
Будем рассматривать случай системы с невырожденной квадратной матрицей $$ \mathbf{Ax} = \mathbf{b} \qquad \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{pmatrix} \begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix} = \begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix} $$
Из линейной алгебоы известно, что система разрешима при $\operatorname{det} \mathbf{A} \neq 0$ и при этом решение единственно.
Что такое вырожденная матрица?¶
С точки зрения вычислительной математики матрица никогда не бывает строго вырождена в смысле $\operatorname{det}{A} = 0$. Но может ли небольшая коррекция коэффициентов быть решением проблемы $\operatorname{det}{A} = 0$?
Рассмотрим следующие две системы, которые лишь немного отличаются $$ \begin{cases} x_1 + 2 x_2 & = 1\\ 2x_1 + 4.0001 x_2 &= 2 \end{cases} \qquad\qquad \begin{cases} x_1 + 2 x_2 & = 1\\ 2x_1 + 4.0001 x_2 &= 2.0001 \end{cases} $$ Их решения совершенно различны $$ \begin{cases} x_1 & = 1\\ x_2 & = 0 \end{cases} \qquad\qquad \begin{cases} x_1 & = -1\\ x_2 & = 1 \end{cases} $$
Нормы векторов¶
Для количественного исследования данной проблемы нужно ввести некоторую норму для векторов. В вычислительной математике наиболее часто используются
- $||\mathbf x||_\infty = \max_i |x_i|$ — максимум-норма, Чебышевская норма, $\ell_\infty$ норма
- $||\mathbf x||_{\ell_1} = \sum_i |x_i|$ — Манхэттенская норма, $\ell_1$ норма
- $||\mathbf x||_E = \sqrt{(\mathbf x, \mathbf x)} = \sqrt{\sum_i x_i^2}$ — Евклидова норма
Матричные нормы¶
Говорят, что матричная норма $\color{red}{\|\mathbf A\|}$ согласована с векторной нормой $\color{blue}{\|\mathbf x\|}$, если для любой матрицы $\mathbf A$ и любого вектора $\mathbf x$ выполняется следующее неравенство $$ \color{blue}{\|\mathbf{Ax}\|} \leqslant \color{red}{\|\mathbf A\|} \color{blue}{\|\mathbf x\|} $$
Вводят понятие матричной нормы $\color{green}{\|\mathbf A\|}$, подчиненной данной векторной норме $\color{blue}{\|\mathbf x\|}$ $$ \color{green}{\|\mathbf A\|} = \sup_{\mathbf x} \frac{\color{blue}{\|\mathbf{Ax}\|}}{\color{blue}{\|\mathbf x\|}} $$ Каждая векторная норма порождает свою подчиненную матричную норму. Подчиненная норма является согласованной.
Стандартные подчиненные матричные нормы¶
Доказывается, что
- $\|\mathbf A\|_\infty = \max_i \sum_j |a_{ij}|$.
- $\|\mathbf A\|_{\ell_1} = \max_j \sum_i |a_{ij}| = \|\mathbf A^\top \|_\infty$.
- $\|\mathbf A\|_E = \sigma_\max(\mathbf A) = \sqrt{\lambda_\max(\mathbf A^\top \mathbf A)}$
- для $\mathbf A = \mathbf A^\top$, $\|\mathbf A\|_E = \max |\lambda(\mathbf A)|$
- для $\mathbf A = \mathbf A^\top > 0$, $\|\mathbf A\|_E = \lambda_\max(\mathbf A)$
Задание. Вычислить все три нормы для $$ \mathbf A = \begin{pmatrix} 3 & -1\\ 0 & 4 \end{pmatrix} $$
Число обусловленности для СЛАУ¶
Расмотрим СЛАУ $$ \mathbf {Ax} = \mathbf {b} $$ и полученную из нее возмущением правой части $$ \mathbf {Az} = \mathbf {b} + \Delta \mathbf {b}. $$ Пусть $\Delta \mathbf x = \mathbf z - \mathbf x$.
Нам хотелось бы оценить относительную погрешность решения $\frac{\|\Delta \mathbf x\|}{\|\mathbf x\|}$, связав ее с относительной погрешностью правой части $\frac{\|\Delta \mathbf b\|}{\|\mathbf b\|}$
Пользуясь тем, что $\Delta \mathbf x = \mathbf A^{-1} \Delta \mathbf b$, оценим $$ \frac{\|\Delta \mathbf x\|}{\|\mathbf x\|} \leqslant \frac{\|\mathbf A^{-1}\|\|\Delta \mathbf b\|}{\|\mathbf x\|} = \color{blue}{\frac{\|\mathbf A^{-1}\|\|\mathbf b\|}{\|\mathbf x\|}} \frac{\|\Delta \mathbf b\|}{\|\mathbf b\|} $$ Величина $$ \nu(\mathbf A, \mathbf b) = \frac{\|\mathbf A^{-1}\|\|\mathbf b\|}{\|\mathbf x\|} \equiv \frac{\|\mathbf A^{-1}\|\|\mathbf b\|}{\|\mathbf A^{-1} \mathbf b\|} $$ называется числом обусловленности системы уравнений $\mathbf {Ax} = \mathbf b$. $$ \frac{\|\Delta \mathbf x\|}{\|\mathbf x\|} \leqslant \nu(\mathbf A, \mathbf b) \frac{\|\Delta \mathbf b\|}{\|\mathbf b\|} $$
import numpy as np
from numpy.linalg import norm, inv
def nu(A, b, kind = np.inf):
return norm(inv(A), kind) * norm(b, kind) / norm(inv(A).dot(b), kind)
eps = 0.0001
A = np.array([[1, 2], [2, 4 + eps]])
b = np.array([1, 2])
print('nu_inf(A, b) =', nu(A, b, np.inf))
print('nu_1(A, b) =', nu(A, b, 1))
print('nu_E(A, b) =', nu(A, b, 2))
Число обусловленности матрицы¶
Насколько плохо может быть обусловлена система с данной матрицей $\mathbf A$? Можно ли за счет выбора правой части $\mathbf b$ cделать систему сколь угодно плохой? Оказывается, нет.
$$ \nu(\mathbf A, \mathbf b) = \frac{\|\mathbf A^{-1}\| \|\mathbf b\|}{\|\mathbf A^{-1} \mathbf b\|} = \frac{\|\mathbf A^{-1}\| \|\mathbf {Ax}\|}{\|\mathbf x\|} \leqslant \|\mathbf A\|\|\mathbf A^{-1}\|. $$Последнаяя величина зависит лишь от матрицы $\mathbf A$ и называется числом обусловленности матрицы $$ \mu(\mathbf A) = \|\mathbf A\|\|\mathbf A^{-1}\| $$ Матрицу можно считать вырожденной, если ее число обусловленности превосходит $\frac{1}{\delta}$, где $\delta$ — относительная погрешность выполнения машинных операций.
def mu(A, kind = np.inf):
return norm(inv(A), kind) * norm(A, kind)
eps = 0.0001
A = np.array([[1, 2], [2, 4 + eps]])
print('mu_inf(A) =', mu(A, np.inf))
print('mu_1(A) =', mu(A, 1))
print('mu_E(A) =', mu(A, 2))
Плохо обусловленные задачи¶
Решение СЛАУ — пример потенциально плохо обусловленной задачи, то есть задачи, в которой небольшое возмущение входных данных может приводить к существенным отличиям в решении. Для таких задач необходимо задавать входные данные с большой точностью, иначе результат может получиться совершенно недостоверным.