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

  • 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, ,