Дискретно-непрерывная математика (стр. 134 )

Предварительно определим так называемый R-фактор:

где обозначает одну из последовательностей или . Ортега и Рейнбольдт, опираясь на теорему об эквивалент­ностинорм, доказали, что значение Rt не зависит от того, какая норма используется в качестве ||∙||. Справедлива также следующая лемма.

Лемма 1. Пусть — последовательность, порожденная про-

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

к и обладает свойством (1). Тогда для соответствующих по­следовательностей выполнено равенство

Доказательство. Исходя из (27 из микромодуля 29) для k≥0, получаем

При использовании монотонной векторной нормы имеем

Так как очевидно, что

то

Поскольку доказательство для t=1 можно провести аналогич­ным образом, оно здесь опущено.

Из леммы 1 следует, что в дальнейших рассуждениях можно не указывать, какая именно из последовательностей или

— имеется в виду. Это не так, если (1) не выполнено. Проиллюстрируем сказанное на примере.

Пример. Последовательность

имеет предел [0, 1]. Очевидно, что

и, следовательно, при t = 1

С другой стороны, при всех k ≥ 0, откуда следует, что

Обозначим через множество порожденных итерационной процедурой I последовательностейдля которых

справедливо

Под R-фактором процедуры I будем понимать

Из доказанных выше утверждений следует, что этот R-фактор не зависит от того, какая именно норма была использована в его определении; кроме того, с равным yспехом он мог быть определен через последовательность

Теперь мы можем определить R-порядок итерационной про­цедуры I как

(6)

Это определение применительно к последовательностям векторов из предложили Ортега и Рейнбольдт.

Приведем несколько утверждений, касающихся вычисления (и оценивания) R-порядка.

Теорема 2. Пусть 1 — итерационная процедура с пределом и пусть— множество всех порожденных процедурой I

последовательностей, для которых

k ≥ 0. Если существует t≥= 1 и константа γ2 такая что для всех из и нормывыполнено

либо

то R-порядок процедуры I удовлетворяет неравенству

С другой стороны, если существуют положительная константа и последовательностьиз такие что

либо

то R-порядок процедуры I удовлетворяет неравенству

Если с некоторыми константамии выполнены оба указан­ных условия, то

Доказательство этой теоремы строится аналогично соответ­ствующему доказательству у Ортеги и Рейнбольдта.

Теорема 3. Пусть I — итерационная процедура с пределом и пусть — множество всех порожденных I последовательностей, для которых

Пусть

где все mі — целые неотрицательные числа. Тогда,

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

либо

то R-порядок процедуры I удовлетворяет неравенству

где s — единственное положительное решение уравнения

Часто оказывается возможным проверить какое-либо из при­веденных в теоремах 2 и 3 неравенств и тем самым получить оценку R - порядка на данной итерации.

Сделанные в этом приложении утверждения могут быть пе­ренесены на случай В частности, останутся спра­ведливыми лемма 1 и теорема 2 и 3.

Приложение В

РЕАЛИЗАЦИЯ МАШИННОЙ ИНТЕРВАЛЬНОЙ АРИФМЕТИКИ НА АЛГОЛЕ 60

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

Формулы (2 п.7.1) и определение 1из микромодуля 25 задают рамки, в которых реализуются машинные интервальные операции:

логическую часть, определяющую порядок вычисления гра­ниц результата по формулам (2 п.7.1), и арифметическую часть, в которой пара границ результирую­щего интервала вычисляется при помощи арифметических операций с направленными округлениями (см. например формулы (8 из микромодуля 25) и (9 из микромодуля 25)).

Первая часть может быть без труда описана на Алголе 60 и не нуждается поэтому в более подробном объяснении. Вторая часть, однако, требует больших усилий, поскольку в реализациях Алгола 60 направленные округления обычно не доступны. По­этому займемся моделированием машинной арифме­тики, целиком основанной на использовании направленного округления вниз (↓). Соответствующая процедура LOW будет определена через обычные машинные операции. При употребле­нии знака * для обозначения машинных операций предполага­ется выполнение установленных в микромодуле 25 соглашений. В частности, считается, что

(а) множество машинных чисел Rm симметрично относи­тельно нуля и состоит из нормализованных чисел с плавающей точкой, т. е имеющих вид

где т — мантисса, b — основание степени, е — порядок;

(б) все арифметические операции с плавающей точкой опти­мальны, т. е. результат вещественной операции округляется с по­мощью отображения fl, обладающего свойством (3 из микромодуля 25) (см (9 из микромодуля 25)).

Как было указано в микромодулe 25, направленное округление вверх ↑ получается из ↓ по формуле (5 из микромодуля 25). Эта формула сохраняет силу и для машинных операций:

Здесь ↓ обозначает результат выполнения процедуры LOW, a *— машинную операцию

Запишем теперь процедуру LOW на Алголе 60. Эта про­цедура позволяет вычислить нижнюю границу вещественного результата операции над числами с плавающей точкой. Ее заго­ловок выглядит так:

'REAL"PROCEDURE'LOW(X);

'VALUE'X; 'REAL'X;

Каким будет тело процедуры, зависит от некоторых особенно­стей машинной арифметики. К их числу относятся

(I) тип округления fl, используемого для перехода от ве­щественных операций к операциям с плавающей точкой. Мы различаем