Math10.com

 

Глава 13

УНИТАРНИ ДЕКОМПОЗИЦИИ

13 УНИТАРНИ ДЕКОМПОЗИЦИИ - 2 част

Нека да сме благодарни на проф. Михаил Константинов за разрешението да четем "Елементи на линейната алгебра: вектори и матрици" online.

13.1 Уводни бележки

В тази глава се разглеждат унитарните декомпозиции, или факторизации, на комплексна матрица и съответните им ортогонални аналози при реална матрица. Първо са разгледани елементарните унитарни матрици. После е описано преcмятането на унитарно-триъгълната, или QR-декомпозицията на матрица. Обсъдени са и някои свързани с това декомпозиции.

Разгледани са също декомпозицията на Шур и полярната декомпозиция на квадратна матрица. Накрая е разгледана декомпозицията по сингулярни числа на произволна матрица.

Унитарните и ортогоналните матрици са особено полезни при извършване на пресмятания в крайна аритметика тъй като техните елементи по абсолютна стойност не надхвърлят 1. По този начин елементите на преобразуваните матрици също не могат да нарастнат много. Също така при трансформации с унитарни или ортогонални матрици унитарно инвариантните норми на преобразуваните матрици обикновено се запазват, а другите матрични норми не се променят съществено. Това е важно предимство при пресмятания в изчислителна среда с плаваща точка, където грешките от закръгляне по принцип са пропорционални на абсолютните стойности на пресмятаните величини.

Ще припомним, че матрицата U F^nxn е унитарна ако U^HU = I_n, и ортогонална, ако U^TU = I_n. Важно е да се знае, че ортогоналните матрици могат и да са комплексни, а не са непременно реални.

Комплексната унитарна или реалната ортогонална матрица U се нарича също ортонормирана тъй като нейните стълбове u_i удовлетворяват условията u*_iu_j = 0 при i ≠ j и u*_iu_i = 1, където u* = u^H в комплексния случай и u* = U^T в реалния случай.

Множеството на комплексните унитарни матрици се означава с U(n), а множеството на ортогоналните n х n матрици над полето F - с O(n,F). Тези множества са мултипликативни групи относно стандартното матрично умножение.

Ако U U(n) или U O0(n,R), то ||U||₂ = 1 и ||U||_F = √n. Следователно U(n) С^nxn и O(n,R) R^nxn са централни затворени кълба с радиус √n относно метриката, породена от скаларните произведения = tr(U^HV) и = tr(U^TV) (или от нормата на Фробениус).

Ако дадена (комплексна) матрица U е представена като
U = U₀ + iU₁
където матриците U₀ и U₁ са реални, то тя е унитарна точно когато реалната матрица

е ортогонална (докажете!).

В много приложения, а и при някои теоретични разглеждания, една обща матрица А се декомпозира като произведение, включващо унитарни или ортогонални матрици, от вида
А = USV^H
или
А = USV^T,
където матрицата S има размерите на A, а матриците U и V са унитарни или ортогонални. Матриците U и V могат да са свързани (например V може да е равна на U), или пък една от тях може да е единичната матрица, или пък да е пермутационна матрица. Матрицата S е в опростена, или кондензирана форма, например триъгълна или даже диагонална. Тази кондензирана форма отразява инвариантната структура на матрицата А = [a_i,j] под действието на унитарните
А → S = U^HАV
или ортогоналните А → S = U^TAV.
трансформации.

Спектралната, или 2-нормата
||A||₂ = max{||Аx||₂ : ||x||₂ = 1} = &radicλ_max(А^HА)
и нормата на Фробениус, или F-нормата

играят важна роля при използването на унитарни и ортогонални трансформации. Причината е, че тези норми са унитарно инвариантни в смисъл, че описаните по-горе трансформации запазват нормата на преобразуваната матрица:
||S||₂ = ||A||₂, ||S||_F = ||A||_F.

Също така в сила е полезното неравенство
||AB||_F ≤ ||A||₂||В||_F,
което лесно се обобщава до неравенството
(1)
за всяко k {1,... , r} и r ≥ 2. Неравенството (1) ще бъде доказано по-късно.

13.2 Елементарни унитарни матрици

Една обща унитарна матрица може да се декомпозира като произведение от елементарни унитарни матрици. Има няколко вида унитарни матрици, които се смятат за елементарни в известен смисъл. Сред тях по-важни за приложенията са равнинните ротации (или ротациите на Гивънс) и елементарните отражения (или отраженията на Хаусхолдър).

Елементарната комплексна равнинна ротация е унитарна n х n матрица (n > 1), която се различава от единичната матрица I_n в не повече от четири позиции, заети от елементите на една 2 x 2 унитарна матрица. По-точно, ротация в (р, q)-равнината, p < q, е n х n матрица R_pq, чиито (i,k) елементи r_ik са определени както следва. Матрицата с размер 2 x 2
(2)
е унитарна (вж. упражнение 13.5), а r_ik е символът на Кронекер когато {i,k} ∩ {p,q} = 0.

