Программа решения систем линейных уравнений методом якоби

Отчёт (Якоби)

Постановка задачи

При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат. Поэтому иногда удобнее использовать приближенные (итерационные) численные методы, метод Якоби относится к таким.

В работе требуется решить систему линейных алгебраических уравнений вида:

При предположении, что диагональные коэффициенты ненулевые.

Метод решения

Решив 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 поэлементно будет разослан всем процессам и будет вычисляться очередное приближение решения.

Анализ эффективности

Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой:
T = k * (2*n^2 — n), где k – число выполненных итераций, а n – число уравнений.

Время, затраченное на параллельное выполнение алгоритма на p процессорах без учета затрат на передачу данных, выражается формулой:
T(p) = k/p * (2*n^2 — n)

Тогда ускорение равно:
S = T(1) / T(p) = p

Эффективность:
E = T1 / p*Tp = 1

Разработанный способ параллельных вычислений позволяет достичь идеальных показателей ускорения и эффективности.

Определим время, затрачиваемое на передачу данных. Для этого используем модель Хокни.

Первоначальная рассылка данных требует следующее время:
Tcomm1 = (p-1) * (4*alfa + (n^2 / p + n) / betta), где alfa — латентность, betta — пропускная способность сети

Передача данных, выполняемая в итерационном процессе, затрачивает следующее время:
Tcomm2 = k * (p-1) * (3*alfa + (n / p + n) / betta), где k — количество выполненных итераций

В итоге общее время передачи данных выражается формулой:
Tcomm = (p-1) * (4*alfa + (n^2 / p + n) / betta) + k * (p-1) * (3*alfa + (n / p + n) / betta)

Это время зависит от числа итераций. Как правило, их количество меньше числа уравнений n. Значит время на передачу данных можно оценить величиной:
Tcomm = O(n^2)
В свою очередь и ко времени выполнения алгоритма применима та же оценка:
T = O(n^2)

Если число итераций будет сравнимо с n, то для времени выполнения алгоритма будет справедлива уже другая оценка:
T = O(n^3)

Демонстрация

На каждой итерации итерации вычисление (k+1)-ого вектора происходит по следующей схеме:

Результаты вычислительных экспериментов

Эксперименты проводились на следующем компьютере: Процессор Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz, ОС Windows 8 64-bit.

Решение системы линейных алгебраических уравнений. Метод Якоби

Стерлитамакский филиал Башкирского государственного университета

NovaInfo56, с. 6-10
Опубликовано 6 декабря 2016
Раздел: Физико-математические науки
Просмотров за месяц: 41
CC BY-NC

Аннотация

В работе рассмотрено решение СЛАУ одним из методов простых итераций, методом Якоби. Данная задача имеет значимую прикладную роль при решении научных и промышленных проблем. Кроме этого, считается вспомогательной при реализации многочисленных алгоритмов вычислительной математики, математической физики, обрабатывания результатов экспериментальных исследований. Написана компьютерная программа на языке программирования C++, позволяющая найти решение СЛАУ.

Ключевые слова

Текст научной работы

Пусть дана система линейных уравнений:

A=\begin a_ <11>& \cdots & a_<1n>\\ \vdots & \ddots & \vdots\\ a_ <1n>& \cdots & a_ \end

\begin a_<11>x_1+\cdots+a_<1n>x_n=b_1 \\ \cdots \\ a_x_1+\cdots+a_x_n=b_n\end

Представим матрицу A системы (1) в виде:

Где D — диагональная, L — левая треугольная матрица и R — правая треугольная матрица. Тогда система (1) может быть записана в виде:

И если на диагонали исходной матрицы не будет нулей, то эквивалентной (1) задачей будет:

Приведение системы (2) к виду (4) основано на методе простых итераций, который называется метод Якоби. В матричном виде он представляется формулой:

Для того, чтобы записать решение системы (1) метод Якоби в развернутом виде, достаточно заметить, что обратная матрица к матрице D=(a_)_^n

служит диагональная матрица D^

с элементами диагонали d_=\frac<1>>

. Поэтому представление (4) системы (1), записанной в виде (3), равнозначно выражению диагональных элементов через другие:

