Кінцеві різниці Похибки

Реферат
«Кінцеві різниці. Погрішності »

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