9: Адекватність рішень

Цілі навчання

Прочитавши цю главу, ви повинні мати можливість:

1. знати різницю між погано обумовленими та умовленими системами рівнянь,
2. визначити і знайти норму матриці
3. визначити та оцінити номер умови оборотної квадратної матриці
4. співвіднести номер умови матриці коефіцієнтів з поганим або свердловинним кондиціонуванням системи одночасних лінійних рівнянь, тобто наскільки можна довіряти розв'язку одночасних лінійних рівнянь.

Що ви маєте на увазі під погано обумовленою та умовленою системою рівнянь?

Система рівнянь вважається добре обумовленою, якщо невелика зміна матриці коефіцієнтів або невелика зміна правого боку призводить до невеликої зміни вектора розв'язку.

Система рівнянь вважається погано обумовленою, якщо невелика зміна матриці коефіцієнтів або мала зміна правого боку призводить до великої зміни вектора розв'язку.

Приклад 1

Чи добре обумовлена ця система рівнянь?

$$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\ \nonumber$$

Рішення

Рішення вищевказаної множини рівнянь є

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber$$

Зробіть невелику зміну правого вектора рівнянь

$$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix}\ \ \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} \nonumber$$

Зробіть невелику зміну в матриці коефіцієнтів рівнянь

$$\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.998 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\ \ \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 3.994 \\ 0.001388 \\ \end{bmatrix} \nonumber$$

Ця остання система рівняння «виглядає» погано обумовленою, оскільки невелика зміна матриці коефіцієнтів або правої сторони призвела до великої зміни вектора розв'язку.

Приклад 2

Чи добре обумовлена ця система рівнянь?

$$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\ \ \nonumber$$

Рішення

Рішення вищевказаних рівнянь є

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber$$

Зробіть невелику зміну правого вектора рівнянь.

$$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix}\ \ \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} \nonumber$$

Зробіть невелику зміну в матриці коефіцієнтів рівнянь.

$$\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.001 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\ \ \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2.003 \\ 0.997 \\ \end{bmatrix} \nonumber$$

Ця система рівнянь «виглядає» добре обумовленою, оскільки невеликі зміни в матриці коефіцієнтів або правій частині призвели до невеликих змін вектора розв'язку.

Отже, що робити, якщо система рівнянь погано умовлена або добре умовлена?

Ну, якщо система рівнянь погано обумовлена, ми не можемо довіряти рішенню так сильно. Повторно переглядайте задачу швидкості, приклад 5.1 у главі 5. Значення в матриці коефіцієнтів$\lbrack A\rbrack$ є квадратами часу тощо Наприклад, якщо замість$a_{11} = 25,$ вас використовується, ви$a_{11} = 24.99,$ хочете, щоб ця невелика зміна мала мала значення у векторі розв'язку. Якби це сталося, ви б довіряли рішенню?

Пізніше ми побачимо, скільки (кількісних термінів) ми можемо довіряти розв'язку в системі рівнянь. Кожна оборотна квадратна матриця має номер умови і в поєднанні з машиною epsilon, ми можемо кількісно оцінити, скільки значущих цифр можна довіряти в рішенні.

Щоб обчислити номер умови оборотної квадратної матриці, мені потрібно знати, що означає норма матриці. Як визначається норма матриці?

Так само, як і детермінант, норма матриці - це просте унікальне скалярне число. Однак норма завжди позитивна і визначається для всіх матриць — квадратних або прямокутних, а також оборотних або незворотних квадратних матриць.

Одне з популярних визначень норми - норма суми рядків (також називається рівномірно-матричною нормою). Для$m \times n$$\lbrack A\rbrack$ матриці норма суми рядків$\lbrack A\rbrack$ визначається як

$$\left\| A \right\|_{\infty} = \begin{matrix} \max \\ 1 \leq i \leq m \\ \end{matrix}\sum_{j = 1}^{n}\left| a_{ij} \right| \nonumber$$

тобто знайти суму абсолютного значення елементів кожного рядка матриці$\lbrack A\rbrack$. Максимум з$m$ таких значень - норма суми рядків матриці$\lbrack A\rbrack$.

Приклад 3

Знайти норму суми рядків наступної матриці [A].

$$A = \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix} \nonumber$$

Рішення

