Реферат: Конечные разности. Погрешности

Реферат

«Конечные разности.Погрешности»


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 с.

еще рефераты
Еще работы по экономико-математическому моделированию