5.5: Кондиціонування інверсії матриці

Зараз ми можемо вирішити деякі питання, які виникли в прикладі 1 лекції 4, щодо чутливості зворотного\(A^{-1}\) і рішення\(x = A^{-1}b\) збурень в\(A\) (та/або\(b\), якщо на те пішло). Спочатку розглянемо випадок, коли\(A\) є оборотним, і вивчимо чутливість\(A^{-1}\). Взявши диференціали в визначальному\(A^{-1}A = I\) рівнянні, знаходимо

\[d\left(A^{-1}\right) A+A^{-1} d A=0 \ \tag{5.23}\]

де, звичайно, важливий порядок термінів у кожній половині суми. (Замість того, щоб працювати з диференціалами, ми могли б еквівалентно працювати з збуреннями форми тощо\(A+\epsilon P\), де\(\epsilon\) зникає мало, але це дійсно дорівнює тому ж.) Переставляючи попередній вираз, знаходимо

\[d\left(A^{-1}\right) = A^{-1} d A A^{-1} \ \tag{5.24}\]

Беручи норми, результат

\[\left\|d\left(A^{-1}\right)\right\| \leq\left\|A^{-1}\right\|^{2}\|d A\| \ \tag{5.25}\]

або еквівалентно

\[\frac{\left\|d\left(A^{-1}\right)\right\|}{\left\|A^{-1}\right\|} \leq\|A\|\left\|A^{-1}\right\| \frac{\|d A\|}{\|A\|} \ \tag{5.26}\]

Ця деривація тримається для будь-якої субмультиплікативної норми. Твір\(\|A\|\left\|A^{-1}\right\|\) називається умовою номер по\(A\) відношенню до інверсії (або просто умова номер\(A\)) і позначається\(K(A)\):

\[K(A) = \|A\|\left\|A^{-1}\right\| \ \tag{5.27}\]

Коли ми хочемо вказати, яка норма використовується, до нього додається індекс\(K(A)\). Наші попередні результати на SVD показують, наприклад, що

\[K_{2}(A)=\sigma_{\max } / \sigma_{\min } \ \tag{5.28}\]

Число умови в цій 2-нормі говорить нам про те, наскільки струнким\(\|x\|_{2}=1\) є еліпсоїд\(Ax\) для - див. Рис. Далі ми зосередимося на 2-нормовому номері умови (але опустимо індекс, якщо це не суттєво).

Деякі властивості 2-нормового номера умови (всі вони легко показати, а деякі з яких поширюються на номер умови в інших нормах) є

• \(K(A) \geq 1;\)
• \(K(A) = K(A^{-1});\)
• \(K(AB) \leq K(A) K(B);\)
• З огляду\(U^{\prime}U = I\) на,\(K(UA) = K(A)\).

Важливість (5.26) полягає в тому, що межа насправді може бути досягнута для деякого вибору збурень\(dA\) та матричної норми, тому ситуація може стати настільки поганою, як дозволяє межа: дробова зміна в зворотному може бути в\(K(A)\) рази більшою, ніж дробова зміна оригіналу . У випадку з 2-нормами особливе збурення, яке досягає зв'язаного

Малюнок\(\PageIndex{1}\): Зображення того, як A (реальна\(2 \times 2\) матриця) відображає одиничне коло. Велика вісь еліпса відповідає найбільшому сингулярному значенню, малій - найменшому.

може бути отриманий\(\Delta\) з теореми 5.1, просто\(\Delta\) замінивши\(-\sigma_{n}\) в диференціальне збурення:

\[d A=-d \sigma u_{n} v_{n}^{\prime} \ \tag{5.29}\]

Встановлено, що великому умові число відповідає матриці, обернена якої дуже чутлива до відносно малих збурень у матриці. Таку матрицю називають погано обумовленою або погано обумовленою щодо інверсії. Ідеально обумовлена матриця - це та, чиє число умови приймає мінімально можливе значення, а саме 1.

Число високої умови також вказує на те, що матриця близька до втрати рангу, у наступному сенсі: Існує збуреність\(\Delta\) малої норми (\(=\sigma_{min}\)) щодо\(\|A\|\left(=\sigma_{\max }\right)\) такої, яка\(A + \Delta\) має нижчий ранг, ніж\(A\). Це випливає з нашого адитивного результату збурень в теоремі 5.1. Це тлумачення поширюється і на неквадратні матриці. Ми будемо вважати відношення в (5.28) умова число\(A\) парних, коли не\(A\) є квадратним, і думати про це як міра близькості до втрати рангу.

Перейшовши тепер до чутливості рішення\(x = A^{-1}b\) лінійної системи рівнянь за формою\(Ax = b\), можна поступити аналогічно. Беручи диференціали, ми виявляємо, що

\[d x=-A^{-1} d A A^{-1} b+A^{-1} d b=-A^{-1} d A x+A^{-1} b \ \tag{5.30}\]

Беручи норми, то врожайність

\[\|d x\| \leq\left\|A^{-1}\right\|\|d A\|\|x\|+\left\|A^{-1}\right\|\|d b\| \ \tag{5.31}\]

Розділивши обидві сторони цього на\(\|x\|\), і використовуючи те\(\|x\| \geq (\|b\|/\|A\|)\), що, отримуємо