$$\begin{split} \left\| A \right\|_{\infty} &= \begin{matrix} \max \\ 1 \leq i \leq 3 \\ \end{matrix}\sum_{j = 1}^{3}\left| a_{ij} \right|\\ &= max\left\lbrack \left( \left| 10 \right| + \left| - 7 \right| + \left| 0 \right| \right),\left( \left| - 3 \right| + \left| 2.099 \right| + \left| 6 \right| \right),\left( \left| 5 \right| + \left| - 1 \right| + \left| 5 \right| \right) \right\rbrack\\ &= max\left\lbrack \left( 10 + 7 + 0 \right),\left( 3 + 2.099 + 6 \right),\left( 5 + 1 + 5 \right) \right\rbrack\\ &= max\left\lbrack 17,\ 11.099,\ 11 \right\rbrack\\ &= 17 \end{split} \nonumber$$

Як норма пов'язана з кондиціонуванням матриці?

Почнемо відповідати на це питання на прикладі. Повертаємося до погано обумовленої системи рівнянь,

$$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix} \nonumber$$

що дає рішення як

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber$$

Позначення наведеного вище набору рівнянь як

$$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber$$

$$\left\| X \right\|_{\infty} = 2 \nonumber$$

$$\left\| C \right\|_{\infty} = 7.999 \nonumber$$

Здійснюючи невелику зміну в правій частині,

$$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix} \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} \nonumber$$

Позначення вищевказаного набору рівнянь

$$\left\lbrack A \right\rbrack\left\lbrack X' \right\rbrack = \left\lbrack C' \right\rbrack \nonumber$$

правий бік вектор знаходить по

$$\left\lbrack \Delta C \right\rbrack = \left\lbrack C' \right\rbrack - \left\lbrack C \right\rbrack \nonumber$$

і зміна вектора розв'язку знаходить

$$\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber$$

потім

$$\begin{split} \left\lbrack \Delta C \right\rbrack &= \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix} - \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.001 \\ - 0.001 \\ \end{bmatrix} \end{split} \nonumber$$

і

$$\begin{split} \left\lbrack \Delta X \right\rbrack &= \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} - \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}\\ &= \begin{bmatrix} - 5.999 \\ 3.000 \\ \end{bmatrix} \end{split} \nonumber$$

потім

$$\left\| \Delta C \right\|_{\infty} = 0.001 \nonumber$$

$$\left\| \Delta X \right\|_{\infty} = 5.999 \nonumber$$

Відносна зміна норми вектора розчину дорівнює

$$\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} = \frac{5.999}{2} \nonumber$$

$$\ = 2.9995 \nonumber$$

Відносна зміна норми вектора правого боку дорівнює

$$\frac{\left\| \Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} = \frac{0.001}{7.999} \nonumber$$

$$\ = 1.250 \times 10^{- 4} \nonumber$$

$1.250 \times 10^{- 4}$Див. Мала відносна зміна норми правого вектора призводить до великої відносної зміни норми вектора розв'язку 2,9995.

По суті, співвідношення між відносною зміною норми вектора розв'язку і відносною зміною норми правого вектора дорівнює

$$\begin{split} \frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta C \right\|_{\infty}/\left\| C \right\|_{\infty}} &= \frac{2.9995}{1.250 \times 10^{- 4}}\\ &= 23993 \end{split} \nonumber$$

Давайте тепер повернемося до добре обумовленої системи рівнянь.

$$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix} \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber$$

Позначення системи рівнянь по

$$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber$$

$$\left\| X \right\|_{\infty} = 2 \nonumber$$

$$\left\| C \right\|_{\infty} = 7 \nonumber$$

Внесення невеликої зміни в правій частині вектора

$$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix} \nonumber$$

дає

$$\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} \nonumber$$

Позначення вищевказаного набору рівнянь

$$\left\lbrack A \right\rbrack\left\lbrack X' \right\rbrack = \left\lbrack C' \right\rbrack \nonumber$$

зміна вектора правого боку потім знаходить

$$\left\lbrack \Delta C \right\rbrack = \left\lbrack C' \right\rbrack - \left\lbrack C \right\rbrack \nonumber$$

і зміна вектора розв'язку

$$\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber$$

потім

$$\begin{split} \left\lbrack \Delta C \right\rbrack &= \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix} - \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.001 \\ 0.001 \\ \end{bmatrix} \end{split} \nonumber$$

і

$$\begin{split} \left\lbrack \Delta X \right\rbrack &= \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} - \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}\\ &= \begin{bmatrix} - 0.001 \\ 0.001 \\ \end{bmatrix} \end{split} \nonumber$$

потім

$$\left\| \Delta C \right\|_{\infty} = 0.001 \nonumber$$

$$\left\| \Delta X \right\|_{\infty} = 0.001 \nonumber$$

Відносна зміна норми вектора розчину дорівнює

$$\begin{split} \frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} &= \frac{0.001}{2}\\ &= 5 \times 10^{- 4} \end{split} \nonumber$$

Відносна зміна норми вектора правого боку дорівнює

$$\begin{split} \frac{\left\| \Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} &= \frac{0.001}{7}\\ &= 1.429 \times 10^{- 4} \end{split} \nonumber$$

Див. Малу відносну зміну норми правого вектора$1.429 \times 10^{- 4}$ результатів при малій відносній зміні вектора розв'язку норми$5 \times 10^{- 4}$.

По суті, співвідношення між відносною зміною норми вектора розв'язку і відносною зміною норми правого вектора дорівнює

$$\begin{split} \frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta C \right\|_{\infty}/\left\| C \right\|_{\infty}} &= \frac{5 \times 10^{- 4}}{1.429 \times 10^{- 4}}\\ &= 3.5 \end{split} \nonumber$$

Які деякі властивості норм?

1. Для матриці$\lbrack A\rbrack$,$\left\| A \right\| \geq 0$
2. Для матриці$\lbrack A\rbrack$ і скаляра k,$\left\| {kA} \right\| = \left| k \right|\left\| A \right\|$
3. Для двох матриць$\lbrack A\rbrack$ і$\lbrack B\rbrack$ одного порядку,$\left\| A + B \right\| \leq \left\| A \right\| + \left\| B \right\|$
4. Для двох матриць$\lbrack A\rbrack$ і$\lbrack B\rbrack$ які можна помножити як$\lbrack A\rbrack\ \lbrack B\rbrack$,$\left\| {AB} \right\| \leq \left\| A \right\|\left\| B \right\|$

Чи існує загальний зв'язок, який існує між$\left\| \mathbf{\Delta}\mathbf{X} \right\|\mathbf{/}\left\| \mathbf{X} \right\|$ і$\left\| \mathbf{\Delta}\mathbf{C} \right\|\mathbf{/}\left\| \mathbf{C} \right\|$ або між$\left\| \mathbf{\Delta}\mathbf{X} \right\|\mathbf{/}\left\| \mathbf{X} \right\|$ і$\left\| \mathbf{\Delta}\mathbf{A} \right\|\mathbf{/}\left\| \mathbf{A} \right\|$? Якщо так, то це може допомогти нам визначити добре обумовлену і погано обумовлену систему рівнянь.

Якщо є такий зв'язок, чи допоможе це нам кількісно оцінити обумовлення матриці? Тобто, чи скаже це нам, скільки значущих цифр ми могли б довіряти у розв'язанні системи одночасних лінійних рівнянь?

Існує зв'язок, яка існує між

$$\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\text{and}\frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber$$

і між

$$\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\text{and}\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber$$

Ці відносини

$$\frac{\left\| \Delta X \right\|}{\left\| X \right\|} \leq \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber$$

і

$$\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|}\leq \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber$$

Наведені вище дві нерівності показують, що відносна зміна норми правого вектора або матриці коефіцієнта може посилюватися на стільки ж, скільки$\left\| A \right\|\left\| A^{- 1} \right\|$.

Це число$\left\| A \right\|\left\| A^{- 1} \right\|$ називається умовою номер матриці і в поєднанні з машиною епсилон, ми можемо кількісно оцінити точність рішення$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$.

Доведіть для

$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$

що

$$\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|} \leq \ \ \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber$$

Доказ

Нехай

$$\left\lbrack A \right\rbrack{\ \ }\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \;\;\;\;\;\;\;(1) \nonumber$$

Тоді якщо буде$\lbrack A\rbrack$ змінено на$\left\lbrack A' \right\rbrack$, то$\lbrack X\rbrack$ зміниться на$\left\lbrack X' \right\rbrack$, такий

що

$$\left\lbrack A' \right\rbrack{\ \ }\left\lbrack X' \right\rbrack = \left\lbrack C \right\rbrack\;\;\;\;\;\;\;(2) \nonumber$$

З рівнянь (1) і (2),

$$\left\lbrack A \right\rbrack{\ \ }\left\lbrack X \right\rbrack = \left\lbrack A' \right\rbrack\left\lbrack X' \right\rbrack \nonumber$$