\begin x_1=-(a_<12>x_2+a_<13>x_3+\cdots+a_<1n>x_n-b_1)/a_ <11>\\ \cdots \\ x_n=-(a_x_1+a_x_2+\cdots+a_x_-b_n)/a_ \end

Далее для записи итерационного процесса (5) расставим в равенствах системы (6) итерационные индексы:

Таким образом, для реализации данного метода все a_\neq 0

. Если в системе выполняется диагональное преобладание, то метод Якоби сходится.

Диагональное преобладание матрицы A означает, что

Критерий для окончания итераций:

— заданная точность для вычислений.

Реализация метода в среде C++

Материал, изложенный в статье, будет интересен и полезен студентам физико-математических специальностей. Программа проста в использовании и нетребовательна к ресурсам. Она находит решение за малое количество итераций и также делает проверку, с помощью которой мы можем убедиться в правильности работы программы и действительно ли метод Якоби находит верное решение.

Читайте также

Средства стохастической подготовки обучающихся на основе информационных технологий

Инструментальная реализация прикладной математической подготовки бакалавра экономики и менеджмента

1. Синчуков А.В.

NovaInfo59, с.24-28, 13 февраля 2017 , Физико-математические науки, CC BY-NC

Список литературы

1. Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения. Учеб. пособие для вузов. — М.: Высшая школа, 2000, 266 с.
2. Кризский В.Н. Численные методы линейной алгебры: Учебно — методическое пособие / Изд-во Стерлитамакской госпедакадемии – Стерлитамак, 2006 – 80 с.

Цитировать

Алексеева, К.В. Решение системы линейных алгебраических уравнений. Метод Якоби / К.В. Алексеева. — Текст : электронный // NovaInfo, 2016. — № 56. — С. 6-10. — URL: https://novainfo.ru/article/9182 (дата обращения: 26.02.2022).

Поделиться

Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

Соучредители СМИ: Долганов А.А., Майоров Е.В.

Программная реализация метода Якоби

Автор: Пользователь скрыл имя, 28 Декабря 2010 в 00:25, реферат

Краткое описание

В отличие от метода Гаусса-Зейделя мы не можем заменять на в процессе итерационной процедуры, т.к. эти значения понадобятся для остальных вычислений. Это наиболее значимое различие между методом Якоби и методом Гаусса-Зейделя решения СЛАУ. Таким образом на каждой итерации придётся хранить оба вектора приближений: старый и новый.

Файлы: 1 файл

Реализация метода Якоби.docx

Московский Государственный Университет Приборостроения и Информатики

По дисциплине: Вычислительная математика

Тема: «Программная реализация метода Якоби»

Работу выполнил: Козеев И.В.

Возьмём систему линейных уравнений:

Для того, чтобы построить итеративную процедуру метода Якоби, необходимо провести предварительное преобразование системы уравнений к итерационному виду . Оно может быть осуществлено по одному из следующих правил:

где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы U и L содержат верхнюю и нижнюю треугольные части A, на главной диагонали которых нули, E — единичная матрица .

Тогда процедура нахождения решения имеет вид:

где k счётчик итерации.

В отличие от метода Гаусса-Зейделя мы не можем заменять на в процессе итерационной процедуры, т.к. эти значения понадобятся для остальных вычислений. Это наиболее значимое различие между методом Якоби и методом Гаусса-Зейделя решения СЛАУ . Таким образом на каждой итерации придётся хранить оба вектора приближений: старый и новый.

Приведем достаточное условие сходимости метода.

Условие окончания итерационного процесса при достижении точности в упрощённой форме имеет вид:

(Существует более точное условие окончания итерационного процесса, которое более сложно и требует дополнительных вычислений)

Алгоритм реализации на C++

#define eps 0.001 //желаемая точность

void Jacobi (int N, double **A, double *F, double *X)

// N — размерность матрицы; A[N][N] — матрица коэффициентов, F[N] — столбец свободных членов,

// X[N] — начальное приближение, ответ записывается также в X[N];

double * TempX = new double[N];

double norm; // норма, определяемая как наибольшая разность компонент столбца иксов соседних итераций.