Отчёт сохранён неверно! Пожалуйста, пересохраните отчёт согласно инструкции:

https://plagiarism-detector.com/smf_bb/index.php?topic=341.msg369#msg369

# Детектор Плагиата v. 2762 - Отчёт оригинальности: 20.01.2023 14:03:24

Проанализированный документ: Semenov (master thesis).pdf Лицензия: ВОЛОДИМИР МАТІЄВСЬКИЙ
Тип поиска: Поиск переписанного Язык: Uk
Тип проверки: Интернет
TEE и кодировка: PdfPig

Детальный анализ тела документа:
Диаграмма соотношения частей:
Граф распределения зон:
Источники плагиата: 32

2% 2117 1. https://dspace.sfa.org.ua/bitstream/123456789/483/4/4 Zaytsev_Розд. 2.pdf 1% 1129 2. https://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/ 0,8% 403 3. https://knowledge.allbest.ru/programming/3c0a65625a3ac68a5c53a88521316d37_0.html

0,8%
1166
4. https://dspace.hnpu.edu.ua/bitstreams/b719ca62-e751-457c-a326-43ac154b1e1e/download
0,6%
411
5. https://www.chegg.com/homework-help/questions-and-answers/proof-suppose-p-n-defined-p-n-k-1-n-1-k-k-1-1-1-n-1-n-base-case-p-1-true-sides-evaluate-1--q59435896
0,5%
386
6. https://poemanalysis.com/nursery-rhyme/1-2-3-4-5-once-i-caught-a-fish-alive/
0,4%
309
7. https://www.stumblingrobot.com/2015/07/06/find-a-formula-for-a-sum-of-1kk1/
0,3%
564
8. https://djvu.online/file/QBjLFvddnjopM
0,3%
352
9. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UilOYW_8TFGmQ
0,3%
367
10. https://web.kpi.kharkov.ua/apm/wp-content/uploads/sites/82/2023/09/Lektsiya-04.pdf
0,3%
425
11. https://dl.sumdu.edu.ua/coursebook/d85ee21b-b380-4a39-a120-bc4c62e50d1c/738693/file-assets/LEKTS_YA_2_pptx.pdf
0,2%
444
12. https://www.netspotapp.com/blog/ip-addresses/10-0-0-0-1.html
0,2%
197
13. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UeiMoW_8DBJlQ
0,2%
234
14. https://www.reddit.com/r/learnmath/comments/qqdqo2/how_is_kk1_k1/
0,2%
271
15. https://tk.znu.edu.ua/nmk/Lec_vm_2.pdf
0,1%
26
16. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UilP4y9-jpDlQ
0,1%
236
17. https://matryza.blogspot.com/2015/03/blog-post_34.html
0,1%
82
18. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kunOIWw8TdHlg
0,1%
14
19. https://vuzlit.com/895283/elementi_teoriyi_matrits_viznachniki
0,1%
61
20. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=80unOYW49zpJnw
0,1%
61
21. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9k6uOoC-9jBInA
0,1%
52
22. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kqkMo28-jHU
0,1%
10
23. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UiiP4y7-zZBmw
0,1%
116
24. https://routerhax.com/10.0.0.1/
0,1%
50
25. http://freetutor.com.ua/Math/Sets_and_subsets_Their_properties
0,1%
49
26. https://www.bbc.co.uk/teach/school-radio/articles/zdy6jhv
0,1%
49
27. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UulPoW-9TRCnQ
0%
82
28. https://zaxid.net/yak_variti_ris_pravilno_i_smachno_poradi_dlya_riznih_vidiv_skilki_variti_ris_n1602689
0%
79
29. https://uk.wikipedia.org/wiki/Матриця_(математика)
0%
26
30. https://ukrayinska.libretexts.org/Математика/Математична_логіка_та_докази/Докази_та_поняття_-_Основи_абстрактної_математики_(Morris_і_Morris)/03:_Набори/3.02:_Множини,_підмножини_та_предикати
0%
35
31. https://math.stackexchange.com/questions/293244/compute-sum-k-1n-frac-1-kk-1
0%
22
32. https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_0auPIO49TPW
Детали обработанных ресурсов: 165 - ОК / 6 - Ошибок

n\a 1. https://ukrayinska.libretexts.org/Доколеджна_освіта/Орфографія/02:_Приголосні_звуки_та_написання/2.05:_Приголосний_звук_[k]
curl: (3) bad range in URL position 457: https://ukrayinska.libretexts.org/%D0%94%D0%BE%D0%BA%D0%BE%D0%BB%D0%B5%D0%B4%D0%B6%D0%BD%D0%B0_%D0%BE%D1%81%D0%B2%D1%96%D1%82%D0%B0/%D0%9E%D1%80%D1%84%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D1%96%D1%8F/02:_%D0%9F%D1%80%D0%B8%D0%B3%D0%BE%D0%BB%D0%BE%D1%81%D0%BD%D1%96_%D0%B7%D0%B2%D1%83%D0%BA%D0%B8_%D1%82%D0%B0_%D0%BD%D0%B0%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%BD%D1%8F/2.05:_%D0%9F%D1%80%D0%B8%D0%B3%D0%BE%D0%BB%D0%BE%D1%81%D0%BD%D0%B8%D0%B9_%D0%B7%D0%B2%D1%83%D0%BA_[k]
n\a 2. https://elar.urfu.ru/bitstream/10995/34809/1/978-5-7996-1457-7.pdf
timeouted: curl: (28) Connection timeout after 5001 ms!
n\a 3. http://www.toe-mirea.ru/download/file2.pdf
timeouted: curl: (28) Connection timeout after 5003 ms!
n\a 4. https://rozrobki.at.ua/load/algebra/pidmnozhina_operaciji_nad_mnozhinami/1-1-0-810
timeouted: curl: (28) Connection timeout after 5002 ms!
404 5. https://www.gauthmath.com/solution/1806025073794053/1-5-1-3-2-3-
Код ошибки веб-сервера:404
403 6. https://zkan.com.ua/navchannja/jak-pravilno-v-pershomu-drugomu-tretomu-i-t-d.html
Код ошибки веб-сервера:403
2%
1,1
2117
7 (D): https://dspace.sfa.org.ua/bitstream/123456789/483/4/4 Zaytsev_Розд. 2.pdf
0,8%
1,8
1166
8 (D): https://dspace.hnpu.edu.ua/bitstreams/b719ca62-e751-457c-a326-43ac154b1e1e/download
1%
1,24
1129
9 (D): https://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/
0,3%
1,48
564
10 (D): https://djvu.online/file/QBjLFvddnjopM
0,2%
1,36
444
11 (D): https://www.netspotapp.com/blog/ip-addresses/10-0-0-0-1.html
0,3%
0,62
425
12 (D): https://dl.sumdu.edu.ua/coursebook/d85ee21b-b380-4a39-a120-bc4c62e50d1c/738693/file-assets/LEKTS_YA_2_pptx.pdf
0,6%
2,04
411
13 (D): https://www.chegg.com/homework-help/questions-and-answers/proof-suppose-p-n-defined-p-n-k-1-n-1-k-k-1-1-1-n-1-n-base-case-p-1-true-sides-evaluate-1--q59435896
0,8%
0,52
403
14 (D): https://knowledge.allbest.ru/programming/3c0a65625a3ac68a5c53a88521316d37_0.html
0,5%
2,9
386
15 (D): https://poemanalysis.com/nursery-rhyme/1-2-3-4-5-once-i-caught-a-fish-alive/
0,3%
0,55
367
16 (D): https://web.kpi.kharkov.ua/apm/wp-content/uploads/sites/82/2023/09/Lektsiya-04.pdf
0,3%
0,92
352
17 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UilOYW_8TFGmQ
0,4%
2,2
309
18 (D): https://www.stumblingrobot.com/2015/07/06/find-a-formula-for-a-sum-of-1kk1/
0,2%
0,66
271
19 (D): https://tk.znu.edu.ua/nmk/Lec_vm_2.pdf
0,1%
1,03
236
20 (D): https://matryza.blogspot.com/2015/03/blog-post_34.html
0,2%
1
234
21 (D): https://www.reddit.com/r/learnmath/comments/qqdqo2/how_is_kk1_k1/
0,2%
1,52
197
22 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UeiMoW_8DBJlQ
0,1%
0,74
116
23 (D): https://routerhax.com/10.0.0.1/
0%
1,33
82
24 (D): https://zaxid.net/yak_variti_ris_pravilno_i_smachno_poradi_dlya_riznih_vidiv_skilki_variti_ris_n1602689
0,1%
0,55
82
25 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kunOIWw8TdHlg
0%
0,7
79
26 (D): https://uk.wikipedia.org/wiki/Матриця_(математика)
0,1%
0,61
61
27 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9k6uOoC-9jBInA
0,1%
0,58
61
28 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=80unOYW49zpJnw
0,1%
0,55
52
29 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kqkMo28-jHU
0,1%
1,51
50
30 (D): http://freetutor.com.ua/Math/Sets_and_subsets_Their_properties
0,1%
0,86
49
31 (D): https://www.bbc.co.uk/teach/school-radio/articles/zdy6jhv
0,1%
0,77
49
32 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UulPoW-9TRCnQ
0%
0,87
35
33 (D): https://math.stackexchange.com/questions/293244/compute-sum-k-1n-frac-1-kk-1
0%
2,05
26
34 (D): https://ukrayinska.libretexts.org/Математика/Математична_логіка_та_докази/Докази_та_поняття_-_Основи_абстрактної_математики_(Morris_і_Morris)/03:_Набори/3.02:_Множини,_підмножини_та_предикати
0,1%
1,01
26
35 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UilP4y9-jpDlQ
0%
0,59
22
36 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_0auPIO49TPW
0,1%
0,91
14
37 (D): https://vuzlit.com/895283/elementi_teoriyi_matrits_viznachniki
0,1%
0,18
10
38 (C): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UiiP4y7-zZBmw
0%
0,58
0
39 (D): https://en.wikipedia.org/wiki/Dotted_I_(Cyrillic)
0%
1,42
0
40 (D): https://kampus.ai/biblioteka/reshenie-zadach/elektronika-elektrotehnika-radiotehnika/sxema-ris-11-sostavlennaia-iz-rezistivnyx-elementov-pitaetsia-ot-istocnika-postoiannogo-napriazeniia-istocnik-podkliucen-ko-vxodnym-121229/
0%
0,48
0
41 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=80ujOIew8zNJnQ
0%
0,66
0
42 (D): https://topuch.com/4-peredatochnie-mehanizmi-ris-shema-cepnoj-peredachi/index.html
0%
0,77
0
43 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=80akOIa79zfU
0%
0,63
0
44 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_kyuO4y8-ztInw
0%
0,7
0
45 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UyvOI258TdCmg
0%
1,13
0
46 (D): https://www.cleancss.com/router-default/10.0.0.1
0%
0,5
0
47 (D): https://scicenter.online/lineynaya-algebra-scicenter/sistema-liniynih-algebrajichnih-144470.html
0%
0,75
0
48 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9EulP4249DRImA
0%
0,46
0
49 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8EqhP4K99jtHkQ
0%
0,5
0
50 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_0ilP4W79jFBlQ
0%
0,57
0
51 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kukOYO69jZJlA
0%
2,41
0
52 (D): https://www.xfinity.com/support/articles/wifi-change-admin-tool
0%
0,54
0
53 (D): https://en.wikipedia.org/wiki/One,_Two,_Three,_Four,_Five
0%
1,2
0
54 (D): https://allnurseryrhymes.com/one-two-three-four-five/
0%
0,53
0
55 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8EyjPYe_8zBFnA
0%
4,91
0
56 (D): https://www.ukrainianlessons.com/ukrainian-conjunctions/
0%
0,58
0
57 (D): https://osvita.ukr-lit.com/cherguvannya-i-j/
0%
1,75
0
58 (D): https://litmisto.org.ua/?p=12551
0%
1,58
0
59 (D): https://ukrainian.stackexchange.com/questions/7158/заміна-букви-і-на-ї
0%
1,11
0
60 (D): https://math.stackexchange.com/questions/1390516/sequence-of-1-2-2-3-3-3-4-4-4-4-5-5-5-5-5
0%
0,56
0
61 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8U6jM4y59jTY
0%
1,88
0
62 (D): https://www.chegg.com/homework-help/questions-and-answers/1-5-1-3-2-form-b--value-b-q110317741
0%
0,08
0
63 (C): https://stackoverflow.com/questions/38875628/what-is-this-series-1-1-2-2-3-3-3-4-4-4-5-5-5
0%
0,72
0
64 (D): https://www.calculator.net/fraction-calculator.html?ctype=2
0%
1,3
0
65 (D): https://www.mathway.com/Calculator/fraction-calculator
0%
0,92
0
66 (D): https://www.calculatorsoup.com/calculators/math/fractions.php
0%
0,77
0
67 (D): https://www.hackmath.net/en/calculator/fraction
0%
0,48
0
68 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kukOIC_9DZFmQ
0%
0,07
0
69 (C): http://www.duckduckhack.com
0%
0,56
0
70 (D): https://subjectum.eu/textbook/mathematics/mathematics6/37.html
0%
1
0
71 (D): https://en.wiktionary.org/wiki/і
0%
0,99
0
72 (D): https://uk.wikipedia.org/wiki/Послідовність_«Подивися-і-скажи»
0%
1,33
0
73 (D): https://znanija.com/task/53970328
0%
1,05
0
74 (D): https://znanija.com/task/56423600
0%
0,65
0
75 (D): https://naurok.com.ua/vivchaemo-chisla-i-cifri-1-2-doslidzhuemo-sklad-chisla-2-372533.html
0%
0,57
0
76 (D): https://uk.wikipedia.org/wiki/Список_хімічних_елементів
0%
0,54
0
77 (D): https://uahistory.co/pidruchniki/popel-chemistry-7-class-2024-reissue/12.php
0%
1,25
0
78 (D): https://znanija.com/task/20322803
0%
1,36
0
79 (D): https://znanija.com/task/11283524
0%
1,07
0
80 (D): https://superuser.com/questions/949659/how-can-i-access-storage-emulated-0-dcim-on-android-device
0%
1,04
0
81 (D): https://superuser.com/questions/1321276/how-to-access-router-with-ipv6-address
0%
2,16
0
82 (D): https://jingyan.baidu.com/article/ca41422f1d62601eae99ed92.html
0%
2,27
0
83 (D): https://jingyan.baidu.com/article/afd8f4de36697f74e286e9d6.html
0%
0,66
0
84 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kujPoe5-zVHlw
0%
0,54
0
85 (D): https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero
0%
1,69
0
86 (D): https://ukrainian.stackexchange.com/questions/306/difference-between-i-й-and-та
0%
0,56
0
87 (D): https://naurok.com.ua/pidmnozhina-operaci-nad-mnozhinami-422296.html
0%
0,44
0
88 (D): https://one.one.one.one/dns/
0%
0,66
0
89 (D): https://www.cloudflare.com/learning/dns/what-is-1.1.1.1/
0%
4,46
0
90 (D): https://blog.cloudflare.com/announcing-1111/
0%
1,62
0
91 (D): https://blog.cloudflare.com/introducing-1-1-1-1-for-families/
0%
0,42
0
92 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_06iOoC69jRFlA
0%
0,82
0
93 (D): https://studwood.net/1996745/informatika/mnozhennya_matrits_strichkoviy_shemi_rozdilennya_danih
0%
0,73
0
94 (D): https://yukhym.com/uk/matritsi-ta-viznachniki/vidi-matrits-operatsiji-dodavannnya-vidnimannya-transponuvannya-mnozhennya.html
0%
1,13
0
95 (D): https://vavi.od.ua/news/nou/uk/algoritm-nou-intuit-lekcia-paralelni-metodi-matricnogo-mnozenna.html
0%
0,53
0
96 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8k6uPYy59zpClQ
0%
0,54
0
97 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kanOYW-8jrd
0%
0,58
0
98 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8U6iOoC_-jvZ
0%
0,49
0
99 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9E2iM4259zVJlw
0%
0,59
0
100 (D): https://en.wikipedia.org/wiki/Basic_reproduction_number
0%
0,57
0
101 (D): https://en.wikipedia.org/wiki/Zero_ring
0%
1,38
0
102 (D): https://math.stackexchange.com/questions/3907172/what-does-the-set-r-0-represent
0%
0,7
0
103 (D): https://naurok.com.ua/zvuk-k-poznachennya-yogo-bukvami-k-k-slovnikovo---logichni-vpravi-1-klas-8770.html
0%
0,68
0
104 (D): https://nuschool.eu/lessons/mathematics/1klas_1/71.html
0%
0,71
0
105 (D): https://naurok.com.ua/uzhivannya-i-i-na-pochatku-slova-ta-uzhivannya-literi-za-novim-pravopisom-312983.html
0%
0,97
0
106 (D): https://vsimpptx.com/lesson/073-chitannya-zvuk-k-poznachennya-jogo-bukvoyu-k-k-ka-chitannya-skladiv-i-sliv-iz-bukvoyu-k
0%
0,92
0
107 (D): https://vseosvita.ua/library/vchymo-litery-litera-kk-zvuk-k-1-klas-725312.html
0%
0,45
0
108 (D): https://one.one.one.one/
0%
0,6
0
109 (D): https://one.one.one.one/nl-NL/
0%
0,55
0
110 (D): https://one.one.one.one/pl-PL/
0%
1,78
0
111 (D): https://www.wordnik.com
0%
0,73
0
112 (D): https://en.wikipedia.org/wiki/List_of_Cyrillic_letters
0%
1,26
0
113 (D): https://znanija.com/task/36280266
0%
0,56
0
114 (D): https://ru.wikipedia.org/wiki/Ї_(кириллица)
0%
1,42
0
115 (D): https://ell.stackexchange.com/questions/76708/how-to-read-1-2-1-and-1-2-1
0%
1,99
0
116 (D): https://stackoverflow.com/questions/3635955/how-to-create-a-1-1-1-2-1-3-html-list
0%
1,38
0
117 (D): https://math.stackexchange.com/questions/3367037/sum-of-1-1-2-1-3-1-n
0%
1,89
0
118 (D): https://stackoverflow.com/questions/31859932/style-an-ordered-list-like-1-1-1-2-instead-of-1-2
0%
0,85
0
119 (D): https://simple.wikipedia.org/wiki/Dotted_I_(Cyrillic)
0%
0,83
0
120 (D): https://matryza.blogspot.com/2015/03/blog-post_24.html
0%
0,62
0
121 (D): https://ru.wikipedia.org/wiki/І_(кириллица)
0%
0,91
0
122 (D): https://vsimpptx.com/lesson/0027-zvuki-l-l-mala-bukva-l-chitannya-skladiv-z-bukvoyu-l
0%
0,97
0
123 (D): https://svitporad.com.ua/skilky-ta-iak-varyty-rys.html
0%
1,18
0
124 (D): https://www.moyo.ua/ua/news/kak_varit_ris_9_layfkhakov_dlya_raznykh_vidov_i_sortov.html
0%
1,75
0
125 (D): https://tsn.ua/ukrayina/yak-zvariti-smachniy-ris-osnovni-sekreti-prigotuvannya-rozsipchastoyi-stravi-1911466.html
0%
0,52
0
126 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=806iOIW59DdGng
0%
0,66
0
127 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kekO4y-8DdFmg
0%
0,9
0
128 (D): https://slovnyk.ua/index.php?swrd=рядкові
0%
0,87
0
129 (D): https://slovnyk.ua/index.php?swrd=рядковий
0%
0,06
0
130 (C): https://zno.if.ua/?p=1422
0%
0,52
0
131 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kqiM4Gw-jJAkA
0%
0,53
0
132 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_0ygM4y_9DRFlg
0%
0,48
0
133 (D): https://myedu.cc/advanced-mathematics/elementi-teorii-viznachnikiv-i-matric/
0%
0,51
0
134 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9kqlP4269TtEmw
0%
0,56
0
135 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8UikM4W7-jJCmg
0%
0,74
0
136 (D): https://hrinchenko.com/spisok/bukva/i-1.html
0%
0,52
0
137 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8EikOYew8DJAkA
0%
0,48
0
138 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9EigPoO59jBHmQ
0%
0,82
0
139 (D): https://maimo.elit.sumdu.edu.ua/images/stories/docs/L_1.pdf
0%
0,71
0
140 (D): https://vseosvita.ua/lesson/mnozhyna-pidmnozhyna-chyslovi-mnozhyny-ratsionalni-chysla-irratsionalni-chysla-diisni-chysla-767908.html
0%
0,64
0
141 (D): https://vseosvita.ua/lesson/mnozhyna-pidmnozhyna-operatsii-nad-mnozhynamy-75583.html
0%
0,81
0
142 (D): https://www.miyklas.com.ua/p/algebra/11-klas/kombinatorika-15331/rozmishchennia-15338/re-dbf39c8b-f380-43a3-a5f7-b9bf14451a66
0%
0,58
0
143 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8EeiOYew8DNFnQ
0%
0,69
0
144 (D): https://ukrtvir.com.ua/biografiya-publij-vergilij-maron/
0%
0,59
0
145 (D): https://uahistory.co/pidruchniki/world-literature-8-class-2021-milyanovska-reissue/12.php
0%
0,9
0
146 (D): https://dityinfo.com/zarubizhnoi/publii-vergilii-maron.html
0%
0,55
0
147 (D): https://uahistory.co/zno/step-to-vnz-world-literature-2013-spivak-full-course/8.php
0%
1,61
0
148 (D): https://archive.org/details/book1989_Chislenye_metodi
0%
0,6
0
149 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=_kqnP4Cx8zVDmA
0%
0,6
0
150 (D): https://libcats.org/book/757869
0%
1,44
0
151 (D): https://rusneb.ru/catalog/010003_000061_6cefc45e078d568329ed25cd2ea4a442/
0%
1,03
0
152 (D): https://en.m.wiktionary.org/wiki/і
0%
0,88
0
153 (D): https://medmuv.com/uk/ukrainskij-alfavit/
0%
0,65
0
154 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9EmuMoe58DdAmA
0%
1,9
0
155 (D): https://ukrayinska.libretexts.org/Математика/Комбінаторика_та_дискретна_математика/Прикладні_дискретні_структури_(Doerr_і_Levasseur)/11:_Алгебраїчні_структури/11.04:_Найбільші_спільні_дільники_та_цілі_числа_по_модулю_n
0%
0,54
0
156 (D): https://matematik.org.ua/?p=887
0%
0,98
0
157 (D): https://vsimpptx.com/lesson/0034-dodavannya-i-vidnimannya-chisla-0
0%
0,91
0
158 (D): https://vseosvita.ua/library/konspekt-uroku-z-matematiki-1-klas-dodaemo-i-vidnimaemo-cisla-0-1-2-221371.html
0%
1,08
0
159 (D): https://vsimpptx.com/lesson/0047-vidkrivayemo-sposib-mirkuvannya-pri-dodavanni-i-vidnimanni-chisla-0
0%
1,12
0
160 (D): https://stackoverflow.com/questions/27552342/minimum-possible-jumps-needed-to-reach-m-1-n-1-from-0-0-in-a-2d-array
0%
1,24
0
161 (D): https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/
0%
0,77
0
162 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=8kqkMoy59TVEnw
0%
1,21
0
163 (D): https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
0%
0,6
0
164 (D): https://en.wikipedia.org/wiki/Division_by_zero
0%
1,96
0
165 (D): https://math.stackexchange.com/questions/3412295/justifying-why-0-0-is-indeterminate-and-1-0-is-undefined
0%
1,17
0
166 (D): https://discuss.pytorch.org/t/whats-different-between-dim-1-and-dim-0/61094
0%
1,21
0
167 (D): https://www.physicsforums.com/threads/disputing-1-0-infinity-agree-or-disagree.382475/
0%
1,24
0
168 (D): https://www.bbc.co.uk/blogs/ukrainian/ponomariv/2011/01/post-40.html
0%
1,72
0
169 (D): https://ukrayinska.libretexts.org/Математика/розрахунку/Книга:_Обчислення_(OpenStax)/15:_Багаторазова_інтеграція/15.06:_Обчислення_центрів_мас_і_моментів_інерції
0%
0,55
0
170 (D): https://web-crawler.plagiarism-detector.com/get-doc-pt?did=9UilPYG--ztCmA
0%
0,65
0
171 (D): https://uk.wikipedia.org/wiki/Нотація_Ландау
Важные замечания:

Википедия: | Google Книги: | Сервисы платных работ: | Античит:
Обнаружена Wiki! | [не обнаружено] | [не обнаружено] | Обнаружено сокрытие!

Античит-отчет UACE:
1. Статус: Анализатор Включен Нормализатор Включен сходство символов установлено на 100%
2. Обнаруженный процент загрязнения UniCode: 11,7% с лимитом: 4%
3. Процент нераспознанных символов после нормализации: 7,1%
4. Все подозрительные символы будут отмечены фиолетовым цветом: Abcd...
5. Найдены невидимые символы: 0

Рекомендации по оценке:
Особое внимание следует уделить анализу этого отчета! Предполагается, что этот документ содержит значительное количество символов, чуждых языку документа. Это прямое указание на то, что автор документа использовал специальное программное обеспечение\онлайн-веб-сервис, чтобы эффективно скрыть текст в попытке избежать обнаружения потенциального плагиата. Настоятельно рекомендуется передать это дело на более высокий уровень! В случае сомнений обращайтесь: в службу поддержки Детектора плагиата!

Алфавитная статистика и анализ символов:

