Кесілген матрица

Кесілген матрица

Нөлдік мәні жоқ матрицалар толық матрица деп аталады.Кейбір элементтері нөлдік мәнге тең матрицалар кесілген матрица деп аталады.Нөл емес n санды элементтер тұратын матрица үшін :

• O(n).Матрица алгоритмінің асимптотикалық қасиеті бар теориялық анализ жасау үшін
• Әрбір жолда 10  әдеттегі оқиғадан аспайтын
• Шектеуі егер
• Осы алгоритм және есептеуіш жүйе үшін нөлдерді тиімді пайдалану керек

Олар көбінесе қолданбалы есептерді  шығару үшін қолданылады.Оларға кіші квадраттар әдісі, түйіскен градиенттер әдісі және ортақ байланыстың жоқтығын минималдаудың итерациялық әдісі қолданылады.

Ең кіші квадраттар әдісі

Ең кіші квадраттар әдісі— қателер теориясының белгісіз шамаларды кездейсоқ қателері бар өлшеулердің нәтижесін бағалау үшін қолданатын әдістерінің бірі. Ең кіші квадраттар әдісі берілген функцияларды олардан гөрі қарапайым функциялар арқылы жуықтап өрнектеу үшін де пайдаланылады. Бұл әдісті 1794 — 95 ж. ‘’К.Гаусс’’ және 1805 — 06 ж. француз математигі  ‘’А.Лежандр’’ (1875 — 1961) ұсынған. Ең кіші квадраттар әдісі алғашқыда астрономия және геодезия бақылаулардың нәтижесін өңдеу үшін қолданылды. Бірақ оның дәл математикалық негіздемесін жасап, қолданылу шекарасын көрсетіп берген орыс ғалымдары А.А. Марков (1856 — 1922) пен А.Н. Колмогоров болды. Ең кіші квадраттар әдісі — математикалық  статистиканың аса маңызды бір бөлімі және ол статистика қорытынды жасау үшін ғылым мен техниканың әр түрлі саласында кеңінен қолданылады . Гаусс бойынша, Ең кіші квадраттар әдісінің мәні – физикалық шаманың (m) дәл мәнін (белгісіз) оның бақылаулар нәтижесінде есептелген жуық мәнімен(Х)  ауыстырғандағы “шығын” , (X–m)2 қателік квадратына пропорцмонал болады деген пайымдауға негізделген. Мұндай жағдайда , “шығынының” орташа мәні ең кіші болатындай Х шамасының жүйелі қатесін тиімді баға деп есептеуге болады. Міне, осы талап Ең кіші квадраттар әдісінің негізіне алынады. Ал, жалпы алғанда, Х шамасының Ең кіші квадраттар әдісі мағынасындағы тиімді бағасын іздеу күрделі есеп. Сондықтан практика бұл есептің ауқымын тарылта отырып, Х ретінде бақылаулар нәтижесінен алынатын жүйелі қатесі болмайтын сызықтық функция таңдалады және ол функцияның барлық сызықтық функциялар класындағы “шығынының” орташа мәні ең кіші болуы тиіс. Егер бақылаулардың орташа қателері қалыпты үлестірілуге  бағынса ірә бағаланатын шама  (m) бақылаулар нәтижесінің орташа мәндеріне сызықты тәуелді болса, онда мұндай есептің шешімі жалпы есептің де шешімі болады. Бұл жағдайда  Х-тің тиімді бағасы да  m -дің орташа мәні бар қалыпты үлестірілуге бағынады.Сондықтан Х кездейсоқ шамасының ықтималдық тығыздығы  (p): )=(x; s,mp)= exp([(x– –m)/s]2), х=Х болғанда m=Х нүктесінде ең үлкен мәнге ие болады.

Итерация әдісі

 

Итерация (лат. іteratіo – қайталау) – қандай да бір математикалық амалды қайталап қолдану. Мысалы, егер y=f(x)²f1(x) х-қа тәуелді қандай да бір функция болса, онда f2(x)=f[f1(x)], f3(x)=f[f2(x)], ..., fn(x)=f[fn-1(x)] функциялар тізбегі f(x) функциясының сәйкес түрде екінші, үшінші, ..., n-итерациясы деп аталады. Сондай-ақ f(x)=x² деп ұйғара отырып, f2(x)=(x²)²=, f3(x)= ==, ..., fn(x)== = тізбегін алуға болады. n индексі итерация көрсеткіші, ал f(x) функциясынан f2(x), f3(x), ... функцияларына көшу итераттау деп аталады. Итерация әдісі әр түрлі теңдеулер мен теңдеулер жүйесін шешуде қолданылады. Ол интегралдық теңдеулер теориясында да маңызды рөл атқарады.

 

Сызықты алгебралық жүйе берілсін:

      (35) 

 

 

 

 

              

матрицаларын енгізе отырып, жүйені келесі матрицалық теңдеу түрінде  жазуға болады:

         (36)

Диагональдық коэффициенттер   деп ұйғарып, (35) жүйесінің бірінші теңдеуін  -ге, екіншісін  -ге, т.с.с. қатысты 

шешеміз. Онда мынадай келесі жүйені аламыз:

  (37) 

 

 

   

мұндағы   және 

  

 

 

 

матрицаларын енгізіп, (37) жүйені

      (38)

матрицалық формасы түрінде  жазуға болады.

