Пәннің ОҚУ-Әдістемелік кешені «Матрицалар теориясы»
Матрицаларды көбейтудің есептеуіш аспектісі
жүктеу/скачать 2,25 Mb.
|
7d448e60-8cb2-11e3-bf6e-f6d299da70eeказ умм теория матриц
1.7 Матрицаларды көбейтудің есептеуіш аспектісіАйталық - өлшемді матрицалары берілсін және олардың көбейтіндісін есептеу керек болсын. Бұны есептеудің классикалық алгоритмі мынадай (программа алгоритмдік Фортран тіліне ұқсас): Алайда алдымен элементтерін нөлге айналдырып алу керек. «Бұл бағдарламаның жақсы жағы неде?»,- деген сұрақ туындайды. Бұл сұраққа жауап беру оңай емес. Алдымен бізге қандай да бір критерий қажет – айталық осы бағдарламаны орындау уақыты болсын. Алайда уақыт тек компьютердің түріне ғана тәуелді емес. Бұл жерде бірдене түсіну үшін көптеген бөлшектерді алып тастап, ең негізгісін қалтыру керек. Егер де барлық амалдар тізбектей орындалса, онда жұмыстың орындалу уақытын амалдар санына пропорционал деп есептеуімізге болады. біз қарай жүрейік және тек арифметикалық амалдарды есептейміз. Олардың жалпы санын алгоритмнің арифметикалық күрделілігі деп атаймыз. Алгоритм –бұл элементар амалдардың соңғы бекітілген жиынтығынан алынған элементар амалдардың тізбегі деп есептейік. Анықтық үшін, айталық бұл төрт арифметикалық амал болсын. Сонымен, математикалық есеп қойылды. Бұрындары классикалық алгоритм ең жақсы деп есептелген. Қазір байқайтынымыздай ол бұлай емес. 1.8 Виноград әдісі Классикалық алгоритмді қолданбай матрицаларды көбейткен алғашқылардың бірі (60 жылдардың басында) Виноград болды. Ол келесі тепе – теңдікті қолдануға болатынын көрсетті: Айталық болсын. Барлық үшін екінші және үшінші қосындыны көбейту және қосу амалы арқылы табуға болады. Бірінші қосынды үшін көбейту және қосу амалы қажет. Нәтижесінде – бұрынғыдай, амал орындалады, бірақ мұнда енді көбейту және қосу амалы болады. көбейту амалы қосуға қарағанда күрделі амал болғандықтан Виноград әдісінің практикалық маңызы бар. жүктеу/скачать 2,25 Mb. Достарыңызбен бөлісу:
|