Самарский А.А. Гулин А.В. - Численные методы, страница 4

Алгоритм называется устойчивым, если в процессе его работы вычислительные погрешности возрастают незначительно, и неустойчивыхг — в противоположном случае. При использовании неустойчивых вычислительных алгоритмов накопление погрешностей округления приводит в процессе счета к переполнению арифметического устройства ЭВМ. Итак, следует различать погрешности модели, метода и вычис. лительную. Какая же из этих трех погрешностей является преобладающей? Ответ здесь неоднозначен.

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

Например, нецелесообразно пользоваться разностными схемами, имеющими точность 1О', если коэффициенты исходных уравнений задаются с точностью 1О-'. 3. Требования к вычислительным методам. Одной и той х<е математической задаче можно поставить в соответствие множество различных дискретных моделей. Однако далеко не все из них пригодны для практической реализации. Вычислительные алгоритмы, предназначенные для быстродействующих ЭВМ, должны удовлетворять многообразным и зачастую противоречивым требованиям. Попытаемся здесь сформулировать основные из этих требований в общих чертах. Далее в частях П и П! книги эти требования конкретизируются при рассмотрении алгоритмов численного решения типичных математических задач. Можно выделить две группы требований к численным методам.

Первая группа связана с адекватностью дискретной модели исход. ной математической задаче, и вторая группа — с реализуемостью численного метода на ЭВМ. К первой группе относятся такие требования, как сходимость численного метода, выполнение дискретных аналогов законов сохранения, качественно правильное поведение решения дискретной задачи.

Поясним эти требования. Предположим, что дискретная модель математической задачи представляет собой систему большого, но конечного числа алгебраических уравнений. Обычно, чем точнее мы хотим получить решение, тем больше уравнений приходится брать. Говорят, что численный метод сходится, если при неогранн- !4 ченном увеличении числа уравнений решение дискретной задачи стремится к решению исходной задачи. Поскольку реальная ЭВМ может оперировать лишь с конечным числом уравнений, на практике схадимость, как правило, не достигается, Поэтому важно уметь оценивать погрешность метода в зависимости от числа уравнений, составляющих дискретную модель. По этой же причине стараются строить дискретную модель таким образом, чтобы она правильно отражала качественное поведение решения исходной задачи даже при сравнительно небольшом числе уравнений.

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

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

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

15 й 2. Погрешности округления !. Представление вещественных чисел в ЭВМ. Одним из источников вычислительных погрешностей является приближенное яредставленне вещественных чисел в ЭВМ, обусловленное конечностью разрядной сетки. Хотя исходные данные представляются в ЭВМ с большой точностью, накопление погрешностей округления в процессе счета может привести к значительной результирующей погрешности, а некоторые алгоритмы могут оказаться н вовсе непригодными для реального счета на ЭВМ. Напомним о способах представления чисел в ЭВМ и связанных с ними погрешностях округления.

Более подробно этот круг вопросов рассматривается в [6, 8, 15, 29!. При ручном счете пользуются десятичной системой счисления. Например, запись 103,67 определяет число 1 10" +О 10'+3 !О'+6 10 '+7 !О '. Здесь 1Π— основание системы счисления, запятая отделяет дробную часть числа от целой, 1, О, 3, 6, 7 — числа из базисного набора (О, 1, 2, 3, 4, 5, 6, 7, 8, 9), с помощью которого можно представить любое вещественное число.

ЭВМ работают, как правило, в двоичной системе, когда любое число записывается в ниде последовательности нулей и единиц. Например, запись О, 010! в двоичной системе определяет число 0„2а +О 2-~ !.2-г ! 0.2-г 1 Как двоичная, так и десятичная системы относятся к позиционным системам счисления. В позиционной системе с основанием г запись а= -~-а„а„ ,... а„ а ,а ,... (1) означает, что а = ь ( а „г" + а„, »" -' +... + а,»'+ а, г ' + а, г-'+...) . Будем считать далее, что г — целое число, большее единицы.

Каждое из чисел а; может принимать одно из значений (О, 1,... ..., г — 1), Числа а; называются разрядами, например: а, — третий разряд перед запятой, а, — второй разряд после запятой. Запись вещественного числа в виде (1) называется также его представлением в форме числа с фиксированной запятой. В ЭВМ чаще всего используется представление чисел в форме с плаваю- и(ей запятой, т. е. в виде (2) а=Л!»', где г — основание системы счисления, р — целое число (положительное, отрицательное илн нуль) и г-'~ ~М~ (1, (3) Число М представляется в форме числа с фиксированной запятой н называется мантиссой числа а.

с1исло р называется порядком числа а. В виде (2) можно единственным образом представить 16 любое вещественное число кроме нуля. Единственность обеспечивается условием нормировки (3). Например, число !03,6? в форме с плавающей запятой имеет вид 0,10367 1О', т. е. М=О,!0367, Р=З. Двоичное число 0,0101= =О,!01.2 ' имеет в двоичной системе мантиссу М=О,101 и порядок р=-1. зг р рт рс Рис. 2. Рззряднзя сетка В ЭВМ для записи каждого числа отводится фиксированное число разрядов (разрядная сетка).

Например, в ЭВМ БЭСМ-6 для записи числа, представленного в форме с плавающей запятой, отводится 48 двоичных разрядов, которые распределяются следующим образом: в разрядах с 1 по 40 помещается абсолютное значение мантиссы, в 41 разряде — знак мантиссы, в разрядах от 42 до 47 — абсолютная величина порядка, в 48 разряде — знак порядка (см. рис.

2). Отсюда легко найти диапазон чисел, представимых в ЭВМ БЭСМ-6. Поскольку максимальное значение порядка в двоичной системе равно 111111=63 и мантисса ие превосходит единицы, то с помощью указанной разрядной сетки можно представить числа, абсолютная величина которых лежит примерно в. диапазоне от 2-" до 2", т. е. от 10г м до 10". Ту же 48-рззрядную сетку можно использовать для представления чисел с фиксировзиной запятой. Пусть, например, разряды с ! по 24 отводятся для ззписи дробной части числа и разряды с 25 по 47 — для записи целой чести числа.

Тогда максимальное число, которое можно представать с помощью двиной разрядной сетки, будет равна !1 ... 1, 1! ° ° ° 1 ( 2ьз - 10'. 23 ряэрядя 24 разряда Следовательно, в данном случае дивпззон допустимых чисел в 1О" рвз меньше, чем прн использовзнии представления с плавающей запятой. Возможностью существенного увеличения диапазона допустимых чисел при той же рззрядной сетке и объясняется преимущественное использование в ЭВМ представления чисел в форме с плавающей запятой.