Наближені обернені матриці та число обумовленості

Близько 32 років тому я опублікував те, що дехто описував як «елегантний результат» щодо числа обумовленості матриці. Він стверджує, що невироджена матриця має суттєво різні наближені праву та ліву обернені тоді і тільки тоді, коли вона є погано обумовленою. Однак я не опублікував доведення. Доведення не є особливо складним. Тут воно публікується вперше.

Усі наведені нижче результати стосуються скінченновимірних дійсних векторних просторів. Вектори зазвичай подаються стовпчиковими векторами. Усі вектори мають однаковий розмір, а всі матриці є квадратними дійсними матрицями з такою ж кількістю рядків, як у векторів.

Існують стандартні узагальнення на скінченновимірні комплексні векторні простори, але деякі результати не є правильними у нескінченновимірному випадку.

Означення. Норма вектора це дійснозначна функція ||x|| від вектора x така, що для всіх векторів x і y та всіх скалярів c:

1. ||x|| >= 0 з рівністю тоді і тільки тоді, коли x є нульовим.
2. ||cx|| = |c| ||x||.
3. ||x + y|| <= ||x|| + ||y||.

Одним прикладом норми вектора є евклідова норма:

||x|| = sqrt(x^T x).

Іншим прикладом є «максимальна норма»:

||x|| = max (|x₁|, |x₂|, ..., |x_n|),

де x₁, x₂, ..., x_n є компонентами вектора x.

Означення. Норма матриці, що відповідає нормі вектора, це дійснозначна функція ||A|| від матриці A, визначена як

||A|| = sup _{||x|| = 1} ||Ax||.

Аргументи компактності показують, що супремум завжди існує і досягається, отже завжди існує принаймні один ненульовий вектор x, для якого

||Ax|| = ||A|| ||x||.

||Ax|| <= ||A|| ||x||,

1. ||A|| >= 0 з рівністю тоді і тільки тоді, коли A = 0.
2. ||cA|| = |c| ||A||.
3. ||A + B|| <= ||A|| + ||B||.
4. ||AB|| <= ||A|| ||B||.

Означення. Число обумовленості невиродженої матриці A відносно норми матриці це

||A|| ||A^-1||.

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

Доведення наступного твердження потребує деякої теорії опуклості див. Додаток A.

Твердження. Для будь-якої норми вектора і будь-якої пари векторів x і y з ненульовим x існує матриця A така, що Ax = y і ||A|| = ||y|| / ||x||.

Доведення. Множина {z | ||z|| <= ||x||} є обмеженою та опуклою і x лежить на її межі. Отже існує опорна гіперплощина іноді її називають дотичною гіперплощиною у точці x. Тоді існує базис

x, s₂ , s₃, ..., s_n,

у якому всі вектори, крім x, паралельні опорній гіперплощині.

Нехай тепер A це матриця лінійного відображення, яке переводить x у y, а кожен інший базисний вектор у нуль, тобто для будь-якого вектора w

w = cx + c₂s₂ + c₃s₃ + ... + c_ns_n,

Aw = cy.

Тоді якщо c не дорівнює нулю,

w/c = x + (c₂/c)s₂ + (c₃/c)s₃ + ... + (c_n/c)s_n .

Оскільки w/c лежить на опорній гіперплощині, він має лежати на межі або поза множиною {z | ||z|| <= ||x||}. Отже

||w/c|| >= ||x||,

||w|| >= |c| ||x||.

Отже

||Aw|| / ||w|| = ||cy|| / ||w|| <= (|c| ||y||) / (|c| ||x||) = ||y|| / ||x||.

Якщо c = 0, тоді ||Aw|| = 0, тому нерівність також виконується. Крім того, маємо рівність при w = x. Отже

||A|| = ||y|| / ||x||.

Теорема. Для будь-якої невиродженої дійсної матриці A і будь-якої дійсної матриці B, що не дорівнює оберненій до A,

||AB - I|| / ||BA - I|| <= ||A|| ||A^-1||,

з рівністю для деякої матриці B, довільно близької до оберненої до A.

Також

||BA - I|| / ||AB - I|| <= ||A|| ||A^-1||,

з рівністю для деякої матриці B, довільно близької до оберненої до A.

Доведення. Нехай D = BA - I. Тоді перше твердження набуває вигляду

||ADA^-1|| / ||D|| <= ||A|| ||A^-1||,

з рівністю для деякого ненульового D. Ми можемо зробити D довільно близьким до нуля, просто масштабуючи його.

Тепер за властивістю (4) вище нерівність легко довести. Щоб довести існування матриці D, для якої досягається рівність, нехай x і y ненульові вектори такі, що

||A^-1x|| = ||A^-1|| ||x||,

||Ay|| = ||A|| ||y||.

Нехай D матриця така, що

D(A^-1x) = y,

||D|| = ||y|| / ||A^-1x|| .

Тоді

||ADA^-1|| ||x|| >= ||ADA^-1x|| = ||Ay|| = ||A|| ||y|| = ||A|| ||A^-1x|| ||D|| = ||A|| ||A^-1|| ||x|| ||D||,

звідки бажаний результат випливає безпосередньо.

Доведення іншого твердження є подібним.

Додаток A Мала теорія опуклості

Цю частину було додано 30 жовтня 2006.

