ЭФФЕКТИВНОСТЬ  ПРИМЕНЕНИЯ  ТОЧНЫХ  РЕЛАКСАЦИЙ  К  МЕТОДУ  ПРОСТОЙ  ИТЕРАЦИИ

Михеев  Сергей  Евгеньевич

д-р  физ.-мат.  наук,  профессор  кафедры  информационных  систем

Санкт-Петербургского  государственного  университета,  РФ,  г.  Санкт-Петербург

E -mail:  him2@mail.ru

EFFICIENCY  OF  EXACT  RELAXATION  APPLICATION  TO  FIXED–POINT  ITERATION  METHOD

Serge  Miheev

dr.  of  sciences  in  phys.  &  math.,  professor  of  St.Petersburg  State  University,  Russia  Saint  Petersburg

АННОТАЦИЯ

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

ABSTRACT

The  principle  of  minimality  is  used  to  construct  exact  relaxation  of  a  fixed-point  iteration  method  having  linear  convergence  rate.  The  exact  relaxation  has  increased  convergence  rate  versus  parent  fixed-point  iteration  method.  Calculation  spending  for  the  constructed  method  is  found.  Formulas  for  efficiency  estimations  of  achieved  acceleration  are  reduced  for  the  worst  case  and  for  some  statistic  hypothesis.  Some  numerical  efficiency  estimations  are  calculated.

Ключевые   слова:  сходимость;  скорость  сходимости;  оценки  погрешности;  вычислительные  затраты.

Keywords:   convergence;  convergence  rate;  error  estimation;  computational  cost.

Развитие  вычислительной  техники  расширяет  круг  задач  доступных  для  численного  решения,  с  одной  стороны,  а  с  другой  —  создает  потребности  в  новых  численных  алгоритмах,  которые  должны  лечь  в  новые  пакеты,  нацеленные  на  решение  новых,  неприступных  ранее  задач.  Существующие  пакеты  программ  исправно  решают  давно  известные  конкретные  задачи  и  на  новой  технике  они,  конечно,  будут  быстрее  это  делать.  Зачем  же  нужны  новые  алгоритмы?

Поясним  на  примере  метода  Ньютона  решения  системы  нелинейных  уравнений  g(y)=0.  Если  его  описать  итеративной  формулой  ,  то  легко  заметить,  что  трудоемкость  собственно  метода,  т.е.\  объем  вычислений,  величины  ,  производимых  после  получения  каким-нибудь  подалгоритмом  значений    и  ,  может  оказаться  пренебрежимо  малой  в  сравнении  с  затратами  на  вычисление  этих  значений.  Пусть  доступной  для  решения  методом  Ньютона  на  старой  технике  были  задачи,  трудоемкости  упомянутых  подалгоритмов  и  метода  Ньютона  в  которых  совпадали  и  были  равны  T,  а  нужная  точность  достигалась  за  k  итераций.  Т.  е.  полная  трудоемкость  была  k2T.  И  время  на  решение  задач  такой  трудоемкости  было  предельно  допустимым.  Если  бы  существовал  метод  M  в  2  раза  более  трудоемкий,  чем  метод  Ньютона,  и  обеспечивающий  сокращение  числа  итераций  на  25  %,  то  его  применение  было  бы  не  выгодно,  поскольку  его  общая  трудоемкость  составила  бы  0.75k3T=2.25kT.  Какое  увеличение  трудоемкости  подалгоритмов  доступно  после  повышения  производительности  ЭВМ  в  100  раз?  Для  метода  Ньютона:  k2T≥  k(T/100+zT/100).  Отсюда  z  ≤  200­1=199.  Т.  е.  возможно  увеличение  в  199  раз.  Для  метода  M:  k2T  ≥  0.75k(2T/100+zT/100).  Отсюда  z  ≤  (800/3)-2=264+2/3.  Таким  образом,  на  новой  технике  метод  M  позволяет  решать  уравнения  с  трудоемкостью  вычисления  правой  части  и  ее  производной  почти  на  33  %  больше,  чем  метод  Ньютона.  Таким  образом,  повышение  эффективности  (скорости  сходимости)  многих  численных  методов,  всегда  бывшее  актуальным,  становится  сверхактуальным  ввиду  сокращения  их  личного  удельного  веса  на  итерации.

1.  ПРИНЦИП  МИНИМАЛЬНОСТИ

Принцип  минимальности  (ПМ)  для  улучшения  приближений  итеративного  метода  заключается  в  привлечении  всей  имеющейся  информации  на  текущем  шаге  для  замены  приближения,  доставляемого  базовым  алгоритмом,  на  то,  которое  обеспечит  минимальную  оценку  погрешности  нового  приближения.  Итеративный  метод,  полученный  применением  принципа  минимальности  к  какому  либо  методу  будем  называть  точной  релаксацией  (ТР)  этого  метода.

