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