Позначення зміни$\lbrack X\rbrack$ матриць$\lbrack A\rbrack$ і як$\left\lbrack \Delta A \right\rbrack$ і$\left\lbrack \Delta X \right\rbrack$, відповідно

$$\left\lbrack \Delta A \right\rbrack = \left\lbrack A' \right\rbrack - \left\lbrack A \right\rbrack \nonumber$$

$$\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber$$

потім

$$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \ \ \left( \left\lbrack A \right\rbrack + \left\lbrack \Delta A \right\rbrack \right)\ \left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber$$

Розширення вищевказаного виразу

$$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \ \left\lbrack A \right\rbrack\left\lbrack X \right\rbrack + \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left\lbrack X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left\lbrack \Delta X \right\rbrack \nonumber$$

$$\lbrack 0\rbrack = \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber$$

$$- \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack = \left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber$$

$$\left\lbrack \Delta X \right\rbrack = - \left\lbrack A \right\rbrack^{- 1}\left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber$$

Застосовуючи теорему норм, що норма множених матриць менше множення окремих норм матриць,

$$\left\| \Delta X \right\|\leq \left\| A^{- 1} \right\| \left\| \Delta A \right\| \left\| X + \Delta X \right\| \nonumber$$

Множення обох сторін на$\left\| A \right\|$

$$\left\| A \right\|\ \left\| \Delta X \right\|\leq \left\| A \right\| \left\| A^{- 1} \right\| \left\| \Delta A \right\|\left\| X + \Delta X \right\| \nonumber$$

$$\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|}\leq \left\| A \right\|\ \left\| A^{- 1} \right\|\ \frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber$$

Як використовувати наведені вище теореми, щоб знайти, скільки значущих цифр є правильними в моєму векторі рішення?

Відносна похибка в нормі вектора розв'язку дорівнює$\times$ відносній похибці$\leq$ Cond (A) у нормі правого вектора.

Можлива відносна похибка в нормі вектора розв'язку дорівнює$\leq$$Cond(A) \times \in_{mach}$

Звідси$Cond(A) \times \in_{mach}$ слід дати нам кількість значущих цифр, m які є хоча б правильними в нашому рішенні, з'ясувавши найбільше значення m для$Cond(A) \times \in_{mach}$ якого менше$0.5 \times 10^{- m}$.

Приклад 4

Скільки значущих цифр можна довіряти в розв'язанні наступної системи рівнянь?

$$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix} \nonumber$$

Рішення

Для

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\ \nonumber$$

це може бути показано

$$\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 3999 & 2000 \\ 2000 & - 1000 \\ \end{bmatrix}\ \nonumber$$

$$\left\| A \right\|_{\infty} = 5.999 \nonumber$$

$$\left\| A^{- 1} \right\|_{\infty} = 5999 \nonumber$$

$$\begin{split} {Cond}\left( A \right) &= \left\| A \right\|\left\| A^{- 1} \right\|\\ &= 5.999 \times 5999.4\\ &= 35990 \end{split} \nonumber$$

Припускаючи одинарну точність з 23 бітами, що використовуються в мантиссі для дійсних чисел, машина epsilon є

$$\begin{split} \in_{mach} &= 2^{- 23}\\ &= 0.119209 \times 10^{- 6} \end{split} \nonumber$$

$$\begin{split} {Cond}(A) \times \in_{mach} &= 35990 \times 0.119209 \times 10^{- 6}\\ &= 0.4290 \times 10^{- 2} \end{split} \nonumber$$

Для чого максимальне додатне значення m,${Cond}(A) \times \in_{mach}$ буде менше або дорівнює$0.5 \times 10^{- m}$

$$0.4290 \times 10^{- 2} \leq 0.5 \times 10^{- m} \nonumber$$

$$0.8580 \times 10^{- 2} \leq 10^{- m} \nonumber$$

$$log(0.8580 \times 10^{- 2}) \leq log(10^{- m}) \nonumber$$

$$- 2.067 \leq - m \nonumber$$

$$m \leq 2.067 \nonumber$$

$$m \leq 2 \nonumber$$

Отже, дві значущі цифри є принаймні правильними в векторі розв'язку.

Приклад 5

Скільки значущих цифр можна довіряти в розв'язанні наступної системи рівнянь?

$$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix} \nonumber$$

Рішення

Для

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \nonumber$$

це може бути показано

$$\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 3 & 2 \\ 2 & - 1 \\ \end{bmatrix}\ \nonumber$$

Тоді