Елементарната реална равнинна ротация се определя по подобен начин. Тя е реална ортогонална n х n матрица R_pq, като матрицата (2) е ортогонална, вж. упражнение 13.1.

При тази дефиниция може да се окаже, че в реалния случай подматрицата (2), а следователно и цялата матрица R_pq, имат детерминанта, равна на —1. В този случай и двете матрици са отражения в рамките на определението, според което една реална ортогонална матрица е ротация или отражение когато детерминантата й е равна на 1 или —1 съответно.

Един друг вид елементарни унитарни матрици са елементарните отражения. Нека u Cⁿ е ненулев вектор. Матрицата
Н(u) := I_n - 2uu^H/u^Hu C^nxn
се нарича комплексно елементарно (или хаусхолдърово) отражение. От това определение следва, че Н(u) = Н(αu) за всеки ненулев скалар α. Матрицата Н(u) е едновременно ермитова и унитарна.

Реалните елементарни отражения се определят аналогично от
Н(v) := I_n - 2vv^T/v^Tv R^nxn, 0 ≠ v Rⁿ.
Mатрицата Н(v) е едновременно симетрична и ортогонална.

Умножаването на отражение Н(u) по вектор х Cⁿ се свежда до пресмятане на едно скаларно произведение u^Hx, умножаване на вектор по скалар и изваждане на два вектора съгласно зависимостта
H(u)x = x - (2u^Hx/u^H)u.
В частност имаме
H(u)u = u - 2u^Hu/u^Hu)u = u -2u = -u,
и
det(H(u)) = -1.

Елементарните отражения водят своето наименование от факта, че изображението х → Н(u)х е отражение относно равнината
Кеr(u^H) = {x Cⁿ : u^Hx = 0}.
Действително, имаме
u^H(x + H(u)x) = 2u^H(x - uu^Hx/u^Hu) = 2(u^Hx - u^Hx) = 0,
т.е., векторът и е ортогонален на сумата от вектора х и неговия образ Н(u)х. Другояче казано, векторът u е колинеарен на разликата х — Н(u)х, тъй като векторите х и Н(u)х имат еднакви 2-норми. Следователно умножаването на вектор с матрицата Н(u) отразява този вектор относно равнината Кеr(u^H).

Като използваме тези съображения можем да получим едно много елегантно решение на следната задача. Нека са дадени два различни вектора х,у Cⁿ с еднакви 2-норми. Търси се унитарна матрица U, която преобразува х в у в смисъл, че у = Ux. От показаното по-горе отражателно свойство на преобразуванието с матрица Н(u) следва, че решението на тази задача е
U = Н(х - у),
т.е.,
H(х — у)х = у.

Често срещана в практиката задача е да се преобразува даден ненулев вектор х във вектор с единствен ненулев елемент, например в k-та позиция. Това се прави по следния начин.

Да предположим, че векторът х Сⁿ не е успореден (или пропорционален) на k-тия стълб е_k на единичната матрица I_n (ако векторът x е успореден на е_k няма какво да преобразуваме). Нека α С и |α| = 1. Тогава търсената трансформация е
Н(х - у)х = у, у := α||x||₂e_k (3)
Матрицата H(x — у) е коректно определена понеже у ≠ х.

В реалния случай x Rⁿ имаме а = ± 1 и съответно
H(x - у)x = у, у:= ±||х||₂е_k. (4)

Изборът на параметъра α в (3), съответно на знака в (4), се прави въз основа на числени съображения с оглед на избягване на възможно взаимно унищожение при изваждане на близки числа както следва.

Ако аргументът на елемента x_k на x е φ_k, т.е., ако
x_k = ρ_kexp(iφ_k), &rho_k ≥ 0,
то избираме аргумента на α като φ_k + π, което дава
а = -ехр(iφ_k). По този начин k-тият елемент на вектора х — у става
x_k - y_k = (ρ_k + ||x||₂)ехр(iφ_k).

Аналогично, в реалния случай когато елементът х_k е неотрицателен (съответно отрицателен) избираме у = ||х||₂е_k (съответно у = — ||х||₂е_k).

Тъй като матрицата

е едновременно ермитова и унитарна, имаме
х = Н(х - у)у = α||х||₂Н(х - у)е_k = α||х||₂h_k(х - у),
където h_k(х — у) е k-тият стълб на Н(х — у). Следователно матрицата Н(u) трансформира даден вектор х ≠ 0 в α||x||₂е_k, |α| = 1, точно когато нейният k-ти стълб h_k(u) е колинеарен на вектора х.

