Отчёт (Якоби)
Постановка задачи
При большом числе неизвестных метод Гаусса становится весьма сложным в плане вычислительных и временных затрат. Поэтому иногда удобнее использовать приближенные (итерационные) численные методы, метод Якоби относится к таким.
В работе требуется решить систему линейных алгебраических уравнений вида:
При предположении, что диагональные коэффициенты ненулевые.
Метод решения
Решив 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.
Итерационные методы решения системы линейных алгебраических уравнений
В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.
Общие сведения об итерационных методах или методе простой итерации
Метод итерации — это численный и приближенный метод решения СЛАУ.
Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .
Рассмотрим систему A x = b .
Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.
Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.
Метод Якоби
Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.
Результатом служит матрица В , в которой на главной диагонали находятся нулевые элементы, а все остальные вычисляются по формуле:
b i j = — a i j / a i i , i , j = 1 , 2 . . . , n
Элементы (компоненты) вектора d вычисляются по следующей формуле:
d i = b i / a i i , i = 1 , 2 , . . . , n
Расчетная формула метода простой итерации:
x ( n + 1 ) = B x ( x ) + d
Матричная запись (координатная):
x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b
Критерий окончания в методе Якоби:
x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε
В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:
x ( n + 1 ) — x ( n ) ε
Решить СЛАУ методом Якоби:
10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10
Необходимо решить систему с показателем точности ε = 10 — 3 .
Приводим СЛАУ к удобному виду для итерации:
x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1
Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.
В таком случае, первая итерация имеет следующий внешний вид:
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
Аналогичным способом вычисляются приближения к решению:
x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111
Находим норму матрицы В , для этого используем норму B ∞ .
Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:
x ( n + 1 ) — x ( n ) ε
Далее вычисляем нормы разности векторов:
x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .
Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.
x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .
Метод Зейделя
Метод Зейделя — метод является модификацией метода Якоби.
Суть: при вычислении очередного ( n + 1 ) — г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) — е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n — о е приближение, как в методе Якоби.
x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +
+ . . . + b i m x m ( n ) + d i
За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.
Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.
Решим 3 системы уравнений:
2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1
Приведем системы к удобному для итерации виду:
x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .
Отличительная особенность, условие сходимости выполнено только для первой системы:
Вычисляем 3 первых приближения к каждому решению:
1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109
Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.
2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129
Итерационный процесс разошелся.
Решение: x 1 = 1 , x 2 = 2
3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2
Итерационный процесс зациклился.
Решение: x 1 = 1 , x 1 = 2
Метод простой итерации
Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:
x = x — τ ( A x — b ) , τ — итерационный параметр.
Расчетная формула имеет следующий внешний вид:
x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .
Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .
Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .
τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .
Метод Якоби 4
Вы будете перенаправлены на Автор24
Метод Якоби относится к итерационным способам решения систем линейных алгебраических уравнений (СЛАУ).
Итерация — результат повторяющегося алгоритма, последовательно применяемого к каждому элементу множества, иными словами их обработка методом перебора.
Перед тем, как применить итерацию к системе $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_
Формула для расчета по методу простой итерации:
Координатная (матричная) запись:
Критерий окончания итераций в методе Якоби:
Если $B \lt 1/2$, можно использовать более простой критерий окончания:
Готовые работы на аналогичную тему
Решим методом Якоби следующую СЛАУ с показателем точности $ε = 10^<−3>$:
$\begin
Прежде всего, следует привести систему уравнений к виду, удобному для итераций:
$\begin
Начальное приближение (вектор правой части) выглядит так:
Вычислим первую итерацию:
$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 02 2022
http://zaochnik.com/spravochnik/matematika/issledovanie-slau/iteratsionnye-metody-reshenija-slau/
http://spravochnick.ru/matematika/metod_yakobi/