• 3. Методи розв’язання систем лінійних алгебраїчних рівнянь (СЛАР)
  • 3.1. Метод Гаусса
  • 3.2. Метод квадратних коренів
  • 3.3. Обчислення визначника та оберненої матриці
  • 3.4. Метод прогонки
  • 3.5. Обумовленість систем лінійних алгебраїчних рівнянь

3. Методи розв’язання систем лінійних алгебраїчних рівнянь (СЛАР)

Методи розв’язування СЛАР поділяються на прямі та ітераційні. При умові точного виконання обчислень прямі методи за скінчену кількість операцій в результаті дають точний розв’язок. Використовуються вони для невеликих та середніх СЛАР $n = 10^2 - 10^4$. Ітераційні методи використовуються для великих СЛАР $n > 10^5$, як правило розріджених. В результаті отримуємо послідовність наближень, яка збігається до розв’язку.

3.1. Метод Гаусса

Література:

• Самарский, Гулин, стор. 49–67: djvu, pdf;

• Березин, Жидков, том II, стор. 10–17: djvu, pdf.

Розглянемо задачу розв’язання СЛАР

\begin{equation} \label{eq:3.1.1} A \vec x = \vec b, \end{equation}

причому $A = (a_{ij})_{i, j = 1}^n$, $\det A \ne 0$, $\vec x = (x_i)_{i = 1}^n$, $\vec b = (b_j)_{j = 1}^n$. Метод Крамера з обчисленням визначників для такої системи має складність $Q = O(n! \cdot n)$.

Запишемо СЛАР у вигляді

