. , , ,

,,,

:

 

2002

............................................................................................................................................................................. 3

1. .................................................................................................. 7

1.1. ......................................................................................................... 7

1.2. ................................................................................................... 9

1.3. .......................................................................... 10

1.4. ................................................................................................... 11

1.5. QR........................................................................................................................................ 15

1.6. ....................................................................................................................... 20

2. .......................................................................... 25

2.1. .................................................................................................................................................. 25

2.2. ....................................................................................................................... 27

2.3. .................................................................................................. 29

3. ⠠ 33

................................................................................................................................................................... 38

..................................................................................................................................................................... 39

1. ............................................................................... 40

2. ..................................................................................................... 45

. , . : , ..

, .

m´n A k£min(m,n) m b. n x0, Axb.

y n , x n , b y n j:

.

, b, e=yXb, X , n , xj: xj. , . . :

. . .

, =0

.

, , . . , , ( ) , . .

. (. 1): y=0 x=0; y=1 x=1; y=2 x=3; y=5 x=4. , , . , . :

Xb=y. XTX :

b=(XTX)-1XTy

, ( ) , . , . , , . t. , , , . D, , :

. (1)

, ,

. 1. .

(1). , (1) :

, m>2, C D . .

, C D l m. , . , l m, .

1.

1.1.

|| Ax-b ||.

1. m´n k,

A=HRKT (2)

H m´m ; R m´n

, (3)

: R11 kxk k; K kxk.

(4)

. (5)

R11y1=g1. :

1.       ||Ax-b|| , y2 .

2.       . (6)

3.       r

4.      

. A HRKT (2) HT ( )

(7)

(3) (5) ,

.

(4)

(7)

R11y1=g1, , R11 . y , y2 .

,

(3). , y2=0. , . .

(2) . , , ||Ax-b|| . .

. : , .

1.2.

. 2 , . 2´2 , :

(8)

. :

.

.

1.3.

. : , (9)

, v , .. , . H . :

.

: , .. . [1] [2]. , m, H , ,

s = +1, = 1, .

. .

, :

1.4.

X Nxp, N>p, r X. r=p, , r<p.

,

(10)

V Nxr, , .. ; U pxr; , ; rxr, , X, . , V, U, X, (10), :

(11)

.

        XX' NxN, r Nr . XX' , . , XX', V .

        X'X pxp, r pr . X'X , , , X'X, U .

X'X XX' . , um X'X, vm XX', , um vm

(12)

, , . :

. (13)

X'X R-, XX' Q. (12)(13) , Q R .

.

1.   X'X XX', , . , X'X.

2.   X'X .

3.   .

4.   (11).

(11) . (11) , . .

1. S, pxp r . , pxp, k, k<r, S .

2. X, Nxp r k<r. W pxp k, X .

:

(14)

k . T W S X . : T S , ST . W X , XW. , .. rk XX.

(15)

.

p=r.

S p . T p , T k<p, p k . , p , S, k .

X Nxp X=VU, V Nxp c ; pxp, U pxp.

W

k V, k , k U. WX,

(16)

(17)

pxk X p k ; (16) , X Nxp Nxk. X N p , k . k .

1.5. QR

2. m´n. m´m Q , QA=R .

. m´m Q (9), , Q1A 2 m. (m-1)´(m1) P2 . m1 , 2 m Q1A, 3 m .

, Q2Q1A . , , n , . .

QR.

3. m´n , k<n£m. m´m Q m´n P ,

, (18)

R ´ .

. , AP, . 2, m´m Q , QAP . , QAP.

QAP, +1,...,m +1,...,n, . rankQAP>k, rankA=k. , QAP , (4). .

[R:T] (18) , R 2. .

1. [R:T] ´, R . n´n W ,

.

3, n, k, [R:T], W m, n, AT, QT 3.

3 1 .

4. m´n . m´m n´n ,

(19)