Сега сме в състояние да решим и следната задача. Даден е единичен вектор х Cⁿ и е необходимо да се намери n х (n — 1) матрица V, такава че матрицата U := [х,V] да бъде унитарна. Ако векторът х е колинеарен на някои стълб е_k на единичната матрица I_n, то V съдържа останалите стълбове на I_n. Нека в общия случай векторът х не е колинеарен на стълб на I_n. Нека h₁,..., h_n са стълбовете на отражението Н(х ± е₁), което трансформира х в е₁ (по-горе беше показано как се строи такова отражение). Тогава едно възможно решение на задачата е
V = [h₁,...,h_n].
Действително, в този случай имаме х = ±h₁.

13.3 QR декомпозиция

Трансформациите с елементарни унитарни матрици обикновено се използват за анулиране на елементите в зададени позиции на вектори и матрици, например за привеждане на вектор в множител на даден стълб на единичната матрица. С помощта на такива трансформации и в рамките на краен брой стъпки се получава унитарно-тригъгълната, или QR декомпозицията на обща правоъгълна матрица.

Да припомним първо какво представлява ешалонната форма на матрица.

Нека А = [a_i,j] e m х n матрица от ранг r ≥ 1. Да означим с k₁,..., k_r номерата на първите r линейно независими стълба на А. Нека s {1,... ,r} е зададено цяло число. Ще казваме, че матрицата А е в редова s-ешалонна форма, ако а_i,j = 0 при i = 1,..., s и j < k_i, както и при l = 1,..., s и i > k_l, j = k_l. Матрицата А е в редова ешалонна форма, ако тя е в редова r-ешалонна форма. Ще приемем също, че нулевата матрица е в редова ешалонна форма, както и че всяка матрица е в редова 0-ешалонна форма.

Така редовата ешалонна форма е матрица А с a_i,ki ≠ 0 при i = 1,... ,r и с нулеви елементи под всеки елемент а_i,ki. Ако А е в редова s-ешалонна форма, то а_i,ki ≠ 0 при i = 1,... ,s. Също така, ако А е в редова ешалонна форма, то а_i,j = 0 за i > r. Ясно е също, че ако А е в редова s-ешалонна форма с s ≥ 1, то тя е и в редова l-ешалонна форма за l = 1,..., s — 1.

Редовата ешалонна форма на A е горно триъгълна матрица, и даже горно трапецовидна матрица когато k_r > r, т.е., когато първите r стълба на А са линейно зависими.

Аналогично се дефинират стълбови ешалонни форми. В частност матрицата А е в стълбова ешалонна форма точно когато А^T е в редова ешалонна форма. По-долу са дадени примери за редови ешалонни форми.

Пример 13.1 Нека m = 4, n = 6, r = 3 и k₁ = 2, k₂ = 4, k₃ = 5. Редови 1,2,3-ешалонни форми са както следва:

Във всички тези редови ешалонни форми елементите, отбелязани с X, са произволни, първият стълб на A е нулев, а вторият, четвъртият и петият стълбове на А са линейно независими. В редовата 1-ешалонна форма първият „куршум" • (наричан също водещ елемент) е ненулев, а елементите, означени с а, са нулеви. В редовата 2-ешалонна форма първите два куршума са ненулеви, а елементите, означени с а и b, са нулеви. И накрая, в редовата ешалонна форма всичките три куршума са ненулеви, а елементите, означени с а, b и с, са нулеви.

Ако матрицата А F^mxn от ранг r е в редова s-ешалонна форма (s < m), то

където s X k_s матрицата A_s е в редова ешалонна форма, а (m — s) X (n — k_s) матрицата A_s+1 е от ранг r — s. По този начин редовите ешалонни форми разкриват последователно ранговата структура на съответната матрица.

Нека е дадена общата m х n матрица А от ранг r. Тогава можем да конструираме унитарна матрица Q U(n), такава че
А = QR (5)
където m х n матрицата R е в редова ешалонна форма. Ще отбележим, че ако r < m, то последните m — r реда на матрицата R са нулеви и следователно
(6)
където R₁ е r х n матрица от пълен редови ранг, а Q₁ е матрицата, формирана от първите r стълба на Q.

Факторизациите А = QR и А = Q₁R₁ се наричат съответно QR декомпозиция и кондензирана QR декомпозиция на матрицата А.

Понякога се разглежда QR декомпозиция, включваща десен множител, например,
А = QRП,
където П е n х n пермутационна матрица, избрана така, че първите r стълба на АП да бъдат линейно независими.

Използва се също и триъгълно-унитарната, или LQ декомпозиция
A = LР^Н,
където матрицата L е в стълбова ешалонна форма, а Р U(n). Когато r < n последните n — r стълба на L са нулеви и

