Choliy.NumericaMethods.2011Dec01

Київський нацiональний унiверситет iменi Тараса Шевченка

Чолiй В.Я.

Чисельнi методи

Навчальний посiбник для студентiв фiзичного факультету Версiя вiд 01 грудня 2011 р.

Редакцiйно-видавничий центр "Київський унiверситет"

Київ, 2011

Змiст

3

Вступ.

Цей методичний посiбник мiстить матерiал лекцiй та збiрник задач з курсу ”Математичне моделювання“ у вiдповiдностi до програми курсу, що читається автором на фiзичному факультетi для студентiв першого та другого курсiв.

Усi задачi адаптовано з джерел, перелiчених у списку лiтератури. Для збереження досвiду, накопиченого попередниками, виклад, в основному, слiдує пiдходу [1], однак для поглибленого знайомства з предметом рекомендуються книги зi списку лiтератури, особливо [2].

Автор буде вдячний за конструктивну критику, спрямовану на покращення посiбника, а також за повiдомлення про помилки чи неточностi, якi можна надсилати за адресою charlie@mail.univ.kiev.ua.

Студентам та спiвробiтникам, якi надiслали свої коментарi та правки, автор виражає велике спасибi.

4

1. Похибки та обчислення значень

функцiй

Методи обчислень (обчислювальна математика) є математичною дисциплiною, що займається побудовою алгоритмiв для розв’язання математичних та фiзичних задач. Це важливо в тому смислi, що в природi, очевидно, немає процесiв та явищ, якi можна було б представити в виглядi моделей з абсолютною точнiстю. Результат моделювання утворюється шляхом опрацювання спостережень. Але на кожному з етапiв, коли взаємодiють прилад, явище, комп’ютер та оператор виникають похибки.

Похибки прийнято дiлити на такi категорiї:

методичнi;

заокруглення

нескiнченi ряди стають скiнченими;

точнi параметри стають неточними;

бiльшiсть дiйсних чисел представляються неточно;

неусувнi.

Робота комп’ютера завжди супроводжується появою похибок. Це пов’язано в першу чергу зi скiнченiстю розрядної сiтки комп’ютерiв. Так, згiдно iснуючого стандарту, дiйсне число повинно представлятися нормалiзованим з кiлькiстю двiйкових розрядiв пiсля коми 24 (числа типу float) або 56 (double), що дозволяє оцiнити вiдносну похибку як 2−25 ≈ 10−7 та 2−57 ≈ 10−16 вiдповiдно.

Таке непросте положення справ створює головну труднiсть чисельних методiв: як так побудувати алгоритм, щоб незважаючи на повсюдну наявнiсть похибок, отримувати результат, на який вони впливають якнайменше. Покажемо тут лише два приклади.

По-перше, будь-яка арифметична операцiя приводить до розповсюдження похибок обчислень: похибка суми рiвна сумi похибок результатiв, i т.п. Однак,

5

похибка суми ще зростає, якщо мати на увазi, що навiть правильно вирахувана сума може отримати додаткову похибку через її неточне представлення. Скорочення кiлькостi операцiй при виконаннi тих, чи iнших обчислень, є таким чином, важливою задачею. Так, при обчисленнi значення полiнома можна поступати двома способами:

P (x) = a0xn + a1xn−1 + a2xn−2 + · · · + an−1x + an,

або так

P (x) = (. . . ((a0x + a1)x + a2)x + · · · + an−1)x + an.

Другий алгоритм вiдомий як схема Горнера. Елементарний аналiз обидвох способiв показує, що якщо у другому способi загальна кiлькiсть операцiй складає n−1 множення та n додавань, то в першому способi кiлькiсть операцiй складає знову n−1 множень i n додавань, а крiм того, ще n−2 пiднесення до степеня. Строго кажучи, пiднесення до степеня не є операцiєю, воно виконується або множенням числа самого на себе (що дає нам ще n(n − 1) множень), або пiдсумовуванням рядiв, тобто xy = exp(y · ln x), кiлькiсть операцiй у цьому випадку взагалi не пiддається простому аналiзу. Очевидно, що другий алгоритм значно кращий, нiж перший: обидва видають одинаковi результати, хоча й виконують рiзну роботу.

По-друге, результати окремих спостережень повиннi правильно опрацьовуватися, щоб зменшити присутню в спостереженнях похибку. У статистицi показується, що найбiльш iмовiрним значенням спостережної величини є її середнє арифметичне, яке до того ж мiнiмiзує середньоквадратичну помилку результату (див. [1] для виведення необхiдних формул). Очевидним наслiдком цього факту є те, що значно правильнiшим є проведення одного обчислення з усередненими числами анiж усереднення обчислень, проведених з окремими спостереженнями.

Для ефективного знаходження значень функцiй використовують такi пiдходи: схема Горнера для полiномiв; степеневi ряди з рекурентними спiввiдношеннями та полiномiальнi наближення на iнтервалах для трансцедентних функцiй; iтерацiйнi схеми, ланцюжковi дроби та деякi бiльш складнi апроксимацiї, що будуть розглянутi пiзнiше.

6

Задачi. У цьому роздiлi кожна задача мiстить по одному полiному, для якого потрiбно скласти таблицю значень на iнтервалi [0.5, 2.0] з кроком 0.05 та точнiстю 10−4 та функцiональний ряд для вiдомої функцiї, значення якої потрiбно обчислити з заданою точнiстю ε для довiльного заданого x, використовуючи рекурентнi спiввiдношення мiж членами ряду, та порiвняти зi значенням, що можна отримати з вiдповiдної функцiї мови С.

1.

P (x) = 1.723x5 + 0.137x4 − 0.814x3 + 2.364x2 − 1.176x + 3.962

5.

P (x) = 0.853x5 − 1.154x4 − 0.143x3 + 1.217x2 − 2.243x + 2.415

∞ x2n

P

ch(x) =

n=0 (2n)!

6.

P (x) = 0.623x5 + 1.275x4 − 0.217x3 + 1.315x2 − 3.174x − 1.862

7

8

16.