R11 ´.

, (19) , R11 .

(19) A=HRKT, R , . , R . ATA AAT (. 11).

5. m´n k. m´m U, n´n V m´n S ,

UTAV=S, A=USVT (20)

S , ; .

S . m=n=rankA.

2. n´n n. n´n U, n´n V n´n S , UTAV=S, A=USVT S .

. ATA

ATA=VDVT, (21)

V n´n, D , D . S n´n, D.

D=STS=S2, S-1DS-1=I. (22)

U=AVS-1 (23)

(21), (22), (23) V ,

UTU=S-1VTATAVS-1=S-1DS-1=I .. U . (23) V USVT=AVS-1SVT=AVVT=A .

5. A=HRKT, H, R, KT , 4. R11 (19) ´, 2 ,

(24)

´, , . (24) , R (19)

(25)

:

m´m;

n´n;

m´n;

, U V

(26)

(24) (26), A=USVT, U, S, V , 5. .

, , , U, V . s , l. , I ,

k=min(m,n), Q ´

l´l A=USVT si==si+l-1, , .

1.6.

. .

:

: (x-2)2=10-6

2+10-3 2-10-3. 10-6 , 10-3.

, , . . , . , . , . .

. .

x , , :

1)     

2)      ;

3)      .

, , 1 3 :

1)      ;

2)     

3)     

4)     

:

        頠

       

       

:

       

       

       

[3] ; ( [4], ( [5]) ³ 0). : .

, .

. , , m=0. M/m ,

(7)

[6] .

, , . . , 1/ , . , . (7) . .

Ax=b, , : A(x+Dx)=b+Db . Db b, Dx x, . A(Dx)=Db, M m , m¹0,

, , . . , .

. , M³m cond()³1. [7], Px . , cond(P)=1 . cond(I)=1. , cond(c)= cond(). D ,

2.

2.1.

QR - , : , , :

QR . n3. , [8] . ( ) , . , , [9]. n2, n.

Qs , Ls . QL.

, , As , , . , , p, p.

, As s- , kij . QL . , As As-ksI (QL ). :

. , , . ks ( ), . , , n-1- . , QL , , ks.

, , s ; , Qs s .

2.2.

, . , :

J0 , : Si Ti .

Ti , . Si , Ji . (10) . ,

.

, , Ji+1 , Ji. , ; ; .., , .

. , , Mi+1 , , Mi. , QR , s.

QR :

. , . s ( 2´2) Mi. s .

2.3.

,

, .

A2 . :

, . :

:

,

A2 v1 A1. , , .

, A3=A2Q1, . , , ; , . n2 .

A2:

A3 i

.

, A2 .

, A2 A3, Q1 , A3 A2.

, :

2, . 0.000, , . , , :

, . , , . H3 , . H3 1.080 A4.

, . . n n H n2 Q, . m, m , .

3.

(SVD Singular Value Decomposition) . y=Xb y=USVTb. , b UTy=SVTb. .. sj, j=1,,n, S ,

, .

, sj . SVD t . sj, , t, , (1.20). sj, , t, , . , . , , t, , . , , =0, sj £t.

sj, , t, . , .

:

t Y
1900 75994575
1910 91972266
1920 105710620
1930 123203000
1940 131669275
1950 150697361
1960 179323175
1970 203211926

Y X =1980.

, . . . , , , Y=227780000 , Y=145210000. , . . 8 ´ 3

. 2.

: .

, 1, t t2 . , .

, , . , . :

. , , , , , . Y(1980) 212910000 214960000. , .

, . : . t 1900 1970 0.0017, a , , 0.0017a. .

, .

. , [1900, 1970] [0, 70] , , [3.5, 3.5]. 5750 10.7 . .

, .. 1. , , 0, .

, , , , .

, , . 2 , . , .

. FORTRAN. , .

, .

1.       . . -.: , 1969, 368.

