Сызықтық алгебралық теңдеулер жүйесін шешу

Бұл пунктте біз сызықтық теңдеулер жүйесін шешудің тура әдісімен қарастырамыз: белгісіздерді шығарып тастау – Гаус әдісі және итерациялық әдіс Якоби әдісі.

Гаусс әдісі

Ах=b сызықтық алгебралық теңдеулер жүйесін шешу қажет болсын.

Мұндағы

А – берілген коэффициенттер матрицасы

b- берілген вектор

х-белгісіз вектор

белгісіздерді шығару әдісі – Гаус әдісі А матрицасын көбейткіштерге жіктеуден тұрады:

PA=LU

L – төменгі үшбұрыш матрица

U – жоғарғы үшбұрыш матрица

Р-ауыстыру матрицасы, яғни Р – А сияқты матрица, бірақ оның жолдары ауыстырылған.

Сонымен, біз үшбұрыштың теңдеулер жүйесін шешеміз:

Ly=Pb және Ux=y

Алдымен у-ті, одан кейін х-ті табамыз.

PA=LU

А матрицасының жолдарын Р-ға реттеуді pivoting (беру) деп аталады. Бұл сандық орнықтылық үшін қажет.

Біз жартылай бұрудың стандарт схемасын қолданамыз: бұл L оның диагоналлінде 1-лер бар және басқа элементтері модуль бойынша 1-мен шектелген деген сөз.

Гаусс әдісінің қарапайым нұсқасы – бас элементті таңдау. Ол А матрицасының бір жолдарын басқа жолдарға қосып, диагональ астындағы элементтерін 0-ге айналдыру керек. Сонда Гаусстың алгоритмінің тізбекті коды мынадай:

?

Ары қарай біз A(I,j,k,l) белгілеуін қолданамыз, бұл i-ден j-ге дей3н жолдары ж2не к-дан 1-ге дейінгі бағандары бар ішкі матрица деген сөз.

?

Бір қатарын түрлендіру ең үлкен жұмыс, түрлендіру өзінен кейін (n-k)x(n-k) өлшемді A(k+1:n,k+1:n) ішкі матрицасын алып жүреді, олардың әрбіреуі паралель жаңартылуы мүмкін.

?

хабар беру бір қадамда жасауы мүмкін деп санайық, n-1 хабар беру болады,олар тізбекті орындалу керек, өйткені жолдар әрбір хабар беру аралығында өзгереді, I – ші хабар беру n-i+1 элементтен тұрады.

жол жіберілген кейін, әрбір pi процессорынан жоғары pi процессоры хабар алады, оның көбейткішін есептейді, және берілген жолдың n-j+2 элементіне әсер етеді. Көбейткіштерді есептеуді ескермей n-j+2 көбейтінді және n-j+2 айырыма жасау қажет.

a[][] және b[] теңдеу тұрақтыларынан тұратын белгісіздерден тұратын x[] массиві берілген, сондай-ақ қажетті итерациялар санын (limit) таптық деп есептейік, сонда Якоби алгоритмінің тізбекті коды келесі түрде көрсетіледі.

For (i=; i

{x[i]=b[i];

for (it=0; it

{for (i=0; i

{ sum=0;

for (j=0; j

if (i!=j) sum=sum+a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];}

for (i=0; iОсы кодты паралельдейміз. Кез келген белгісіз үшін бір процесс белілген және әрбір итерацияда жақын арада есептелінген белгісіздер саны басқа барлық процесстерге берілуі керек.

Паралель кодта біз нақты бір барьер қосылуы керек, pi процессі төмендегі түрде болады:

x[i]=b[i];

for()it=0;it

{ for()j=0;j

sum=sum+a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];

broadcast_receive(&new_x[i]);

global_barrier();}

Хабар беру шаблоны - broadcast_receive(), жақын арада есептелген x[i] мәнін процесінен басқа кез-келген процеске жібереді және басқа процесінен жіберген деректерді жинайды.

Сонда есептеу уақыты:

Ал байланыс уақыты: