Анализ точности вычислительных процессов

2. Анализ точности вычислительных процессов.

2.2.1.  Общая формула для оценки главной части погрешности.

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

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

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

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

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

Пусть А и а - два "близких" числа; условимся считать А точным, а — приближенным.

Величина называется абсолютной погрешностью при­ближенного числа а, а его относительной погрешностью.

Числа Δa и δа такие, что Δa > Δа и δа = a, называются оценками или границами абсолютной и относительной погрешностей соответствен­но (к Δa и δа часто применяют также термин "предельные погрешно­сти"). Так как обычно истинные погрешности не известны, то там, где не может возникнуть недоразумений, будем иногда называть Δa и δа просто абсолютной и относительной погрешностями.

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

, а точная абсолютная погрешность результата есть

- модуль полного приращения функции. Главной, т. е. линейной частью этого приращения является, как известно, полный дифференциал du . Та­ким образом, имеем:

, (2.1)

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

(2.2)

Отсюда легко получается формула приближенной оценки относительной погрешности значения u:

(2.3)

Как частные случаи формул (2.2), (2.3) (точных для функций, линей­ных относительно xi, или lnxi соответственно) можно получить известные правила оценивания погрешностей результатов арифметических действий [1].

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

Пусть теперь , где можно считать все сомножители положительными. Так как и , то, согласно (2.3),

. (2.4)

Если же , то и, значит

. (2.5)

Последнее вместе с (2.4) означает известный результат о сложении пре­дельных относительных погрешностей при умножении и делении прибли­женных чисел.

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

,

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

С вычитанием приближённых чисел дело обстоит хуже: оценка

относительной погрешности разности x1 - х2 двух приближенных поло­жительных чисел указывает на возможность сильного возрастания по­грешности при x1 - х2 → 0. В этом случае говорят о потере точности при вычитании близких чисел.

2.2.2.  Статистический и технический подходы к учёту погрешности действий.

Рассмотренный выше аналитический (или классический) способ учета погрешностей действий, предполагающий точное оценивание по­грешностей, основанное либо на приведенных в предыдущем параграфе правилах подсчета погрешностей арифметических действий, либо на па­раллельной работе с верхними и нижними границами исходных данных, имеет два существенных недостатка. Во-первых, этот способ чрезвычайно громоздок и не может быть рекомендован при массовых вычислениях. Во-вторых, он учитывает крайние, наихудшие случаи взаимодействия погреш­ностей, которые допустимы, но маловероятны. Ясно, что, например, при суммировании нескольких приближенных чисел (полученных в результате измерений, округлений или каким-либо другим путем) среди них почти на­верное будут слагаемые как с избытком, так и с недостатком, т. е. произойдёт частичная компенсация погрешностей. При больших количествах од­нотипных вычислений вступают в силу уже вероятностные или стати­стические законы формирования погрешностей результатов действий. Например, методами теории вероятностей показывается, что математиче­ское ожидание абсолютной погрешности суммы n слагаемых с одинако­вым уровнем абсолютных погрешностей, при достаточно большом n, про­порционально √n. В частности, если n>10 и все слагаемые округлены до m-го десятичного разряда, то для подсчета абсолютной по­грешности суммы 5 применяют правило Чеботарева .

(2.6)

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

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

,

т. е. такая же, как и у исходных данных. В тоже время по формуле (2.6) имеем

.

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

2.2.3.  Графы вычислительных процессов.

Рассмотрим более удобный способ подсчёта распространения ошибки в каком-либо арифметическом вычислении.

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

На рис. 2.1 изображен граф вычи­слительного процесса u = (х + у)*z. Граф следует читать снизу вверх, следуя стрелкам. Сначала выполняются операции, расположенные на каком-либо горизонтальном уровне, после этого — операции, расположенные на более высоком уровне, и т. д. Из рис. 2.1, например, ясно, что x и у сна­чала складываются, а потом умножаются на z. Граф, изображенный на рис. 2.1, является только изображением самого вычислительного процесса. Для подсчета общей ошибки результата необходимо дополнить этот граф коэффициентами, которые пишутся около стрелок согласно следующим правилам.

Рис. 2.1. Граф вычислительного процесса u = (х + у)*z.

Сложение

Пусть две стрелки, которые входят в кружок сложения, выходят из двух кружков с величинами a1 и а2. Эти величины могут быть как исходными, так и результатами предыдущих вычислений. Тогда стрелка, ведущая от a1 к знаку + в кружке, получает коэффициент a1/(a1 + a2) стрелка же, ведущая от a2 к знаку + в кружке, получает коэффициент a2/(a1 + a2).

Вычитание

Если выполняется операция al — a2, то соответствующие стрелки получают коэффициенты a1/(a1 - a2) a1/(a1 - a2).

Умножение

Обе стрелки, входящие в кружок умножения, получают коэффициент +1.

Деление

Если выполняется деление a1/a2, то стрелка от a1 к косой черте в кружке получает коэффициент +1, а стрелка от a2 к косой черте в кружке получает коэффициент -1.

Смысл всех этих коэффициентов следующий: относительная ошибка результата любой операции (круж­ка) входит в результат следующей операции, умножаясь на коэффи­циент у стрелки, соединяющей эти две операции.

В качестве примера можно рас­смотреть рис. 2.2, который отли­чается от 2.1 только тем, что около стрелок расставлены соответствую­щие коэффициенты.

Предположим, что три исход­ные величины на рис. 2.1 имеют относительные ошибки округления, равные соответственно ix, iy и iz, и посмотрим, как применяется пра­вило подсчета ошибки. Сначала рассмотрим сложение. Относитель­ная ошибка величины х составля­ет ix; эта ошибка войдет в резуль­тат следующей операции (сложе­ния) умноженной на коэффициент у стрелки, соединяю­щей х в кружке со знаком + в кружке:

Рис. 2.2. Граф вычи­слительного процесса

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

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

.

Теперь можно применить то же правило к умножению. Один из сомножителей есть сумма х и у, ошибку которой мы только что вычислили; эта ошибка, согласно изложен­ным выше правилам, войдет в результат умножения умноженной на +1. Относительная ошибка сомножителя z, равная iz, также войдет в результат умножения умноженной на +1. При выполнении операции умножения появляется ошибка округления, равная r2. Полная ошибка результата операции умножения выразится следующим образом:

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

Если х и у оба неотрицательны, то сумма

не может быть больше 1, и окончательно мы имеем [6]

(2.7)