Метод обратной итерации пример. Метод простой итерации для решения систем линейных уравнений (слау)
В этом разделе мы рассмотрим стационарный итерационный процесс, когда матрица и итерационный параметрне зависят от индекса, и докажем следующую теорему о достаточных условиях его сходимости.
Теорема Самарского
Пусть - самосопряженная положительно определенная матрица:
,
,
- положительно определенная матрица, - положительное число:
,
.
Тогда при любом выборе нулевого приближения итерационный процесс, который определяется рекуррентной формулой , сходится к решению исходной системы.
Прежде, чем переходить к доказательству
теоремы, обсудим более подробно главное
ее требование – положительную
определенность матрицы
.
Это требование можно переписать в виде:
,
,
.
т. е. оно, в частности, предполагает, что матрица является положительно определенной. Кроме того, неравенство определяет интервал, в котором может изменяться параметр:
.
После этих замечаний перейдем к доказательству теоремы. Выразим из соотношения через:
и подставим в рекуррентную формулу для итерационной последовательности. В результате получим:
.
Отличие итерационной формулы от заключается в том, что она является однородной.
Матрица
- положительно определенная. Следовательно
она невырожденная и имеет обратную
.
С ее помощью рекуррентное соотношение
можно разрешить относительно
:
,
так что
.
Умножая обе части равенства слева на матрицу , получим еще одно рекуррентное соотношение
.
Рассмотрим последовательность положительных функционалов:
.
Составим
аналогичное выражение для
и преобразуем его с помощью рекуррентных
формул и:
Из самосопряженности матрицы и формулы следует
В результате формула принимает вид:
Таким образом, последовательность
функционалов
с учетом условия
образует монотонно невозрастающую
последовательность, ограниченную снизу
нулем
.
,
где
- строго положительная константа. В
результате, согласно и будем иметь
Из этого неравенства
и сходимости последовательности
функционалов
следует, что
при
.
В свою очередь
,
так что
Теорема доказана.
Метод простой итерации.
Такое название получил метод, при котором
в качестве матрицы
выбирается единичная матрица:
,
а итерационный параметрпредполагается независящим от номера
итерации.
Иными словами, метод простой итерации
– это явный стационарный метод, когда
очередная итерация
вычисляется по рекуррентной формуле
Будем считать, что матрица
удовлетворяет условию теоремы Самарского,
,
тогда формула, определяющая границу
интервала сходимости по итерационному
параметру,
принимает вид
.
Пусть
- ортонормированный базис собственных
векторов оператора, соответствующего
матрице.
В силу положительной определенности
все его собственные значения положительны.
Будем считать их занумерованными в
порядке убывания:
Разложим вектор
по базису собственных векторов
В результате из формулы следует, что метод простой итерации сходится при любом , принадлежащем интервалу
.
Дальнейшее исследование метода простой итерации построим на конкретном анализе рекуррентной формулы. Введем матрицу оператора перехода
,
и перепишем формулу в виде
.
При этом погрешность
будет удовлетворять аналогичному
рекуррентному соотношению, только
однородному
.
Докажем две леммы, которые позволяют более полно исследовать условия сходимости метода простой итерации.
Лемма 1
Пусть оператор, который порождает матрица , имеет собственный вектор с собственным значением , тогда оператор перехода, который порождается матрицей, также имеет собственный вектор , но с собственным значением
.
Доказательство элементарно. Оно проводится прямой проверкой
При самосопряженной матрице
матрицатакже является самосопряженной.
Следовательно, ее норма определяется
наибольшим по модулю собственным
значением
:
.
Лемма 2
Для того, чтобы метод простой итерации сходился к решению системы при любом выборе начального приближения, необходимо и достаточно, чтобы все собственные значения оператора перехода были по модулю меньше единицы:
,
Достаточность
. Условие означает,
что норма матрицы,
согласно, будет меньше единицы:
.
В результате получаем
При
.
Необходимость . Допустим, что среди собственных значенийнашлось хотя бы одно, которое не удовлетворяет условию леммы, т. е.
.
Выберем
нулевой член итерационной последовательности
в виде
,
гдерешение системы, тогда нулевой член
последовательности погрешностей
совпадет с собственным векторомоператора перехода:
.
В результате рекуррентная формула для
следующих членов последовательности
погрешностей примет вид:
,
.
т. е.
.
Необходимость выполнения неравенства
для всех собственных значенийдля сходимости метода простой итерации
доказана.
Лемма 2 определяет программу дальнейшего
исследования сходимости метода простой
итерации: нужно установить диапазон
изменения параметра
при котором все собственные значения
удовлетворяют неравенству. Это легко
сделать. На рис. 1 приведены графики
убывающих линейных функций
. Все они выходят из одной точки
,
и идут вниз из-за отрицательных
коэффициентов при,
причем быстрее всех убывает функция
.
Когда она принимает значение
,
условие для нее перестает выполняться:
,
при
.
Найденное значение является границей интервала сходимости метода простой итерации
.
Это неравенство нам уже известно. Оно было получено ранее из теоремы Самарского как достаточное условие сходимости. Дополнительный анализ на основе леммы 2 позволяет уточнить результат. Теперь мы установили, что принадлежность итерационного параметра интервалу является необходимым и достаточным условием сходимости метода простой итерации.
Перейдем к исследованию скорости сходимости метода. Оценка погрешности показывает, что она убывает по закону геометрической прогрессии со знаменателем
.
Рассмотрим
рис. 2, который поможет нам провести
анализ этой формулы. Он аналогичен
рис.1, только на нем приведены графики
не функций
,
а их модулей. При малыхвсе собственные значения
положительны, причем наибольшим из
них является
,
которое убывает с ростомс наименьшей скоростью. Однако с переходом
через точку
собственное значение
,
меняя знак, становится отрицательным.
В результате теперь его модуль с
увеличениемне убывает, а растет и при
приближается к предельному значению –
к единице.
Найдем на отрезке
точку,
в которой убывающая функция
сравнивается с возрастающей функцией
.
Она определяется уравнением
которое дает
.
В результате получаем:
Свое наименьшее
значение норма матрицы
достигает при
:
.
Формула
показывает, что для плохо обусловленной
матрицы даже при оптимальном выборе
итерационного параметра
норма матрицыблизка к единице, так что сходимость
метода простой итерации в этом случае
оказывается медленной.
В заключение заметим, что формула, определяющая границу интервала сходимости , и формула для оптимального значения итерационного параметрапредставляют прежде всего теоретический интерес. Обычно при решении СЛАУ наибольшее и наименьшее характеристические числа матрицынеизвестны, так что подсчитать величиныизаранее невозможно. В результате итерационный параметрнередко приходится подбирать прямо в процессе вычислений методом проб и ошибок.
Задача 2.
Рассмотреть систему двух уравнений с двумя неизвестными
и построить для нее приближенное решение с помощью метода простой итерации.
Выпишем сразу решение системы
,
,
чтобы потом иметь возможность сравнивать его с членами итерационной последовательности.
Перейдем к решению системы методом простой итерации. Матрица системы имеет вид
.
Она самосопряженная и положительно определенная, поскольку
Составим характеристическое уравнение для матрицы и найдем его корни:
,
,
С их помощью можно определить границу интервала сходимости и оптимальное значение итерационного параметра:
,
.
Для построения итерационной
последовательности выберем какое-нибудь
значение итерационного параметра на
интервале сходимости, например,
.
В этом случае рекуррентная формула для
членов итерационной последовательности
принимает вид:
,
где
Возьмем
простейшее начальное приближение
и выпишем несколько первых членов
итерационной последовательности,
подсчитывая для каждого из них невязку
. В результате получим:
,
,
,
,
,
,
,
,
,
,
,
.
Норма невязок, хотя и медленно, но убывает, что говорит о сходимости процесса. Это же видно из сравнения членов итерационной последовательности с решением системы. Медленная сходимость связана с плохой обусловленностью матрицы:
.
Лекция Итерационные методы решения системы алгебраических линейных уравнений.
Условие сходимости итерационного процесса.Метод Якоби.Метод Зейделя
Метод простой итерации
Рассматривается система линейных алгебраических уравнений
Для применения итерационных методов система должна быть приведена к эквивалентному виду
Затем выбирается начальное приближение к решению системы уравненийи находится последовательность приближений к корню.
Для сходимости итерационного процесса
достаточно, чтобы было выполнено условие
(норма матрицы). Критерий окончания
итераций зависит от применяемого
итерационного метода.
Метод Якоби .
Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:
Из первого уравнения системы выразим неизвестное 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, то можно просмотреть все найденные итерации.
1. Пусть известен отрезок , который содержит один корень уравнения f(x) = 0. Функция f является непрерывно дифференцируемой функцией на этом отрезке (f(x)ÎC 1 ). При выполнении этих условий можно применять метод простой итерации.
2. По функции f(x) строится функция j(x), удовлетворяющая трём условиям: она должна быть непрерывно дифференцируемой (j(x)ÎC 1 ), такая, что уравнение x = j(x) равносильно уравнению f(x)=0; должна также переводить отрезок в себя .
Будем говорить, что функция j(x) переводит отрезок [ a, b] в себя, если для любого x Î [ a, b], y = j(x) также принадлежит [ a, b] (y Î [ a, b]).
На функцию j(x) накладывается третье условие:
Формула метода: x n +1 = j(x n).
3. При выполнении этих трех условий для любого начального приближения x 0 Î последовательность итераций x n +1 = j(x n) сходится к корню уравнения: x = j(x) на отрезке ().
Как правило, в качестве x 0 выбирается один из концов .
,
где e – заданная точность
Число x n +1 при выполнении условия остановки итерационного процесса является приближенным значением корня уравнения f(x) = 0 на отрезке , найденным методом простой итерации с точностью e.
Построить алгоритм для уточнения корня уравнения: x 3 + 5x – 1 = 0 на отрезке методом простой итерации с точностью e.
1. Функция f(x) = x 3 +5x-1 является непрерывно дифференцируемой на отрезке , содержащем один корень уравнения.
2. Наибольшую трудность в методе простой итерации представляет построение функции j(x), удовлетворяющей всем условиям:
Рассмотрим: .
Уравнение x = j 1 (x) эквивалентно уравнению f(x) = 0, но функция j 1 (x) не является непрерывно дифференцируемой на отрезке .
Рис. 2.4. График функции j 2 (x)
С другой стороны, , следовательно, . Отсюда: – непрерывно дифференцируемая функция. Отметим, что уравнение:x = j 2 (x) эквивалентно уравнению f(x) = 0. Из графика (рис. 2.4) видно, что функция j 2 (x) переводит отрезок в себя.
Условие, что функция j(x) переводит отрезок в себя, можно переформулировать следующим образом: пусть – область определения функции j(x), а – область изменения j(x).
Если отрезок принадлежит отрезку , то функция j(x) переводит отрезок в себя.
, .
Все условия для функции j(x) выполнены.
Формула итерационного процесса: x n +1 = j 2 (x n).
3. Начальное приближение: x 0 = 0.
4. Условие остановки итерационного процесса:
Рис. 2.5. Геометрический смысл метода простой итерации
.
При выполнении этого условия x n +1 – приближенное значение корня на отрезке , найденное методом простой итерации с точностью e . На рис. 2.5. иллюстрируется применение метода простой итерации.
Теорема о сходимости и оценка погрешности
Пусть отрезок содержит один корень уравнения x = j(x), функция j(x) является непрерывно дифференцируемой на отрезке , переводит отрезок в себя, и выполнено условие :
.
Тогда для любого начального приближения x 0 Î последовательность сходится к корню уравнения y = j(x) на отрезке и справедлива оценка погрешности :
.
Устойчивость метода простой итерации. При выполнении условий теоремы о сходимости алгоритм метода простой итерации является устойчивым.
Сложность метода простой итерации . Объем памяти ЭВМ, необходимый для реализации метода простой итерации, незначителен. На каждом шаге нужно хранить x n , x n +1 , q и e.
Оценим число арифметических действий, необходимых для реализации метода простой итерации. Запишем оценку для числа n 0 = n 0 (e) такого что, для всех n ³ n 0 выполняется неравенство:
Из этой оценки вытекает, что чем ближе q к единице, тем медленнее сходится метод.
Замечание. Не существует общего правила построения j(x) по f(x) так, чтобы выполнялись все условия теоремы о сходимости. Часто используется следующий подход: в качестве функции j выбирается функция j(x) = x + k× f(x), где k – константа.
При программировании метода простой итерации для остановки итерационного процесса часто требуют одновременного выполнения двух условий:
и .
Все остальные итерационные методы, которые мы будем рассматривать, являются частными случаями метода простой итерации. Например, при метод Ньютона является частным случаем метода простой итерации.
Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, их самоисправляемость и простота реализации на ПК. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.
Следует заметить, что условия и скорость сходимости итерационного процесса существенно зависят от свойств матрицы А системы и от выбора начальных приближений.
Для применения метода итераций исходную систему (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:
Как видно, получен результат почти седьмой итерации.