Безкръвен K - Разтвор на SLAE с матрици с оскъден коефициент с използване на методи
В много области на науката и техниката при решаването на различни проблеми става необходимо да се изчисляват системи от линейни уравнения, които понякога са много оскъдни. Тъй като такива системи от уравнения обикновено са от голям порядък, възможно е да се намери тяхното решение (във всеки предвидим момент) само с използването на компютърни технологии. За да разрешите такива проблеми, можете да използвате директни методи (Gauss, Cramer) и приблизителни (Seidel, градиентно спускане и др.). Директните методи дават точно решение (грешката може да се дължи само на факта, че стойностите по време на преобразувания надхвърлят точността на типовете за използваната платформа), но те обикновено изискват повече повторения. Приблизителните методи обикновено работят по-бързо, но може да изискват специални начални условия или някаква подготовка на първоначалните данни и решението не винаги се сближава. Тази статия разглежда прилагането на метода на Гаус, модифициран за решаване на оскъдни системи от линейни уравнения. Този метод не е „математически“, а по-скоро „алгоритмичен“ и показва как прости техники могат да се използват за ускоряване на изчислението стотици пъти.
Условия за ползване
Разглежданият метод е подходящ за всякакви неродени (с едно решение) системи от линейни уравнения. По-нататък думата матрица ще означава матрица от коефициенти на линейни уравнения. Единственото условие е методът да има смисъл само за силно разредени матрици с големи размери N> 1000, където поне две трети от коефициентите са равни на 0. За обикновените матрици методът няма да даде печалба нито в скоростта, нито в спестяване на памет.
Описание на метода
Методът на Гаус се състои в нулиране на долната (или горната) полуматрица a [i, k], където ред i = 2.N, колона k = 1.i-1. Използвайки добре познатото правило, че решението на системата няма да се промени, ако едно от нейните уравнения се добави към друго, умножено по произволен коефициент, редовете на матрицата последователно, започвайки с първата, се умножават по специални коефициенти и се сумират нагоре с всички редове по-долу. Коефициентите се избират по такъв начин, че всеки ред да нулира съответната (i = k) колона под нея (само нейната поддиагонална част). Така че първият ред нулира първата колона A [2.N, 1], вторият - втората A [3.N, 2] и т.н. до предпоследния ред. Коефициентите се изчисляват по следния начин: например, за да нулирате първата колона, трябва да умножите първия ред по k = -A [2,1]/A [1,1] и да добавите към втория, след това по k = -A [3,1]/A [1,1] и добавете към трети и т.н. След това операцията се повтаря с втория ред (тя се умножава по съответните коефициенти и се добавя към всички подлежащи редове) и т.н. до предпоследния. Резултатът е матрица само с нули, останали под основния диагонал. Сега в последното уравнение има само един коефициент - съответно можете лесно да изчислите стойността на последното неизвестно: X [N] = B [N]/A [N, N], където B е векторът на свободните членове на уравнения, които между другото също участват в трансформации при нулиране на матрицата А. В предпоследното уравнение има два коефициента, а последното неизвестно вече е известно, можете да изчислите предпоследното: X [N-1] = ( B [N-1] -A [N-1, N] * X [N])/A [N-1, N-1]. По този начин, използвайки обратния ход, могат да бъдат изчислени всички неизвестни. По време на преобразуването на матрицата коефициентите на главния диагонал не трябва да бъдат занулени. Ако това се случи, тогава матрицата не е факторизирана или уравненията не са написани правилно. Или тази система има повече от едно решение. Повече подробности за метода на Гаус можете да намерите тук.
Горният алгоритъм е лесен за изпълнение. Броят на итерациите е известен предварително и зависи само от реда на матрицата. Ако е програмиран в класически стил, той лесно ще се справи с малки матрици N
1000. Матриците обаче понякога са от порядъка на 100 000 или повече. Ще са необходими години, за да се изчисли такава матрица, използвайки класическия метод на Гаус, тъй като броят на итерациите ще бъде огромен. Ако тази матрица се съхранява в обикновен двумерен масив, тогава при използване на двойния тип тя ще заема 100 000 x 100 000 x 8 = 800 000 000 байта = 800 MB в паметта, което е доста. И ако вземем предвид, че размерът на матрицата се увеличава пропорционално на квадрата от порядъка на матрицата, то за матрица от порядъка на 400 000 това ще бъде 16 пъти повече, т.е. 12,8 GB!