Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 17
Текст из файла (страница 17)
Пусть для задачи Коши у — ~ у = о(х)х, у (1) = 2, (3.23) где а(х) = 2.6 + 0.01е х, найдено приближенное решение у = 2хт. Как оценить его качество? 74 которые после округления коэффициентов совпадают с уравнением (3.22) и становятся неотличимы от исходного уравнения.
Найденное решение следует признать превосходным с точки зрения "философии" обратного анализа ошибок, так как оно является точным решением задачи, лежащей в пределах области неопределенности задачи (3.22). Рассчитывать на то, что после записи уравнения в виде (3.22) удастся получить лучший ответ, просто бессмысленно. Конечно, это немного обидно, особенно если учесть, что исходное уравнение в действительности есть развернутая запись уравнения (х — 2.5)5 = 0 и истинным значением корня является х = 2.5.
Условие у (1) = 2, очевидно, выполнено. Подставляя у (г) в левую часть уравнения, убеждаемся, что у (х) удовлетворяет уравнению (3.23) с коэффици- ентом а* = 4 — 42 и 2.586 вместо а. Обратим внимание на то, что "истинное" значение ао коэффициента а нам в действительности неизвестно и а (х)— лишь некоторое его приближение. Числовой параметр 2.6 в лучшем случае получен округлением "истинного" значения, и, следовательно, а может отличаться от ао и на 0.05. Так как ~ а* — а~ ~ 0.03, то в силу естественной неопределенности в постановке задачи функция у = 2г" с позиции обратного анализа ошибок может считаться таким же равноправным решением поставленной задачи, как и найденное сколь угодно точно решение задачи (3.23). Во всяком случае теперь для того, чтобы отказаться от найденного приближенного решения, нужны довольно веские аргументы.
Подчеркнем, что в основе методов решения некорректных и плохо обусловленных задач также лежит существенное переосмысление постановок вычислительных задач. 3. Огатистический анализ ошибок. Даже для простых алгоритмов строгий анализ влияния ошибок округления очень сложен. При большом числе выполняемых операций гарантированные оценки погрешности, рассчитанные на самый неблагоприятный случай, как правило, бывают сильно завышенными. Можно надеяться на то, что появляющиеся в реальном вычислительном процессе ошибки округления случайны и их взаимное влия— ние приводит к определенной компенсации результирующей ошибки.
Статистический анализ ошибок, исходящий из предположения об их случайности, направлен на исследование не максимально возможных, а наиболее вероятных ошибок. Для сравнения покажем отличие в результатах на примере задачи У вычисления суммы Яу = Е а~ большого числа положительных слага/с=1 емых. Гарантированная оценка погрешности дает значение относительной погрешности Б(Я), растущее пропорционально Ф. В то же время статистический анализ показывает, что если ошибки округления явля— ются случайными с нулевым средним значением, то 6(Я) растет про- порционально,~~, т.е. гораздо медленнее.
К сожалению, на тех ЭВМ, где округление производится усечением, последнее предположение не выполнено, так как ошибки округления смещены в одну сторону и поэтому имеют ненулевое среднее значение. Здесь б(Я) растет опять пропорционально Х 4. Некоторые нестрогие способы анализа Распространенным мето- 75 дом оценки влияния вычислительной погрешности является расчет с обычной и удвоенной точностью.
Если результаты двух вычислений получаются существенно различными, это является свидетельством плохой обусловленности алгоритма. В то же время есть надежда на то, что совпадающие в ответах цифры верны. Примерно такие же суждения о чувствительности решения к ошибкам округления можно сделать, если провести вычисления на двух различных вычислительных машинах или использовать различные компиляторы. Разумеется, такое исследование имеет смысл провести на одном-двух типичных примерах до начала массовых однотипных расчетов. Влияние ошибок во входных данных на результат вычислений можно увидеть, если решить задачу несколько раз, изменяя случайным образом входные данные в пределах ошибки их задания. Проделав такой эксперимент несколько раз, можно грубо оценить погрешность решения, вызванную погрешностями входных данных.
з 3.7. Требования, предъявляемые к вычислительным алгоритмам В ~ 3.4 и 3.5 были сформулированы два важнейших требования— корректность и хорошая обусловленность. Помимо них к алгоритмам предъявляется еще целый ряд существенных требований. 1. Требования к абстрактным алгоритмам. К числу этих требований относятся: 1) экономичность; 2) надлежащая точность; 3) экономия памяти; 4) простота. Экономичность алгоритма измеряется числом элементарных операций, необходимых для его реализации, и в конечном итоге сводится к затратам машинного времени. Это требование формулируют иногда как требование максимальной быстроты исполнения алгоритма. Экономичность особенно важна при массовых расчетах. Естественно, что при создании алгоритмов большое внимание уделяют минимизации числа операций. Для некоторых задач разработаны алгоритмы, требующие минимально возможного числа операций.
Пример такого алгоритма — схема Горнера (см. пример 3.19). Отметим, что ряд математических алгоритмов, созданных в домашинный период, оказался удивительно неэкономичным. Приведем классический пример такого алгоритма. Пример 3.34 (и р а в и л о К р а м е р а1). Для решения системы линей- 1 Габриэль Крамер (1704 — 1752) — швейцарский математик. ных алгебраических уравнений Ах = 6 порядка тп по правилу Крамера предлагается вычислять компоненты вектора т как отношения специальным образом построенных определителей: х, = Ь;/Ь, 1 = 1, 2, ..., т. Если вычислять определитель непосредственно по его определению, то нужно выполнить (т — 1)т! умножений и т! сложений. Пусть для вычислений используется ЭВМ с производительностью 10в умножений в секунду и решается система с числом неизвестных тп = 15, весьма скромным для приложений. Тогда вычисление только одного определителя потребует 14 ° 15! 1.8 ° 101З умножений, в результате чего на вычисление решения уйдет около 10 лет непрерывной работы ЭВМ.
Вместе с тем для решения той же системы на той же ЭВМ методом Гаусса (см. гл. 5) потребуется примерно 0.002 с. Естественно, что как вычислительный алгоритм правило Крамера следует забраковать. Даже для самых простых задач выбор экономичного алгоритма может дать существенное уменьшение числа операций. Пример 3.35. Пусть требуется вычислить х", где п — натуральное число. Вычисление этой величины последовательным умножением на х предполагает выполнение п — 1 операций умножения.
Нетрудно убедиться в том, что этот способ не самый экономичный. Например, хе4 можно найти, выполнив не 63, а всего 6 операций умножения, если последовательным возведением в квадрат вычислить тт, х4, ~в, х4в,,тэ2, ~в4. В общем случае представим а в виде разложения (2.25) по степеням двойки (именно так число п хранится в памяти ЭВМ). Тогда ~ь)оь ( ~Ы)~Ч,-1 д о1 ао (3. 24) Заметим, что в произведении (3.24) следует учитывать при вычислении только те сомножители, для которых а, ~~ 0 (т.е. а; = 1). Алгоритм, основанный на разложении (3.24), называется бинарнмл алаориталол.
Он позволяет найти х" не более чем за 21о82а операций умножения. Требование точности означает, что вычислительный алгоритм должен давать решение задачи с заданной или приемлемой для задачи точностью я, Важным является требование эконолии пал~яти. Хотя в последнее время доступная память ЭВМ существенно расширилась, для "больших" задач требование экономии памяти может в ряде случаев стать основным. Интерес к экономному размещению информации в памяти возрастает в связи с более широким использованием персональных ЭВМ для решения научно-технических и инженерных задач. Учитывая необходимость дальнейшей программной реализации алгоритма, подчеркнем, что простота ал~орипьиа также является весьма желательным его свойством.
77 2 Требования к программным реализациям алгоритмов. К настоящему времени выработан ряд требований к программам, реализующим вычислительные алгоритмы и предназначенным для длительного и широкого использования. Перечислим некоторые из них: 1) надежность; 2) работоспособность (робастность); 3) переносимость (портабельность); 4) поддерживаемость; 5) простота в использовании и др.
Рассмотрим эти требования более подробно. Надежностиь программы означает, что она не содержит ошибок и вычисляет именно тот результат, для которого она предназначена. Работпоспособность (робастностпь) включает в себя надежность и предполагает, что программа способна выявлять недопустимые исходные данные, обнаруживать различные критические для задачи или алгоритма ситуации.
Робастная программа реагирует на такие ситуации приемлемым для пользователя образом. Она составлена так, чтобы исключить какие-либо аварийные остановы, в том числе по переполнению, из-за деления на нуль, неудачной попытки применить операцию извлечения квадратного корня или взятия логарифма от отрицательного числа. Алгоритм может "потерпеть неудачу" при решении задачи, если заданное входное данное не является для него допустимым.
Конечно, в простых ситуациях пользователь должен сам различать допустимые для алгоритма входные данные от недопустимых. Однако чаще всего сделать это до вычислений очень трудно или невозможно, и в программе должен быть предусмотрен анализ данных и сообщение пользователю о недопустимых или сомнительных данных. Необходимо исключить ситуацию, характерную для некачественных программ, когда реакцией на задание данных, при которых алгоритм не может по объективным причинам найти решение задачи, является аварийный останов или же выдача внешне вполне правдоподобного, но совершенно бессмысленного результата. Переносилосгиь (портпбельность) означает, что программа может работать на различных ЭВМ без изменения или с незначительными изменениями. Всякая характеристика ЭВМ, используемая в программе (например, значение машинного эпсилон я„), должна или вычисляться самой программой, или задаваться пользователем.
Поддержпваелость означает прежде всего требование легкости модификации. Для того чтобы была возможность внесения в программу изменений с минимальной вероятностью появления ошибок, она должна быть составлена максимально ясно и логично. Полезно вносить в текст программы содержательные комментарии. Разобраться в плохо составленной программе может оказаться труднее, чем создать новую. Поддерживаемая программа должна быть хорошо документирована. 78 Плохое описание программы в лучшем случае способно вызвать к ней недоверие, а в худшем — может не позволить пользователю правильно ее эксплуатировать.
К сожалению, нередка ситуация, когда предназначенная для широкого использования программа настолько плохо документирована, что пользователь предпочитает потратить время на написание аналогичной программы (возможно, гораздо худшего качества) либо вообще отказаться от решения задачи. Простота в использовании программы — весьма желательное, но трудно достижимое свойство, Зачастую добиться простоты в использовании можно только жертвуя надежностью или экономичностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
