Приблизні матричні інверсії та номер умови

Посилання на оригінальну статтю: http://www.efgh.com/math/invcond.htm

 

Філіп Дж. Ердельський (Philip J. Erdelsky)

9 червня 2001 року

 

Надішліть коментарі, виправлення та доповнення електронною поштою веб-майстру за адресою pje@efgh.com.

 

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

Всі наступні результати стосуються скінченно-мірних дійсних векторних просторів. Вектори умовно представлені векторами COLUMN (тобто колонками). Всі вектори мають однаковий розмір і всі матриці є квадратними реальними матрицями з однаковим числом рядків, що й вектори.

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

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

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

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

||x|| = sqrt(xTx).

Ще одна «максимальна норма»:

||x|| = max (|x 1|, |x 2|, …, |x n|),

де x 1 , x 2 , …, x n – записи у векторі x.

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

||A|| = sup ||x|| = 1 |Ax|

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

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

Альтернативно || може бути визначено як таке число, що

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

для всіх x, при рівності для принаймні одного ненульового x. Досить легко довести, що якщо A і B є матрицями, а c – скаляром,

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

Визначення. Номер умови несингулярної матриці А відносно матричної норми

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

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

Доведення наступного твердження вимагає деякої теорії опуклості (див. Додаток А ).

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

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

x, s 2 , s 3 , …, s n ,

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

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

w = cx + c 2 s 2 + c 3 s 3 + … + n n n ,

Aw = cy.

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

w/c = x + (c2/c) s 2 + (c3/c) s 3 + … + (cn/c) sn.

Оскільки 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 -1 x|| = ||A -1|| ||x||,

||Аy|| = ||A|| ||y||.

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

D (A -1 x) = y,

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

Потім

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

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

Доказ іншого твердження подібний.

 

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

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

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

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

M-розмірний симплекс is n – множина всіх лінійних комбінацій m + 1 точок x 0 , x 1 , x 2 , …, x m (називаються вершинами ) з невід’ємними коефіцієнтами, сума яких дорівнює 1:

{a 0 x 0 + a 1 x 1 + a 2 x 2 + … + a m x m | 0 + a 1 + a 2 + … + a m = 1, a 0 > = 0, a 1 > = 0, a 2 > = 0, …, a m > = 0,

і де вектори x 1 -x 0 , x 2 -x 0 , …, x m -x 0 лінійно незалежні.

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

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

Гіперплоскость є перекладеним (n-1) -мірним підпространством, n , тобто має вигляд {h + s | s в S}, де h – точка в гіперплощині, а S – (n-1) -мірне підпростір S of ℜ n . (Це уявлення не є унікальним, оскільки h може бути будь-якою точкою на гіперплощині.) Гіперплоскою називають гіперплоскою, що проходить через h і паралельною S. Гіперплоскость у is 1 є точкою, гіперплоскою у is 2 є пряма, а гіперплотка в ℜ 3 – площина.

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

Доказ . Припустимо, що гіперплотка проходить через h і паралельна S, і нехай s 1 , s 2 , …, s n-1 є основою для S. Для будь-якого x в ℜ n нехай f (x) є визначником матриця, стовпці якої є s 1 , s 2 , …, s n-1 і xh. Тоді f (x) = 0 if, і тільки якщо, x знаходиться на гіперплощині. Оскільки f є неперервним, то дві множини {x in ℜ n | f (x) <0} і {x in ℜ n | f (x)> 0} є необхідними відкритими множинами.

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

Теорема A.2. З урахуванням непустої опуклої множини C в and n і точки x у зовнішній частині C існує гіперплоскость, що відокремлює C від x; тобто x і C лежать на протилежних сторонах гіперплощини.

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

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

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

 

 

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

ілюстрації

 

 

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

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

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

 

 

 

 

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

ілюстрації

 

 

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

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

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

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

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