Лекция Итерационные методы решения системы алгебраических линейных уравнений.
Условие сходимости итерационного процесса.Метод Якоби.Метод Зейделя
Метод простой итерации
Рассматривается система линейных алгебраических уравнений
Для применения итерационных методов система должна быть приведена к эквивалентному виду
Затем выбирается начальное приближение к решению системы уравненийи находится последовательность приближений к корню.
Для сходимости итерационного процесса
достаточно, чтобы было выполнено условие
(норма матрицы). Критерий окончания
итераций зависит от применяемого
итерационного метода.
Метод Якоби .
Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:
Из первого уравнения системы выразим неизвестное x 1 , из второго уравнения системы выразимx 2 , и т. д.
В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:
Компоненты вектора d вычисляются по формулам:
Расчетная формула метода простой итерации имеет вид:
или в покоординатной форме записи выглядит так:
Критерий окончания итераций в методе Якоби имеет вид:
Если
,
то можно применять более простой критерий
окончания итераций
Пример 1. Решение системы линейных уравнений методом Якоби.
Пусть дана система уравнений:
Требуется найти решение системы с
точностью
Приведем систему к виду удобному для итерации:
Выберем начальное приближение, например,
- вектор правой части.
Тогда первая итерация получается так:
Аналогично получаются следующие приближения к решению.
Найдем норму матрицы B.
Будем использовать норму
Так как сумма модулей элементов в каждой
строке равна 0.2, то
,
поэтому критерий окончания итераций в
этой задаче
Вычислим нормы разностей векторов:
Так как
заданная точность достигнута на четвертой
итерации.
Ответ: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1
Метод Зейделя .
Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1) -го приближения к неизвестномуx i приi >1 используют уже найденные(n+1)- е приближения к неизвестнымx 1 ,x 2 , ...,x i - 1 , а неn -ое приближение, как в методе Якоби.
Расчетная формула метода в покоординатной форме записи выглядит так:
Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.
Пример 2. Решение систем линейных уравнений методом Зейделя.
Рассмотрим параллельно решение 3-х систем уравнений:
Приведем системы к виду удобному для итераций:
Заметим, что условие сходимости
выполнено только для первой системы.
Вычислим 3 первых приближения к решению
в каждом случае.
1-ая система:
Точным решением будут значения: x 1 = 1.4, x 2 = 0.2 . Итерационный процесс сходится.
2-ая система:
Видно, что итерационный процесс расходится.
Точное решение x 1 = 1, x 2 = 0.2 .
3-я система:
Видно, что итерационный процесс зациклился.
Точное решение x 1 = 1, x 2 = 2 .
Пусть матрица системы уравнений A – симметричная и положительно определенная. Тогда при любом выборе начального приближения метод Зейделя сходится. Дополнительных условий на малость нормы некоторой матрицы здесь не накладывается.
Метод простой итерации .
Если A – симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:
x =x -τ (Ax - b), τ – итерационный параметр.
Расчетная формула метода простой итерации в этом случае имеет вид:
x (n+1 ) =x n - τ (Ax (n ) - b).
и параметр τ > 0 выбирают так, чтобы по
возможности сделать минимальной величину
Пусть λ min и λ max – минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра
В этом случае
принимает минимальное значение равное:
Пример 3. Решение систем линейных уравнений методом простой итерации. (вMathCAD)
Пусть дана система уравнений Ax = b
Для построения итерационного процесса найдем собственные числа матрицы A:
- используется встроенная функция для
нахождения собственных чисел.
Вычислим итерационный параметр и проверим условие сходимости
Условие сходимости выполнено.
Возьмем начальное приближение - вектор x0, зададим точность 0.001 и найдем начальные приближения по приведенной ниже программе:
|
| |
Точное решение
Замечание. Если в программе возвращать матрицу rez, то можно просмотреть все найденные итерации.
Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, их самоисправляемость и простота реализации на ПК. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.
Следует заметить, что условия и скорость сходимости итерационного процесса существенно зависят от свойств матрицы А системы и от выбора начальных приближений.
Для применения метода итераций исходную систему (2.1) или (2.2) необходимо привести к виду
после чего итерационный процесс выполняется по рекуррентным формулам
, k
= 0, 1, 2, ... . (2.26а
)
Матрица G и вектор получены в результате преобразования системы (2.1).
Для сходимости (2.26а ) необходимо и достаточно, чтобы |l i (G )| < 1, где l i (G ) – все собственные значения матрицы G . Сходимость будет также и в случае, если ||G || < 1, так как |l i (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 –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 || < 1.
Если имеет место преобладание (2.28), тогда преобразование к (2.26) можно осуществить, решая каждое i -е уравнение системы (2.1) относительно x i по следующим рекуррентным формулам:
(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)
Такой прием можно применять для нахождения решения широкого класса матриц.
или 
Взяв в качестве начального приближения вектор = (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) Т .
Ошибка e 2 = 
= 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 . Задаем начальные значения векторов x 0 i и х i (i = 1, 2, 3).
Блок 5. Обнуляем счетчик числа итераций.
Блок 6. Обнуляем счетчик текущей погрешности.
В цикле II выполняется изменение номеров строк матрицы А и вектора .
Цикл II: i = 1: s = b 1 = 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 = 2 – (–1) × 0 = 2, переходим к блоку 9, в котором j увеличиваем на единицу: j = 3.
В блоке 10 условие j ¹ i выполняется, поэтому переходим к блоку 11.
Блок 11: s = 2 – (–1) × х 0 3 = 2 – (–1) × 0 = 2, после чего переходим к блоку 9, в котором j увеличиваем на единицу (j = 4). Значение j больше n (n = 3) – заканчиваем цикл и переходим к блоку 12.
Блок 12: s = s / a 11 = 2 / 4 = 0,5.
Блок 13: w = 1; s = s + 0 = 0,5.
Блок 14: d = | x i – s | = | 1 – 0,5 | = 0,5.
Блок 15: x i = 0,5 (i = 1).
Блок 16. Проверяем условие d > de : 0,5 > 0, следовательно, переходим к блоку 17, в котором присваиваем de = 0,5 и выполняем возврат по ссылке «А » к следующему шагу цикла II – к блоку7, в котором i увеличиваем на единицу.
Цикл II: i = 2: s = b 2 = 4 (блок 8).
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 / a 22 = 4 / 5 = 0,8.
Блок 13: w = 1; s = s + 0 = 0,8.
Блок 14: d = | 1 – 0,8 | = 0,2.
Блок 15: x i = 0,8 (i = 2).
Блок 16. Проверяем условие d > de : 0,2 < 0,5; следовательно, возвращаемся по ссылке «А » к следующему шагу цикла II – к блоку7.
Цикл II: i = 3: s = b 3 = 6 (блок 8).
Переходим во вложенный цикл III, блок9: j = 1.
Блок 11: s = 6 – 1 × 0 = 6, переходим к блоку 9: j = 2.
Посредством блока 10 выполняем переход к блоку 11.
Блок 11: s = 6 – 1 × 0 = 6. Заканчиваем цикл III и переходим к блоку 12.
Блок 12: s = s / a 33 = 6 / 4 = 1,5.
Блок 13: s = 1,5.
Блок 14: d = | 1 – 1,5 | = 0,5.
Блок 15: x i = 1,5 (i = 3).
Согласно блоку 16 (с учетом ссылок «А » и «С ») выходим из цикла II и переходим к блоку18.
Блок 18. Увеличиваем число итераций it = it + 1 = 0 + 1 = 1.
В блоках 19 и 20 цикла IV заменяем начальные значения х 0 i полученными значениями х i (i = 1, 2, 3).
Блок 21. Выполняем печать промежуточных значений текущей итерации, в данном случае: = (0,5; 0,8; 1,5) T , it = 1; de = 0,5.
Переходим к циклу II на блок 7 и выполняем рассмотренные вычисления с новыми начальными значениями х 0 i (i = 1, 2, 3).
После чего получим х 1 = 1,075; х 2 = 1,3; х 3 = 1,175.
Здесь , значит, метод Зейделя сходится.
По формулам (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 |
Ответ: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.
Замечание . Если для одной и той же системы методы простой итерации и Зейделя сходятся, то метод Зейделя предпочтительнее. Однако на практике области сходимости этих методов могут быть различными, т. е. метод простой итерации сходится, а метод Зейделя расходится и наоборот. Для обоих методов, если ||G || близка к единице , скорость сходимости очень малая.
Для ускорения сходимости используется искусственный прием – так называемый метод релаксации . Суть его заключается в том, что полученное по методу итерации очередное значение x i ( k ) пересчитывается по формуле
где w принято изменять в пределах от 0 до 2 (0 < w £ 2) с каким-либо шагом (h = 0,1 или 0,2). Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.
Релаксация – постепенное ослабление какого-либо состояния тела после прекращения действия факторов, вызвавших это состояние (физ. техн.).
Пример 2.4 . Рассмотрим результат пятой итерации с применением формулы релаксации. Возьмем w = 1,5:
Как видно, получен результат почти седьмой итерации.
ВВЕДЕНИЕ
1.РЕШЕНИЕ СЛАУ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ
1.1 Описание метода решения
1.2 Исходные данные
1.3 Алгоритм
1.4 Программа на языке QBasic
1.5 Результат работы программы
1.6 Проверка результата работы программы
2. УТОЧНЕНИЕ КОРНЯ МЕТОДОМ КАСАТЕЛЬНЫХ
2.1 Описание метода решения
2.2 Исходные данные
2.3 Алгоритм
2.4 Программа на языке QBasic
2.5 Результат работы программы
2.6 Проверка результата работы программы
3.ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ ПО ПРАВИЛУ ПРЯМОУГОЛЬНИКА
3.1 Описание метода решения
3.2 Исходные данные
3.3 Алгоритм
3.4 Программа на языке QBasic
3.5 Проверка результата работы программы
4.1 Общие сведения о программе
4.1.1 Назначение и отличительные особенности
4.1.2 Ограничения WinRAR
4.1.3 Системные требования WinRAR
4.2 Интерфейс WinRAR
4.3 Режимы управления файлами и архивами
4.4 Использование контекстных меню
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Целью данной курсовой работы является разработка алгоритмов и программ для решения системы линейных алгебраических уравнений с помощью метода Гаусса; нелинейного уравнения с помощью метода хорд; для численного интегрирования по правилу трапеций.
Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.
Способы решения систем линейных алгебраических уравнений делятся на две группы:
· точные методы, представляющие собой конечные алгоритмы для вычисления корней системы (решение систем с помощью обратной матрицы, правило Крамера, метод Гаусса и др.),
· итерационные методы, позволяющие получить решение системы с заданной точностью путем сходящихся итерационных процессов (метод итерации, метод Зейделя и др.).
Вследствие неизбежных округлений результаты даже точных методов являются приближенными. При использовании итерационных методов, сверх того, добавляется погрешность метода.
Решение систем линейных алгебраических уравнений – одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности – нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.
Для того чтобы система линейных алгебраических уравнений имела решение, необходимо и достаточно, чтобы ранг основной матрицы был равен рангу расширенной матрицы. Если ранг основной матрицы равен рангу расширенной матрицы и равен числу неизвестных, то система имеет единственное решение. Если ранг основной матрицы равен рангу расширенной матрицы, но меньший числа неизвестных, то система имеет бесконечное число решений.
Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод известен в различных вариантах уже более 2000 лет. Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.
Строго говоря, описываемый выше метод правильно называть методом "Гаусса-Жордана" (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г.). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).
Под нелинейными уравнениями понимаются алгебраические и трансцендентные уравнения вида , где х - действительное число, а – нелинейная функция. Для решения этих уравнений применяется метод хорд – итерационный численный метод приближенного нахождения корней. Как известно, многие уравнения и системы уравнений не имеют аналитических решений. В первую очередь это относится к большинству трансцендентных уравнений. Доказано также, что нельзя построить формулу, по которой можно было бы решить произвольное алгебраическое уравнение степени выше четвертой. Кроме того, в некоторых случаях уравнение содержит коэффициенты, известные лишь приблизительно, и, следовательно, сама задача о точном определении корней уравнения теряет смысл. Для их решения используются итерационные методы с заданной степенью точности. Решить уравнение итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.
Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:
· отделение корней - отыскание приближенного значения корня или содержащего его отрезка;
· уточнение приближенных корней - доведение их до заданной степени точности.
Определенным интегралом функции f(x), взятом в интервале от a
до b
, называется предел, к которому стремится интегральная сумма при стремлении всех промежутков ∆x i к нулю. Согласно правилу трапеций, необходимо заменить график функции F(x) прямой, проходящей через две точки (х 0 ,у 0) и (х 0 +h,у 1), и вычислить значение элемента интегральной суммы как площадь трапеции: 
.
РЕШЕНИЕ СЛАУ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ
1.1 Описание метода постой итерации
Системы алгебраических уравнений (СЛАУ) имеют вид:
или, при записи в матричной форме:
В практике используют два типа методов численного решения СЛАУ – прямые и косвенные. При использовании прямых методов СЛАУ приводится к одной из специальных форм (диагональной, треугольной) позволяющих точно получить искомое решение (если таковое существует). Наиболее распространенным прямым методом решения СЛАУ является метод Гаусса. Итерационные методы служат для поиска приближенного решения СЛАУ с заданной точностью. Следует отметить, что итерационный процесс не всегда сходится к решению системы, а только тогда, когда последовательность получаемых при расчетах приближений стремиться к точному решению. При решении СЛАУ методом простой итерации ее преобразуют к виду, когда в левой части находится только одна из искомых переменных:
Задав некоторые исходные приближения xi, i=1,2,…,n , подставляют их в правую часть выражений и вычисляют новые значения x . Процесс повторяют до тех пор, пока максимальная из невязок, определяемых по выражению:
не станет меньше заданной точности ε. Если максимальная невязка при k -ой итерации окажется больше максимальной невязки при k-1 -ой итерации, то процесс аварийно завершают, т.к. итерационный процесс расходится. Для минимизации количества итераций новые значения x можно вычислять с использованием значением невязок на предыдущей итерации.
Тема 3. Решение систем линейных алгебраических уравнений итерационными методами.
Описанные выше прямые методы решения СЛАУ не очень эффективны при решении систем большой размерности (т.е. когдо значение n достаточно велико). Для решения СЛАУ в таких случаях больше подходят итерационные методы
Итерационные методы решения СЛАУ (их второе название - методы последовательного приближения к решению) не дают точного решения СЛАУ, а дают только приближение к решению, причем каждое следующее приближение получается из предыдущего и является более точным, чем предыдущее (при условии, что обеспечена сходимость итераций). Начальное (или, так называемое, нулевое) приближение выбирается вблизи предполагаемого решения или произвольно (в качестве его можно взять вектор правой части системы). Точное решение находится как предел таких приближений при стремлении их количества к бесконечности. Как правило, за конечное число шагов (т.е. итераций) этот предел не достигается. Поэтому, на практике, вводится понятие точности решения , а именно задается некоторое положительное и достаточно малое число e и процесс вычислений (итераций) проводят до тех пор, пока не будет выполнено соотношение .
Здесь - приближение к решению, полученное после итерации номер n , а - точное решение СЛАУ (которое заранее неизвестно). Число итераций n = n (e ) , необходимое для достижения заданной точности для конкретных методов можно получить из теоретических рассмотрений (т. е. для этого имеются расчетные формулы). Качество различных итерационных методов можно сравнить по необходимому числу итераций для достижения одной и той же точности.
Для исследования итерационных методов на сходимость необходимо уметь вычислять нормы матриц. Норма матрицы - это некая числовая величина, характеризующая величину элементов матрицы по абсолютной величине. В высшей математике имеется несколько различных видов норм матриц, которые, как правило, являются эквивалентными. В нашем курсе мы будем пользоваться только одной из них. А именно, под нормой матрицы мы будем понимать максимальную величину среди сумм абсолютных величин элементов отдельных строк матрицы . Для обозначения нормы матрицы - ее название заключается в две пары вертикальных черточек. Так, для матрицы A под ее нормой будем понимать величину
. (3.1)
Так, к примеру, норма матрицы А из примера 1 находится следующим образом:
Наиболее широкое применение для решения СЛАУ получили три итерационных метода
Метод простой итерации
Метод Якоби
Метод Гуасса-Зейделя.
Метод простой итерации предполагает переход от записи СЛАУ в исходном виде (2.1) к записи ее в виде
(3.2)
или, что тоже, в матричном виде,
x = С × x + D , (3.3)
C - матрица коэффициентов преобразованной системы размерности n ´ n
x - вектор неизвестных, состоящий из n компонент
D - вектор правых частей преобразованной системы, состоящий из n компонент.
Система в виде (3.2) может быть представлена в сокращенном виде
Исходя из этого представления формула простой итерации будет иметь вид
где m - номер итерации, а - значение x j на m -ом шаге итерации. Тогда, если процесс итераций сходится, с увеличением количества итераций будет наблюдаться
Доказано, что процесс итераций сходится, если норма матрицы D будет меньше единиц ы .
Если за начальное (нулевое) приближение взять вектор свободных членов, т.е. x (0) = D , то величина погрешности имеет вид
(3.5)
здесь под x * понимается точное решение системы. Следовательно,
если 
, то по заданной точности
e
можно заранее расчитать необходимое количество итераций
. А именно, из соотношения
после небольших преобразований получим
. (3.6)
При выполнении такого количества итераций гарантировано будет обеспечена заданная точность нахождения решения системы. Эта теоретическая оценка необходимого количества шагов итерации несколько завышена. На практике необходимая точность может быть достигнута за меньшее количество итераций.
Поиск решений заданной СЛАУ методом простой итерации удобно производить с занесением полученных результатов в таблицу следующего вида:
| x 1 | x 2 | x n |
||
Следует особо отметить, что в решении СЛАУ этим методом наиболее сложным и трудоемким является выполнение преобразования системы из вида (2.1) к виду (3.2). Эти преобразования должны быть эквивалентными, т.е. не меняющими решения исходной системы, и обеспечивающие величину нормы матрицы C (после выполнения их) меньшей единицы. Единого рецепта для выполнения таких преобразований не существует. Здесь в каждом конкретном случае необходимо проявлять творчество. Рассмотрим примеры , в которых будут приведены некоторые способы преобразования системы к необходимому виду.
Пример 1. Найдем решение системы линейных алгебраических уравнений методом простой итерации (с точностью e = 0.001)
Эта система приводится к необходимому виду простейшим способом. Перенесем все слагаемые из левой части в правую, а затем к обоим частям каждого уравнения прибавим по x i (i =1, 2, 3, 4). Получим преобразованную систему следующего вида
.
Матрица C и вектор D в этом случае будут следующими
C
=
,
D
=
.
Вычислим норму матрицы C . Получим
Так как норма оказалась меньшей единицы - сходимость метода простой итерации обеспечена. В качестве начального (нулевого) приближения примем компоненты вектора D . Получим
, 
, 
, 
.
По формуле (3.6) вычислим необходимое число шагов итерации. Определим сначала норму вектора D . Получим
.
Следовательно, для достижения заданной точности необходимо выполнить не менее 17 итераций. Выполним первую итерацию. Получим
Выполнив все арифметические операции, получим
.
Продолжая аналогично, выполним дальнейшие шаги итераций. Результаты их сведем в следующую таблицу (D - наибольшая величина изменения компонент решения между текущим и предыдущим шагами)
| M | |||||
Так как уже после десятого шага разность между значениями на двух последних итерациях стала меньше заданной точности - процесс итераций прекратим. В качестве найденного решения примем значения, полученные на последнем шаге.
Пример 2.
Поступим сначала аналогично предыдущему примеру. Получим
Матрица C такой системы будет
C
=
.
Вычислим ее норму. Получим
Очевидно, что итерационный процесс для такой матрицы сходящимся не будет. Необходимо найти иной способ преобразования заданной системы уравнений.
Переставим в исходной системе уравнений отдельные ее уравнения так, чтобы третья строка стала первой, первая - второй, вторая - третьей. Тогда, преобразуя ее тем же способом, получим
Матрица C такой системы будет
C
=
.
Вычислим ее норму. Получим
Так как норма матрицы C оказалась меньшей единицы, преобразованная таким образом система пригодна для решения методом простой итерации.
Пример 3. Преобразуем систему уравнений
к виду, который позволил бы использовать при ее решении метод простой итерации.
Поступим сначала аналогично примеру 1. Получим
Матрица C такой системы будет
C
=
.
Вычислим ее норму. Получим
Очевидно, что итерационный процесс для такой матрицы сходящимся не будет.
Для преобразования исходной матрицы к виду, удобному для применения метода простой итерации поступим следующим образом. Сначала образуем “промежуточную” систему уравнений, в которой
- первое уравнение является суммой первого и второго уравнений исходной системы
- второе уравнение - суммой удвоенного третьего уравнения со вторым за вычетом первого
- третье уравнение - разность третьего и второго уравнений исходной системы.
В результате получим эквивалентную исходной “промежуточную” систему уравнений
Из нее несложно получить еще одну систему “промежуточную” систему
,
а из нее преобразованную
.
Матрица C такой системы будет
C
=
.
Вычислим ее норму. Получим
Итерационный процесс для такой матрицы будет сходящимся.
Метод Якоби предполагает, что все диагональные элементы матрицы A исходной системы (2.2) не равны нулю. Тогда исходную систему можно переписать в виде
(3.7)
Из такой записи системы образована итерационная формула метода Якоби
Условием сходимости итерационного процесса метода Якоби является так называемое условие доминирования диагонали в исходной системе (вида (2,1)). Аналитически это условие записывается в виде
. (3.9)
Следует отметить, что если в заданной системе уравнений условие сходимости метода Якоби (т.е. условие доминирования диагонали) не выполняется, во многих случаях можно путем эквивалентных преобразований исходной СЛАУ привести ее решение к решению эквивалентной СЛАУ, в которой это условие выполняется.
Пример 4. Преобразуем систему уравнений
к виду, который позволил бы использовать при ее решении метод Якоби.
Эту систему мы уже рассматривали в примере 3, поэтому перейдем от нее к полученной там “промежуточной” системе уравнений. Легко установить, что у нее условие доминирования диагонали выполняется, поэтому преобразуем ее к виду, необходимому для применения метода Якоби. Получим
Из нее получаем формулу для выполнения вычислений по методу Якоби для заданной СЛАУ
Взяв за начальное, т.е. нулевое, приближение вектор свободных членов выполним все необходимые вычисления. Результаты сведем в таблицу
| m | D |
||||
Довольно высокая точность полученного решения достигнута за шесть итераций.
Метод Гаусса-Зейделя является усовершенствованием метода Якоби и также предполагает, что все диагональные элементы матрицы A исходной системы (2.2) не равны нулю. Тогда исходную систему можно переписать в виде аналогичном методу Якоби, но несколько отличном от него
Здесь важно помнить, что если в знаке суммирования верхний индекс меньше нижнего, то никакого суммирования не производится.
Идея метода Гаусса-Зейделя заключается в том, что авторы метода усмотрели возможность ускорить процесс вычислений по отношению к методу Якоби за счет того, что в процессе очередной итерации найдя новое значение x 1 можно сразу же использовать это новое значение в этой же итерации для вычисления остальных переменных. Аналогично этому, дальше, найдя новое значение x 2 можно его также сразу использовать в этой же итерации и т.д.
Исходя из этого, формула итераций для метода Гаусса-Зейделя имеет следующий вид
Достаточным у словием сходимости итерационного процесса метода Гаусса-Зейделя является все то же условие доминирования диагонали (3.9). Скорость сходимости этого метода несколько выше, чем в метода Якоби.
Пример 5. Решим методом Гаусса-Зейделя систему уравнений
Эту систему мы уже рассматривали в примерах 3 и 4, поэтому сразу перейдем от нее к преобразованой системе уравнений (см. пример 4), в которой условие доминирования диагонали выполняется. Из нее получаем формулу для выполнения вычислений по методу Гаусса-Зейделя
Взяв за начальное (т.е. нулевое) приближение вектор свободных членов, выполним все необходимые вычисления. Результаты сведем в таблицу
| m | ||||
Довольно высокая точность полученного решения достигнута за пять итераций.
