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

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

Вы будете перенаправлены на Автор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. Приведение системы уравнений к виду, в котором на каждой строчке выражено какое-либо неизвестное значение системы.
2. Произвольный выбор нулевого решения, в качестве него можно взять вектор-столбец свободных членов.
3. Производим подстановку произвольного нулевого решения в систему уравнений, полученную под пунктом 1.
4. Осуществление дополнительных итераций, для каждой из которых используется решение, полученное на предыдущем этапе.

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

Сущность этого метода состоит в том, что в нём переносятся в правые части все члены уравнений, индекс при которых больше индекса, выражаемого $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)$.

Получи деньги за свои студенческие работы

Курсовые, рефераты или другие работы

Автор этой статьи Дата последнего обновления статьи: 13 02 2022

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

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

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

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

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

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

Стандартные итерационные методы

В разделах Метод исключения Гаусса и Методы решения систем с симметричными матрицами процедуры решения систем алгебраических уравнений были связаны с разложением матрицы коэффициентов \( A \). Методы такого типа называются прямыми методами. Противоположностью прямым методам являются итерационные методы. Эти методы порождают последовательность приближенных решений \( \ < x^<(k)>\> \). При оценивании качества итерационных методов в центре внимания вопрос от том, как быстро сходятся итерации \( x^ <(k)>\).

Итерации Якоби и Гаусса — Зейделя

Простейшей итерационной схемой, возможно, являются итерации Якоби. Они определяются для матриц с ненулевыми диагональными элементами. Идею метода можно представить, используя запись \( 3 \times 3 \)-системы \( Ax = b \) в следующем виде: $$ \begin x_1 &= (b_1 — a_<12>x_2 — a_<13>x_3) / a_<11>, \\ x_2 &= (b_2 — a_<21>x_1 — a_<23>x_3) / a_<22>, \\ x_3 &= (b_3 — a_<31>x_1 — a_<32>x_2) / a_<33>. \\ \end $$ Предположим, что \( x^ <(k)>\) — какое-то приближение к \( x = A^<-1>b \). Чтобы получить новое приближение \( x^ <(k+1)>\), естественно взять: $$ \begin x_1^ <(k+1)>&= (b_1 — a_<12>x_2^ <(k)>— a_<13>x_3^<(k)>) / a_<11>, \\ x_2^ <(k+1)>&= (b_2 — a_<21>x_1^ <(k)>— a_<23>x_3^<(k)>) / a_<22>, \\ x_3^ <(k+1)>&= (b_3 — a_<31>x_1^ <(k)>— a_<32>x_2^<(k)>) / a_<33>. \\ \end $$

Эти формулы и определяют итерации Якоби в случае \( n = 3 \). Для произвольных \( n \) мы имеем $$ \begin \tag <7>x_i^ <(k+1)>= \left( b_i — \sum_^ a_x_j^ <(k)>— \sum_^ a_x_j^ <(k)>\right)/a_, \quad i = 1, 2, \ldots, n. \end $$

Заметим, что в итерациях Якоби при вычислении \( x_i^ <(k+1)>\) не используется информация, полученная в самый последний момент. Например, при вычислении \( x_2^ <(k+1)>\) используется \( x_1^ <(k)>\), хотя уже известна компонента \( x_1^ <(k+1)>\). Если мы пересмотрим итерации Якоби с тем, чтобы всегда использовать самые последние оценки для \( x_i \), то получим: $$ \begin \tag <8>x_i^ <(k+1)>= \left( b_i — \sum_^ a_x_j^ <(k+1)>— \sum_^ a_x_j^ <(k)>\right)/a_, \quad i = 1, 2, \ldots, n. \end $$ Так определяется то, что называется итерациями Гаусса — Зейделя.

Для итераций Якоби и Гаусса — Зейделя переход от \( x^ <(k)>\) к \( x^ <(k+1)>\) в сжатой форме описывается в терминах матриц \( L, D \) и \( U \), определяемых следующим образом: $$ \begin L &= \begin 0 & 0 &\cdots & \cdots & 0 \\ a_ <21>& 0 &\cdots & \cdots & 0 \\ a_ <31>& a_ <32>& 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots &\vdots\\ a_ & a_ & \cdots & a_ & 0 \end, \\ D &= \mathrm(a_<11>, a_<12>, \ldots, a_), \\ U &= \begin 0 & a_ <12>&a_ <13>& \cdots & a_ <1n>\\ 0 & 0 & a_ <23>& \cdots & a_ <2n>\\ \vdots & \vdots & \ddots & \ddots &\vdots\\ 0 & 0 & \cdots & 0 & a_ \\ 0 & 0 & \cdots & 0 & 0 \end. \end $$ Шаг Якоби имеет вид \( M_J x^ <(k+1)>= N_J x^ <(k)>+ b \), где \( M_J = D \) и \( N_J = -(L+U) \). С другой стороны, шаг Гаусса — Зейделя определяется как \( M_G x^ <(k+1)>= N_G x^ <(k)>+ b \), где \( M_G = (D+L) \) и \( N_G = -U \).

Процедуры Якоби и Гаусса — Зейделя — это типичные представители большого семейства итерационных методов, имеющих вид $$ \begin \tag <9>M x^ <(k+1)>= N x^ <(k)>+ b, \end $$ где \( A = M-N \) — расщепление матрицы \( A \). Для практического применения итераций (9) должна «легко» решаться система с матрицей \( M \). Заметим, что для итераций Якоби и Гаусса — Зейделя матрица \( M \) соответственно диагональная и нижняя треугольная.

Сходятся ли итерации (9) к \( x = A^<-1>b \), зависит от собственных значений матрицы \( M^<-1>N \). Определим спектральный радиус произвольной \( n \times n \)-матрицы \( G \) как $$ \rho(G) = \max \< |\lambda| :\ \lambda \in \lambda(G) \>, $$ тогда если матрица \( M \) невырожденная и \( \rho(M^<-1>N) —>