1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 6
Текст из файла (страница 6)
Интервальные расширения функций33то интервальная оценка производной на заданном интервале областиопределения есть 1 11,4= 162([1, 3] + 1)Поэтому если в качестве центра разложения взять середину интервалаmid x = 2, то 1 1, 4 · [−1, 1]f (mid x) + f ′ (x) (x − mid x) = 32 + 16 5 11 = 23 + − 41 , 14 = 12, 12 .Как видим, этот результат значительно точнее естественного интервального расширения (1.20).За дальнейшей информацией мы отсылаем заинтересованного читателя к книгам [1, 24, 28, 29], развёрнуто излагающим построениеинтервальных расширений функций. Важно отметить, что точностьинтервального оценивания при использовании любой из форм интервального расширения критическим образом зависит от ширины брусаоценивания. Если обозначить через f (x) точную область значений целевой функции на x, т. е.
f (x) = { f (x) | x ∈ x }, то для естественногоинтервального расширения липшицевых функций имеет место неравенствоdist f ♮ (x), f (x) ≤ C kwid xk(1.21)с некоторой константой C, и этот факт обычно выражают словами«естественное интервальное расширение имеет первый порядок точности». Для центрированной формы верно соотношениеdist fc (x, x̃), f (x) ≤ 2 (wid g(x, x̃))⊤ | x − x̃ |,(1.22)где g(x, x̃) = ( g 1 (x, x̃), g 2 (x, x̃), . . .
, g n (x, x̃) ). В случае, когда интервальные оценки для функций g i (x, x̃) находятся с первым порядкомточности, общий порядок точности центрированной формы согласно(1.22) будет уже вторым. Вывод этих оценок заинтересованный читатель может найти, к примеру, в [24, 29].Интервальные оценки областей значений функций, которые находятся с помощью интервальных расширений, оказываются полезными в самых различных вопросах вычислительной математики. В частности, с помощью интервального языка очень элегантно записываются остаточные члены различных приближённых формул. В качестве341.
Введениедвух содержательных примеров применения интервальных расширений функций мы рассмотрим решение уравнений и оценку константыЛипшица для функций.1.7Элементы конструктивной математики«Конструктивная математика» — это неформальное название тойчасти современной математики, тех математических дисциплин, — теории алгоритмов, теории сложности вычислений, и ряда других — вкоторых главным объектом изучения являются процессы построениятех или иных математических объектов. Оформление конструктивнойматематики в отдельную ветвь общего математического дерева произошло на рубеже XIX и XX веков под влиянием обнаруженных к томувремени парадоксов теории множеств.
Эти парадоксы заставили критически переосмыслить существовавшие в математике способы рассуждений и само понятие «существования» для математических объектов.Создание основ конструктивного направления в математике связано,прежде всего, с деятельностью Л.Э.Я. Брауэра и развиваемым им «интуиционизмом».В частности, теория алгоритмов и рекурсивных функций — это математическая дисциплина, исследующая конструктивные свойства различных математических объектов. Её основные понятия — это алгоритм, конструктивный объект, вычислимость, разрешимость и др.Алгоритм — это конечная последовательность инструкций, записанных на некотором языке и определяющих процесс переработки исходных данных в искомые результаты (ответ решаемой задачи и т.п.).Алгоритм принципиально конечен и определяет собой конечный процесс. Далее, конструктивным объектом называется объект, которыйможет быть построен с помощью некоторой конечной последовательности действий над каким-то конечным алфавитом.
Таковы, например,рациональные числа. Строго говоря, конструктивные объекты и только они могут быть получены в качестве ответов при решении задачина реальных цифровых ЭВМ с конечными быстродействием и объёмомпамяти.В частности, конечными машинами являются широко распространенные ныне электронные цифровые вычислительные машины: ониспособны представлять, по сути дела, только конечные множества чисел. Таким образом, обречены на неудачу любые попытки использо-1.7.
Элементы конструктивной математики35вать их для выполнения арифметических абсолютно точных операцийнад числовыми полями R и C, которые являются бесконечными (и даже непрерывными) множествами, большинство элементов которых непредставимы в цифровых ЭВМ.Оказывается, что значительная часть объектов, с которыми работают современная математика и её приложения, не являются конструктивными.
В частности, неконструктивным является традиционное понятие вещественного числа, подразумевающее бесконечную процедуруопределения всех знаков его десятичного разложения (которое в общемслучае непериодично). Факт неконструктивности вещественных чиселможет быть обоснован строго математически (см. [32]), и он указываетна принципиальные границы возможностей алгоритмического подходаи ЭВМ в деле решения задач математического анализа.Тем не менее, и в этом океане неконструктивности имеет смысл выделить объекты, которые могут быть «достаточно хорошо» приближены конструктивными объектами.
На этом пути мы приходим к понятию вычислимого вещественного числа [22, 32]4 : вещественное число αназывается вычислимым, если существует алгоритм, дающий по всякому натуральному числу n рациональное приближение к α с погрешностью n1 . Множество всех вычислимых вещественных чисел образуетвычислимый континуум. Соответственно, вычислимая вещественнаяфункция определяется как отображение из вычислимого континуума ввычислимый континуум, задаваемая алгоритмом преобразования программы аргумента в программу значений.Важно помнить, что и вычислимое вещественное число, и вычислимая функция — это уже не конструктивные объекты. Но, как выясняется, даже ценой ослабления наших требований к конструктивностинельзя вполне преодолеть принципиальные алгоритмические трудности, связанные с задачей решения уравнений.
Для вычислимых вещественных чисел и функций ряд традиционных постановок задач оказывается алгоритмически неразрешимыми в том смысле, что построениеобщих алгоритмов их решения принципиально невозможно.Например, алгоритмически неразрешимыми являются задачи1) распознавания равно нулю или нет произвольное вычислимое вещественного число [31, 32, 33], распознавания равенства двух вычислимых вещественных чисел [22, 25, 31, 32];4 Совершенно аналогичным является определение конструктивного вещественного числа у Б.А. Кушнера [31].361. Введение2) нахождения для каждой совместной системы линейных уравнений над полем конструктивных вещественных чисел какого-либоее решения [31, 33];3) нахождения нулей всякой непрерывной кусочно-линейной знакопеременной функции [33].Приведённые выше результаты задают, как нам представляется, туабсолютную и совершенно объективную мерку (в отличие от субъективных пристрастий), с которой мы должны подходить к оценке трудоёмкости тех или иных вычислительных методов.
Получается, чтонеобходимость переформулировки задачи решения уравнений и системуравнений связана ещё и с тем, что в традиционной постановке этизадачи оказываются алгоритмически неразрешимыми! На фоне этогомрачного факта наличие даже экспоненциально трудного алгоритма снебольшим основанием «одноэтажной» экспоненты в оценке сложности(вроде 2n ) можно рассматривать как вполне приемлемый вариант разрешимости задачи.
Именно это имеет место в ситуации с вычислениемвращения векторного поля (степени отображения).Вычислительная математика тесно примыкает к конструктивной,хотя их цели и методы существенно разнятся.1.8Сложность задачи трудоёмкость алгоритмовКак правило, нас удовлетворит не всякий процесс решения поставленной задачи, а лишь только тот, который выполним за практическиприемлемое время.
Соответственно, помимо алгоритмической разрешимости задач огромную роль играет трудоёмкость тех или иных алгоритмов для их решения.Например, множество вещественных чисел, точно представимых вцифровых ЭВМ в формате «с плавающей точкой» согласно стандартуIEEE 754/854, является конечным, и потому мы можем найти, скажем,приближённые значения корней полинома (или убедиться в их отсутствии) за конечное время, просто перебрав все эти машинные числа ивычисляя в них значения полинома.
Но, будучи принципиально выполнимым, такой алгоритм требует непомерных вычислительных затрат идля практики бесполезен.1.8. Сложность задач и трудоёмкость алгоритмов37Естественно измерять трудоёмкость алгоритма количеством «элементарных операций», требуемых для его исполнения. Следует лишьиметь в виду, что эти операции могут быть весьма различными. Скажем, сложение и умножение двух чисел «с плавающей точкой» требуютдля своего выполнения разного количества тактов современных процессоров и, соответственно, разного времени. До определённой степениэти различия можно игнорировать и оперировать понятием усреднённой арифметической операции.Большую роль играет также объём данных, подавамых на вход алгоритма.
К примеру, входными данными могут быть небольшие целыечисла, а могут и рациональные дроби с внушительными числителями и знаменателями. Ясно, что переработка бо́льших объёмов данныхдолжна потребовать бо́льших трудозатрат от алгоритма, так что имеетсмысл сложность исполнения алгоритма в каждом конкретном случаеотносить к сложности представления входных данных алгоритма.5На качественном уровне полезно различать полиномиальную трудоёмкость и экспоненциальную трудоёмкость. Говорят, что некоторый алгоритм имеет полиномиальную трудоёмкость, если сложностьего выполнения не превосходит значений некоторого полинома от длины входных данных. Напротив, про некоторый алгоритм говорят, чтоон имеет экспоненциальную трудоёмкость, если сложность его выполнения превосходит значения любого полинома от длины подаваемыхему на вход данных.Получение оценок трудоёмкости задач является непростым делом.Если какой-то алгоритм решает поставленную задачу, то, очевидно,его трудоёмкость может служить верхней оценкой сложности решенияэтой задачи.
Но вот получение нижних оценок сложности решения задач является чрезвычайно трудным. В явном виде такие нижние оценки найдены лишь для очень небольшого круга задач, которые имеют,скорее, теоретическое значение. В этих условиях широкое распространение получила альтернативная теория сложности, в основе которойлежат понятие сводимости задач друг к другу и вытекающее из негопонятие эквивалентности задач по трудоёмкости.Наибольшее распространение получило полиномиальное сведениеодних задач к другим, под которым понимается такое преобразованиеодной задачи к другой, что данные и ответ исходной задачи перево5 В связи с этим получили распространение также относительные единицы измерения трудоёмкости алгоритмов — через количество вычислений функции, правойчасти уравнения и т. п.381. Введениедятся в данные и ответ для другой, а трудоёмкость этого преобразования не превышает значений некоторого полинома от размера исходнойзадачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