В  этой  работе  будет  исследовано  применение  принципа  минимальности  к  методу  простой  итерации  (МПИ).  Пусть  имеется  некоторый  базовый  алгоритм,  являющийся  отображением  A:B→B,  где  B  —  банахово  пространство.  Надо  найти  неподвижную  точку  α  отображения  A.  Одним  из  способов  поиска  приближенного  решения  этой  задачи  является  МПИ.  Согласно  ему  (k+1)-е  приближение  вычисляется  по  формуле

,..  (1)

О  базовом  алгоритме  часто  известна  некоторая  дополнительная  информация  I.  Например,  такая

    (2)

Кроме  того,  при  реализации  МПИ  должен  появиться  критерий  остановки.  Часто  для  этого  привлекается  оценка  погрешности  k-го  приближения:  ||,  вычисляемая  тем  или  иным  способом.  В  частности,  вытекающим  из  (1)  и  (2):

  (3)

Итерации  заканчиваются  после  достижения  оценкой  заданного  уровня:  .

Для  ускорения  МПИ  (1)+(2),  а  точнее  создания  нового  итеративного  процесса  с  базовым  алгоритмом  A,  описанный  выше  ПМ  принимает  вид

Принцип  минимальности  (ПМ).   Ввести  в  состав  итеративной  информации    оценку  (2)  и  оценку  текущей  погрешности  .  Обозначим  множество  элементов  α,  удовлетворяющих  информации  ,  через  .  Следующей  итерацией  назначить  минимайзер  величины  (y):=arg  ||y-z||,  а  ее  минимум  будет  оценкой  погрешности  следующей  итерации.  Иными  словами, 

||y-z||  ,  ).  (4)

Опуская  постоянный  компонент  итеративной  информации,  ТР  принимает  вид:

():=M(,),  k=0,1,…  (5)

В  разновидности  банахова  пространства  —  евклидовом  или  гильбертовом  —  можно  дать  простую  геометрическую  интерпретацию  вышеизложенному.  Неизвестная  неподвижная  точка    после  вычисления  -й  итерации  находится  в  шаре  .  После  вычисления  -й  итерации  согласно  базовому  алгоритму    определено  еще  одно  множество,  в  котором  должна  находится  неподвижная  точка.  Это  зона  Аполлония    —  множество  из  ,  удовлетворяющих  (1).  Доказано,  что    —  шар  (  —  не  центр).  Таким  образом,  после  вычисления    известно,  что  неподвижная  точка  должна  принадлежать  мениску  —  пересечению  шаров:  .  Принцип  минимальности  предлагает  следующим  приближением  назначить  не  ,  а  центр  шара  минимального  радиуса,  содержащего  указанный  мениск.  Это  минимизирует  наибольшую  возможную  погрешность  при  имеющейся  информации. 

Далее,  где  возможно,  индекс  текущей  итерации  у  оценок  погрешностей  и  итеративных  точек  будет  опускаться,  а  вместо  индекса  последующей  итерации  (k+1)  будет  *,  т.  е.  x:=  ,  d:=,  :,    .

Когда  ,  итерации  (1)  согласно  (2)  порождают  глобально  сходящуюся  к    последовательность  ,  т.е.  сходимость  происходит  из  любой  начальной  точки  пространства  .

Поскольку  решение    должно  находиться  как  в  S(x,A),  так  и  в  ,  и  это  единственное  условие  для  формирования  ,  имеем  .  Согласно  принципу  минимальности  -й  итеративной  точкой  следует  назначить  центр  минимального  шара  (т.е.  шара  минимального  радиуса),  содержащего  множество  .  Лучшая  оценка  погрешности    итеративной  точки    тогда  будет  равна  радиусу  минимального  шара.  Числа,  большие  чем  этот  радиус  дали  бы  больший  оценочный  шар  на  следующей  итерации.

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

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

Распространенный  подход  к  исследованию  погрешности  текущей  итерации    в  МПИ  с  использованием  оценки  (2)  заключается  в  получении  оценки    погрешности  начального  приближения    и  далее  .  Использование  такого  типа  оценок  для  остановки  итеративного  процесса  по  достижении  заданной  точности  фактически  превращает  МПИ  в  метод  вида  (5).

2.  РАСЧЕТНЫЕ  ФОРМУЛЫ

Для  описания  зоны  Аполлония  введем  обозначения  r:=  A(x)-x,  r  :=  ||r||  . 

2.1.             Скалярный  случай

