复旦大学：《Matlab》（ppt实验英文版）Chapter 7 The QR and Cholesky Factorizations

Introduction to scientific Computing A Matrix Vector Approach Using Matlab Written by Charles FVan Loan 陈文斌 Wbchen(fudan. edu. cn 复日大学

Introduction to Scientific Computing -- A Matrix Vector Approach Using Matlab Written by Charles F.Van Loan 陈 文 斌 Wbchen@fudan.edu.cn 复旦大学

Chapter 7 The qr and cholesky Factorizations Least Squares Fitting The qr factorization The cholesky factorization High-Performance Cholesky

Chapter 7 The QR and Cholesky Factorizations • Least Squares Fitting • The QR factorization • The Cholesky Factorization • High-Performance Cholesky

Least Squares Fitting 0 overdetermined 34‖x1 56 Given A∈R""andb∈R",fndx∈Rnto minimize Ax-61

Least Squares Fitting             =           1 1 0 5 6 3 4 1 2 1 2 x x 2 minimize Given and , find to Ax b A R b R x R m n m n −     overdetermined

Setting Up Least Squares Problems x∈[25,】 ,(1)=∑(a+k)-x n、(a,B) B

Setting Up Least Squares Problems f (x) = x, x[.25,1]   = = + − m i m i i x x 1 2  (, ) (  ) 2 2 2 1 2 1 1 1 1 ( , )             −                  = m m m f f f x x x        

Matlabs Least Squares Tools XLSAb m=2,apha=0.33333,bea=0.666667 m=100,apha=0.369810,bea=0.652299 0 0.5 0.6

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 m = 100, alpha = 0.369810, beta = 0.652299 Matlab’s Least Squares Tools xLs=A\b; 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 m = 2, alpha = 0.333333, beta = 0.666667

∑a+)=√]-2a+)==a Minimizer ao 0 aa 3 15 1521尸 31 3264 80 0.37037037 0.651851851 polyfit t If we try to fit data point in the least squares sense with a polynomial of degree d, the m-by-(d+1) least squares problems arises

( )  ( )  ( , ) .75 1 1 .2 5 2         =  + −  + −   x x x x dx m m i i i 0, = 0   =        Minimizer             =                80 31 12 7 64 21 32 15 32 15 4 3 * *          =      0.651851851 0.37037037 * *   polyfit If we try to fit data point in the least squares sense with a polynomial of degree d, the m-by-(d+1) least squares problems arises

Matlabs Least Squares Tools Ax-b x∈Rn is equivalent to a transformed problem min x∈R Q4k-(b)2 2Q=00=l, orthogonal cos(6) sin( 0) 2 sin (o)cos(0) The column of an orthogonal matrix define an orthonormal basis

Matlab’s Least Squares Tools min 2 Ax b n x R −  is equivalent to a transformed problem ( ) ( ) 2 min Q A x Q b T T x R n −  QQ Q Q I orthogonal T T = = , 2 2 2 2 Q r r T =       − = sin( ) cos( ) cos( ) sin( )     Q The column of an orthogonal matrix define an orthonormal basis

min Ax-bll= min oa x∈R2 I2x-(o bl ∈R 22 x mn X∈R2‖00 4 12 22C min Ax-b ls b Ca O x∈R2 2 2

( ) ( ) 2 4 3 2 1 2 2 2 1 1 1 1 2 2 2 0 0 0 0 0 min min min 2 2 2              −                  = − = −    c c c c x r x r r Ax b Q A x Q b x R T T x R x R        =            2 1 2 1 22 11 12 0 c c x x r r r 2 4 2 min 2 Ax b 2 AxLs b 2 c3 c x R − = − = + 

A=OR QR factorization problem To find an orthonormal basis for the subspace defined by the columns of a A(2j)=Q(21)*R(,j+Q(2)*R(2,j)+…+Q(;j)*R(, Any column of a is in the span of (Q( 1).Q( n)) 8 1/3-2/3-2/3‖36 2/3-1/32/3015 214 2/32/3 l/3‖00

A = QR QR factorization problem To find an orthonormal basis for the subspace defined by the columns of A A(:, j) = Q(:,1)*R(1, j) + Q(:,2)*R(2, j) ++ Q(:, j)*R( j, j) Any column of A is in the span of {Q(:,1),…,Q(:,n)}                     − − − − =           − − 0 0 0 15 3 6 2 / 3 2 / 3 1/ 3 2 / 3 1/ 3 2 / 3 1/ 3 2 / 3 2 / 3 2 14 2 1 1 8

Rotations The Q in the qr factorization can be computed using a special family of orthogonal matrices that are called rotations G C=coS(O), S=sin( 0) c=x1/√x2+x2,s=x2/√x2+x2 Gx

Rotations The Q in the QR factorization can be computed using a special family of orthogonal matrices that are called rotations. , = cos( ), = sin( )       − = c s s c c s G 2 2 2 2 1 2 2 2 1 1 c = x / x + x ,s = x / x + x y = Gx, y2 = 0