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

Содержание

Итерационные методы решения СЛАУ
Сущность итерационных методов решения систем линейных уравнений
Метод Якоби (метод простых итераций СЛАУ)
Готовые работы на аналогичную тему
Метод Гаусса-Зейделя
Итерационные методы решения системы линейных алгебраических уравнений
Общие сведения об итерационных методах или методе простой итерации
Метод Якоби
Метод Зейделя
Метод простой итерации
Решение СЛАУ методом простой итерации
Метод итераций для системы уравнений в Excel
Методы Зейделя и простой итерации
Методы решения систем линейных алгебраических уравнений
Метод простых итераций
Готовые работы на аналогичную тему
Метод Зейделя

Итерационные методы решения СЛАУ

Вы будете перенаправлены на Автор24

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

Особенность прямых методов состоит в том, что вычисления в них всегда проводятся точно, например, с использованием целых чисел, но при этом эти методы трудно применимы для вычисления решений для больших систем. К прямому методу относится, например, метод Крамера.

Ниже подробно рассмотрены итерационные методы решения СЛАУ.

Сущность итерационных методов решения систем линейных уравнений

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

Процесс вычисления одного столбца называется итерацией.

Различают несколько основных способов итерационного решения СЛАУ:

Метод Якоби (метод простых итераций СЛАУ)

Рассмотрим систему уравнений, с коэффициентами, которые можно записать в виде матрицы:

$A=\left(\begin a_ <11>& a_ <12>& … & a_ <1n>\\ a_ <21>& a_ <22>& … & a_ <2n>\\ … & … & … & … \\ a_ & a_ & … & a_ \\ \end\right)$

Саму же систему уравнений можно записать в виде равенства $A \cdot X = F$, где $X$ — вектор-столбец собственных значений системы, а $F$ — вектор-столбец свободных членов.

Метод состоит в том, чтобы в каждом уравнении системы выразить соответственно $x_1, x_2,…, x_n$ и затем получить новую матрицу $B$, у которой элементы главной диагонали принимают нулевые значения.

В общем виде формула для вычисления корней уравнений записывается так: $\overrightarrow= B\overrightarrow + \overrightarrow$

Добиться такого вида от системы можно следующими способами:

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

$B= E – D^<-1>A=D^<-1>(D-A), \overrightarrow = D^<-1>\overrightarrow;$

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

Процедура нахождения корней тогда запишется так:

$\overrightarrow^<(k+1)>= B\overrightarrow^ <(k)>+ \overrightarrow$

Для конкретного элемента она будет выглядеть так:

