num-meth

Теорема 1.2.1. Итерационный процесс:

x(k+1) = h + Bx(k)

сходится к единственному решению исходной системы, если какая-либо норма матрицы B меньше единицы.

Доказательство. Возьмем последовательность приближенных решений {x(i)}ni=1, где x(k) = h + Bx(k−1), k = 1, n. Имеем:

x(k) = h + Bx(k−1) = h + B(h + Bx(k−2)) = (E + B)h + Bx(k−2)

Откуда:

∑k−1

x(k) = (E + B + B2 + · · · + B(k−1))h + Bkx(0) = ( Bp)h + Bkx(0)

p=0

Т.к. по условию B < 1, то Bk →k→∞ 0 и lim Bk = 0.

k→∞

Имеем ряд:

∑∞

Bp

p=0

При этом, для всякой матрицы B, у которой все собственные значения по модулю не превосходят 1, имеет место1:

∑∞

Bp = (E − B)−1

p=0

Отсюда сразу получаем:

x = h + Bx, т.е. вектор x, полученный как предел последовательности {x }i=1, является точным решением исходной и приведенной систем.J

Теорема 1.2.2. Погрешность k-го приближенного решения x(k) в методе итераций оценивается при произвольном выборе нулевого приближенного решения по формуле:

x − x(k) ≤ x(k+1) − x(k)

1 − B

Доказательство.(без доказательства)J

1Почему это так для матрицы B будет установлено в разделе, посвященном проблеме собственных значений

Откуда видно, что метод Зейделя эквивалентен методу простой итерации. Из этого же уравнения определяются условия сходимости метода Зейделя – необходимо, чтобы определитель матрицы (E − B1)−1B2 не превосходил 1. Однако, по сравнению с методом простой итерации, метод Зейделя обычно лучше сходится.

1.2.2.3Преобразование СЛАУ к виду, удобному для итераций

Один из простейших способ получения приведенной системы из исходных заключается в выражении в каждом i-м уравнении i-й же переменной через остальные. В этом случае, диагональные элементы матрицы B будут нулевые.

Оказывается, что достаточным (но не необходимым) условием сходимости итерацион-

Но величина µ есть в точности одна из норм матрицы B, следовательно, согласно доказанной ранее теореме, итерационный процесс сходится.

Таким образом, можно попытаться исходную систему преобразовать к эквивалентной так, чтобы для получившейся матрицы выполнялось условие диагонального преобразования. Однако этот способ не слишком эффективен, особенно при системах больших размерностей. Поэтому поступают по-другому.

В этом случае, возьмем некоторый параметр τ, и, в предположении, что матрица A является симметрической положительно определенной, от исходной системы перейдем к следующей:

ˆ

τAxˆ = τb

Если же матрица A не является симметрической положительно определенной, то домножим слева обе части исходного уравнения на матрицу AT. Тогда перейдем к системе

ˆ

ATAxˆ = ATb, в которой матрица коэффициентов при переменных ATA является симметрической положительно определенной. Может оказаться, что эта матрица уже соответствует

26 Глава 1. Численные методы линейной алгебры

требованию сходимости итерационного процесса. Тогда выполнять дальнейшие шаги нет необходимости. В противном случае, полученную систему с симметрической положительной матрицей домножаем слева на параметр τ.

max µ(λ) достигается, когда µ(m) = µ(M). А это, в свою очередь, выполняется, когда

Учитывая, что вычисление собственных значений в общем случае представляет собой трудоемкую задачу, в качестве параметра tau можно взять величину:

τ = σ2 ,

где σ – число, большее какой-либо легко вычисляемой нормы матрицы A.

Обобщением описанного метода является подход, когда вместо матрицы E берется некоторая матрица M, и осуществляется переход к системе:

ˆ

Mxˆ = (B − τA)ˆx + τb

Итерационный процесс в этом случае приобретает вид:

Параметр τ выбирают так, чтобы полученный итерационный процесс сходился. Этого достигают, исходя либо из границ собственных значений матрицы исходной системы, либо из требований минимизации на каждой итерации погрешности в соответствии с той или иной нормой.

Соответственно выбору вида матрицы M и параметра τ приходят к тем или иным итерационным методам.

Определение 1.2.1. Итерационный процесс, в котором M = E, называется явным. Итерационный процесс, в котором M ≠ E, называется неявным.

Выбирая в качестве M какую-либо легко обратимую матрицу, получают общий неявный метод простой итерации.

Если

то получают модифицированный метод простой итерации. Если же

M = D + τA1,

где

то получается т.н. метод верхней релаксации

Замечание 1.2.1. Если B − A > 0, то B > A.

Теорема 1.2.3. Если имеет место A > 0, то для того, чтобы сходился итерационный процесс общего неявного метода простой итерации при любом выборе нулевого приближения, достаточно, чтобы выполнялось условие 2M > A > 0.

Доказательство.(без доказательства)J