2.       .. . -.: , 1988, 548.

3.       . . -.: , 1982, 387.

4.       ., . . .: , 1979, 447

5.       .. . .: , 1980

6.       . . .: , 1988, 350

7.       . . .: , 1980, 454

8.       ., . . , .: , 1976, 390

9.       .., .. . -.: , 1963, 536.

10.    ., ., . . .: , 1980, 279

11.    .. . .: - , 1995, 76 .

1.

REAL A(3,3), U(3,3), V(3,3), SIGMA(3), WORK(3),Y(3),C(3),Y0(3)

INTEGER I,IERR, J, M, N, NM

OPEN (6,FILE="SVD.OUT",STATUS="UNKNOWN",FORM="FORMATTED")

OPEN (5,FILE= "SVD.IN",STATUS="UNKNOWN",FORM="FORMATTED")

140 FORMAT(3I5)

150 FORMAT(4E15.7)

READ(5,140) NM,M,N

DO 131 I=1,M

READ(5,150) (A(I,J),J=1,N)

131 CONTINUE

READ (5,150) (Y(I),I=1,M)

CALL SVD(NM,M,N,A,SIGMA,.TRUE.,U,.TRUE.,V,IERR,WORK)

IF(IERR.NE.0) WRITE (6,2) IERR

2 FORMAT(15H TROUBLE.IERR=,I4)

WRITE(6,120)

120 FORMAT(/' ')

DO 121 I=1,M

WRITE(6,130) (A(I,J),J=1,N)

130 FORMAT(8E15.7)

121 CONTINUE

WRITE (6,160) (Y(I),I=1,N)

160 FORMAT(/' '/8E15.7)

210 FORMAT(/' ')

WRITE(6,210)

DO 3 J=1,N

WRITE(6,6) SIGMA(J)

3 CONTINUE

SMA=SIGMA(1)

SMI=SIGMA(1)

DO 211 J=2,N

IF(SIGMA(J).GT.SMA) SMA=SIGMA(J)

IF(SIGMA(J).LT.SMI.AND.SIGMA(J).GT.0.) SMI=SIGMA(J)

211 CONTINUE

OBU=SMA/SMI

230 FORMAT(/' =',E15.7)

WRITE(6,230) OBU

SIGMA1=0.

DO 30 J=1,N

IF(SIGMA(J) .GT. SIGMA1) SIGMA1=SIGMA(J)

C(J)=0.

30 CONTINUE

TAU=SIGMA1*0.1E-6

DO 60 J=1,N

IF(SIGMA(J).LE.TAU) GO TO 60

S=0.

DO 40 I=1,N

S=S+U(I,J)*Y(I)

40 CONTINUE

S=S/SIGMA(J)

DO 50 I=1,N

C(I)=C(I) + S*V(I,J)

50 CONTINUE

60 CONTINUE

write (6,560)

WRITE (6,6) (C(I),I=1,3)

DO 322 J=1,N

SS=0.

DO 321 I=1,M

321 SS=A(J,I)*C(I)+SS

322 Y0(J)=SS

write (6,570)

WRITE (6,6) (Y0(I),I=1,3)

C WRITE(6,7)

C DO 4 I=1,M

C WRITE(6,6) (U(I,J),J=1,N)

C4 CONTINUE

C WRITE(6,7)

C DO 5 I=1,N

C WRITE(6,6) (V(I,J),J=1,N)

C5 CONTINUE

6 FORMAT(3E15.7)

560 format(2x,'roots')

570 format(2x,'right')

7 FORMAT(1H )

STOP

E N D

SUBROUTINE SVD(NM,M,N,A,W,MATU,U,MATV,V,IERR,RV1)

REAL A(NM,N),W(N),U(NM,N),V(NM,N),RV1(N)

LOGICAL MATU,MATV

IERR=0

DO 100 I=1,M

DO 100 J=1,N

U(I,J)=A(I,J)