Тук L₁ е матрица от пълен стълбов ранг и Р₁ е матрицата, формирана от първите r стълба на Р.

Когато матрицата А е реална всички матрици в QR и LQ декомпозициите могат да се изберат също реални. При това матриците Q и Р са ортогонални.

При някои допълнителни изисквания към матриците R и L, те се оказват канонични форми за действията
А → R = Q^HА
и
А → АР
на матричните групи U(m) и U(n) в множеството С^mxn. Например, за целта е достатъчно да се поиска водещите елементи в R и L да бъдат реални и положителни.

Нека l₁,..., l_r са номерата на първите r линейно независими реда на матрицата А и следователно на матрицата L. Каноничните форми R и L съдържат не повече от

ненулеви елемента (сред тях r положителни), съответно. Тези елементи формират алгебричната инварианта на матрицата А относно действията на ляво и дясно умножаване на групите U(m) и U(n). Генерично е изпълнено k_i = l_i = i и в този случай броят на скаларните алгебрични инварианти е r(2n — r + 1)/2 и r(2m — r + 1)/2 съответно.

Наредените целочислени r-торки (k₁,...,k_r) и (l₁,...,l_r) образуват аритметичните инварианти относно разгледаните по-горе действия. Аритметичната и алгебричната инварианти образуват пълно множество от инварианти относно мултипликативните действия на съответната унитарна матрична група.

Един директен краен алгоритъм за пресмятане на QR декомпозицията се основава на следното обстоятелство. Нека А е произволна m х n матрица и а е нейният първи ненулев стълб. Тогава елементарното отражение Н, което трансформира а във вектор На = α||a||₂e₁, |α| = 1, успореден на първия стълб e₁ на единичната матрица I_m, също така трансформира матрицата А в 1-ешалонна форма НА.

По-долу е описан алгоритъм за построяване на QR декомпозицията на матрица, като за удобство на читателя са дадени размерите на съответните подматрици.

На първата стъпка нека Н₁ е елементарното отражение, което трансформира матрицата А в редова 1-ешалонна форма,

където А₂ е (m — 1) X (n — k₁) матрица от ранг r — 1.

На втората стъпка нека Н'₂ е елементарното (m — 1) X (m — 1) отражение, което трансформира подматрицата А₂ в редова 1-ешалонна форма. Тогава отражението
H₂ := diag(1,H'₂)
не засяга първия ред на матрицата Н₁А и трансформира подматрицата А₂ в редова 1-ешалонна форма. В резултат матрицата Н₂Н₁А е в редова 2-ешалонна форма,
Н₂Н₁А =
където матрицата А₃ е с размери (m — 2) X (n — k₂) и е от ранг r - 2.

Продължавайки по същия начин, на s-тата стъпка получаваме матрицата
Н_s.....H₂Н₁А,
която е в редова s-ешалонна форма, и съответно (m — s) X (n — k_s) подматрицата А_s+1 от ранг r — s.

На r-тата стъпка процесът се прекъсва, тъй като подматрицата А_r+1 е нулева (в противен случай рангът на А щеше да надвишава r). Матрицата
R := Н_r.......Н₂Н₁А
е в редова ешалонна форма. Като положим
Q := (Н_r......Н₂Н₁)^H = Н₁Н₂......Н_r
получаваме желаната QR декомпозиция А = QR на матрицата А.

Като се използва QR декомпозицията на матрица може да се реши следната задача. Нека е дадена m х n матрицата X с n < m ортонормирани стълбове. Необходимо е да се намери m х (m — n) матрица Y, такава че матрицата [X, Y] да е унитарна. Решението е елегантно и просто. Ако X = QR е QR е декомпозиция на X, то Y може да се избере като матрицата, формирана от последните m — n стълба на Q.

Ако рангът r на А е по-малък от min{m,n} каноничните форми R и L могат да бъдат още компресирани с допълнителна унитарна трансформация. Така се получава т.нар. QCP декомпозиция, описана по-долу. Нека
R₁ = [C₁,0]Р^Н
е LQ декомпозицията на матрицата R₁ в (6). Тогава е в сила QСР декомпозицията
(7)
където r х r матрицата С₁ е неособена (тази декомпозиция понякога се нарича URV декомпозиция).

QCР декомпозицията може да се запише и в кондензирана форма като
А = Q1С₁Р^H₁,
където Q₁ и Р₁ са матриците, формирани от първите r стълба на Q и Р съответно.

За разлика от декомпозицията по сингулярни стойности, описана по-долу, QСР декомпозицията се получава с помощта на краен брой стъпки и лесно може да бъде актуализирана. Декомпозицията (7) също така позволява да се получат (поне теоретично) полярната декомпозиция и декомпозицията по сингулярни стойности.

За мен   За реклама   Дарения    Детска енциклопедия