§ 6. Оптимизация скорости сходимости итерационных процессов

Рассмотрим простейший итерационный способ решения системы уравнений :

Мы видели, что скорость сходимости такого итерационного процесса существенно зависит от максимального модуля собственных значений матрицы . Если собственные значения матрицы А, то . Из рис. 6.6.1 видно, что при действительных собственных значениях различных знаков этот максимум больше 1 и итерационный процесс расходится.

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

Рассмотрим задачу минимизации за счет выбора .

Рис. 6.6.1

Рис. 6.6.2

Для нахождения удобно обратиться к геометрической картине (рис. 6.6.2). Ясно, что при . При функция неотрицательна и монотонно убывает на отрезке , поэтому . При величина отрицательна и модуль ее растет с ростом . При некотором наступит момент, когда

и тогда . Если , то если , то .

Таким образом, значение является искомым. Решая уравнение (1) относительно , получим . Отсюда

Задача 1. Доказать сходимость итерационного процесса при .

На примере систем с матрицей (здесь и далее неравенство означает, что А — симметричная положительно определенная матрица) рассмотрим более формализованные постановки проблем оптимизации скорости сходимости итерационных процессов.

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

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

Рассмотрим несколько более общий итерационный метод, чем метод простой итерации. А именно, в методе простой итерации

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

где — некоторое начальное приближение.

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

Тогда через шагов итерационного метода (2) погрешность будет выражаться через погрешность начального приближения следующим образом:

где — погрешность начального приближения.

Обозначим . Таким образом, оператор (матрица) связывает погрешности приближения на нулевом и шагах итерационного процесса. Из (4) имеем

(Всюду далее на протяжении этого параграфа под знаком нормы будем иметь в виду норму )

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

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

здесь , как обычно, означает аргумент, т.е. мы ищем многочлен , для которого имеет место равенство .

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

Лемма. Справедливо равенство

где — многочлен Чебышева степени .

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

Так как на , то по предположению имеет место строгое неравенство

(9)

Рассмотрим многочлен . Пусть

Из равенства имеем

Поскольку , то, согласно (9),

Отсюда следует, что .

Точки расположены монотонно на отрезке . Поскольку меняет знак при переходе от каждой из этих точек к следующей, то имеет корней на . Кроме того,

Мы получили многочлен степени , который имеет нуль; следовательно, ,

Мы пришли к противоречию с (9). Лемма доказана.

Заметим, что данный многочлен решает также исходную оптимизационную задачу, так как по построению он имеет на отрезке n нулей.

Оценим скорость сходимости полученного метода. Воспользуемся явным представлением многочленов Чебышева

При имеем

Введем обозначение . Из (10) имеем . Так как то при больших

Поскольку и одного знака, то

На основе приведенных построений можно предложить несколько типов итерационных процессов.

В одном случае задаются последовательностью значений , приближения определяют по рекуррентной формуле

где . Имеем

где , и в итоге

Рассмотрим случай , т.е. . Тогда, обозначив , можно записать итерационный процесс (12) в виде

Соответствующая оценка погрешности имеет вид

Такой итерационный процесс называют оптимальным (по числу итераций) линейным, k шаговым итерационным процессом. В частном случае согласно (5), выполняются соотношения

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

а погрешность оценивается следующим образом:

(этот метод мы уже построили выше в этом параграфе).

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

то являются величинами, обратными к корням многочлена . Но по доказанному выше , т.е. корни этого многочлена равны

Отсюда следует, что значения надо брать из совокупности

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

При больших k и произвольном выборе алгоритм вычисления по формулам (2), (15) также неустойчив к погрешностям округления. Так, например, если взять , то согласно (3) уравнение для погрешности имеет вид . При наличии округлений оно запишется в виде

Последовательно выражая через предыдущие, имеем равенство

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

При реальных вычислениях для обеспечения устойчивости алгоритма к округлениям осуществляют «перемешивание» чисел . Алгоритм перемешивания в случае заключается в следующем. Последовательно, при строится «наиболее перемешанная» перестановка чисел . При она состоит из двух чисел 2, 1. Пусть уже построена перестановка следующая перестановка берется в виде . Например, при эта перестановка имеет вид (11, 6, 14, 3, 10, 7, 15, 2, 12, 5, 13, 4, 9, 8, 16, 1). При таком алгоритме выбора итерационных параметров норма оператора перехода всегда не будет превосходить 1.

Задаваясь к строим таблицу чисел , и производим итерации (2) при значениях

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

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

Запишем соотношение (17) последовательно для . Получим

Многочлены Чебышева связаны рекуррентным соотношением

Умножим первое уравнение (18) на , третье — на , а к обеим частям второго уравнения применим матрицу . Складывая результаты, получим

Выражение в фигурных скобках в (20) равно нулю в силу (19). Таким образом, погрешности искомого итерационного процесса должны удовлетворять трехчленному соотношению

(21)

Так как , то подставляя это выражение в (21), получим

Вследствие (19) и равенства имеем

и соотношение (22) может быть переписано в виде

Мы получили требуемое рекуррентное соотношение. Приведем его к более удобному виду. Вследствие (23) равенство (24) можно переписать в виде

или

где / Разделив обе части получим

откуда

Таким образом, можно рекуррентно вычислять величины из (26) и затем векторы из (25). Для получения совокупности векторов потребуется произвести умножений матрицы на вектор, умножений векторов на числа, сложений векторов и операций с числами. При этом для всех , вследствие (5), (9), выполняется оценка

Квадратное уравнение

имеет два положительных корня

Наименьший из этих корней, равный

обозначим через .

Итерационный процесс (25). (26) называют оптимальным (по количеству итераций) линейным итерационным . При реализации процесса (25), (26) после любых к применений матрицы А мы получаем оптимальный результат в смысле (6). Из сказанного видно, что по скорости сходимости итерационный процесс (25), (26) предпочтительнее, чем (12). Однако иногда от него отказываются в пользу (12) из-за соображений экономии памяти ЭВМ.

Получим более наглядную оценку скорости сходимости построенных итерационных процессов. Согласно (27) и (11) для оптимального итерационного процесса выполняется оценка

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

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

Для сравнения рассмотрим оптимальный линейный одношаговый процесс, имеющий, согласно (13), оценку погрешности

отсюда получаем оценку числа итераций

При имеем

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

Задача 2. Рассматривается итерационный процесс

Пусть р нечетное и при всех к совокупности совпадают с совокупностями

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

Задача 3. Пусть и совокупности при каждом совпадают с совокупностями величин

Показать, что для такого итерационного процесса при всех справедлива оценка

т.е.

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

при ;

Матрица этой системы является положительно определенной, и для нее

т.е. . Например, при шаге выигрыш в числе итераций примерно в 20 раз.

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

Примечание. При имеем

Таким образом, при больших итерационная формула (25) близка к формуле

Если при итерации будут производиться по этой формуле, то при условии этот итерационный процесс требует примерно столько же итераций, сколько итерационный процесс (25).

Задача 4. Для итерационного процесса (29) получить оценку погрешности

Указание. Представить погрешность в виде , где — полная ортогональная система собственных векторов матрицы А. Подстановкой в (29) получить разностное уравнение, связывающее . Получить явное выражение для и с его помощью получить требуемую оценку (30).

Задача 5. Показать, что оценка (30) не может быть улучшена на множестве матриц, удовлетворяющих условию .