§ 36. Итерации с переменным шагом

1. Идея Ричардсона.

Механизм сходимости простейшей схемы установления (4) § 35

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

то коэффициенты Фурье погрешности следующего приближения

выражаются через по формулам (см. (10), (11), § 35):

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

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

2. Чебышевский набор параметров.

Итерационный процесс Ричардсона задается формулами

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

Введем обозначение , положив

Тогда

Очевидно, что неравенство

при некоторых становится точным равенством. Числа задаваемые формулой (3), разбросаны по отрезку

где

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

многочлен (5) на отрезке наименее уклонялся от нуля: минимально. (8)

Эта задача теории аппроксимации функций решена в 1892 году А. А. Марковым. Искомый многочлен выражается через многочлен Чебышева (см., например, В. Л. Гончаров, Теория интерполирования и приближения функций, М., 1954)

наименее уклоняющийся от нуля на отрезке среди всех многочленов степени k, с коэффициентом единица при Именно, если сделать линейное преобразование

переводящее отрезок в отрезок , а точку в точку , то

итерационных параметров , при которых возникает многочлен (10), определяется из условия, чтобы нули многочлена при преобразовании. (9) переходили в нули многочлена Чебышева :

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

Далее, из (9) получаем

Поэтому при больших М

откуда, с учетом (13), следует

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

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

Для погашения первоначальной погрешности в раз надо выбрать k из условия т. е.

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

Оно лишь в конечное число раз

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

Использовать циклы длины нецелесообразно. Например, при процесс Ричардсона (4) превратится в процесс простых итераций (1) с оптимальным выбором т. Число шагов процесса для уменьшения нормы первоначальной ошибки в раз будет как показано в п. 2 § 35. Это число в раз превышает число шагов, необходимых для этой же цели при выборе длины k цикла в соответствии с (15).

3. Нумерация итерационных параметров.

Формулы (11) задают оптимальный набор итерационных параметров (при заданном фиксированном k). Переставим как-либо члены последовательности , расположив их в некоторой очередности и будем вести итерации по формулам

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

Рис. 45.

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

Проследим за эволюцией с ростом l при . В этом случае

Рассмотрим линейные функции нули которых определяются формулами (11). Из этих формул видно, что при или справедливо неравенство и поэтому (рис. 45)

Если то и поэтому

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

Если гипотетически считать, что этого не произошло и что счет продолжается точно, то к шагу величина вновь уменьшится, так что

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

причем величина не малая по абсолютной величине.

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

Но при , очевидно,

Поэтому

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

Если на шаге процесса (13) внесена погрешность округления

то на шаге она разовьется в

Поэтому целесообразно стремиться к такому выбору при котором имеет место оценка

при умеренном значении А.

Пусть компонента погрешности нулевого приближения. К l-му шагу она разовьется в

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

при умеренном значении В.

В работе В. И. Лебедева и С. А. Финогенова, ЖВМ и МФ 11, № 2, (1971), и в работе А. А. Самарского [23] указаны различные целесообразные способы нумерации параметров и освещена история вопроса. Приведем результаты работы В. И. Лебедева и С. А. Финогенова. В ней предполагается, что k является степенью числа 2, т. е. и указаны реккурентные формулы для построения

Именно, при

Если при порядок уже определен:

то полагаем

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

При указанном способе (21) упорядочения итерационных параметров числа А и В в неравенствах (19) и (20) можно выбрать независимыми от k и от

Алгоритм упорядочения параметров, указанный А. А. Самарским, формулируется несколько сложнее, но при этом k не обязательно степень двойки. Число k может иметь вид . Вместо (19), (20) установлены другие оценки, гарантирующие устойчивость в некотором смысле.

4. Метод Дугласа Рэкфорда.

В схеме переменных направлений (6) § 35 будем считать итерационный параметр зависящим от номера шага, положив

Для погрешности и получим выражение

где

При заданном k оптимальным является такой выбор чисел при котором величина

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

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

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

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

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

Обоснуем равенство (22) и при этом объясним, как можно выбрать параметры . Очевидно, что

Поэтому для выполнения при любых неравенства (22) достаточно, чтобы при любом хотя бы один из k сомножителей удовлетворял неравенству

Все числа принадлежат отрезку

Итак, для выполнения (22) достаточно ввиду (23), чтобы для каждого значения из отрезка (24) хотя бы при одном выполнялись неравенства

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

Для этого нужно, чтобы для каждого из отрезка (24) при некотором , выполнялись неравенства

Зададим соответственно формулами

Тогда при возрастании от до число пробегает отрезок (25).

Очевидно, что, выбрав k из условия

мы и получим по формуле (26) интересующую нас последовательность

ЗАДАЧИ

1. Можно ли выбрать итерационные параметры та так, чтобы за конечное число шагов итерационного процесса (4) получилось точное решение разностной задачи Дирихле?

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

2. Объяснить механизм вычислительной неустойчивости, развивающейся при расчете по формулам (16) при

и больших значениях k и М.

Какие гармоники будут преобладать в ряде Фурье для погрешности , полученной в результате расчета при с ошибками округления?

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

при произвольном выборе произвольно?

4. Почему при использовании схемы Дугласа — Рэкфорда очередность использования параметров не влияет существенным образом на вычислительную устойчивость итерационного процесса?

5. Считая, что затраты машинного времени на один шаг итерационного процесса Дугласа — Рэкфорда в двадцать раз больше, чем на один шаг процесса Ричардсона, прикинуть по формулам (15) и (27), при каких М преимущества метода Дугласа — Рэкфорда начинают проявляться.