100 CONTINUE

G=0.0

SCALE=0.0

ANORM=0.0

DO 300 I=1,N

L=I+1

RV1(I)=SCALE*G

G=0.0

S=0.0

SCALE=0.0

IF(I.GT.M) GO TO 210

DO 120 K=I,M

120 SCALE=SCALE+ABS(U(K,I))

IF(SCALE.EQ.0.0) GO TO 210

DO 130 K=I,M

U(K,I)=U(K,I)/SCALE

S=S+U(K,I)**2

130 CONTINUE

F=U(I,I)

G=-SIGN(SQRT(S),F)

H=F*G-S

U(I,I)=F-G

IF(I.EQ.N) GO TO 190

DO 150 J=L,N

S=0.0

DO 140 K=I,M

140 S=S+U(K,I)*U(K,J)

F=S/H

DO 150 K=I,M

U(K,J)=U(K,J)+F*U(K,I)

150 CONTINUE

190 DO 200 K=I,M

200 U(K,I)=SCALE*U(K,I)

210 W(I)=SCALE*G

G=0.0

S=0.0

SCALE=0.0

IF(I.GT.M.OR.I.EQ.N) GO TO 290

DO 220 K=L,N

220 SCALE=SCALE+ABS(U(I,K))

IF(SCALE.EQ.0.0) GO TO 290

DO 230 K=L,N

U(I,K)=U(I,K)/SCALE

S=S+U(I,K)**2

230 CONTINUE

F=U(I,L)

G=-SIGN(SQRT(S),F)

H=F*G-S

U(I,L)=F-G

DO 240 K=L,N

240 RV1(K)=U(I,K)/H

IF(I.EQ.M) GO TO 270

DO 260 J=L,M

S=0.0

DO 250 K=L,N

250 S=S+U(J,K)*U(I,K)

DO 260 K=L,N

U(J,K)=U(J,K)+S*RV1(K)

260 CONTINUE

270 DO 280 K=L,N

280 U(I,K)=SCALE*U(I,K)

290 ANORM=AMAX1(ANORM,ABS(W(I))+ABS(RV1(I)))

300 CONTINUE

IF(.NOT.MATV) GO TO 410

DO 400 II=1,N

I=N+1-II

IF(I.EQ.N) GO TO 390

IF(G.EQ.0.0) GO TO 360

DO 320 J=L,N

320 V(J,I)=(U(I,J)/U(I,L))/G

DO 350 J=L,N

S=0.0

DO 340 K=L,N

340 S=S+U(I,K)*V(K,J)

DO 350 K=L,N

V(K,J)=V(K,J)+S*V(K,I)

350 CONTINUE

360 DO 380 J=L,N

V(I,J)=0.0

V(J,I)=0.0

380 CONTINUE

390 V(I,I)=1.0

G=RV1(I)

L=I

400 CONTINUE

410 IF(.NOT.MATU) GO TO 510

MN=N

IF(M.LT.N) MN=M

DO 500 II=1,MN

I=MN+1-II

L=I+1

G=W(I)

IF(I.EQ.N) GO TO 430

DO 420 J=L,N

420 U(I,J)=0.0

430 IF(G.EQ.0.0) GO TO 475

IF(I.EQ.MN) GO TO 460

DO 450 J=L,N

S=0.0

DO 440 K=L,M

440 S=S+U(K,I)*U(K,J)

F=(S/U(I,I))/G

DO 450 K=I,M

U(K,J)=U(K,J)+F*U(K,I)

450 CONTINUE

460 DO 470 J=I,M

470 U(J,I)=U(J,I)/G

GO TO 490

475 DO 480 J=I,M

480 U(J,I)=0.0

490 U(I,I)=U(I,I)+1.0

500 CONTINUE

510 DO 700 KK=1,N

K1=N-KK

K=K1+1

ITS=0

520 DO 530 LL=1,K

L1=K-LL

L=L1+1

IF(ABS(RV1(L))+ANORM.EQ.ANORM) GO TO 565

IF(ABS(W(L1))+ANORM.EQ.ANORM) GO TO 540

530 CONTINUE

540 C=0.0

S=1.0

DO 560 I=L,K

F=S*RV1(I)

RV1(I)=C*RV1(I)

IF(ABS(F)+ANORM.EQ.ANORM) GO TO 565

G=W(I)

H=SQRT(F*F+G*G)

W(I)=H

C=G/H

S=-F/H

IF(.NOT.MATU) GO TO 560

DO 550 J=1,M

Y=U(J,L1)

Z=U(J,I)

U(J,L1)=Y*C+Z*S

U(J,I)=-Y*S+Z*C

550 CONTINUE

560 CONTINUE

565 Z=W(K)

IF(L.EQ.K) GO TO 650

IF(ITS.EQ.30) GO TO 1000

ITS=ITS+1

X=W(L)

Y=W(K1)

G=RV1(K1)

H=RV1(K)

F=((Y-Z)*(Y+Z)+(G-H)*(G+H))/(2.0*H*Y)

G=SQRT(F*F+1.0)

F=((X-Z)*(X+Z)+H*(Y/(F+SIGN(G,F))-H))/X

C=1.0

S=1.0

DO 600 I1=L,K1

I=I1+1

G=RV1(I)

Y=W(I)

H=S*G

G=C*G

Z=SQRT(F*F+H*H)

RV1(I1)=Z

C=F/Z

S=H/Z

F=X*C+G*S

G=-X*S+G*C

H=Y*S

Y=Y*C

IF(.NOT.MATV) GO TO 575

DO 570 J=1,N

X=V(J,I1)

Z=V(J,I)

V(J,I1)=X*C+Z*S

V(J,I)=-X*S+Z*C

570 CONTINUE

575 Z=SQRT(F*F+H*H)

W(I1)=Z

IF(Z.EQ.0.0) GO TO 580

C=F/Z

S=H/Z

580 F=C*G+S*Y

X=-S*G+C*Y

IF(.NOT.MATU) GO TO 600

DO 590 J=1,M

Y=U(J,I1)

Z=U(J,I)

U(J,I1)=Y*C+Z*S

U(J,I)=-Y*S+Z*C

590 CONTINUE

600 CONTINUE

RV1(L)=0.0

RV1(K)=F

W(K)=X

GO TO 520

650 IF(Z.GE.0.0) GO TO 700

W(K)=-Z

IF(.NOT.MATV) GO TO 700

DO 690 J=1,N

690 V(J,K)=-V(J,K)

700 CONTINUE

GO TO 1001

1000 IERR=K

1001 RETURN

E N D

2.

( )

3 3 3

.3200000E 02 .1400000E 02 .7400000E 02

-0.2400000E 02 -0.1000000E 02 -0.5700000E 02

-0.8000000E 01 -0.4000000E 01 -0.1700000E 02

-0.1400000E 02 0.1300000E 02 0.1000000E 01

.3200000E+02 .1400000E+02 .7400000E+02

-.2400000E+02 -.1000000E+02 -.5700000E+02

-.8000000E+01 -.4000000E+01 -.1700000E+02

-.1400000E+02 .1300000E+02 .1000000E+01

.1048255E+03

.7310871E-06

.1271749E+01

= .1433830E+09

.1215394E+01 .1821742E+01 -.1059419E+01

-.1400000E+02 .1300000E+02 .1000001E+01

, . .



[1] .

[2] , .

[3] m´n , U V , S . S (, i=1,...,k, k=min(m,n)) . . .

[4] , . P , .

[5] , . P , . mxn . , rankA=n.

[6] , .

[7] - , . .

[8] ( ) j<i1 ( ). .

[9] |i-j|>1. .

 

 

 

! , , , .
. , :