Суперкомпьютеры 2020 инд. 9 Метод Якоби численного решения СЛАУ. Постановка задачи
 Скачать 125.19 Kb.
|
|
Постановка задачи 1) Реализовать последовательный алгоритм метода Якоби 2) Реализовать параллельный алгоритм численного решения СЛАУ с помощью OpenMP на системе с общей памятью 3) Провести сравнение скорости работы двух алгоритмов При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат. Поэтому иногда удобнее использовать приближенные (итерационные) численные методы, метод Якоби относится к таким. В работе требуется решить систему линейных алгебраических уравнений вида: При предположении, что диагональные коэффициенты ненулевые. Метод решения Решив 1-ое уравнение системы относительно x1 получим: 2-ое - относительно x2 , n-ое - относительно xn В итоге эквивалентная система, в которой диагональные элементы строки выражены через оставшиеся. Далее вводится некоторое начальное приближение - вектор x(0)=[b1/a11, ... ,bi/aii, ... ,bn/ann], затем используя x(1) находится x(2). Данный процесс называется итерационным, условием окончания является достижение заданной точности (система сходится и есть решение) или прерывание процесса. Процесс прерывается когда число итераций превышает заданное допустимое количество, при этом система не сходится либо заданное количество итераций не хватило для достижения требуемой точности. Итерационный процесс. Верхний индекс в скобках - номер итерации. Если последовательность приближений (x(0),x(1),...,x(k+1),...) имеет предел то этот предел является решением. k=1,2,3,...N-1. , N-1 - заданное количество итераций Достаточный признак сходимости метода Якоби: Если в системе выполняется диагональное преобладание, то метод Якоби сходится. Критерий окончания итераций при достижении требуемой точности имеет вид: где ε - заданная точность вычисления Параллельная схема При распараллеливании алгоритма предполагается, что размерность системы больше числа процессоров. Каждый процессор считает “свои” элементы вектора Х=(x1,x2,x3,...,xn). Перед началом выполнения метода на каждый процессор рассылаются необходимые данные: 1) размерность системы N 2) начальное приближение X0 3) строки матрицы A 4) элементы вектора свободных членов b. После получения необходимой информации каждый процессор будет вычислять соответствующие компоненты вектора X и передавать их главному процессору. Главный процессор при получении очередного приближения решения Xk должен сравнить его с предыдущим приближением Xk-1. Если норма разности этих векторов: ||Xk – Xk-1|| = max {|Xk,i – Xk,i-1|, i = 1,1,…n} окажется меньше или равной заданной точности (ε), то вычисления закончатся. В противном случае вектор Xk поэлементно будет разослан всем процессам и будет вычисляться очередное приближение решения. |