$x_^=\frac<1>(b_i — \sum\limits_ a_ij\cdot x_j^(k)\left(1\right)$, где $i=1,2,…, n$

буквой $(k)$ во всех формулах выше обозначается номер итерации, сама же формула $(1)$ называется рекуррентной.

Окончание вычисления происходит в том случае, если разница между вычислениями в двух соседних итераций составляет не более чем $ε_1$:

В упрощённой форме условие окончания итераций выглядит как $||x^<(n+1)>-x^<(n)>||$

Порядок решения СЛАУ методом Якоби такой:

Приведение системы уравнений к виду, в котором на каждой строчке выражено какое-либо неизвестное значение системы.

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

Производим подстановку произвольного нулевого решения в систему уравнений, полученную под пунктом 1.

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

Метод Гаусса-Зейделя

Сущность этого метода состоит в том, что в нём переносятся в правые части все члены уравнений, индекс при которых больше индекса, выражаемого $x$. В краткой форме это можно записать так:

$(L + D) \cdot \overrightarrow = -U\overrightarrow + \overrightarrow$

Сами итерации в методе Гаусса-Зейделя производятся по формуле:

$(L +D)\overrightarrow^<(k+1)>=-U\overrightarrow^ <(k)>+ \overrightarrow$

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

Читайте также: Способ завивки волос выпрямителем
Метод простых итераций: пример решения

Дана система уравнений:

$\begin 10x_1 – x_2 + 2x_3 = 6 \\ -x_1 + 11x_2 – x_3 + 3x_4 = 25 \\ 2x_1- x_2 + 10x_3 -x_4 = -11 \\ 3x_2 – x_3 + 8x_4 = 15 \end$

Решите данную систему с помощью метода простых итераций.

Выберем в качестве нулевого приближения корни $(0; 0; 0; 0)$ и подставим их в преобразованную систему:

$\begin x_1 = (6 + 0 – (2 \cdot 0))/10 = 0,6 \\ x_2 = (25 + 0 – 0 – (3 \cdot 0))/11 = 25/11 = 2,2727 // x_3 = (-11 – (2 \cdot 0) + 0 + 0) /10 = -1,1 \\ x_4 = (15 – (3 \cdot 0) + 0) / 8 = 1,875\\ \end$

Проведём 5 итераций, используя на каждой результат, полученный с предыдущей и для них получим следующую таблицу:

Рисунок 1. Таблица итераций для решения СЛАУ. Автор24 — интернет-биржа студенческих работ

Продолжать вычисление можно до достижения заданной требуемой точности. Точный ответ системы — $(1; 2; -1; 1)$.

Источник

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

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

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

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

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

Источник

Решение СЛАУ методом простой итерации

Назначение сервиса . Онлайн-калькулятор предназначен для решения СЛАУ методом простой итерации в онлайн режиме (см. пример решения). Для проверки решения генерируется шаблон в Excel .

Шаг №1

Шаг №2

Видеоинструкция

Рассмотрим достаточные условия сходимости итерационной последовательности n>.
Практически, для применения метода итерации систему линейных уравнений удобно «погрузить» в одну из трёх следующих метрик:
(3.4)
Для того, чтобы отображение F, заданное в метрическом пространстве соотношениями (3.2), было сжимающим, достаточно выполнение одного из следующих условий:
а) в пространстве с метрикой ρ₁: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по строкам, должна быть меньше единицы.
б) в пространстве с метрикой ρ₂: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по столбцам, должна быть меньше единицы.
в) в пространстве с метрикой ρ₃: , т. е. сумма квадратов при неизвестных в правой части системы (3.2) должна быть меньше единицы

Пример . Вычислить два приближения методом простой итерации. Оценить погрешность второго приближения. В качестве начального приближения выбрать x 0 =(0; 0; 0).

Так как диагональные элементы системы являются преобладающими, то приведем систему к нормальному виду:

Последовательные приближения будем искать по формулам:

Получаем:
x 1 =(-1.9022; 0.4889; 2.1456), x 2 =(-1.1720; 0.6315; 1.2389).
Для оценки погрешности в метрике ρ₁ вычисляем коэффициент μ
.
Вычисляем погрешность:

При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае для решения СЛАУ иногда удобнее пользоваться методом простой итерации.

Метод итераций для системы уравнений в Excel

Для вычисления точности epsilon .
Итерация №1: =ABS(B7)-ABS(B6);=ABS(C7)-ABS(C6);=ABS(D7)-ABS(D6)
Итерация №2: =ABS(B8)-ABS(B7);=ABS(C8)-ABS(C7);=ABS(D8)-ABS(D7)
Скачать шаблон решения.

Источник

Методы Зейделя и простой итерации

Вы будете перенаправлены на Автор24

Методы Зейделя и простой итерации — это методы решения систем линейных алгебраических уравнений при помощи итераций.

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

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

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

В итерационных методах обычно присутствуют следующие основные этапы:

Приведение исходной системы вида $ ¯A * ¯x = ¯b $ к итерационной форме.

Осуществление проверки условия сходимости.

Реализация решения системы выбранным методом.

Метод простых итераций

Для систем общего вида должно выполняться тождество m = n, где m — это число уравнений в системе, а n — это количество неизвестных.

То есть, нет смысла в решении не доопределенных (m меньше n) и переопределенных (m больше n) систем уравнений, так как их можно свести за счёт элементарных алгебраических преобразований к нормальным (m=n) системам линейных уравнений. Иначе говоря, когда присутствует «ненормальная» система уравнений, то перед началом использования метода простых итераций, следует преобразовать её в нормальную.

