ku1 (К.Ю. Богачёв - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений), страница 5
Описание файла
Файл "ku1" внутри архива находится в папке "К.Ю. Богачёв - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений". PDF-файл из архива "К.Ю. Богачёв - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений", который расположен в категории "". Всё это находится в предмете "практика расчётов на пэвм" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
"*% LU -%6"7A $"A %$*"#' %?9./): )'+=.+)/@ )'+6,(-%&1-$:1.L *-)'(0. 4(,-0a cBB d11 a12 c2BB d a . . .23A=BBB... ... cn;2BBdn;2 an;1@dn;17'+,/)-4(): 4 4(,+ A = LU , %,+010l1BB 1 l2CCBB 1BCCB2 l3L=BBBCC U = BBB@... ...B@CAn;1 lncn;1an1CCCCCCCCCAu11 u2 .1 .... . un;11(1)1CCCCCC :A(2) ;)&* /$.3-+ 5&'*.$< (4.13) -$%&'()*- 7&/)'&+1(@ LU -'->$&A+1(@ *&%.)=<): 7&$.3+1< 7.)+* 1+7&/'+,/)4+11&%& 7+'+*1&A+1(@ *-)'(0 L ( U ( '+K+1(@ 7&$.3-LC(6/@ .'-41+1(8:l1 = a1 1 = d1...i = di...n;2 = dn;2n;1 = dn;1u1 = c1 =l1l2 = a2 ; 1u1...li+1 = ai+1 ; iui...ln;1 = an;1 ; n;2un;2ln = an ; n;1un;1u2 = c2=l2...ui+1 = ci+1=li+1...un;1 = cn;1=ln;1(3)9&/)'&+1(+ LU -'->$&A+1(@ 7& ;)(* 5&'*.$-* )'+=.+) n ; 1 -,,()(41<6 (2(n ; 1) *.$:)(7$(2-)(41<6 &7+'-0(8.+K+1(+ $(1+81&8 /(/)+*< A x = b *&A+) =<): &/.C+/)4$+1& /$+,.LC(*&='->&*:1.
1-3-$+ /)'&()/@ LU -'->$&A+1(+ *-)'(0< A 7& 5&'*.$-* (3), 1- ;)&)'+=.+)/@ n ; 1 -,,()(41<6 ( 2(n ; 1) *.$:)(7$(2-)(41<6 &7+'-0(8... !!x5. #% *0 *$%1 #(242. -)+* 1-6&,()/@ '+K+1(+ y $(1+81&8 /(/)+*< L y = b 7.)+* 7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6, 1-3(1-@ / 7+'4&%& .'-41+1(@:y1 = b1 =l1yi = (bi ; i;1 yi;1)=li i = 2 : : : n:(4)- ;)&* ;)-7+ )'+=.+)/@ 7'&(>4+/)( n ; 1 -,,()(41<6 ( 2(n ; 1) + 1 *.$:)(7$(2-)(41<6 &7+'-0(8.3. /2&*<8 4+2)&' x 1-6&,()/@ 2-2 '+K+1(+ $(1+81&8 /(/)+*< U x = y7.)+* 7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6, 1-3(1-@ / 7&/$+,1+%& .'-41+1(@:xn = yn xi = yi ; uixi+1 i = n ; 1 : : : 1:(5)- ;)&* ;)-7+ )'+=.+)/@ 7'&(>4+/)( n ; 1 -,,()(41<6 ( n ; 1 *.$:)(7$(2-)(41<6 &7+'-0(8.2$-,<4-@ &0+12( )'.,&+*2&/)( 1- 2-A,&* K-%+, 1-6&,(*, 3)& ,$@ &/.C+/)4$+1(@ -$%&'()*- )'+=.+)/@ 7'&(>4+/)( 3(n ; 1) -,,()(41<6 ( 5(n ; 1) + 1*.$:)(7$(2-)(41<6 &7+'-0(8.4 1.
2% & 5A D %? A , L U . -)'(0.4(,- (1) 4 7-*@)( F &=<31& 1+ 6'-1@). *+/)& ;)&%& >-7&*(1-L) 4+2)&'a = (a1 : : : an)t c = (c1 : : : cn;1)t d = (d1 : : : dn;1)t . 1-$&%(31&, 4*+/)& *-)'(0< L 6'-1@)/@ 4+2)&'- l = (l1 : : : ln)t = (1 : : : n;1)t , - 4*+/)& *-)'(0<U { 4+2)&' u = (u1 : : : un;1)t . -2 ( 4 &=<31&* -$%&'()*+ LU -'->$&A+1(@, *-)'(0< L ( U *&A1& 6'-1(): 1- *+/)+ *-)'(0< A : 4+2)&' l { 1- *+/)+ 4+2)&'a , 4+2)&' { 1- *+/)+ d , u { 1- *+/)+ c .4 2. /7&*&%-)+$:1<8 4+2)&' y 4 7'(4+,+11&* 4<K+ -$%&'()*+'+K+1(@ $(1+81&8 /(/)+*< *&A+) 6'-1()/@ 1- *+/)+ 4+2)&'- x .
F)& /$+,.+) (>5&'*.$ (4), (5), 2&)&'<+ *&A1& >-7(/-): 4 4(,+x1 = b1 =l1 xi = (bi ; i;1 xi;1 )=li i = 2 : : : n xi := xi ; uixi+1 i = n ; 1 : : : 1:x 5.3. $ 5%* $"A %$*"#' %?9./): )'+=.+)/@ )'+6,(-%&1-$:1.L *-)'(0. A 4(,- (1) 7'+,/)-4(): 4 4(,+A = LU , %,+0110l1vu11BB 1 lCCCCBB v2 u22BBCCCCB.v3 . . .L=BCC U = BBCC :BB 1 .l.3 . .B.C.un;1 A@. .@Avn1 ln.. !!x5. #% *0 *$%1 #(25 &)$(3(+ &) LU -'->$&A+1(@, ;)& 7'+,/)-4$+1(+ 1+ +,(1/)4+11&. 9+'+*1&A-@*-)'(0< L ( U , 1-6&,(* .'-41+1(@ ,$@ &7'+,+$+1(@ 2&;55(0(+1)&4 li vi ui :l1 v1= a1 l1u1 = c1vi;1 = di;1 ui;1 + livi = ai liui = ci i = 2 : : : n ; 1(6)vn;1 = dn;1 un;1 + lnvn = an:(/$& .'-41+1(8 4 ;)&8 /(/)+*+, '-41&+ 2 + 3(n ; 2) + 2 = 3n ; 2, 1- 1 *+1:K+3(/$- 1+(>4+/)1<6 li vi ui .
9+'+7(K+* (6) 4 4(,+v1 = d1 l1 v1= a1 l1 u1 = c1vi = di ui;1 + li vi = ai liui = ci i = 2 : : : n ; 1un;1 + lnvn = an:)/L,- 7&$.3-+* '-/3+)1<+ 5&'*.$<:v1 = d1 l1 = a1 =v1u1 = c1 =l1vi = di li = (ai ; ui;1)=vi ui = ci =li i = 2 : : : n ; 1(7)lnvn = an ; un;1:> 7&/$+,1+%& .'-41+1(@ 4 (7) *< *&A+* &7'+,+$(): )&$:2& 7'&(>4+,+1(+ lnvn .-5(2/('&4-4 &,(1 (> 7-'-*+)'&4 ln ($( vn , *< &7'+,+$(* 4)&'&8.
< =.,+* /3()-):, 3)& vn = 1 . ;)&* /$.3-+, 2&$(3+/)4& -'(5*+)(3+/2(6 &7+'-0(8,1+&=6&,(*&+ ,$@ &/.C+/)4$+1(@ '->$&A+1(@ 7& 5&'*.$-* (7) '-41& 2&$(3+/)4. -'(5*+)(3+/2(6 &7+'-0(8, 1+&=6&,(*&*. ,$@ &/.C+/)4$+1(@ '->$&A+1(@7& 5&'*.$-* (3).+K+1(+ $(1+81&8 /(/)+*< A x = b *&A+) =<): &/.C+/)4$+1& /$+,.LC(*&='->&*:1. 1-3-$+ /)'&()/@ LU -'->$&A+1(+ *-)'(0< A 7& 5&'*.$-* (7), 1- ;)&)'+=.+)/@ n ; 1 -,,()(41<6 ( 2(n ; 1) *.$:)(7$(2-)(41<6 &7+'-0(8.2.
-)+* 1-6&,()/@ '+K+1(+ y $(1+81&8 /(/)+*< L y = b 7.)+* 7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6, 1-3(1-@ / 7+'4&%& .'-41+1(@:y1 = b1 =l1 yi = (bi ; yi;1)=li i = 2 : : : n:(8)- ;)&* ;)-7+ )'+=.+)/@ 7'&(>4+/)( n ; 1 -,,()(41<6 ( (n ; 1) + 1 *.$:)(7$(2-)(41<6 &7+'-0(8.3. /2&*<8 4+2)&' x 1-6&,()/@ 2-2 '+K+1(+ $(1+81&8 /(/)+*< U x = y7.)+* 7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6, 1-3(1-@ / 7&/$+,1+%& .'-41+1(@:xn = yn=vn xi = (yi ; uixi+1 )=vi i = n ; 1 : : : 1:(9)- ;)&* ;)-7+ )'+=.+)/@ 7'&(>4+/)( n ; 1 -,,()(41<6 ( 2(n ; 1) *.$:)(7$(2-)(41<6 &7+'-0(8 (/ .3+)&* vn = 1).2$-,<4-@ &0+12( )'.,&+*2&/)( 1- 2-A,&* K-%+, 1-6&,(*, 3)& ,$@ &/.C+/)4$+1(@ -$%&'()*- )'+=.+)/@ 7'&(>4+/)( 3(n ; 1) -,,()(41<6 ( 5(n ; 1) + 1*.$:)(7$(2-)(41<6 &7+'-0(8...
!!x6. +$ 70 #(%264 3. 2% & 5A D %? A , L U &/.C+/)4$@+)/@ )-2, 2-2 &7(/-1& 4 -*+3-1(( 1. *+/)& *-)'(0< A >-7&*(1-L) 4+2)&'a = (a1 : : : an)t c = (c1 : : : cn;1)t d = (d1 : : : dn;1)t , 4*+/)& *-)'(0< L {4+2)&' l = (l1 : : : ln)t , - 4*+/)& *-)'(0< U { 4+2)&'- v = (v1 : : : vn)t u =(u1 : : : un;1)t .
1-$&%(31& -$%&'()*. LU -'->$&A+1(@, *-)'(0< L ( U *&A1&6'-1(): 1- *+/)+ *-)'(0< A : 4+2)&' l { 1- *+/)+ 4+2)&'- a , 4+2)&' v { 1*+/)+ d (7&/$+,1@@, 1+ &7'+,+$@+*-@ &,1&>1-31& 2&*7&1+1)- vn 4+2)&'- v 1+6'-1()/@S ++ *&A1& /3()-): '-41&8 1), u { 1- *+/)+ c .4 4. /7&*&%-)+$:1<8 4+2)&' y 4 7'(4+,+11&* 4<K+ -$%&'()*+'+K+1(@ $(1+81&8 /(/)+*< *&A+) 6'-1()/@ 1- *+/)+ 4+2)&'- x . F)& /$+,.+) (>5&'*.$ (8), (9), 2&)&'<+ *&A1& >-7(/-): 4 4(,+x1 = b1 =l1 xi = (bi ; xi;1 )=li i = 2 : : : n xi := (xi ; uixi+1 )=vi i = n ; 1 : : : 1:(>,+/: /3()-+)/@ vn = 1 .)x6.
! ' -//*&)'(* >-,-3. 1-6&A,+1(@ *-)'(0<, &='-)1&8 2 ,-11&8."! 5%6&"#* "*%. 9./): Y { 1+2&)&'<8 -$%&'()* '+K+1(@ $(1+81<6 /(/)+* 4(,- A x = b , )-2, 3)& x = Y(A b). &%,- j -8 /)&$=+0xj *-)'(0< A;1 '-4+1 xj = Y(A ej ), %,+ ej = (0| :{z: : 0} 1 0 : : : 0)t +/): j -8j ;1&') /)-1,-')1&%& =->(/-. /$( -$%&'()* Y )'+=.+) ,$@ /4&+%& 7'&4+,+1(@ d(n)-'(5*+)(3+/2(6 &7+'-0(8, )& ;)&) /7&/&= 1-6&A,+1(@ &='-)1&8 *-)'(0< 7&)'+=.+) n d(n) -'(5*+)(3+/2(6 &7+'-0(8. -7'(*+', +/$( Y { ;)& *+)&, !-.//-, )&7&)'+=.+)/@ 2=3 n4 + O(n3) -'(5*+)(3+/2(6 &7+'-0(8."! 5?"#* "*%. 1&%(+ -$%&'()*< '+K+1(@ $(1+81<6/(/)+* (4 3-/)1&/)(, 4/+ -$%&'()*<, '-//*-)'(4-+*<+ 1-*() &=$-,-L) /$+,.LC(* /4&8/)4&*: -$%&'()* (7& 2'-81+8 *+'+ +%& /-*-@ )'.,&+*2-@ / 4<3(/$()+$:1&8 )&32( >'+1(@ 3-/):) /&/)&() 4 7'&4+,+1(( 1-, /(/)+*&8 7'+&='->&4-1(8,2&)&'<+ 4<7&$1@L)/@ 1-, *-)'(0+8 /(/)+*< ( 7'-4&8 3-/):L 1+>-4(/(*&.
F)&/&=+11&/): 7&>4&$@+) 4*+/)& 7'-4&8 3-/)( { 4+2)&'- b { '-//*-)'(4-): 1-=&'7'-4<6 3-/)+8, ).+. *-)'(0. B . 9'+&='->&4-1(@ -$%&'()*- 4<7&$1@L)/@ 1-,*-)'(0+8 /(/)+*< ( 1-=&'&* 7'-4<6 3-/)+8. -2(* &='->&*, )-2&8 -$%&'()*'+K+1(@ /(/)+*< Ax = b *&A+) =<): 7'+&='->&4-1 4 -$%&'()* '+K+1(@ *-)'(31&%& .'-41+1(@ AX = B , %,+ X B { n n *-)'(0<. =<31& -$%&'()*'+K+1(@ /(/)+*< Ax = b )'+=.+) O(n3) -'(5*+)(3+/2(6 &7+'-0(8 ,$@ 7'&4+,+1(@ 7'+&='->&4-1(8 1-, *-)'(0+8 ( O(n2) -'(5*+)(3+/2(6 &7+'-0(8 ,$@7'&4+,+1(@ 7'+&='->&4-1(8 1-, 7'-4&8 3-/):L.
9&;)&*. -$%&'()* '+K+1(@ *-)'(31&8 /(/)+*< AX = B )'+=.+) O(n3) + n O(n2) = O(n3) -'(5*+)(3+/2(6&7+'-0(8... !!x7. # 34 /%# 3*/3 9*#275"#6& LU -%6"7A $"A <%BA %?'. 9./): ,$@*-)'(0< A 4&>*&A1& &/.C+/)4(): LU -'->$&A+1(+. +8/)4()+$:1&, +/$( A =LU , )& A;1 = U ;1 L;1 . -)'(0<, &='-)1<+ 2 L ( U , /)'&@)/@, 1-7'(*+', &7(/-11<* 4<K+ /7&/&=&*. 9&/2&$:2. /(/)+*< / *-)'(0-*( L ( U '+K-L)/@ *+)&,&*7&/$+,&4-)+$:1&%& (/2$L3+1(@ 1+(>4+/)1<6 >- /&&)4+)/)4+11& n(n ; 1) + n =n2 + O(n) ( n(n ; 1) = n2 + O(n) ,+8/)4(8 (/*.
5&'*.$< (4.10)), )& *-)'(0< U ;1( L;1 *&%.) =<): 4<3(/$+1< / >-)'-)&8 n3 + O(n2) -'(5*+)(3+/2(6 &7+'-0(8.$+,&4-)+$:1&, ,$@ 4<3(/$+1(@ &='-)1&8 *-)'(0< )'+=.+)/@: 2=3 n3 + O(n2)-'(5*+)(3+/2(6 &7+'-0(8 ,$@ 7&/)'&+1(@ LU -'->$&A+1(@, n3 + O(n2) -'(5*+)(3+/2(6 &7+'-0(8 ,$@ 4<3(/$+1(@ U ;1 ( L;1 , n3 + O(n2) -'(5*+)(3+/2(6&7+'-0(8 ,$@ 4<3(/$+1(@ A;1 = U ;1 L;1 S 4/+%&: 8=3 n3 + O(n2) -'(5*+)(3+/2(6&7+'-0(8.x7. ! " )+&'+*- 4.1 7&2-><4-+), 3)& *+)&, !-.//- 4 (>$&A+11&* 4<K+ 4(,+ 7'(*+1(*1+ 2& 4/+* 1+4<'&A,+11<* *-)'(0-*. -7'(*+', +/$( 4 /(/)+*+ (4.1) a11 =0, )& 1+$:>@ &/.C+/)4(): 7+'4<8 A+ K-% -$%&'()*-.
&,+'1(>('.+* -$%&'()*/$+,.LC(* &='->&*."'-41+1(@ 4 /(/)+*+ (4.1) '-41&7'-41<, *< *&A+* (6 >-1.*+'&4-): 4 7'&(>4&$:1&* 7&'@,2+. 9'(/4&(* 1&*+' 1 )&*. .'-41+1(L, 4 2&)&'&* 2&;55(0(+1)7'( x1 &)$(3+1 &) 0. /$( )-2&%& .'-41+1(@ 1+ 1-K$&/:, )& *-)'(0- A (*++)1.$+4&8 7+'4<8 /)&$=+0, ).+. 4<'&A,+1-. 9&/$+ ;)&8 7+'+1.*+'-0(( .'-41+1(8*< /,+$-+* 7+'4<8 K-% *+)&,- !-.//-, ).+.
7+'+8,+* &) /(/)+*< (4.1) 2 /(/)+*+ (4.3). -$++ 4 7&,*-)'(0+ A(1) = (a(1)ij )ij =2:::n 2 Mn;1 7'(/4&(* 1&*+' 2 )&*..'-41+1(L, 4 2&)&'&* 2&;55(0(+1) 7'( x2 &)$(3+1 &) 0, ( /,+$-+* /$+,.LC(8K-% *+)&,- !-.//-. -)+* ;)&) 7'&0+// 7'(*+1@+)/@ 2 7&,*-)'(0+ A(2) 2 Mn;2( )-2 ,-$++./$( .'-41+1(8, 4 2&)&'<6 2&;55(0(+1) 7'( x1 &)$(3+1 &) 0, 1+/2&$:2&, )& /4<3(/$()+$:1&8 )&32( >'+1(@ 1+ =+>'->$(31&, 2-2&+ (> ;)(6 .'-41+1(8 7&$.3()1&*+' 1. 9./): 7&%'+K1&/): 4 ;$+*+1)+ aij *-)'(0< A '-41- "ij , ).+. 4*+/)&)&31&8 *-)'(0< A '-//*-)'(4-+)/@ *-)'(0- A^ , ;$+*+1)< 2&)&'&8 /&,+'A-)4<3(/$()+$:1<+ 7&%'+K1&/)(: a^ij = aij + "ij .