У линеарној алгебри, Хаусхолдерова трансформација (такође позната као Хаусхолдерова рефлексија или елементарни рефлектор) јесте линеарна трансформација која описује рефлексију око равни или хиперравни која садржи координатни почетак. Хаусхолдерова трансформација је коришћена у раду из 1958. године чији је аутор Алстон Скот Хаусхолдер.
Дефиниција
Оператор и трансформација
Хаусхолдеров оператор се може дефинисати над било којим коначнодимензионалним простором унутрашњег производа са унутрашњим производом и јединичним вектором као
Такође је уобичајено одабрати вектор који није јединични , и нормализовати га директно у изразу Хаусхолдеровог оператора:
Такав оператор је линеаран и самоконјугован.
Ако је , треба приметити да рефлексиона хиперраван може бити дефинисана својим вектором нормале, јединичним вектором (вектор дужине ) који је ортогоналан на хиперраван. Рефлексија тачке око ове хиперравни јесте Хаусхолдерова трансформација:
где је вектор од координатног почетка до тачке , а је конјуговано транспонован вектор вектора .
мини|400px|Хаусхолдерова трансформација која делује као рефлексија тачке око хиперравни дефинисане вектором .
Хаусхолдерова матрица
Матрица конструисана из ове трансформације може се изразити преко спољашњег производа као:
и позната је као Хаусхолдерова матрица, где је јединична матрица.
Својства
Хаусхолдерова матрица има следећа својства: она је ермитска матрица: , она је унитарна матрица: (према Шерман—Морисоновој формули), стога је она и инволутивна матрица: . Хаусхолдерова матрица има сопствене вредности . Да би се ово увидело, треба приметити да ако је ортогонално на вектор који је коришћен за стварање рефлектора, тада је , тј., је сопствена вредност вишеструкости , јер постоји независних вектора ортогоналних на . Такође, треба приметити да је (пошто је по дефиницији јединични вектор), па је тако сопствена вредност вишеструкости . Детерминанта Хаусхолдеровог рефлектора је , пошто је детерминанта матрице производ њених сопствених вредности, при чему је у овом случају једна од њих , док су остале (као у претходној тачки), што се такође може показати преко леме о детерминанти матрице.
Пример
Размотримо нормализацију вектора који садржи на свакој позицији,
Тада је Хаусхолдерова матрица која одговара вектору
Треба приметити да ако имамо још један вектор који представља координату у 2Д равни
онда у овом случају обрће и негира и координате, другим речима имамо
што одговара рефлексији вектора преко праве , на коју је наш почетни вектор нормалан.
Примене
Геометријска оптика
У геометријској оптици, регуларна рефлексија се може изразити преко Хаусхолдерове матрице (погледати ).
Нумеричка линеарна алгебра
Треба приметити да представљање Хаусхолдерове матрице захтева само елементе једног вектора, а не целе матрице (која се у већини алгоритама никада експлицитно не формира), чиме се минимизује потребан простор за складиштење и приступ меморији који су потребни за њихово коришћење.
Надаље, множење Хаусхолдерове матрице вектором не укључује пуно множење матрице и вектора, већ само један скаларни производ вектора, а затим једну axpy операцију. То значи да је њена аритметичка сложеност истог реда као две операције ниског нивоа BLAS-1. Због тога су Хаусхолдерове матрице изузетно аритметички ефикасне.
Коначно, користећи да означимо израчунату вредност и да означимо математички тачну вредност, тада за дату Хаусхолдерову матрицу важи:
Где је (при чему је јединична грешка заокруживања, величина матрице , а нека мала константа). Другим речима, множења Хаусхолдеровим матрицама су такође изузетно уназад стабилна.
Пошто Хаусхолдерове трансформације минимизују меморијски простор, приступ меморији и аритметичку сложеност, а оптимизују нумеричку стабилност, оне се широко користе у нумеричкој линеарној алгебри, на пример, за поништавање елемената испод главне дијагонале матрице, за извођење QR декомпозиција и у првом кораку QR алгоритма. Такође се широко користе за трансформацију у Хесенбергову форму. За симетричне или ермитске матрице, симетрија се може сачувати, што резултира тридијагонализацијом.
QR декомпозиција
Хаусхолдерове трансформације се могу користити за израчунавање QR декомпозиције. Размотримо матрицу која је триангуларизована до колоне ; тада је наш циљ да конструишемо такве Хаусхолдерове матрице које делују на главне подматрице дате матрице
преко матрице
.
(треба приметити да смо већ раније установили да су Хаусхолдерове трансформације унитарне матрице, а пошто је множење унитарних матрица такође унитарна матрица, ово нам даје унитарну матрицу QR декомпозиције)
Ако можемо пронаћи тако да
могли бисмо ово да постигнемо. Геометријски посматрано, тражимо раван такву да рефлексија око ове равни пада тачно на базни вектор. Другим речима,
за неку константу . Међутим, да би се ово десило, морамо имати
А пошто је јединични вектор, то значи да морамо имати
Сада, ако применимо једначину () назад у једначину (), добијамо
Или, другим речима, упоређивањем скалара испред вектора морамо имати
Или
Што значи да можемо изразити као
Ово комплетира конструкцију; међутим, у пракси желимо да избегнемо катастрофално поништавање у једначини (). Да бисмо то урадили, бирамо знак за као
Тридијагонализација (Хесенберг)
Ова процедура је представљена у књизи „Нумеричка анализа” чији су аутори Берден и Ферс, и функционише када је матрица симетрична. У несиметричном случају, и даље је корисна јер слична процедура може резултирати Хесенберговом матрицом.
Користи се благо измењена функција са . У првом кораку, да бисмо формирали Хаусхолдерову матрицу у сваком кораку потребно је да одредимо и , који су:
Из и , конструишемо вектор :
где је , , и за свако
Затим рачунамо:
Након што пронађемо и израчунамо , процес се понавља за на следећи начин:
Настављајући на овај начин, формира се тридијагонална и симетрична матрица.
Примери
У овом примеру, такође из књиге Бердена и Ферса, дата матрица се трансформише у сличну тридијагоналну матрицу A3 коришћењем Хаусхолдерове методе.
Пратећи те кораке у Хаусхолдеровој методи, имамо:
Прва Хаусхолдерова матрица:
Коришћењем за формирање
Као што можемо видети, коначни резултат је тридијагонална симетрична матрица која је слична почетној. Процес је завршен након два корака.
Квантно рачунарство
мини|310px|Слика која приказује геометријску интерпретацију прве итерације Гроверовог алгоритма. Вектор стања је ротиран према циљном вектору као што је приказано.
Пошто су унитарне матрице корисне у квантном рачунарству, а Хаусхолдерове трансформације су унитарне, оне су веома корисне у квантном рачунарству. Један од главних алгоритама где су корисне јесте Гроверов алгоритам, где покушавамо да пронађемо решење за репрезентацију пророчке функције која је представљена оним што се испоставља као Хаусхолдерова трансформација:
(овде је део бра-кет нотације и аналогно је које смо користили претходно)
Ово се ради преко алгоритма који итерира преко пророчке функције и још једног оператора познатог као Гроверов дифузиони оператор који је дефинисан као
и .
Рачунарски и теоријски однос са другим унитарним трансформацијама
Хаусхолдерова трансформација је рефлексија око хиперравни са јединичним вектором нормале , као што је раније наведено. -са- унитарна трансформација задовољава . Узимање детерминанте (-ти степен геометријске средине) и трага (пропорционално аритметичкој средини) унитарне матрице открива да њене сопствене вредности имају јединични модуо. Ово се може директно и брзо видети:
Пошто су аритметичка и геометријска средина једнаке ако су променљиве константне (погледати неједнакост аритметичке и геометријске средине), установљавамо тврдњу о јединичном модулу.
За случај реалних унитарних матрица добијамо ортогоналне матрице, . Доста лако следи (погледати ортогонална матрица) да се свака ортогонална матрица може разложити у производ 2-са-2 ротација, названих Гивенсове ротације, и Хаусхолдерових рефлексија. Ово је интуитивно привлачно јер множење вектора ортогоналном матрицом чува дужину тог вектора, а ротације и рефлексије исцрпљују скуп (реалних) геометријских операција које чине дужину вектора инваријантном.
Показано је да Хаусхолдерова трансформација има однос један-на-један са канонском декомпозицијом косета унитарних матрица дефинисаном у теорији група, која се може користити за параметризацију унитарних оператора на веома ефикасан начин.
Коначно, напомињемо да једна Хаусхолдерова трансформација, за разлику од појединачне Гивенсове трансформације, може деловати на све колоне матрице, и као таква показује најнижу рачунарску цену за QR декомпозицију и тридијагонализацију. Казна за ову „рачунарску оптималност” је, наравно, то што се Хаусхолдерове операције не могу тако дубоко нити ефикасно паралелизовати. Због тога се Хаусхолдерова метода преферира за густе матрице на секвенцијалним машинама, док се Гивенсова преферира за ретке матрице и/или паралелне машине.
Види још Блок рефлектор Гивенсова ротација Јакобијева ротација
Референце
Литература
(Овде је Хаусхолдерова трансформација цитирана као један од 10 најбољих алгоритама овог века)
Категорија:Трансформација (функција) Категорија:Матрице Категорија:Нумеричка линеарна алгебра