ku1 (1108607), страница 3
Текст из файла (страница 3)
-//*&)'(* *-)'(0. D = A;1 C = A;1(A+B ) = I +A;1 B .-2 2-2 7& ./$&4(L kA;1B k kA;1 k kB k < 1 , )& 7& 7'+,<,.C+8 )+&1'+*+ /.C+/)4.+) *-)'(0- D;1 = P (;1)k (A;1B )k , &='-)1-@ 2 D . -//*&k=0)'(* *-)'(0. C^ = D;1A;1 ( 4<3(/$(* C^ C = D;1A;1 (A + B ) = D;1(I +A;1B ) = D;1D = I C C^ = (A + B )D;1A;1 = A A;1(A + B )D;1A;1 =A(I + A;1 B1)D;1A;1 = A A;1 = I . $+,&4-)+$:1&, /.C+/)4.+) C ;1 = C^ =D;1A;1 = P (;1)k (A;1 B )k A;1 .k=0x3. 9./): '+K-+)/@ $(1+81-@ /(/)+*- A x = b A 2 Mn b 2 Cn .
9./): Y- -$-%&'()* '+K+1(@ ;)&8 /(/)+*< 1- (,+-$:1&8 4<3(/$()+$:1&8 /(/)+*+, )-2, 3)&x = Y(A b) { )&31&+ '+K+1(+ /(/)+*< ( 7&)&*. x = Y(A b) { &)&='-A+1(+ 12$-//+ 1+4<'&A,+11<6 *-)'(0 ( x = A;1 b ). 9./): ^Y - )&) A+ -$%&'()*, '+-$(>&4-11<8 1- '+-$:1&8 4<3(/$()+$:1&8 /(/)+*+. '+>.$:)-)+ +%& 7'&4+,+1(@7&$.3+1& 7'(=$(A+11&+ '+K+1(+ x^ = ^Y (A b) . 7'+,+$(* *-)'(0. A^ ( 4+2)&'^b (> ./$&4(@ x^ = Y(A^ ^b) ( ^b = A^;1 x^ ), ).+. x^ @4$@+)/@ )&31<* '+K+1(+* /(/)+*<.. !!x3. . / .01 *,%1 #13A^x^ = ^b .
=&>1-3(* A^ = A + E ^b = b + e . -2(* &='->&*, )&31&+ '+K+1(+x .,&4$+)4&'@+) /(/)+*+ A x = b , - 7'(=$(A+11&+ '+K+1(+ x^ .,&4$+)4&'@+)/(/)+*+ (A + E )^x = b + e .9./): kk - 7'&(>4&$:1-@ *-)'(31-@ 1&'*-, /&%$-/&4-11-@ / 4+2)&'1&8 1&'*&8 k k . .,+* /3()-):, 3)& &K(=2-, 41&/(*-@ 4 *-)'(0.
7'( 7'&4+,+1((-$%&'()*-, 1+ &3+1: 4+$(2-: kE k < kA1;1k . 9& )+&'+*+ 2.2 &)/L,- /$+,.+),13)& *-)'(0- A + E &='-)(*- ( (A + E );1 = P (;1)k (A;1 E )k A;1 . <3(/$(*k=07&%'+K1&/): x ; x^ :x ; x^ = A;1b ; (A + E );1 (b + e) = (A;1 ; (A + E );1)b ; (A + E );1e11= ; P (;1)k (A;1E )k A;1b ; P (;1)k (A;1E )k A;1ek=1k=011PP= ; (;1)k (A;1E )k x ; (;1)k (A;1 E )k A;1 e:k=1k=0$+,&4-)+$:1&,kx ; x^k (kP=1 kA;1 E kk )kxk + (kP=0 kA;1E kk )kA;1 ekkx ; x^k kA;1 E k +1kA;1ek :kxk1 ; kA;1E k 1 ; kA;1 E k kxk-2 2-2 A x = b , )& kbk = kA xk kAk kxk ( 1 kAk .
9&;)&*.kxk kbk1kx ; x^k kA;1k kE k +;1 k kek kAkkA;1;1kxk1 ; kA k kE k 1 ; kA k kE kkbk;1k kE kkAkkAkx ; x^k 1kAk +;1k kekkAkkAkxkkbk1 ; kAk kA;1k kE k 1 ; kAk kA;1k kE kkAkkAk115%$". & *-)'(0< A 7& &)1&K+1(L 2 *-)'(31&8 1&'*+ k k 1-><4-+)/@(;1(A) = k1Ak kA k+/$( A 1+4<'&A,+1-+/$( A 4<'&A,+1-: (/7&$:>&4-1(+* ;)&%& &=&>1-3+1(@ 7&/$+,1++ 1+'-4+1/)4& *&A1& 7+'+7(/-): 4 4(,+!kE k + kek :kx ; x^k (A)kxk1 ; (A) kE k kAk kbkkAk..
!!x3. . / .01 *,%1 #14k,+/: kxk;xkx^k 1-><4-+)/@ '( ( x , kkEAkkek1-><4-+)/@ '( A , kbk 1-><4-+)/@ '( b .-/)&, 3)&=< &0+1(): )&31&/): 7&$.3+11&%& 7'(=$(A+11&%& '+K+1(@ x^ , 4<3(/$@L) ) r = b ; A x^ . 0+1(* &)1&/()+$:1.L 7&%'+K1&/): '+K+1(@ 3+'+> 1+4@>2. r .x ; x^ = A;1 b ; x^ = A;1(b ; A x^) = A;1rkx ; x^k = kA;1rk 1 kA;1k krk kAk kA;1 k krk = (A) krk :kxkkxkkxkkbkkbk.%%.
-//*&)'(* $(1+81.L /(/)+*.! !1;1A x = 1 ;1 + " x = b = 11 : !+ )&31&+ '+K+1(+ x = 10 : -//*&)'(* 7'(=$(A+11&+ '+K+1(+ x^ =!!0 , 4+2)&' &K(=2( x ; x^ =1 + ";1=2 . &%,- 4+2)&' 1+4@>2( r =;1=2;"1=2 ";1=2 !;";";1=2 . 9&;)&*.-) &)1&/()+$:1-@ 4+$(3(1- 1+4@>2( kkrbkk = O("1=2) ! 0 (" ! 0)S=) &)1&/()+$:1-@ 4+$(3(1- &K(=2( kxk;xkx^k = O(";1=2) ! 1 (" ! 0)S&& " <!"&"1. (A) 1 .2. (A) = (A;1 ) .3. (AB ) (A)(B ) .9+'4<+ )'( /4&8/)4- /$+,.L) 1+7&/'+,/)4+11& (> &7'+,+$+1(@ 3(/$- &=./$&4$+11&/)( ( &/1&41<6 /4&8/)4 *-)'(31<6 1&'*.max (A) 4.
/$( A = A , )& 7& &)1&K+1(L 2 /7+2)'-$:1&8 1&'*+ (A) = (A) ,min%,+ max(A) ( min(A) /&&)4+)/)4+11& *-2/(*-$:1&+ ( *(1(*-$:1&+ 7& *&,.$L/&=/)4+11<+ >1-3+1(@ *-)'(0< A .6"#&. /($. >-*+3-1(@ 1.1 (/*. $+**. 1.4) ,$@ /-*&/&7'@A+11<6 *-)'(0 kAk2 = (A) = jmax(A )j , kA;1k2 = (A;1 ) = jmax(A;1 )j =jmin(A)j . 9&;)&*. (A) = kAk kA;1k = max((AA)) .min.. !!x4. # 34155. $@ 4/@2&8 *-)'(0< A 2 Mn 3(/$& &=./$&4$+11&/)( &)1&/()+$:1& $L=&8*-)'(31&8 1&'*< (A) max((AA)) .min6"#& 4<)+2-+) (> $+**< 1.4: kAk (A) = jmax (A)j , k A;1k (A;1 ) = jmax(A;1)j = jmin(A)j S 7&;)&*.
(A) = kAk kA;1k max((AA)) .min6. $@ 4/@2&8 *-)'(0< A 2 Mn ( $L=<6 .1()-'1<6 (&')&%&1-$:1<6) *-)'(0U V 2 Mn 3(/$& &=./$&4$+11&/)( &)1&/()+$:1& /7+2)'-$:1&8 1&'*< (A) =(UAV ).F)& /4&8/)4& 1+7&/'+,/)4+11& /$+,.+) (> $+**< 1.5.7. $@ 4/@2&8 1+4<'&A,+11&8 *-)'(0< A 2 MnkAk(A) supkA ; B kB 2 Mn B ; 4<'&A,+11-@6"#&.
9&2-A+*, 3)& ,$@ 4/@2&8 4<'&A,+11&8 *-)'(0< B 2 Mn/7'-4+,$(4& 1+'-4+1/)4& kA ; B k 1=kA;1k . 9'+,7&$&A(*, 3)& ;)& 1+ )-2,).+. /.C+/)4.+) 4<'&A,+11-@ *-)'(0- B , )-2-@, 3)& ,$@ *-)'(0< C = A ; B4<7&$1+1& kC k < 1=kA;1k . &%,- 7& )+&'+*+ 2.2 *-)'(0- A;C = A;(A;B ) = B&='-)(*-, 3)& 7'&)(4&'+3() 4<'&A,+11&/)( B .
-2(* &='->&*, ./)-1&4$+1&,3)& ,$@ 4/@2&8 4<'&A,+11&8 *-)'(0< B kA;1k 1=kA ; B k . $+,&4-)+$:1&,(A) = kAk kA;1k kAk=kA ; B k ,$@ 4/@2&8 4<'&A,+11&8 B 2 Mn . 9&/2&$:2.$+4-@ 3-/): ;)&%& 1+'-4+1/)4- 1+ >-4(/() &) B , )& (> 1+%& 4<)+2-+) )'+=.+*&+/&&)1&K+1(+.x4. ! "x 4.1.
"*% $ !9./): )'+=.+)/@ '+K(): $(1+81.L /(/)+*. A x = b A 2 Mn :a11 x1 + a12 x2 + : : : + a1nxn = b1a21 x1 + a22 x2 + : : : + a2nxn = b2(1)............ . . . ......... ...an1x1 + an2 x2 + : : : + annxn = bn+)&, !-.//- /&/)&() 4 )&*, 3)& ;$+*+1)-'1<*( 7'+&='->&4-1(@*( 1-, /)'&2-*(*-)'(0< &1- 7'(4&,()/@ 2 )'+.%&$:1&*. 4(,. / %$-41&8 ,(-%&1-$:L, /&/)&@C+8(> +,(1(31<6 ;$+*+1)&4 (7'@*&8 6&, *+)&,- !-.//-)S 7&$.3+11-@ /(/)+*- / )'+.%&$:1&8 *-)'(0+8 '+K-+)/@ 4 @41&* 4(,+ (&='-)1<8 6&, *+)&,- !-.//-).9'+,7&$&A(*, 3)& a11 6= 0. 9&,+$(4 7+'4&+ .'-41+1(+ /(/)+*< (1) 1- a11 ,7+'+7(K+* +%& 4 4(,+x1 + c12x2 + : : : + c1nxn = y1(2)..
!!x4. # 3416%,+ c1j = a1j =a11 j = 2 : : : n y1 = b1 =a11 . "*1&A(* .'-41+1(+ (2) 1- ai1 (4<3)+* +%& (> i -%& .'-41+1(@ /(/)+*< (1) ( i = 2 : : : n ). '+>.$:)-)+ /(/)+*- (1)7'(*+) 4(,x1 + c12 x2 + : : : + c1nxn = y1(1)(1)a(1)22 x2 + : : : + a2n xn = b2(3)...... . . . ......... ...(1)(1)a(1)n2 x2 + : : : + ann xn = bn(1)%,+ a(1)ij = aij ; c1j ai1 bi = bi ; y1 ai1 i j = 2 : : : n . -$++ ;)&) 7'&0+//7'(*+1@+)/@ 2 7&,*-)'(0+ A(1) = (a(1)ij )ij =2:::n 2 Mn;1 .9./): /,+$-1< k ; 1 k = 1 : : : n K-%&4 ;)&%& 7'&0+//-, ).+. /(/)+*- (1)7'+&='->&4-1- 2 4(,.x1 + c12 x2 + : : :x2 + : : :...+ c1k;1xk;1 + c1k xk + : : : + c1nxn = y1+ c2k;1xk;1 + c2k xk + : : : + c2nxn = y2...............
. . . ......... ...xk;1 + ck;1k xk + : : : + ck;1nxn = yk;1k;1) x = b(k;1)a(kkk;1) xk + : : : + a(knnk...... . . . ......... ...k;1) x + : : : + a(k;1) x = b(k;1)a(nkknn nn(4)9'+,7&$&A(*, 3)& a(kkk;1) 6= 0. 9&,+$(4 k -+ .'-41+1(+ /(/)+*< (4) 1- a(kkk;1) ,7+'+7(K+* +%& 4 4(,+xk + ckk+1xk+1 + : : : + cknxn = yk (5)%,+(k;1)a(kjk;1)bckj = (k;1) j = k + 1 : : : n yk = k(k;1) :(6)akkakk"*1&A(* .'-41+1(+ (5) 1- a(ikk;1) ( 4<3)+* +%& (> i -%& .'-41+1(@ /(/)+*< (4)( i = k + 1 : : : n ). '+>.$:)-)+ /(/)+*- (4) 7'(*+) 4(,x1 + c12 x2 + : : :x2 + : : :.....+ c1k;1xk;1 + c1k xk + c1k+1xk+1 + : : : + c1n xn = y1+ c2k;1xk;1 + c2k xk + c2k+1xk+1 + : : : + c2n xn = y2......... ...
......... . . . ... ... ... ...xk;1 + ck;1k xk + ck;1k+1xk+1 + : : : + ck;1nxn = yk;1xk + ckk+1xk+1 + : : : + cknxn = yka(kk+1) k+1xk+1 + : : : + a(kk+1) nxn = b(kk+1)... . . . ... ... ... ......k) x(k )(k )a(nk+1 k+1 + : : : + ann xn = bn(7) !!x4. # 3417%,+a(ijk) = a(ijk;1) ; a(ikk;1) ckj b(ik) = b(ik;1) ; a(ikk;1) yk i j = k + 1 : : : n: (8)<'-A+1(@ (6), (8) @4$@L)/@ 5&'*.$-*( 7+'+6&,- &) /(/)+*< (4) 2 /(/)+*+ (7).(0)/$( &=&>1-3(): a(0)ij = aij bi = bi i j = 1 : : : n , )& 7+'+6&, &) /(/)+*< (1) 2/(/)+*+ (3) =.,+) &/.C+/)4$@):/@ 7& )+* A+ 5&'*.$-* 7'( k = 1.9&/$+ 7'&4+,+1(@ 4<3(/$+1(8 7& 5&'*.$-* (6), (8) 7'( k = 1 : : : n (2&)&'<+/&/)-4$@L) * +) /(/)+*- (1) 7'(*+) 4(,x1 + c12 x2 + : : : + c1nxn;1 + c1n xn = y1x2 + : : : + c2nxn;1 + c2n xn = y2............
.... . . ...(9)xn;1 + cn;1nxn = yn;1xn = yn+K+1(+ /(/)+*< (9) / )'+.%&$:1&8 *-)'(0+8 *&A+) =<): 1-8,+1& 1+7&/'+,/)4+11& (*+)&,&* 7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6 4 7&'@,2+xn xn;1 : : : x1 ):nXxn = yn xi = yi ;cij xj i = n ; 1 : : : 1:(10)j =i+1<3(/$+1(@ 7& 5&'*.$-* (10) /&/)-4$@L) * +.x 4.2. ? "& % 5%? & $ !,+/: ( ,-$++ 7'( &0+12+ 2&$(3+/)4- -'(5*+)(3+/2(6 &7+'-0(8 *< =.,+*&),+$:1& 1-6&,(): 2&$(3+/)4& -,,()(41<6 &7+'-0(8 (/$&A+1(8 ( 4<3()-1(8) (2&$(3+/)4& *.$:)(7$(2-)(41<6 &7+'-0(8 (.*1&A+1(8 ( ,+$+1(8).
$@ .7'&C+1(@ 4<2$-,&2 *< =.,+* 1-6&,(): )&$:2& %$-41<8 3$+1 -/(*7)&)(2( 2&$(3+/)4&7+'-0(8 7'( n ! 1 .1. - 4<3(/$+1(+ckjP7'( j = k + 1 : : : n k = 1 : : : n 7& 5&'*.$-* (6)Pn;1 i = n(n ; 1)=2 = O(n2 ) (n ! 1) &7+'-0(8 ,+$+1(@.)'+=.+)/@ k=1(n ; k) = ni=0(k)2. - 4<3(/$+1(+ aij 7'( i j = k + 1 : : : n k = 1 : : : n 7& 5&'*.$-* (8);1 i2 = (n ; 1)n(2n ; 1)=6 = n3 =3 + O(n2 ) (n ! 1))'+=.+)/@ Pnk=1(n ; k)2 = Pni=0&7+'-0(8 .*1&A+1(@ ( /)&$:2& A+ &7+'-0(8 4<3()-1(@.)-2, 1- 4<3(/$+1(+ 2&;55(0(+1)&4 ckj j = k + 1 : : : n k = 1 : : : n/(/)+*< (9) )'+=.+)/@ O(n2) + n3 =3 + O(n2) = n3 =3 + O(n2) (n ! 1) *.$:)(7$(2-)(41<6 &7+'-0(8 ( /)&$:2& A+ -,,()(41<6 &7+'-0(8.3.
- 4<3(/$+1(+ yk 7'( k = 1 : : : n 7& 5&'*.$-* (6) )'+=.+)/@ n &7+'-0(8,+$+1(@.4. -P4<3(/$+1(+ Pb(ik) 7'( i = k + 1 : : : n k = 1 : : : n 7& 5&'*.$-* (8) )'+;1 i = n(n ; 1)=2 = O(n2 ) (n ! 1) &7+'-0(8 .*1&A+1(@=.+)/@ nk=1(n ; k) = ni=0( /)&$:2& A+ &7+'-0(8 4<3()-1(@... !!x4. # 3418)-2, 1- 4<3(/$+1(+ 7'-4<6 3-/)+8 yk k = 1 : : : n /(/)+*< (9) )'+=.+)/@ O(n2) (n ! 1) *.$:)(7$(2-)(41<6 &7+'-0(8 ( /)&$:2& A+ -,,()(41<6&7+'-0(8.-2(* &='->&*, 7'@*&8 6&, *+)&,- !-.//- )'+=.+) n3=3 + O(n2) + O(n2) =n3 =3 + O(n2) (n ! 1) *.$:)(7$(2-)(41<6 &7+'-0(8 ( /)&$:2& A+ -,,()(41<6&7+'-0(8.5. - 4<3(/$+1(+ '+K+1(@P7& 5&'*.$-*P(10) ().+.
1- 7'&4+,+1(+ &='-)1&%&;1 (n;i) = n;1 i = n(n;1)=2 = O(n2 ) (n ! 1)6&,- *+)&,- !-.//-) )'+=.+)/@ ni=1i=1&7+'-0(8 .*1&A+1(@ ( /)&$:2& A+ &7+'-0(8 4<3()-1(@.$+,&4-)+$:1&, *+)&, !-.//- )'+=.+) n3 =3+O(n2)+O(n2) = n3 =3+O(n2) (n !1) *.$:)(7$(2-)(41<6 &7+'-0(8 ( /)&$:2& A+ -,,()(41<6 &7+'-0(8. /+%&:(2=3) n3 + O(n2) (n ! 1) -'(5*+)(3+/2(6 &7+'-0(8.x 4.3. .%$&" $ ! & &$ 5"$&"#@"%' 5%<%6&9'+&='->&4-1(+ /(/)+*<, >-,-4-+*&+ 5&'*.$-*( (6), ;24(4-$+1)1& .*1&A+1(L *-)'(0< /(/)+*< /$+4- 1- *-)'(0.;1Dk = diag T |1 :{z: : 1} a(kkk;1) 1 : : : 1 ]k;1(%,+ diag T d1 : : : dn ] &>1-3-+) ,(-%&1-$:1.L *-)'(0. / ;$+*+1)-*( d1 : : : dn 1%$-41&8 ,(-%&1-$().9'+&='->&4-1(+ /(/)+*<, >-,-4-+*&+ 5&'*.$-*( (8), ;24(4-$+1)1& .*1&A+1(L *-)'(0< /(/)+*< /$+4- 1- *-)'(0.011BB .
.CC.BBCCBBCC1Lk = BCC(k;1)BB;ak+1k 1BBCC...... C@A;a(nkk;1)1(1+ &=&>1-3+11<+ ;$+*+1)< *-)'(0< Lk '-41< 1.$L).$+,&4-)+$:1&, 7'@*&8 6&, *+)&,- !-.//- ;24(4-$+1)+1 .*1&A+1(L *-)'(0</(/)+*< (1) 7&/$+,&4-)+$:1& 1- *-)'(0< Lk Dk k = 1 : : : n :Ln Dn : : : L1 D1 Ax = LnDn : : : L1D1 b:(11)7'(3+* *-)'(0- U = LnDn : : : L1 D1 A +/): *-)'(0- /(/)+*< (9), ).+. @4$@+)/@ 4+'61+8 )'+.%&$:1&8 / +,(1(0-*( 1- %$-41&8 ,(-%&1-$(. =&>1-3(* 3+'+>LT (n) %'.77.