×   HOME JAVA NETPLOT OCTAVE Traži ...
  matematika2
QR rastav matrice     QR rastav     Rješavanje problema najmanjih kvadrata


Numeričko računanje QR rastava

Za formiranje Householderove matrice $ H$ potrebno je $ O(n^2)$ računskih operacija. Za množenje nekog vektora $ x$ Householderovom matricom također je potrebno $ O(n^2)$ računskih operacija. No, umnožak $ H\mathbf{x}$ može se izračunati bez formiranja matrice $ H$ :

$\displaystyle H\mathbf{x}=\left(I-2\frac{\mathbf{v}\mathbf{v}^T}{\mathbf{v}^T\m...
...mathbf{x}-\mathbf{v} \frac{2(\mathbf{v}^T\mathbf{x})}{\mathbf{v}^T\mathbf{v}}.
$

Za računanje produkta $ H\mathbf{x}$ pomoću prethodne jednakosti potrebno je samo $ O(6n)$ računskih operacija. Slično, produkt $ HA$ u praksi se računa pomoću formula:

$\displaystyle \beta$ $\displaystyle =-\frac{2}{\mathbf{v}^T\mathbf{v}},$    
$\displaystyle \mathbf{w}$ $\displaystyle = \beta A^T \mathbf{v}$ (6.5)
$\displaystyle HA$ $\displaystyle = A+\mathbf{v} \mathbf{w}^T.$    

Koristeći prethodna poboljšanja možemo napisati funkcije za računanje QR rastava. Prva funkcija računa vektor $ \mathbf{v}$ iz zadanog vektora $ \mathbf{x}$ prema formuli (6.4) i napomeni 6.3:

   function v=House(x)
      % računa Householderov vektor v iz vektora x
      sig=sign(x(1)); if sig==0, sig=1; end
      v=x
      v(1)=v(1)+sig*norm(v)
   end
Slijedeća funkcija računa umnožak $ HA$ bez formiranja matrice $ H$ prema formulama (6.5):
   function B=mnoziHouse(v,A)
      % računa produkt HA=(I-2*v*v'/(v'*v))*A
      % bez formiranja matrice H
      beta=-2/(v'*v)
      w=beta*A'*v
      B=A+v*w'
   end
Konačno, sljedeća funkcija računa QR rastav matrice $ A$ prema postupku opisanom u prethodnom poglavlju:
   function [Q,R]=mojQR(A)
      % QR rastav A=Q*R. A je m x n i mora biti rank(A)=n.
      [m,n]=size(A)
      Q=eye(m)
      for i=1:min(m-1,n)
         v=House(A(i:m,i))
         A(i:m,i:n)=mnoziHouse(v, A(i:m,i:n))
         Q(i:m,:)=mnoziHouse(v, Q(i:m,:))
      end
      R=A
      Q=Q'
   end

Zadatak 6.5   Izračunajte QR rastav matrice $ A$ iz primjera 6.2 pomoću prethodnih funkcija i usporedite ga s rastavom koji se dobije pomoću Matlabove naredbe [Q,R]=qr(A).



Octave On-line

     


[Octave On-line Home]    [Octave User's Guide]


QR rastav matrice     QR rastav     Rješavanje problema najmanjih kvadrata