В Н Беловодский, Р Л Варзар - Скорости сходимости метода зейделя в зависимости от начальных условий - страница 1

Страницы:
1 

УДК 518

 

О скорости сходимости метода Зейделя в зависимости от начальных условий

 

Беловодский В. Н., Варзар Р. Л.

Донецкий национальный технический университет

 

На примере простейших линейных систем вскрываются особенности сходимости итерационного процесса типа Зейделя. Обнаруженные экспериментально аномалии объясняются теоретически.

 

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

Итак, рассмотрим систему линейных уравнений

Ax = b, (1)

где A = (ai}) nn , X = (x1,..xn )T, b = (b1,...bn )T , det A Ф 0.Известна

простая универсальная процедура, позволяющая привести её к нормальному виду [1]. Она заключается в следующем.

Умножим обе части системы (1) на AT , обозначим полученную систему через

Ax = b

и разделим первое уравнение на a11 , второе на a22 и так далее. Такая

операция возможна, т. к в силу det A Ф 0 , очевидно, ati Ф 0 . Обозначим новую систему через

A"x = b".

Её отличительной особенностью является то, что диагональные элементы матрицы A" равны единице. Это позволяет естественным образом отделить в левой части вектор x

x + (A'- E) x = b" и представить систему (1) в виде

x = Dx + d, (2) где D = E - A", d = b".

Оказывается, что метод Зейделя, применённый к системе (2) сходится при любом начальном приближении. Это означает, что областью притяжения точного решения  x * системы (1) является

пространство Rn.

На рисунке 1 для системы

(1   2^       . (5\

A ■■

3 4


v 6 очное решение которой, очевидно, равно

( - 4 ^ x* = ,

V4,5 J

приводятся результаты визуализации скорости сходимости итерационного процесса, сформированного по методу Зейделя для нормальной системы (2).

Алгоритм визуализации состоял в следующем. Путем сканирования площади прямоугольника с заданным шагом h как по горизонтали, так и по вертикали, в данном случае значение h было принято равным 0.5, осуществлялся последовательный перебор его

точек. Каждая из полученных точек xki принималась в качестве начальной, после чего для нее производился запуск итерационного процесса и устанавливалось количество итераций Nkl, необходимое для покоординатного достижения заданной точности є к точному решению x*. После формирования массива Nkl производилось определение  его  наибольшего  M  и  наименьшего  m значений.

Ранжирование цвета точки xki на экране монитора осуществлялось по формуле

гк = ^(256-1),

M - m

где 256 - число уровней в градациях серого.

На    рисунке    1    видна    выраженная    темная полоса. Расположенным на ней точкам соответствует наименьшее число

итераций, а именно Nkl =1 . Эта полоса и представляет собой область

«оптимальных» начальных условий или область наивысшей скорости сходимости метода Зейделя. Обратим внимание на то, что она не является     «круговой».     Следовательно,     близость начального

приближения x(0) к точному решению x* не является решающим фактором, обуславливающим скорость итерационного процесса.


Так,  например,  для  начальных точек x


(0)


:(-4;20)


и

x    = (30;4.5) значения Nkl соответственно равны 249 и 1. Попытаемся разобраться в этих явлениях.

Прежде всего, приведем метод Зейделя к методу простых итераций. Для этого представим соответствующую ему итерационную процедуру в виде

x(n+1) = D1 x(n) + D2 x (n+1) + d1,

где D = D1 + D2, D1, D2 - треугольные матрицы.

Разрешая  теперь  последнее     соотношение относительно

„(n+1)

x      , имеем

(3)

x(n+1) =

\-1

D/ x(n) + d1

где D/ = (E-D2)-1 D1, d = (E -D2)-1 d.

Выполнив  теперь  описанные  действия  для исследуемой системы, получим

0.09

(0   -1.4^                   ( 2.3 ^

j

привести

D1 =1                I, d

V0   0.98 J

D/

Если    же    теперь    последнюю систему каноническому виду, то все становится очевидным.

Действительно, собственные значения  12 матрицы

равны l1 = 0 , l2 = 0.98 . Соответствующие им собственные векторы, определенные с точностью до постоянного множителя, равны e1 = (1;0), e1 = (1;-0.7). Выбирая их в качестве нового базиса, получим матрицу перехода

T

(1      1 ^ 0   - 0.7

Тогда связь между координатами точек в старом и новом базисах описываются соотношениями

x = Ty или y = T 1 x

а точное решение

y* =

( 1.7/0.7 ^

■4.5/0.7

Далее, итерационный процесс в новом базисе будет выглядеть

так

—1,7/

-1 /Ут-іДn)

У(n+1) = t-1 d Ty(n) + T ~ldа для полученной системы

 

y


(n+1)


(0     0 ^

0 0.98


y(n)+


( 1.7/0.7 ^ - 0.09/0.7

Отсюда следует, что компоненты (п+1)-й итерации через начальные условия выражаются следующим образом

y(n+1) = 0 • y(0) + 0 • y20) +1.7/0.7 ' y2n+1) = 0• y10) + (0.98)n y20) -— (0.98n-1 + 0.98n-2 + ... +1)

 

Или, после использования формулы суммы геометрической прогрессии,

' y(n+1) = 1.7/0.7

*y2n+1) = (y20) + 0L^) 0.98n -4.5/0.7 .

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

компоненте регулируется величиной отклонения y2(0) от значения

- 4.5/0.7 . В частности, при y20) = -4.5/0.7 точное значение y2 *

также достигается на первой итерации независимо от y1(0) . Таким

образом, прямая y2 = -4.5/ 0.7 или в прежних координатах, x2 = 4.5,

для рассматриваемой системы является прямой наивысшей, а прямые

y = y0, где y0 є R - линиями равной скорости сходимости. Для всех

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

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

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

Литература

 

1. Поршнев С. В. Вычислительная математика. Курс лекций. -СПб.: БХВ-Петербург, 2004. - 320 с.

Страницы:
1 


Похожие статьи

В Н Беловодский, Р Л Варзар - Скорости сходимости метода зейделя в зависимости от начальных условий