Бабенко - Основы численного анализа (947491), страница 57
Текст из файла (страница 57)
приведем соответствующий численный пример. В квадрате 1 = 1л: 0 < т < л, 1 = 1, 2) решалась задача ДиРихле длЯ УРавнепиЯ гзи = )"1а) с гРапичным Условием и/в — — О. БРалась функция ие(л) = зш тг сйплг/(1 — е зш тд зш тг) и правая часть 7 находилась путем подстановки ие(л) в уравнение. Задача решалась на сетке 109 х 109 при значениях в = 0.5; 0,75; 0,9; 0,95.
Найденные приближенные значения решения рассматривались на редкой сетке, содержащей Э 7, Оиеикп иепсрсчников 271 узлы с номерами 1, 11,21,31,41,51,61, 71,81,91, 101, 109 как по лз, так и по лш т. е. бралось всего 144 узла вместо 11881. Затем с этой редкой сетки решение квадратично интерполировалось на исходную сетку и все величины округлялись.
В табл. 1 содержатся окрутленные значения точного решения, разностного решения и результата интерполяции в узлах сетки с номерами 41, 42, 43, 44, 45 по шм Читатель может убедиться, что результат интерполяции находится в допустимых. ГлАвА 4 Теория табулирования и б-энтропия й 1.
Таблицы функций 1. Классические таблицы. Когда вычисления производились вручную или на настольных клавишных машинках, использование таблиц и работа с ними, были теми могущественными средствами, с помощью которых резко уменьшалось число операции, необходимых для получения требуемого результата. Кроме таблиц логарифмической функции широко б»или распространены таблицы функции тригонометрических, гиперболических тригонометрических, функции 1/л', степенной х" для некоторых показателей и в др.
Таблицы строились по единому правилу: с некоторым шагом бралось значение аргумента и приводилось соответствующее значение функции. Значения функции, соответствующие значениям аргумента, отсутствовавшим в таблице, находилисгв как правило, с помощью линейной интерполяции, для чего приводились разности соседних величии, а под названием «Р. рг» (Рапеэ ргорог11опа1еэ) -- вспомогательные величины для осуществления такой интерполяции. Поэтому для того, чтобы найти по аргументу х значение функции 1'(л), нужно было сделать несколько операций выборки из таблиц (основной и вспомогательной), т, е, нужно было найти соответствующие данные в таблицах и их «считагь», а затем, как правило, произвести максимум одну арифметическую операцию сложение.
Функция вычислялась с некоторой абсолютной точностью н, и эта точность определяла обьем таблиц. Таблицы представляли собой солидные фолианты, а если учесть, что множество специальных функций. с которыми часто приходилось работать., насчитывало не один десяток наименований, то собрание таблиц представляло уже целую библиотеку (причем это все для функции одной переменной). Так, например, «Пятизначные таблицы логарифмов> [9Ц содержат десятичные логарифмы целых чисел от 1 до 10800.
Эта таблица занимает 36 страниц убористого текста„так что на каждой странице содержится 3056 десятичных знаков„не считая различных служебных знаков. Таким образом, вся таблица содержит 50 016 десятичных знаков при довольно скромной точности мантиссы десятичного логарифма в пять десятичных знаков.
Таким образом, классические таблицы функпий состояли из следующих двух частей: приближенных значений )'(т1), ..., Д(т,„) табулируел«о»3 функции )': ]а, Ь] — К, при сем в основном эти значения брались для равноотстоящих узлов хм ..., л ~ ]а, Ь], и некоторого правила, по которому восстанавливалось приближенное значение функции в произвольной точке отрезка (а, Ь]. Это правило — способ интерполяции обгспечи- 273 З 1. Таблицы функций валось различной служебной информацией. вспомогательными величинаин, позволявшими просто провести интерполяцию.
Основное вниь<шп<е при составлении таблиц обращалось на простоту работы с ними, причем сложность работы оценивалась числом арифметических операций, которые нужно выполнить лля получения результатов, и почти игнорировались такие операции.
как поиск по таблице и считывание результата. ЭВМ п<жволяют по-новому подойти к вопросал< табулирования, поскольку сильно ослаблены ограничения на сложность того алгоритма, с помощью которого восстанавливается приближенное значение функции. Ниже приводится пример таблицы логарифмической функции 1к(1 л х) на отрезке (О, Ц. Если х > 1, то, полагая 1 —, :х — 2™(1 + у)., где 0 < у < 1, т — положительное число, получим !к(1 + х) = т !я 2+ !и(1+ у).
Пгимкг. Таблица 1 построена следующим образом: функция 7" (х) = !8(1+х) разложена в ряд по приведе<п<ым многочленам Чебышева Т„'(х) = = Тв(2х — 1) и в качестве собственно таблицы предлагается взять приближенные значения коэффициентов ряда. Учитывая, что многочлены !'„*(х) ортогональны на отрезке (О, Ц по мере <!а =. [х(1— -, — 1~2 — х) ' <(х, несложно после элементарных преобразований получить формулу Таблица 1. КоэФФициенты ряда Фурье — Чебьппева для функции !я(1 + х) х =о"'"7 (х) !8(1+х) = — 2М!8(! — д) — 2М ~ 7'„"(х), (1) ( — у)"„.
и э=1 где д = 3 — 2г2, ЛХ =!ие Для того чтобы в мантиссе иметь пять правильных десятичных знаков, достаточно взять первые шесть членов разложения с точностью 10 ь. Приближенное значение логарифма предлагается вычислять по формуле !8(1-~ х) = ~ а*„7'„'(у) -!- ш182, (2) э=в где у находится из условия 1 з х = 2""(1+ у) (О < у < 1) и а„приближенные значения коэффициентов, приведенные в табл. 1, где указан дополнительный шестой десятичный знак. От отбрасывания остальных членов ряда вносится погрешностгь меньшая 2,23 10 в; от округления величин а„вносится суммарная погрешность не более 2.,6 10 в.
Наконец, если вычислять значения многочленов Чебышева Т„',(у) с точностью 10 б, то это даст суммарную погрешность, меньшую 3,2 10 в. Таким образом, погрешность при вычислении суммы в формуле (2) пе будет прево<ходить 8,03 10 в. Мы привели значение !и2 с запасом для того, чтобы получить значение !йх при 1 < х < 10800 с пятью верными знаками. Итак, мы видим, сколь значительна разница может быть в объеме таблицы, если допустить более сложные алгоритмы для приближенного 274 Глава 4. Теория табйлирооанил и г-энтропия восстановления функции.
Применяя схему Горнера для вычисления суммы (2), в силу формул (2.4.16), (2.4.17), (2.3.б2) получим, что нужное число умножений и сложений равно 14. Причем мы подсчитали умножение на 2 дважды, а если вычисления делать в двоичной арифметике, то умножение на 2 можно не учитывать, 1'!оэтому вычисление логарифма потребует всего ) 2 арифметических операций. ц 2. Работа с таблицами на компьютере. При решении задач математической физики па ЭВХ! мы вынуждены прибегнуть к таолицам различного рода специальных функций.
Естественно, что мы заинтересованы в том, чтобы таблица функций была по вгхгможности короче. В сапоги деле, если мы будем записывать последовательность значений функции ), то каждая запись будет содержать специальное поле, называемое ключом, однозначно определяющим свою запись. Если записей слишком много, таблица большая (большие таблицы принято называть файлами), то возникает проблема поиска данной записи в файле по ее ключу.
Сама по себе эта проблема совсем не тривиальна, и. даже удовлетворительно решив ее, мы столкнемся с тем, что на поиск по ключу будет требоваться довольно много времени, При работах с таблицами вручную обычно проблеме поиска не уделяется должного внимания, хотя, когда мы пользуемся словарями, на поиск слова тратим времени столько же, сколько и па его запись. Из сказанного вьгтекает, что целесообразно на ЭВМ раоотать с очень короткими таблицами (файлами), переложив тяжесть рабюты на алгоритм восстановления приближенного значения функции, Конечно, мы не можем пойти на очень сложные алгоритмы восстановления, но практически всегда можно найти коьшромиссное решение, как в предыдущем примере.
Поэтому нужно разобраться в общих принципах построения таблиц функций. Начнем с общих определений, Чтобы сделать наши построения содержательными, будем рассматривать проблему табулирования пе для одной конкретной функции, а для произвольного элемента некоторого компакта. Вопрос о том, в какой компакт следует включить конкретную функцию, может быть сравнительно просто решен после изучения задачи табулирования для отдельных компактов. В основном мы будем рассматривать компакты гладких и аналитических функций.
Итак, пусть В линейное нормированное пространство. Х ~ В компакт. Поскольку в таблице содержится преимущественно цифровая информация, то при их составлении будем пользоваться алфавитом Ао = (О, 1, ~ ~), причем сз --. есть разделительный знак. Разделительный знак, выполняет подчиненную функцикх позволяя отделить вспомогательную информацию от основной, и поэтому в дальнейшем при подсчете длины слов мы будем его игнорировать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