Наиболее  наглядно  проявление  метода  ТР  в  скалярном  пространстве.  Шар    и  зона  Аполлония  :  S(x,A)  превращаются  в  сегменты.  Пересечение  двух  сегментов  есть  сегмент.  Его  центр,  согласно  ТР,  назначается  следующей  итеративной  точкой  ,  а  половина  его  длины  —  оценкой    погрешности  точки  .  Вывод  расчетных  формул  для    и    несложен. 

=    (6)

  =  (7)

Дополнительные  вычислительные  затраты  на  итерацию  ТР  определяются  из  этих  формул.  Это  —  операция  умножения    на  ,  одна  операция  сравнения,  затем,  когда  ,  две  операции  умножения:    на    и    на  ,  а  когда    —  одно  умножение    на  ,  одно  деление    на  2  и  два  сложения-вычитания.  Итого:  одна  операция  сравнения  плюс  3-4  арифметических  операции.

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

, 

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

2.2.             Многомерный  случай

Расчетные  формулы  для  ТР  с  базовым  алгоритмом    [1]  следующие: 

r  :=  A(x)-x,  r  :=  ||r||  ,  R  :=  d(1-)/,

:=  (8)

:=  (9)

3.  ОБОБЩАЮЩАЯ  СХЕМА

Поведение  оценок  погрешностей  в  методе  ТР  носит  совсем  иной  характер  в  силу  их  зависимости  от  последовательности  результатов  применения  ТР  на  каждом  шаге.  То  есть  априори  эти  оценки  носят  вероятностный  характер  и  корректное  сравнение  их  поведений  следует  проводить  привлекая  ту  или  иную  статистику.  Вместе  с  тем,  согласно  принципу  минимальности  оценки  погрешностей  итераций  метода  ТР  всегда  не  больше  оценок  модифицируемого  метода,  а  в  некоторых  случаях  возможно  для  погрешности  следующей  итерации  по  ТР  получить  оценку  сверху,  которая  для  любой  текущей  итерации  будут  строго  меньше  оценки  следующей  итерации  исходным  алгоритмом.  Оценки    погрешности  последующей  итерации  метода  ТР  в  (7),  (9)  отличны  существено  от  оценок    в  МПИ  своей  непредсказуемостью.  Поэтому  сравнение  этих  оценок  по  худшему  варианту  представляется  неполноценным.

  Пусть  ,  где  ,    —  информация  заданной  структуры.  Пусть  для  поиска  приближенных  решений  задач    семейства    имеется  одноточечный  итеративный  метод  ,  порождающий  из  начальной  точки    и  начальной  информации    с  помощью  базового  алгоритма  вида  G  сходящуюся  к    —  решению  задачи    —  последовательность  итеративных  точек    по  рекуррентной  формуле  =G(,  ()),  k=1,2,...  Здесь    —  вектор  наблюдения,  вообще  говоря,  случайная  величина.  Будем  называть  такой  базовый  алгоритм  обобщающей  схемой.

Выбор  начальных  значений    и    лежит  вне  рамок  метода  .  Природа  параметра    может  быть  весьма  разнообразна.  Здесь  же  будет  рассмотрено  только  включение  в    скалярного  параметра  ,  смысл  которого  —  оценка  погрешности  текущего  приближения  :  .  Обозначим  с  помощью  индекса    x-составляющую  обобщающей  схемы,  d-составляющую  —  с  помощью  индекса  .  Тогда 

Пусть  G  и  H  две  обобщающие  схемы  для  решения  одной  задачи.  Без  случайностей  их  качество  количественно  можно  было  бы  сравнивать  так.

Определение  1.   В  детерминированном  случае  схема  H  в    раз  лучше  схемы  G,  если  верно  утверждение  (Y)  K(Y,v(Y))Y,v(Y))  и  для  бльших    оно  неверно. 

Расширим  такую  трактовку  качества  на  схемы  со  случайностями.

Определение  2.   Пусть  Е  —  символ  математического  ожидания.Схема  H  в    раз  лучше  схемы  G,  если  .  Величину    назовем  коэффициентом  эффективности  схемы  H  относительно  схемыG. 

Легко  заметить,  что  определение  1  есть  частный  случай  определения  2.

Сравним  с  этих  позиций  МПИ  совместно  с  оценкой  (2)  и  ТР  этого  МПИ.

4.  СТАТИСТИЧЕСКИЕ  СВОЙСТВА  ТОЧНОЙ  РЕЛАКСАЦИИ  МЕТОДА  ПРОСТОЙ  ИТЕРАЦИИ    МПИ  с  базовым  алгоритмом  ,  удовлетворяющим  оценке  (2),  соответствует  обобщающая  схема 