$$\left\| A \right\|_{\infty} = 5, \nonumber$$

$$\left\| A^{- 1} \right\|_{\infty} = 5. \nonumber$$

$$\begin{split} Cond\ (A) &= \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\\ &= 5 \times 5\\ &= 25 \end{split} \nonumber$$

Припускаючи одинарну точність з 23 бітами, що використовуються в мантиссі для дійсних чисел, машина epsilon

$$\begin{split} \in_{mach} &= 2^{- 23}\\ &= 0.119209 \times 10^{- 6} \end{split} \nonumber$$

$$\begin{split} {Cond}(A) \times \in_{mach} &= 25 \times 0.119209 \times 10^{- 6}\\ &= 0.2980 \times 10^{- 5} \end{split} \nonumber$$

Для чого максимальне додатне значення m,${Cond}(A) \times \in_{mach}$ буде менше або дорівнює$0.5 \times 10^{- m}$

$$0.2980 \times 10^{- 5} \leq 0.5 \times 10^{- m} \nonumber$$

$$m \leq 5 \nonumber$$

Отже, п'ять значущих цифр є принаймні правильними в векторі розв'язку.

Адекватність рішень вікторини

Вікторина 1

Норма суми рядків матриці

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 6 & - 7 & 3 & 13 \\ 19 & - 21 & 23 & - 29 \\ 41 & 47 & - 51 & 61 \\ \end{bmatrix} \nonumber$$ є

(А)$29$

(Б)$61$

(С)$98$

(D)$200$

Вікторина 2

Адекватність розв'язку одночасних лінійних рівнянь $$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber$$ залежить від

(A) умова номер матриці коефіцієнта$\left\lbrack A \right\rbrack$

(B) машина епсилон

(C) номер умови для матриці$\left\lbrack A \right\rbrack$ та машини epsilon

(D) норма матриці коефіцієнтів$\left\lbrack A \right\rbrack$

Вікторина 3

З огляду на набір рівнянь у матричній формі, $$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack, \nonumber$$ $$\left\| A \right\| = 250,\left\| A^{- 1} \right\| = 40 \;\;and \nonumber$$ $$\varepsilon_{mach} = 0.119 \times 10^{- 6}, \nonumber$$ то кількість значущих цифр, яким можна хоча б довіряти розв'язку, дорівнює.

(А)$1$

(Б)$2$

(С)$3$

(D)$4$

Вікторина 4

Розв'язок множини одночасних лінійних рівнянь

$$\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 44 \\ 94 \\ 138 \\ \end{bmatrix} \nonumber$$ дається як

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ 7 \\ \end{bmatrix} \nonumber$$ Розв'язок іншого набору одночасних лінійних рівнянь задається (зверніть увагу, що матриця коефіцієнтів така ж, як і вище)

$$\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 43.99 \\ 93.98 \\ 138.03 \\ \end{bmatrix} \nonumber$$

дається як

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 214.01 \\ - 208.01 \\ 60 \\ \end{bmatrix} \nonumber$$

Виходячи з норми суми рядків, номер умови матриці коефіцієнтів більше (вибираємо максимально можливе значення)

(А)$1$

(Б)$138$

(С)$4500$

(D)$139320$

Вікторина 5

Номер умови матриці$n \times n$ ідентичності на основі норми суми рядків дорівнює

(А)$0$

(Б)$1$

(С)$n$

(D)$n^{2}$

Вікторина 6

Нехай$\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 + \delta \\ 2 - \delta & 1 \\ \end{bmatrix}$. Виходячи з норми суми рядків і враховуючи$\delta \rightarrow 0$$\delta > 0$, що, умова номер матриці дорівнює

(А)$\displaystyle \frac{3 - \delta}{3 + \delta}$

(Б)$\displaystyle \frac{9 - \delta^{2}}{3 - \delta^{2}}$

(С)$\displaystyle \frac{(3 + \delta)^{2}}{3 - \delta^{2}}$

(D)$\displaystyle \frac{3 - 2\delta - \delta^{2}}{3 - \delta^{2}}$

Адекватність рішень вправи

Вправа 1

Адекватність розв'язку одночасних лінійних рівнянь залежить від

1. Номер умови
2. машина Епсілон
3. Твір номера стану та машина epsilon
4. Норма матриці.

Відповідь

C

Вправа 2

Якщо система рівнянь погано$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$ обумовлена, то

1. $det(A) = 0$
2. $Cond(A) = 1$
3. $Cond(A)$великий.
4. $\left\| A \right\|$великий.