\begin{equation} \left\{ \begin{aligned} & a_{1, 1} x_1 + a_{1, 2} x_2 + \ldots + a_{1, n} x_n = b_1 \equiv a_{1, n + 1}, \newline & a_{2, 1} x_1 + a_{2, 2} x_2 + \ldots + a_{2, n} x_n = b_2 \equiv a_{2, n + 1}, \newline & \ldots \newline & a_{n, 1} x_1 + a_{n, 2} x_2 + \ldots + a_{n, n} x_n = b_n \equiv a_{n, n + 1}. \end{aligned} \right. \end{equation}

Якщо $a_{1, 1} \ne 0$, то ділимо перше рівняння на нього і виключаємо $x_1$ з інших рівнянь:

\begin{equation} \left\{ \begin{aligned} x_1 + a_{1, 2}^{(1)} x_2 + \ldots + a_{1, n}^{(1)} x_n = a_{1, n + 1}^{(1)}, & \newline a_{2, 2}^{(1)} x_2 + \ldots + a_{2, n}^{(1)} x_n = a_{2, n + 1}^{(1)}, & \newline \ldots & \newline a_{n, 2} x_2^{(1)} + \ldots + a_{n, n}^{(1)} x_n = a_{n, n + 1}^{(1)} &. \end{aligned} \right. \end{equation}

Процес повторюємо для $x_2, \ldots, x_n$. В результаті отримуємо систему з трикутною матрицею

\begin{equation} \left\{ \begin{aligned} x_1 + a_{1, 2}^{(1)} x_2 + \ldots + a_{1, n}^{(1)} x_n = a_{1, n + 1}^{(1)}, & \newline x_2 + \ldots + a_{2, n}^{(2)} x_n = a_{2, n + 1}^{(2)}, & \newline \ldots & \newline x_n = a_{n, n + 1}^{(n)}. & \end{aligned} \right. \end{equation}

Тобто

\begin{equation} \label{eq:3.1.2} A^{(n)} \vec x = \vec a^{(n)}. \end{equation}

Це прямий хід методу Гаусса. Формули прямого ходу

for k in range(1, n):
  for j in range(k + 1, n + 2):
    a[k, j][k] = a[k, j][k - 1] / a[k, k][k - 1]
    for i in range(k + 1, n + 1):
      a[i, j][k] = a[i, j][k - 1] - \
        a[i, j][k - 1] * a[k, j][k]

Звідси

\begin{equation} \label{eq:3.1.3} x_n = a_{n, n + 1}^{(n)}, \quad x_i = a_{i, n + 1}^{(i)} - \Sum_{j = i + 1}^n a_{i, j}^{(n)} x_j, \end{equation}

для $i = \overline{n - 1, 1}$. Це формули оберненого ходу.

Складність, тобто кількість операцій, яку необхідно виконати для реалізації методу: $Q_f = 2/3 n^2 + O(n^2)$ для прямого ходу, $Q_b = n^2 + O(n)$ для оберненого ходу.

Умова

\begin{equation} a_{k, k}^{(k - 1)} \ne 0 \end{equation}

не суттєва, оскільки знайдеться $m$, для якого

\begin{equation} \left\vert a_{m, k}^{(k - 1)} \right\vert = \Max_i \left\vert a_{i, k}^{(k - 1)} \right\vert \ne 0 \end{equation}

(оскільки $\det A \ne 0$). Тоді міняємо місцями рядки номерів $k$ і $m$.

Означення: Елемент

\begin{equation} a_{k, k}^{(k - 1)} \ne 0 \end{equation}

називається ведучим.

Введемо матриці

\begin{equation} M_k = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & m_{k,k} & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & m_{n,k} & \cdots & 1 \end{pmatrix} \end{equation}

елементи якої обчислюється так:

\begin{equation} m_{k, k} = \frac{1}{a_{k, k}^{(k - 1)}}, \quad m_{k, k} = - \frac{a_{i, k}^{(k - 1)}}{a_{k, k}^{(k - 1)}}. \end{equation}

Нехай на $k$-му кроці $A_{k - 1} \vec x = \vec b_{k - 1}$. Множимо цю СЛАР зліва на $M_k$: $M_k A_{k - 1} \vec x = M_K \vec b_{k - 1}$. Позначимо $A_k = M_k A_{k - 1}$; $A_0 = A$. Тоді прямий хід методу Гаусса можна записати у вигляді

\begin{equation} M_n M_{n - 1} \ldots M_1 A \vec x = M_n M_{n - 1} \ldots M_1 \vec b. \end{equation}

Позначимо останню систему, яка співпадає з \eqref{eq:3.1.2}, так

\begin{equation} \label{eq:3.1.4} U \vec x = \vec c, \quad U = (u_{i, j})\void_{i, j = 1}^n, \end{equation}

причому

\begin{equation} \begin{cases} u_{i, i} = 1, & \newline u_{i, j} = 0, & i > j. \end{cases} \end{equation}

Таким чином $U = M_n M_{n - 1} \ldots M_1 A$. Введемо матриці

\begin{equation} L_k = M_k^{-1} = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & a_{k,k}^{(k-1)} & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & a_{n,k}^{(k-1)} & \cdots & 1 \end{pmatrix} \end{equation}

Тоді

\begin{equation} A = L_1 \ldots L_n U = L U; \quad L = L_1 \ldots L_n, \end{equation}

де $L$ — нижня трикутня матриця, $U$ — верхня трикутня матриця. Таким чином метод Гаусса можна трактувати, як розклад матриці $A$ в добуток двох трикутних матриць — $LU$-розклад.

Введемо матрицю перестановок на $k$-му кроці (це матриця, отримана з одиничної матриці перестановкою $k$-того і $m$-того рядка). Тоді при множені на неї матриці $A_{k - 1}$ робимо ведучим елементом максимальний за модулем.

\begin{equation} P_k = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & 0 & \cdots & 1 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & 1 & \cdots & 0 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \newline \end{pmatrix} \end{equation}

За допомогою цих матриць перехід до трикутної системи \eqref{eq:3.1.4} тепер має вигляд:

\begin{equation} M_n M_{n - 1} P_{n - 1} \ldots M_1 P_1 A \vec x = M_n M_{n - 1} P_{n - 1} \ldots M_1 P_1 \vec b. \end{equation}

Твердження: Знайдеться така матриця $P$ перестановок, що $P A = L U$ — розклад матриці на нижню трикутну з ненульовими діагональними елементами і верхню трикутну матрицю з одиницями на діагоналі.

Висновки про переваги трикутного розкладу:

• Розділення прямого і оберненого ходів дає змогу економно розв’язувати декілька систем з одноковою матрицею та різними правими частинами.

• Зберігання $M$, або $L$ та $U$ на місці $А$.

• Обчислюючи $\ell$ — кількість перестановок, можна встановити знак визначника.

3.2. Метод квадратних коренів

Література:

• Самарский, Гулин, стор. 69–73: djvu, pdf;

• Березин, Жидков, том II, стор. 23–25: djvu, pdf.

Цей метод призначений для розв’язання систем рівнянь із симетричною матрицею

\begin{equation} \label{eq:3.2.1} A \vec x = \vec b, \quad A^\intercal = A. \end{equation}

Він оснований на розкладі матриці $A$ в добуток:

\begin{equation} \label{eq:3.2.2} A = S^\intercal D S, \end{equation}

де $S$ — верхня трикутна матриця, $S^\intercal$ — нижня трикутна матриця, $D$ — діагональна матриця.

Виникає питання: як обчислити $S$, $D$ по матриці $A$? Маємо

\begin{equation} \label{eq:3.2.3} DS_{i, j} = \begin{cases} d_{i, i} s_{i, j}, & i \le j, \newline 0, & i > j. \end{cases} \end{equation}

Далі

\begin{equation} \begin{aligned} S^\intercal DS_{i, j} &= \Sum_{l = 1}^n s_{i, l}^\intercal d_{l, l} s_{l, j} = \newline &= \Sum_{l = 1}^{i - 1} s_{l, i}^\intercal s_{l, j} d_{l, l} + s_{i, i} s_{i, j} d_{i, i} + \newline &\quad + \underset{= 0}{\underbrace{s_{l, i}^\intercal \Sum_{l = i + 1}^n s_{l, i}^\intercal s_{l, j} d_{l, l}}} = a_{i, j}, \end{aligned} \end{equation}

для $i, j = \overline{1, n}$.

Якщо $i = j$, то

\begin{equation} \vert s_{i, i}^2 \vert d_{i, i} = a_{i, i} - \Sum_{l = 1}^{i - 1} \vert s_{l, i}^2 \vert d_{l, l} \equiv p_i. \end{equation}

Тому

\begin{equation} d_{i,i} = \text{sign}(p_i), \quad s_{i,i} = \sqrt{\vert p_i \vert}. \end{equation}

Якщо $i < j$, то

\begin{equation} s_{i,j} = \left( a_{i,j} - \Sum_{l = 1}^{i - 1} s_{l,i}^\intercal d_{l,l} s_{l,j} \right) / (s_{i,i} d_{i,i}), \end{equation}

де $i = \overline{1, n}$, а $j = \overline{i + 1, n}$.

Якщо $A > 0$ (тобто головні мінори матриці $A$ додатні), то всі $d_{i,i} = +1$.

Знайдемо розв’язок рівняння \eqref{eq:3.2.1}. Враховуючи \eqref{eq:3.2.2}, маємо:

\begin{equation} \label{eq:3.2.4} S^\intercal D \vec y = \vec b \end{equation}

і

\begin{equation} \label{eq:3.2.5} S \vec x = \vec y \end{equation}

Оскільки $S$ — верхня трикутна матриця, а $S^\intercal D$ — нижня трикутна матриця, то

\begin{equation} \label{eq:3.2.6} y_i = \frac{b_i - \Sum_{j = 1}^{i - 1} s_{j,i} d_{j,j} y_j}{s_{i,i} d_{i,i}}, \end{equation}

для $i = \overline{1, n}$ і

\begin{equation} \label{eq:3.2.7} x_i = \frac{y_i - \Sum_{j = 1}^{i - 1} s_{i, j} x_j}{s_{i,i}}, \end{equation}

для $i = \overline{n - 1, 1}$, де $x_n = y_n / s_{n,n}$.

Метод застосовується лише для симетричних матриць. Його складність $Q = n^3/3 + O(n^2)$.

Переваги цього методу:

• він витрачає в 2 рази менше пам’яті ніж метод Гаусса для зберігання $A^\intercal = A$ (необхідний об’єм пам’яті $n(n+1)/2 \sim n^2/2$;

• метод однорідний, без перестановок;

• якщо матриця $A$ має багато нульових елементів, то і матриця $S$ також.

Остання властивість дає економію в пам’яті та кількості арифметичних операцій. Наприклад, якщо $A$ має $m$ ненульових стрічок по діагоналі ($m$-діагональна), то $Q = O(m^2 n)$.

3.3. Обчислення визначника та оберненої матриці

Література:

• Самарский, Гулин, стор. 67–69: djvu, pdf;

• Березин, Жидков, том II, стор. 17–19: djvu, pdf.

Кількість операцій обчислення детермінанту за означенням — $Q_{\det} = n!$. В методі Гаусса — $P A = L U$. Тому

\begin{equation} \det P \det A = \det L \det U \end{equation}

звідки

\begin{equation} \det A = (-1)^\ell \det L \det U = (-1)^\ell \Prod_{k = 1}^n a_{k, k}^{(k)}, \end{equation}

де $\ell$ — кількість перестановок. Ясно, що за методом Гаусса

\begin{equation} Q_{\det} = \frac{2}{3} \cdot n^3 + O(n^2) \end{equation}

В методі квадратного кореня $A = S^\intercal DS$. Тому

\begin{equation} \label{eq:3.4.2} \det A = \det S^\intercal \det D \det S = \Prod_{k = 1}^n d_{k, k} \Prod_{k = 1}^n s_{k, k}^2. \end{equation}

Тепер $Q_{\det} = n^3/3 + O(n^2)$.

За означенням

\begin{equation} \label{eq:3.4.3} A A^{-1} = E, \end{equation}

де $A^{-1}$ обернена до матриці $A$. Позначимо

\begin{equation} A^{-1} = (\alpha_{i, j})\void_{i, j = 1}^n. \end{equation}

Тоді $\vec \alpha_j = (\alpha_{i, j})\void_{i = 1}^n$ — вектор-стовпчик оберненої матриці. З \eqref{eq:3.4.3} маємо

\begin{equation} \label{eq:3.4.5} A \vec \alpha_j = \vec e_j, \quad j = \overline{1, n}. \end{equation}

де $\vec e_j$ — стовпчики одиничної матриці: $\vec e_j = (\delta_{i, j})\void_{i = 1}^n$,

\begin{equation} \delta_{i, j} = \begin{cases} 1, & i = j, \newline 0, & i \ne j. \end{cases} \end{equation}

Для знаходження $А^{-1}$ необхідно розв’язати $n$ систем. Для знаходження $А^{-1}$ методом Гаусса необхідна кількість операцій $Q = 2 n^3 + O(n^2)$.

3.4. Метод прогонки

Література:

• Самарский, Гулин, стор. 45–47: djvu, pdf;

Це економний метод для розв’язання СЛАР з три діагональною матрицею:

\begin{equation} \left\{ \begin{aligned} & - c_0 y_0 + b_0 y_1 = - f_0, \newline & a_i y_{i - 1} - c_i y_i + b_i y_{i + 1} = - f_i, \newline & a_N y_{N - 1} - c_N y_N = - f_N. \end{aligned} \right. \end{equation}

Матриця системи

\begin{equation} A = \begin{pmatrix} -c_0 & b_1 & & 0 \newline a_0 & \ddots & \ddots & \newline & \ddots & \ddots & b_N \newline 0 & & a_N & -c_N \end{pmatrix} \end{equation}

тридіагональна.

Розв’язок представимо у вигляді

\begin{equation} \label{eq:3.4.4} y_i = \alpha_{i + 1} y_{i + 1} + \beta_{i + 1}, \quad i = \overline{0, N - 1}. \end{equation}

Замінимо в \eqref{eq:3.4.4} i $i \mapsto i - 1$ і підставимо в \eqref{eq:3.4.2}, тоді

\begin{equation} (a_i \alpha_i - c_i) \cdot y_i + b_i y_{i + 1} = - f_i - a_i \beta_i \end{equation}

Звідси

\begin{equation} y_i = \frac{b_i}{c_i - a_i \alpha_i} \cdot y_{i + 1} + \frac{f_i + a_i \beta_i}{c_i - a_i \alpha_i}. \end{equation}

Тому з \eqref{eq:3.4.5}

\begin{equation} \alpha_{i + 1} = \frac{b_i}{c_i - a_i \alpha_i}, \quad \beta_{i + 1} = \frac{f_i + a_i \beta_i}{c_i - a_i \alpha_i}, \quad i = \overline{1, N - 1}. \end{equation}

Умова розв’язності $(38)$ — $c_i - a_i \alpha_i \ne 0$.

Щоб знайти всі $\alpha_i$, $\beta_i$, треба задати перші значення. З $(38)$:

\begin{equation} \alpha_1 = \frac{b_0}{c_0}, \quad \beta_1 = \frac{f_0}{c_0}. \end{equation}

Після знаходження всіх $\alpha_i$, $\beta_i$ обчислюємо $y_N$ з системи

\begin{equation} \left\{ \begin{aligned} & a_N y_N - c_N y_N = - f_N, \newline & y_{N - 1} = \alpha_N y_N + \beta_N. \end{aligned} \right. \end{equation}

Звідси

\begin{equation} y_N = \frac{f_N + a_N \beta_N}{c_N - a_N \alpha_N}. \end{equation}

Алгоритм:

alpha[1], beta[1] = b[0] / c[0], f[0] / c[0]

for i in range(1, N):
  z[i] = c[i] - a[i] * alpha[i]
  alpha[i + 1], beta[i + 1] = b[i] / z[i], \
    (f[i] + a[i] * beta[i]) / z[i]

y[N] = (f[N] + a[N] * beta[N]) / \
  (c[N] - a[N] * alpha[N])

for i in range(N - 1, -1, -1):
  y[i] = alpha[i + 1] * y[i + 1] + beta[i + 1]

Складність алгоритму $Q = 8 N - 2$.

Метод можна застосовувати, коли $c_i - a_i \alpha_i \ne 0$, $\forall i: \vert \alpha_i \vert \le 1$. Якщо $\vert \alpha_i \vert \ge q > 1$ то $\Delta y_0 \ge q^N \Delta y_N$ (тут $\Delta y_i$ абсолютна похибка обчислення $y_i$), а це приводить до експоненціального накопичення похибок заокруглення, тобто нестійкості алгоритму прогонки.

Теорема (про достатні умови стійкості метода прогонки): Нехай $a_i, b_i \ne 0$, та

\begin{equation} \vert c_i \vert \ge \vert a_i \vert + \vert b_i \vert, \quad \forall i, \quad a_0 = b_N = 0, \end{equation}

та хоча би одна нерівність строга. Тоді $\vert \alpha_i \vert \le 1$ та

\begin{equation} z_i = c_i - a_i \alpha_i \ne 0, \quad i = \overline{1, N}. \end{equation}

Задача 8: Довести теорему про стійкість методу прогонки.

3.5. Обумовленість систем лінійних алгебраїчних рівнянь

Література:

• Самарский, Гулин, стор. 74–81: djvu, pdf;

Нехай задано СЛАР

\begin{equation} \label{eq:3.5.1} A \vec x = \vec b. \end{equation}

Припустимо, що матриця і права частина системи задані неточно і фактично розв’язуємо систему

\begin{equation} \label{eq:3.5.2} B \vec y = \vec h, \end{equation}

де $B = A + C$, $\vec h = \vec b + \vec \eta$, $\vec y = \vec x + \vec z$.

Малість детермінанту $\det A \ll 1$ не є необхідною умовою різкого збільшення похибки. Це ілюструє наступний приклад:

\begin{equation} A = \text{diag}(\varepsilon), \quad a_{i,j} = \varepsilon \delta_{i,j}. \end{equation}

Тоді $\det A = \varepsilon^n \ll 1$, але $x_i = b_i/\varepsilon$. Тому $\Delta x_i = \Delta b_i/\varepsilon \gg 1$.

Оцінимо похибку розв’язку. Підставивши значення $B$, $\vec h$, та $\vec z = \vec y - \vec x$, отримаємо:

\begin{equation} (A+C)(\vec x + \vec z) = \vec b +\vec \eta. \end{equation}

Віднімемо від цієї рівності \eqref{eq:3.5.1} у вигляді $A \vec z + C \vec x + C \vec z = \vec \eta$. Тоді

\begin{equation} A \vec z = \vec \eta - C \vec x - C \vec z, \quad \vec z = A^{-1}(\vec \eta - C \vec x - C \vec z). \end{equation}

Означення: Введемо норми векторів: $\|\vec z\|$:

\begin{align} |\vec z|\void_1 &= \Sum_{i=1}^n |z_i|, \newline |\vec z|\void_2 &= \left(\Sum_{i=1}^n |z_i|^2\right)^{1/2}, \newline |\vec z|\void_\infty &= \Max_i |z_i|. \end{align}

Означення:_ Норми матриці_, що відповідають нормам вектора, тобто

\begin{equation} |A|\void_m = \Sup_{|\vec x|\void_m \ne 0} \frac{|A\vec x|\void_m}{|\vec x|\void_m}, \quad m=1,2,\infty. \end{equation}

такі:

\begin{align} |A|\void_1 &= \Max_j \Sum_{i=1}^n \vert a_{i,j}\vert, \newline |A|\void_2 &= \Max_i \sqrt{\lambda_i (A^\intercal A)}, \newline |A|\void_\infty &= \Max_i \Sum_{j=1}^n \vert a_{i,j}\vert, \end{align}

де $\lambda_i(B)$ — власні значення матриці $B$.

Позначимо $\delta(\vec x) = \|\vec z\|/\|\vec x\|$, $\delta(\vec b) = \|\vec \eta\|/\|\vec b\|$, $\delta(A) = \|C\|/\|A\|$ — відносні похибки $\vec x$, $\vec b$, $A$, де $\|\cdot\|\void_k$ — одна з введених вище норм.

Для характеристики зв’язку між похибками правої частини та розв’язку вводять поняття обумовленості матриці системи.

Означення: Число обумовленості матриці $A$ — $\cond (A) = \|A\| \cdot \|A^{-1}\|$.

Теорема: Якщо $\exists A^{-1}$ та $\|A^{-1}\| \cdot \|C\| < 1$, то

\begin{equation} \label{eq:3.5.3} \delta(\vec x) \le \dfrac{\cond (A)}{1-\cond (A)\cdot\delta(A)}(\delta(A)+\delta(\vec b)), \end{equation}

де $\cond (A)$ — число обумовленості.

Доведення:

\begin{equation} A \vec z = \vec \eta - C \vec x - C \vec z, \quad \vec z = A^{-1} \vec \eta - A^{-1} C \vec x - A^{-1} C \vec z \end{equation}

\begin{equation} \begin{aligned} |\vec z| &\le |A^{-1}\vec \eta|+|A^{-1}C\vec x| +|A^{-1}C\vec z| \le \newline &\le |A^{-1}|\cdot|\vec \eta|+|A^{-1}|\cdot |C|\cdot |\vec x| +|A^{-1}|\cdot |C|\cdot |\vec z|. \end{aligned} \end{equation}

\begin{equation} |\vec z| \le \dfrac{|A^{-1}|\cdot(|\vec\eta|+|C|\cdot|\vec x|)}{1 - |A^{-1}| \cdot |C|} \end{equation}

Оцінка похибки

\begin{equation} \begin{aligned} \delta(\vec x) &\le \dfrac{|A^{-1}|}{1-|A^{-1}| \cdot |C|} \left(\dfrac{|\vec \eta|}{|\vec x|}+|C| \right) = \newline &= \dfrac{|A^{-1}|\cdot |A|}{1-|A^{-1}|\cdot|A|\cdot \dfrac{|C|}{|A|}} \left(\dfrac{|\vec \eta|}{|A|\cdot |\vec x|} + \delta(A) \right) \le \newline &\le \dfrac{\cond (A)}{1-\cond(A)\cdot\delta(A)}\left(\dfrac{|\vec\eta|}{|\vec x|}+\delta(A)\right). \quad \square \end{aligned} \end{equation}

Наслідок: Якщо $C \equiv 0$, то $\delta(\vec x)\le\cond(A)\cdot\delta(\vec b)$.

Властивості $\cond (A)$:

• $\cond (A)\ge1$;

• $\cond (A)\ge \max_i\vert\lambda_i(A)\vert/ \min_i\vert\lambda_i(A)\vert$;

• $\cond (AB) \le \cond (A) \cdot \cond (B)$;

• $A^\intercal = A^{-1} \implies \cond (A) = 1$.

Друга властивість має місце оскільки довільна норма матриці не менше її найбільшого за модулем власного значення. Значить $\|A\|\ge\max\vert\lambda_A\vert$. Оскільки власні значення матриць $A^{-1}$ та $A$ взаємно обернені, то

\begin{equation} |A^{-1}| \ge \max \dfrac{1}{|\lambda_A|} = \dfrac{1}{\min|\lambda_A|}. \end{equation}

Якщо $1\ll \cond (A)$, то система називається погано обумовленою.

Оцінка впливу похибок заокруглення при обчисленні розв’язку СЛАР така (Дж. Уілкінсон): $\delta (A) = O(n\beta^{-t})$, $\delta(\vec b) = O(\beta^{-t})$, де $\beta$ — розрядність ЕОМ, $t$ — кількість розрядів, що відводиться під мантису числа. З оцінки \eqref{eq:3.5.3} витікає: $\delta(\vec x) = \cond (A)\cdot O(n\beta^{-t})$. Висновок: найпростіший спосіб підвищити точність обчислення розв‘язку погано обумовленої СЛАР — збільшити розрядність ЕОМ при обчисленнях. Інші способи пов’язані з розглядом цієї СЛАР як некоректної задачі із застосуванням відповідних методів її розв’язання.

Приклад погано обумовленої системи — системи з матрицею Гільберта

\begin{equation} H_n = \left(\dfrac{1}{i+j-1}\right)\void_{i,j=1}^n, \end{equation}

наприклад $\cond (H_8)\approx 10^9$.

Назад до лекцій

Назад на головну