Читайте также: Сбер аптека способ оплаты
Готовые работы на аналогичную тему

Систему линейных уравнений можно записать в матричной форме, где:

A является матрицей коэффициентов.

b является вектором свободных членов.

x является вектором неизвестных.

В качестве примера рассмотрим следующую систему:

Рисунок 1. Система уравнений. Автор24 — интернет-биржа студенческих работ

Представим её в матричной форме:

Рисунок 2. Система уравнений в матричной форме. Автор24 — интернет-биржа студенческих работ

Первый этап итерационного метода заключается в преобразовании исходной системы, то есть матрицы А и вектора b в итерационную форму, где С и d являются итерационными формами исходных данных.

Преобразование в итерационный вид может быть реализована по следующим формулам:

$c_ = -a_ / a_$ $D_i = b_i / a_$ где i, j = 1,2,3…

Необходимо заметить, что диагональные компоненты новой матрицы обнуляются, хотя должны быть равны -1. В результате для рассматриваемой системы получается:

Рисунок 3. Матрица. Автор24 — интернет-биржа студенческих работ

Если выполнять преобразование исходной системы к итерационной форме, то она не удовлетворит условию сходимости:

Рисунок 4. Формула. Автор24 — интернет-биржа студенческих работ

То есть отдельные элементы матрицы C оказываются больше единицы. А по условию сходимости, приведённому выше, очевидно, что, если хотя бы один элемент будет больше единицы, то условие не выполнится, и решение системы путем простых итераций найти невозможно. Прежде чем осуществлять этапы итерационных методов, следует привести исходную систему к виду, в котором все диагональные компоненты будут максимальными по модулю в своих строках. Лишь при этом виде матрицы коэффициентов будет выполняться условие сходимости.

Очевидно, что в рассматриваемом примере третий элемент третьей строки по модулю больше других. Его следует оставить неизменным. Необходимо поменять местами первую и вторую строки, а далее умножить строку, ставшую первой, на минус единицу и сложить её с новой второй строкой. В результате получится:

Рисунок 5. Матрица. Автор24 — интернет-биржа студенческих работ

Теперь при подстановке в формулы итерационная форма получится верной и второй этап, то есть проверка условия сходимости, может быть успешно пройден. Если же система не проходит эту проверку, то приближения не будут сходиться к реальному решению, и ответ получен не будет. Если же условие сходимости исполняется, то стратегия метода простых итераций может быть применена и можно переходить к третьему этапу. В конечном счете будет получена система линейных алгебраических уравнений в итерационной форме:

Рисунок 6. Система линейных уравнений. Автор24 — интернет-биржа студенческих работ

Здесь $x_1, x_2, x_3$ являются приближениями, которые получаются на текущем шаге итерации за счет приближений, найденных на предыдущей итерации — $x^0_1, x^0_2, x^0_3$.

Итерационный процесс по методу простых итераций продолжается до тех пор, пока вектор приближений не придёт к необходимой точности, то есть, пока не исполнится условие выхода:

$Max|x_i – x^0_i|$ ∠ $ε$

Здесь ε является требуемой точностью.

Метод Зейделя

Как уже отмечалось выше, метод простых итераций и метод Зейделя, по своей сути, являются идентичными. Разница заключается в том, что в методе Зейделя вычисление вектора приближений на текущей итерации выполняется с применением данных, которые были получены ни только на предыдущей, но и на исполняемой итерации. Это означает, что элемент x1 определяется через x2 и x3, величины которых были рассчитаны на предыдущей итерации, а последующий элемент x2 уже рассчитывается на основании x1, найденного именно на текущей итерации, и x3, вычисленного на предыдущей. Иначе говоря, данные в методе Зейделя для определения вектора X используются в процессе расчётов по мере их вычисления. А в методе простых итераций применяются данные, которые были получены именно на предыдущей итерации.

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

Ниже представлена программная реализация метода Зейделя:

Procedure Zeidel(C:array of array of real;d:array of real;n:integer);

Источник