Способы хранения и представления разреженных матриц, операции над ними: Методические указания к спецкурсу

  • Published on
    08-Dec-2016

  • View
    219

  • Download
    4

Embed Size (px)

Transcript

  • ,

    3

    :

    .. . .

    ..

    2002

  • - 2 -

    1. .. 3 2. . ... 3 3. ... . 9 4. . 24 . 33

  • - 3 -

    1. ,

    , . 1.1. ( ) ,

    . 1.2. ,

    , , . . :

    1) ;

    2) ( ); 3) .

    () fAU = ( A ), .. . A , :

    1) ; 2) .

    2.

    , , , .

    2.1. ( ) .

    mn { }ijaA = . : 1) AN A ; 2) JA - A; 3) IA , i - , c AN JA i - A . , AN JA .

  • - 4 -

    , i - A )(iAI ]1)1([ +iAI AN JA

    I )()1( iAIiAI =+ , , i - . , . A m , AI )1( +m .

    , .. A . , JA ( ), . : , , , . . . 1. A .

    N : 7654321

    =

    0000000063000000005040002011

    A .

    N : 87654321

    6354211:AN 6531421:JA 88641:AI

    . AI 1 .

    2. IAJAAN ,, A ( ). 9854321:AN 5432176:JA 86531:AI

  • - 5 -

    JAAN , : N : 7654321

    9854321:AN 5432176:JA

    , A 4 7 , 1- 6 1, 7- 2 ..

    N : 7654321

    3. 1 ,

    .

    2.2. ( ) , , .

    . , JAT , ATI , A .

    4. A 1

    . a) N : 87654321 ANT : 6325141 JAT : 3312121 ATI : 8765431

    5. A 1

    , 5. 6. A .

    =

    001070000000000000000050003100

    A .

    =

    0098000000050000000432100000

    A

  • - 6 -

    2.3. { }n

    jiijaA

    1, == )( jiij aa =

    ( ) . : 1) ( )

    ( ); 2) A AD ,

    ( ) A ( ) ( ).

    7.

    =

    3011030010101002

    A

    a) ; ) .

    a) :NA 331112 ) :AN 11 :JA 434241 :JA 44 :AI 76531 :IA 33321 :AD 3312

    2.4. ( ) 2.1. { }n

    jiijaA

    1, ==

    )12( +m , 0=ija ji, , mji > || . )12( +m , m .

    nm

  • - 7 -

    , , . :

    , , . 8. A 1) m ; 2) AD ; 3) .

    a)

    =

    70000000690000

    121151000000104090000038000068200000001

    A ; )

    =

    5020003000200010002000101

    A .

    ) 1) 2=m ; ) 1) 2=m ; 2) )57( AD ; 2) )35( AD ;

    3)

    =

    7000690

    12115100010409003806820001

    AD ; 3)

    =

    502300001201

    AD .

    9. - A AD .

  • - 8 -

    2.5. ( ) ,

    , . .

    )(min ijii = , i , )(min ij i - A , . . i - i .

    2.2. { }njiij

    aA1, =

    =

    i : =

    ==n

    iiAprofileApr

    1)()( .

    2.3. A { }iij jia i i -

    ]1)1([ +iDA )(iDA . 11a )1(AN .

    10.

    =

    20200018010

    1700130

    10

    A

    1) , AN ; 2) .

    N : 87654321 2021801171310:AN 86321:DA

  • - 9 -

    11. AN DA A : 123456789:AN 976531:DA 3. . , .. . , ( ). . 1. , , , , . . IA , JA ; , . 2. . , . 3.1. 3.1.1. , , 3.1. (), . , . , , . : 1) N ; 2) A ; 3) NEXT , IP . 12. dcba ,,, , A : 7654321:N cadbA : : 427:NEXT ; 5=IP . 13. fedcba ,,,,, , : 654321:N

    .853dim,3)(,1,2,0,0,0)1 54321

    =+==

    =====

    ANApr

  • - 10 -

    fedcbaA : 12356:NEXT 4=IP : afbecd ,,,,, .

    3.2. , . A , { }n,...,2,1 . 3.3. n . m . nm

  • - 11 -

    B , ),...,1( niAi = ( ).

    16. B ,, , .2,7:;5,11,3:;5,3,7,2: B

    , B , , , B . , .11,5,3,7,2:

    , , . Y p . 1=p .

    ( 11). Y . , i , i - ( 1). ( j ) j M , , . . . .

    : N : 1110987654321 :Y 00000000000 00001010110 A 10001010110 B 10001010110 C

    3.1.3. ( ) .

    ( ), ( , ).

    , . ( ) p .

    1=p . p ( . . 1+= pp ), .

  • - 12 -

    17. B ,, 1 ED, 2 , p .

    N : 13121110987654321 :Y 11121121122 0000000000000 22

    3.2. ( ) 3.2.1. ( ) B, ,

    BC += .

    1. : JBJ, J .

    2. 01 . X ,

    J . X JC . 02 . J AN

    X AN . - BN X .

    03 . X , CN , ))(()(: iJCXiCNJ = .

    18. B, .

    1. JBJ, J : 547310 . 2. X :

    N : 10987654321 X : 00000

    2.04.07.03.0 AN 5.06.07.0 BN

    7.04.06.003.0 6.004.03.07.0:CN

    4,8,7:;11,5,4:

    13,12,11:

    CBA

    =

    =

    ).2(2,1,9,8,7,6:4,8,7:);1(8,7,5,4,13,12,11:9,8,7,6:

    2

    1

    pEpMD

    .1045:

    5.07.06.0:

    JBBN

    ;47310:7.04.03.02.0:

    JAAN

  • - 13 -

    . , CN , . C :

    57310:6.04.03.07.0:

    JCCN

    .

    3.2.2. ( ) B, ,

    BC += . CN .

    1. : JBJ, J . 2.

    01 . ( ) IX , J . J , )( jIX , CN j - , . . )( j . IX - .

    02 . CN . ANJ, CN , IX CN , . BNJB, CN : )()))((()))((( iANiJAIXCNiJAIXCN += ; )()))((()))((( iBNiJBIXCNiJBIXCN += .

    19. B, .

    ;43710:14.08.06.04.0:

    JAAN

    .1359:4.03.02.01.0:

    JBBN

    1. N : 7654321 N - J :JC 15943710 N N 2. 1) N : 10987654321 N JC (CN ) :IX 0000000000

    1526437 2) N : 7654321

    CN : 14.08.06.04.0 AN 4.02.01.03.0 BN

    ______________

    4.02.01.014.01.16.04.0 N , 4.02.01.014.01.16.04.0: CN

  • - 14 -

    15943710:JC

    3.3. )(, mnB

    . BC += . Y

    X . A B : mXY == dimdim .

    A B .

    1. ( ICJC, )

    01 . 1=i ( ). 02 . JAIA, JBIB, ,

    i - A B Y . , , 1- JC .

    03 . 1+= ii 02 . , ni . JC .

    04 . IC JC .

    2. ( B, )

    01 . 1=i . 02 . ICJC, ,

    i - JA JB . 03 . X i - A

    B , . CN JC .

    04 . 1+= ii 02 . , ni . CN . . X . 20. B, . BC += .

    ;9731:

    4261543153:1112733412:

    IAJAAN

  • - 15 -

    1512951:432215631:

    211642511:

    IAJBBN

    .

    1. 34226154316153:JC 1512951:IC

    N : 654321 :Y

    324432 11422131000000

    2. N : 654321 X : 0000 1

    12 AN 511 BN 5111

    000000 2 7334 AN 2 BN

    5334 000000 3

    12 AN 64 BN

    162

    000000 4 11 AN 211 BN

    310

    13061253345111: AN 3.4. B, n . P B . IX , , .3.2.2, ,

  • - 16 -

    , J . , . IX J . k JB , ki ,...,1= ))(( iJBIX . , JB ; ,

    )))((()( iJBIXANIBNPP += JB . , : 1) 0=P ; 2) ki ,...,1= 0))(( =IJBIX JA 1+= ii )))((()( iJBIXANIBNPP JA+= 1+= ii

    21.

    N : 87654321 :JAIX 32000154 0=P , 8,...,1=i :1=i 0))1(( =JBIX JA 2=i : 01))2(( =JBIX JA 717)1()2(0 ==+= ANBNP :3=i 05))3(( =JBIX JA 47587)5()3(7 =+=+= ANBNP :4=i 4))4(( =JBIX JA 834947 =+=P

    . . . . . . . . . . . . . . . . . . . . . . . .

    3.5. ( ) B , ABC = . , , B .3.4 .

    ;21873:54321:

    JAAN

    .861234:

    11109876:

    JBBN

  • - 17 -

    1. IX ( ) B.

    2. 1=i . 3. IA , JA

    i - . 4. JA , i - .

    )(kJA ( k - ) , ; , AN B )(iC .

    5. , 1+= ii 3. , . . 1=k 0)( =k )()1( kIAkIA =+

    1)1(),( += kAIkAIi 1+= kk 0))(( =IJAIX 1+= ii )))((()()()( iJAIXBNIANkCkC JA+= 1+= ii 1+= kk 22. ( ).

    N : 121110987654321

    N : 10987654321 :JBIX 7065043021

    10875421:10875421:

    JBBN

    131211941:3110987523641:6210864297531:

    IAJAAN

  • - 18 -

    1=k ; 0)1( = ; )1()2( AIAI = :3,...,1=i :1=i 01)1())1(( == IXJAIX

    ...

Recommended

View more >