Алгоритм метода простых итераций для решения систем линейных уравнений блок схема (8 видео)

Содержание

Итерационные методы решения СЛАУ
Итерационные методы решения системы линейных алгебраических уравнений
Общие сведения об итерационных методах или методе простой итерации
Метод Якоби
Метод Зейделя
Метод простой итерации
📺 Видео

Видео:Решение систем линейных уравнений методом простой итерации в ExcelСкачать

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

Дата добавления: 2013-12-23 ; просмотров: 12847 ; Нарушение авторских прав

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

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

Для применения метода итераций исходную систему (2.1) или (2.2) необходимо привести к виду

, (2.26)

после чего итерационный процесс выполняется по рекуррентным формулам

, k = 0, 1, 2, . . (2.26а)

Матрица G и вектор получены в результате преобразования системы (2.1).

Для сходимости (2.26а) необходимо и достаточно, чтобы |l_i(G)| –1 B= − B –1 C+ B –1 , откуда= − B –1 C+ B –1 .

Положив –B –1 C = G, B –1 = , получим (2.26).

Из условий сходимости (2.27) и (2.28) видно, что представление А = В + С не может быть произвольным.

Если матрица А удовлетворяет условиям (2.28), то в качестве матрицы В можно выбрать нижнюю треугольную:

, a_ii ¹ 0.

; Þ ; Þ ; Þ

Þ .

Подбирая параметр a, можно добиться, чтобы ||G|| = ||E + aA|| Т , будем решать эту систему по технологии (2.26а):

k = 0, 1, 2, . .

Процесс вычисления прекращается, когда два соседних приближения вектора решения совпадают по точности, т. е.

Технология итерационного решения вида (2.26а) названа методомпростой итерации.

Оценка абсолютной погрешности для метода простой итерации:

где символ || . || означает норму.

Пример 2.1. Методом простой итерации с точностью e = 0,001 решить систему линейных уравнений:

Число шагов, дающих ответ с точностью до e = 0,001, можно определить из соотношения

£ 0,001.

Оценим сходимость по формуле (2.27). Здесь ||G|| = = max = 0,61 Т . Подставим значения вектора в (2.26а):

Продолжив вычисления, результаты занесем в таблицу:

k	х₁	х₂	х₃	х₄
2,15	–0,83	1,16	0,44
2,9719	–1,0775	1,5093	–0,4326
3,3555	–1,0721	1,5075	–0,7317
3,5017	–1,0106	1,5015	–0,8111
3,5511	–0,9277	1,4944	–0,8321
3,5637	–0,9563	1,4834	–0,8298
3,5678	–0,9566	1,4890	–0,8332
3,5760	–0,9575	1,4889	–0,8356
3,5709	–0,9573	1,4890	–0,8362
3,5712	–0,9571	1,4889	–0,8364
3,5713	–0,9570	1,4890	–0,8364

Сходимость в тысячных долях имеет место уже на 10-м шаге.

Это решение может быть получено и с помощью формул (2.28а).

Пример 2.2. Для иллюстрации алгоритма с помощью формул (2.28а) рассмотрим решение системы (только две итерации):

; . (2.31)

Преобразуем систему к виду (2.26) согласно (2.28а):

Þ (2.32)

Возьмем начальное приближение = (0; 0; 0) Т . Тогда для k = 0 очевидно, что значение = (0,5; 0,8; 1,5) Т . Подставим эти значения в (2.32), т. е. при k = 1 получим = (1,075; 1,3; 1,175) Т .

Ошибка e₂ = = max(0,575; 0,5; 0,325) = 0,575.

Блок-схема алгоритма нахождения решения СЛАУ по методу простых итераций согласно рабочим формулам (2.28а) представлена на рис. 2.4.

Особенностью блок-схемы является наличие следующих блоков:

– блок 13 – его назначение рассмотрено ниже;

– блок 21 – вывод результатов на экран;

– блок 22 – проверка (индикатор) сходимости.

Проведем анализ предложенной схемы на примере системы (2.31) (n = 3, w = 1, e = 0,001):

= ; .

Блок 1. Вводим исходные данные A, , w, e, n: n = 3, w = 1, e = 0,001.

Цикл I. Задаем начальные значения векторов x0_i и х_i (i = 1, 2, 3).

Блок 5. Обнуляем счетчик числа итераций.

Блок 6. Обнуляем счетчик текущей погрешности.

В цикле II выполняется изменение номеров строк матрицы А и вектора .

Цикл II: i = 1: s = b₁ = 2 (блок 8).

Переходим во вложенный цикл III, блок9 – счетчик номеров столбцов матрицы А: j = 1.