Підмножина C простору ℜⁿ називається опуклою, якщо для будь-яких x і y з C відрізок, що їх з’єднує, також належить C, тобто tx + (1 t)y належить C для кожного t між 0 і 1.

Легко показати, що внутрішність і замикання опуклої множини також є опуклими, і що перетин двох опуклих множин є опуклим.

m вимірний симплекс простору ℜⁿ це множина всіх лінійних комбінацій m + 1 точок x₀, x₁, x₂, ... , x_m з невід’ємними коефіцієнтами, сума яких дорівнює 1:

{a₀x₀ + a₁x₁ + a₂x₂ + ... + a_mx_m | a₀ + a₁ + a₂ + ... + a_m = 1, a₀ >= 0, a₁ >= 0, a₂ >= 0, ..., a_m >= 0},

де вектори x₁ x₀, x₂ x₀, ... , x_m x₀ є лінійно незалежними.

Одновимірний симплекс це відрізок, двовимірний симплекс це трикутник, а тривимірний симплекс це тетраедр.

Легко показати, що якщо опукла множина містить усі вершини симплекса, то вона містить кожну точку симплекса.

Гіперплощина це перенесений підпростір розмірності n 1 простору ℜⁿ, тобто має вигляд {h + s | s належить S}, де h точка на гіперплощині, а S підпростір розмірності n 1 простору ℜⁿ. Гіперплощина називається гіперплощиною, що проходить через h і паралельна S. Гіперплощина в ℜ¹ це точка, в ℜ² це пряма, а в ℜ³ це площина.

Теорема A.1. Гіперплощина в ℜⁿ ділить простір ℜⁿ на дві частини, точніше доповнення гіперплощини складається з двох неперетинних відкритих множин, які називаються двома сторонами гіперплощини. Крім того, відрізок з однієї сторони на іншу проходить через гіперплощину.

Доведення. Нехай гіперплощина проходить через h і паралельна S, а s₁, s₂, ..., s_n-1 базис для S. Для будь-якого x з ℜⁿ нехай f(x) визначник матриці, стовпці якої s₁, s₂, ..., s_n-1 і x h. Тоді f(x) = 0 тоді і тільки тоді, коли x лежить на гіперплощині. Оскільки f неперервна, множини {x з ℜⁿ | f(x) < 0} і {x з ℜⁿ | f(x) > 0} є потрібними відкритими множинами.

Теорему про проміжні значення можна використати для доведення іншої частини.

Теорема A.2. Для непорожньої опуклої множини C в ℜⁿ і точки x поза C існує гіперплощина, що відокремлює C від x, тобто x і C лежать по різні боки гіперплощини.

Доведення. Розглянемо точку c у замиканні C, найближчу до x у звичайній евклідовій метриці. Стандартні аргументи компактності показують, що така точка існує.

Оскільки x лежить поза C, c відрізняється від x. Отже існує підпростір S розмірності n 1 простору ℜⁿ, перпендикулярний відрізку, що з’єднує c і x, і існує гіперплощина, що проходить через середину цього відрізка і паралельна S.

Точки x і c лежать по різні боки гіперплощини.

Тепер припустимо для доведення від супротивного, що існує точка d з C на гіперплощині або з того ж боку, що й x. Оскільки замикання C є опуклим, відрізок від d до c повністю лежить у замиканні C. Ілюстрація показує співвідношення у двовимірній площині, що містить d, c і x. Кут dcx гострий, тому деяка точка на відрізку достатньо близько до c має бути ближчою до x, ніж c, що суперечить вибору c як найближчої точки замикання C до x.

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

Твердження A.3. Нехай S опукла множина в ℜⁿ, а b гранична точка S. Тоді існують точки поза S, довільно близькі до b.

Доведення. Припустимо для доведення від супротивного, що деякий окол b не містить точок поза S. Тоді кожна точка в околі є або граничною, або внутрішньою точкою S.

Тепер побудуємо n вимірний симплекс всередині околу з b у його внутрішності. Вершини симплекса мають бути або точками з S, або граничними точками S. У будь-якому випадку існують точки довільно близькі до них, що належать S. Виберемо такі точки, щоб побудувати трохи спотворений симплекс, який все ще містить b.

Оскільки S опукла, вона містить усі точки спотвореного симплекса. Отже точка b є внутрішньою точкою S. Це і є потрібна суперечність.

Гіперплощина називається дотичною або опорною гіперплощиною множини в ℜⁿ у граничній точці, якщо гіперплощина містить цю точку і всі інші точки множини, що не лежать на гіперплощині, розташовані по один бік від неї.

Теорема A.4. Опукла множина в ℜⁿ має принаймні одну дотичну гіперплощину в кожній граничній точці.

Доведення. Нехай b гранична точка опуклої множини S, і нехай x₁, x₂₁, ... послідовність зовнішніх точок, що наближаються до b. За теоремою A.3 для кожного x_i існує гіперплощина H_i, що відокремлює b від S. Деяка підпослідовність цих гіперплощин збігається до потрібної дотичної гіперплощини.

Можна запитати, як можуть збігатися гіперплощини. Просто пов’яжемо H_i з точкою її перетину з прямою, що з’єднує x_i з найближчою точкою замикання S, і з нормованим базисом її підпростору S. Координати всіх цих векторів обмежені, тому всі вони мають збіжні підпослідовності.