§ 4. Замыкания вычислительных алгоритмов

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

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

и пусть

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

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

здесь

Соотношение (4) называется замыканием вычислительного алгоритма (3).

Мы не дали строгого определения замыкания вычислительного алгоритма. Существо дела станет понятнее после рассмотрения замыканий алгоритмов решения краевой задачи.

Определение понятия вычислительного алгоритма не исключает возможности . В этом случае равенства

понимаются в том смысле, что

Случай соответствует итерационным методам решения задачи (1). Если операторы равномерно ограничены по , то говорят, что алгоритм (3) имеет регулярное замыкание. В противном случае говорят, что алгоритм имеет нерегулярное замыкание.

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

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

При прямом ходе прогонки получаются соотношения

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

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

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

Таким образом, (6) имеет ненулевой предел. Применим такую же нормировку и в общем случае. Поскольку в рассмотренном примере существовал предел

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

Умножим соотношение (5) на и положим . Тогда (5) перепишется в виде

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

отсюда

Соотношение (9) можно преобразовать к виду

а соотношение (10) — к виду

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

Соотношения (11), (12) показывают, что величины , удовлетворяют уравнениям, напоминающим метод Эйлера численного интегрирования дифференциальных уравнений

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

Таким образом, в окрестности точки начальные условия для численного интегрирования по формулам (11): (12) имеют не совсем обычный характер и развитые нами методы оценки близости решений сеточных и дифференциальных задач в рассматриваемом случае неприменимы. Глядя на соотношения (15), можно было бы предположить, что функция является решением (13), ведущим себя вблизи нуля, как решением (14). ведущим себя вблизи нуля, как .

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

и соответствующую сеточную задачу

Решения этих задач можно записать в виде

(определение и см. в § 2). Поскольку для этой краевой задачи и все , то и соотношение (8) имеет вид

Подставляя сюда , получим

Пользуясь оценками близости

можно получить оценку

Функция

удовлетворяет дифференциальному уравнению (13), поскольку

Согласно определению при малых имеем и, таким образом, , как и предполагалось.

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

и, таким образом,

Для точек этой окрестности можно написать цепочки соотношений

и, таким образом,

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

Выпишем теперь соотношения (3) и соответствующие замыкания алгоритма. Возьмем и при за (3) примем совокупность соотношений

а при — совокупность соотношений

где — точное решение сеточной задачи. Положим . Тогда замыкание алгоритма (4) будет выглядеть следующим образом:

где для

и для

здесь - точное решение дифференциальной задачи (равенство опущено).

Рассмотрим примеры поведения функции . Пусть тогда, согласно уравнению .

и

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

Рис. 9.4.1

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

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

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

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

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

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

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

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

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