При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат. Поэтому иногда удобнее использовать приближенные итерационные численные методы, метод Якоби относится к таким. В работе требуется решить систему линейных алгебраических уравнений вида: При предположении, что диагональные коэффициенты ненулевые. Решив 1-ое уравнение системы относительно x1 получим: Данный процесс называется итерационным, условием окончания является достижение заданной точности система сходится и есть решение или прерывание процесса. Процесс прерывается когда число итераций превышает заданное допустимое количество, при этом система не сходится либо заданное количество итераций не хватило для достижения требуемой точности. Верхний индекс в скобках - номер итерации. Если последовательность приближений x 0 ,x 1 , Если в системе выполняется диагональное преобладание, то метод Якоби сходится. Критерий окончания итераций при достижении требуемой точности имеет вид: При распараллеливании алгоритма предполагается, что размерность системы больше числа процессоров. Перед началом выполнения метода на каждый процессор рассылаются необходимые данные: После получения необходимой информации каждый процессор будет вычислять соответствующие компоненты вектора X и передавать их главному процессору. Главный процессор при получении очередного приближения решения Xk должен сравнить его с предыдущим приближением Xk Если норма разности этих векторов: В противном случае вектор Xk поэлементно будет разослан всем процессам и будет вычисляться очередное приближение решения. Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой: Время, затраченное на параллельное выполнение алгоритма на p процессорах без учета затрат на передачу данных, выражается формулой: Разработанный способ параллельных вычислений позволяет достичь идеальных показателей ускорения и эффективности. Первоначальная рассылка данных требует следующее время: Передача данных, выполняемая в итерационном процессе, затрачивает следующее время: В итоге общее время передачи данных выражается формулой: Это время зависит от числа итераций. Как правило, их количество меньше числа уравнений n. Значит время на передачу данных можно оценить величиной: Если число итераций будет сравнимо с n , то для времени выполнения алгоритма будет справедлива уже другая оценка: Эксперименты проводились на следующем компьютере: Процессор Intel R Core TM iQM CPU 2. Результаты программы MPI Размер матрицы. Lobachevsky State University of Niznhi Novgorod. Постановка задачи При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат. Метод решения Решив 1-ое уравнение системы относительно x1 получим: Анализ эффективности Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой: Определим время, затрачиваемое на передачу данных. Для этого используем модель Хокни. Результаты вычислительных экспериментов Эксперименты проводились на следующем компьютере: Результаты программы MPI Размер матрицы Последовательный алгоритм 1 процесс 4 процесса 2 процесса Параллельный алгоритм мс Теор. Каждое значение, представленное в данной таблице, является средним временем на основе 25 экспериментов. Размер матрицы 8 процессов 4 процесса 2 процесса Последовательный алгоритм мс Параллельный алгоритм мс Теор. Отчёт Якоби Постановка задачи При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат.
Затем выбирается начальное приближение к решению системы уравнений и находится последовательность приближений к корню. Для сходимости итерационного процесса достаточно, чтобы было выполнено условие. Критерий окончания итераций зависит от применяемого итерационного метода. Самый простой способ приведения системы к виду удобному для итерации состоит в следующем: В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:. Решение системы линейных уравнений методом Якоби. Метод можно рассматривать как модификацию метода Якоби. Расчетная формула метода в покоординатной форме записи выглядит так:. Условия сходимости и критерий окончания итераций можно взять такими же как в методе Якоби. Решение систем линейных уравнений методом Зейделя. Пусть матрица системы уравнений A - симметричная и положительно определенная. Тогда при любом выборе начального приближения метод Зейделя сходится. Дополнительных условий на малость нормы некоторой матрицы здесь не накладывается. Если A - симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:. Пусть и - минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра. Решение систем линейных уравнений методом простой итерации. Дата последнего обновления информации на сайте: Теория погрешностей и машинная арифметика. Методы бисекций, простой итерации, Ньютона. Обусловленность задачи нахождения корня. Решение систем линейных алгебраических уравнений. Нормы векторов и матриц. Решение систем линейных алгебраических уравнений прямыми методами. Решение систем линейных алгебраических уравнений итерационными методами. Решение задачи Коши одношаговыми методами. В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам: Компоненты вектора d вычисляются по формулам: Расчетная формула метода простой итерации имеет вид , или в покоординатной форме записи выглядит так: Критерий окончания итераций в методе Якоби имеет вид: Расчетная формула метода в покоординатной форме записи выглядит так: Если A - симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду: Расчетная формула метода простой итерации в этом случае имеет вид: Научно-практический журнал "Exponenta Pro. Приглашаем преподавателей к участию в конкурсе ИТ-Прорыв! Курс введения в вычислительную математику.
https://gist.github.com/04e9b9f54dfbaec8e6f25a20c2e4cef8
https://gist.github.com/41bf432c4887102d38755290f6c64757
https://gist.github.com/b91008b72d303f77ec06b9bc74d1034e