символ: | кол-во: | частота%: | описание юникода:
--- | --- | --- | ---
[ ] | 24560 | 15,41% | space
о | 8958 | 5,62% | cyrillic small letter o
а | 7524 | 4,72% | cyrillic small letter a
н | 7450 | 4,67% | cyrillic small letter en
и | 6362 | 3,99% | cyrillic small letter i
і | 5858 | 3,68% | cyrillic small letter byelorussian-ukrainian i
т | 5722 | 3,59% | cyrillic small letter te
е | 5247 | 3,29% | cyrillic small letter ie
р | 5170 | 3,24% | cyrillic small letter er
в | 4707 | 2,95% | cyrillic small letter ve
. | 4357 | 2,73% | full stop
с | 3958 | 2,48% | cyrillic small letter es
м | 3709 | 2,33% | cyrillic small letter em
к | 3489 | 2,19% | cyrillic small letter ka
л | 3325 | 2,09% | cyrillic small letter el
д | 3282 | 2,06% | cyrillic small letter de
я | 2869 | 1,8% | cyrillic small letter ya
у | 2677 | 1,68% | cyrillic small letter u
п | 2676 | 1,68% | cyrillic small letter pe
з | 2348 | 1,47% | cyrillic small letter ze
ь | 1755 | 1,1% | cyrillic small letter soft sign
б | 1685 | 1,06% | cyrillic small letter be
t | 1660 | 1,04% | latin small letter t
, | 1576 | 0,99% | comma
o | 1505 | 0,94% | latin small letter o
г | 1497 | 0,94% | cyrillic small letter ghe
ц | 1434 | 0,9% | cyrillic small letter tse
i | 1372 | 0,86% | latin small letter i
e | 1340 | 0,84% | latin small letter e
r | 1293 | 0,81% | latin small letter r
х | 1240 | 0,78% | cyrillic small letter ha
n | 1185 | 0,74% | latin small letter n
ч | 1092 | 0,69% | cyrillic small letter che
a | 1029 | 0,65% | latin small letter a
1 | 1017 | 0,64% | digit one
) | 997 | 0,63% | right parenthesis
c | 987 | 0,62% | latin small letter c
( | 983 | 0,62% | left parenthesis
_ | 941 | 0,59% | low line
l | 850 | 0,53% | latin small letter l
ж | 848 | 0,53% | cyrillic small letter zhe
m | 841 | 0,53% | latin small letter m
є | 840 | 0,53% | cyrillic small letter ukrainian ie
0 | 810 | 0,51% | digit zero
ю | 754 | 0,47% | cyrillic small letter yu
s | 751 | 0,47% | latin small letter s
й | 743 | 0,47% | cyrillic small letter short i
p | 676 | 0,42% | latin small letter p
d | 653 | 0,41% | latin small letter d
2 | 648 | 0,41% | digit two
ї | 573 | 0,36% | cyrillic small letter yi
ш | 525 | 0,33% | cyrillic small letter sha
; | 520 | 0,33% | semicolon
v | 516 | 0,32% | latin small letter v
u | 501 | 0,31% | latin small letter u
щ | 427 | 0,27% | cyrillic small letter shcha
3 | 415 | 0,26% | digit three
: | 400 | 0,25% | colon
- | 371 | 0,23% | hyphen-minus
k | 363 | 0,23% | latin small letter k
ф | 360 | 0,23% | cyrillic small letter ef
b | 342 | 0,21% | latin small letter b
5 | 333 | 0,21% | digit five
4 | 322 | 0,2% | digit four
x | 315 | 0,2% | latin small letter x
= | 294 | 0,18% | equals sign
 | 272 | 0,17% | private use-f03d
6 | 257 | 0,16% | digit six
< | 255 | 0,16% | less-than sign
' | 244 | 0,15% | apostrophe
w | 237 | 0,15% | latin small letter w
f | 232 | 0,15% | latin small letter f
7 | 227 | 0,14% | digit seven
j | 219 | 0,14% | latin small letter j
9 | 216 | 0,14% | digit nine
[ | 211 | 0,13% | left square bracket
] | 211 | 0,13% | right square bracket
8 | 209 | 0,13% | digit eight
 | 201 | 0,13% | private use-f02d
y | 188 | 0,12% | latin small letter y
+ | 166 | 0,1% | plus sign
& | 155 | 0,1% | ampersand
h | 136 | 0,09% | latin small letter h
{ | 128 | 0,08% | left curly bracket
} | 128 | 0,08% | right curly bracket
z | 126 | 0,08% | latin small letter z
 | 122 | 0,08% | private use-f02b
" | 116 | 0,07% | quotation mark
> | 105 | 0,07% | greater-than sign
/ | 102 | 0,06% | solidus
g | 79 | 0,05% | latin small letter g
* | 79 | 0,05% | asterisk
 | 72 | 0,05% | private use-f0ea
 | 72 | 0,05% | private use-f0fa
� | 65 | 0,04% | non private use high surrogate-d835
– | 59 | 0,04% | en dash
~ | 53 | 0,03% | tilde
# | 48 | 0,03% | number sign
q | 42 | 0,03% | latin small letter q
| | 41 | 0,03% | vertical line
� | 38 | 0,02% | low surrogate-dc65
 | 34 | 0,02% | private use-f062
 | 28 | 0,02% | private use-f061
 | 27 | 0,02% | private use-f067
 | 16 | 0,01% | private use-f06b
ˆ | 15 | 0,01% | modifier letter circumflex accent
 | 14 | 0,01% | private use-f0e7
 | 14 | 0,01% | private use-f0f7
− | 13 | 0,01% | minus sign
 | 13 | 0,01% | private use-f0b9
 | 10 | 0,01% | private use-f0e9
 | 10 | 0,01% | private use-f0f9
 | 10 | 0,01% | private use-f0eb
 | 10 | 0,01% | private use-f0fb
 | 9 | 0,01% | private use-f0ce
« | 8 | 0,01% | left-pointing double angle quotation mark
» | 8 | 0,01% | right-pointing double angle quotation mark
 | 8 | 0,01% | private use-f03c
— | 8 | 0,01% | em dash
 | 8 | 0,01% | private use-f0a3
 | 7 | 0% | private use-f022
 | 7 | 0% | private use-f073
 | 7 | 0% | private use-f0e6
 | 7 | 0% | private use-f0f6
 | 7 | 0% | private use-f0e8
 | 7 | 0% | private use-f0f8
’ | 6 | 0% | right single quotation mark
 | 6 | 0% | private use-f0e5
! | 6 | 0% | exclamation mark
� | 5 | 0% | low surrogate-dc3c
 | 5 | 0% | private use-f0ac
 | 5 | 0% | private use-f0d1
\ | 5 | 0% | reverse solidus
 | 4 | 0% | private use-f0cc
 | 4 | 0% | private use-f05e
 | 4 | 0% | private use-f0c5
 | 4 | 0% | private use-f06d
ы | 4 | 0% | cyrillic small letter yeru
� | 3 | 0% | low surrogate-dc4f
§ | 3 | 0% | section sign
 | 3 | 0% | private use-f03e
 | 3 | 0% | private use-f0b4
 | 3 | 0% | private use-f0bb
� | 3 | 0% | low surrogate-dc58
� | 2 | 0% | low surrogate-dc4e
� | 2 | 0% | low surrogate-dc50
� | 2 | 0% | low surrogate-dc34
 | 2 | 0% | private use-f077
� | 2 | 0% | low surrogate-dc5d
� | 2 | 0% | low surrogate-dc56
 | 2 | 0% | private use-f0c7
 | 2 | 0% | private use-f0b3
σ | 2 | 0% | greek small letter sigma
 | 2 | 0% | private use-f05b
 | 2 | 0% | private use-f05d
 | 2 | 0% | private use-f0de
 | 2 | 0% | private use-f0b7
ґ | 2 | 0% | cyrillic small letter ghe with upturn
� | 2 | 0% | low surrogate-dc57
? | 1 | 0% | question mark
� | 1 | 0% | low surrogate-dc51
β | 1 | 0% | greek small letter beta
� | 1 | 0% | low surrogate-dc41
� | 1 | 0% | low surrogate-dc46
` | 1 | 0% | grave accent
 | 1 | 0% | private use-f0ae
 | 1 | 0% | private use-f0ad
 | 1 | 0% | private use-f028
 | 1 | 0% | private use-f029
 | 1 | 0% | private use-f0db
 | 1 | 0% | private use-f0c6
 | 1 | 0% | private use-f0ba
� | 1 | 0% | low surrogate-dc5b

Активные ссылки (URL-адреса, извлеченные из документа):

URL не найдены

Исключённые ресурсы:

URL не найдены

Включённые ресурсы:

URL не найдены

Детальный анализ документа:
Міністерство освіти і науки України Державний заклад
id: 1
Цитирования: 0,02%
«Луганський національний університет імені Тараса Шевченка»
Навчально-науковий інститут фізики, математики та інформаційних технологій Кафедра інформаційних технологій та систем Семенов Микола Анатолійович РОЗРОБКА ТА ДОСЛІДЖЕННЯ СПОСОБІВ ПРЕДСТАВЛЕННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ ЗА ДОПОМОГОЮ ОБ’ЄКТНО-ОРІЄНТОВАНОГО ПРОГРАМУВАННЯ кваліфікаційна робота здобувача вищої освіти другого (магістерського) рівня освітньої програми
id: 2
Цитирования: 0,01%
«Мультимедійні системи»
за спеціальністю 121 Інженерія програмного забезпечення Особистий підпис ______ ______ __ Микола СЕМЕНОВ Науковий керівник _____ ______ __ Геннадій МОГИЛЬНИЙ, кандидат технічних наук, доцент кафедри інформаційних технологій та систем Завідувач кафедри _____ ______ __ Микола СЕМЕНОВ, кандидат педагогічних наук, доцент кафедри інформаційних технологій та систем Полтава – 2023 АНОТАЦІЯ Семенов М.А. Тема: Розробка та дослідження способів представлення систем лінійних алгебраїчних рівнянь за допомогою об’єктно-орієнтованого програмування Спеціальність: 121
id: 3
Цитирования: 0,01%
«Інженерія програмного забезпечення».
Установа: ЛНУ імені Тараса Шевченка, 2023р. Магістерська робота містить: 114 с., 29 рис., 13 табл., 65 джерел. Об’єкт дослідження – оптимізація представлення інформації в пам'яті комп'ютера для обчислень лінійної алгебри. Предмет дослідження – розробка об'єктно-орієнтованих бібліотек класів для ефективного зберігання та обробки матриць у пам'яті та розв'язання систем лінійних алгебраїчних рівнянь. Мета роботи - розробка структур даних, у яких реалізовані ефективні методи зберігання та обробки матриць та векторів у пам'яті комп'ютера, а також реалізація алгоритмів розв'язання СЛАР на їх основі. Результати роботи – в роботі виконано огляд практичної реалізації структур даних для широкого класу матриць, які дозволяють ефективно зберігати та обробляти матрицю у пам'яті. Реалізовано проекційні методи вирішення СЛАР підпростору Крилова на основі структур даних, які розроблені за допомогою об’єктно-орієнтованого програмування. Досліджено ефективність проекційних методів рішення з різними передумовами. Ключові слова: СИСТЕМІ ЛІНІЙНИХ АЛГЕБРАІЧНИХ РІВНЯНЬ, ОБ’ЄКТНО-ОРІЄНТОВАНЕ ПРОГРАМУВАННЯ;.СТРУКТУРИ ДАНИХ, МЕТОДИ ПРЕДСТАВЛЕННЯ ДАНИХ, МЕТОДИ ЗБЕРІГАННЯ ДАНИХ, МЕТОДИ ОПТИМІЗАЦІЇ ЗБЕРІГАННЯ ДАНИХ 2 А N N О T А T І О N S е m е n о v M у k о l а T h е m е: D е v е l о р m е n t а n d r е s е а r с h о f m е t h о d s о f r е р r е s е n t і n g s у s t е m s о f l і n е а r а l g е b r а і с s у s t е m s u s і n g о b j е с t-о r і е n t е d р r о g r а m m і n g. S р е с і а l і t у: 121 " S о f t w а r е е n g і n е е r і n g ". І n s t і t u t і о n: L u h а n s k T а r а s S h е v с h е n k о N а t і о n а l U n і v е r s і t у (L T S N U), 2023 у е а r. M а s t е r's w о r k о f: 114 р., 29 і m, 13 t b l, 65 s о u r с е s. T h е о b j е с t о f t h е r е s е а r с h і s t h е о р t і m і z а t і о n о f t h е r е р r е s е n t а t і о n о f і n f о r m а t і о n і n t h е с о m р u t е r m е m о r у f о r l і n е а r а l g е b r а с а l с u l а t і о n s. T h е s u b j е с t о f r е s е а r с h і s t h е d е v е l о р m е n t о f о b j е с t-о r і е n t е d с l а s s l і b r а r і е s f о r е f f і с і е n t s t о r а g е а n d р r о с е s s і n g о f m а t r і с е s і n m е m о r у а n d s о l v і n g s у s t е m s о f l і n е а r а l g е b r а і с е q u а t і о n s. T h е р u r р о s е о f t h е t h е s і s і s t h е d е v е l о р m е n t о f d а t а s t r u с t u r е s t h а t і m р l е m е n t е f f е с t і v е m е t h о d s о f s t о r і n g а n d р r о с е s s і n g m а t r і с е s а n d v е с t о r s і n с о m р u t е r m е m о r у, а s w е l l а s t h е і m р l е m е n t а t і о n о f а l g о r і t h m s f о r s о l v і n g s у s t е m s о f l і n е а r а l g е b r а і с е q u а t і о n s b а s е d о n t h е m . T h е r е s u l t s і n с l u d е а n о v е r v і е w о f t h е р r а с t і с а l і m р l е m е n t а t і о n о f d а t а s t r u с t u r е s f о r а w і d е с l а s s о f m а t r і с е s, w h і с h а l l о w е f f і с і е n t s t о r а g е а n d р r о с е s s і n g о f t h е m а t r і х і n m е m о r у. Р r о j е с t і v е m е t h о d s f о r s о l v і n g t h е s у s t е m s о f l і n е а r а l g е b r а і с е q u а t і о n s о f t h е K r у l о v s u b s р а с е b а s е d о n d а t а s t r u с t u r е s d е v е l о р е d u s і n g о b j е с t-о r і е n t е d р r о g r а m m і n g h а v е b е е n і m р l е m е n t е d. T h е е f f е с t і v е n е s s о f р r о j е с t і о n m е t h о d s о f t h е s о l u t і о n w і t h d і f f е r е n t р r е r е q u і s і t е s w а s і n v е s t і g а t е d. K е у w о r d s: S У S T Е M S О F L І N Е А R А L G Е B R А І С Е Q U А T І О N S, О B J Е С T-О R І Е N T Е D Р R О G R А M M І N G; D А T А S T R U С T U R Е S, D А T А R Е Р R Е S Е N T А T І О N M Е T H О D S, D А T А S T О R А G Е M Е T H О D S, D А T А S T О R А G Е О Р T І M І Z А T І О N M Е T H О D S. 3 ЗМІСТ ВСТУП ................................................................................................................. 6 РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ ТЕХНОЛОГІЇ ЗБЕРІГАННЯ МАТРИЦЬ ........................................................................................................... 9 1.1. Формулювання критерій подання матриць ......................................... 9 1.2. Зберігання масивів, списків, стеків та черг ....................................... 12 1.3. Зберігання цілих списків ....................................................................... 16 1.4. Подання та зберігання графів .............................................................. 19 1.5. Схеми зберігання матриць великої розмірності ................................ 23 1.6. Символічна обробка та динамічні схеми зберігання ........................ 37 Висновки до першого розділу ...................................................................... 41 РОЗДІЛ 2. МАТЕМАТИЧНЕ ПРЕДСТАВЛЕННЯ МАТРИЧНИХ АЛГОРИТМІВ .................................................................................................. 43 2.1. Принципи побудови ітераційних процесів ......................................... 43 2.2. Побудова проекційних методів ............................................................. 46 2.3. Підпростори Крилова ............................................................................ 52 2.3.1. Метод спряжених градієнтів.............................................................................................. 54 2.3.2. Метод біспряжених градієнтів ........................................................................................... 56 2.4. Передумовлення ..................................................................................... 57 2.5. І L U-факторизація ................................................................................... 62 Висновки до другого розділу ....................................................................... 66 РОЗДІЛ 3. РОЗРОБКА БІБЛІОТЕКИ КЛАСІВ ДЛЯ ПРЕДСТАВЛЕННЯ СЛАР .................................................................................................................. 68 3.1. Використання ООП підходу до подання СЛАР ................................. 68 3.2. Реалізація моделі бібліотеки класів ..................................................... 69 3.3. Програмна реалізація класів ................................................................ 72 3.4. Дослідження ефективності методів вирішення представлених у розробленій бібліотеці ................................................................................... 85 Висновки до третього розділу ..................................................................... 88 ВИСНОВКИ ...................................................................................................... 89 4 СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ....................................................... 93 ДОДАТКИ ......................................................................................................... 99 Додаток А. Реалізація класу M V_V е с t о r .................................................... 99 Додаток Б. Реалізація класу С о m р С о l_M а t_d о u b l е ............................... 104 Додаток В. Реалізація класу С о m р R о w_M а t_d о u b l е .............................. 108 Додаток Г. Дані дослідження ..................................................................... 112 5 ВСТУП Актуальність теми магістерської роботи обумовлена необхідністю ефективного (з високою точністю та мінімальними витратами ресурсів) чисельного вирішення систем лінійних алгебраїчних рівнянь (СЛАР). Чисельне рішення СЛАР – одне з найпоширеніших завдань у науково- технічних дослідженнях. Таке завдання виникає у математичній фізиці (чисельне рішення диференціальних та інтегральних рівнянь), економіці, статистиці. При цьому прикладні завдання часто вимагають вирішення великих і надвеликих СЛАР з числом невідомих більше 10000. До таких СЛАР, наприклад, наводить чисельне рішення двовимірних і особливо тривимірних задач математичної фізики, в яких умови фізичної та геометричної апроксимації двовимірної та тривимірної області диктують використання досить дрібної розрахункової сітки з великою кількістю розрахункових вузлів за лінійним розміром [40]. У зв'язку з цим основна причина розробки та дослідження нових форматів зберігання даних, особливо якщо йдеться про багатовимірні матриці з розрідженою структурою,
id: 4
Обнаружен Плагиат: 0,1%https://web-crawler.plagiarism-detect…
0,1%
https://web-crawler.plagiarism-dete…
полягає в тому, що класичні схеми зберігання даних не забезпечують високої продуктивності обчислень для деяких структур і топологій матриць. Нові схеми зберігання можуть бути використані для
програм, написаних для різних мов програмування. Особливо слід підкреслити, що хороші результати оптимізації коду можуть бути отримані для сучасних компіляторів, в яких реалізовані ефективні алгоритми оптимізації коду [55]. У разі реалізації алгоритму в класичному стилі, коли кількість ітерацій заздалегідь відома і залежить тільки від порядку матриці, алгоритм буде ефективним лише у роботі з невеликими матрицями N~1000. Однак у разі застосування алгоритму до матриці близько 100000 і більше алгоритм буде неефективним. Наприклад, на розрахунок такої матриці методом Холецького піде чимало часу, оскільки число арифметичних операцій множення для N чисельного розв'язання СЛАР розмірністю за допомогою прямого методу 6 3 N ~ . Якщо дану матрицю зберігати в звичайному двовимірному масиві, то при використанні речовинного типу з подвійною точністю (d о u b l е) вона займатиме в пам'яті 100000*100000*8=800000000 байт − 800 Мб, що є досить ресурсомістким завданням навіть для сучасних ЕОМ. А якщо врахувати, що розмір матриці зростає пропорційно квадрату порядку матриці, то для матриці близько 400000 це буде в 16 разів більше, тобто 12.8 Гб. В даний час відсутні бібліотеки структур даних широкого призначення для зберігання та обробки матриць великої розмірності, які можуть застосовуватись в алгоритмах для чисельного вирішення великих та надвеликих СЛАР. Таким чином, розробка структур даних, які дозволяють ефективно зберігати та обробляти широкого класу матриці великої розмірності та як наслідок брати участь у реалізації алгоритмів
id: 5
Обнаружен Плагиат: 0,06%https://knowledge.allbest.ru/program… + 2 ресурсов!
0,8%
https://knowledge.allbest.ru/progra…
0,1%
https://vuzlit.com/895283/elementi_…
розв'язання, систем лінійних алгебраїчних рівнянь є актуальним завданням. Дослідженням методів вирішення систем лінійних алгебраїчних рівнянь
займалися: Д. Мак-Кракен, С. Годунов, В. Воєводін, А. Островський, Дж. Форсайт, К. Молер, Жегульська. Об'єктно-орієнтований підхід у реалізації чисельних методів використовували: Р. Беретт, М. Бері, Тоні Ф. Чан, Д. Демл, Д. Донато, Д. Донгарра, Ст Ейджкаут, Р. Позо, Ч. Ромін. Об'єкт дослідження – оптимізація представлення інформації в пам'яті комп'ютера для обчислень лінійної алгебри. Предмет дослідження – розробка об'єктно-орієнтованих бібліотек класів для ефективного зберігання та обробки матриць у пам'яті та розв'язання систем лінійних алгебраїчних рівнянь. Метою роботи є розробка структур даних, у яких реалізовані ефективні методи зберігання та обробки матриць та векторів у пам'яті комп'ютера, а також реалізація алгоритмів розв'язання СЛАР на їх основі. Відповідно до мети роботи поставлені такі завдання: 1. Реалізація структур даних для широкого класу матриць, які дозволяють ефективно зберігати та обробляти матрицю у пам'яті. 7 2. Реалізація проекційних методів вирішення СЛАР підпростору Крилова на основі розроблених структур даних. 3. Розробка структури та програмних модулів бібліотеки класів мовою С++ для вирішення СЛАР. 4. Дослідження ефективності у вигляді порівняння часу виконання проекційних методів рішення з різними передумовами використовуючи реалізовані структури даних для зберігання широкого класу матриць. Гіпотеза – об'єктно-орієнтовані бібліотеки класів можуть ефективно використовуватися у вирішенні систем лінійних алгебраїчних рівнянь. 8 РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ ТЕХНОЛОГІЇ ЗБЕРІГАННЯ МАТРИЦЬ 1.1. Формулювання критерій подання матриць У багатьох галузях людської діяльності інформацію часто подають у формі матриць. Матриця - це регулярний числовий масив. Головними характеристиками представлення матриць є щільність чи розрідженість її структури, дані характеристики залежать від значення елементів, що містяться в матриці [45]. Найбільш важливим є поняття розріджених матриць, особливо якщо йдеться про матриці великої розмірності. У спеціальній літературі є кілька визначень розрідженої матриці. Суть їх полягає в тому, що матриця розріджена, якщо в ній розміщено велику кількість нульових елементів. У [33] використовують поняття, пов'язані з граничним переходом: матрицю порядку n називають розрідженою, якщо О (n) число її ненульових елементів є . Це означає, що кількість елементів, що відрізняються від нуля, при досить великих n пропорційно n. Однак для заданої матриці n не є достатньо великим, а цілком конкретним числом. Відповідно до [26] критерієм розрідженості пропонується вважати обмеженість числа ненульових елементів у рядку, у типовому випадку від 2 до 10. Інше визначення полягає в тому, що матриця порядку n вважається 1 v n розрідженою, якщо число її ненульових елементів виражається як , де v  1 . Типові значення v: 0.2 для електричних задач; 0.5 для стрічкових v  0,9 матриць, асоційованих із сітками. Матриця порядку 1000 при має 501187 ненульових елементів, в цьому випадку виникає питання, чи варто вважати таку матрицю розрідженою. Більш практичний підхід до визначення розрідженої матриці спирається на взаємозв'язок трьох основних інгредієнтів: даної матриці, даного алгоритму та даної обчислювальної машини. Це поняття за своєю природою є евристичним: матриця розріджена, якщо має сенс отримувати вигоду з наявності в ній багатьох нулів. Будь-яку розріджену матрицю можна 9 обробляти так, ніби вона була щільною: навпаки, будь-яку щільну, або заповнену, матрицю можна обробляти алгоритмами для розріджених матриць. У обох випадках вийдуть правильні чисельні результати, але обчислювальні витрати зростуть [45]. Приписування матриці якості розрідженості еквівалентно твердженню про існування алгоритму, що використовує її розрідженість і робить обчислення з нею дешевше в порівнянні зі стандартними алгоритмами. Розріджену матрицю можна розглядати як числовий масив, у загальному випадку не регулярний. Однак найчастіше асоціюють з цими числами позиції в значно більшому регулярному масиві, оскільки зручніше аналізувати в термінах регулярних масивів і виходити з них при конструюванні алгоритмів [64]. Розглянемо наступну систему восьми лінійних рівнянь із вісьмома невідомими: х  3 3 х  2 х  16 1 6 х  х  3 1 2 х  х  6 2 8 х  2 х  х  1 4 5 7  х  х  3 3 6  х  х  2 5 7  2 х  х  0 4 8 Цій системі можна поставити у відповідність таку матрицю коефіцієнтів:
id: 6
Обнаружен Плагиат: 0,38%https://dspace.sfa.org.ua/bitstream/1… + 14 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,8%
https://knowledge.allbest.ru/progra…
0,3%
https://djvu.online/file/QBjLFvddnjo…
0,3%
https://dl.sumdu.edu.ua/courseboo…
0,3%
https://web-crawler.plagiarism-dete…
0,3%
https://web.kpi.kharkov.ua/apm/wp…
0,2%
https://tk.znu.edu.ua/nmk/Lec_vm_…
0,2%
https://www.netspotapp.com/blog/ip…
0,1%
https://matryza.blogspot.com/2015…
0,1%
https://routerhax.com/10.0.0.1/
0%
https://uk.wikipedia.org/wiki/Матри…
0%
https://zaxid.net/yak_variti_ris_prav…
0 0 1 0 0 0 0 0     1 0 0 0 0 2 0 0     1 1 0 0 0 0 0 0   0 1 0 0 0 0 0  1     0 0 0 1  2 0 1 0   0 0  1 0 0 1 0 0     0 0 0 0  1 0 1 0   0 0 0  2 0 0 0 1     10
Ця система має лише 16 коефіцієнтів, а використовується 64 позиції. У цьому випадку не є ефективним заповнювати несуттєві позиції нулями, а потім намагатися отримати вигоду з наявності настільки великої кількості нулів. У загальному випадку, розріджену матрицю слід представляти не як матрицю, а скоріше як граф, де кожна пара рівняння – невідоме асоціюється з вершиною, а кожен коефіцієнт – з ребром. Тому теорія графів відіграє важливу роль у технології розріджених матриць. Розріджена матриця, будучи безліччю чисел, що не мають регулярності, не може бути представлена в пам'яті машини тим самим простим способом, що і повна матриця. Якщо зберігаються чисельні значення коефіцієнтів системи рівнянь, необхідно разом із значенням кожного коефіцієнта зберігати номер відповідного рівняння та номер відповідного невідомого. Тобто потрібно зберігати значення ненульових елементів плюс індексна інформація, що вказує на розташування кожного елемента в регулярному масиві. Ця додаткова інформація становить накладні витрати – ціну, яку доводиться сплачувати за відмову від зберігання нулів [45]. Матричні алгоритми повинні проектуватися таким чином, щоб оброблялися тільки ненульові елементи і щоб на підставі попереднього знання розташування ненульових елементів уникалися операції типу складання з нулем або множення на нуль. Таким чином, число операцій, що робляться машиною при виконанні алгоритму, пропорційно числу ненульових елементів, а не числу всіх елементів матриці. Слід зазначити, що було б неправильно зберігати всі елементи, включаючи нулі, а потім оминати операції з нулями за допомогою оператора і f. Цей оператор без необхідності 2 n виконуватиметься раз чи більше, перетворюючи алгоритм на квадратичний по порядку n матриці. Хороший алгоритм для розріджених матриць використовує наявні в нього відомості про позиції ненульових елементів, щоб робити необхідні операції. Якщо для розрідженої матриці 11 число ненульових елементів у рядку постійно, то в багатьох випадках порядок оптимального алгоритму може зменшуватися до n [54]. Розріджена матриця, що представляє задану інформацію, має певну задану розрідженість. Проте якщо розріджена матриця породжується якимось алгоритмом як проміжний результат у межах ширшого рахунку, виникає питання: чи немає способу збільшити її розрідженість шляхом генерування меншого числа ненульових елементів? Найважливіший випадок, коли відповідь ствердна, — це гауссовий виняток. У гауссовому винятку розрідженість матриці зменшується порівняно з вихідною, оскільки виникають нові ненульові елементи. Результуюча матриця менш розріджена, ніж вихідна, але ступінь її заповнення залежить від порядку, в якому вибираються основні елементи. Хороший алгоритм для розріджених матриць намагається зберегти розрідженість, наскільки можна зменшуючи заповнення [45]. Таким чином, можна сформулювати три основні критерії, які спрямовували розвиток більшої частини технології розріджених матриць: зберігати лише ненульові елементи, оперувати лише з ненульовими елементами та зберігати розрідженість. Не всі алгоритми для розріджених матриць досягають цих цілей, лише найбільш витончені. Багато схем зберігання допускають певну частку нулів, і алгоритм обробляє їх, якби вони були нулями. Алгоритм, що зберігає і обробляє меншу кількість нулів, складніший у реалізації і доцільний лише досить великих матриць. Існує повний спектр алгоритмів, розрахованих на різні типи матриць, від щільних до дуже розріджених, з різними необхідними для практики ступенями ефективності, складності чи простоти. 1.2. Зберігання масивів, списків, стеків та черг Технологія представлення матриць часто вимагає зберігання та обробки списків, елементами яких можуть бути числа, цілі, речові або комплексні або об'єкти більш складної структури, такі, як матриця, масив або вершина графа разом з відповідними ребрами. Основними операціями, які 12 зазвичай виконуються над списками є: додавання елемента в кінець списку, видалення елемента з кінця списку, вставка або видалення елемента в середині або на початку списку, визначення позиції деякого елемента або елемента, наступного за даними, сортування, впорядкування. Вибір схеми зберігання залежить від операцій, які передбачається проводити, оскільки ефективність виконання цієї операції не регулярна щодо різних схем зберігання [45]. Найпростіша структура даних – це масив. Його особливістю є те, що крім зберігання чисел він може містити покажчики на елементи складнішої природи, що зберігаються насправді десь в іншому місці. Всі елементи масиву доступні безпосередньо за час, що не залежить від його розміру. Але з накладними витратами пов'язане використання подвійних чи кратних індексів, оскільки машинна пам'ять одномірна. У машинах з віртуальною пам'яттю масив може знаходитися на периферійному пристрої, що запам'ятовує, і це призводить до великих тимчасових витрат для доступу по індексу [55]. Лінійний зв'язковий список - це послідовність осередків, пов'язаних у певному порядку. Кожна комірка містить елемент списку та покажчик, що повідомляє положення наступної комірки. Припустимо, що необхідно зберігати числа а, b, с, d у вказаному порядку в масиві А (І). Схема зберігання може бути представлена наступним чином (символом х відзначені несуттєві значення): позиція = 1 2 3 4 5 6 7 8 А(��) = �� �� �� �� �� �� �� �� n е х t(��) = �� 7 �� 0 2 �� 4 �� І Р = 5 ознака кінця = 0 Рис. 1.1. Схема зберігання зв'язкового списку У масиві А(І) зберігаються елементи списку, а n е х t(І) — покажчики позицій наступних елементів. І Р є вказівником входу, що показує 13 розташування першого елемента. У цьому випадку він дорівнює 5. У позиції 5 знаходимо перший елемент А(5) = а, а n е х t(5) = 2 повідомляє, що наступний елемент потрібно шукати в позиції 2. У такий спосіб можна переглянути весь список. В останню клітинку повинно бути поміщено - ознака кінця, що вказує закінчення списку; в даному прикладі такою ознакою служить 0. Ще один спосіб полягає в тому, щоб зберігати загальну кількість елементів списку та за допомогою цього числа визначати, коли список вичерпаний. Порожній список зручно задавати, присвоюючи покажчику входу значення, яке може адресувати будь-яку позицію масивів, наприклад непозитивне число [58]. Досить легко вставляти або видаляти елементи в будь-якому місці. Якщо між b і с необхідно вставити число е, і відомо, що комірка 3 порожня, а b знаходиться в позиції 2. Наступна процедура виконує необхідну операцію: А(3)  е n е х t(3)  n е х t(2) n е х t(2)  3 Процедура видалення елемента значно простіша: n е х t(2)  n е х t(7) Для виконання цієї процедури необхідно знати, що елемент, що передує, розташований в позиції 2, таким чином, відбувається видалення елемента, наступного за b, а не самого с. Якщо потрібно вставити або видалити елемент на початку списку, слід перевизначити покажчик входу. Вставлення або видалення елементів не змінює порядок, у якому зберігаються інші елементи [55]. Якщо список зберігається у масиві, важливо мати інформацію про вільні позиції останнього. Їх також пов'язують у список, що потребує ще одного покажчика входу. Обидва списки не перетинаються, тому можуть бути збережені в тих самих масивах. Нижче наведена структура даних вийде, якщо зв'язати вільні позиції. (І Е – покажчик входу для нового списку): позиція = 1 2 3 4 5 6 7 8 14 А(��)= �� �� �� �� �� �� �� �� n е х t(��) = 3 7 6 0 2 8 4 0 І Р = 5 І Е = 1 ознака кінця = 0 Рис. 1.2. Зв'язковий список з інформацією про вільні позиції Зв'язковий список стає кільцевим зв'язковим списком, якщо в його останню позицію замість ознаки кінця помістити покажчик на початкову позицію. Кільцевий список не має початку і кінця, він вимагає окремого покажчика входу, що зберігається окремо, який може вказувати на будь-яку зайняту позицію. У кільцевому списку елементи можна видаляти чи додавати, не змінюючи порядку інших, а вільні позиції пов'язувати так само, як у лінійному списку [45]. Двонаправлений зв'язковий список, лінійний або кільцевий, можна отримати у разі, якщо ввести масив, що містить для кожної комірки адресу попередньої комірки. Двонаправлений список можна переглядати в обох напрямках; одним з головних його переваг є те, що можна вставляти або видаляти елементи, не знаючи позиції попереднього елемента. Лінійний двонаправлений список вимагає двох покажчиків входу – покажчик початку списку та покажчик кінця списку. Для кільцевого двонаправленого списку достатньо одного покажчика входу. Є можливість пов'язати між собою вільні позиції двонаправленого списку. Стек – це список зі спрощеним способом зберігання та обробки [55]. У стеку елементи зберігаються у послідовних позиціях, чим усувається потреба у зв'язках. Для визначення позиції останнього елемента використовується спеціальний покажчик. Застосування стека зумовлене ситуаціями, коли елементи потрібно додавати або видаляти тільки через верх стека. Щоб увімкнути або опустити новий елемент у стек, необхідно збільшити значення покажчика на одиницю, перевіривши вільну кількість пам'яті, а потім 15 виконується запис елемента у позицію, що повідомляється покажчиком. Щоб виключити або підняти останній елемент з верху стека, слід зменшити на одиницю значення вказівника. Порожній стек розпізнається за нульовим значенням покажчика. Стеки використовують у кількох алгоритмах для розріджених матриць. Прикладами можуть бути алгоритм Джорджа для деревоподібного розбиття, що обговорюється в [57], і алгоритм Тар'яна для блокової тріангуляризації матриці, що розглядається в [57]. Черга - це список елементів, що зберігаються в послідовних позиціях, причому включення елементів проводиться через початок черги, а виняток - через кінець [55]. Для зазначення позицій початку та кінця черги використовуються два покажчики. Порожня черга пізнається завдяки тому, що для неї значення покажчика кінця на одиницю більше значення покажчика початку. Для черги з єдиним елементом значення обох покажчиків збігаються. Якщо ділянка пам'яті, відведена для зберігання черги, вичерпана, нові елементи можна записувати на початок цієї ділянки, закільцевавши тим самим чергу; при цьому початок черги не повинен перетинатися з її кінцем. Усі вище описані схеми зберігання спираються на масив як єдину структуру даних, підтримувану мовою програмування С++. Властивості зв'язкових списків можна ефективно реалізувати, використовуючи таку структуру даних, як запис. У цьому випадку не потрібно непрямої адресації, і пам'ять може динамічно розподілятися ціною деяких системних витрат пам'яті [41]. 1.3. Зберігання цілих списків Цілі списки є особливо важливими технологіями розріджених матриць [43]. Елементи списку належать множині (1, 2, ..., n); деякі з них можуть повторюватись. Нехай m – кількість елементів списку; n називається m  n розмахом списку. Список називають розрідженим, якщо . Цілий список можна зберігати у компактній формі, користуючись масивом довжини, не меншою за m; так, для списку 3, 11, 7, 4: 16 позиція = 1 2 3 4 5 6 J А = 3 11 7 4 M = 4 Рис. 1.3 Зберігання списку у компактній формі Крім масиву J А необхідно зберігати (за допомогою змінної М) число m елементів списку; у вище поданому випадку m = 4. Порожній список упізнається за нульовим значенням М. Щоб включити до списку новий елемент, достатньо збільшити М на одиницю і потім записати новий елемент у позицію з номером М. Щоб виключити елемент із позиції і, необхідно перенести в цю позицію останній елемент і зменшити М на одиницю. Якщо потрібно зберігати впорядкованість цілих чисел, то включення або виключення елемента в якійсь позиції викликає зсув всіх елементів, що знаходяться праворуч від неї. Цілі списки з повтореннями або без них можуть зберігатися як зв'язні лінійні або кільцеві списки за допомогою масиву J А довжини не менше m і додаткового масиву N Е Х T; Цей тип зберігання також компактний, тому підходить для розріджених списків. Для цілих списків із різними елементами існує альтернатива. Такий список може зберігатися одним масивом довжини n або більшої у формі зв'язного списку, лінійного або кільцевого. Якщо у наведеному вище прикладі використовувати кільцевий зв'язковий список, то отримаємо наступний опис матриці, представлений (рис. 1.4). позиція = 1 2 3 4 5 6 7 8 9 10 11 12 J А = �� �� 11 3 �� �� 4 �� �� �� 7 �� І Р = 3 Рис. 1.4. Кільцевий зв'язковий список Число, яке зберігається в кожній позиції J А, дає одночасно значення елемента списку та адресу наступного елемента; тому додатковий масив n е х t стає зайвим. Для входу в ланцюг необхідний вказівник І Р, що задає позицію першого числа у списку. Цей тип зберігання називають розширеним, на 17 противагу компактному, тому що для нього потрібний масив довжини, принаймні n. У будь-якому місці списку нескладно увімкнути або виключити елемент, не змінюючи порядку, де зберігаються інші елементи. Наприклад, якщо і, k - два послідовні елементи списку, що знаходяться в масиві J А, так що J А(і) = k і тепер потрібно вставити j між і і k. Тоді вважаємо наступне: Якщо, навпаки, необхідно виключити k, то J А(j)  J А(k) Якщо необхідно увімкнути елемент перед першим елементом або видалити перший елемент, слід перевизначити покажчик входу. Список одного елемента, припустимо 5, при використанні розширеної схеми виглядає наступним чином: позиція = 1 2 3 4 5 6 7 8 9 J А = �� �� �� �� 5 �� �� �� �� І Р = 5 Рис. 1.5. Розширена схема зберігання Порожній список можна впізнати за нульовим чи негативним значенням покажчика входу. Одне з головних застосувань розширеної схеми - це зберігання декількох списків, що не перетинаються, тобто списків, що не мають загальних елементів [54]. У більшості випадків всі списки мають однаковий розмах, але в загальному випадку вважатимемо n максимальним з розмахів окремих списків. Усі списки можна зберігати в тому самому масиві, довжини n або більшої. Також потрібен масив покажчиків входу. Проілюструємо описуваний спосіб зберігання прикладом. Розглянемо три цілих списки, що не перетинаються: 1. Список: 2, 8, 6, 3; 2. Список: 5, 4, 9; 18 3. Список: 7, 1, 10; Дані списки можуть бути розміщені як кільцеві зв'язкові списки в одному масиві довжини 10: позиція = 1 2 3 4 5 6 7 8 9 10 J А = 10 8 2 9 4 3 1 6 5 7 І Р = 2 5 7 Рис. 1.6. Кільцеві зв'язкові списки в одному масиві При використанні цього типу зберігання легко виконуються такі операції, як розбиття списку на два або конкатенація двох списків з утворенням нового [55]. 1.4. Подання та зберігання графів Графи є важливою частиною технології розріджених матриць, оскільки існує відповідність між матрицями і графами, що зберігає деякі властивості. На рис. 1.7 (а) представлений граф, що складається з п'яти вершин і семи ребер. Точніше, граф G = (U, Е) складається з безлічі вершин U та безлічі ребер Е; ребро можна ототожнити з парою (u, v) різних вершин із U. Наприклад, на рис. 1.7 (а) 3 є вершина, а (3, 5) - ребро, що зображується відрізком, що з'єднує вершини 3 і 5. Рис. 1.7. Неорієнтований граф (а) та орієнтований граф (б) 19 Якщо пари (u, v) і (v, u) не відрізняються, то кажуть, що ребра ототожнюються з невпорядкованими парами, а граф називають неорієнтованим. Якщо пари, що представляють ребра, упорядковані, то граф (u , v)  Е називають орієнтованим графом. Якщо в орієнтованому графі , то кажуть, що v суміжна з u. Якщо (u, v) — ребро неорієнтованого графа, то кажуть, що v суміжна з u і u суміжна з v. Неорієнтований граф можна розглядати як орієнтований, у якому, якщо (u, v) — ребро, то (v, u) також ребро. Щоб зобразити граф з вершинами n, зручно помітити його, встановивши відповідність між вершинами і цілими числами 1, 2, n. На рис. 1.7 показані приклади орієнтованого та неорієнтованого графа. У пам'яті машини граф можна представити, зберігаючи для кожної вершини список вершин, суміжних із нею. Така множина списків називається структурою суміжності графа [40]. Якщо списки зберігаються у компактній формі (масив l і s t), то необхідний ще масив покажчиків (І Р) початку кожного списку. Для орієнтованого графа (рис. 1.7 б) структура суміжності може бути представлена наступним чином: позиція = 1 2 3 4 5 6 7 8 l і s t = 2 5 1 5 1 3 2 І Р = 1 3 3 5 7 8 Рис. 1.8. Структура суміжності орієнтованого графа Список суміжності, наприклад, для вершини 4 починається з 5 позиції масиву l і s t, що випливає зі значення 5 покажчика І Р(4), і закінчується в 6 позиції, це пов'язано з тим, що наступний список, тобто список для вершини 5, починається з позиції І Р(5) = 7. Таким чином, з вершиною 4 суміжні вершини 1 і 3. Список для вершини 2 порожній, оскільки значення покажчиків І Р(2) та І Р(3) збігаються. У кінець масиву І Р включено додатковий покажчик; він є першою вільною позицією масиву l і s t. Цей прийом є зручним у програмній реалізації. Неорієнтований граф (рис. 1.7 а) представляє наступна структура суміжності: позиція =
id: 7
Обнаружен Плагиат: 0,13%https://dspace.sfa.org.ua/bitstream/1… + 13 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,8%
https://knowledge.allbest.ru/progra…
0,5%
https://poemanalysis.com/nursery-…
0,3%
https://web.kpi.kharkov.ua/apm/wp…
0,3%
https://web-crawler.plagiarism-dete…
0,2%
https://web-crawler.plagiarism-dete…
0,1%
http://freetutor.com.ua/Math/Sets_a…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
https://www.bbc.co.uk/teach/schoo…
0,1%
https://web-crawler.plagiarism-dete…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 20 l і s t = 2 3 4 5 1 5 1 4 5 1 3 1 2 3
І Р = 1 5 7 10 12 15 Рис. 1.9. Структура суміжності неорієнтованого графа Кожне ребро представлене двічі. Компактне зберігання списків суміжності ідентично малої схеми зберігання портрета розрідженої матриці, асоційованої з цим графом [26]. При використанні цього типу зберігання може бути зручним зв'язати обидві копії ребра за допомогою додаткового масиву. Так, якщо те саме ребро зберігається в позиціях і і j масиву l і s t, то l і n k(і) = j і l і n k(j) = і. Недолік компактного зберігання структури суміжності в тому, що важко додавати та виключати ребра. Ці труднощі долаються, якщо зберігати структуру суміжності як безліч зв'язкових списків, лінійних чи кільцевих, разом із масивом І Р покажчиків входу кожен список [43]. Серед списків зазвичай існують такі що перетинаються, тому неможливе застосування техніки зберігання, яка описувалася в § 1.3, і потрібен додатковий масив n е х t. Використовуючи кільцеві списки, орієнтований граф (рис. 1.7, б) можна подати так (несуттєві позиції позначені символом х): позиція = 1 2 3 4 5 6 7 8 9 l і s t = 3 5 1 2 �� 5 1 �� 2 n е х t = 3 7 1 6 �� 4 2 �� 9 І Р = 4 0 7 3 9 Рис. 1.10. Орієнтований граф у кільцевому списку Зв'язне подання неорієнтованого графа (рис. 1.7, а) може бути подане таким чином: позиція =
id: 8
Обнаружен Плагиат: 0,13%https://dspace.sfa.org.ua/bitstream/1… + 5 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,3%
https://web-crawler.plagiarism-dete…
0,3%
https://dl.sumdu.edu.ua/courseboo…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 l і s t = 5 �� 5 1 4 �� 3 5 2 2 1 1 4 3 1
3 �� n е х t = 4 �� 13 1 14 �� 11 5 12 8 7 16 15 10 3 9 �� І Р = 8 4 13 11 9 Рис. 1.11. Неорієнтований граф у кільцевому списку 21 Кожне ребро зберігається двічі. Наприклад, ребро (1,5) зберігається в позиціях 8 і 12 спочатку як (1, 5), потім як (5, 1). Як зазначено вище, для зв'язування обох копій кожного ребра можна використовувати масив (l і n k). Якщо з неорієнтованого графа необхідно зробити видалення ребра, то у цьому випадку можна скористатися двонаправленим списком. У всіх випадках вільні позиції можуть бути пов'язані між собою з метою подальшого використання. Ще одна поширена схема зберігання - це таблиця зв'язків [45]. Якщо граф має n вершин і m - максимальна ступінь вершини (тобто число суміжних з нею вершин), то таблиця зв'язків є масивом з n рядків і m стовпців; при цьому в 1-му рядку зберігається список суміжності вершини І. Для графа на рис. 1.7 (б) таблиця зв'язків складається з 5 рядків та двох стовпців: 2 5     0 0     1 5   1 3     2 0   Для представлення графа можна використовувати матрицю суміжності [26]. Для графа з n вершинами матриця суміжності - це квадратна матриця А а  1 порядку n, яка визначається таким чином: тоді і лише тоді, коли (і, j) і j а  0 - ребро даного графа; в іншому випадку . Матриця суміжності для і j графа на рис. 1.7 (б) має вигляд
id: 9
Обнаружен Плагиат: 0,15%https://dspace.sfa.org.ua/bitstream/1… + 10 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,3%
https://djvu.online/file/QBjLFvddnjo…
0,3%
https://dl.sumdu.edu.ua/courseboo…
0,3%
https://web-crawler.plagiarism-dete…
0,2%
https://tk.znu.edu.ua/nmk/Lec_vm_…
0,2%
https://www.netspotapp.com/blog/ip…
0,1%
https://matryza.blogspot.com/2015…
0,1%
https://routerhax.com/10.0.0.1/
0 1 0 0 1     0 0 0 0 0     1 0 0 0 1   1 0 1 0 0     0 1 0 0 0
  Матриця суміжності неорієнтованого графа симетрична. Цей тип зберігання не є неекономічним, якщо матриця повністю записується в 22 пам’ять машини. Але він може бути зручний для алгоритмів, яким часто потрібна інформація про наявність чи відсутність будь-яких ребер. Матрицю суміжності можна зберігати і як розріджену матрицю, наприклад, рядками, не запам'ятовуючи числові значення її елементів. І тут вийде компактна схема зберігання структури суміжності. Кліка - це граф, у якому кожна пара вершин з'єднана ребром. Для завдання кліки достатньо зберігати список посилань на її вершини, і немає потреби запам'ятовувати будь-яку інформацію про її ребра. Ця властивість знайшла важливе застосування у гауссовому виключенні [29]. 1.5. Схеми зберігання матриць великої розмірності З стрічковими матрицями пов'язана найпростіша стратегія використання нульових елементів матриці. Матрицю А називають стрічковою, якщо її ненульові елементи укладені всередині стрічки, утвореної діагоналями, паралельними головній діагоналі. Таким чином, а  0 а  0 а  0 і  j  якщо та або хоч би для одного k , k  k , k  і j 2 1  значення k. Тут – півширина, а – ширина стрічки. Стрічкою матриці і  j  А називається безліч елементів, для яких . Іншими словами, для і будь-якого рядка стрічці належать всі елементи зі стовпцевими індексами і  і  2 1 від до , тобто елементів. Це число може бути набагато менше порядку матриці [64]. Якщо матриця симетрична, достатньо зберігати її напівстрічку. Верхня напівстрічка складається з елементів, що знаходяться у верхній частині 0  j  і  стрічки, тобто таких, що ; нижня напівстрічка складається з 0  і  j  елементів нижньої частини стрічки, тобто таких, що ; в обох  випадках у рядку елементів. 23 1 1         2 8 9 0 2         8 5 0 8 3     А  А N ( І , J )  9 4 10 9 0 4         10 5 11 12 0 10 5     11 6 0 11 6         12 7 12 0 7     (а) (б) Рис. 1.12. Симетрична стрічкова матриця 7х7 з шириною стрічки 5 (а); діагональна схема зберігання в прямокутному масиві А N(І,J) (б) Діагональна схема зберігання симетричної стрічкової матриці за А N (і , j ) допомогою масиву представлена на рис. 1.12. Для матриці порядку n  ( 1)  n та півширини стрічки масив має розміри . Головна діагональ зберігається в останньому стовпці, а нижні кодіагоналі - в інших стовпцях зі зсувом на одну позицію вниз при кожному зміщенні вліво. У цьому прикладі   2 n  7 , . Для масиву необхідно 21 осередок пам'яті. Для несиметричної n  (2 1) матриці А необхідний масив розміром ; нижня напівстрічка і головна діагональ зберігаються як і раніше, а верхні кодіагоналі – у правій частині масиву зі зсувом однією позицію вгору при кожному зміщенні  n вправо. Діагональна схема зручна, якщо . Вона є схемою прямого доступу в тому сенсі, що є проста взаємно однозначна відповідність між а положенням елемента в матриці А та її положенням у масиві: і j А N (і, j  і  1) зберігається компонентом . У стрічкових матрицях ширина стрічки залежить від порядку, в якому розташовані рядки та стовпці. Тому можна шукати перестановки рядків та стовпців, що призводять до зменшення ширини стрічки. Мінімальна ширина стрічки означає зниження запитів до пам'яті; у обчисленнях, пов'язаних із матрицями, вона зазвичай зменшує і роботу. У разі симетричної матриці 24 цінна властивість симетрії буде збережена, якщо для стовпців і рядків використовуються однакові перестановки [45]. Якщо система лінійних рівнянь має стрічкову матрицю коефіцієнтів і вирішується за допомогою гауссового виключення, причому головні елементи вибираються на головній діагоналі, вся арифметика обмежена стрічкою, поза якою ніяких нових ненульових елементів не виникає. Гауссовий виняток можна проводити на місці, оскільки для будь-якого ненульового елемента, якщо він з'явиться, вже зарезервована позиція у схемі зберігання. Власні значення і власні вектори стрічкової матриці, а також власні значення і власні вектори узагальненої спектральної задачі з двома стрічковими матрицями однакової ширини, можна обчислити, не використовуючи додаткову пам'ять [21]. Стрічкова матриця високого порядку може мати широку стрічку з великою кількістю нулів. Для такої матриці діагональна схема не є неекономним рішенням. У цьому випадку оптимальним є застосування схеми, яка називається профільною схемою, або схемою змінної стрічки. Для і кожного рядка симетричної матриці А буде   і  j (і ) і m і n а  0 j (і ) і де - мінімальний стовпцевий індекс рядка , для якого . і j m і n і Таким чином, перший ненульовий елемент рядка знаходиться на позиції m а х(  )  ліворуч від головної діагоналі. Певна півширина стрічки є . і а 0  і  j  Оболонка матриці А - це безліч елементів для яких . У і j і і рядку оболонці належать всі елементи зі стовпцевими індексами від j (і ) і  1  до , всього елементів. Діагональні елементи не входять до m і n і оболонки. Профіль матриці А визначається як кількість елементів в оболонці: р r о f і l е(А)  β  і і 25 При використанні профільної схеми всі елементи оболонки, впорядковані рядками, зберігаються, включаючи нулі, в одновимірному масиві (А N) [54]. Діагональний елемент даного рядка поміщається у його кінець. Довжина масиву А N дорівнює сумі профілю та порядку А. Необхідний ще масив покажчиків (І А); елементи цього масиву вказують на і  1 і розташування діагональних елементів А N. Так, при елементи рядка а І А(і ) І А(і  1 )  1 знаходяться в позиціях від до . Єдиний елемент 1-го 11 А N (1) рядка зберігається у . Елементи мають послідовні стовпцеві індекси, що легко обчислюються. Наприклад, для матриці на рис. 1.12 (а) профіль дорівнює 7, а профільна схема виглядає так: позиція =
id: 10
Обнаружен Плагиат: 0,14%https://www.geeksforgeeks.org/minim…
1%
https://www.geeksforgeeks.org/min…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 ���� = 1 2 8 3 9 0 4 10 5 11 6 12 0 7 ���� = 1 2 4 7
9 11 14 Рис. 1.13. Профільна схема зберігання Можливий варіант профільної схеми із зберіганням оболонки по стовпчикам. І тут стовпці матриці зберігають свої довжини, цю схему часто називають вертикальної. Ще одне з понять, яке використовується при конструюванні схем зберігання симетричних матриць можна виділити при j , j  і і розгляді рядка матриці А. Кажуть, що стовпець активний у цьому і рядку, якщо він містить ненульовий елемент у рядку або вище за неї. m а х   і Нехай , - Число стовпців, активних у рядку . Тоді , - називають і і хвильовим фронтом або шириною фронту А. У прикладі (рис. 1.12, а) стовпець 4 активний у рядку 3, а ширина фронту А дорівнює 2. Як і у разі стрічкових матриць, профіль зазвичай змінюється при перестановках рядків та стовпців. Менший профіль означає меншу пам'ять і менше операцій у обчисленнях, виконуваних з матрицею, тому алгоритми мінімізації профілю відіграють важливу роль технології розріджених матриць [45]. 26 Розглядаючи елементи, укладені в оболонці, можна виявити, що у  гауссовому винятку значення кожного рядка не зміниться, якщо головні і елементи вибирати на головній діагоналі. Нові ненульові елементи не можуть виникнути у позиціях, зовнішніх для оболонки. Вони можуть з'явитися всередині оболонки, де їм вже виділено місце; звідси випливає, що виняток можна проводити за статичної схеми зберігання. Профільну схему можна з вигодою використовувати і в інших випадках. Наприклад, вона добре пристосована для ітераційних алгоритмів, де потрібна ефективність при обчисленні добутків матриці на вектори. До цієї категорії належать алгоритми Ланцоша та сполучених градієнтів. У цьому контексті поняття оболонки можна поширити на несиметричні матриці [34]. Схема змінної стрічки рядково орієнтована, будь-який рядок матриці в цьому випадку сканується ефективно; в той же час, сканування стовпців буде неефективним. Крім того, схема є статичною, тому що включення нового елемента, що лежить поза оболонкою, вимагає зміни всієї структури (якщо тільки не використовуються записи змінної довжини) [36]. Вище описані схеми зберігання матриць дають високу ефективність у багатьох важливих практичних додатках. Розріджена матриця А, яку можна переупорядкувати так, щоб вона мала вузьку стрічку або малу оболонку, вимагає набагато меншої пам'яті, ніж при зберіганні у двовимірному масиві, як це реалізовано для щільних матриць. Нулі, що знаходяться всередині стрічки або оболонки, зберігатимуться і беруть участь в операціях (або принаймні у перевірках на нульове значення), простота, властива цим схемам і пов'язаному з ними програмуванню, може значно переважити цю незручність. Порівняння двох методів зберігання показує, що при використанні профільної схеми зберігається менше нулів; ціна, яку доводиться платити за це зменшення, – необхідність мати додатковий масив, що містить допоміжну інформацію, і внаслідок цього збільшується складність програми. 27 Труднощі реалізації і накладна пам'ять зростають паралельно з ускладненням схеми зберігання. Високо складні схеми вимагають професійної програмної реалізації, інакше їх потенційні переваги будуть втрачені [45]. З цього погляду проста схема може бути більш підходящою для завдання малого або середнього розміру. З іншого боку, можливість застосування високо складної схеми може визначати, чи можна вирішити взагалі велике завдання на даній машині. Нижче представлені схеми, в яких нулі не зберігаються або зберігаються тільки деякі нулі. Розглянемо розріджену матрицю А; без втрати спільності припустимо, що А є матрицею великої розмірності. Її ненульові елементи, які представлені в малій кількості порівняно з числом нулів, розпорошені по всій матриці, утворюючи портрет матриці або шаблон нулів – не нулів. 6     9 4 7   А    5   2 8   Однією зі схем, що дозволяє зберігати не нульові елементи в компактній формі і в довільному порядку в одновимірному масиві (А N) є схема Д. Кнута. Інформація про положення ненульових елементів може зберігатися двома додатковими паралельними одновимірними масивами (І та J); В даному випадку для кожного ненульового елемента містяться його а  0 рядковий та стовпцевий індекси. Так, для кожного у пам'яті і j а , і, j знаходиться . Далі, для того щоб проводити швидкий пошук і j елементів довільного рядка або стовпця матриці, необхідна пара покажчиків а , і, j для кожної , а також покажчики входу для рядків і стовпців, що і j повідомляють початок кожного рядкового або стовпцевого списку. Нехай N R - масив, що зберігає малі покажчики, а N С - масив стовпцевих покажчиків. 28 Масиви А N, І, J, N R, N С мають однакову довжину, та їх однойменні позиції відповідають одна одній. Нехай J R і J С – масиви містять покажчики входу для рядків та стовпців розташовані відповідно до порядку рядків та стовпців матриці. Нижче представлена матриця А, що зберігається згідно зі схемою Кнута.
id: 11
Обнаружен Плагиат: 0,16%https://dspace.hnpu.edu.ua/bitstream… + 2 ресурсов!
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0%
https://web-crawler.plagiarism-dete…
1 2 3 4 5 6 7 А N  6 9 4 7 5 2 8 І  1 2 2 2 3 4 4 J  2 1 2 4 1 2 4 N R  0 3 4 0 0
7 0 N С  3 5 6 7 0 0 0 J R  1 2 5 6 J С  2 1 0 4 Рис. 1.14. Схема зберігання Д. Кнута Якщо необхідно, наприклад, елементи 2-го стовпця, то, визначивши, що J С(2) = 1. потрібно почати з 1 позиції масивів А N, І і N С. Так як А N(1) = 6. і І (1) = 1, то елемент 6. знаходиться у 2-му стовпці, 1-му рядку. Оскільки N С(1) = 3, переходимо в позицію 3 і знаходимо елемент 4 у 2-му рядку. Визначивши, що N С(3) = 6, переходимо у позицію 6 і знаходимо елемент 2. у 4-му рядку. Більше елементів у 2-му стовпці немає, тому що N С(6) = 0. Також слід зазначити, що J С(3) = 0; це означає, що третій стовпець порожній. а При користуванні даною схемою елемент можна знайти, тільки входячи і j і до списку рядка і переглядаючи його до тих пір, поки не буде знайдено j стовпцевий індекс [45]. Схема Кнута вимагає п'яти клітинок пам'яті для кожного ненульового елемента А та наявності покажчиків входу для рядків та стовпців. Внаслідок великої накладної пам'яті така схема неекономна. Переваги її в тому, що будь-де можна включити або виключити елемент, і можна ефективно сканувати рядки і стовпці. Для цього використовується описана в § 1.2 29 техніка обробки зв'язкових списків. Записи, що мають фіксовану довжину, можуть бути розміщені в довільних сферах фізичної пам'яті і потім пов'язані між собою; вільні записи також зв'язуються для подальшого використання. Схема пристосована для випадків, коли матриця А будується алгоритмом, у якому не можна передбачити кінцеве число та позиції ненульових елементів. Найважливішим прикладом такого алгоритму є гауссовий виняток для матриць загального виду [30]. Існує модифікація схеми Кнута, яка зберігає її цінні властивості, і дозволяє використовувати значно менше накладної пам'яті. Ця модифікація називається схемою Кнута-Рейн-болдта-Містеньї або кільцевою КРМ- схемою. Зв'язкові списки рядків і стовпців закільцьовуються, а початкові позиції списків входять у покажчики входу. Списки, асоційовані з рядками (стовпцями), попарно не перетинаються тому можуть спільно зберігатися одним масивом N R (для стовпців N С). Нижче наведено приклад кільцевої КРМ-схеми:
id: 12
Обнаружен Плагиат: 0,16%https://dspace.sfa.org.ua/bitstream/1… + 2 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
0,8%
https://knowledge.allbest.ru/progra…
1 2 3 4 5 6 7 А N  6 9 4 7 5 2 8 N R  1 3 4 2 5 7 6 N С  3 5 6 7 2 1 4 J R  1 2 5 6
J С  2 1 0 4 Рис. 1.15. Кільцева КРМ-схема Подана схема більш щільна, порівняно зі схемою Кнута. Однак якщо необхідно переглядати елементи деякого рядка (або стовпця), то не можна отримати інформацію про стовпцеві (маленькі) індекси цих елементів. Для а і того щоб знайти елемент спочатку необхідно зробити сканування -й і j S рядка і визначити множину , яка є позицією елементів рядка в масиві А N: і �� = {��|А N(��) є елемент ��-й рядка} �� 30 Мається на увазі, що повторення відсутні, тобто кожній парі р, q рядкового і стовпцевого індексів відповідає найбільш одна позиція в j кожному з масивів А N, N R і N С. Далі скануванням -го стовпцевого списку j визначається безліч позицій масиву А N, де зберігаються елементи -го S  S  S S стовпця [45]. Після чого необхідно знайти , є порожнім, і j і j і j S S а або містить тільки один елемент. Якщо порожнє, то . Якщо і j і j і j а  А N(k) містить одне число, припустимо, k , то . Зворотнє завдання, і j тобто за заданою позицією k в А N знайти відповідні рядковий і стовпцевий j і індекси та має рішення тільки у разі перегляду всієї матриці. Нижче наведено варіант КРМ-схеми, що дозволяє шукати необхідні індекси.
id: 13
Обнаружен Плагиат: 0,19%https://dspace.sfa.org.ua/bitstream/1… + 2 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
0,8%
https://knowledge.allbest.ru/progra…
1 2 3 4 5 6 7 А N  6 9 4 7 5 2 8 N R   1 3 4  2  3 7  4 V С  3 5 6 7  1  2  4 J R  1 2 5 6
J С  2 1 0 4 Рис. 1.16. Модифікована КРМ-схема Вказівники входу для рядків та стовпців включаються до відповідних кільцевих списків. І тому існує кілька способів; ілюстрований вище спосіб, використовує негативні числа посилань на покажчики входу рядків і стовпців. У цій схемі достатньо переглядати ряд доти, доки не буде знайдено негативне посилання. Абсолютна її величина є номером ряду; в той же час вона відсилає до відповідного покажчика входу, тому перегляд ряду при необхідності може продовжуватися. Припустимо, необхідно знайти рядковий індекс елемента А N(3). Так як N R(3) = 4 і N R(4) = -2, то шуканий індекс дорівнює 2. Крім того, J R(2) = 2, тому А N(2) містить наступний елемент 2-го а рядка. Щоб знайти в масиві А N елемент можна застосувати описану і j 31 і вище процедуру. Інша можливість полягає в тому, щоб переглянути рядок і знайти стовпцевий індекс кожного елемента, скануючи відповідні стовпцеві j списки, поки не зустрінеться . Існує ще один варіант схеми Кнута він використовується для зберігання симетричних позитивно визначених матриць, елементами яких можуть бути як числа, так і підматриці. Називається ця схема вперед рядком - назад по стовпцю. Зберігаються тільки діагональ та верхній трикутник матриці; потрібний лише один масив покажчиків входу, які відсилають до діагональних елементів [54]. А А А   11 13 14   А А 22 25     А А 33 35   А 44     А 55   Рис. 1.17. Модифікація схеми Кнута для зберігання симетричних матриць з ненульовими діагональними елементами Від кожного діагонального елемента починаються два списки: один описує частину відповідного рядка праворуч від діагоналі і проходить у прямому напрямку, інший описує частину відповідного стовпця над діагоналлю і проходить у зворотному напрямку, тобто знизу вгору. Це пояснює назву схеми. Приклад показано на рис. 1.17. Ідею схеми досить легко поширити на матриці загального вигляду. Якщо є діагональ з ненульових елементів, то від кожного діагонального елемента можуть 32 починатися чотири списки. З іншого боку, може вистачити двох неупорядкованих списків: оскільки, під час роботи з розрідженими матрицями впорядковані представлення не завжди бажані [14]. Одна зі схем зберігання розріджених матриць, що найбільш широко використовуються, являє собою розріджено малий формат. Ця схема пред'являє мінімальні вимоги до пам'яті і водночас є зручною для кількох важливих операцій над розрідженими матрицями: додавання, множення, перестановок рядків і стовпців, транспонування, рішення лінійних систем з розрідженими матрицями коефіцієнтів як прямими, так і ітераційними методами та іншими. Значення ненульових елементів матриці та відповідні стовпцеві індекси зберігаються у цій схемі по рядках у двох масивах; назвемо їх відповідно А N та J А. Використовується також масив покажчиків (І А), що відзначає позиції масивів А N та J А, з яких починається опис чергового рядка. Додаткова компонента в І А містить покажчик першої вільної позиції J А і А N. Нижче наведено приклад розрідженого рядкового зберігання для матриці А.
id: 14
Обнаружен Плагиат: 0,21%https://dspace.sfa.org.ua/bitstream/1… + 9 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,8%
https://knowledge.allbest.ru/progra…
0,3%
https://web.kpi.kharkov.ua/apm/wp…
0,3%
https://dl.sumdu.edu.ua/courseboo…
0,3%
https://djvu.online/file/QBjLFvddnjo…
0,3%
https://web-crawler.plagiarism-dete…
0,2%
https://tk.znu.edu.ua/nmk/Lec_vm_…
0 0 1 3 0 0 0 5 0 0     А  0 0 0 0 0 0 0 0 0 0     0 0 0 0 0 7 0 1 0 0   Матриця А представляється так: позиція = 1 2 3 4 5 6
І А = 1 4 4 6 J А = 3 4 8 6 8 А N = 1 3 5 7 1 Рис. 1.18. Розріджений малий формат Опис 1-го рядка матриці починається з позиції І А(1) = 1 масивів А N та JА. Оскільки опис 2-го рядка починається з І А(2) = 4, це означає, що 1-му рядку в А N і J А відповідають позиції 1, 2 і 3. Наведеному прикладі І А(1) = 1 перший рядок починається з J А(1) ) та А N(1). ІА(2) = 4 другий рядок починається з J А(4) та А N(4). І А(3) = 4 третій рядок починається з J А(4) та 33 А N(4). Оскільки це ті ж позиції, з яких починається другий рядок, це означає, що 2-й рядок порожній. І А(4) = 6 це перша вільна позиція у J А та А N. Таким чином, опис 3-го рядка закінчується в позиції 6 - 1 = 5 масивів J А та А N. У загальному випадку опис r-го рядка матриці А зберігається в позиціях з І А(r) до І А(r + 1) – 1 масивів J А та А N, за винятком рівності І А(r + 1) = І А(r), що означає, що r-й рядок порожній. Якщо матриця має m рядків, то І А містить m + 1 позицій. Даний спосіб подання називають повним, оскільки представлена вся матриця А, і впорядкованим, оскільки елементи кожного рядка зберігаються відповідно до зростання стовпцевих індексів. Таким чином, це рядкове подання, повне та впорядковане, або скорочено R R(С)О [26]. Масиви І А і JА представляють портрет матриці А, що задається як безліч списків суміжності асоційованого з графом матриці А. Якщо в алгоритмі розмежовані етапи символічної обробки та чисельної обробки, то масиви І А і J А заповнюються на першому етапі, а масив А N – на другому. Існує ще один варіант малої схеми зберігання, орієнтований для додатків, де доводиться виконувати операції і над рядками, і над стовпцями. Матриця А зберігається рядками, як описано вище; крім того, визначають Т Т А А портрет і зберігають по рядках. Термінове уявлення портрета рівносильне стовпцевому уявленню портрета А. Його можна отримати транспонуванням рядкового портрета А. Ця схема застосовувалася під час вирішення завдань лінійного програмування [26]. Для несиметричних матриць була запропонована інша, спрощена рядкова схема [45]. Ненульові елементи зберігають у двовимірному масиві з n  m розмірами , де n – порядок матриці, m – максимальна кількість ненульових елементів у рядку. Ця схема припускає просту обробку; недолік її в тому, що m може бути невідомо заздалегідь або виявитися занадто великим. 34 Ще одним із варіантів схем зберігання матриць великої розмірності є блокова схема зберігання. Метод розбиття великої матриці на підматриці чи блоки виникає природним чином. З блоками можна поводитися, ніби вони були елементами матриці, і блокова матриця перетворюється на матрицю з матриць. Розбиття на блоки грає важливу роль технології розріджених матриць, оскільки багато алгоритмів, сконструйовані спочатку для числових матриць, можна узагальнити у разі матриць з матриць. Велика гнучкість, що з поняттям розбиття, може давати певні обчислювальні переваги. З іншого боку, розбиття можна розглядати просто як інструмент управління даними, що допомагає організувати обмін інформацією між оперативною пам'яттю і зовнішніми пристроями, що запам'ятовують. Розбиття рядків і стовпців може бути однаковим, але якщо вони однакові, то діагональні блоки квадратні. Зберігання блочної матриці має на увазі зберігання множини її підматриць [38]. Розглянемо неявну схему зберігання, призначену головним чином для симетричних матриць з квадратними діагональними блоками. Діагональні блоки розглядаються так, ніби вони становили єдину матрицю, і зберігаються відповідно до профільної схеми. Чисельні значення елементів зберігаються рядками в масиві А N, а покажчики на діагональні елементи кожного рядка – загалом в масиві І А. Піддіагональні блоки, що розглядаються так, як якщо б вони становили єдину матрицю, зберігаються за допомогою розрідженого рядкового формату. Ненульові елементи розміщуються по рядках у дійсному масиві АР, а відповідні стовпцеві індекси – у паралельному масиві J А. Покажчики початку рядків в АР та J А зберігаються у масиві І Р; в останній для зручності програмної реалізації включений додатковий покажчик першої вільної позиції в АР та J А. Саме розбиття визначається номерами перших рядків кожного блоку, що зберігаються в L Р, де також є додаткова компонента. Масив L Р можна використовувати разом із масивами І А та І Р. Ця гібридна схема зберігання успішно застосовувалася для гауссового виключення у 35 комбінації з такими алгоритмами впорядкування, як деревоподібне розбиття та перерізи [26]. Нижче наведено приклад симетричної блокової матриці А. Рядки та стовпці матриці А згруповані в підмножини (1, 2, 3, 4), (5, 6, 7) та (8, 9, 10). 1 3 | 17 |     2 4 6 | | 21     3 4 5 | 18 | 24   6 7 | 19 20 |         |    |      17 | 8 10 | 23   А    18 19 | 9 | 22   20 | 10 11 | 25         |    |        21 | 22 | 12 13 15   | 23 | 13 14     24 | 25 | 15 16   В результаті матриця розділилася на 9 блоків. Діагональні блоки квадратні, тому що рядки та стовпці розбивалися однаковим чином. На рис. 1.19 показано відповідну неявну схему зберігання матриці А. позиція =
id: 15
Обнаружен Плагиат: 0,25%https://dspace.sfa.org.ua/bitstream/1… + 17 ресурсов!
2%
https://dspace.sfa.org.ua/bitstream…
1%
https://www.geeksforgeeks.org/min…
0,8%
https://dspace.hnpu.edu.ua/bitstrea…
0,8%
https://knowledge.allbest.ru/progra…
0,5%
https://poemanalysis.com/nursery-…
0,3%
https://dl.sumdu.edu.ua/courseboo…
0,3%
https://web.kpi.kharkov.ua/apm/wp…
0,3%
https://web-crawler.plagiarism-dete…
0,2%
https://web-crawler.plagiarism-dete…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
http://freetutor.com.ua/Math/Sets_a…
0,1%
https://www.bbc.co.uk/teach/schoo…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
https://web-crawler.plagiarism-dete…
0,1%
https://web-crawler.plagiarism-dete…
0%
https://ukrayinska.libretexts.org/Ма…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 А N = 1 2 3 4 5 6 0 7 8 9 10 0 11 12 13 14 15 0 16 І А = 1 2 5 8 9 10 13 14 16 19 А Р = 17 18 19 20 21 22 23 24 25
J А = 1 3 4 4 2 6 5 3 7 І Р = 1 1 1 1 1 2 4 5 7 8 10 L Р = 1 5 8 11 Рис. 1.19. Неявна схема зберігання блокової матриці Інша схема зберігання блокових матриць, звана блок усередині блокового стовпця [54]. Вона особливо підходить для методів перерізів. Діагональні блоки зберігаються як колись, а піддіагональні блоки трактуються як блокові стовпці. В результаті перерізів ненульові елементи кожного блокового стовпця групуються в блоки. Ці блоки зберігаються 36 послідовно в дійсному масиві разом з інформацією про початок кожного блоку і блоковий стовпчик, якому належить даний блок. Гіперматрична схема виходить, якщо матриця А зберігається як матриця, елементами якої є матриці [32]. Для зберігання матриці можна використовувати будь-яку з представлених схем зберігання; відмінність буде тільки в тому, що замість чисельних значень елементів потрібно зберігати інформацію про розташування та розміри підматриць. Самі підматриці, елементами яких будуть числа, зберігаються відповідно до деякого стандартного формату. У випадку, коли матриця А, розріджена можна використовувати розріджене подання, що зберігається в оперативній пам'яті, в той час як підматриці, так само як у деякому розрідженому поданні, розміщуються в периферійній пам'яті і вносяться в оперативну тільки тоді, коли цього вимагає виконання алгоритму. Такий варіант називається понад розрідженою схемою [54]. Всі гіперматричні схеми зберігання дозволяють проводити обробку великих завдань за помірних запитів до пам'яті. Їхня головна перевага полягає в легкості, з якою користувач може зменшити пам'ять або час (ціною збільшення іншої з цих характеристик), для чого достатньо, в залежності від наявної пам'яті, задати більш дрібне або грубіше розбиття. Ця техніка успішно використовувалася в гауссовому виключенні та при вирішенні спектральних завдань. Вона передбачає, що з розріджених матриць (прямокутних, квадратних і трикутних) і векторів ефективно реалізовані такі операції, як додавання, множення, перестановки, і навіть факторизація квадратних діагональних блоків. 1.6. Символічна обробка та динамічні схеми зберігання Алгоритм для розріджених матриць може породжувати нові ненульові елементи та змінювати значення тих, що вже є в даній матриці; або він може користуватися цією матрицею, не змінюючи її, як у випадку ітераційних алгоритмів, яким потрібні лише добутки матриці з векторами. Безліч нових ненульових елементів, що додаються до вже існуючої розрідженої матриці, називається заповненням. Алгоритм може будувати і зовсім нову матрицю, 37 але концептуально це рівнозначно генеруванню ненульових елементів спочатку нульової матриці. Перш ніж розпочнеться виконання такого алгоритму, необхідно переконатися, що в пам'яті є місце для нових елементів. Повинні бути встановлені закони управління пам'яттю, що визначають внутрішнє подання даних, або структуру даних; від них залежить, де і як зберігатиметься кожен новий елемент. Для структури даних є вибір: вона може бути сформована до того, як почнеться чисельна обробка, або будуватися паралельно з обробкою відповідно до потоку елементів, що обчислюються. Структура даних, заготовлена до початку чисельної обробки, називається статичною структурою [55]. Її формування вимагає знання числа ненульових елементів та його становища в матриці ще до того, як вони реально обчислені. Ряд матричних алгоритмів дозволяє передбачення необхідної інформації. У цю категорію потрапляють додавання та множення матриць, а також гауссовий виняток, коли послідовність головних елементів відома, як буде у разі симетричних позитивно визначених матриць. Кожен такий алгоритм природно розпадається на дві частини: символічну частину, де виконується символічна обробка чи розподіл пам'яті, чи формування структури даних, і чисельну частину, де виконуються реальні обчислення чи чисельна обробка. Результат символічного етапу – статична структура даних; результат чисельного етапу – значення ненульових елементів, розміщених у клітинках пам'яті, які були заготовлені на символічному етапі [26]. Деякі статичні схеми деяких конкретних додатків можуть вимагати явного символічного етапу. Стрічкові та профільні схеми були сконструйовані таким чином, що гауссовий виняток з вибором головних елементів на діагоналі може породжувати ненульові елементи лише всередині стрічки або оболонки; отже, ці схеми є потрібними статичними структурами. Те саме справедливо при приведенні стрічкової матриці до тридіагонального виду в ході вирішення спектральних завдань; але до профільної схеми зберігання це стосується. Додавання двох матриць з 38 однаковою стрічкою або оболонкою зберігає стрічку або оболонку, але множення двох стрічкових матриць розширює стрічку. Якщо гауссовий виняток проводиться для стрічкової матриці і при виборі головного елемента допускаються тільки перестановки рядків, то нижня напівстрічка зберігається, а верхня півстрічка може в гіршому випадку подвоїти ширину [2]. З іншого боку, використання методу такого алгоритму мінімізації стрічки або профілю повинно розглядатися як символічний етап; так як такі алгоритми лише розподіляють пам'ять, маючи на увазі її зменшення та відповідне зменшення роботи, але не знаходять жодних чисельних результатів. До тієї ж категорії належать деякі інші методи – перерізи, деревоподібне розбиття, блочна тріангуляризація. Якщо матриця зберігається в розрідженому рядковому форматі, необхідним символічним етапом буде обчислення портрета матриці. Статичні схеми заохочують модульність, оскільки символічний та чисельний етапи виконуються окремо і, отже, можуть бути оптимізовані незалежно. Що стосується прямих методів для лінійних систем існують ефективні процедури, що дозволяють виконувати символічний етап набагато швидше, ніж чисельний. Вони використовують фіксовану пам'ять, яка лише трохи перевищує ту, що потрібно для зберігання матриці, проте дають суттєву для користувача інформацію: кількість пам'яті і обчислювальної роботи, необхідні для чисельного етапу. Ще одна важлива перевага модульності виявляється у додатках, що вимагають повторного використання даного алгоритму при різних чисельних значеннях. Прикладами можуть служити ітераційні методи, які потребують вирішення багатьох лінійних систем з однією і тією ж матрицею та різними правими частинами, або з матрицями, що мають (при різних чисельних значеннях) однаковий портрет. У таких випадках символічний етап може бути проведений лише один раз, і у всіх наступних обчисленнях може використовуватися та сама статична структура даних. 39 Статичні структури даних можуть застосовуватися не завжди. Найпомітнішим винятком є метод Гаусса із вибором головного елемента для матриць загального виду [45]. Щоб запобігти сильному зростанню помилок, основні елементи вибираються під час винятку відповідно до їх чисельних значень; при цьому використовуються такі стратегії вибору головного елемента, як повний вибір, частковий вибір або вибір бар'єру. Вибір головних елементів рівносильний перестановкам рядків і стовпців, які у свою чергу впливають на розташування заповнення, що виходить. Наслідком цього є непередбачуваність портрета остаточної матриці, і рішення про те, де і як розмістити кожен новий ненульовий елемент, слід приймати, коли цей елемент вже обчислений і готовий до запису в пам`ять. Така процедура називається динамічним розподілом пам'яті та породжує динамічну структуру даних. Якщо гауссовий виняток проводити для стрічкової матриці загального вигляду і при виборі головного елемента користуватися лише перестановками рядків, то верхня напівстрічка подвоюється, а нижня не змінюється. Суворо кажучи, ця схема статична, оскільки може бути сформована заздалегідь. Вона має недолік, властивий кожній статичній схемі: у процесі виключення не можна заощадити пам'ять, необхідно зберігати та обробляти (або піддавати перевіркам) велику кількість нулів. Справді динамічні структури вимагають схем, які не залежать від статичного по суті характеру машинної пам'яті. Ця сильна вимога зазвичай задовольняється за допомогою ефективної системи зв'язок та покажчиків. Схема Кнута та КРМ-схема добре пристосовані для цієї мети. Кожен ненульовий елемент матриці має внутрішнє подання у вигляді запису фіксованої довжини, яка зберігається в довільному місці машинної пам'яті, а потім зв'язується з відповідними списками, малим і стовпцевим. Елементи можуть бути включені або виключені в будь-якій позиції матриці без переміщення інших даних, і коли алгоритм цього вимагатиме, можна переглядати як рядки, так і стовпці. 40 Для динамічного зберігання розріджених матриць [41] було запропоновано використовувати записи змінної довжини. Запис розуміється як двовимірний масив спеціального типу, в який можна динамічно додавати рядки і стовпцями якого можуть бути прості змінні різних типів. Рядки, що не використовуються, розпізнаються автоматично і при необхідності схема зберігання стискається. Не потрібно зберігати покажчики та зв'язки; також немає потреби у непрямій адресації. Зв'язкові списки формуються, якщо привласнити змінній, що зберігається в рядку, значення адреси наступного рядка. Вартість цього термінах накладної пам'яті рівнозначна використанню цілої змінної на рядок. Ця схема підтримується сучасними трансляторами; її застосування вимагає від транслятора здатності обробляти зв'язки та покажчики. Програма, що спирається на цю структуру даних, витримує порівняння з програмою, яка використовує впорядковані спискові схеми [45]. Висновки до першого розділу 1. Визначено основні критерії, які дозволяють ефективно зберігати та обробляти матриці великої розмірності. Такими критеріями є: а. зберігання тільки ненульових елементів матриці; b. оперування тільки з ненульовими елементами; с. збереження розрідженості матриці. 2. Проаналізовано зберігання масивів, списків, стеків та черг. Виділено різні схеми зберігання матриць на основі розглянутих структур. Визначено, що ефективність застосування різних схем зберігання залежить від операцій, які передбачаються в алгоритмі обробки. 3. Розглянуто діагональну схему зберігання стрічкової матриці. Визначено, що у стрічкових матрицях ширина стрічки залежить від порядку, в якому розташовані рядки та стовпці. Це дозволяє проводити пошук перестановок рядків і стовпців, що призводить до зменшення ширини стрічки. У свою чергу мала ширина стрічки призводить до зниження запитів до пам'яті, що збільшує швидкість роботи. 41 4. Розглянуто профільну схему зберігання симетричних матриць. Визначено, що одним із напрямків використання даної схеми зберігання є стрічкова матриця високого порядку з широкою стрічкою і великою кількістю нулів, оскільки використання діагональної схеми зберігання не є неекономним рішенням. 5. Проаналізовано зв'язкові схеми розрідженого зберігання та зберігання блокових матриць. Виявлено, що проблеми реалізації і накладна пам'ять зростають паралельно з ускладненням схеми зберігання. Високо складні схеми вимагають професійної програмної реалізації, інакше їх потенційні переваги будуть втрачені. Проста схема може бути ефективнішою для завдання малого або середнього розміру. З іншого боку, можливість застосування високо складної схеми може визначати, чи можна вирішити взагалі велике завдання на даній машині. 42 РОЗДІЛ 2. МАТЕМАТИЧНЕ ПРЕДСТАВЛЕННЯ МАТРИЧНИХ АЛГОРИТМІВ 2.1. Принципи побудови ітераційних процесів Основні ітераційні процеси для вирішення лінійних систем можуть бути описані за допомогою наступної загальної схеми. Нехай дана система лінійних рівнянь А х  b (2.1) (1) (2) ( k ) х , х ,..., х ,... з матрицею А. Будується послідовність векторів за рекурентними формулами (2.2) ( k ) ( k 1) ( k ) ( k 1) х  х  H (b  А х ) (0) (1) (2) х H , H де – деяка послідовність матриць, – початкове наближення. ( k ) H Різний вибір послідовності матриць призводить до різних ітераційних процесів [12]. Ітераційні процеси, що протікають за формулою (2.2), мають таку * х властивість, що для кожного з них точне рішення є нерухомою точкою. (0) * х х Це означає, що й за початкове наближення взято , всі наступні * х наближення також рівні . * х Зворотньо, будь-який ітераційний процес, для якого є нерухомою точкою, що протікає за формулою ( k ) (
id: 16
Обнаружен Плагиат: 0,74%https://www.chegg.com/homework-h… + 4 ресурсов!
0,6%
https://www.chegg.com/homework-…
0,4%
https://www.stumblingrobot.com/20…
0,2%
https://www.reddit.com/r/learnmath…
0%
https://math.stackexchange.com/qu…
k ) ( k 1) ( k ) х  С х  Z (2.3) ( k ) ( k ) С Z де послідовність матриць, послідовність векторів. Може * ( k ) * * * х  С х  Z х бути поданий у вигляді (2.2). Для маємо звідки ( k ) * ( k ) ( k 1) * ( k 1) ( k ) ( k 1) * х  х  С ( х  х )  х  (С  Е )( х  х )  ( k 1) ( k ) 1 * ( k 1) ( k 1) ( k ) ( k 1)  х  (Е  С ) А А( х  х )  х  H (b  А х ) при 43 ( k ) ( k ) 1 H  (Е  С ) А Неважко дати необхідні та достатні умови для того, щоб ітераційний процес (2.2) сходився до рішення за будь-якого початкового вектора. * ( k ) ( k ) ( k 1) (1) * (0) х  х  (Е  H А)(Е  H А)...(Е  H А)( х  х ) * ( k ) х  х  0 Для того, щоб при будь-якому початковому векторі (0) х необхідно і достатньо, щоб матриця ( k ) ( k ) ( k 1) (1
) T  (Е  H А)(Е  H А)...(Е  H А) прагнула до нуля, навіщо, своєю чергою, достатньо, щоб будь-яка ( k ) T матриця прагнула до нуля. Виділена умова дає лише загальну думку для побудови умов збіжності конкретних ітераційних процесів [26]. Найпростішими серед ітераційних процесів є стаціонарні процеси, в ( k ) ( k ) k H  Е H яких матриці не залежать від номера кроку . Зокрема, при виходить класичний процес послідовних наближень. Будь-який стаціонарний H  Е процес можна розглядати як процес послідовних наближень, H А Х  H b застосований до рівносильної системи , підготовленої до застосування методу послідовних наближень. Здійснювати таку підготовку зазвичай немає необхідності, і такого роду розгляд стаціонарних процесів лише дає зручний засіб для їхнього теоретичного дослідження. Близькими до ( k ) H стаціонарних ітераційних процесів є циклічні, в яких матриці періодично повторюються через кілька р кроків. З кожного циклічного процесу можна отримати рівносильний йому стаціонарний [20], приймаючи за один крок стаціонарного процесу результат застосування повного циклу р кроків вихідного циклічного процесу. Нестаціонарні ітераційні процеси, своєю чергою, можна поділити на два типи. 1. Нестаціонарні ітераційні процеси зі зміною матриці здійснюються на кожному кроці. 44 2. Стаціонарні процеси з прискоренням збіжності у вигляді заміни час H від часу стаціонарної матриці , що визначає процес, на деякі ( k ) H спеціальним чином підібрані, матриці . Вибір матриці для стаціонарного процесу і матриць для нестаціонарного може здійснюватися багатьма різними способами виходячи з різних принципів [34]. Можлива побудова матриць так, щоб ітераційний процес сходився до рішення для більш широкого класу систем рівнянь. Можлива протилежна точка зору, в силу якої при побудові матриць максимально використовуються приватні особливості даної системи для отримання ітераційного процесу, що має найшвидшу збіжність. Для застосування ітераційного процесу, побудованого виходячи з останнього принципу, потрібно мати більшу інформацію про матрицю коефіцієнтів системи, зокрема про розташування її власних значень. Важливим принципом побудови ітераційних процесів є принцип ( k ) H релаксації. Під цим принципом розуміють вибір матриць із деякого заздалегідь окресленого класу матриць так, щоб на кожному кроці процесу зменшувалася будь-яка величина, що характеризує точність розв'язання системи [25]. Серед релаксаційних методів найбільше розроблені координатні. В ( k ) H яких матриці підібрані так, що на кожному кроці змінюються одна або декілька компонентів послідовних наближень, і градієнтні, в яких матриці ( k ) H є скалярними [2]. х А х  b Про точність наближення рішення системи природно * У  х  х судити за величиною вектора помилки . Проте вектор помилки може бути обчислений без знання точного рішення системи і може лише х оцінюватися. Вектором, що характеризує точність наближеного рішення А х  b r  b  А х системи , може служити також вектор нев'язки [1] . 45 r  А У Зрозуміло, що . Таким чином, релаксація може бути побудована на зменшенні будь-якої норми кожного з цих векторів. А При позитивно визначених матрицях зручною мірою точності є так звана функція помилки 1 f ( х)  ( А У , У )  (У , r )  ( А r , r ) f ( х )  0 А З огляду на позитивності визначеності завжди , причому * f ( х)  0 х  х лише за . Функція помилки не може бути обчислена, якщо не відоме точне рішення. Однак її значення лише постійним доданком відрізняються від значень функціоналу f ( Х )  ( А х , х)  2( х, b) 0 * х які можуть бути обчислені без знання . Тому можемо судити про зменшення функції помилки порівнюючи відповідні значення функціоналу f ( х) [7]. 0 Іншим важливим принципом побудови ітераційних процесів є принцип послідовного
id: 17
Цитирования: 0,01%
«придушення компонентів»
вектора помилки в розкладанні його за власними векторами матриці коефіцієнтів системи. 2.2. Побудова проекційних методів А х  b Розглянемо систему та сформулюємо для неї наступне n n   R   R завдання. Нехай задані деякі два підпростори та . Потрібно х  знайти такий вектор , який би гарантував рішення вихідної системи,  оптимальне щодо підпростору , тобто щоб виконувалася умова l  :( А х , l )  (b, l ) звана умовою Петрова-Галеркіна. Згрупувавши обидві частини рівності b  А х  r за властивостями скалярного добутку і помітивши, що , цю умову х можна подати у вигляді 46 l  :(r , l )  0 (2.4) х r  b  А х  тобто . Таке завдання називається завданням х  х  проектування рішення на підпростір ортогонально до підпростору [5]. У більш загальній постановці завдання виглядає так. Для вихідної * х х системи (2.1) відомо деяке наближення до рішення . Потрібно 0 b  А( х  )    уточнити його поправкою таким чином, щоб 0 х х . Умову Петрова-Галеркіна у цьому разі можна записати як l  :(r , l )  ((b  А х )  А , l )  (r  А , l )  0 х  0 х 0 х 0 х   d і m   d і m   m Нехай . Введемо у підпросторах та базиси m m {v } {w } та відповідно. Неважко бачити, що (2.4) виконується тоді j j 1 j j 1 і тільки тоді, коли j( 1  j  m): (r -А σ ,w )  0 (2.5) 0 х j   V  v v v При введенні для базисів матричних позначень та 1 2 . . . m m σ  V   W  w w w у  R можна записати де — вектор х у 1 2 ... m коефіцієнтів [1]. Тоді (2.5) може бути записано у вигляді T W (r  А V )  0 (2.6) 0 у T T W А V  W звідки та у r 0 T 1 T у  (W А V ) W (2.7) r 0 Таким чином, рішення має уточнюватися відповідно до формули T 1 T х  х  V (W А V ) W (2.8) 1 0 r 0 з якої відразу випливає важлива вимога: у практичних реалізаціях   проекційних методів підпростору та , їх базиси повинні вибиратися 47 T W А V так, щоб матриця або була малої розмірності, або мала просту структуру, зручну для обігу [15]. З (2.6) також випливає співвідношення 1 1 V  А r  А (b  А х )  х  х у 0 0 * 0 V у  Тобто являє собою проекцію на підпростір K різниці між точним х рішенням та початковим наближенням. q n   ...   R  , Нехай є набір пар підпросторів таких, що і 1 2 q і і і 1 n   ...   R . Тоді очевидно, що послідовне застосування описаного 1 2 q х раніше процесу до всіх таких пар призведе до рішення , що задовольняє q А х  b вихідну систему [5]. Відповідно, у загальному вигляді алгоритм будь-якого методу проекційного класу може бути записаний таким чином: Рис. 2.1. Блок-схема методу розв'язання проекційного класу 48   Найбільш простою ситуацією є випадок, коли простори та   s р а n{w}   s р а n{v} одновимірні. Нехай і [1]. Тоді (2.8) набуває вигляду х  х   v (2.9) k 1 k k k  причому коефіцієнт легко знаходиться з умови ортогональності k r  А( v )  w : k k k k (r   А v , w )  (r w )   ( А v , w )  0 k k k k k , k k k k   (r w )/( А v , w ) v  w  r Звідки [5]. Якщо вибрати . k k , k k k k k k Тоді (2.9) набуде вигляду (r , r ) k k х  х  r (2.10) k 1 k k ( А r , r ) k k T r А r Оскільки вираз у знаменнику є квадратичною формою , k k збіжність процесу гарантована, якщо матриця А є симетричною і позитивно визначеною [21]. Цей спосіб є спосіб якнайшвидшого спуску; можна показати, що з 2 Ф( х)  х  х кожної ітерації у ньому мінімізується функціонал у бік — * А Ф ( х) [58]. В силу позитивної визначеності А, квадратична форма T х  х ( х  х ) А( х  х )  Ф( х) досягає свого мінімуму (рівного нулю) та * * * строго випукла. При цьому Ф(х)  ( А( х  х ), х  х )  * *  ( А х, х) -( А х,х ) -(b,х)  (b,х )  * * T T T T  х А х  х А х  b  b * х х * 49 T T 1 T х А х  b ( А ) А х  b х В силу симетричності матриці А справедливо , і * функціонал дорівнює T T T Ф( х)  х А х  2b х  b х (2.11) * Ф( х)  r Ф( х)  2 А х  2b  2r його градієнт [53]; отже, — . х х T   r /( r А r ) Ф( х) Покажемо тепер, що вибір доставляє мінімум х х х T b х х r у цьому напрямі. Підставим в (2.11) вираз ; останнім доданком * при цьому можна знехтувати, так як він постійний і не впливає на процес мінімізації [5]. Знову враховуватимемо симетрію матриці А T T f ( )  Ф( х r )  ( х r ) А( х r )  2b ( х r )  T T 2 T T T  х А х  2х А r   r А r  2b х  2b r  T T T T T 2 T  [ х А х  b х]  b х  2 [ х А r  b  ]   r А r  T T 2 T  (r  b)  2r r   r А r х m і n f ( ) Ф( х) Знайдемо ; враховуючи опуклість , для цього  f ( ) достатньо знайти стаціонарну точку : T r r (r , r ) ' T T f ( )  2r А r  2r r  0     T r А r ( А r , r ) що збігається з (2.10). У практичних завданнях метод якнайшвидшого спуску має досить повільну збіжність, відповідний аналіз наведено в [24]. T v  А r w  А v Якщо вибрати і . Формула (2.9) набуває вигляду k k k k T (r , А А r ) T х k х  х  А r  k 1 k k T T ( А А r , А А r ) k k T T (2.12) ( А r , А r ) T k k  х  А r k k T T T ( А А А r , А r ) k k Цей спосіб є спосіб якнайшвидшого зменшення невязки; умовою його збіжності є невиродженість матриці А. 50 Порівнюючи (2.12) і (2.10), неважко переконатися, що метод якнайшвидшого зменшення незв'язки збігається з методом якнайшвидшого T T А А х  А b спуску, застосованим до системи . Тоді на підставі співвідношення (2.10) можна стверджувати, що в методі (2.12) на кожному 2 Ф( х)  b  А х Ф ( х) кроці мінімізується функціонал у напрямку - . 2 T v  w  А е Якщо вибір на k-й ітерації це дає методи класу А B S k k k   [1]. Щоб різних ітерацій виконувалося умова , можливе або і j v зберігання всіх із їх ортогоналізацією по мірі знаходження (схема k Хуанга), або перерахунок матриці А (схема Абрамова). Перший варіант веде до збільшення витрат пам'яті реалізації алгоритму, другий – до зміни заповненості матриці. Отже, дані методи придатні лише вирішення щільних чи невеликих систем; з іншого боку, їх єдиною умовою збіжності є існування рішення як такого, тому даний клас придатний для СЛАР з виродженими і неквадратними матрицями [43]. v Безпосередньо з визначення векторів випливає, що у даних методах k на k-й ітерації поправка до рішення обчислюється з умови звернення k-го рівняння у тотожність [5]. У найпростішому випадку, якщо припускати, що матриця А квадратна і невироджена, обчислення описуються як алгоритм представлений на рис. 2.2. і схема має такий вигляд: 51 Рис. 2.2. Блок-схема методів розв'язання класу А B S 2.3. Підпростори Крилова При побудові та реалізації проекційних методів важливу роль  відіграють так звані підпростори Крилова, які часто обираються як . v Підпростором Крилова розмірності m, породженим вектором та матрицею А називається лінійний простір d е f 2 m1   K v, А s р а n{v, А v, А v,..., А v} (2.13) m  v В якості вектора зазвичай вибирається нев'язка початкового r  наближення ; тоді вибір підпростору та спосіб побудови базисів 0 підпросторів повністю визначає обчислювальну схему методу [5]. До ідеї використання підпросторів Крилова можна дійти таким чином. Оскільки відомо, що в побудові релаксаційних методів використовується А  D  Е  F уявлення матриці А як , а методи Якобі і Гаусса-Зейделя є окремими випадками класу методів, заснованого на розщепленні А як різниці 52 R А  K  R K двох матриць і . Тоді вихідна система (2.1) може бути записана у вигляді K х  b  R х  b  (K  А) х що дозволяє побудувати ітераційний процес K х  K х  (b  А х ) k 1 k k або, еквівалентний вираз, 1 х  х  K r (2.14) k 1 k k R  І  А K  І Виберемо і , тоді процес (2.14) буде зведений до вигляду х  х  r (2.15) k 1 k k звідки х  х  r  r  ...  r (2.16) k 0 0 1 k 1 ( А) b Помноживши обидві частини (2.15) зліва на та додавши до них отримаємо b  А х  b  А х  А r  r  А r k 1 k k k k що дозволяє знайти вираз для нев'язки на k-ої ітерації через нев'язку початкового наближення: k r  ( І  А)r  ( І  А) r (2.17) k k 1 0 Після підстановки (2.17) в (2.16) отримуємо k 1   j х  х  ( І  А) r    k 0 0 j 0   k 1   s р а n{r , А r ,..., А r }  k (r , А) тобто х 0 0 0 k 0 Безпосередньо з визначення випливають такі властивості підпросторів q q( А)v  0 Крилова. Нехай поліном, такий що , причому має ступінь d е g q  мінімальний серед усіх таких поліномів. Тоді 53 m(m  ): K (v, А)  K (v, А)  . Більше того, K інваріантно m  щодо А. m : d і m( K )  m  m   m  Крім того, з (2.17) випливає, що в методах, що використовують підпростір Крилова, нев'язка k-ої ітерації виражається через початкову нев'язку деяким матричним поліномом [13]. До ітераційних методів підпростору Крилова відносяться: метод квазімінімізації нев'язки, метод Річардсона, метод спряжених градієнтів та його варіації, такі як метод біспряжених градієнтів, стійкий двонаправлений метод спряжених градієнтів, квадратичний метод спряжених градієнтів. Наведемо виклад деяких з перерахованих вище методів алгоритми, яких будуть описані в бібліотеках класів. 2.3.1. Метод спряжених градієнтів Метод спряжених градієнтів є одним із найефективніших методів вирішення розріджених симетричних позитивно визначених систем [29]. Нижче наведено виклад методу. А х  b Розглядаючи систему лінійних рівнянь із семеричною позитивно визначеною матрицею А. Метод ґрунтується на ідеї мінімізації функції. 1 T T f ( х)  х А х  b х 2 f ( х) Функція досягає свого мінімального значення тоді і лише тоді, f  А х  b коли її градієнт перетворюється у нуль, що еквівалентно рівності (2.1). х Нехай – початкове наближення до рішення (точки мінімуму). На k-й 1 р х ітерації метод вибирає напрям і по наближенню будується k k f ( х   р )  х  х   р наближення , де мінімізує величину . k k k k k 1 k k k 54 Напрямок вибирається так, що мінімізує функцію не тільки на прямій, а й на лінійній оболонці вектора. Звідси випливає, якщо помилок округлення немає, то метод досягається мінімум за n кроків [18]. Нижче наведені розрахункові формули: р  r r  b  А х , , 1 1 1 1 T r r k k r  r  А р   ,
id: 18
Обнаружен Плагиат: 0,12%https://www.reddit.com/r/learnmath/c…
0,2%
https://www.reddit.com/r/learnmath…
k k 1 k k k T , р А р k k T r r k 1 k 1   р  r  р , k k 1 k 1
k k T , r r k k х  х  а р . k 1 k k k А р На кожній ітерації добуток достатньо вирахувати лише один раз. k r  b  А х х r Вектор є нев'язкою для наближення , тобто , а вектори в k k k k {r } послідовності ортогональні попарно: k T r r  0 і j (і  j ) , { р } В той же час вектори в послідовності попарно пов'язані: k T р А р  0 і j (і  j ) Справедлива так само рівність T r А р  r р  0 і j і j (і  j ) . Ітерації тривають до того часу, поки відносна форма нев'язки || r || / || b || не стане менше заданого значення. k 55 Зважаючи на помилки округлення, описаний процес необхідно розглядати як ітераційний. Цей процес може бути не стійким або навіть завершатися аварійно (наприклад, при діленні на 0) [33]. 2.3.2. Метод біспряжених градієнтів Одним із узагальнень методу спряжених градієнтів у разі лінійної А А х  b системи з довільною квадратичною невиродженою матрицею є T А А метод біспряжених градієнтів. Відомо, що матриця – симетрична та T T А А х  А b позитивно визначена, а система еквівалентна вихідній. Для вирішення цієї системи можливе застосування методу спряжених градієнтів, проте таке застосування є не оптимальним рішенням задачі, оскільки T А А А обумовленість матриці набагато гірша за обумовленість матриці [30]. З іншого боку, доведено, що за допомогою рекурентного співвідношення невеликого порядку домогтися попарної ортогональності А {r } нев'язок у разі довільної матриці неможливо. У методі біспряжених k {r } градієнтів послідовність ортогональних нев'язок замінена на дві k ~ {r } {r } біортогональні послідовності , . Послідовність спряжених k ~ { р } { р } { р } напрямків замінена на біспряжені послідовності , . k k k Розрахунки виконуються за формулами: ~ ~ р  р р  r r  r r  b  А х 1 1 1 1 1 1 1 1 T ~ r r T k k ~ ~ ~ r  r  А р r  r  А р а  k 1 k k
id: 19
Обнаружен Плагиат: 0,18%https://www.reddit.com/r/learnmath/c…
0,2%
https://www.reddit.com/r/learnmath…
k k 1 k k k k T ~ р А р k k T ~ r r ~ ~ ~ k 1 k 1 р  r  р р  r  р   k 1 k 1 k k k 1 k 1
k k k T ~ r r k k 56 х  х  а р k 1 k k k А р На кожній ітерації необхідно обчислити один добуток та один k ~ T ~ {r } {r } А р добуток . Покажемо, що вектори в послідовностях і k k біоортогональні: T ~ (і  j ) r r  0 , і j ~ { р } { р } а вектори в послідовностях та біспряжені: k k T ~ (і  j ) р А р  0 . і j Справедлива також рівність T ~ ~ (і  j ) r А р  r р  0 . і j і j 2.4. Передумовлення Нехай М деяка невиражена матриця розмірності n. Домноживши (2.1) 1 M на , отримаємо систему 1 1 M А х  M b (2.18) х яка через невиродженість М має те саме точне рішення . Ввівши * 1 1 ˆ ˆ b  M b А  M А позначення і , запишемо (2.9) у вигляді ˆ ˆ А х  b (2.19) Запис (2.19) алгебраїчно еквівалентна (2.1), а спектральні ˆ А характеристики матриці відрізняються від характеристик матриці А, що призводить до зміни швидкості збіжності чисельних методів (2.19) по відношенню до (2.1) в кінцевій арифметиці. Процес переходу від (2.1) до (2.19) з метою покращення характеристик матриці для прискорення збіжності до рішення називається передумовою, а матриця М - матрицею передумови [5]. 57 З (2.19) випливає вимога: матриця М має бути близька до матриці 1 І х  А b M  А А.(Вибір наводить (2.1) до виду , проте немає 1 А практичного сенсу, оскільки вимагає знаходження , що з суті і зводиться до рішення(2.1)). Другою природною вимогою є вимога легкої обчислюваності матриці М. 1 ˆ M А А Знаходження добутку для обчислення у загальному випадку Р  Р веде до зміни портрета ( ). Тому на практиці використовується ˆ А А інший підхід. ˆ r r Нев'язка системи (2.19) пов'язана з нев'язкою системи (2.1) нижче наведеним співвідношенням ˆ M r  r (2.20) ˆ ˆ z  А q z  А q яке справедливе і для матрично-векторних добутків і 1 ˆ ˆ ˆ z  А q  M А q  M z  А q  z (2.21) Це дозволяє замість явного переходу від (2.1) до (2.19) вводити схеми методів коригучі кроки для обліку впливу передумовної матриці. З (2.21) випливає ще одна умова: структура матриці передумови повинна допускати легке і швидке рішення
id: 20
Цитирования: 0,01%
«зворотних до передумов»
систем ˆ M r  r виду . Таким чином: А M − має бути близька до ; M − повинна бути легко обчислювана; M − повинна бути легко оборотна. M Вибір в якості як деякої діагональної матриці задовольняє двом останнім вимогам з трьох перерахованих і зводить передумову до масштабування СЛАР. Як відомо, у ряді випадків масштабування здатне значно прискорити процес розв'язання. 58 Описана вище передумова іноді називається лівою, так як домноження матриці СЛАР на матрицю передумови проводиться зліва. Інший підхід ґрунтується на переході від (2.1) до системи 1 А M у  b (2.22) у х у якої точне рішення пов'язане стічним рішенням вихідної * * СЛАР [48]. 1 х  M у (2.23) * * Передумовлення (2.22) реалізується шляхом виконання матрично- 1 z  А q z  А(M q) векторних множень подвійних множень крім того. При досягненні необхідної точності здійснюється перерахунок рішення відповідно до (2.23). Така схема передумови називається правою. Для прискорення збіжності в проекційному методі підпростору Крилова часто використовуються передумови. Опишемо застосування передумови до вищевикладених методів сполучених та біспряжених градієнтів. 1 1 M M А  M b Нехай матриця є матрицею передумови. Система еквівалентна вихідній системі, проте застосування методу спряжених 1/ 2 M А градієнтів до нової системи неможливе, оскільки матриця у загальному випадку не симетрична. Ідея методу спряжених градієнтів із передумовою полягає у розгляді системи 1/ 2 1/ 2 1/ 2 M А M у  M b (2.24) 1/ 2 M де - обумовлена єдиним чином симетрична позитивно визначена 1/ 2 2 у (M )  M х матриця, така, що . Нові невідомі пов'язані з невідомим 1/ 2 х  M у системами (2.1) за формулами . Застосуємо до системи (2.24) метод спряжених градієнтів. 59 Для ефективної реалізації цієї ідеї вводиться на розгляд нова {z } послідовність векторів . Розглянуті формули набувають вигляду: k р  r r  b  А х , , 1 1 1 1 1 z  M r k k T r r k k r  r  А р   ,
id: 21
Обнаружен Плагиат: 0,12%https://www.reddit.com/r/learnmath/c…
0,2%
https://www.reddit.com/r/learnmath…
k k 1 k k k T , р А р k k T r z k 1 k 1   р  z  р , k k 1 k 1
k k T , r z k k х  х  а р . k 1 k k k А р На кожній ітерації необхідно один раз обчислити добуток і один k 1 1/2 M r M раз обчислити вираз . З цього видно, що явного не k відбувається. Розглянемо деякі способи вибору передумови. Якщо діагональні А елементи матриці сильно відрізняються один від одного, то одним з А M можливих рішень є взяття в якості як діагональну частину матриці . У 1 M А цьому випадку добуток можна розцінювати як балансування матриці 1 А M r , яке покращує її зумовленість. У той же час обчислення виразу n  О (1) досить просте і використовує операцій [4]. Інший спосіб вибору передумови заснований на неповному розкладанні T А  L L Холецького. Нехай - розкладання Холецького розрідженої матриці А L . може мати більш заповнену структуру, ніж нижньотрикутна частина А матриці . Неповним розкладанням Холецького називається наближена ~ ~ ~ T А  L L L рівність , де нижньотрикутна невироджена розріджена матриця 60 ~ ~ T M  L L А  M з невеликим заповненням. Нехай . Оскільки , то матриця 1 M А близька до одиничної і, отже, добре обумовлена. З іншого боку, якщо ~ 1 M r L вже знайдено, то обчислення матриці зводиться до розв'язання ~ ~ 2 2n  О(n) L х  у L у  r двох трикутних систем і що вимагає час . Оцінку швидкості збіжності методу спряжених градієнтів з обумовленням можна дати в термінах числа обумовленості 1 1 k  с о n d (M А) х M А матриці . Нехай - точне рішення системи 2 А А х  b з симетричною позитивно визначеною матрицею . Тоді для методу спряжених градієнтів із симетричною позитивно визначеною M передумовою справедлива оцінка k || х  х ||  2а || х  х || (2.25) k А 1 А а  ( k  1) /( k  1) де . Нерівність (2.25) є лише верхньою оцінкою. Якщо власні значення 1 M А матриці добре відокремлені. То часто спостерігається збіжність зі швидкістю геометричної прогресії зі зменшуваним знаменником. У разі методу біспряжених градієнтів як передумову можна взяти А діагональну частину матриці або неповне L U-розкладання, тобто ~ ~ ~ ~ U А  L U L наближення виду , де нижньотрикутна, а верхньотрикутна невироджені матриці з невеликим заповненням. Розрахункові формули методу біспряжених градієнтів з обумовленням мають вигляд: ~ ~ р  р р  r r  r r  b  А х 1 1 1 1 1 1 1 1 1 1 T ~ z  M r z  M r k k k k 61 T ~ r z T k k ~ ~ ~ r  r  А р r  r  А р а  k 1 k k
id: 22
Обнаружен Плагиат: 0,18%https://www.reddit.com/r/learnmath/c…
0,2%
https://www.reddit.com/r/learnmath…
k k 1 k k k k T ~ р А р k k T ~ r z ~ ~ ~ k 1 k 1 р  z  р р  z  р   k 1 k 1 k k k 1 k 1
k k k T ~ r r k k х  х  а р k 1 k k k 1 T ~ M r А р А р На кожної ітерації необхідно обчислити добуток , , , k k k 1 T M r . k 2.5. І L U-факторизація Одним із широко відомих способів розкладання матриць на множники є L U-факторизація [5], що дозволяє подати матрицю А у вигляді А  L U (2.26) А А L U де − нижньо і - верхньотрикутні матриці відповідно. А А А х  b Дане уявлення дозволяє легко вирішувати СЛАР виду L у  b шляхом виконання прямого ходу для нижньотрикутної системи А U х  у та зворотного ходу для верхньотрикутної системи . Проте А алгоритм факторизації непридатний для СЛАР з розрідженими матрицями, оскільки веде до заповнення портрета, тобто появі в L U матрицях і ненульових елементів у тих позиціях, для яких А А а  0 і, як наслідок, різкого збільшення обсягу пам'яті, необхідної для і j зберігання матриць [31]. Замість задачі знаходження факторизації (2.26) сформулюємо задачу для заданої матриці А представивши її у вигляді А  L U  R (2.27) де матриці у правій частині задовольняють наступним властивостям: 62 − матриці L та U є нижньотрикутною та верхньотрикутною відповідно; Р  Р Р  Р − і ; U А L А (і, j )  Р : [ L U ]  [ А]і j − ; А і j Р  Р  − А R А  L U Тоді наближене представлення називається неповною L U- факторизацією матриці А або коротко її І L U-розкладом [5]. Р Останні дві вимоги означають, що на множині індексів матричний А добуток L U повинен точно відтворювати елементи А. Для знаходження матриць L і U генеруватимемо їх рядково. Припустимо, що перші k – 1 рядків вже знайдені і потрібно знайти k-й. Запишемо у блочному вигляді перші k рядків розкладу (2.27): А А L 0 U U R R       11 12 11
id: 23
Обнаружен Плагиат: 0,42%https://dspace.sfa.org.ua/bitstream/1…
2%
https://dspace.sfa.org.ua/bitstream…
11 12 11 12        T T T T T T       (2.28) а а l 1 0 u r r 21 22 21 22 21 22       T T T T l u r r де , , и — деякі вектори. Виконав дії над матрицями в правій 22 21 22 21 частині (2.28), отримуємо А А L U  R L U  R     11 12 11 11 11 11 12 12      T T T T T T T
    а а l  U  r l  U  u  r 21 22 21 11 21 21 12 22 22     T T l u З рівності матриць випливає, що шукані вектори і повинні 21 22 задовольняти умови: T T T l U  r  а (2.29) 21 11 21 21 T T T T u  r  а  l U (2.30) 22 22 22 21 12 Вирішивши ці системи, можна визначити коефіцієнти k-х рядків матриць l ,..., l , u ,..., u розкладання [37]. k1 k , k 1 k k k n 63 l l ...l Визначимо з (2.29) у припущенні, що вже знайдено. Згідно з k j k 1 k j1 а  0 l  0 раніше сформульованими умовами, якщо , то . В іншому k j k j r  0 випадку і (2.29) можна записати у вигляді k j j j 1 l u  l u  l u  а   k і і j k і і j k j j j k j (2.31) і 1 і 1 l Це дозволяє обчислити наступним чином: k j j 1   1   l  а  l u  k j k j k і і j (2.32)   u і 1   j j l  1 Аналогічними міркуваннями з урахуванням (2.30) можна отримати j j u вираз для : k j k 1 u  а  l u  k j k j k і і j (2.33) і 1 а  0 u  0 для тих випадків, коли , інакше . k j k j U L Елементи матриць і отриманих в результаті І L U-розкладання, не L U збігаються з відповідними елементами матриць і , отриманих при А А повній L U-факторизації [31]. Матриця, отримана на вході І L U-розкладання, як правило, задовольняє всім трьом вимогам до матриці передумовника, сформульованим у § 2.4. Р Вона наближає матрицю А, оскільки на множині індексів точно А відтворює її; вона легко обчислюється на підставі формул (2.32) та (2.33) на рис. 2.3 представлено блок-схему алгоритму І L U-розкладання; вона так само легко оборотна, оскільки є добутком двох трикутних матриць [5]. M  L U Таким чином, використання є досить ефективним способом передумовлення. 64 Рис. 2.3. Блок-схема алгоритму І L U-розкладу А  L U У випадку, коли матриця А симетрична, з рівностей та T T U L L  U А  А для трикутних матриць і випливає, що . Факторизація (2.27) у цьому випадку набуває вигляду T T А  L L  R  U U  R (2.34) В цьому випадку для знаходження діагональних елементів такої L матриці потрібні операції вилучення квадратного кореня. Щоб уникнути цього, замість факторизації (2.34) використовується дещо різний варіант T А  L D L  R L D де головна діагональ складається з одиничних елементів, а діагональна матриця. Нижче на рис 2.4 наведена блок-схема алгоритму для 65 L D обчислення коефіцієнтів і із застосуванням логіки І L U-факторизації у разі, коли матриця симетрична. _ ___ _ для �� = 1,�� збільшити �� _ ___ ___ __ для �� = 1, �� − 1збільшити �� Так Ні Рис. 2.4. Блок-схема І L U-розкладу для симетричної матриці Висновки до другого розділу 1. Наведено принципи побудови ітераційних процесів. Здійснено поділ ітераційних процесів на стаціонарні циклічні та нестаціонарні. Розглянуто принцип релаксації як із основних принципів побудови ітераційних процесів. 2. Розглянуто побудову проекційних методів. Наведено блок-схему в загальному вигляді, що описує алгоритм будь-якого методу проекційного класу. 3. Розглянуто проекційні методи підпростору Крилова. Наведено опис методів розв'язання спряжених градієнтів та біспряжених градієнтів, що належать до даного підпростору. 66 4. Визначено призначення передумови. Зформульовані вимоги необхідні для формування матриці, що зумовлює. Описано методи спряжених та біспряжених градієнтів з урахуванням застосування передумовлення. 5. Проаналізовано неповну L U-факторизацію матриці. Визначено, що отримана матриця вході І L U-розкладання задовольняє всім вимогам до матриці передумовника, будучи легко обчислюваною і оборотною, так як є добутком двох трикутних матриць. Використання неповної L U-факторизації є ефективним способом передумовлення. 67 РОЗДІЛ 3. РОЗРОБКА БІБЛІОТЕКИ КЛАСІВ ДЛЯ ПРЕДСТАВЛЕННЯ СЛАР 3.1. Використання ООП підходу до подання СЛАР Дослідження різних методів розв'язання систем лінійних алгебраїчних рівнянь (СЛАР) полягає в порівняльному аналізі продуктивності методів при вирішенні СЛАР на ЕОМ. У цьому випадку оцінку ефективності даних методів доцільно проводити в рамках єдиного програмного комплексу – бібліотеки класів. Найлегше реалізувати подібний комплекс вдається за допомогою технології об'єктно-орієнтованого програмування (ООП), яка є методологією програмування, заснованою на представленні програми як сукупності взаємодіючих об'єктів, кожен із яких є екземпляром певного класу, а класи є членами певної ієрархії успадкування [8]. Технологія ООП дозволяє в рамках єдиної програми будувати функціонально однорідні елементи (в даному випадку алгоритми рішення СЛАР), які використовують загальні структури та механізми програмної реалізації. До цих структур слід віднести, перш за все, представлення в пам'яті ЕОМ матриць та векторів, які можуть бути реалізовані, проаналізувавши схеми зберігання матриць великої розмірності. До механізмів відносяться процедури визначення та введення вихідних даних, матрично-векторні операції лінійної алгебри, а також процедури контролю процесом виконання розрахунку. Всі загальні структури та механізми інкапсулюються і можуть бути об'єднані в базовий абстрактний клас рішення СЛАР, наслідуючи який далі здійснюється реалізація конкретного методу (алгоритму) рішення СЛАР. Використовуючи цей підхід, можна надати програмний комплекс рішення СЛАР у вигляді бібліотеки класів. Розроблена бібліотека дозволить виконати рішення заданої СЛАР будь-яким із наявних методів. Розрахунок може проводитися при заданні деяких початкових умов, таких як установки точності обчислення та кількості використовуваних ітерацій, вибору передумови та схеми зберігання матриці в пам'яті. Переважна більшість алгоритмів рішення СЛАР, у рамках представленої бібліотеки, будуть орієнтовані рішення несиметричних 68 матриць довільної структури. Такі матриці виходять під час реалізації різних чисельних алгоритмів. Використовуючи такий програмний комплекс, для заданого типу СЛАР можна підбирати найоптимальніший метод рішення, і навіть найефективніший режим розрахунку, як із погляду продуктивності, і економії пам'яті ЕОМ. Однією з основних переваг при використанні ООП підходу для представлення СЛАР є те, що досить просто в рамках бібліотеки, що розробляється, проводити модифікування наявних і розробку нових методів рішення СЛАР успадковуючи вже існуючі властивості та методи обробки матриці. Також зручним є використання поліморфних властивостей об'єктів, які є екземплярами класів методів рішення. У цьому випадку залежно від матриці об'єкт може приймати такий стан, у якому метод вирішення найефективніший. 3.2. Реалізація моделі бібліотеки класів Для того щоб розробити ефективний інструмент вирішення та дослідження систем лінійних алгебраїчних рівнянь у вигляді об'єктно- орієнтованої бібліотеки класів незалежної від інших компонентів і бібліотек крім як стандартних засобів мови програмування в даній магістерській роботі були виділені наступні завдання: 1. Реалізація структур даних для широкого класу матриць, які дозволяють ефективно зберігати та обробляти матрицю у пам'яті ЕОМ. 2. Реалізація проекційних методів вирішення СЛАР підпростору Крилова на основі розроблених структур даних. Для цього у вигляді аналізу предметної області було проаналізовано існуючі технології зберігання матриць великої розмірності та математичне представлення матричних алгоритмів. На наступному етапі розробки необхідно проведення об'єктно-орієнтованого аналізу бібліотеки класів, що розробляється. Об'єктно-орієнтований аналіз – є метод аналізу, що досліджує вимоги до системи з точки зору класів та об'єктів [8]. У цьому випадку на основі 69 отриманої інформації в ході аналізу предметної області можна виділити такі сутності, що представлені на рис 3.1 як результат об'єктно-орієнтованого аналізу, що визначають вимоги до системи. Рис. 3.1. Результат об'єктно-орієнтованого аналізу предметної області На зображеному вище малюнку представлені основні визначення предметної області, які необхідно реалізувати у вигляді класів та екземпляри об'єктів, що дадуть необхідну функціональність бібліотеці, що розробляється. Наступним кроком розробки об'єктно-орієнтованого програмного комплексу є реалізація його моделі, використовуючи метод об'єктно- орієнтованого проектування. Об'єктно-орієнтоване проектування є метод проектування, що поєднує процес об'єктно-орієнтованої декомпозиції та систему позначень для представлення логічної та фізичної моделей проектованої системи [8]. Декомпозиція здійснюється під час проектування складних систем програмного забезпечення. В цьому випадку проводять поділ системи на більш дрібні її частини, кожну з яких можна уточнювати незалежно один від одного. Скориставшись результатами об'єктно-орієнтованого аналізу можна спроектувати наступну логічну модель бібліотеки, що розробляється, представлену на рис 3.2. 70 Рис. 3.2. Логічна модель бібліотеки, що розробляється У представленій моделі було зроблено уточнення деяких визначень, описані методи вирішення СЛАР, що стосуються безлічі проекційних методів підпростору Крилова. Уточнено схеми зберігання матриць та алгоритми передумовлення, що використовуються. На основі представленої логічної моделі реалізовано діаграму класів U M L, яка зображена на рис. 3.3. Дана діаграма є структурною і описує архітектурну організацію та фізичну модель бібліотеки, що розробляється. 71 Рис. 3.3. Діаграма класів У представленій діаграмі можна виділити три абстрактні базові класи, в яких описуються основні властивості визначень, виділених з об'єктно- орієнтованого аналізу предметної області. Наслідуючи ці базові класи, проводиться уточнення схем зберігання та методів обробки матриць для покращення спектральних характеристик, а також алгоритмів розв'язання СЛАР. Так, наприклад, клас M V_V е с t о r є базовим класом, в якому визначається можливість зберігання вектора і деякі операції лінійної алгебри, що дозволяють робити дії над векторами. У свою чергу класи спадкоємці розширюють його можливості та дозволяють ефективно зберігати та обробляти як щільні, так і розріджені матриці відповідно до реалізованої в них схеми зберігання. 3.3. Програмна реалізація класів На основі, наведеній, на рис. 3.3 діаграми класів, що описує архітектурну організацію та фізичну модель розроблюваної бібліотеки, була розроблена бібліотека класів мовою програмування С++. Ядром бібліотеки є 14 класів, які використовуються для реалізації алгоритмів рішення або є методами вирішення СЛАР за визначенням, надаючи зручний інтерфейс 72 використання. Також бібліотека містить класи введення-виведення, що інкапсулюють роботу зі стандартними функціями мови програмування, що дозволяє спростити операції введення-виведення. Для коректної обробки виняткових ситуацій в ході рішення в бібліотеці реалізований клас, що дозволяє обробляти помилку, що робить розроблювані додатки з використанням даної бібліотеки більш стабільними. Так для організації зберігання матриць у пам'яті комп'ютера була розроблена ієрархія у вигляді базового класу M V_V е с t о r, про який говорилося раніше, та його спадкоємців: 1. клас С о m р R о w_M а t_d о u b l е – з реалізацією малої схеми зберігання матриці (С S R), у разі всі ненульові елементи матриці перераховуються по рядкам; 2. клас С о m р С о l_M а t_d о u b l е – з реалізацією стовпцевої схеми зберігання матриці (С S С), де ненульові елементи матриці перераховуються стовпцями; 3. клас С о о r d_M а t_d о u b l е – з координатною схемою зберігання матриці (С О О R), де всі ненульові елементи матриці перераховуються по рядкам і стовпцям з допомогою координат. Базовий клас цієї ієрархії є шаблонним і складається з трьох полів шести конструкторів та двадцяти чотирьох членів-функцій. Нижче в таблиці 3.1 представлені поля класу та описано їх призначення. Таблиця 3.1 Поля класу M V_V е с t о r Назва Тип Специфікатор Опис та призначення поля даних доступу в класі Вказівник на одновимірний р_ T У Р Е * р r о t е с t е d масив, що містить елементи вектора 73 Назва Тип Специфікатор Опис та призначення поля даних доступу в класі d і m_ і n t р r о t е с t е d Розмір вектора r е f_ і n t р r о t е с t е d Лічильник кількості посилань Наслідуючи клас M V_V е с t о r можна використовувати його конструктори, які дозволяють виділити необхідну кількість пам'яті та проініціалізувати її. Нижче у таблиці 3.2 представлені прототипи деяких конструкторів. Таблиця 3.2 Конструктори класу M V_V е с t о r Прототип Опис M V_V е с t о r() Конструктор за замовчуванням Конструктор із встановленням M V_V е с t о r( і n t) розмірності вектора Конструктор із встановленням M V_V е с t о r( і n t, с о n s t T У Р Е&) розмірності та ініціалізації значенням параметра T У Р Е Конструктор з ініціалізації значенням M V_V е с t о r(T У Р Е*, і n t) параметра T У Р Е* та встановленням розмірності Конструктор з ініціалізації значенням M V_V е с t о r(T У Р Е*,і n t, параметра T У Р Е*, встановлення M V_V е с t о r_::r е f_t у р е і) розмірності та кількості посилань M V_V е с t о r(с о n s t Конструктор копіювання M V_V е с t о r T У Р Е &) У класі M V_V е с t о r представлена реалізація двадцяти чотирьох членів функції серед них сім є перевантаженням операторів. Перевантаження операторів дозволило реалізувати основні операції лінійної алгебри. Ця можливість мови програмування С++ одна із її переваг. Так як 74 перевизначення математичних операцій
