Общие сведения о итерационных методах
Вся совокупность существующих численных методик подразделяется на точные и приближенные методы. Точные методы могут выдать решение задачи за конечное количество арифметических операций. Решение может получиться точным лишь в том случае, когда начальные данные задавались точно и промежуточные вычисления выполнялись без использования округлений. К точным методам следует отнести метод Гаусса, методику квадратного корня, метод оптимального исключения, метод ортогонализации.
Итерационные методы могут предоставить бесконечную последовательность приближений, предел которой, когда он имеется, будет являться решением задачи. Итерационные методы могут использоваться для приближенного решения алгебраических и транcцендентных уравнений, систем уравнений и других задач, включая поиск точек равновесия. Решение уравнения или системы уравнений при помощи итерационного метода может получиться как предел последовательности приближений, которые вычисляются в ходе процесса итераций. К итерационным методам следует отнести метод простых итераций, метод Ньютона, хорд, секущих решения уравнений, метод простой итерации и метод Ньютона решения систем уравнений.
При решении задачи методом итераций необходимо вначале задать начальное приближение. Затем из данного исходного приближения должны получиться новые, более точные приближенные значения. Далее эти новые приближенные значения продолжают «улучшаться» и так далее. При некоторых условиях, сформированная подобным образом последовательность приближений должна сходиться к точному решению.
Совокупность начальных приближений, при которых последовательность приближений может сходиться к решению задачи, именуется областью сходимости метода. Помимо сходимости к решению, если используется итерационный метод, считается существенным фактором и скорость сходимости, определяемая следующим выражением:
|xn+1 – x^∗ | = Θ|x n – x^∗ | k ,
где Θ является символом Ландау, то есть, некоторой константой.
При k = 1 реализуется линейная скорость сходимости, при k = 2 реализуется квадратичная скорость сходимости, а при k = 3 реализуется кубическая скорость сходимости.
Каждая скорость, которая превышает линейную, является сверх линейной. Базовым принципом большинства итерационных методов является так называемый принцип сжимающих отображений.
Итерационные методы для задач поиска точек равновесия. Метод простых итераций (метод Якоби)
Предположим имеется система квадратных линейных уравнений с вещественными коэффициентами, представленная в матричном виде:
AX=F
Предположим, что существует однозначная разрешимость этой системы, и выполним замену матричного уравнения эквивалентным ему уравнением:
X=X – ƬAX+ƬF (1),
где Ƭ является вещественным числом, именуемым стационарным параметр.
При помощи уравнения (1) можно составить итерационную последовательность векторов, определив ее рекуррентно:
{Xk}= Xk – ƬAXk + ƬF (2)
(k = 0, 1, 2, ….)
при предположении произвольного выбора нулевого приближения. Это означает, что метод простой итерации может быть сведен к замене точного решения системы (1) k - ой итерацией, имеющей достаточно большой номер k.
В графическом формате метод Якоби может быть представлен следующим образом. Следует оценить погрешность метода простой итерации. Является очевидным, что:
$Z_{k+1} = (E – ƬA)Z_k$ (3)
где Е является единичной матрицей. На рисунке ниже представлена схема исполнения метода Якоби.
Рисунок 1. Схема исполнения метода Якоби. Автор24 — интернет-биржа студенческих работ
Далее следует ввести в рассмотрение норму вектора в пространстве E^n и операторную норму квадратной матрицы порядка n. Присвоим название норме вектора X число ǁXǁ, которое равно длине вектора, и присвоим название операторной норме произвольной матрицы A число ǁAǁ, которое равно или точной верхней грани отношения: ǁAXǁ/ǁAǁ
на множестве всех векторов, отличных от нуля, X, или, что, то же самое, точной верхней грани нормы ǁAXǁ на множестве всех векторов X, которые имеют единичную норму. То есть по определению:
Рисунок 2.
Из (3) следует неравенство, которое является справедливым для любой матрицы A и любого вектора X:
ǁAXǁ ≤ ǁAǁǁXǁ (5).
Из матричного уравнения погрешности (3) и неравенства (5) можно получить, что для каждого номера k:
ǁZk+1ǁ ≤ ǁE – ƬAǁǁZkǁ (6)
Для того чтобы итерационная последовательность (2) при любых выборах начальных приближений X0 и при выбранном значении параметра Ƭ сходилась к точному решению системы (2), необходимым и достаточным является выполнение условия:
Ƿ = ǁE – ƬAǁ $\lt$ 1 (7)
Причем итерационная последовательность должна сходиться со скоростью геометрической последовательности со знаменателем ƿ. В случае симметричной матрицы, это условие выступает как необходимое условие сходимости итерационной последовательности при любых выборах начального, то есть, нулевого, приближения.
Для практических целей является недостаточной установка факта сходимости последовательности итераций. Здесь основным вопросом считается оценка скорости сходимости. Необычайно важно узнать, каким образом лучше всего распорядиться стационарным параметром Ƭ, для того чтобы получить самую быструю сходимость.
Приведенный выше итерационный метод Якоби получается из неявного метода в частном случае с заменой матрицы «В» единичной матрицей Е(n×n). Неявный метод простой итерации состоит в процедуре замены итерационной последовательности (1) более общей последовательностью, которая определяется следующим соотношением:
Рисунок 3.
Где матрица В является некоторой «легкообратимой» в квадратную матрицу порядка n, а ז является стационарным параметром.
Если матрица A представлена как симметричная и положительно определенная, а матрица B является положительно определенной. Тогда для того, чтобы итерационная последовательность:
Рисунок 4.
при любых выборах нулевого приближения X0 могла сходиться к точному решению X системы AX=F, достаточно выполнения следующего условия:
Рисунок 5.