Теорема 1.2.4. Для сходимости итерационного процесса модифицированного метода простой итерации при любом выборе нулевого приближения достаточно, чтобы выполнялось условие: 2D > A > 0.

Доказательство.(без доказательства)J

Теорема 1.2.5. Если A > 0, то для сходимости процесса верхней релаксации достаточно, чтобы выполнялось условие 0 < τ < 2.

Доказательство.(без доказательства)J

ˆ

Замечание 1.2.2. В случае, если для исходной системы Axˆ = b условие A > 0 не вы-

T Tˆ

полняется, то можно перейти к системе A Axˆ = A b, для которой уже приведенные выше три теоремы оказываются применимы.

1.2.2.4Метод Некрасова.

Систему Axˆ = fˆ можно подготовить к виду, удобному для применения одношагового циклического процесса различными способами. Наиболее употребительной является модификация одношагового циклического процесса, параллельная методу простой итерации (метод Некрасова).

Система Axˆ = fˆ записывается в виде

и последовательные приближение определяются по формулам

Выбранная подготовка системы Axˆ = fˆ к виду xˆ = Bxˆ + G основана на предвари-

A = L + D + R

что в прежних обозначениях:

M = −D−1L, N = −D−1R,

S = (E − M)−1N = −(E + D−1L)−1D−1R = −(D + L)−1R

Характеристический полином

| − (D + L)−1R − tE|

матрицы

−(D + L)−1R

после умножения на

| − (D + L)|

принимает вид

|R + (D + L)t|.

Следовательно, для сходимости метода Некрасова необходимо и достаточно, что бы все корни уравнения (уравнение Некрасова)

были бы по модулю меньше единицы.

Утверждение1

Если матрица А положительно определена, то метод Некрасова для системы АХ = F сходится. Это условие в предположении положительности диагональных элементов матрицы А оказывается также необходимым.

Установленный критерий показывает, что если матрица системы симметричная с положительными диагональными элементами, то область сходимости метода Некрасова шире области сходимости метода простой итерации.

Вычисление по методу Некрасова зависит от порядка нумерации уравнений (и неизвестных). Если в каждом цикле неизвестные вычисляются начиная с xn и далее xn−1, . . . , x1, то рассчетные формулы будут

В матричной форме один так проведенный цикл равносилен одному шагу метода последовательных приближений, примененному к системе X = BX + G

при B = −(D + R)−1L, G = (D + R)−1F.

Два последовательных цикла по формулам (2) и (2′) равносильны одному шагу метода последовательных приближений, примененному к системе , подготовленной к виду

X = (D + R)−1L(D + L)−1RX + (D + R)−1(E − L(D + L)−1)F.

Собственные значения матрицы C = (D + R)−1L(D + L)−1R равны собственным значениям матрицы R(D + R)−1L(D + L)−1.

Легко видеть, что для любых двух матриц D и R справедливо тождество

R(D + R)−1D = D(D + R)−1R.

Поэтому

R(D + R)−1L(D + L)−1 = D(D + R)−1RD−1L(D + L)−1.

Последняя матрица подобна матрице

Если исходная матрица симметрична и ее диагональные элементы положительны, то мат-

так что E − S будет положительно-определенной в том и только том случае, когда A положительно определена. Поэтому для симметричной матрицы с положительными диагональными элементами процесс сходится в том и только том случае, когда A положительно определена.

Очевидное тождество

|(1 + t)S − tE| = |D−1||L′D−1L − tA|

показывает, что наибольшее собственное значение σ матрицы S равно µ+1µ , где µ− наибольший корень уравнения |L′D−1L − tA| = 0.

1.2.2.5Итерационный метод с Чебышевским набором параметров.

Пусть симметрическая матрица A > 0. Тогда явный итерационный метод

tk = cos (2k − 1)π , k = 1, 2, 3m . . .

2n

называется явным итерационным методом с чебышевским набором параметров. Особенность этого метода состоит в том, что он обеспечивает минимальную евклидову норму погрешности на n-м шаге итераций. Имеет место оценка:

xˆ(k+1) − xˆ(k) E ≤ qn xˆ(0) − xˆ E,

Из приведенных соотношений оценивается номер итерации, на которой достигается требуемая точность. Легко убедиться, что этот номер определяется по формуле:

Упражнение 1.2.1. Доказать верность приведенной выше формулы.

Следующий неявный итерационный метод:

xˆ(k+1) − xˆ(k)

(k) ˆ

M + Axˆ = b, k = 0, . . .,

где параметры τk определяется аналогично предыдущему, за исключением следующего:

ξ= λmin(B−1A) , λmax(B−1A)

–такой процесс называется неявным итерационным процессом с чебышевским набором параметров.

Этот метод обеспечивает минимальную норму xˆ(k+1) − xˆ(k) M . Имеет место:

xˆ(k+1) − xˆ(k) M ≤ qn xˆ(0) − xˆ M

Параметр qn рассчитывается аналогично предыдущему, за исключением того, что в качестве ξ берется: