Реферат: Конечные разности. Погрешности
Реферат
«Конечные разности.Погрешности»
1. Погрешности
1.1 Действительные и конечно-разрядныечисла
Представлениедействительных чисел в вычислительных машинах с фиксированной разрядной сеткой влечетпоявление инструментальной погрешности в обрабатываемых числах и результатахарифметических действий.
Принятое при вводе преобразованиеисходных действительных чисел в нормализованную экспоненциальную форму иразмещение их в ограниченной разрядной сетке ЭВМ с порядком и дробной частью(мантиссой) в общем случае вносит в этот операнд относительную инструментальнуюпогрешность, величина которой не превышает
/>
где n – числозначащих дробных двоичных разрядов, отведенных для хранения мантиссы.
Приближенноеконечно-разрядное число a – это действительное число, занимающее заданноеколичество разрядов и округленное до числа с ближайшим значением достоверногомладшего разряда. Приближенные действительные числа имеют абсолютную /> и относительную /> погрешности. Этипогрешности при анализе распространения ошибки при вычислениях приписываются к приближенномучислу результата и связываются между собой следующим образом:
/>
Если число a = 5,3812имеет все разряды достоверные, то его абсолютная погрешность принимаетсяравной половине единицы младшего разряда, т.е. />=0.00005,а относительная погрешность, округляемая обычно до одного-двух значащихдостоверных разрядов, будет />
Всякие арифметическиеоперации с операндами, представленными в системе с плавающей точкой, в общемслучае вносят в результат аналогичную относительную инструментальнуюпогрешность:
/>
где fl(•) – указание наарифметику с плавающей точкой,
/> – арифметическаяоперация из множества />.
Значение результата,равное нулю принудительно устанавливается в машинах при операциях умножения сдвумя операндами, приводящее к исчезновению порядка (отрицательный порядок помодулю не умещается на отведенном для него количестве разрядов).
Несколько иначе обстоитдело при вычитании чисел с плавающей точкой и одинаковым порядком:
/>,
/>.
Из последнего можнозаключить, что для операции вычитания относительная погрешность численноопределяется количеством значащих разрядов в результате, которое из-завыполнения нормализации не может быть меньше />.Т.е. погрешность приближается к 100% последовательно. Это предупреждениеадресуется составителям вычислительных алгоритмов, которым необходимовыискивать эквивалентные формулы с контролем величины операндов, в определенныхситуациях можно использовать программный переход к вычислениям с удвоеннойточностью.
При выполнении аддитивныхопераций с приближенными операндами погрешность результата равна суммеабсолютных погрешностей всех чисел, участвовавших в операции. Выполнениемультипликативных операций вносит в результат относительную погрешность, равнуюсумме относительных погрешностей каждого из операндов.
1.2 Погрешностьалгоритмов
Инструментальныепогрешности арифметических машинных команд из-за различия и непредсказуемости величиныошибки результата нарушают дистрибутивный, ассоциативный и коммутативный законыарифметики. Каждый же программист, составляя программу, уже на уровне интуициипользуется ими, как незыблемыми. Отсюда различие в точности тех или иныхвычислительных алгоритмов и трудно уловимые ошибки.
Проследить накопление вычислительнойпогрешности алгоритма для операндов, которые имеют производные, удобно, если результатr каждой двуместной арифметической операции умножать на множитель /> с последующим разложениемрезультирующей функции алгоритма по степеням этого множителя или этихмножителей, если /> в группахоператоров отличаются по величине. Например, для алгоритма вычисления значенияполинома /> третьей степени по схемеГорнера с псевдокодом:
P:=0; j:=3;
repeat
S:=a[j]*x+a [j-1];
P:=P+S*x;
j:=j-1;
until j=1;
функция алгоритма будет:
/>
Учитывая, что />, последнее выражение даетвозможность после раскрытия скобок выделить из суммы и оценить сначалаабсолютную погрешность, а по абсолютной погрешности – относительную:
/>
Условные арифметическиеоператоры с проверкой равенства операндов необходимо заменять проверкой вида: />.
2. Конечные разности
2.1 Определение конечныхразностей
Конечная разность «вперед»для таблично заданной функции в i-той точке определяется выражением: />, где функция /> задана, как функцияцелочисленного аргумента с единичным шагом по аргументу i.
Для аналитически заданнойи протабулированной с постоянным шагом h функции /> определяющее соотношениеимеет вид:
/>.
Преобразование таблицыфункции /> в функцию целочисленногоаргумента /> осуществляют при помощилинейного соотношения между аргументами x и i: />.
Коэффициенты a и bнаходят из системы уравнений, получаемой в результате подстановки в пределахзаданной таблицы вместо x и i сначала начальных значенийаргументов />, а затем конечных />. При этом начало таблицыудобно совместить с началом координат функции с целочисленным аргументом/>(/>). Тогда для таблицы с (n+1) –й строками:
/>,
/>
Повторные конечныеразности n-го порядка вi-той точке для табличной функции /> определяются соотношением
/>.
2.2 Конечно-разностныеоператоры
Линейностьконечно-разностного оператора /> позволяетввести конечно-разностный оператор сдвига /> имногочлены от оператора /> сцелыми коэффициентами, такие, как />, где /> должно рассматриваться какоператор повторной разности k-того порядка.
Действие любогомногочлена /> на функцию g(i)определяется как
/>.
Применение операторасдвига к g(i) преобразует последнее в g (i+1):
g (i+1)= E g(i)= (1+/>)g(i)=g(i)+ />g(i).
Повторное применениеоператора сдвига позволяет выразить (i+n) – е значение ординатыфункции g через конечные разности различных порядков:
/>
где /> – число сочетаний изnэлементов по k;
/> – многочлен степени kот целой переменной n (/>),имеющий k сомножителей. При k=n />.
В силу линейностиоператора сдвига можно конечно-разностный оператор выразить, как />, и определить повторныеконечные разности через многочлены от операторов сдвига так />.
Последнее позволяетформульно выражать n-ную повторную разность через (n+1) ординатутабличной функции, начиная с i-той строки:
/>
Если в выражении для g(i+n) положить i=0 и вместо /> подставитьих факториальные представления, то после несложных преобразований получится разложениефункции целочисленного аргумента по многочленам />,которые в литературе называют факториальными:
/>.
Можно поставить задачуразложения и функции действительной переменной f(x) помногочленам /> относительно началакоординат (аналогично ряду Маклорена), т.е. />.Если последовательно находить конечные разности от левой и правой частей, то,зная, что /> и />, после подстановки x=0будем получать выражения для коэффициентов разложения />. У многочленов k-тойстепени, />, поэтому
/>.
Такое разложениетабличной функции f(x) в литературе называют интерполяционныммногочленом Ньютона для равных интервалов.
2.3 Взаимосвязьоператоров разности и дифференцирования
Значение функции наудалении h от некоторой точки /> можновыразить через значения производных в этой точке, разложив ее в ряд Тейлора:
/>
где /> – оператордифференцирования,
/> – оператор сдвига,выраженный через оператор p.
h – шаг по осидействительной переменной
Из равенства операторовсдвига, выраженных через p и />, можнополучить взаимосвязь этих линейных операторов:
/>,
Оператордифференцирования порядка n, перенесенный в точку, удаленную от текущей,например, на 2 шага вперед представляется так:
/>.
Выполнив алгебраическоеперемножение многочленов с конечно-разностными операторами и ограничившисьоператорами со степенью не выше n, получим одну из возможныхаппроксимаций оператора дифференцирования. Действуя таким сложным конечно-разностнымоператором на ординату f(x), получаем формулу длявычисления n-й производной в точке /> позначениям ее конечных разностей. Например, для n=2, отбрасывая всеповторные разности выше третьего порядка, получим:
/>.
Если f(x)является многочленом степени n, то повторные разности (n+1) –го порядка тождественно равны нулю. Приравнивая нулю повторные разностипорядков выше n мы фактически аппроксимируем f(x)многочленом степени n.
В предыдущем выражении,выразив повторные разности через ординаты табличной функции, получим еще одинвид формулы для вычисления значения производной:
/>.
Для целочисленногоаргумента табличной функции запись выражения можно упростить, если положить h=1и />
/>
2.4 Исчисление конечныхразностей
Разложение функций в рядпо факториальным многочленам (интерполяционным многочленам Ньютона в частности)дает возможность получать формулы суммирования функциональных рядов в видеаналитических выражений, зависящих от пределов. Эта возможность открывается всвязи с тем, что суммировать конечные разности не представляет большойсложности, а выразить конечную разность от факториального многочлена черезфакториальный же многочлен можно, воспользовавшись соотношением:
/>
Факториальные многочленыпо отношению к исчислению разностей ведут себя так же, как степенные функции висчислении производных: дифференцирование тоже понижает степень многочлена наединицу. Это свойство позволяет в факториальном разложении заменить факториальныемногочлены своими конечными разностями следующего вида:
/>
Замена хороша тем, чтосуммирование конечных разностей в заданных пределах мнемонически весьманапоминает вычисление определенного интеграла от функции по ее первообразной:
/>
Если />, то
/>.
Процедуру суммированияфункционального ряда продемонстрируем на примере получения суммы квадратовнатурального ряда чисел в пределах от a=1 до b=5 (Для проверки: />):
/>
Вторая сумма попеременной n представляет разложение /> пофакториальным многочленам, в которое входят значения конечных разностей 0, 1 и2-го порядков, вычисленные в начале координат целочисленной переменной, т.е.при x=0. Они соответственно равны:
/>,
/>,
/>.
После подстановкизначений разностей во второй сумме останутся два факториальных полинома: первойи второй степеней:
/>
Если распределитьвычисление сумм по слагаемым, то мы перейдем к суммированию конечных разностейот факториальных многочленов:
/>
Литература
1. Бахвалов Н.С.,Жидков Н.П., Кобельков Г.М. Численные методы: Учеб. пособие. –М.: Наука, 1987. – 600 с.
2. Воеводин В.В. Численныеметоды алгебры. Теория и алгорифмы. – М.: Наука, 1966. – 248 с.
3. Воеводин В.В. Вычислительныеосновы линейной алгебры. – М.: Наука, 1977. – 304 с.
4. Волков Е.А. Численныеметоды. – М.: Наука, 1987. – 248 с.
5. Калашников В.И. Аналоговыеи гибридные вычислительные устройства: Учеб. пособие. – Харьков: НТУ «ХПИ», 2002. – 196 с.
6. Вержбицкий,В.М. Численные методы. Математический анализ и обыкновенныедифференциальные уравнения. М.: Высш.шк., 2001. 383 с.
7. Волков,Е.А. Численные методы. СПб.: Лань, 2004. 248 с.
8. Мудров,А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. Томск:МП «РАСКО», 1991. 272 с.
9. Шуп, Т.Е. Прикладныечисленные методы в физике и технике. М.: Высш. шк., 1990. 255 с.
10. Бахвалов, Н.С. Численныеметоды в задачах и упражнениях / Н.С. Бахвалов, А.В. Лапин, Е.В. Чижонков.М.: Высш. шк., 2000. 192 с.