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

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

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

NovaInfo56, с. 6-10
Опубликовано 6 декабря 2016
Раздел: Физико-математические науки
Просмотров за месяц: 40
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 (дата обращения: 23.02.2022).

Поделиться

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

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

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

В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

Общие сведения об итерационных методах или методе простой итерации

Метод итерации — это численный и приближенный метод решения СЛАУ.

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня 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_, i = 1, 2. n$

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

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

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

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

Готовые работы на аналогичную тему

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

$\begin\begin10x_1 + x_2 − x_3 = 11\\x_1 + 10x_2−x_3 = 10\\−x_1 + x_2 + 10x_3 = 10\end\end$

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

$\begin\beginx_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 + 1\end\end$

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

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

$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