Условие сходимости метода якоби

Условие сходимости метода якоби

Числовые параметры k вводят для ускорения сходимости. Способ выбора итерационных параметров определяется при исследовании сходимости метода, т.е. при каких значениях параметров метод сходится и когда сходимость будет наиболее быстрой, тогда соответствующие параметры будут оптимальными.

Итерационный метод называют явным, если Bk+1 — единичная матрица. Неявные итерационные методы применяют в том случае, когда решение системы уравнений с матрицей Bk требует меньше машинной памяти, времени, алгоритмически проще, чем решение исходной системы.

Методом простой итерации называют явный метод с постоянным параметром

где r (k) = Ax (k) — b — вектор невязки. Метод сходится для симметричных положительно определенных матриц

Для окончания итерационного процесса используют три способа.

При первом определяют величину стабилизации и прекращают вычисления, если она меньше , т.е.

Недостатком этого способа является то, что при медленно сходящихся итерациях величина стабилизации может быть малой, хотя приближенное решение отличается от точного.

При втором способе вычисляют нормы невязки до начала итераций и на каждой итерации. Итерации прекращают при выполнении неравенства

При третьем способе предварительно оценивается число итераций, необходимое для получения заданной точности [6].

Для погрешности итерационного метода выполняются оценки

где q (0,1). Метод сходится со скоростью геометрической прогрессии со знаменателем q. Можно определить, потребовав, чтобы q n (0) — и строится рекуррентная последовательность векторов x (1), x (2), ., x (k), . по формуле

Для сходимости этой последовательности при любом начальном приближении необходимо и достаточно, чтобы все собственные значения матрицы G были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости — итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.

Чем меньше норма матрицы G, тем быстрее сходится итерационный процесс.

Преобразование системы можно осуществить, просто решая каждое i-е уравнение относительно xi:

Метод Зейделя использует следующий алгоритм построения приближений:

Если A — матрица с доминирующей диагональю, т.е.

то метод Зейделя сходится при любом начальном приближении x (0) и

Метод Зейделя сходится примерно так же, как геометрическая прогрессия со знаменателем ||G||. Если норма матрицы G близка к 1, то скорость сходимости очень медленная. Для ускорения сходимости используется метод релаксации [7].

Если 1 — верхняя релаксация. Параметр подбирают, чтобы сходимость метода достигалась за минимальное число итераций.

Метод Зейделя является одношаговым итерационным методам, когда для нахождения x (k+1) требуется помнить только одну предыдущую итерацию x (k).

Читайте также:  Соцсети для творческих людей

Погрешность итерации вычисляется по формуле:

n — порядок матрицы A.

Если меньше заданной точности , то итерационный процесс прекращают.

Элементы главной диагонали называются главными. Если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент, то произойдет сбой программы. Чтобы избежать этого, необходимо сделать перестановку строк таким образом, чтобы на главной диагонали находились максимальные элементы строк, т.е. если в k-й строке максимальным является i-й элемент, то необходимо поменять местами k-ю и i-ю строки, поменять местами соответствующие элементы вектора b. Такой выбор главного элемента необходим для сходимости итерационного процесса.

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

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

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

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

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

Решив 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.

Метод Якоби относится к итерационным способам решения систем линейных алгебраических уравнений (СЛАУ).

Итерация — результат повторяющегося алгоритма, последовательно применяемого к каждому элементу множества, иными словами их обработка методом перебора.

Читайте также:  Имя файла из ячейки excel

Перед тем, как применить итерацию к системе $Ax=b$ необходимо преобразовать ее к виду $x = Bx+d$. После этого следует выполнить начальное приближение к решению $x^ <(0)>= (x_1^0, x_2^0. x_m^0)$ и найти последовательность приближений к корню СЛАУ.

Для проверки итераций на сходимость достаточным является условие $Vert В Vert lt 1$. Процесс итерации заканчивается в зависимости от выбранного метода, одним из которых и является метод Якоби.

Другими популярными методами итерации являются метод Зейделя и метод простой итерации.

Достоинством метода Якоби для приведения системы матрицы к виду, удобному для итерации является его простота. Сначала из каждого уравнения матрицы $A$ следует выразить неизвестное ($x_1, x_2. x_n$). В итоге получается матрица $B$. На ее главной диагонали располагаются нулевые элементы. Остальные вычисляются по формуле:

Попробуй обратиться за помощью к преподавателям

Компоненты (элементы) вектора $d$ вычисляются по формуле:

$d_i = b_i/a_, i = 1, 2. n$

Формула для расчета по методу простой итерации:

Координатная (матричная) запись:

Критерий окончания итераций в методе Якоби:

Если $B lt 1/2$, можно использовать более простой критерий окончания:

Решим методом Якоби следующую СЛАУ с показателем точности $ε = 10^<−3>$:

$eginegin10x_1 + x_2 − x_3 = 11\x_1 + 10x_2−x_3 = 10\−x_1 + x_2 + 10x_3 = 10endend$

Прежде всего, следует привести систему уравнений к виду, удобному для итераций:

$egineginx_1 = −0,1x_2 + 0,1x_3 + 1,1\x_2 = −0,1x_1 + 0,1x_3 + 1\x_3 = 0,1x_1 − 0,1x_2 + 1endend$

Начальное приближение (вектор правой части) выглядит так:

Вычислим первую итерацию:

$x_1^ <(1)>= −0,1 × 1 + 0,1 × 1 + 1,1 = 1,1\x_2^ <(1)>= −0,1 × 1,1 + 0,1 + 1 = 0,99\x_3^ <(1)>= 0,1 × 1,1 − 0,1 × 1 + 1=1,01$

Приближения к решению вычислим аналогично:

Выразим норму матрицы $В$ исходя из сумм модулей элементов каждой строки:

$Vert B Vert_∞ = 0,2$

Поскольку $0,2 lt 1/2$, можно применить простой критерий окончания итерации:

Определим нормы разности векторов:

$Vert x^ <(3)>− x^<(2)>Vert_∞ = 0,002, Vert x^ <(4)>− x^<(3)>Vert_∞ = 0,00002$

Найдя, что $Vert x^ <(4)>− x^<(3)>Vert_∞ lt ε$, мы можем сказать, что на 4-ой итерации достигнута заданная точность.

Ответ:

$x_1 = 1,102; x_2 = 0,991; x_3 = 1,101$

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Ссылка на основную публикацию
Усилитель сигнала для тв антенны отзывы
Характеристика в рейтинге 1 Alcad AL-200 Высокое качество во всех аспектах эксплуатации. Самый популярный усилитель в России 2 Eurosky SWA-105...
У каких авто самый крепкий кузов
Получайте на почту один раз в сутки одну самую читаемую статью. Присоединяйтесь к нам в Facebook и ВКонтакте. Специалисты Шведского...
У какого телефона самая большая память
Производительность, крутые тыловые камеры, объем ОЗУ или выделенный аудиочип – все это не имеет значения для определенных людей, которые ставят...
Усилитель сотового сигнала отзывы
Нашел вот еще информацию что Mobi-900 стал занял 1 место в рейтинге репитеров по версии журнала Provider-Review: http://provider-review.ru/reyting-usiliteley-sotovoy-svyazi.html А вот...
Adblock detector