Відповідь

C

Вправа 3

Якщо$Cond(A) = 10^{4}$ і$\in_{mach}$ = 0,119$\times$ 10 ^-6, то в$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$, принаймні ці багато значущих цифр вірні у вашому рішенні,

1. $0$
2. $1$
3. $2$
4. $3$

Відповідь

C

Вправа 4

Зробіть невелику зміну в матриці коефіцієнтів$\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}$
і знайдіть
$$\frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta A \right\|_{\infty}/\left\| A \right\|_{\infty}} \nonumber$$

Це велика чи мала кількість? Як це число пов'язане з номером умови матриці коефіцієнтів?

Відповідь

Зміна$\lbrack A\rbrack$ на

$$\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 4.000 \\ \end{bmatrix} \nonumber$$

Результати в розв'язці

$$\begin{bmatrix} 5999 \\ -2999 \\ \end{bmatrix} \nonumber$$

$$\frac{\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}}}{\frac{\left\| \Delta A \right\|_{\infty}}{\left\| A \right\|_{\infty}}} = \frac{\frac{5999.7}{2}}{\frac{0.002}{5.999}} \nonumber$$

4$= 8.994 \times 10^{6}$ $

Вправа 5

Зробіть невелику зміну в матриці коефіцієнтів
$\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \ 7 \\ \end{bmatrix}$
і знайдіть
$$\frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta A \right\|_{\infty}/\left\| A \right\|_{\infty}}. \nonumber$$ це велике чи маленьке число? Порівняйте свої результати з попередньою проблемою. Як це число пов'язане з номером умови матриці коефіцієнтів?

Відповідь

Зміна$\lbrack A\rbrack$ на

$$\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.000 \\ \end{bmatrix} \nonumber$$

Результати в розв'язці

$$\begin{bmatrix} 2.003 \\ 0.9970 \\ \end{bmatrix} \nonumber$$

$$\frac{\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}}}{\frac{\left\| \Delta A \right\|_{\infty}}{\left\| A \right\|_{\infty}}} = \frac{\frac{0.003}{2.000}}{\frac{0.002}{5}} \nonumber$$

$$= 3.75 \nonumber$$

Вправа 6

Довести

$$\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\ \ \left\| A \right\|\ \left\| A^{- 1} \right\|\ \frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber$$

Відповідь

Використовуйте теорему, що якщо$\lbrack A\rbrack\lbrack B\rbrack = \lbrack C\rbrack$ тоді$\left\| A \right\|\left\| B \right\| \geq \left\| C \right\|$

Вправа 7

Для

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix} \nonumber$$

дає

$$\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 0.1099 & - 0.2333 & 0.2799 \\ - 0.2999 & - 0.3332 & 0.3999 \\ 0.04995 & 0.1666 & 6.664 \times 10^{- 5} \\ \end{bmatrix} \nonumber$$

1. Що таке умова номер$\lbrack A\rbrack$?
2. Скільки значущих цифр ми можемо хоча б довіряти в рішенні$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$ if$\in_{mach} = 0.1192 \times 10^{- 6}$?
3. Не обчислюючи обернену матрицю$\lbrack A\rbrack$, чи можете ви оцінити номер умови$\lbrack A\rbrack$ використання теореми в задачі #6?

Відповідь

А.$\left\| A \right\| = 17$
$\left\| A^{- 1} \right\| = 1.033$
${Cond}(A)=17.56$

Б. 5

Спробуйте різні значення правої сторони з знаками,$C = \lbrack \pm 1\ \ \pm 1\ \ \pm 1\rbrack^{T}$ вибраними випадковим чином. Потім$\left\| A^{- 1} \right\| \leq \left\| X \right\|$ отримане від розв'язання рівняння встановлюється$\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack$ як$\left\| C \right\| = 1$.

Вправа 8

Доведіть, що${Cond}(A) \geq 1$.

Відповідь

Ми знаємо, що

$$\left\| A\ B \right\| \leq \left\| A \right\|\left\| B \right\| \nonumber$$

то якщо

$$\lbrack B\rbrack = \lbrack A\rbrack^{- 1}, \nonumber$$

$$\left\| A\ A^{- 1} \right\| \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber$$

$$\left\| I \right\| \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber$$

$$1 \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber$$

$$\left\| A \right\|\left\| A^{- 1} \right\| \geq 1 \nonumber$$

$${Cond}(A) \geq 1 \nonumber$$