• 1.2 Похибка алгоритмів
  • 2. Кінцеві різниці
  • 2.2 Звичайно-різницеві оператори
  • 2.3 Взаємозвязок операторів різниці і диференціювання
  • 2.4 Обчислення кінцевих різниць


  • Дата конвертації25.03.2017
    Розмір19.47 Kb.
    Типреферат

    Скачати 19.47 Kb.

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

    реферат

    «Кінцеві різниці. похибки »

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