id: 24
Цитирования: 0%
«+»,
id: 25
Цитирования: 0%
«-»,
id: 26
Цитирования: 0%
«=»
для розроблених програмістом класів дає можливість, змусити ці класи поводитися подібно до вбудованих типів і дає більше ступенів свободи в управлінні поведінкою алгоритму, що реалізується. У таблиці 3.3 подано основні функції-члени класу M V_V е с t о r. Таблиця 3.3 Основні методи класу M V_V е с t о r Тип значення, що Прототип Опис повертається Перевантаження оператора виклику T У Р Е& о р е r а t о r()(і n t) функції прямого доступу до елемента вектора і n t s і z е() с о n s t Повертає розмір вектора Повертає кількість і n t r е f() с о n s t посилань Встановлює новий M V_V е с t о r T У Р Е & n е w s і z е(і n t) розмір вектора Встановлює новий M V_V е с t о r T У Р Е & n е w s і z е(і n t, і n t) розмір вектора та ініціалізує його Перевантаження о р е r а t о r=(с о n s t оператора присвоєння. M V_V е с t о r T У Р Е & M V_V е с t о r T У Р Е &); Надає значення одного вектора іншому. о р е r а t о r*(с о n s t T У Р Е Перевантаження M V_V е с t о r T У Р Е &, с о n s t оператора множення. M V_V е с t о r T У Р Е &) Множить вектори 75 Тип значення, що Прототип Опис повертається о р е r а t о r+(с о n s t Перевантаження M V_V е с t о r T У Р Е &, M V_V е с t о r T У Р Е оператора додавання. с о n s t Додавадання векторів M V_V е с t о r T У Р Е &) о р е r а t о r-(с о n s t Перевантаження M V_V е с t о r T У Р Е &, M V_V е с t о r T У Р Е оператора віднімання. с о n s t Різниця векторів M V_V е с t о r T У Р Е &) d о t(с о n s t M V_V е с t о r T У Р Е &, Скалярний добуток T У Р Е с о n s t векторів M V_V е с t о r T У Р Е &) n о r m(с о n s t T У Р Е Евклідова норма M V_V е с t о r T У Р Е &) Класи спадкоємці – С о m р R о w_M а t_d о u b l е, С о m р С о l_M а t_d о u b l е, С о о r d_M а t_d о u b l е складаються з п'яти полів, п'яти варіантів конструкторів та шістнадцяти членів-функцій. Функції-члени мають ідентичні імена і призначення, різниця полягає лише у схемі зберігання елементів матриці та як наслідок алгоритмів її обробки. Це спрощує освоєння бібліотеки користувачем та її використання. У таблиці 3.4 представлені поля спадкоємців класу M V_V е с t о r та описано їхнє призначення. Таблиця 3.4 Поля спадкоємців класу M V_V е с t о r Назва Тип Специфікатор Опис та призначення поля даних доступу в класі 76 Назва Тип Специфікатор Опис та призначення поля даних доступу в класі Усі ненульові елементи матриці. Залежно від схеми зберігання M V_V е с t о r v а l_; р r і v а t е вони перераховуються або в d о u b l е рядковому або в стовпцевому порядку Залежно від схеми зберігання вказує, в якому рядку M V_V е с t о r r о w і n d_ р r і v а t е знаходиться елемент або з якої і n t позиції в масивах v а l_, с о l і n d_ починається і рядок матриці Залежно від схеми зберігання вказує, в якому стовпці M V_V е с t о r с о l р t r_ р r і v а t е знаходиться елемент або з якої і n t позиції в масивах v а l_, r о w і n d_ починається і рядок матриці n z_ і n t р r і v а t е Кількість ненульових елементів Масив, що містить розмірність d і m_[2] і n t р r і v а t е матриці Конструктори класів – С о m р R о w_M а t_d о u b l е, С о m р С о l_M а t_d о u b l е, С о о r d_M а t_d о u b l е також ідентичні. У таблиці 3.5 наведені прототипи деяких конструкторів класу С о m р R о w_M а t_d о u b l е. Таблиця 3.5 Конструктори класу С о m р R о w_M а t_d о u b l е Прототип Опис С о m р R о w_M а t_d о u b l е(с о n s t Конструктор копіювання С о m р R о w_M а t_d о u b l е &) 77 Прототип Опис Конструктор приймає як параметр С о m р R о w_M а t_d о u b l е(с о n s t посилання на об'єкт класу С о m р С о l_M а t_d о u b l е &) С о m р С о l_M а t_d о u b l е Конструктор приймає як параметр С о m р R о w_M а t_d о u b l е(с о n s t посилання на об'єкт класу С о о r d_M а t_d о u b l е &) С о о r d_M а t_d о u b l е Функції-члени спадкоємців класів від M V_V е с t о r надають зручний інтерфейс доступу до елементів матриці її ініціалізації, а також дозволяють легко отримувати кількість не нульових елементів і розмірність матриці. Нижче в таблиці 3.6 представлені основні функції-члени спадкоємців класу M V_V е с t о r та описано їхнє призначення. Таблиця 3.6 Прототипи методів спадкоємців класу M V_V е с t о r Тип значення, що Прототип Опис повертається Повертає елемент матриці, що зберігається в одновимірному масиві d о u b l е& v а l(і n t) у вигляді вектора Повертає посилання на ціле значення, яке вказує з якої позиції в масивах v а l_, r о w і n d_ і n t& r о w_і n d(і n t) починається і-й рядок матриці Повертає посилання, яке вказує в якому стовпці і n t& с о l_р t r(і n t) знаходиться елемент 78 Тип значення, що Прототип Опис повертається Повертає кількість і n t N u m N о n z е r о s() с о n s t ненульових елементів Перевантаження о р е r а t о r=(с о n s t оператора присвоєння. С о m р С о l_M а t_d о u b l е& С о m р С о l_M а t_d о u b l е Привласнює одну &) матрицю іншою Встановлює нову С о m р С о l_M а t_d о u b l е& n е w s і z е(і n t , і n t , і n t) розмірність матриці та ініціалізує її t r а n s_m u l t(с о n s t Транспонує матрицю та M V_V е с t о r d о u b l е V Е С T О R_d о u b l е &) множить її на вектор с о n s t Оскільки швидкість збіжності ітераційних методів розв'язання СЛАР залежить від спектральних характеристик матриці, необхідне використання алгоритмів передумовлення. Для цього вихідна матриця множиться на матрицю передумови, яка покращує спектральні властивості, що збільшує швидкість збіжності. Тому, крім найітераційнішого методу, важливою частиною обчислювальної методики є передумова матриці. Використання передумови вносить додаткові обчислення на етапі побудови та застосування на кожній ітерації. Однак виграш у швидкості збіжності може бути значним. Тому в розробленій бібліотеці реалізовано ієрархію класів, що надає інтерфейс до алгоритмів передумовлення. Бібліотека містить такі передумови: 1) діагональна передумова Якобі – клас D і а g Р r е с о n d і t і о n е r є факторизацією головної діагоналі матриці; 2) передумова Холецького – клас І С Р r е с о n d і t і о n е r у ньому реалізовано розкладанням з нульовим заповненням; 79 3) І L U-факторизація – клас І L U Р r е с о n d і t і о n е r. Його призначення не повна L U факторизація матриці. Реалізована ієрархія складається з базового абстрактного класу Р r е с о n d і t і о n е r та трьох класів спадкоємців D і а g Р r е с о n d і t і о n е r, І С Р r е с о n d і t і о n е r, І L U Р r е с о n d і t і о n е r. На діаграмі класів U M L ці елементи бібліотеки розташовані у верхній лівій частині (рис. 3.3). Клас D і а g Р r е с о n d і t і о n е r містить алгоритм діагональної передумови Якобі і складається з одного поля двох конструкторів та двох членів функції. Нижче в таблиці 3.7 представлені конструктори класу D і а g Р r е с о n d і t і о n е r. Таблиця 3.7 Конструктори класу D і а g Р r е с о n d і t і о n е r Прототип Опис Конструктор, що приймає параметр у D і а g Р r е с о n d і t і о n е r (с о n s t вигляді константного посилання на об'єкт С о m р С о l_M а t_d о u b l е &) класу С о m р С о l_M а t_d о u b l е, що містить вихідну матрицю Конструктор, який приймає параметр у D і а g Р r е с о n d і t і о n е r (с о n s t вигляді константного посилання на об'єкт С о m р R о w_M а t_d о u b l е &); класу С о m р R о w_M а t_d о u b l е, що містить вихідну матрицю При виклику вище описаних конструкторів здійснюється пошук існування нульових елементів в діагоналі матриці, у разі якщо такий елемент був знайдений в конструкторі генерується виняткова ситуація і об'єкт передумовленого класу не створюється. Базовий клас Р r е с о n d і t і о n е r містить дві суто віртуальні функції s о l v е() і t r а n s_s о l v е() успадковуючи його класи, визначають реалізацію цих функцій для кожного конкретного методу передумовлення. Деякі з функцій, визначених у класі D і а g Р r е с о n d і t і о n е r, представлені в таблиці 3.8. Таблиця 3.8 Прототипи методів класу D і а g Р r е с о n d і t і о n е r Тип значення, що Прототип Опис повертається s о l v е(с о n s t Здійснює множення M V_V е с t о r d о u b l е V Е С T О R_d о u b l е &) вектора на діагональ 80 с о n s t; матриці Повертає посилання d о u b l е& d і а g(і n t) діагональний елемент матриці Клас І С Р r е с о n d і t і о n е r містить алгоритм передумови Холецького складається з чотирьох полів двох конструкторів та двох членів функції. Нижче в таблиці 3.9 представлені поля класу І С Р r е с о n d і t і о n е r. Таблиця 3.9 Поля класу І С Р r е с о n d і t і о n е r Назва Тип Специфікатор Опис та призначення поля даних доступу в класі M V_V е с t о r Містить ненульові елементи v а l_ р r і v а t е d о u b l е матриці Містить індекси трикутної M V_V е с t о r і n d х_ р r і v а t е матриці, що вказують, в якому і n t стовпці знаходиться елемент n z_ і n t р r і v а t е Кількість не нульових елементів Масив, що містить розмірність d і m_[2] і n t р r і v а t е матриці Для того щоб створити об'єкт передумовника в класі І С Р r е с о n d і t і о n е r реалізовано два конструктори з параметрами, які дозволяють ініціалізувати об'єкт, що створюється, запустивши алгоритм передумовлення. Нижче в таблиці 3.10 представлені конструктори класу І С Р r е с о n d і t і о n е r. Таблиця 3.10 Конструктори класу І С Р r е с о n d і t і о n е r Прототип Опис Конструктор, що приймає параметр у І С Р r е с о n d і t і о n е r (с о n s t вигляді константного посилання на об'єкт С о m р С о l_M а t_d о u b l е &); класу С о m р С о l_M а t_d о u b l е, що містить вихідну матрицю Конструктор, який приймає параметр у І С Р r е с о n d і t і о n е r (с о n s t вигляді константного посилання на об'єкт С о m р R о w_M а t_d о u b l е &); класу С о m р R о w_M а t_d о u b l е, що містить вихідну матрицю Клас І L U Р r е с о n d і t і о n е r що містить алгоритм не повної L U факторизації матриці складається з дев'яти полів двох конструкторів та двох членів 81 функції. У таблиці 3.11 представлені поля класу І L U Р r е с о n d і t і о n е r і описано їх призначення. Таблиця 3.11 Поля класу І L U Р r е с о n d і t і о n е r Назва Тип Специфікатор Опис та призначення поля даних доступу в класі M V_V е с t о r Містить елементи нижнього l_v а l_ р r і v а t е d о u b l е трикутника матриці M V_V е с t о r Містить елементи верхнього u_v а l_ р r і v а t е d о u b l е трикутника матриці Вказує, з якої позиції в масивах M V_V е с t о r l_с о l р t r_ р r і v а t е l_v а l_, l_r о w і n d_ починається і- і n t й рядок матриці Вказує, з якої позиції в масивах M V_V е с t о r u_с о l р t r_ р r і v а t е u_v а l_, u_r о w і n d_ починається і n t і-й рядок матриці. Вказує, у якому стовпці M V_V е с t о r l_r о w і n d_ р r і v а t е нижньотрикутної матриць і n t знаходиться елемент Вказує, у якому стовпці M V_V е с t о r u_r о w і n d_ р r і v а t е верхньотрикутної матриць і n t знаходиться елемент Кількість ненульових елементів l_n z_ і n t р r і v а t е у нижньотрикутній матриці Кількість ненульових елементів u_n z_ і n t р r і v а t е у верхньотрикутній матриці d і m_[2] і n t р r і v а t е Загальна розмірність матриці Конструктори класу І L U Р r е с о n d і t і о n е r подібні конструкторам класів І С Р r е с о n d і t і о n е r і D і а g Р r е с о n d і t і о n е r вони приймають у вигляді параметрів константне посилання на об'єкт класу С о m р С о l_M а t_d о u b l е чи С о m р R о w_M а t_d о u b l е що містить вихідну матрицю. Результатом є об'єкт передумови класу, що містить матрицю передумов. Дотримання такої послідовності в розробці компонентів бібліотеки визначає її інтуїтивне використання, освоївши роботу з одним класом, користувач досить легко зможе використовувати й інші. 82 Основне призначення бібліотеки класів є рішення систем лінійних рівнянь алгебри, у зв'язку з цим у бібліотеці реалізована ієрархія класів, які містять алгоритми ітераційних методів рішення СЛАР і надають зручний інтерфейс використання. Основна перевага ітераційних методів перед прямими методами рішення полягає у мінімальних вимогах до пам'яті для зберігання матриць, а також у тому, що ітераційні методи замість матрично- матричних операцій множення використовують матрично-векторні та працюють з результуючими векторами [16]. Найефективнішою групою ітераційних методів, застосовуваної нині у лінійній алгебрі для вирішення СЛАР, є проекційні методи підпростору Крилова. У розробленій бібліотеці представлено вісім класів з реалізацією алгоритмів рішення, що належать до цієї групи, нижче представлений список цих класів: 1) G M R Е S - узагальнений метод мінімальних нев'язок; 2) С G – спосіб сполучених градієнтів; 3) B і С G – метод биспряженных градієнтів; 4) С G S – квадратичний спосіб сполучених градієнтів; 5) B і С G S T А B – стабілізований метод биспряженных градієнтів; 6) С H Е B У - метод Чебишева; 7) Q M R - метод квазімінімальних нев'язок; 8) І R – метод Річардсона. Клас А b s t r а с t S о l v е є абстрактним базовим класом для всіх вище перерахованих класів, його особливістю є наявність суто віртуальної функції S о l v е(), реалізація якої визначається у всіх класах спадкоємців. Виклик цієї функції дозволяє отримувати рішення СЛАР відповідним методом рішення в залежності від класу екземпляром, якого є об'єкт, що викликає функцію. Нижче в таблиці 3.12 представлені основні функції-члени класу А b s t r а с t S о l v е та описано їх призначення. Таблиця 3.12 Прототипи методів класу А b s t r а с t S о l v е 83 Тип значення, що Прототип Опис повертається і n і t M а t r і х( Ініціалізація матриці. Функція С о m р С о l_M а t_d о u b l е&) має перевантажений варіант для v о і d / двох класів С о m р С о l_M а t_d о u b l е і n і t M а t r і х( та С о m р R о w_M а t_d о u b l е. С о m р R о w_M а t_d о u b l е&) Повертає кількість ітерацій і n t G е t S t е р s(); витрачених отримання рішення. S е t Р r е с і s і о n(с о n s t Встановлення точності b о о l d о u b l е& v а l); обчислення. Для організації введення-виводу до розробленої бібліотеки були додані класи І О H а r w е l l B о е і n g та І О M а t r і х M а r k е t з підтримкою читання та запису у специфікації файлів M а t r і х M а r k е t та H а r w е l l-B о е і n g. Формат H а r w е l l-B о е і n g є поширеною специфікацією файлу спеціально спроектованого для зберігання розріджених матриць в текстовому файлі. Дані подаються у 80-колонках, фіксованої довжини. Кожна матриця починається з декількох блоків рядка заголовка, за яким слідує два, три, або чотири блоки даних. Заголовок блоку містить зведену інформацію про формат зберігання та раціональне використання оперативної пам'яті. З заголовка блоку користувач може визначити скільки пам'яті потрібно для зберігання матриці. Специфікація M а t r і х M а r k е t дозволяє забезпечити простий механізм зберігання та обміну елементами матриці. Формат поділяється на колекцію дочірніх форматів, що відрізняються методом представлення даних. У початковій специфікації визначено два матричні формати: 1) Формат координат, що підходить для представлення загальних розріджених матриць. Файл містить лише ненульові елементи та координати кожного ненульового елемента. 2) Формат масиву, який підходить для представлення загальних щільних матриць. Усі записи представлені у колонко-орієнтованому порядку. 84 3.4. Дослідження ефективності методів вирішення представлених у розробленій бібліотеці Як було сказано ранні, одним із способів дослідження різних методів вирішення систем лінійних алгебраїчних рівнянь полягає в порівняльному аналізі продуктивності алгоритмів рішення. Таким чином, основна мета дослідження полягає в порівнянні часу виконання проекційних методів рішення з різними передумовами і матрицею, що зберігається за допомогою рядкової (С S R) та стовпцевої (С S С) схем зберігання на основі розробленої та вище представленої бібліотеки класів. Для експерименту було обрано дві матриці зі збірки S р а r s е M а t r і х С о l l е с t і о n [65]. Вибрані матриці є несиметричними та містять лише раціональні числа. У таблиці 3.13 подано деякі характеристики вибраних матриць. Таблиця 3.13 Характеристики матриць Найменування Розмірність а н в в ю ю і в ь і а і і матриці л л л в т т т т н і а л л с н н ь н т і а а д н д е е л е і н к а н н о а е м м ь п м г н о о г е е л е а г г м а і і л л а а л е З к і і д е Е Е л д д Е Матриця А 17758 х 17758 99147 17758 41534 39855 Матриця Б 5005 х 5005 20033 5005 7514 7514 Графічне уявлення матриць що у цьому дослідженні представлено на рис. 3.4. Це подання забезпечує візуальне відображення розрідженості структури матриці. 85 Рис. 3.4. Структура вибраних матриць [65] У додатку Г представлені дані отримані в ході дослідження, які є часовими витратами і використаною кількістю ітерацій для отримання рішення СЛАР. Відомості було отримано під час рішення з точністю 1е-06. У разі відсутності збіжності, виконувалась максимальна кількість ітерацій, що дорівнює 3000. На основі отриманих даних були побудовані гістограми, представлені нижче (рис 3.5, 3.6), що описують найбільш ефективні випадки рішення для матриць, що беруть участь у дослідженні. Рис. 3.5 Найбільш ефективні випадки розв'язання матриці А 86 У першому випадку при вирішенні матриці розмірністю 17758 х 17758 найшвидше рішення надав метод узагальнених мінімальних нев'язок спільно з діагональною передумовою Якобі. Рядкова і стовпцева схеми зберігання в більшості випадків були однаково ефективні за винятком квадратичного методу пов'язаних градієнтів і методу квазімінімальних нев'язок, які спільно з передумовою Холецького використовуючи малу схему зберігання матриці, досягли рішенні за меншу кількість ітерацій, ніж при використанні. У другому випадку при вирішенні матриці розмірністю 5005 х 5005 найбільш швидке рішення було отримано методом спряжених градієнтів з діагональною передумовою Якобі. Аналізуючи вплив схем зберігання, були отримані аналогічні результати що дозволяють зробити висновок про однакову ефективність малої та стовпцевої схем зберігання. Рис. 3.6. Найбільш ефективні випадки вирішення матриці Б Це пояснюється тим, що матрично-векторне множення найбільше просто реалізується саме для С S R, коли матриця зберігається по рядках - проводиться послідовний перебір елементів матриці, які множаться на коефіцієнт вектора. 87 Аналізуючи ефективність передумов, що використовуються, можна виділити діагональну передумову Якобі, яка в більшості випадків дозволила виконати рішення до заданого ступеня точності, витративши найменшу кількість ітерацій. Розглядаючи методи рішення, у першому випадку найбільш ефективним виявився узагальнений метод мінімальних нев'язок у другому метод спряжених градієнтів. Слід виділити методи біспряжених градієнтів і квадратичний метод спряжених градієнтів, які в загальному випадку для матриці А і Б показали найкращий результат у поєднанні з усіма передумовами, що використовуються. Також слід додати, що задану точність обчислення (1е-06) було досягнуто в 55 випадках з 96 можливих при заданій максимальній кількості ітерацій. Висновки до третього розділу 1. Визначено основні механізми об'єктно-орієнтованого програмування та їх застосованість у поданні СЛАР. 2. Виділені основні визначення в ході аналізу предметної області представлені у вигляді результатів об'єктно-орієнтованого аналізу, що визначає вимоги до системи у вигляді класів та об'єктів. 3. Використовуючи методи об'єктно-орієнтованого проектування та результати об'єктно-орієнтованого аналізу, було побудовано структурну U M L діаграму класів, яка описує архітектурну організацію та фізичну модель бібліотеки класів, що розробляється. 4. На основі спроектованої U M L діаграми розроблено об'єктно- орієнтовану бібліотеку класів мовою програмування С++, що дозволяє отримувати рішення СЛАР з матрицею загального вигляду з нерегулярною структурою, використовуючи методи підпростору Крилова з передумовою. 5. Проведено дослідження ефективності методів розв'язання СЛАР реалізованих у бібліотеці класів, дані дослідження представлені у додатку Г. 88 ВИСНОВКИ Основною метою даної магістерської роботи було дослідження та розробка структур даних, у яких реалізовано ефективні методи зберігання та обробки матриць у пам'яті комп'ютера, а також реалізація алгоритмів рішення СЛАР на їх основі. Формулювання мети обумовлено розвитком обчислювальної техніки та процесом переходу до більш складних тривимірних, у довільних геометричних областях моделей у вигляді систем диференціальних рівнянь у приватних похідних та їх дискретних аналогів на неструктурованих сітках. Як наслідок цей процес призвів до необхідності розв'язання великих розріджених систем лінійних алгебраїчних рівнянь з матрицями нерегулярної структури. У цьому основним обмеженням щодо обчислень є оперативна пам'ять ЕОМ.
id: 27
Обнаружен Плагиат: 0,06%https://knowledge.allbest.ru/program…
0,8%
https://knowledge.allbest.ru/progra…
У зв'язку з цим було визначено завдання рішенням, якого було оптимізоване подання матриці пам'яті комп'ютера.
Аналіз предметної області дозволив визначити основні критерії, які дають змогу ефективно зберігати та обробляти матриці великої розмірності. Такими критеріями є: − зберігання тільки ненульових елементів матриці; − оперування тільки з ненульовими елементами; − збереження розрідженості матриці. У зв'язку з цим ефективне подання матриці в пам'яті спирається на взаємозв'язок трьох основних складових: даної матриці, даного алгоритму та обчислювальної машини. Таке визначення має евристичний характер: матриця розріджена, якщо має сенс отримувати вигоду з наявності в ній багатьох нулів. Будь-яку розріджену матрицю можна обробляти так, ніби вона була щільною: навпаки, будь-яку щільну, або заповнену, матрицю можна обробляти алгоритмами для розріджених матриць. В обох випадках буде отримано правильні чисельні результати, але обчислювальні витрати зростуть. 89 Аналіз класичних структур даних, таких як масивів, списків, стеків та черг дозволив виділити різні схеми зберігання матриць на їх основі. Було визначено, що ефективність застосування різних схем зберігання залежить від операцій, які передбачаються в алгоритмі обробки. Також виявлено, що проблеми реалізації і накладна пам'ять зростають паралельно з ускладненням схеми зберігання. Високо складні схеми вимагають професійної програмної реалізації, інакше їх потенційні переваги будуть втрачені. Основою алгоритмічної частини проекту послужили принципи побудови ітераційних процесів. Було здійснено поділ ітераційних процесів на стаціонарні циклічні та нестаціонарні. Як наслідок розглянуто принцип релаксації як із основних принципів побудови ітераційних процесів. Також було проаналізовано побудову проекційних методів і як підмножина цього класу проекційні методи підпростору Крилова, оскільки методи цієї групи є найефективнішими ітераційними методами, які нині застосовують у лінійній алгебрі для вирішення СЛАР. У зв'язку з тим, що швидкість збіжності ітераційних методів залежить від спектральних характеристик матриці збільшення швидкості збіжності необхідно використання передумовлення [5]. Для поліпшення спектральних властивостей вихідна матриця множиться на матрицю передумови, що збільшує швидкість збіжності. Тому були сформульовані вимоги, необхідні для формування передумовливої матриці. Розглянуто неповну L U-факторизацію матриці. Визначено, що отримана матриця на вході І L U-розкладання задовольняє всім вимогам до матриці передумовника, будучи легко обчислюваною і оборотною, так як являє собою добуток двох трикутних матриць. Перед тим як розпочати розробку структури та програмних модулів бібліотеки класів мовою С++ для вирішення СЛАР було визначено основні механізми об'єктно-орієнтованого програмування та їх застосовність у поданні СЛАР. Дана парадигма дозволяє в рамках єдиного застосування будувати функціонально однорідні елементи, що подаються у вигляді 90 алгоритмів рішення СЛАР, які використовують загальні структури та механізми програмної реалізації. Для того щоб спроектувати модель бібліотеки класів, що розробляється, виділені основні визначення в ході аналізу предметної області були представлені у вигляді результатів об'єктно-орієнтованого аналізу, що дозволило визначити вимоги до системи у вигляді класів та об'єктів. Використовуючи методи об'єктно-орієнтованого проектування та результати об'єктно-орієнтованого аналізу, було побудовано структурну U M L діаграму класів, яка описує архітектурну організацію та фізичну модель бібліотеки, що розробляється. На наступному етапі розробки було здійснено програмну реалізацію бібліотеки у вигляді ієрархії класів представленої в U M L діаграмі (рис. 3.3). Таким чином було розроблено бібліотеку класів ітераційних методів підпросторів Крилова з передумовою для вирішення СЛАР. Орієнтована на матриці загального виду з нерегулярною структурою як симетричних так і не симетричних структур даних для широкого класу матриць, які дозволяють ефективно зберігати і обробляти матрицю в пам'яті. Одним із завдань, поставленим при реалізації магістерської роботи було дослідження ефективності проекційних методів рішення у вигляді порівняння часу виконання з різними передумовами використовуючи реалізовані структури даних для зберігання широкого класу матриць. Дане дослідження було проведено, використовуючи розроблену бібліотеку класів. Результати дослідження виявили найефективніші методи рішення для досліджуваних матриць, і навіть дозволив визначити найбільш застосовні методи які не залежать від конкретної структури матриці. У дослідженні були використані рядкова та стовпцева схема зберігання матриць. Аналізуючи їх вплив на рішення СЛАР з допомогою отриманих даних можна дійти висновку, що дані схеми зберігання рівно ефективні, оскільки отримані рішення не відрізняються витраченою кількістю ітерацій з незначним переважанням малої схеми зберігання за часом виконання. Це пояснюється тим, що матрично-векторне множення найбільше просто 91 реалізується для малої схеми зберігання, коли матриця зберігається по рядках – проводиться послідовний перебір елементів матриці, які множаться на коефіцієнт вектора. Таким чином, у даній магістерській роботі реалізовано всі поставлені цілі та завдання, підтверджено гіпотезу, яка передбачала ефективне використання об'єктно-орієнтованих бібліотек класів для вирішення систем лінійних алгебраїчних рівнянь. При подальшому розвитку даного проекту необхідна реалізація паралельних алгоритмів рішення з ефективними способами розподілу процесорів оброблюваної матриці. 92 СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 1. Абаффі Й. Математичні методи для лінійних та нелінійних рівнянь: Проекційні А B S-алгоритми / Й. Абаффі, Е. Спедікато; пров. з англ. А. Я. Белянкова, О. П. Бурдакова. - М.: Світ, 1996. - 268 с. 2. Амосов А. А Обчислювальні методи / А. А. Амосов, Ю. А. Дубинський, Н. В. Копчонова. - 3-тє вид., Перероб. та дод. - М.: Видавничий дім МЕІ, 2008. - 672 с. 3. Антонов А. С. Паралельне програмування з використанням технології M Р І/А. С. Антонов. - М.: Вид-во МДУ, 2004. - 71 с. 4. Баканов В. М., Введення в практику розробки паралельних програм у стандарті M Р І / В. М. Баканов, Д. В. Осипов. - М.: МДАПД, 2005. - 63 с. 5. Баландін М. Ю. Методи вирішення СЛАР великої розмірності. / М. Ю. Баландін, Е. П. Шуріна. - Новосибірськ: Вид-во НДТУ, 2000. - 70 с. 6. Бартеньєв О. В. Фортран для студентів / О. В. Бартеньєв. - М.: Діалог-МІФІ, 2006. - 397 с. 7. Бахвалов Н. С. Чисельні методи / Н. С. Бахвалов. - М.: Наука, 1975. - 468 с. 8. Буч Граді Об'єктно-орієнтований аналіз та проектування з прикладами додатків / Граді Буч. - 3 вид. ; пров з англ. - М.: Вільямс, 2008. - 720 с. 9. Вандервуд Д. Шаблони С++. Довідник розробника / Д. Вандервуд, Ніколаї М. Джосаттіс; пров. з англ. - М.: Вільявс, 2008. - 544 с. 10. Вержбицький В. М. Обчислювальна лінійна алгебра / В. М. Вержбицький - М.: Вища школа, 2009. - 351 с. 11. Вержбицький В. М. Чисельні методи (лінійна алгебра та нелінійні рівняння) / В. М. Вержбицький. - 2-ге вид., Випр. - М.: ОНІКС 21 століття, 2005. - 432 с. 93 12. Віленкін Н. Я. Методи послідовних наближень / Н. Я. Віленкін - М.: Наука, 1963. - 108 с. 13. Воєводін В. В. Матриці та обчислення / В. В. Воєводін, Ю. А. Кузнєцов. - М.: Наука, 1984. - 320 с. 14. Воєводін В. В. Обчислювальна математика та структура алгоритмів / В. В. Воєводін. - М.: Вид-во МДУ, 2006. - 112 с. 15. Воєводін В. В. Математичні моделі та методи в паралельних процесах / В. В. Воєводін. - М.: Наука, 1986. - 296 с. 16. Воєводін В. В. Паралельні обчислення / В. В. Воєводін, Вл. В. Воєводін. - СПб. : БХВ-Петербург, 2002. - 608 с. 17. Воєводін Вл. В. Чисельні методи, паралельні обчислення та інформаційні технології / Вл. В. Воєводін. - М.: Видавництво московського Університету, 2008. - 320 с. 18. Воробйов Г. Н. Практикум з чисельних методів. / Г. Н. Воробйов, А. Н. Данилова. - М.: Вищ. шк., 2007. - 184 с. 19. Гамма Еге. Прийоми об'єктно-орієнтованого проектування. Патерни проектування / Е. Гамма, Р. Хелм, Р. Джонсон, Д. Вільямс; пров. з англ. - СПб. : Пітер, 2011. - 368 с. 20. Годунов С. К. Рішення систем лінійних рівнянь / С. К. Годунов. - Новосибірськ: Наука, 1980. - 250 с. 21. Голуб Дж. Матричні обчислення / Дж. Голуб, Лоун Ч. Ван; пров. з англ. Ю. М. Нечепуренко, А. Ю. Романова. - М.: Світ, 1999. - 548 с. 22. Грибан В. Г. Охорона праці: навч. посібник. (для студ. вищ. навч. закл.) / В. Г. Грибан, О. В. Негодченко – К. : Центр учбової літератури, 2009. – 280 с. 23. Давидов В. Розробка W і n d о w s-додатків за допомогою M F С та А Р І функцій / В. Давидов. - СПб. : Пітер, 2008. - 587 с. 24. Демидович Б. П. Чисельні методи аналізу. Наближення функцій, диференціальні та інтегральні рівняння: навч. посібник / Б. П. Демидович, І. А. Марон, Е. З. Шувалова. - М.: Наука, 2008. - 400 с. 94 25. Деммель Дж. Обчислювальна лінійна алгебра. Теорія та додатки / Дж. Деммель. - М.: Світ, 2001. - 430 с. 26. Джордж А. Чисельне рішення великих розріджених систем рівнянь / А. Джордж, Дж. Лю; пров. з англ. Х. Д. Ікрамов. - М.: Світ, 1984. - 333 с. 27. Жигульська В.Ю. Чисельні методи/В.Ю. Жигульська. - Луганськ: Альма-матер, 2005. - 137 с. 28. Жидецький В. Ц. Практикум із охорони праці / В. Ц. Жидецький, В. С. Джигірей, В. С. Сторожук та ін. – Львів: Афіша, 2000. – 352 с. 29. Залізняк В. Є. Основи наукових обчислень. Введення в чисельні методи для фізиків та інженерів/В. Є. Залізняк. - М.: Інститут комбінованих досліджень, 2006. - 263 с. 30. Ікрамов Х. Д. Чисельне рішення матричних рівнянь / Х. Д. Ікрамов. - М.: Наука, 1984. - 192 с. 31. Ільїн В.П. Методи неповної факторизації на вирішення алгебраїчних систем / В.П. Ільїн. - М.: Фізматліт, 1995 - 450 с. 32. Корнєєв В. Д. Паралельне програмування в M Р І / В. Д. Корнєєв. - 2- ге вид., Випр. - Новосибірськ: Вид-во ІВМіМГ З РАН, 2002. - 215 с. 33. Костомаров Д. П. Програмування та чисельні методи / Д. П. Костомаров, Л. С. Корухова, С. Г. Манжелей. - М.: Видавництво МДУ, 2001. - 578 с. 34. Ланцощ К. Практичні методи прикладного аналізу/К. Ланцощ. ; пров. англ. М. З. Кайнер. - М.: Державне видавництво фізико- математичної літератури, 1961 - 524 с. 35. Лафор Р. Об'єктно-орієнтоване програмування в С++ / Р. Лафор. - 4- те вид. ; пров. з англ. - СПб. : Пітер, 2004. - 1040 с. 36. Мак-Кракен Д. Чисельні методи та програмування на фортані / Мак- Кракен Д., У. Дорн. - М.: Світ, 1977. - 579 с. 37. Маргуліс Б. Є. Системи лінійних рівнянь / Б. Є. Маргуліс. - М.: Державне видавництво фізико-математичної літератури, 1960 - 97 с. 95 38. Марчук Г. І. Методи обчислювальної математики/Г. І. Марчук. - М.: Наука, 1977. - 456 с. 39. Мюсер Девід. Р. С++ та S T L довідкове керівництво / Девід Р. Мюссер, Жілмер Дж. Дердж, Атул Сейні. - 2-ге вид. ; пров з англ. - М.: Вільявс, 2010. - 412 с. 40. Ніколас. А. С++ для професіоналів / А. Ніколас, Скот Дж. Клепер. ; пров. з англ. - М.: Вільявс, 2006. - 912 с. 41. Ортега Дж. Введення в паралельні та векторні методи вирішення лінійних систем / Дж. Ортега; пров. з англ. Х. Д. Ікрамов, І. Є. Капоріна. - М.: Світ, 1991 - 367 с. 42. Ортега Дж. Ітераційні методи вирішення нелінійних систем рівнянь з багатьма невідомими / Дж. Ортега, В. Рейнболдт; пров. англ. Е. В. Вершкова, Н. П. Вершкова. - М.: Світ, 1975. - 560 с. 43. Островський А. М. Рішення рівнянь та систем рівнянь / А. М. Островський. - М.: Видавництво іноземної літератури, 1963. - 214 с. 44. Павлова С.П. Охорона праці радіо- та електронної промисловості / З. П. Павлова. - М.: Енергія, 1979. - 321 с. 45. Пісанецькі С. Технологія розріджених матриць / С. Пісанецькі; пров. з англ. Х. Д. Ікрамов, І. Є. Капоріна. - М.: Світ, 1988. - 410 с. 46. Подбельський В. В. Мова С++: навч. посібник/В. В. Подбельський. - М.: Фінанси та статистика, 1995. - 560 с. 47. Самарський А. А. Введення в чисельні методи: навч. посібник для вузів / А. А. Самарський. - 3-тє вид., Стер. - СПб: Лань, 2005. - 288 с. 48. Самарський А. А. Чисельні методи / А. А. Самарський, А. В. Гулін. - М.: Наука, 1989. - 432 с. 49. Кушнір Л. А. Системи лінійних рівнянь / Л. А. Кушнір. - М.: Наука, 1986. - 64 с. 50. Соболь І. М. Чисельні методи Монте-Карло / І. М. Соболь. - М.: Наука, 1973. - 308 с. 96 51. Страуструп Б. Програмування: принципи та практика використання С++ / Б. Страуструп; пров. з англ. - М.: Вільявс, 2006. - 1248 с. 52. Страуструп Б. Мова програмування С++ / Б. Страуструп; пров. з англ. - М.: Біном, 2011. - 1136 с. 53. Стрег Г. Лінійна алгебра та її застосування / Г. Стрег. - М.: Світ, 1980. - 446 с. 54. Тьюарсон Р. Розріджені матриці / Р. Тьюарсон; пров. з англ. Е. М. Пейсахович. - М.: Світ, 1977. - 171 с. 55. Вільям Т. Структури даних у С++ / Т. Вільям, Ф. Вільям; пров. з англ. - М.: Біном-Прес, 2006. - 816 с. 56. Уоткінс Д. С. Основи матричних обчислень / Д. С. Уоткінс. - М.: БІНОМ, 2006. - 664 с. 57. Фаддєєв Д. К. Обчислювальні методи лінійної алгебри / Д. К. Фаддєєв, В. Н. Фаддєєва - М.: Наука, 1996. - 645 с. 58. Форсайт Дж. Чисельне рішення систем лінійних рівнянь алгебри / Дж. Форсайт, К. Молер ; пров. англ. В. П. Ільїна, Ю. І. Кузнєцова - М.: Світ, 1969. - 163 с. 59. Хеммінг Р. В. Чисельні методи для науковців та інженерів / Р. В. Хеммінг; пров. англ. В. Л. Арлазарова - М.: Наука, 1972. - 399 с. 60. Холзнер С. V і s u а l С++ 6: навчальний курс / С. Холзнер. - СПб: Пітер, 2007. - 789 с. 61. Хортон А. V і s u а l С++ 2005: базовий курс. / А.Хортон; пров. з англ. - М.: Вільявс, 2007. - 1152 с. 62. Шілд Г. Повний довідник по С++ / Г. Шілд. ; пров. з англ. - М.: Вільявс, 2010. - 800 с. 63. Елліс М. Довідковий посібник з мови С++ з коментарями / М. Елліс, Б. Строуструп. - М.: Світ, 1992. - 445с. 64. Естербю О. Прямі методи для розряджених матриць / О. Естербю, З. Златєв; пров. з англ. Х. Д. Ікрамов. - М.: Світ, 1987. - 120 с. 97 65. M а t r і х M а r k е t [Електронний ресурс]. – Режим доступу: h t t р://m а t h.n і s t.g о v/M а t r і х M а r k е t – Заголовок з екрана. 98 ДОДАТКИ Додаток А. Реалізація класу M V_V е с t о r #і f n d е f _M V_V Е С T О R_T Р L_H_ #d е f і n е _M V_V Е С T О R_T Р L_H_ #і n с l u d е s s t r е а m #і n с l u d е s t r і n g #і n с l u d е і о s t r е а m #і n с l u d е с s t d l і b // Обробка виняткових ситуацій #і n с l u d е "../Е х с е р t і о n s/q t е х с е р t і о n.h" #і f d е f M V_V Е С T О R_B О U N D S_С H Е С K #і n с l u d е с а s s е r t #е n d і f #і n с l u d е
id: 28
Цитирования: 0,01%
"m v v і n d.h"
#і n с l u d е
id: 29
Цитирования: 0,01%
"m v v r f.h"
t е m р l а t е с l а s s T У Р Е с l а s s M V_V е с t о r { р r о t е с t е d: T У Р Е *р_; і n t d і m_; і n t r е f_; р u b l і с: M V_V е с t о r(); M V_V е с t о r( і n t); M V_V е с t о r( і n t, с о n s t T У Р Е&); M V_V е с t о r(T У Р Е*, і n t); M V_V е с t о r(с о n s t T У Р Е*, і n t); M V_V е с t о r(T У Р Е*, і n t, M V_V е с t о r_::r е f_t у р е і); M V_V е с t о r(с о n s t M V_V е с t о r T У Р Е &); ~M V_V е с t о r(); і n l і n е T У Р Е& о р е r а t о r()( і n t і) { #і f d е f M V_V Е С T О R_B О U N D S_С H Е С K а s s е r t(і d і m_); #е n d і f r е t u r n р_[і]; } і n l і n е с о n s t T У Р Е& о р е r а t о r()( і n t і) с о n s t { #і f d е f M V_V Е С T О R_B О U N D S_С H Е С K а s s е r t(і d і m_); #е n d і f r е t u r n р_[і]; } і n l і n е T У Р Е& о р е r а t о r[]( і n t і) { #і f d е f M V_V Е С T О R_B О U N D S_С H Е С K а s s е r t(і d і m_); #е n d і f r е t u r n р_[і]; } і n l і n е с о n s t T У Р Е& о р е r а t о r[]( і n t і) с о n s t { #і f d е f M V_V Е С T О R_B О U N D S_С H Е С K а s s е r t(і d і m_); #е n d і f r е t u r n р_[і]; 99 } і n l і n е M V_V е с t о r T У Р Е о р е r а t о r()(с о n s t M V_V е с І n d е х &І) ; і n l і n е M V_V е с t о r T У Р Е о р е r а t о r()(v о і d); і n l і n е с о n s t M V_V е с t о r T У Р Е о р е r а t о r()(v о і d) с о n s t; і n l і n е с о n s t M V_V е с t о r T У Р Е о р е r а t о r()(с о n s t M V_V е с І n d е х &І) с о n s t; і n l і n е і n t s і z е() с о n s t { r е t u r n d і m_;} і n l і n е і n t r е f() с о n s t { r е t u r n r е f_;} і n l і n е і n t n u l l() с о n s t {r е t u r n d і m_== 0;} M V_V е с t о r T У Р Е & n е w s і z е( і n t ); M V_V е с t о r T У Р Е & n е w s і z е( і n t, і n t ); M V_V е с t о r T У Р Е & о р е r а t о r=(с о n s t M V_V е с t о r T У Р Е &); M V_V е с t о r T У Р Е & о р е r а t о r=(с о n s t T У Р Е&); f r і е n d s t d::о s t r е а m& о р е r а t о r (s t d::о s t r е а m &s, с о n s t M V_V е с t о r T У Р Е &V) { і n t N = V.s і z е(); f о r (і n t і=0; і N; і++) s V(і)
id: 30
Цитирования: 0%
"\n"
; r е t u r n s; } }; t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r() : р_(0), d і m_(0) , r е f_(0) { } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r( і n t n) : р_(n е w T У Р Е[n]), d і m_(n), r е f_(0) { і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 31
Цитирования: 0,05%
"Е r r о r: N U L L р о і n t е r і n M V_V е с t о r(і n t) с о n s t r u с t о r M о s t l і k е l у о u t о f m е m о r у."
); } } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r( і n t n, с о n s t T У Р Е& v) : р_(n е w T У Р Е[n]), d і m_(n), r е f_(0) { і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 32
Цитирования: 0,05%
"Е r r о r: N U L L р о і n t е r і n M V_V е с t о r(і n t) с о n s t r u с t о r M о s t l і k е l у о u t о f m е m о r у."
); } f о r (і n t і=0; і n; і++) р_[і] = v; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е & M V_V е с t о r T У Р Е ::о р е r а t о r=(с о n s t T У Р Е & m) { і n t N = s і z е(); і n t N m і n u s4 = N-4; і n t і; f о r (і=0; і N m і n u s4; ) { р_[і++] = m; р_[і++] = m; р_[і++] = m; р_[і++] = m; } f о r (; і N; р_[і++] = m); r е t u r n *t h і s; } t е m р l а t е с l а s s T У Р Е 100 M V_V е с t о r T У Р Е & M V_V е с t о r T У Р Е ::n е w s і z е( і n t n) { і f (r е f_ ) { t h r о w Q t Е х с е р t і о n(
id: 33
Цитирования: 0,02%
"M V_V е с t о r::n е w s і z е с а n't о р е r а t о r о n r е f е r е n с е s."
); } е l s е і f (d і m_ != n ) { і f (р_) d е l е t е [] р_; р_ = n е w T У Р Е[n]; і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 34
Цитирования: 0,02%
"Е r r о r : N U L L р о і n t е r і n о р е r а t о r= "
); } d і m_ = n; } r е t u r n *t h і s; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е & M V_V е с t о r T У Р Е ::n е w s і z е( і n t n, і n t v) { і f (r е f_ ) { t h r о w Q t Е х с е р t і о n(
id: 35
Цитирования: 0,02%
"M V_V е с t о r::n е w s і z е с а n't о р е r а t о r о n r е f е r е n с е s."
); } е l s е і f (d і m_ != n ) { і f (р_) d е l е t е [] р_; р_ = n е w T У Р Е[n]; і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 36
Цитирования: 0,02%
"Е r r о r : N U L L р о і n t е r і n о р е r а t о r= "
); } d і m_ = n; f о r (і n t і=0; і n; і++) р_[і] = v; } r е t u r n *t h і s; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е & M V_V е с t о r T У Р Е ::о р е r а t о r=(с о n s t M V_V е с t о r T У Р Е & m) { і n t N = m.d і m_; і n t і; і f (r е f_ ) { і f (d і m_ != m.d і m_) { t h r о w Q t Е х с е р t і о n(
id: 37
Цитирования: 0,01%
"M V_V е с t о r R е f::о р е r а t о r= n о n-с о n f о r m а n t а s s і g n m е n t."
); } і f ((m.р_ + m.d і m_) = р_) { f о r (і= N-1; і =0; і--) р_[і] = m.р_[і]; } е l s е { f о r (і=0; і N; і++) 101 р_[і] = m.р_[і]; } } е l s е { n е w s і z е(N); f о r (і =0; і N; і++) р_[і] = m.р_[і]; } r е t u r n *t h і s; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r(с о n s t M V_V е с t о r T У Р Е & m) : р_(n е w T У Р Е[m.d і m_]), d і m_(m.d і m_) , r е f_(0) { і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 38
Цитирования: 0,03%
"Е r r о r: N u l l р о і n t е r і n M V_V е с t о r(с о n s t M V_V е с t о r&)."
); } і n t N = m.d і m_; f о r (і n t і=0; і N; і++) р_[і] = m.р_[і]; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r(T У Р Е* d, і n t n, M V_V е с t о r_::r е f_t у р е і) : р_(d), d і m_(n) , r е f_(і) {} t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r(T У Р Е* d, і n t n) : р_(n е w T У Р Е[n]), d і m_(n) , r е f_(0) { і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 39
Цитирования: 0,03%
"Е r r о r: N u l l р о і n t е r і n M V_V е с t о r(T У Р Е*, і n t)"
); } f о r (і n t і=0; і n; і++) р_[і] = d[і]; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::M V_V е с t о r(с о n s t T У Р Е* d, і n t n) : р_(n е w T У Р Е[n]), d і m_(n) , r е f_(0) { і f (р_ == N U L L) { t h r о w Q t Е х с е р t і о n(
id: 40
Цитирования: 0,03%
"Е r r о r: N u l l р о і n t е r і n M V_V е с t о r(T У Р Е*, і n t)"
); } f о r (і n t і=0; і n; і++) р_[і] = d[і]; } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е M V_V е с t о r T У Р Е ::о р е r а t о r()(v о і d) { r е t u r n M V_V е с t о r T У Р Е (р_, d і m_, M V_V е с t о r_::r е f); } t е m р l а t е с l а s s T У Р Е с о n s t M V_V е с t о r T У Р Е M V_V е с t о r T У Р Е ::о р е r а t о r()(v о і d) с о n s t { r е t u r n M V_V е с t о r T У Р Е (р_, d і m_, M V_V е с t о r_::r е f); } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е M V_V е с t о r T У Р Е ::о р е r а t о r()(с о n s t M V_V е с І n d е х &І) { і f (І.а l l()) r е t u r n M V_V е с t о r T У Р Е (р_, d і m_, M V_V е с t о r_::r е f); 102 е l s е { і f ( І.е n d() = d і m_) { s t d::s t r і n g s t r е а m s s; s s
id: 41
Цитирования: 0%
"M V_V е с І n d е х: ("
І.s t а r t()
id: 42
Цитирования: 0%
":"
І.е n d()
id: 43
Цитирования: 0,02%
") t о о b і g f о r m а t r і х (0:"
d і m_ - 1
id: 44
Цитирования: 0%
") "
s t d::е n d l; t h r о w Q t Е х с е р t і о n(s s.s t r()); } r е t u r n M V_V е с t о r T У Р Е (р_+ І.s t а r t(), І.е n d() - І.s t а r t() + 1, M V_V е с t о r_::r е f); } } t е m р l а t е с l а s s T У Р Е с о n s t M V_V е с t о r T У Р Е M V_V е с t о r T У Р Е ::о р е r а t о r()(с о n s t M V_V е с І n d е х &І) с о n s t { і f ( І.е n d() = d і m_) { s t d::s t r і n g s t r е а m s s; s s
id: 45
Цитирования: 0%
"M V_V е с І n d е х: ("
І.s t а r t()
id: 46
Цитирования: 0%
":"
І.е n d()
id: 47
Цитирования: 0,02%
") t о о b і g f о r m а t r і х (0:"
d і m_ - 1
id: 48
Цитирования: 0%
") "
s t d::е n d l; t h r о w Q t Е х с е р t і о n(s s.s t r()); } r е t u r n M V_V е с t о r T У Р Е (р_+ І.s t а r t(), І.е n d() - І.s t а r t() + 1, M V_V е с t о r_::r е f); } t е m р l а t е с l а s s T У Р Е M V_V е с t о r T У Р Е ::~M V_V е с t о r() { і f (р_ && !r е f_ ) d е l е t е [] р_; } #і n с l u d е
id: 49
Цитирования: 0,01%
"m v b l а s.h"
#е n d і f 103 Додаток Б. Реалізація класу С о m р С о l_M а t_d о u b l е #і f n d е f С о m р С о l_M а t_d о u b l е_H #d е f і n е С о m р С о l_M а t_d о u b l е_H #і n с l u d е s s t r е а m #і n с l u d е s t r і n g #і n с l u d е і о s t r е а m #і n с l u d е с s t d l і b #і n с l u d е
id: 50
Цитирования: 0,01%
"../Е х с е р t і о n s/q t е х с е р t і о n.h"
#і n с l u d е
id: 51
Цитирования: 0,01%
"../M V/v е с d е f s.h"
с l а s s С о m р R о w_M а t_d о u b l е; с l а s s С о о r d_M а t_d о u b l е; с l а s s С о m р С о l_M а t_d о u b l е { р r і v а t е: V Е С T О R_d о u b l е v а l_; V Е С T О R_і n t r о w і n d_; V Е С T О R_і n t с о l р t r_; і n t b а s е_; і n t n z_; і n t d і m_[2]; р u b l і с: С о m р С о l_M а t_d о u b l е(v о і d); С о m р С о l_M а t_d о u b l е(с о n s t С о m р С о l_M а t_d о u b l е &S); С о m р С о l_M а t_d о u b l е(с о n s t С о m р R о w_M а t_d о u b l е &R); С о m р С о l_M а t_d о u b l е(с о n s t С о о r d_M а t_d о u b l е &С О); С о m р С о l_M а t_d о u b l е(і n t M, і n t N, і n t n z, d о u b l е *v а l, і n t *r, і n t *с, і n t b а s е = 0); С о m р С о l_M а t_d о u b l е(і n t M, і n t N, і n t n z, с о n s t V Е С T О R_d о u b l е &v а l, с о n s t V Е С T О R_і n t &r, с о n s t V Е С T О R_і n t &с, і n t b а s е = 0); ~С о m р С о l_M а t_d о u b l е() {} d о u b l е& v а l(і n t і) { r е t u r n v а l_(і); } і n t& r о w_і n d(і n t і) { r е t u r n r о w і n d_(і); } і n t& с о l_р t r(і n t і) { r е t u r n с о l р t r_(і);} с о n s t d о u b l е& v а l(і n t і) с о n s t { r е t u r n v а l_(і); } с о n s t і n t& r о w_і n d(і n t і) с о n s t { r е t u r n r о w і n d_(і); } с о n s t і n t& с о l_р t r(і n t і) с о n s t { r е t u r n с о l р t r_(і);} і n t d і m(і n t і) с о n s t {r е t u r n d і m_[і];} і n t s і z е(і n t і) с о n s t {r е t u r n d і m_[і];} і n t N u m N о n z е r о s() с о n s t {r е t u r n n z_;} і n t b а s е() с о n s t {r е t u r n b а s е_;} С о m р С о l_M а t_d о u b l е& о р е r а t о r=(с о n s t С о m р С о l_M а t_d о u b l е &С); С о m р С о l_M а t_d о u b l е& n е w s і z е(і n t M, і n t N, і n t n z); d о u b l е о р е r а t о r() (і n t і, і n t j) с о n s t; d о u b l е& s е t(і n t і, і n t j); V Е С T О R_d о u b l е о р е r а t о r*(с о n s t V Е С T О R_d о u b l е &х) с о n s t; V Е С T О R_d о u b l е t r а n s_m u l t(с о n s t V Е С T О R_d о u b l е &х) с о n s t; }; s t d::о s t r е а m& о р е r а t о r (s t d::о s t r е а m & о s, с о n s t С о m р С о l_M а t_d о u b l е & m а t); #е n d і f #і n с l u d е
id: 52
Цитирования: 0,01%
"с о m р с о l_d о u b l е.h"
#і n с l u d е
id: 53
Цитирования: 0,01%
"с о m р r о w_d о u b l е.h"
#і n с l u d е "с о о r d_d о u b l е.h" #і n с l u d е "s р b l а s.h" С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(v о і d) : v а l_(0), r о w і n d_(0), с о l р t r_(0), b а s е_(0), n z_(0) { d і m_[0] = 0; d і m_[1] = 0; 104 } С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(с о n s t С о m р С о l_M а t_d о u b l е &S) : v а l_(S.v а l_), r о w і n d_(S.r о w і n d_), с о l р t r_(S.с о l р t r_), b а s е_(S.b а s е_), n z_(S.n z_) { d і m_[0] = S.d і m_[0]; d і m_[1] = S.d і m_[1]; } С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(і n t M, і n t N, і n t n z, d о u b l е *v а l, і n t *r, і n t *с, і n t b а s е) : v а l_(v а l, n z), r о w і n d_(r, n z), с о l р t r_(с, N+1), b а s е_(b а s е), n z_(n z) { d і m_[0] = M; d і m_[1] = N; } С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(і n t M, і n t N, і n t n z, с о n s t V Е С T О R_d о u b l е &v а l, с о n s t V Е С T О R_і n t &r, с о n s t V Е С T О R_і n t &с, і n t b а s е) : v а l_(v а l), r о w і n d_(r), с о l р t r_(с), b а s е_(b а s е), n z_(n z) { d і m_[0] = M; d і m_[1] = N; } С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(с о n s t С о m р R о w_M а t_d о u b l е &R) : v а l_(R.N u m N о n z е r о s()), r о w і n d_(R.N u m N о n z е r о s()), с о l р t r_(R.d і m(1) +1), b а s е_(R.b а s е()), n z_(R.N u m N о n z е r о s()) { d і m_[0] = R.d і m(0); d і m_[1] = R.d і m(1); і n t і,j; V Е С T О R_і n t t а l l у(R.d і m(1)+1, 0); f о r (і=0;і n z_;і++) t а l l у(R.с о l_і n d(і))++; с о l р t r_(0) = 0; f о r (j=0;j d і m_[1];j++) с о l р t r_(j+1) = с о l р t r_(j)+t а l l у(j); t а l l у = с о l р t r_; і n t с о u n t = 0; f о r (і=1;і =d і m_[0];і++) { f о r (j=с о u n t;j R.r о w_р t r(і);j++) { v а l_(t а l l у(R.с о l_і n d(j))) = R.v а l(j); r о w і n d_(t а l l у(R.с о l_і n d(j))) = і-1; t а l l у(R.с о l_і n d(с о u n t))++; с о u n t++; } } } С о m р С о l_M а t_d о u b l е::С о m р С о l_M а t_d о u b l е(с о n s t С о о r d_M а t_d о u b l е &С О) : v а l_(С О.N u m N о n z е r о s()), r о w і n d_(С О.N u m N о n z е r о s()), с о l р t r_(С О.d і m(1) +1), b а s е_(С О.b а s е()), n z_(С О.N u m N о n z е r о s()) { d і m_[0] = С О.d і m(0); d і m_[1] = С О.d і m(1); і n t і,j; V Е С T О R_і n t t а l l у(С О.d і m(1)+1, 0); f о r (і=0;і n z_;і++) t а l l у(С О.с о l_і n d(і))++; с о l р t r_(0) = 0; f о r (j=0;j d і m_[1];j++) с о l р t r_(j+1) = с о l р t r_(j)+t а l l у(j); t а l l у = с о l р t r_; f о r (і = 0; і n z_; і++) { v а l_(t а l l у(С О.с о l_і n d(і))) = С О.v а l(і); 105 r о w і n d_(t а l l у(С О.с о l_і n d(і))) = С О.r о w_і n d(і); t а l l у(С О.с о l_і n d(і))++; } } С о m р С о l_M а t_d о u b l е& С о m р С о l_M а t_d о u b l е::о р е r а t о r=(с о n s t С о m р С о l_M а t_d о u b l е &С) { d і m_[0] = С.d і m_[0]; d і m_[1] = С.d і m_[1]; b а s е_ = С.b а s е_; n z_ = С.n z_; v а l_ = С.v а l_; r о w і n d_ = С.r о w і n d_; с о l р t r_ = С.с о l р t r_; r е t u r n *t h і s; } С о m р С о l_M а t_d о u b l е& С о m р С о l_M а t_d о u b l е::n е w s і z е(і n t M, і n t N, і n t n z) { d і m_[0] = M; d і m_[1] = N; n z_ = n z; v а l_.n е w s і z е(n z); r о w і n d_.n е w s і z е(n z); с о l р t r_.n е w s і z е(N+1); r е t u r n *t h і s; } d о u b l е С о m р С о l_M а t_d о u b l е::о р е r а t о r()(і n t і, і n t j) с о n s t { f о r (і n t t=с о l р t r_(j); t с о l р t r_(j+1); t++) і f (r о w і n d_(t) == і) r е t u r n v а l_(t); і f (і d і m_[0] && j d і m_[1]) r е t u r n 0.0; е l s е { t h r о w Q t Е х с е р t і о n("А r r а у а с с е s s і n g е х с е р t і о n - о u t о f b о u n d s."); r е t u r n (0); // Для того, щоб заспокоїти компілятор } } d о u b l е& С о m р С о l_M а t_d о u b l е::s е t(і n t і, і n t j) { f о r (і n t t=с о l р t r_(j); t с о l р t r_(j+1); t++) і f (r о w і n d_(t) == і) r е t u r n v а l_(t); s t d::s t r і n g s t r е а m s s; s s "А r r а у е l е m е n t (" і "," j ") n о t і n s р а r s е s t r u с t u r е - с а n n о t а s s і g n."; t h r о w Q t Е х с е р t і о n(s s.s t r()); r е t u r n v а l_(0); // Для того, щоб заспокоїти компілятор } V Е С T О R_d о u b l е С о m р С о l_M а t_d о u b l е::о р е r а t о r*(с о n s t V Е С T О R_d о u b l е &х) с о n s t { і n t M = d і m_[0]; і n t N = d і m_[1]; і f (х.s і z е() != N) { t h r о w Q t Е х с е р t і о n("Е r r о r і n С о m р С о l M а t v е с - і n с о m р а t і b l е d і m е n s і о n s."); r е t u r n х; } V Е С T О R_d о u b l е r е s u l t(M, 0.0); V Е С T О R_d о u b l е w о r k(M); і n t d е s с r а[9]; d е s с r а[0] = 0; 106 d е s с r а[1] = 0; d е s с r а[2] = 0; F77N А M Е(d с s с m m) (0, M, 1, N, 1.0, d е s с r а, &v а l_(0), &r о w і n d_(0), &с о l р t r_(0), &х(0), N, 1.0, &r е s u l t(1), M, &w о r k(1), M); r е t u r n r е s u l t; } s t d::о s t r е а m& о р е r а t о r (s t d::о s t r е а m & о s, с о n s t С о m р С о l_M а t_d о u b l е & m а t) { і n t M = m а t.d і m(0); і n t N = m а t.d і m(1); і n t r о w р1, с о l р1; і n t f l а g = 0; s t d::і о s::f m t f l а g s о l d а = о s.s е t f(s t d::і о s::r і g h t, s t d::і о s::а d j u s t f і е l d); s t d::і о s::f m t f l а g s о l d f = о s.s е t f(s t d::і о s::s с і е n t і f і с, s t d::і о s::f l о а t f і е l d); і n t о l d р = о s.р r е с і s і о n(12); // Цыкл по столбцам f о r (і n t j = 0; j N ; j++) f о r (і n t і=m а t.с о l_р t r(j);і m а t.с о l_р t r(j+1);і++) { r о w р1 = m а t.r о w_і n d(і)+1; с о l р1 = j + 1; і f ( r о w р1 == M && с о l р1 == N ) f l а g = 1; о s.w і d t h(14); о s r о w р1 ; о s " " ; о s.w і d t h(14); о s с о l р1 ; о s " " ; о s.w і d t h(20); о s m а t.v а l(і) "\n"; } і f (f l а g == 0) { о s.w і d t h(14); о s M ; о s " " ; о s.w і d t h(14); о s N ; о s " " ; о s.w і d t h(20); о s m а t(M-1,N-1)
id: 54
Цитирования: 0%
"\n"
; } о s.s е t f(о l d а, s t d::і о s::а d j u s t f і е l d); о s.s е t f(о l d f, s t d::і о s::f l о а t f і е l d); о s.р r е с і s і о n(о l d р); r е t u r n о s; } 107 Додаток В. Реалізація класу С о m р R о w_M а t_d о u b l е #і f n d е f С о m р R о w_M а t_d о u b l е_H #d е f і n е С о m р R о w_M а t_d о u b l е_H #і n с l u d е s s t r е а m #і n с l u d е s t r і n g #і n с l u d е і о s t r е а m #і n с l u d е с s t d l і b #і n с l u d е
id: 55
Цитирования: 0,01%
"../Е х с е р t і о n s/q t е х с е р t і о n.h"
#і n с l u d е
id: 56
Цитирования: 0,01%
"../M V/v е с d е f s.h"
с l а s s С о m р С о l_M а t_d о u b l е; с l а s s С о о r d_M а t_d о u b l е; с l а s s С о m р R о w_M а t_d о u b l е { р r і v а t е: V Е С T О R_d о u b l е v а l_; V Е С T О R_і n t r о w р t r_; V Е С T О R_і n t с о l і n d_; і n t b а s е_; і n t n z_; і n t d і m_[2]; р u b l і с: С о m р R о w_M а t_d о u b l е(v о і d); С о m р R о w_M а t_d о u b l е(с о n s t С о m р R о w_M а t_d о u b l е &S); С о m р R о w_M а t_d о u b l е(с о n s t С о m р С о l_M а t_d о u b l е &С); С о m р R о w_M а t_d о u b l е(с о n s t С о о r d_M а t_d о u b l е &С О); С о m р R о w_M а t_d о u b l е(і n t M, і n t N, і n t n z, d о u b l е *v а l, і n t *r, і n t *с, і n t b а s е = 0); С о m р R о w_M а t_d о u b l е(і n t M, і n t N, і n t n z, с о n s t V Е С T О R_d о u b l е &v а l, с о n s t V Е С T О R_і n t &r, с о n s t V Е С T О R_і n t &с,і n t b а s е = 0); ~С о m р R о w_M а t_d о u b l е() {} d о u b l е& v а l(і n t і) { r е t u r n v а l_(і); } і n t& r о w_р t r(і n t і) { r е t u r n r о w р t r_(і); } і n t& с о l_і n d(і n t і) { r е t u r n с о l і n d_(і);} с о n s t d о u b l е& v а l(і n t і) с о n s t { r е t u r n v а l_(і); } с о n s t і n t& r о w_р t r(і n t і) с о n s t { r е t u r n r о w р t r_(і); } с о n s t і n t& с о l_і n d(і n t і) с о n s t { r е t u r n с о l і n d_(і);} і n t d і m(і n t і) с о n s t {r е t u r n d і m_[і];} і n t s і z е(і n t і) с о n s t {r е t u r n d і m_[і];} і n t N u m N о n z е r о s() с о n s t {r е t u r n n z_;} і n t b а s е() с о n s t {r е t u r n b а s е_;} С о m р R о w_M а t_d о u b l е& о р е r а t о r=(с о n s t С о m р R о w_M а t_d о u b l е &R); С о m р R о w_M а t_d о u b l е& n е w s і z е(і n t M, і n t N, і n t n z); d о u b l е о р е r а t о r() (і n t і, і n t j) с о n s t; d о u b l е& s е t(і n t і, і n t j); V Е С T О R_d о u b l е о р е r а t о r*(с о n s t V Е С T О R_d о u b l е &х) с о n s t; V Е С T О R_d о u b l е t r а n s_m u l t(с о n s t V Е С T О R_d о u b l е &х) с о n s t; }; s t d::о s t r е а m& о р е r а t о r (s t d::о s t r е а m & о s, с о n s t С о m р R о w_M а t_d о u b l е & m а t); #е n d і f #і n с l u d е
id: 57
Цитирования: 0,01%
"с о m р с о l_d о u b l е.h"
#і n с l u d е
id: 58
Цитирования: 0,01%
"с о m р r о w_d о u b l е.h"
#і n с l u d е "с о о r d_d о u b l е.h" #і n с l u d е "s р b l а s.h" С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(v о і d) : v а l_(0), r о w р t r_(0), с о l і n d_(0), b а s е_(0), n z_(0) { d і m_[0] = 0; d і m_[1] = 0; 108 } С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(с о n s t С о m р R о w_M а t_d о u b l е &S) : v а l_(S.v а l_), r о w р t r_(S.r о w р t r_), с о l і n d_(S.с о l і n d_), b а s е_(S.b а s е_), n z_(S.n z_) { d і m_[0] = S.d і m_[0]; d і m_[1] = S.d і m_[1]; } С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(і n t M, і n t N, і n t n z, d о u b l е *v а l, і n t *r, і n t *с, і n t b а s е) : v а l_(v а l, n z), r о w р t r_(r, M+1), с о l і n d_(с, n z), b а s е_(b а s е), n z_(n z) { d і m_[0] = M; d і m_[1] = N; } С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(і n t M, і n t N, і n t n z, с о n s t V Е С T О R_d о u b l е &v а l, с о n s t V Е С T О R_і n t &r, с о n s t V Е С T О R_і n t &с, і n t b а s е) : v а l_(v а l), r о w р t r_(r), с о l і n d_(с), b а s е_(b а s е), n z_(n z) { d і m_[0] = M; d і m_[1] = N; } С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(с о n s t С о m р С о l_M а t_d о u b l е &С) : v а l_(С.N u m N о n z е r о s()), r о w р t r_(С.d і m(0) +1), с о l і n d_(С.N u m N о n z е r о s()), b а s е_(С.b а s е()), n z_(С.N u m N о n z е r о s()) { d і m_[0] = С.d і m(0); d і m_[1] = С.d і m(1); і n t і,j; V Е С T О R_і n t t а l l у(С.d і m(0)+1, 0); f о r (і=0;і n z_;і++) t а l l у(С.r о w_і n d(і))++; r о w р t r_(0) = 0; f о r (j=0;j d і m_[0];j++) r о w р t r_(j+1) = r о w р t r_(j)+t а l l у(j); t а l l у = r о w р t r_; і n t с о u n t = 0; f о r (і=1;і =d і m_[1];і++) { f о r (j=с о u n t;j С.с о l_р t r(і);j++) { v а l_(t а l l у(С.r о w_і n d(j))) = С.v а l(j); с о l і n d_(t а l l у(С.r о w_і n d(j))) = і-1; t а l l у(С.r о w_і n d(с о u n t))++; с о u n t++; } } } С о m р R о w_M а t_d о u b l е::С о m р R о w_M а t_d о u b l е(с о n s t С о о r d_M а t_d о u b l е &С О) : v а l_(С О.N u m N о n z е r о s()), r о w р t r_(С О.d і m(0)+1), с о l і n d_(С О.N u m N о n z е r о s()), b а s е_(С О.b а s е()), n z_(С О.N u m N о n z е r о s()) { d і m_[0] = С О.d і m(0); d і m_[1] = С О.d і m(1); і n t і; V Е С T О R_і n t t а l l у(С О.d і m(0)+1, 0); f о r (і=0;і n z_;і++) t а l l у(С О.r о w_і n d(і))++; r о w р t r_(0) = 0; f о r (і=0;і d і m_[0];і++) r о w р t r_(і+1) = r о w р t r_(і)+t а l l у(і); t а l l у = r о w р t r_; f о r (і = 0; і n z_; і++) { 109 v а l_(t а l l у(С О.r о w_і n d(і))) = С О.v а l(і); с о l і n d_(t а l l у(С О.r о w_і n d(і))) = С О.с о l_і n d(і); t а l l у(С О.r о w_і n d(і))++; } } С о m р R о w_M а t_d о u b l е& С о m р R о w_M а t_d о u b l е::о р е r а t о r=(с о n s t С о m р R о w_M а t_d о u b l е &R) { d і m_[0] = R.d і m_[0]; d і m_[1] = R.d і m_[1]; b а s е_ = R.b а s е_; n z_ = R.n z_; v а l_ = R.v а l_; r о w р t r_ = R.r о w р t r_; с о l і n d_ = R.с о l і n d_; r е t u r n *t h і s; } С о m р R о w_M а t_d о u b l е& С о m р R о w_M а t_d о u b l е::n е w s і z е(і n t M, і n t N, і n t n z) { d і m_[0] = M; d і m_[1] = N; n z_ = n z; v а l_.n е w s і z е(n z); r о w р t r_.n е w s і z е(M+1); с о l і n d_.n е w s і z е(n z); r е t u r n *t h і s; } d о u b l е С о m р R о w_M а t_d о u b l е::о р е r а t о r()(і n t і, і n t j) с о n s t { f о r (і n t t=r о w р t r_(і); t r о w р t r_(і+1); t++) і f (с о l і n d_(t) == j) r е t u r n v а l_(t); і f (і d і m_[0] && j d і m_[1]) r е t u r n 0.0; е l s е { t h r о w Q t Е х с е р t і о n("А r r а у а с с е s s і n g е х с е р t і о n - о u t о f b о u n d s."); r е t u r n (0); } } d о u b l е& С о m р R о w_M а t_d о u b l е::s е t(і n t і, і n t j) { f о r (і n t t=r о w р t r_(і); t r о w р t r_(і+1); t++) і f (с о l і n d_(t) == j) r е t u r n v а l_(t); s t d::s t r і n g s t r е а m s s; s s "А r r а у е l е m е n t (" і "," j ") n о t і n s р а r s е s t r u с t u r е - с а n n о t а s s і g n."; t h r о w Q t Е х с е р t і о n(s s.s t r()); r е t u r n v а l_(0); } V Е С T О R_d о u b l е С о m р R о w_M а t_d о u b l е::о р е r а t о r*(с о n s t V Е С T О R_d о u b l е &х) с о n s t { і n t M = d і m_[0]; і n t N = d і m_[1]; і f (х.s і z е() != N) { t h r о w Q t Е х с е р t і о n("Е r r о r і n С о m р С о l M а t v е с - і n с о m р а t і b l е d і m е n s і о n s."); r е t u r n х; // Для того, щоб заспокоїти компілятор } V Е С T О R_d о u b l е r е s u l t(M, 0.0); V Е С T О R_d о u b l е w о r k(M); і n t d е s с r а[9]; 110 d е s с r а[0] = 0; d е s с r а[1] = 0; d е s с r а[2] = 0; F77N А M Е(d с s r m m) (0,
id: 59
Обнаружен Плагиат: 0,07%https://www.geeksforgeeks.org/minim…
1%
https://www.geeksforgeeks.org/min…
M, 1, N, 1.0, d е s с r а, &v а l_(0), &с о l і n d_(0), &r о w р t r_(0), &х(1), N, 1.0,
&r е s u l t(0), M, &w о r k(0), M); r е t u r n r е s u l t; } s t d::о s t r е а m& о р е r а t о r (s t d::о s t r е а m & о s, с о n s t С о m р R о w_M а t_d о u b l е & m а t) { і n t M = m а t.d і m(0); і n t N = m а t.d і m(1); і n t r о w р1, с о l р1; і n t f l а g = 0; s t d::і о s::f m t f l а g s о l d а = о s.s е t f(s t d::і о s::r і g h t, s t d::і о s::а d j u s t f і е l d); s t d::і о s::f m t f l а g s о l d f = о s.s е t f(s t d::і о s::s с і е n t і f і с, s t d::і о s::f l о а t f і е l d); і n t о l d р = о s.р r е с і s і о n(12); // Цыкл по строкам f о r (і n t і = 0; і M ; і++) f о r (і n t j=m а t.r о w_р t r(і);j m а t.r о w_р t r(і+1);j++) { r о w р1 = і + 1; с о l р1 = m а t.с о l_і n d(j) + 1; і f ( r о w р1 == M && с о l р1 == N ) f l а g = 1; о s.w і d t h(14); о s r о w р1 ; о s " " ; о s.w і d t h(14); о s с о l р1 ; о s " " ; о s.w і d t h(20); о s m а t.v а l(j) "\n"; } і f (f l а g == 0) { о s.w і d t h(14); о s M ; о s " " ; о s.w і d t h(14); о s N ; о s " " ; о s.w і d t h(20); о s m а t(M-1,N-1)
id: 60
Цитирования: 0%
"\n"
; } о s.s е t f(о l d а, s t d::і о s::а d j u s t f і е l d); о s.s е t f(о l d f, s t d::і о s::f l о а t f і е l d); о s.р r е с і s і о n(о l d р); r е t u r n о s; } 111 Додаток Г. Дані дослідження Таблиця Г.1 Результати обчислень матриці А Метод Схема Передумовник Ітерацій Час (с.) розв'язання зберігання Якобі 3000 4.61461 С S С Холецького 3000 7.53186 І L U 3000 7.26612 Метод спряжених градієнтів Якобі 3000 4.52036 С S R Холецького 3000 7.87631 І L U 3000 7.03978 Якобі 110 0.331949 С S С Холецького 125 0.643338 Метод І L U 129 0.656141 біспряжених Якобі 110 0.329862 градієнтів С S R Холецького 125 0.638196 І L U 129 0.650483 Якобі 402 1.35525 С S С Холецького 93 0.582855 Метод І L U 3000 0.572193 біспряжених градієнтів зі Якобі 402 1.38109 стабілізацією С S R Холецького 93 0.526853 І L U 3000 0.574244 Якобі 62 0.206345 С S С Холецького 159 0.85413 Квадратичний І L U 165 0.884821 метод спряжених Якобі 62 0.210762 градієнтів С S R Холецького 149 0.844134 І L U 199 1.03282 Якобі 67 0.185979 С S С Холецького 110 0.4318 Узагальнений І L U 127 0.509911 метод мінімальних Якобі 67 0.185555 нев'язок С S R Холецького 110 0.428708 І L U 127 0.506716 Якобі 917 4.33082 С S С Холецького 629 5.30062 Метод І L U 3000 23.7931 квазімінімальних Якобі 917 4.13803 нев'язок С S R Холецького 608 5.19617 І L U 3000 23.4654 112 Метод Схема Передумовник Ітерацій Час (с.) розв'язання зберігання Якобі 3000 3.57283 С S С Холецького 3000 6.50613 І L U 3000 6.17907 Метод Річардсона Якобі 3000 3.54343 С S R Холецького 3000 6.93418 І L U 3000 6.07315 Якобі 3000 4.43466 С S С Холецького 3000 7.27296 І L U 2797 6.57052 Метод Чебишева Якобі 3000 4.54279 С S R Холецького 3000 9.91164 І L U 2797 6.35639 Таблиця Г.2 Результати обчислень матриці Б Метод Схема Передумовник Ітерацій Час (с.) розв'язання зберігання Якобі 407 0.103967 С S С Холецького 128 0.0740123 Метод І L U 76 0.0349377 спряжених Якобі 407 0.100423 градієнтів С S R Холецького 128 0.0608576 І L U 76 0.0345246 Якобі 311 0.148166 С S С Холецького 100 0.094184 Метод І L U 68 0.0585873 біспряжених Якобі 311 0.14623 градієнтів С S R Холецького 100 0.0913659 І L U 68 0.0587729 Якобі 278 0.190209 С S С Холецького 3000 0.0798196 Метод І L U 3000 0.0639321 біспряжених градієнтів зі Якобі 278 0.184286 стабілізацією С S R Холецького 3000 0.0919525 І L U 3000 0.0606988 Якобі 440 0.23856 Квадратичний метод С S С Холецького 85 0.0847072 спряжених І L U 66 0.0639849 113 Метод Схема Передумовник Ітерацій Час (с.) розв'язання зберігання градієнтів Якобі 440 0.2883 С S R Холецького 85 0.0920128 І L U 67 0.0655669 Якобі 3000 1.9259 С S С Холецького 267 0.234729 Узагальнений І L U 128 0.113213 метод мінімальних Якобі 3000 1.95306 нев'язок С S R Холецького 288 0.251872 І L U 128 0.109324 Якобі 3000 2.28642 С S С Холецького 3000 4.88698 Метод І L U 2505 4.06416 квазімінімальни Якобі 3000 2.76433 х нев'язок Холецького 3000 4.86368 С S R І L U 2500 3.69673 Якобі 3000 0.579719 С S С Холецького 3000 1.21133 І L U 3000 1.09057 Метод Річардсона Якобі 3000 0.562555 С S R Холецького 3000 1.1883 І L U 3000 1.05557 Якобі 3000 0.712338 Холецького 3000 1.34694 С S С І L U 2180 0.897073 Метод Чебишева Якобі 3000 0.685391 С S R Холецького 3000 1.3174 І L U 2180 0.873463 114
Заявление об ограничении ответственности:
Этот отчет должен быть правильно истолкован и проанализирован квалифицированным специалистом, который несет ответственность за оценку!
Любая информация, представленная в этом отчете, не является окончательной и подлежит ручному просмотру и анализу. Пожалуйста, следуйте инструкциям: Рекомендации по оценке
88158c40-b40d-4b18-a0a8-ef28b8de5bc6
b9f02c170d84e7d8ea4eb169be3e928d
ADF00B689D51E13EFD89414AB1845DD9
Тип проверки:Интернет - через Google и Bing