(38) жүйені шешу үшін  тізбектелген жуықтау әдісін  қолданамыз. Бастапқы жуық мәні  үшін   бос мүшелер бағанын аламыз. 

Одан кейін тізбектей  бағана-матрицаларды құрамыз:

,

бірінші жуықтауды  , ...,

    (39)

формуласы бойынша есептейміз.

Егер   жуықтаулар тізбегінің шегі   болса, онда бұл шек (37) жүйенің шешімі болады.

Бұл жағдайда (39) теңдікте шекке  көшсек келесіні аламыз:

 

 

немесе 

яғни шекті вектор (37) жүйенің  шешімі болғандықтан, ол (35) жүйенің  де шешімі болады.

Жуықтаулар формуласын кеңейген түрде жазайық:

   (40)

Кейбір жағдайларда (35) жүйесін  коэффициенттер нөлге тең болмайтындай  (37) жүйесіне келтіру тиімді екенін ескеру қажет.

Мысалы,   жуықтаулар тізбегі әдісін қолдану үшін келесі түрде жазылуы мүмкін:

Дәл осы әдіспен жүйені мына түрде жазады:

, мұндағы  .

Онда берілген жүйе келтірілген  жүйеге эквивалентті. Сондықтан ары  қарай   деп ұйғармайтын боламыз.

 

 

 

 

(39) немесе (40) формуламен анықталатын  тізбектелген жуықтау әдісі итерация  әдісі деп аталады.

Егер   болса, онда (40) жүйе жинақы болады да, (35) жүйенің шешімін анықтауға болады. 

 

Басқа сөзбен айтқанда, жүйенің  диагональдық коэффициенттерінің модулі диагональ емес коэффициенттерінен анағұрлым үлкен

болғанда жүйеге итерация әдісін қолдануға болады.

Мысал. Жүйені шешу керек.

  (41)   

 

Шешуі:

Мұнда жүйенің 4,3,4 диагональдық коэффициентері басқа коэффициенттерден  үлкен, сондықтан итерация әдісін қолдануға  

болады. Осы жүйені қалыпты түрге келтірейік:

    (42) 

Матрицалық формада (42) жүйені былай жазуға болады: (41) жүйенің  түбірінің нөлдік жуықтауы ретінде  келесіні аламыз

 

Бұл мәндерді (42) жүйенің оң жағына қойып, түбірлердің бірінші  жуықтауын аламыз:

Ары қарай осы табылған жуықтауларды (42) формулаға қойып, екінші жуықтауларды аламыз:

Жаңа мәндерді орнына қойып, келесі үшінші жуықтауларды аламыз:

MATLAB-та қарапайым кесілген матрица үшін қолданылатын функциялар:

Spdiags – diagфункциясының мүмкіндігін ұлғайтады. Кіріс аргументі әртүрлі төрт түрлі операция бар.

[B.d] = spdiags(A) – Өлшемі mXnА матрицасындағы нөл емес диагоналдарды шығарады.B – матрица өлшемі min(m,n)Xp,бағаны p нөл емес A матрицасының диагоналы болу керек . d – p векторының ұзындығы , бүтін санды элементі А матрицасының диагонал нөмерін анықтайды(тиімді номер болса – басты диагоналдан жоғары , тиімсіз номер болса - басты диагоналдан төмен )

В = spdiags(A.d) – d векторының диагоналын шығарады

А = spdiags(B,d,A) – d векторымен анықталған B матрицасындағы бағандарын А матрицасының диагоналын ауыстырады.

А = spdiags(B,d,m,n) – d векторымен анықталған В матрицасының бағандарын диагонал бойына орналастырып кесілген матрица құру.

S = speye(m.n) –өлшемі mXnболатын кесілген матрицаға басты диагоналына 1-ді және 0-ді диагонал емес элементтеріне.

S = speye(n) - speye(n.n) сиякты.Мысалы:

» S = speye(4)

 

S =

 

(1,1)     1

 

(2.2)     1

 

(3.3)     1

 

(4.4)     1

R = sprand(m,n,density)–Өлшемі mXnішінде density өлшемі mXnнөлемесэлементтердiңбiрқалыптыорналасқан элементтер кесілген матрица қайтарады (0<density<l)

Мысалы:

>> d=sprand(4,3,0.6)

 

d =

 

   (4,1)       0.9157

   (2,2)       0.1419

   (4,2)       0.7922

   (1,3)       0.8003

   (3,3)       0.4218

   (4,3)       0.9595

Matlabпакетіндегі кесілген матрицалармен жұмыс істейтін операциялар:

SPARSE –кесілген матрица құру

SPDIAGS - кесілген матрицаның диагоналын құру

SPEYE –бірлік кесілген матрица

SPRANDN - кездейсоқ кесілген матрица

SPRANDSYM –кездейсоқ кесілген симметриялы матрица

FIND –нөл емес элементтердің индексін табу

FULL –кесілген матрицаны толық матрицаға ауыстыру

ISSPARSE - кесілген матрица класына тексеру

NNZ –нөл емес элементтер саны

NONZEROS –нөл емес элементтер векторын құру

SPALLOC –кесілген матрицаға орын бөлу

SPFUN –нөл емес элементтер функциясын есептеу

SPONES –байланыс матрицасын құру

GPLOT –график құру

SPY –кесілген матрица құрылысын визуалдау

ETREE –матрица дарағы

ETREEPLOT - матрица дарағын құру

TREELAYOUT –дарақ орналастыру

TREEPLOT - матрица дарағын құру\