русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


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


 

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

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

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

, (2.26)

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

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

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

Для сходимости (2.26а) необходимо и достаточно, чтобы |li(G)| < 1, где li(G) – все собственные значения матрицы G. Сходимость будет также и в случае, если ||G|| < 1, так как |li(G)| < " ||G||, где " – любой.

Символ || ... || означает норму матрицы. При определении ее величины чаще всего останавливаются на проверке двух условий:

||G|| = или ||G|| = , (2.27)

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

. (2.28)

Если (2.27) или (2.28) выполняется, метод итерации сходится при любом начальном приближении . Чаще всего вектор берут или нулевым, или единичным, или берут сам вектор из (2.26).

Существует много подходов к преобразованию исходной системы (2.2) с матрицей А для обеспечения вида (2.26) или выполнения условий сходимости (2.27) и (2.28).

Например, (2.26) можно получить следующим образом.

Пусть А = В + С, det В ¹ 0; тогда (B + С)= Þ B= −C+ Þ Þ B–1B= − B–1C+ B–1, откуда= − B–1C+ B–1.

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



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

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

, aii ¹ 0.

Или

; Þ ; Þ ; Þ

Þ .

Подбирая параметр a, можно добиться, чтобы ||G|| = ||E + aA|| < 1.

Если имеет место преобладание (2.28), тогда преобразование к (2.26) можно осуществить, решая каждое i-е уравнение системы (2.1) относительно xi по следующим рекуррентным формулам:

(2.28а)

т. е. .

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

В качестве примера рассмотрим систему

(2.29)

Как видно, в уравнениях (1) и (2) нет диагонального преобладания, а в (3) есть, поэтому его оставляем неизменным.

Добьемся диагонального преобладания в уравнении (1). Умножим (1) на a, (2) на b, сложим оба уравнения и в полученном уравнении выберем a и b так, чтобы имело место диагональное преобладание:

(2a + 3b) х1 + (–1,8a + 2b) х2 +(0,4a – 1,1b)х3 = a .

Взяв a = b = 5, получим 25х1 + х2 – 3,5х3 = 5.

Для преобразования уравнения (2) с преобладанием (1) умножим на g, (2) умножим на d и из (2) вычтем (1). Получим

(3d – 2g) х1 + (2d + 1,8g) х2 +(–1,1d – 0,4g) х3 = −g .

Положив d = 2, g = 3, получим 0 х1 + 9,4 х2 – 3,4 х3 = −3. В результате получим систему

(2.30)

Такой прием можно применять для нахождения решения широкого класса матриц.

Далее каждое уравнение (2.30) разделим на диагональный элемент, получим

или

Взяв в качестве начального приближения вектор = (0,2; –0,32; 0)Т, будем решать эту систему по технологии (2.26а):

k = 0, 1, 2, ... .

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

.

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

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

,

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

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

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

£ 0,001.

Оценим сходимость по формуле (2.27). Здесь ||G|| = = max{0,56; 0,61; 0,35; 0,61} = 0,61 < 1; = 2,15. Значит, сходимость обеспечена.

В качестве начального приближения возьмем вектор свободных членов, т. е. = (2,15; –0,83; 1,16; 0,44)Т. Подставим значения вектора в (2.26а):

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

k х1 х2 х3 х4
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-м шаге.

Ответ: х1» 3,571; х2 » –0,957; х3 » 1,489; х4 » –0,836.

Это решение может быть получено и с помощью формул (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)Т.

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

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

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

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

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

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

 

Рис. 2.4

 

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

= ; .

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

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

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

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

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

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

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

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

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

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

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

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

Блок 12: s = s / a11 = 2 / 4 = 0,5.

Блок 13: w = 1; s = s + 0 = 0,5.

Блок 14: d = | xis | = | 1 – 0,5 | = 0,5.

Блок 15: xi = 0,5 (i = 1).

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

Цикл II: i = 2: s = b2 = 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.

Блок 12: s = s / a22 = 4 / 5 = 0,8.

Блок 13: w = 1; s = s + 0 = 0,8.

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

Блок 15: xi = 0,8 (i = 2).

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

Цикл II: i = 3: s = b3 = 6 (блок 8).

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

Посредством блока 10 выполняем переход к блоку 11.

Блок 11: s = 6 – 1 × 0 = 6, переходим к блоку 9: j = 2.

Посредством блока 10 выполняем переход к блоку 11.

Блок 11: s = 6 – 1 × 0 = 6. Заканчиваем цикл III и переходим к блоку 12.

Блок 12: s = s / a33 = 6 / 4 = 1,5.

Блок 13: s = 1,5.

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

Блок 15: xi = 1,5 (i = 3).

Согласно блоку 16 (с учетом ссылок «А» и «С») выходим из цикла II и переходим к блоку18.

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

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

Блок 21. Выполняем печать промежуточных значений текущей итерации, в данном случае: = (0,5; 0,8; 1,5)T, it = 1; de = 0,5.

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

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

После чего получим х1 = 1,075; х2 = 1,3; х3 = 1,175.

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

В блоках 19 и 20 цикла IV заменяем начальные значения х0i полученными х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)

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

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

(2.35)

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

(2.36)

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

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

k х1 х2 х3
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

Ответ: x1 = 0,248; x2 = 1,115; x3 = –0,224.

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

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

, (2.37)

где w принято изменять в пределах от 0 до 2 (0 < w £ 2) с каким-либо шагом (h = 0,1 или 0,2). Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Релаксация – постепенное ослабление какого-либо состояния тела после прекращения действия факторов, вызвавших это состояние (физ. техн.).

Пример 2.4. Рассмотрим результат пятой итерации с применением формулы релаксации. Возьмем w = 1,5:

Как видно, получен результат почти седьмой итерации.

 

 



<== предыдущая лекция | следующая лекция ==>
Прямые методы решения СЛАУ | Вычисление обратных матриц


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.01 сек.