,  (10)

с  вектором  наблюдения  .  Как  и  ранее  .

Точной  релаксации  M  на  основе  базового  алгоритма    и  условия  (2)  соответствует  обобщающая  схема 

,  (11)

где  функции    и    те  же,  что  и  в  формулах  (6),  (7)  для  одномерного  случая  и  в  формулах  (8),  (9)  для  многомерного.

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

Гипотеза   I:    равномерно  распределена  в  шаре  .

Эта  гипотеза  является  своего  рода  минорантой  нашего  знания  о  случайной  величине  ,  а  минорантой  нашего  знания  о  величине  отклонения  вектора  наблюдения  от  текущего  приближения    является

Гипотеза   II:  Случайная  величина    равномерно  распределена  на  отрезке  .

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

Из  гипотезы  I  однозначно  определяется  распределение  с.  в.    (см.  далее).  Отметим,  что  в  одномерном  случае  гипотезы  I  и  II  совпадают.

Теорема  1.   В  одномерном  случае  для  гипотез  I  и  II  эффективность  ТР  относительно  МПИ  на  одном  базовом  алгоритме  есть 

Согласно  определению  1  и  теореме  1  ТР  улучшает  МПИ  в  (2+2)  раз.  При  сравнении  по  худшему  варианту  получается  улучшение  лишь  в  (1+)  раз.

В  многомерном  случае  ТР  может  выдавать  то  же  значение,  что  и  МПИ  с  одним  базовый  алгоритм  .  Доказано  [2],  что  это  обеспечивает  значение  ,  которое  максимизирует    в  (9).  То  есть,  можно  говорить,  когда  ,  что  у  ТР  холостой  ход  и  дополнительные  вычисления,  потраченные  на  нее  были  напрасны.  При  гипотезе  I  вероятность  попадания    на  сферу  холостого  хода    есть  отношение  “объема  сферы”    к  объему  шара  .  В  идеальном  случае  оно  равно  нулю.  При  машинном  представлении  множеств  возможны  хотя  и  малые,  но  не  нулевые  значения  этого  отношения.  Они  будут  сильно  зависеть  от  плотности  разрядной  сетки,  расположения  начала  координат  и  от  трактовки  включения  .  С  другой  стороны,  близость  точки    к  сфере  холостого  хода  соответствует  малому  выигрышу  от  применения  модификации,  что  может  вызвать  некоторые  сомнения  по  поводу  ее  эффективности.  Снимем  их  количественными  оценками.

Теорема  2.   Пусть  имеется  МПИ  с  оценкой  (2).  Положим 

.  (12)

.  (13)

Тогда  в  евклидовом  пространстве  E  для  гипотезы  I  эффективность  основанной  на  (2)  ТР  относительно  МПИ  с  одним  и  тем  же  базовым  алгоритмом  есть 

e  =  ,  (14)

а  для  гипотезы  II  независимо  от  размерности  пространства  такая  эффектив-ность  доставляется  формулой  (14)  при  . 

Аналитически  устанавливается,  что  когда  ,  при  гипотезе  I:  ,  а  при  гипотезе  II:  .  Также  аналитически  можно  обнаружить,  что  когда  ,  ,  причем    в  последней  формуле  соответствует  гипотезе  II  в  пространстве  размерности  не  менее  2.  Последний  интеграл  равен  рациональному  числу  для  четных    и  рациональному  числу,  умноженному  на  ,  для  нечетных.  То  есть    принимает  значения  /4  (гипотеза  II),  2/3,  3/16,  8/15,  5/32,  16/35,  ...  когда    пробегает,  соответственно,  1,  2,  3,  4,  5,  6,  ...

Аналитическая  оценка  в  общем  случае  выражения  в  правой  части  формулы  (14)  затруднительна.  При  некоторых  значениях  параметра    можно  получить  значения  коэффициента  эффективности  посредством  ЭВМ  по  формулам  из  теоремы  2,    ,  в  случае  действия  гипотезы  I  и  не  зависимо  от  размерности  (но  )  в  случае  действия  гипотезы  II.  Для  сравнения  посчитаны  также  значения  коэффициента  эффективности  в  одномерном  случае  по  простой  формуле  из  теоремы  1  при  тех  же  значениях  :

Таблица  1.

Коэффициенты  эффективности

Список  литературы:

1. Михеев  С.Е.  Нелинейные  методы  в  оптимизации.  СПб.:  изд.  СПбГУ,  2001.  —  276  с.

2.Михеев  С.Е.  Метод  точных  релаксаций  //  Вычислительные  технологии,  т.  11,  Новосибирск,  —  2005.  —  №  6,  —  С.  71—86.