Reducerea la Forma Hessenberg

Reducerea la forma Hessenberg.

Aducerea unei matrice ARnxn date la forma Schur reală prin transformări (ortogonale) de asemănare este un proces infinit.

Pentru orice ARnxn există o matrice ortogonală URnxn, calculabilă printr-un număr finit de operaţii astfel încât matricea H=UHAU este superior Hessenberg (adică H(i,j)=0 pentru toţi i>j+1).

Matricea U se alege ca un produs de reflectori elementari Householder U=U2U3…Un-1

Reducerea la forma Hessenberg.

1. Pentru k=1:n-2

1. Se determină reflectorul Uk+1 asfel încât

(Uk+1A)(k+2:n,k)=0

2. AUk+1A

3. A AUk+1.

Reflectorul elementar Uk+1 care anulează elementele k+2:n din coloana k a matricei A are forma

Uk+1=diag(Ik,Uk+1)

unde Uk+1 este un reflector de ordinul n-k şi indice 1 . În consecinţă, la primul pas (k=1) premultiplicarea matricei A cu U2 anulează elementele A(3:n,1), iar postmultiplicarea cu U2=U2T, nu afectează prima coloană a matricei U2A, respectiv conservă zerourile create.

Reducerea la forma Hessenberg.

Presupunem că după k-1 paşi matricea

AUk…U2AU2…Uk

este superior Hessenberg în primele k-1 coloane. Premultiplicarea cu reflectorul Uk+1 nu modifică primele k linii şi primele k-1 coloane (conservând astfel zerourile obţinute în paşii precedenţi) şi anulează elementele A(k+2:n,k).

Postmultiplicarea cu Uk+1 nu modifică primele k coloane conservând zerourile create la paşii precedenţi şi cele create prin premultiplicarea de la pasul curent.

Procesul de reducere la forma Hessenberg prin transformări Householder de asemănare se realizează în n-2 paşi.

Reducerea la forma Hessenberg.

În final se obţine matricea

AH=Un-1…U3U2AU2U3…Un-1

în formă superior Hessenberg.

Elementele definitorii vkRn, k=1/2.||vk||2 ale reflectorilor elementari

pot fi memorate în matricea VRnx(n-2) (vk este coloana k-1 a matricei V) şi vectorul bRn-2 (k=bk-1,k=2:n-2).

Dat fiind un vector nenul xRn, elementele definitorii vkRn, k, ale reflectorului care asigură anularea componentelor k+1:n ale lui x, i.e. (Ukx)(k+1:n)=0, se calculează economic cu relaţiile: