1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 4
Текст из файла (страница 4)
С одной стороны, это вызваноособенностями физической реализации современных ЭВМ, где 0 соответствует отсутствию сигнала (заряда и т. п.), а 1 — его наличию. Сдругой стороны, двоичная система оказывается выгодной при выполнении с ней приближённых вычислений (см. [26]).R✲Рис. 1.1. Множество чисел, представимых в цифровой ЭВМ— дискретное конечное подмножество вещественной оси R.Как видим, числа с плавающей точкой обеспечивают практическификсированную относительную погрешность представления вещественных чисел и изменяющуюся абсолютную погрешность.Стандарты IEEE 754/854 предусматривают для чисел с плавающейточкой «одинарную точность» и «двойную точность», а также «расширенные» варианты этих представлений.
При этом для хранения чиселодинарной точности отводится 4 байта памяти ЭВМ, для двойной точности — 8 байтов. Из этих 32 или 64 битов один бит зарезервировандля указания знака числа: 0 соответствует «−», а 1 соответствует «+».Таким образом, во внутреннем «машинном» представлении знак присутствует у любого числа, в том числе и у нуля.Для двойной точности, наиболее широко распространённой в современных расчётах (она обозначается, как правило, ключевым словомdouble), диапазоп чисел, представимых в ЭВМ простирается от примерно 2.22 · 10−308 до 1.79 · 10308 .
Помимо обычных чисел стандарты IEEE754/854 описывают несколько специальных объектов вычислений. Это,201. Введениепрежде всего, машинная бесконечность и специальный нечисловой объект под названием NaN (названный как сокращение английской фразы«Not a Number»). NaN полезен во многих ситуациях, в частности, онможет использоваться для сигнализации о нетипичных и исключительных событиях, случившихся в процессе вычислений, которые, тем неменее, нельзя было прерывать.Очень важной характеристикой множества машинных чисел является так называемое «машинное ε» (машинное эпсилон), которое характеризует густоту множества машинно-представимых чисел.
Это наименьшее положительное число εмаш , такое что в компьютерной арифметике 1 + εмаш 6= 1 при округлении к ближайшему. Из конструкции чисел с плавающей точкой следует тогда, что компьютер, грубоговоря, не будет различать чисел a и b, удовлетворяющих условию1 < a/b < 1 + εмаш . Для двойной точности представления в стандартеIEEE 754/854 машинное эпсилон примерно равно 1.11 · 10−16 .Принципиальной особенностью компьютерной арифметики, вызванной дискретностью множества машинных чисел и наличием округлений, является невыполнение некоторых общеизвестных свойств вещественной арифметики. Например, сложение чисел с плавающей точкойнеассоциативно, т. е.
в общем случае неверно, что(a + b) + c = a + (b + c).Читатель может проверить на любом компьютере, что в арифметикеIEEE 754/854 двойной точности при округлении «к ближайшему»1 + 1.1·10−16 + 1.1·10−16 6= 1 + 1.1·10−16 + 1.1·10−16 .Левая часть этого отношения равна 1, тогда как правая — ближайшемук единице справа машинно-представимому числу. Эта ситуация имеетместо в любых приближённых вычислениях, которые сопровождаютсяокруглениями, а не только при расчётах на современных цифровыхЭВМ.Из отсутствия ассоциативности следует, что результат суммирования длинных сумм вида x1 + x2 + .
. .+ xn зависит от порядка, в которомвыполняется попарное суммирование слагаемых, или, как говорят, отрасстановки скобок в сумме. Каким образом следует организовыватьтакое суммирование в компьютерной арифметике, чтобы получать наиболее точные результаты? Ответ на этот вопрос существенно зависитот значений слагаемых, но в случае суммирования уменьшающихся по1.3. Обусловленность математических задач21абсолютной величине величин суммировать нужно «с конца». Именнотак, к примеру, лучше всего находить суммы большинства рядов.1.3Обусловленность математических задачВынесенный в заголовок этого параграфа термин — обусловленность — означает меру чувствительности решения задачи к изменениям (возмущениям) её входных данных. Ясно, что любая информацияподобного сорта чрезвычайно важна при практических вычислениях,так как позволяет оценивать достоверность результатов, полученных вусловиях приближённого характера этих вычислений.
С другой стороны, зная о высокой чувствительности решения мы можем предпринимать необходимые меры для компенсации этого явления — повышатьразрядность вычислений, наконец, модифицировать или вообще сменить выбранный вычислительный алгоритм и т. п.Существует несколько уровней рассмотрения поставленного вопроса. Во-первых, следует знать, является ли вообще непрерывной зависимость решения задачи от входных данных. Задачи, решение которых независит непрерывно от их данных, называют некорректными .
Далее в§2.8г в качестве примера таких задач мы рассмотрим задачу численного дифференцирования. Во-вторых, в случае наличия этой непрерывности желательно иметь некоторую количественную меру чувствительности решения как функции от входных данных.Переходя к формальным конструкциям, предположим, что в рассматриваемой задаче по значениям из множества D входных данныхмы должны вычислить решение задачи из множества ответов S. Отображение φ : D → S, сопоставляющее всякому a из D решение задачииз S, мы будем называть разрешающим отображением (или разрешающим оператором). Отображение φ может быть выписано явнымобразом, если ответ к задаче задаётся каким-либо выражением.
Часторазрешающее отображение задаётся неявно, как, например, при решении системы уравненийF (a, x) = 0с входными параметрами a. Даже при неявном задании нередко можно теоретически выписать вид разрешающего отображения, как, например, x = A−1 b при решении системы линейных уравнений Ax = b сквадратной матрицей A. Но в любом случае удобно предполагать существование этого отображения и некоторые его свойства. Пусть также D221. Введениеи S являются линейными нормированными пространствами. Очевидно, что самый первый вопрос, касающийся обусловленности задачи,требует, чтобы разрешающее отображение φ было непрерывным относительно некоторого задания норм в D и S.Что касается числовой меры обусловленности математических задач, то существуют два подхода к её введению.
Одни из них условноможет быть назван дифференциальным, а другой основан на оценивании константы Липшица разрешающего оператора.Пусть разрешающее отображение дифференцируемо по крайней мере в интересующей нас точке a из множества входных данных D. Тогдаможно считать, чтоφ(a + ∆a) ≈ φ(a) + φ′ (a) · ∆a,и потому мерой чувствительности решения может служить kφ′ (a)k.Для более детального описания зависимости различных компонент решения φ(a) от a часто привлекают отдельные частные производные∂φi′∂aj , т.
е. элементы матрицы Якоби φ (a) разрешающего отображенияφ, которые при этом называют коэффициентами чувствительности.Интересна также мера относительной чувствительности решения, которую можно извлечь из соотношения ′φ (a)∆aφ(a + ∆a) − φ(a)≈· kak.kφ(a)kkφ(a)kkakВторой подход к определению обусловленности требует нахождениякак можно более точных констант C1 и C2 в неравенствахиkφ(a + ∆a) − φ(a)k ≤ C1 k∆ak(1.6)k∆akkφ(a + ∆a) − φ(a)k≤ C2.kφ(a)kkak(1.7)|f (x′ ) − f (x′′ )| ≤ L · dist (x′ , x′′ )(1.8)Величины этих констант, зависящие от задачи, а иногда и конкретныхвходных данных, берутся за меру обусловленности решения задачи.В связи с неравенствами (1.6)–(1.7) напомним, что вещественнаяфункция f : Rn ⊇ D → R называется непрерывной по Липшицу (илипросто липшицевой), если существует такая константа L, что1.4. Устойчивость алгоритмов23√Рис. 1.2. Непрерывная функция y = x имеет бесконечнуюскорость роста при x = 0 и не является липшицевойдля любых x′ , x′′ ∈ D.
Величину L называют при этом константой Липшица функции f на D. Понятие непрерывности по Липшицу формализует интуитивно понятное условие соразмерности изменения функции изменению аргумента. Именно, приращение функции не должнопревосходить приращение аргумента (по абсолютной величине или внекоторой заданной метрике) более чем в определённое фиксированное число раз. При этом сама функция может быть и негладкой, как,например, модуль числа в окрестности нуля. Отметим, что понятиенепрерывности по Липшицу является более сильным свойством, чемпросто непрерывность или даже равномерная непрерывность, так каквлечёт за собой их обоих.Нетрудно видеть, что искомые константы C1 и C2 в неравенствах(1.6) и (1.7), характеризующие чувствительность решения задачи поотношению к возмущениям входных данных — это не что иное, какконстанты Липшица для разрешающего отображения φ и произведениеконстанты Липшица Lψ отображения ψ : D → S, действующего поправилу a 7→ φ(a)/kφ(a)k на норму kak.
В последнем случаеkφ(a + ∆a) − φ(a)kk∆ak/ Lψ k∆ak ≤ Lψ kak ·.kφ(a)kkak1.4Устойчивость алгоритмовС понятием обусловленности математических задач тесно связанопонятие устойчивости алгоритмов для их решения.Устойчивость численного алгоритма — это мера чувствительности241. Введениеполучаемых с его помощью результатов в зависимости от возмущенийвходных данных. Устойчивый алгоритм характеризауется низкой чувствительностью к возмущениям и погрешностям в данных, подаваемыхему на вход, тогда как у неустойчивого алгоритма эта чувствительностьвысока.Если обусловленность задачи характеризует объективный факт, касающийся самой постановки задачи, то устойчивость алгоритма — этосвойство сконструированной и применяемой нами процедуры для решения этой задачи.
Как следствие, в нашей власти стремиться сделатьэту устойчивость наилучшей.Для количественной характеризации устойчивости можно использовать те же идеи, что и при введение количественной меры обусловленности.Ясно, что для хорошо обусловленных задач наилучшими являютсяустойчивые алгоритмы. Но другая естественная мысль, что для решения плохо обусловленных задач алгоритмы не могут быть лучше самих задач, которые они решают, является верной лишь отчасти. Иногда устойчивые алгоритмы стремятся построить и для плохо обусловленных задач, так как именно такие задачи получаются как наиболееподходящие модели тех или иных явлений (другие модели часто нампросто недоступны). В этом случае говорят, что устойчивый алгоритмрегуляризует исходную плохо обусловленную задачу.1.5Интервальная арифметикаИсходной идеей создания интервальной арифметики является наблюдение о том, что всё в нашем мире неточно, и нам в реальностичаще всего приходится работать не с точными значениями величин,которые образуют основу классической «идеальной» математики, а сцелыми диапазонами значений той или иной величины.
Например, множество вещественных чисел, которые точно представляются в цифровых ЭВМ, конечно, и из-за присутствия округления каждое из этихчисел, в действительности, является представителем целого интервалазначений обычной вещественной оси R (см. Рис. 1.5–1.6).Нельзя ли организовать операции и отношения между диапазонамиинтервалами так, как это сделано для обычных точных значений? Стем, чтобы можно было работать с ними, подобно обычным числам,опираясь на алгебраические преобразования, аналитические операции251.5.
Интервальная арифметикаи т.п.? Ответ на эти вопросы положителен, хотя свойства получающейся «интервальной арифметики» оказываются во многом непохожимина привычные свойства операций с обычными числами.Предположим, что нам даны переменные a и b, точные значениякоторых неизвестны, но мы знаем, что они могут находиться в интервалах [a, a] и [b, b] соответственно. Что можно сказать о значении суммыa + b?Складывая почленно неравенстваa ≤ a ≤ a,b ≤ b ≤ b,получимa + b ≤ a + b ≤ a + b,так что a + b ∈ a + b, a + b .На аналогичный вопрос, связанный с областью значений разностиa − b можно ответить, складывая почленно неравенстваa ≤a ≤a,−b ≤ −b ≤ −b.Имеем в результате a − b ∈ a − b, a − b .Для умножения двух переменных a ∈ [a, a] и b ∈ [b, b] имеет местонесколько более сложная оценкаa · b ∈ min{a b, a b, a b, a b}, max{a b, a b, a b, a b} .Чтобы доказать её заметим, что функция φ : R × R → R, задаваемаяправилом φ(a, b) = a · b, будучи линейной по b при каждом фиксированном a, принимает минимальное и максимальное значения на концахинтервала изменения переменной b.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