Блок 10: j = i, следовательно, возвращаемся к блоку 9 и увеличиваем j на единицу: j = 2.

В блоке 10 j ¹ i (2 ¹ 1) – выполняем переход к блоку 11.

Блок 11: s = 2 – (–1) × х0₂ = 2 – (–1) × 0 = 2, переходим к блоку 9, в котором j увеличиваем на единицу: j = 3.

В блоке 10 условие j ¹ i выполняется, поэтому переходим к блоку 11.

Блок 11: s = 2 – (–1) × х0₃ = 2 – (–1) × 0 = 2, после чего переходим к блоку 9, в котором j увеличиваем на единицу (j = 4). Значение j больше n (n = 3) – заканчиваем цикл и переходим к блоку 12.

Блок 16. Проверяем условие d > de: 0,5 > 0, следовательно, переходим к блоку 17, в котором присваиваем de = 0,5 и выполняем возврат по ссылке «А» к следующему шагу цикла II – к блоку7, в котором i увеличиваем на единицу.

Цикл II: i = 2: s = b₂ = 4 (блок 8).

Переходим во вложенный цикл III, блок9: j = 1.

Посредством блока 10 j ¹ i (1 ¹ 2) – выполняем переход к блоку 11.

Блок 11: s = 4 – 1 × 0 = 4, переходим к блоку 9, в котором j увеличиваем на единицу: j = 2.

В блоке 10 условие не выполняется, поэтому переходим к блоку 9, в котором j увеличиваем на единицу: j = 3. По аналогии переходим к блоку 11.

Блок 11: s = 4 – (–2) × 0 = 4, после чего заканчиваем цикл III и переходим к блоку 12.

Блок 14: d = | 1 – 0,8 | = 0,2.

Блок 16. Проверяем условие d > de: 0,2 T , it = 1; de = 0,5.

Посредством блока 22 по ссылке «D» переходим к блоку 6, de = 0.

Переходим к циклу II на блок 7 и выполняем рассмотренные вычисления с новыми начальными значениями х0_i (i = 1, 2, 3).

Блок 18. Увеличиваем число итераций it = it + 1 = 1 + 1 = 2.

В блоках 19 и 20 цикла IV заменяем начальные значения х0_i полученными х_i (i = 1, 2, 3).

Блок 21. Выполняем печать значений второй итерации: = (1,075; 1,3; 1,175) T , it = 2; de = 0,575 и т. д.

Метод Зейделя. Данный метод является модификацией метода простой итерации и для системы (2.26) выполняется по следующим формулам:

(2.33)

Его суть состоит в том, что при вычислении очередного приближения в системе (2.33) и в формуле (2.28а), если имеет место соотношение (2.28), вместо используются уже вычисленные ранее , т. е. (2. 28а) преобразуется к виду

, i = 1, …, n. (2.34)

Такое преобразование позволяет ускорить сходимость итераций почти в два раза. Оценка точности вычисления аналогична методу простой итерации. Схема алгоритма аналогична схеме метода простой итерации, если x0_j заменить на x_j и убрать строки x0_i = 1, x0_i = x_i.

Пример 2.3. Методом Зейделя решить систему линейных уравнений с точностью e = 0,0001, приведя ее к виду, удобному для итераций:

(2.35)

Система не удовлетворяет условиям (2.28), поэтому приведем ее к соответствующему виду:

(2.36)

Здесь , значит, метод Зейделя сходится.

По формулам (2.33)

k	х₁	х₂	х₃
0,19	0,97	–0,14
0,2207	1,0703	–0,1915
0,2354	1,0988	–0,2118
0,2424	1,1088	–0,2196
0,2454	1,1124	–0,2226
0,2467	1,1135	–0,2237
0,2472	1,1143	–0,2241
0,2474	1,1145	–0,2243
0,2475	1,1145	–0,2243

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

Для ускорения сходимости используется искусственный прием – так называемый метод релаксации. Суть его заключается в том, что полученное по методу итерации очередное значение x_i ( k ) пересчитывается по формуле

, (2.37)

где w принято изменять в пределах от 0 до 2 (0

Видео:Метод простой итерации Пример РешенияСкачать

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

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

Видео:3 Метод простой итерации Блок-схема Решение системы линейных уравнений СЛАУСкачать

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

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

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .

Рассмотрим систему A x = b .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.

Видео:Решение слау методом итераций. Метод простых итераций c++.Скачать

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 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 .

Видео:8 Метод простой итерации Ручной счет Решение системы линейных уравнений СЛАУСкачать

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

Метод Зейделя — метод является модификацией метода Якоби.

Суть: при вычислении очередного ( 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

Видео:Решение систем линейных уравнений, урок 5/5. Итерационные методыСкачать

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

Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

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 ) .