Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 14
Текст из файла (страница 14)
Чем меньше величина Р о' = о(к~о~)/2, тем быстрее будет сходиться метод. Практическая реализация итерационных методов всегда связана с необходимостью выбора критерия окончания итерационного процесса. Вычисления не могут продолжаться бесконечно долго и должны быть прерваны в соответствии с некоторым критерием, связанным, например, с достижением заданной точности. Использование для этой цели априорных оценок чаще всего оказывается невозможным или неэффективным. Качественно верно описывая поведение метода, такие оценки являются завышенными и дают весьма недостоверную количественную информацию. Нередко априорные оценки содержат неизвестные вели- 1 От лат. а'рг1оп — "до опыта".
б1 к'о' > 4 а. Известно, что тогда х' и' >,Га для всех п ~ 0 и погрешности двух последовательных приближений связаны следующим неравен- ством: чины (например, в оценках (3.14), (3.15) содержится величина 4 а), либо предполагают наличие и серьезное использование некоторой дополнительной информации о решении. Чаще всего такой информации нет, а ее получение связано с необходимостью решения дополнительных задач, нередко более сложных, чем исходная. Для формирования критерия окончания по достижении заданной точности, как правило, используют так называемые апостериорныд оценки погрешности — неравенства, в которых величина погрешности оценивается через известные или получаемые в ходе вычислительного процесса величины. Хотя такими оценками нельзя воспользоваться до начала вычислений, в ходе вычислительного процесса они позволяют давать конкретную количественную оценку погрешности. Например, для метода Ньютона (3.13) справедлива следующая апостериорная оценка: (х(п) — ~а~ ~ ~)т(п) — т(о 1) ~ и ) )1, позволяющая оценивать абсолютную погрешность приближения через модуль разности двух последовательных приближений.
Она дает воз- можность сформулировать при заданной точности е > 0 очень простой критерий окончания. Как только окажется выполненным неравенство (3.16) ( т(а) — т(а () ! Пример 3.21. Если значение ~2 требуется найти с точностью в = 10 5, то неравенство (3,16), как видно из приведенных в примере 3.20 вычислений, будет выполнено при )( = 4. Так как ~ т(4) —,т(з) ! = 3 10 (), то с учетом погрешности округления можно записать результат: (2 = 1.41421 -" 0.00001.
5. Методы статистических испытаний (методы Монте — Карло). Это— численные методы, основанные на моделировании случайных величин и построении статистических оценок решений задач. Этот класс методов, как принято считать, возник в 1949 г., когда Дж. фон Нейман2 и ' От лат. а'розог)ог1 — "после опыта".
Джон фон Нейман (1903 — 1957) — американский математик, физик, инженер-изобретатель. Оказал значительное влияние на развитие современной математики. Один из создателей первых ЭВМ. 02 вычисления следует прекратить и принять х( ") за приближение к 4 а с точностью к. С.Улам' использовали случайные числа для моделирования с помощью ЭВМ поведения нейтронов в ядерном реакторе. Эти методы могут оказаться незаменимыми при моделировании больших систем, но подробное их изложение предполагает существенное использование аппарата теории вероятностей и математической статистики и выходит за рамки данной книги.
$ 3.4. Корректность вычислительных алгоритмов 1. Вычислительный алгоритм. Вычислительный метод, доведенный / до степени детализации, позволяющий реализовать его на ЭВМ, принимает форму вычислительного алгоритма. Определим оычислительный ал~оритл/ как точное предписание действий над входными данными, задающее вычислительный процесс, направленный на преобразование произвольных входных данных х (из множества допустимых для данного алгоритма входных данных Х) в полностью определяемый этими входными данными результат. Реальный вычислительный алгоритм складывается из двух частей: абстрактного оычислительноьо альорит/аа, формулируемого в общепринятых математических терминах, и нроьра и иы, записанной на одном из алгоритмических языков и предназначенной для реализации алгоритма на ЭВМ.
Как правило, в руководствах по методам вычислений излагаются именно абстрактные алгоритмы, но их обсуждение проводится так, чтобы выявить особенности алгоритмов, которые оказывают существенное влияние на качество программной реализации. 2. Определение корректности алгоритма. К вычислительным алгоритмам, предназначенным для широкого использования, предъявляется ряд весьма жестких требований.
Первое из них — корректность алгоритма. Будем называть вычислительный алгоритм корректны и, если выполнены три условия: 1) он позволяет после выполнения коночного числа элементарных для вычислительной машины операций преобразовать любое входное данное аЕХ в результат у; 2) результат у устойчив по отношению к малым возмущениям входных данных; 3) Результат у обладает вычислительной устойчивостью. Если хотя бы одно из перечисленных условий не выполнено, то будем называть алгоритм некорректны./а. Уточним и более подробно обсудим эти условия, Станислав Улам (1909 — 1984) — американский математик.
Необходимость выполнения первого условия понятна. Если для получения результата нужно выполнить бесконечное число операций либо требуются операции, не реализованные на ЭВМ, то алгоритм следует признать некорректным. Пример 3.22. Известный алгоритм деления чисел "углом" некорректен, так как он может продолжаться бесконечно, если не определен критерий окончания вычислений. Пример 3.23. Отсутствие критерия окончания делает некорректным и алгоритм Ньютона вычисления 4 а (см, пример 3.20).
Пример 3.24. Алгоритм вычисления корней квадратного уравнения (3.1) пэ формулам (3. 2) некорректен, если он предназначен для использования на вычислительной машине, на которой нс реализована операция извлечения квадратного корня.
3. Устойчивость по входным данным. Устойчивость результата у к малым возмущениям входных данных (устойчивость ио входим.в дакямл~) означает, что результат непрерывным образом зависит от входных данных при условии, что отсутствует вычислительная погрешность. Это требование устойчивости аналогично требованию устойчивости вычислительной задачи. Отсутствие такой устойчивости делает алгоритм непригодным для использования на практике. Отметим, что в формулировку устойчивости алгоритма па входным данным неявно входит одно весьма важное предположение, а именно, что вместе с входным данным т в множество допустимых входных данных Х входят и все близкие к т приближенные входные данные х*.
Пример З.Ю. Пусть алгоритм предназначен для вычисления корней квадратного уравнения (3.1) с коэффициентом, удовлетворяющими условию = Р— 4с ~ ~0. Если в нем используются формулы (3.2), то этот алгоритм некорректен. В самом деле, значение Ы*, отвечающее приближенно заданным к<хзффициентам 6* и с*, может оказаться отрицательным, если Н ~ 0.
Тогда вычисления завершатся аварийным остановом при попытке извлечь квадратный корень из отрицательного числа. Если же в формуле (3.2) заменить а на тпах 1а, 0), то алгоритм становится корректным. 4. Вычислительная устойчивость. Из-за наличия ошибок округления при вводе входных данных в ЭВМ и при выполнении арифметических операций неизбежно появление вычислительной погрешности. Ее величина на разных ЭВМ различна из-за различий в разрядности и способах округления, но для фиксированного алгоритма в основном величина погрешности определяется машинной точностью ем. 64 Назовем алгоритм еыиислитпельно успьойииеыи, если вычислительная погрешность результата стремится к нулю при е„~ О. Обычно вычислительный алгоритм называют устойчивы и, если он устойчив по входным данным и вычислительно устойчив, и иеустойчиоыл, если хотя бы одно из этих условий не выгюлнено.
Пример 3.26~. Пусть требуется составить таблицу значений интегралов 1 1„= ~ х"е~ Ят для и = 1, 2, ... на 6-разрядной десятичной ЭВМ. о Интегрируя по частям, имеем 1 1 1 1 1~ = / "й(- ' ) = — ~ ! + Ге~- д(хи) = — 1 + ) лх" ~е~ ~1л о о о о Следовательно, справедлива формула 1 = ПХ„ ! — 1, и > 1. (3.17) 1 Кроме того, Хо = ~ е~ Ях = е — 1 в 1* = 1.71828.
о о Воспользуемся формулой (3.17) для последовательного вычисления приближенных значений интегралов 1„: Здесь вычисления следует прекратить. Искомые значения интегралов очевидно, положительны, а найденные значения при и — 9 и и = 10 отрицательны. В чем причина появления такой большой ошибки? В данном примере все вычисления проводились точно, а единственная и, на первый взгляд, незначительная ошибка была сделана при округлении значения 1о до 6 значащих цифр (заметим, что Ьо = ~1о — 1,',~ и 2 ° 10 ~).
Однако при вычислении 1~ зта ошибка сохранилась, при вычислении Ет умножилась на 21, при вычислении Еэ — на 3!, ..., при вычислении Хв — на 9! и т.д. ' Идея примера заимствована из Щ, 186]. 65 Ч ~о 1, и 1~ 3 Хз 5 17 Хт 9 11с 1 0'71828 31* — 1 = 0.30968; 514 1 = 0.19360; 7Х* — 1 = 0.13120; 91в 1 0 55360 1г " Ег 21~ 1 0 43656 14 в 14 —— 4Ез = 0.23872; Еб ~ Ее — 61ь — 1 = 0.16160; Хе м Хь = 81т — 1 = 0.00496; Х~о Еь о 101~ — 1 = — 6.5360 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
