А.А. Самарский - Введение в численные методы (1113832), страница 3
Текст из файла (страница 3)
11апример, заменяя производную и (х) разяостпым отношением (и(х+ Лх)— — и(х))/Лх, мы допускаем погрешность дисгзретизацигт, имеющую при Лх- 0 порядок Л.г. Пакопеп, копечоан разрядность чисел, представляемых в ЭВМ, приводит и ошибкам округления, которые могут нарастать в процессе вычислении. Естественно требовать, чтобы погрешности ввкдкпис в задании начальной информации н погре1пность, возникающая в результате дискретпаацип, были согласованы с погрегппостью решения па У)Вй( дискретной задачи. Из сказанного видно, что основное требование, предьявляемое к вычислительному алгоритму, — зто требование точности, Опо означает, что вычислптельньгй алгоритм должен давать реп~зоне исходной задачи с заданной то ы постыо е ) 0 за конечное число г)(е) действий. Ллгорптм должен быт| реализуемым, т. е.
давать решение задачи за допустимое машинное время. Для болыпппства алгоритмов время решения зада п1 (объем вычвслеапй) ()(с) возрастает прп повьпнеппп точности, т. о. прн уменьшении с. 1(онечно, можно задать е настолько малым, что врехш счета задачи станет недопустимо большим, Важно знать, что алгоритм дает прпп1(ит~нальпую возможность получить решение задачи с лк>бой точностью. Однако иа практике величину е выбирают, учитывая возможность реализуемости алгоритма на данной ЭВМ, Для каждой задачи, алгоритма и машины есть свое характерное зиачешге е. Естественно добиваться, чтобы число действии Вп тем самым машинное время решения задачи) ()(е) было минимальным для данной аадачи.
Для любой вада'пг можно предложить много алгоритмов, дающих одинаковую по порядку (прв е - О) то шость с ~ О, но за разное число действий ()(е). Среди этих, как говорят, эквивалентных по порядку точности алгоритмов надо вьгбрать тот, который дает решение с затратой наименьшего машинного времени (шола дойствпй фе)), Такие алгоргггмы будем называть экономичными. Остановимся еще иа одном требовании, пред"ьявляемом к вычислшельному алгоритму, а именно — требовании отсутствия аварийного остапова (авоста) ЭВУй в процессе вычпслений.
Следует иметь в впду, что ЭВй( оперирует с чпсламп, пмеющимп конечное число значащих цифр и принадлежащих (по модулю) не всей числовой оси, а некоторому интервалу (Мм М ), М,>0з М (, где М,— машинный нуль, М вЂ” машинная бесконечность. Гслп условие !М) ( М в процессе вычислений нарушается, то происходит аварийный останов ')Вй( вследствие переполнения разряииой сетки, и вычисления прекращаются.
Возмоягность авоста зависит как от алгоритма, так н от исходной задачи. ввкдвник Коли решение исходной задачи выражается через очень большие (очень малые) числа )М! > М (ЭХ! <Мо), то, как правило, путем изменения масштабов можно привести задачу к виду, содержащему только величины, принадлежащие (по модулю) заданному интервалу (М„М„. 1 вг лх ) Часто возможность авоста может быть устранена путем изменения порядка действий. 11ояспим зто на простом примере. Г(рлмер. Пусть М„=10', М„=10 ", р=2", и— целое число. Требуется вычислить произведение чисел 10~', 10, 10-е~', 10".-~', !0-":. 1-и способ. !!ерепумеруем числа в порядке убываппл: о, = 10'"~', д.
= 10"', д, = 10с", д, = 10 "", д;= ""и п образуем произведения Я,, = Я,д„о Я, = йе Тогда уже па первом шаге мы получим авост, так как Я = ((~у~ = = 106г1*' ) М 2-й способ. Перепумеруем числа в порядке возрастания: д, = 10 '", д. = 10 "', о, =10"", д, = 10"', д = 10'"'. В этом случае мы получим на первом шаге Яз = д, д, = 10 "" ~ М„ т. е. Яз — машинньш пуль; нулю равны п все последузощие произведения бн Бе Я,; таким образояц здесь происходит полная потеря точности, З-й способ. !!еремешаем эти числа, полагая д, =- 10 "', д, =10' ', д, =10"', д, =10 "'-, д, = 10"". Гогда последовательно найдем; Я*= дна 10 ", Яз = Бай~ = !Ом, о, =Ь,Ч, =10", о; =я,о,„== !Ос", т, е.
в процессе вычнслокий не появляются числа, большие 10"", п меньшие 10 "". Такой алгоритм является безавоствым. В гл. 111 мы встретимся с итерационным методом решения системы линейных алгебраических уравнений, который может быть авостным пли безавостпым в вависимости от способа вумерацип итерационных параметров, определяющего послодовательность вычислений. При каждом акте вычислений появляются ошибки округления. В зависимости от алгоритма зти ошибки округления могут либо нарастать, лабо затухать. Вели в процессе вычигтенпй ошибки округления неограниченно нарастают, то такой алгоритм называют не- ввкдкннн устойчивым (вычпслительпо неустойчивым).
Если же ошпокп округления не накапливаются, то алгоритм является устойчивым. Примеры. 1. Пусть требуется найти у; (0<т~т',) по формуле ул«т = у, + тт П ) 0) прп заданных у,, Предположим, что прп вычислении у, внесена ошибка (например, ошибка округления), имеющая величину бь т.
е. вместо точного значения у, получено приближенное значение у, = у, + 6» Тогда вместо точного значения ут«, получим приближенное значение у,, = (у;+ 6,) + тл'= = учы 4- 6» Таким образом, ошибка, допущенная на любо»« промежуточном шаге, пе увеличивается в процессе вычислений. Алгоритм устойчив. 2. Расс»тетри»« уравнение ут„, = т)тут (т ~ О, у„и д заданы). Пусть, как и в примере 1, вместо у, получено значение у, = у, + 6,. Тогда вместо у,„, получим приближенное значение ут, = (т( у, + 6.) = у...
+ обь Отсюда видно, что погрепткость б,,=у„,— уи„о возникающая при вычислении у,, „связана с погрешностью 6, уравнением б,ю=убт, «=0, 1, 2.... Следовательтш, если !т)) ) 1, то в процессе вычислений абсолютное значение погрешности будет возрастать (алгоритм неустойчив). Если нте )д) -1, то погрешность не возрастает, т. е. алгоритм устойчив, Пеустойчизостьобычно связывают со свойством экспоненциального нарастания оптибт«и округления.
Если же ошибка округления нарастает по степенному закону прн переходе от одной операции к другой («от шага к шагу»), то алгоритм считатот условно устойчивым (устойчивым прн некоторых ограничениях на объем вычислений н требуемую точность). Процесс вычислений можно трактовать так: прн переходе от шага к шагу происходит искажение (за счет ошибок округления) последних значащих цифр (от последних значащих цифр справа налево движется «золна отпибки округления»).
Нам нужно обычно сохранить верными несколько первых значащих ппфр (4 — 5 знаков), н поэтому вычисления должны быть закончены до того, как до них дойдет «волна ошибки округления», Если ошибка округления е, нарастает от шага к шагу по экспопенциальяому закону, то это приводит, как правило, к авосту на про- вввдэниэ межуточпом этапе вычислений, если (как в примере 2) ~дре,)М . Гели М„= 10', е„= 10 ~', то авост наступаетпри0) ) (р+ !г,)/1д ~д(. Иначе обстоит дело прн степенном росте ошибки округления. Пусть (бд,) = ("е, (и ~ 1); тогда / 1 авост наступит при (",е,~й1', т.
е. прн (э)~( — Ц = 10 Отсюда видно, что прп и= 1 аноета пе будет в силу очевидного ограничения ( ( э1„= 10", Перавенство )бр,~ ~ е, где е = 10 " — заданная точность, спра(ва "Р' ведливо при ((~( — ~ =10 ' = (, Гслп заданы е э и е„то вто неравенство означает ограничение па число уравнений 1: 1, Так, прп )г„,=12, 1'=б имеем 1<10'о', так что 1~ 10' прп л 2. Ясно, что можно указать такое болыпое п, что допустимое число уравнений й очень мало, Однако, па практике обычно встречаются случаи пеболыпого п (капример, для метода прогонки (з 3 гл. 1) п =2, т.
е. погрешность накапливается по квадратичному аакопу с ростом числа уравнении), Прп решении зпобой задачи необходимо знать какие-то входные (исходные) данные — начальные, граничные значения искомой функции, коэффициенты п правую часть уравнения и др. Для каждой задачи ставятся одкп и те жс вопросы: существует ли решение задачи, является лп опо единственным и как зависит решение от входных данных? Возможны два случая: Задача поставлена корректно (задача корректна); зто значит, что 1) задача разрешима прп любых допустимых входных данных; 2) имеется единственное решение; 3) решение зада ш непрерывно зависит от входных данных (малому изменению входных данных соответствует малое изменение решения) — инымп словамп, задача устойчива, Задача поставлена некорректно (задача некорректна), если ее решение неустойчиво относительно входных данных (малому пзмененшо входных данных может соответствовать большое изменение решения).
Примером корректной задачи может служить задача интегрирования, а примером некорректной задачи — аадача дифференцирования, ввндгиии Примеры, 1.Задача интегрирования, Дапа функция )(х); найти интеграл ! о =- ~ ! (х) <!х. о Заменим ! иа ! и рассмотрим У = 1 !(х) «х и разность о Ы = Х вЂ” Х = ~6!<(х (6! = !(х) — !(х)). Отек<;<а видно, о что (6Х)(<пат (6!(.г)(, (6,)((~е, если )6!)( <, т.
е. l оооо! непрерывно зависит от !. Для вычисления интеграла У восиог<ьзуео<ся квадратуриой форму<лая: Хк = г со!(хо), с!) О, ~' со == 1. о — ! В=! Повторяя рассуждения, приведенные вьппе, получим л 6У .= Ул — Ул —: ~' . (! — ! ) == " с 61, <<- ! !.- ! л (6Ук(( У со п<ак (6!о( =- и!ак (6!о).
о-.< ! ооал ! <*ел Таким образом, задача вычисления интеграла по квадратуриои формуле корректна. 2. Задача дифференцирования, Задач» дифференцирования функции и(х), заданной приближенно, является яекорректноп, В самом деле, пусть 1 и (л) =- и (т) -; — гйп !!<ох, где <!' достаточно велпьо. Тогда Л е метрике С' (<и некотором огрезке О ~ т -- 6 (6 > л<'<!')) имеем )би<з =<<< — <го=-(уй!~с нрп "!'>1/е, Для погрешности производныт 6«' = й' — и =- <!' сое Ю<х имеем ~би'~„=.о!'~ 1/е, Таким образом, маломч изменению 0(е) е (,' функции и<х) соответствует болыпое изменение ()()/е) в С' ее произеодпои.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