\[\frac{\|d x\|}{\|x\|} \leq K(A)\left(\frac{\|d A\|}{\|A\|}+\frac{\|d b\|}{\|b\|}\right) \ \tag{5.32}\]

Ми можемо наблизитися до досягнення цієї межі, якщо, наприклад,\(b\) трапляється майже колінеарно з колоною\(U\) в SVD,\(A\) що пов'язано з\(\sigma_{min}\), і якщо виникають відповідні збурень. Знову ж таки, отже, дробове зміна відповіді може бути близьким до\(K(A)\) разів більше, ніж дробові зміни в заданих матрицях.

Приклад 5.2

Для матриці A, наведеної в прикладі 1 лекції 4, SVD є

\ [A=\ left (\ begin {масив} {cc}
100 & 100\\
100.2 & 100
\ кінець {масив}\ праворуч) =\ left (\ begin {масив} {cc}
.7068\
.7075 & .-7068
\ end {масив}\ праворуч)\ left (\ begin {масив} {cc}
200.1 & 0\\
0 & 0.1
\ end {масив}\ праворуч)\ лівий (\ begin {масив} {cc}
.7075 & .7068\\
-7068 & .7075
\ end {масив}\ праворуч)\\ тег {5.33}\]

Число умов\(A\) вважається 2001, що становить 1000-кратне збільшення похибки в зворотному для збурень, яке ми використовували в цьому прикладі. Збурення\(\Delta\) найменшої 2-норми, яка призводить\(A + \Delta\) до того, щоб стати одниною, є

\ [\ Delta=\ left (\ begin {масив} {cc}
.7068 & .7075\
.7075 & .-7068
\ кінець {масив}\ праворуч)\ лівий (\ begin {масив} {cc}
0 &
0\\ -0.1
\ end {масив}\ праворуч)\ лівий (\ початок {масив} {cc}
.7075 & .7068\\
-7068 & .7075
\ end {масив}\ праворуч)\ nonumber\]

норма якого дорівнює 0,1. Проведення множення дає

\ [\ Дельта\ приблизно\ ліворуч (\ begin {масив} {cc}
.05 & -.05\
-.05 & .05
\ end {масив}\ праворуч)\ nonumber\]

З\(b = [1 - 1]^{T}\), ми побачили велику чутливість розчину\(x\) до збурень в\(A\). Зауважте, що\(b\) це дійсно майже колінеарно з другим стовпцем\(U\). Якби, з іншого боку, у нас був\ (b=\ left [\ begin {array} {ll}
1 & 1
\ end {array}\ right]\), який більш тісно узгоджений з першим стовпцем\(U\), то рішення навряд чи вплинуло б збуренням в\(A\) - твердження, яке ми залишаємо вам для перевірки.

Таким чином,\(K(A)\) служить прив'язаним\(b\) до коефіцієнта збільшення, який пов'язує дробові зміни в нашому розчині\(A\) або з дробовими змінами\(x\).

Обґрунтування оцінки найменших квадратів

Наша мета в задачі оцінки найменших квадратних помилок полягала в тому, щоб знайти\(\widehat{x}\) значення,\(x\) яке мінімізує\(\|y-A x\|_{2}^{2}\), за припущенням, що\(A\) має повний ранг стовпця. Детальний аналіз обумовленості цього випадку виходить за межі нашої сфери (див. Матричні обчислення Голуба та Ван Лоана, наведені вище, для детального лікування). Ми зробимо це з твердженням основного результату в тому випадку, якщо дробовий залишковий набагато менше 1, тобто

\[\frac{\|y-A \widehat{x}\|_{2}}{\|y\|_{2}} \ll 1 \ \tag{5.34}\]

Цей випадок з низьким залишковим рівнем, безумовно, представляє інтерес на практиці, припускаючи, що один підходить досить гарну модель до даних. При цьому можна показати, що дробове\(\|d \widehat{x}\|_{2} /\|\widehat{x}\|_{2}\) зміна розв'язку\(\widehat{x}\) може наблизитися\(K(A)\) раз до суми дробових змін в\(A\) і\(y\), де\(K(A)=\sigma_{\max }(A) / \sigma_{\min }(A)\). У світлі наших попередніх результатів для випадку з оборотними\(A\), цей результат, мабуть, не дивно.

З огляду на цей результат, легко пояснити, навіщо вирішувати нормальні рівняння

\[\left(A^{\prime} A\right) \widehat{x}=A^{\prime} y\nonumber\]

визначити\(\widehat{x}\) чисельно непривабливо (в малозалишковому випадку). Числова інверсія\(A^{\prime}A\) регулюється умовою number of\(A^{\prime}A\), і це квадрат умови числа\(A\):

\[K\left(A^{\prime} A\right)=K^{2}\tag{A}\]

Ви повинні підтвердити це за допомогою SVD\(A\). Процес безпосереднього вирішення нормальних рівнянь, таким чином, призведе до помилок, які не є властивими задачі з найменшою квадратною помилкою, оскільки ця задача регулюється номером умови\(K(A)\), відповідно до результату, наведеним вище. На щастя, існують інші алгоритми обчислень,\(\widehat{x}\) які керуються номером умови,\(K(A)\) а не квадратом цього (і Matlab використовує один такий алгоритм для обчислення,\(\widehat{x}\) коли ви викликаєте команду рішення найменших квадратів).