Итерационные методы решения линейных систем

ЛЕКЦИЯ 10.2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ В этой части мы изучим итерационные методы. В них строится последовательность приближённых решений (итераций), сходящаяся к точному решению. При достижении заданной точности вычисление прекращается, и последняя итерация выдаётся за решение задачи. При этом надо так выбрать начальную итерацию, чтобы последовательность сходилась к точному решению. Поэтому для итерационных методов, кроме собственно расчётной формулы метода, нужны: • множество начальных итераций, для которых метод сходится (это мы называем областью сходимости); • оценки погрешности решения на каждом шаге. 1. Метод простой итерации Постановка задачи прежняя: надо решить систему 𝐴𝑥 = 𝑏, 𝑎12 ⋯ 𝑎22 ⋯ ⋱ ⋮ 𝑎𝑛2 ⋯ 𝑎11 𝑎21 𝐴=� ⋮ 𝑎𝑛1 𝑎1𝑛 𝑎2𝑛 ⋮ �, 𝑎𝑛𝑛 (1) 𝑥1 𝑏1 𝑥2 𝑏 𝑥 = � ⋮ � , 𝑏 = � 2 �. ⋮ 𝑥𝑛 𝑏𝑛 Пусть система (1) приведена к эквивалентному виду 𝑏11 𝐵=� ⋮ 𝑏𝑛1 𝑥 = 𝐵𝑥 + 𝑐, ⋯ ⋱ ⋯ 𝑐1 𝑏1𝑛 ⋮ �, 𝑐 = � ⋮ �. 𝑐𝑛 𝑏𝑛𝑛 (2) Преобразование системы к виду (2) само по себе является нетривиальной задачей и требует индивидуального подхода. Ведь от матрицы 𝐵 зависит сходимость итерационной последовательности. Проще всего взять 𝐵 = 𝐸 − 𝐴, 𝑐 = 𝑏. В этом случае метод простой ите-1- рации называется методом последовательных приближений. В следующем пункте описан другой несложный способ перехода к (2). Итак, требуется построить итерационную последовательность для решения системы (2). Пусть взято некоторое начальное приближение 𝑥 (0) . Подставив его в правую часть (2), получим некоторый вектор, который примем за следующую итерацию: 𝑥 этому же правилу вычислим вторую итерацию: 𝑥 приближение вычисляется по формуле 𝑥 (𝑘) = 𝐵𝑥 (2) (𝑘−1) = 𝐵𝑥 (1) (1) = 𝐵𝑥 (0) + 𝑐. По + 𝑐, и так далее. Произвольное + 𝑐, (3) 𝑘 = 1, 2, … . Это и есть расчётная формула метода простой итерации. В развёрнутом виде она выглядит так: (𝑘) (𝑘−1) (𝑘−1) (𝑘−1) + 𝑏12 𝑥2 + ⋯ + 𝑏1𝑛 𝑥𝑛 + 𝑐1 , ⎧ 𝑥1 = 𝑏11 𝑥1 ⎪ (𝑘) (𝑘−1) (𝑘−1) (𝑘−1) 𝑥2 = 𝑏21 𝑥1 + 𝑏22 𝑥2 + ⋯ + 𝑏2𝑛 𝑥𝑛 + 𝑐2 , ⋮ ⋮ ⋮ ⎨ ⎪ (𝑘) (𝑘−1) (𝑘−1) (𝑘−1) + 𝑏𝑛2 𝑥2 + ⋯ + 𝑏𝑛𝑛 𝑥𝑛 + 𝑐𝑛 . ⎩𝑥𝑛 = 𝑏𝑛1 𝑥1 Теперь рассмотрим проблему сходимости и оценки погрешности. Следующая теорема даёт достаточное условие сходимости и априорную оценку погрешности. Теорема 1. Пусть ‖𝐵‖ < 1. Тогда итерационная последовательность (3) сходится к точному решению 𝑥 системы (2) при любой начальной итерации 𝑥 грешности Δ𝑥 𝑘 = 0, 1, … . (𝑘) =�𝑥−𝑥 (𝑘) � ≤ ‖𝐵‖𝑘 ⋅ �𝑥 − 𝑥 Доказательство. Пусть 𝑥 ― точное решение (2), 𝑥 (3) из (2): 𝑥−𝑥 (𝑘) (𝑘) (0) (0) и имеет место оценка по- � = ‖𝐵‖𝑘 Δ𝑥 (0) , ― k-е приближение к нему. Вычтем = 𝐵 �𝑥 − 𝑥 (𝑘−1) � Перейдём в этом равенстве к нормам и применим свойство матричной нормы: �𝑥 − 𝑥 (𝑘) � = �𝐵 �𝑥 − 𝑥 (𝑘−1) �� ≤ ‖𝐵‖ ⋅ �𝑥 − 𝑥 (𝑘−1) �. Равенство (5) справедливо для любого 𝑘, поэтому в нём можно заменить 𝑘 на 𝑘 − 1: 𝑥−𝑥 (𝑘−1) = 𝐵 �𝑥 − 𝑥 (𝑘−2) � ⇒ �𝑥 − 𝑥 -2- (4) (𝑘−1) � = �𝐵 �𝑥 − 𝑥 (𝑘−2) �� ≤ (5) (6) ≤ ‖𝐵‖ ⋅ �𝑥 − 𝑥 (𝑘−2) Подставляя эту оценку в (6), получаем �𝑥 − 𝑥 (𝑘) �. � ≤ ‖𝐵‖2 ⋅ �𝑥 − 𝑥 (𝑘−2) �. Применяя каждый раз таким же образом (5), в конце концов, приходим к доказываемой оценке. А так как по условию ‖𝐵‖ < 1, то очевидно, что lim � 𝑥 − 𝑥 𝑘→∞ чает сходимость итерационной последовательности. ∎ (𝑘) � = 0, а это и озна- Замечание. Оценка (4) показывает, что на каждом шаге погрешность уменьшается в ‖𝐵‖ раз. В таком случае говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем 𝑞 = ‖𝐵‖ < 1. Такая скорость называется линейной. Очевидно, что чем меньше ‖𝐵‖, тем выше скорость сходимости. Оценка (4) непригодна для практического применения, поскольку она использует неизвестный вектор 𝑥. Для получения критерия остановки процесса требуется другая, апостериорная, оценка. Теорема 2. Пусть ‖𝐵‖ < 1. Тогда итерационная последовательность (3) сходится к точному решению 𝑥 системы (2) при любой начальной итерации 𝑥 грешности Δ𝑥 𝑘 = 1, 2, … . (𝑘) = �𝑥−𝑥 (𝑘) �≤ (0) и имеет место оценка по- ‖𝐵‖ (𝑘−1) (𝑘) ⋅ �𝑥 − 𝑥 �, 1 − ‖𝐵‖ (7) Доказательство. Понятно, что здесь достаточно доказать оценку (7). Для этого преобразуем (5): 𝑥−𝑥 (𝑘) = 𝐵 �𝑥 − 𝑥 (𝑘−1) = 𝐵 �𝑥 − 𝑥 � = 𝐵 �𝑥 − 𝑥 (𝑘) Теперь переходим к нормам: �𝑥 − 𝑥 ≤ �𝐵 �𝑥 − 𝑥 (𝑘) (𝑘) � + 𝐵 �𝑥 � = �𝐵 �𝑥 − 𝑥 �� + �𝐵 �𝑥 (𝑘) (𝑘) Из последнего неравенства получаем (𝑘) (𝑘−1) −𝑥 -3- +𝑥 −𝑥 � + 𝐵 �𝑥 −𝑥 +‖𝐵‖ ⋅ �𝑥 (𝑘) (𝑘) (𝑘) (𝑘−1) (𝑘) −𝑥 (𝑘−1) �. −𝑥 (𝑘−1) �� ≤ �� ≤ ‖𝐵‖ ⋅ �𝑥 − 𝑥 (𝑘−1) �. �= (𝑘) �+ откуда и следует (7). ∎ �𝑥 − 𝑥 (𝑘) � (1 − ‖𝐵‖) ≤ ‖𝐵‖ ⋅ �𝑥 (𝑘) −𝑥 (𝑘−1) �, Полученная оценка позволяет сформулировать условие остановки итерационного процесса. Если требуется найти решение с заданной точностью ε, то 𝑥 лять до достижения неравенства (𝑘) следует вычис- ‖𝐵‖ (𝑘) (𝑘−1) ⋅ �𝑥 − 𝑥 � ≤ ε, 1 − ‖𝐵‖ или �𝑥 где (𝑘) −𝑥 ε1 = (𝑘−1) � ≤ ε1 , 1 − ‖𝐵‖ ε. ‖𝐵‖ В заключение этого пункта внесём ясность в вопрос о том, какую норму надо использовать при применении теорем 1-3. Нормы ‖⋅‖α и ‖⋅‖β называются эквивалентными, если существуют положительные постоянные γαβ , γβα , для которых при 𝑥 ≠ 0 ‖𝑥‖β ‖𝑥‖α ≤ γαβ , ≤ γβα . ‖𝑥‖α ‖𝑥‖β Пусть условие теоремы 1 выполнено для подчинённой векторной норме ‖⋅‖α матричной нормы. Тогда для эквивалентной ‖⋅‖α нормы ‖⋅‖β имеем �𝑥−𝑥 (𝑘) � ≤ γαβ � 𝑥 − 𝑥 β (𝑘) � ≤ γαβ ‖𝐵‖𝑛α ⋅ � 𝑥 − 𝑥 α ≤ γαβ γβα ‖𝐵‖𝑛α ⋅ � 𝑥 − 𝑥 (0) � . (0) � ≤ α β Таким образом, итерационная последовательность сходится к точному решению и по норме ‖⋅‖β . В силу неравенств 1 ‖𝐴‖∞ ≤ ‖𝐴‖1 ≤ 𝑛‖𝐴‖∞ 𝑛 лекции 10.1 все введённые в п. 2 лекции 10.1 нормы эквивалентны, поэтому при выполнении условия ‖𝐵‖ < 1 по любой из них гарантирована сходимость последовательности (3) по любой другой норме и справедливы оценки (4), (7). -4- 2. Метод Якоби Осуществим переход от системы (1) к (2) следующим простым способом. Предполагая, что 𝑎𝑖𝑖 ≠ 0, выразим в i-м уравнении (1) 𝑥𝑖 через остальные переменные: 𝑥𝑖 = − 𝑎𝑖1 𝑎𝑖,𝑖−1 𝑎𝑖,𝑖+1 𝑎𝑖𝑛 𝑏𝑖 𝑥1 − ⋯ − 𝑥𝑖−1 − 𝑥𝑖+1 − ⋯ − 𝑥𝑛 + . 𝑎𝑖𝑖 𝑎𝑖𝑖 𝑎𝑖𝑖 𝑎𝑖𝑖 𝑎𝑖𝑖 В результате приходим к системе 𝑥1 = 𝑏12 𝑥2 + 𝑏13 𝑥3 + ⋯ + 𝑏1𝑛 𝑥𝑛 + 𝑐1 , ⎧𝑥 = 𝑏 𝑥 + 𝑏23 𝑥3 + ⋯ + 𝑏2𝑛 𝑥𝑛 + 𝑐2 , 21 1 ⎪ 2 ⋮ ⋮ ⎨ 𝑥𝑖 = 𝑏𝑖1 𝑥1 + ⋯ + 𝑏𝑖,𝑖−1 𝑥𝑖−1 + 𝑏𝑖,𝑖+1 𝑥𝑖+1 + ⋯ + 𝑏𝑖𝑛 𝑥𝑛 + 𝑐𝑖 , ⋮ ⋮ ⎪ + 𝑐𝑛 , ⎩𝑥𝑛 = 𝑏𝑛1 𝑥1 + ⋯ + 𝑏𝑛,𝑛−1 𝑥𝑛−1 где 𝑏𝑖𝑗 = − 𝑖, 𝑗 = 1, … , 𝑛, 𝑖 ≠ 𝑗, 𝑐𝑖 = 𝑖 = 1, … , 𝑛. Это система вида (2) с матрицей 𝑎𝑖𝑗 , 𝑎𝑖𝑖 𝑏𝑖 , 𝑎𝑖𝑖 0 𝑏12 ⋯ 𝑏1𝑛 𝑏 0 𝑏23 ⋯ 𝑏2𝑛 𝐵 = � 21 �. ⋮ ⋱ ⋮ 𝑏𝑛1 ⋯ 𝑏𝑛,𝑛−1 0 Метод Якоби ― это метод простой итерации для системы (2), полученной описанным способом (некоторые авторы называют методом Якоби общий метод простой итерации из п. 1 или, наоборот, методом простой итерации описанный здесь метод Якоби). Итерационная последовательность строится по (3), расчётная формула в развёрнутом виде выглядит так: (𝑘) (𝑘−1) (𝑘−1) (𝑘−1) 𝑏12 𝑥2 + 𝑏13 𝑥3 + ⋯ + 𝑏1𝑛 𝑥𝑛 + 𝑐1 , ⎧ 𝑥1 = (𝑘−1) (𝑘) (𝑘−1) (𝑘−1) ⎪ + 𝑏23 𝑥3 + ⋯ + 𝑏2𝑛 𝑥𝑛 + 𝑐2 , ⎪ 𝑥2 = 𝑏21 𝑥1 ⋮ ⋮ (𝑘−1) (𝑘−1) (𝑘) (𝑘−1) (𝑘−1) ⎨𝑥𝑖 = 𝑏𝑖1 𝑥1 + ⋯ + 𝑏𝑖,𝑖−1 𝑥𝑖−1 + 𝑏𝑖,𝑖+1 𝑥𝑖+1 + ⋯ + 𝑏𝑖𝑛 𝑥𝑛 + 𝑐𝑖 , ⎪ ⋮ ⋮ ⎪ (𝑘−1) (𝑘) (𝑘−1) + ⋯ + 𝑏𝑛,𝑛−1 𝑥𝑛−1 + 𝑐𝑛 , ⎩ 𝑥𝑛 = 𝑏𝑛1 𝑥1 𝑘 = 1, 2, … , начальная итерация 𝑥 (0) задана. -5- Естественно, для этого метода справедливы утверждения о сходимости и оценки погрешности предыдущего пункта. 3. Метод Зейделя Метод Зейделя представляет собой модификацию метода Якоби, заключающуюся (𝑘) в следующем. При вычислении очередного приближения переменной 𝑥𝑖 (𝑘−1) не (𝑘 − 1)-е итерации 𝑥1 (𝑘) (𝑘−1) используются , … , 𝑥𝑖−1 , как в методе простой итерации, а найденные на (𝑘) текущем k-м шаге 𝑥1 , … , 𝑥𝑖−1. Тогда расчётная формула будет выглядеть так: (𝑘) (𝑘−1) (𝑘−1) (𝑘−1) 𝑏12 𝑥2 + 𝑏13 𝑥3 + ⋯ + 𝑏1𝑛 𝑥𝑛 + 𝑐1 , ⎧ 𝑥1 = (𝑘−1) (𝑘) (𝑘) (𝑘−1) ⎪𝑥2 = 𝑏21 𝑥1 + 𝑏23 𝑥3 + ⋯ + 𝑏2𝑛 𝑥𝑛 + 𝑐2 , ⎪ (𝑘−1) (𝑘) (𝑘) (𝑘) (𝑘−1) ⎪𝑥 = 𝑏 𝑥 + 𝑏 𝑥 + 𝑏34 𝑥4 + ⋯ + 𝑏3𝑛 𝑥𝑛 + 𝑐2 , 31 1 32 2 3 ⋮ ⋮ ⎨ (𝑘) (𝑘−1) (𝑘) (𝑘) (𝑘−1) + 𝑐𝑖 , ⎪ 𝑥𝑖 = 𝑏𝑖1 𝑥1 + ⋯ + 𝑏𝑖,𝑖−1 𝑥𝑖−1 + 𝑏𝑖,𝑖+1 𝑥𝑖+1 + ⋯ + 𝑏𝑖𝑛 𝑥𝑛 ⎪ ⋮ ⋮ ⎪ (𝑘) (𝑘) (𝑘) + 𝑐𝑛 , ⎩ 𝑥𝑛 = 𝑏𝑛1 𝑥1 + ⋯ + 𝑏𝑛,𝑛−1 𝑥𝑛−1 𝑘 = 1, 2, … . Если определить треугольные матрицы 0 ⋯ 𝑏21 ⋯ ⎛ 𝑏32 0 ⋯ 𝐵1 = ⎜ 𝑏31 ⋮ ⋱ ⎝ 𝑏𝑛1 𝑏𝑛2 𝑏𝑛3 ⋯ 𝑏𝑛,𝑛−1 0 ⎞ 0 ⎟, ⋮ 0⎠ 0 𝑏12 𝑏13 ⋯ 𝑏1𝑛 ⎛0 0 𝑏23 ⋯ 𝑏2𝑛 ⎞ 𝐵2 = ⎜ ⋮ ⋱ ⋮ ⎟, 𝑏 0 ⋯ 𝑛−1,𝑛 0 ⋯ 0 0 ⎠ ⎝0 0 (тогда 𝐵 = 𝐵1 + 𝐵2), то расчётную формулу метода Зейделя можно записать в матричном виде: 𝑥 (𝑘) = 𝐵1 𝑥 (𝑘) + 𝐵2 𝑥 (𝑘−1) + 𝑐. ( 8) Далее приведены без доказательств утверждения о сходимости и оценках погрешности метода Зейделя. Теорема 3. Пусть ‖𝐵1 ‖ + ‖𝐵2 ‖ < 1. Тогда итерационная последовательность (8) сходится к точному решению 𝑥 системы (2) при любой начальной итерации 𝑥 погрешности -6- (0) и имеет место оценка где 𝑘 = 0, 1, … , Δ𝑥 (𝑘) = �𝑥−𝑥 (𝑘) � ≤ 𝑞 𝑘 ⋅ �𝑥 − 𝑥 𝑞= (0) � = 𝑞 𝑘 Δ �𝑥 (0) �, ‖𝐵2 ‖ < 1. 1 − ‖𝐵1‖ Замечание. Из теоремы следует, что метод Зейделя также имеет линейную скорость сходимости, как и метод простой итерации, причём чем меньше ‖𝐵2 ‖, тем она выше. Оценка погрешности априорная, она неприменима практически. Апостериорная оценка даётся следующей теоремой. Теорема 4. Пусть ‖𝐵‖ < 1. Тогда итерационная последовательность (8) сходится к точному решению 𝑥 системы (2) при любой начальной итерации 𝑥 грешности 𝑘 = 1, 2, … . Δ𝑥 (𝑘) =�𝑥−𝑥 (𝑘) �≤ (0) и имеет место оценка по- ‖𝐵2 ‖ (𝑘−1) (𝑘) ⋅ �𝑥 − 𝑥 �, 1 − ‖𝐵‖ Несмотря на то, что метод Зейделя является улучшением метода Якоби, он не обя- зательно сходится быстрее метода Якоби. Возможны случаи, когда метод Зейделя сходится медленнее метода Якоби. Причина в том, что они ориентированы на решение различных классов систем (1): последний ― с близкими к диагональным матрицами 𝐴, первый ― с близкими к нижнетреугольным (см. замечания к теоремам 1, 3). Пример. Решить систему методом итераций Запишем её в матричном виде: 2𝑥1 + 10𝑥2 − 6𝑥3 = 72, �−3𝑥1 + 𝑥2 + 25𝑥3 = −92, 20𝑥1 − 4𝑥2 − 2𝑥3 = −32. 𝐴𝑥̅ = 𝑏�, 2 10 −6 72 𝐴 = �−3 1 25 � , 𝑏� = �−92�. 20 −4 −2 −32 Попытаемся исключить неизвестные из уравнений и привести к виду 𝑥̅ = 𝐵𝑥̅ + 𝑐̅. Система примет вид 𝑥1 = −5𝑥2 + 3𝑥3 + 36, � 𝑥2 = 3𝑥1 − 25𝑥3 − 92, 𝑥3 = 10𝑥1 − 2𝑥2 + 16, -7- таким образом, 𝐵=�3 10 −5 3 0 −25�, −2 норма матрицы ‖𝐵‖1 =28. Применение метода итераций не гарантирует сходимости. нения: Приведем систему к виду 𝑥̅ = 𝐵𝑥̅ + 𝑐̅ другим образом. В системе переставим урав20𝑥1 − 4𝑥2 − 2𝑥3 = −32, � 2𝑥1 + 10𝑥2 − 6𝑥3 = 72, −3𝑥1 + 𝑥2 + 25𝑥3 = −92. Затем точно так же исключим неизвестные: 𝑥1 = 0,2𝑥2 + 0,1𝑥3 − 1,6 0,2 0,1 0,6�, � 𝑥2 = −0,2𝑥1 + 0,6𝑥3 + 7,2 ⇒ 𝐵 = �−0,2 𝑥3 = 0,12𝑥1 − 0,04𝑥2 − 3,68 0,12 −0,04 0 норма матрицы ‖𝐵‖1 = 0,8 < 1. Решим систему методом итераций. В таблице 1 дана по- следовательность векторов приближения. Табл. 1. Последовательность векторов приближения в примера на с. 7 𝑥1 −1,6 −0,5280 −0,9536 −1,0337 −0,9952 −0,9975 −1,0008 𝑥3 −3,68 −4,1600 −3,9558 −3,9868 −4,0047 −4,0000 −3,9996 𝑥2 7,2 5,3120 4,8096 5,0172 5,0146 4,9962 4,9995 Последовательность итераций приводит к решению с точностью ε = 1,7 ∙ 10−2. Эта величина вычислена как �𝑥̅ (6) − 𝑥̅ (5) �. Точное решение системы �𝑥̅ (6) − 𝑥̅ � = 1,0 ∙ 10−3 . −1 𝑥̅ = � 5 �; −4 Поэтому фактическая погрешность приближенного решения равна 1,0 ∙ 10−3 . -8-