Черкаси 2009 1 страница

 

Deutsche Vierteljahrschrift fuer Literatur und Geistesgeschichte. Статті: W. Brecht, W. Bietak, P. Kluckhohn, G. Weydt, IX (1931), XII (1934), 13 (1935) — І. Панькевич «Праці укр. іст.-філ. товариства в Празі», III (1941). — Про натуралізм: В. Виноградов: Гоголь и натуральная школа. 1925; Этюды о етиле Гоголя. 1926; Эволюция русского натурализма. 1929 (деякий матеріял з «укр. школи» в російській літературі). — D. Cizevsky: Outline, to. 94 — 97.

 

 

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

ЧЕРКАСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

Ім. Богдана Хмельницького

ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

ТА БІОМЕДИЧНОЇ КІБЕРНЕТИКИ

Супруненко О.О.

ЧИСЕЛЬНІ МЕТОДИ

В ІНФОРМАТИЦІ

Курс лекцій

для студентів, які навчаються за напрямами підготовки

050101 „Комп‘ютерні науки ” та 050103 „ Програмна інженерія ”

Черкаси 2009

 

УДК 519.6, 004.423

ББК 22.19

 

Рецензенти: Онищенко Б.О., кандидат фізико-математичних наук,

доцент кафедри математичного і програмного забезпечення автоматизованих систем Черкаського національного університету імені Богдана Хмельницького;

Данченко О.Б., кандидат технічних наук, доцент кафедри адміністрування бізнесу Університету економіки і права «Крок».

 

Супруненко О.О.

Чисельні методи в інформатиці. Курс лекцій: для студентів, які навчаються за напрямами підготовки 050101 „Комп‘ютерні науки ”, 050103 „Програмна інженерія ”. – Черкаси: ЧНУ, 2009. – 130 с.

 

ISBN 978-966-353-143-4

 

У курсі лекцій з дисципліни „Чисельні методи в інформатиці ” розгля­даються особливості отримання чисельних розв‘язків задач найбільш розповсюджених у моделюванні обчислювальних систем та систем керування технологічними процесами, оцінка похибок чисельного розв‘язку, поняття стійкості та коректності постановки задачі.

У першій частині курсу лекцій розглядаються точні та наближені методи розв’язання лінійних рівнянь, ітераційні методи розв‘язання систем нелінійних та трансцендентних рівнянь, методи інтерполяції поліномами і сплайнами, методи обробки експериментальних даних.

У другій частині курсу лекцій викладені методи чисельного диферен­ціювання та інтегрування, одно- й багатокрокові методи розв‘язання задачі Коші, сіткові методи розв‘язання крайових задач для звичайних диференційних рівнянь.

Кожна з тем має контрольні питання. У додатку наведена інформація по застосуванню внутрішньої мови програмування середовища автоматизації математичних розрахунків МatLab для створення програм, що реалізують розглянуті чисельні методи.

Матеріали курсу лекцій спрямовані на освоєння прикладних аспектів застосування чисельних методів в інженерній практиці. Дані лекції використовуються у навчальному процесі – при вивченні дисципліни “Чисельні методи в інформатиці ”, що викладається автором для студентів бакалаврату напрямів підготовки “Програмна інженерія ” та “Комп‘ютерні науки ” факультету інформаційних технологій та біомедичної кібернетики Черкаського національного університету імені Богдана Хмельницького.

Зміст

Передмова. 5

 

Частина 1. Чисельні методи розв‘язання систем лінійних та нелінійних рівнянь. Інтерполяція та наближення функцій. 6

 

Розділ 1. Чисельні методи розв‘язання задач. Похибки чисельного розв‘язку. 6

1.1. Основні поняття. 7

1.2. Поняття стійкості та коректності задачі 8

1.3. Похибки результату чисельного розв‘язання задачі 10

Контрольні питання. 13

Розділ 2. Розв‘язання функціональних рівнянь з однією змінною.. 14

2.1. Етап 1: відокремлення коренів. 16

2.2. Етап 2: уточнення коренів. 18

2.2.1. Метод половинного ділення. 18

2.2.2. Метод хорд. 19

2.2.3. Метод січних. 20

2.2.4. Метод дотичних (Ньютона) 21

2.2.5. Метод простої ітерації 23

Контрольні питання. 24

Розділ 3. Прямі та непрямі методи розв’язання систем лінійних алгебраїчних рівнянь. Методи Гауса та LU-розкладу. 25

3.1. Основні поняття. 25

3.2 Прямі методи розв‘язання систем лінійних алгебраїчних рівнянь. 26

3.2.1. Метод Гауса. 26

3.2.2. Метод LU-розкладу. 28

3.2.3. Зв‘язок методу Гауса з методом LU - розкладу. 29

3.3 Непрямі методи розв‘язання систем лінійних алгебраїчних рівнянь. 32

3.3.1. Забезпечення збіжності ітераційного процесу. 32

3.3.2. Метод простої ітерації та метод Зейделя для розв‘язання систем лінійних алгебраїчних рівнянь 33

3.3.3. Метод релаксації для розв‘язання систем лінійних алгебраїчних рівнянь 34

Контрольні питання. 35

Розділ 4. Розв‘язання систем нелінійних рівнянь. Метод Ньютона. 36

Контрольні питання. 40

Розділ 5. Інтерполяція функцій. Інтерполяційні поліноми Лагранжа. Сплайн-інтерполяція 41

5.1. Кусково-лінійна інтерполяція. Інтерполяційні поліноми вищих порядків. Інтерполяційний поліном Лагранжа. 43

5.2. Сплайн-інтерполяція. 46

Контрольні питання. 51

Розділ 6. Апроксимація експериментальних даних. Метод найменших квадратів. Інтерполяція функцій за допомогою ортогональних поліномів. 52

6.1. Апроксимація експериментальних даних. Метод найменших квадратів. 52

6.2. Інтерполяція функцій ортогональними поліномами. 54

6.3. Базисні сплайни (В-сплайни) 57

Контрольні питання. 61

 

Частина 2. Чисельне диференціювання та інтегрування. Роз‘вязання диференційних рівнянь. 62

 

Розділ 7. Чисельне диференціювання та чисельне інтегрування. 62

7.1. Чисельне диференціювання. 62

7.1.1. Використання скінченних різниць. 62

7.1.2. Чисельне диференціювання на основі інтерполяційної формули Лагранжа 65

7.1.3. Застосування похідних. 66

7.2. Чисельне інтегрування. 67

7.2.1. Квадратурні формули інтерполяційного типу. 69

7.2.2. Замкнуті формули квадратури Ньютона-Котеса. 70

Контрольні питання. 71

Розділ 8. Чисельні методи розв’язання задачі Коші для звичайних диференційних рівнянь 73

8.1. Основні поняття. 73

8.2. Явний метод Ейлера. 76

8.3. Неявний метод Ейлера. 78

8.4. Модифікації методу Ейлера. 80

8.5. Метод Гюна. 83

8.6. Метод рядів Тейлора. 84

8.7. Методи Рунге-Кутта. 85

Контрольні питання. 88

Розділ 9. Багатокрокові методи розв’язання диференційних рівнянь в частинних похідних 90

9.1. Метод Адамса-Бешфорса-Маултона. 90

9.2. Метод Мілна-Сімпсона. 93

9.3. Метод Хеммінга. 95

9.4. Обмеження при застосуванні методів прогнозу-корекції 96

Контрольні питання. 98

Розділ 10. Крайові задачі для звичайних диференційних рівнянь. Методи сіток. 99

10.1. Основні поняття. 99

10.2. Методи сіток. 101

10.2.1. Метод кінцевих різниць. 102

10.2.2. Метод кінцевих елементів. 109

10.2.3. Алгоритм методу кінцевих елементів. 112

Контрольні питання. 119

 

Додаток А. Короткі теоретичні відомості по програмуванню в інтегрованій системі автоматизації математичних розрахунків MatLab. 120

Додаток Б. Пакети прикладних програм інтегрованої системи автоматизації математичних розрахунків MatLab. 126

Список літературних джерел. 130

Передмова

 

Підготовка інженерних кадрів передбачає набуття практичних навичок у вирішенні прикладних задач, які пов‘язані з конкретної областю техніки відповідно спеціальності. При підготовці інженерів-програмістів основна увага приділяється вивченню теоретичного матеріалу та його реалізації у практичних задачах при моделюванні та створенні програмних продуктів для автоматизації різноманітних технологічних процесів, при створенні інформаційно-аналітичних комплексів для управління організаційними структурами.

Підпорядковуючись основним задачам навчання програмістів, даний лекційний курс передбачає вивчення чисельних методів, які використовуються при створенні моделей динамічних систем, обробці результатів експериментальних даних, управлінні обчислювальними процесами. Курс лекцій вміщує чисельні методи, які необхідно знати і вміти застосовувати кожному інженеру та науковцю-досліднику, що є фахівцем в області інформаційних технологій.

Знайомлячись із матеріалом даної дисципліни та вивчаючи особливості конкретних чисельних методів студент не може повною мірою зрозуміти особливості функціонування алгоритмів методів та накопичення похибок результатів без самостійної програмної реалізації даних алгоритмів. Тому реалізацію чисельних методів у даному курсі пропонується здійснювати в системі Matlab (корпорації The MathWorks, Inc. (США)), що має внутрішню мову програмування та найбільшу бібліотеку чисельних методів NAG Foundation Toolbox, яка створена групою The Numerical Algorithms Group Ltd. і на даний момент нараховується більше 400 функцій у вигляді m –файлів.

Система автоматизації математичних розрахунків Matlab дозволяє використовувати сотні пакетів прикладних програм, найвідоміші з яких Symbolic Math Toolbox, Spline Toolbox, Statistics Toolbox, Optimization Toolbox, Fizzy Logic Toolbox, Neural Networks Toolbox, Partial Differencial Equations Toolbox та ін. Система Matlab має підсистему імітаційного моделювання Simulink for Windows, яка дозволяє виконувати блочне, імітаційне та ситуаційне моделювання різних систем та пристроїв, має спеціальний інструментарій для візуалізації результатів розрахунків.

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

Частина 1. Чисельні методи розв‘язання систем лінійних та нелінійних рівнянь. Інтерполяція та наближення функцій.

Розділ 1. Чисельні методи розв‘язання задач. Похибки чисельного розв‘язку

 

У сучасних математичних дослідженнях надзвичайно важливим завданням є отримання числових розв‘язків задач, які використовуються в моделях реальних фізичних об‘єктів та систем.

В більшості галузей сучасної науки і техніки часто зустрічаються математичні задачі, які не можливо точно розв‘язати класичними методами або такий розв‘язок отримується у складному вигляді, абсолютно не прийнятному для практичного використання. Наприклад, досить часто необхідно розв‘язувати системи лінійних алгебраїчних рівнянь з десятками і сотнями невідомих. Розповсюдженим є і знаходження коренів алгебраїчних рівнянь високого порядку та коренів трансцендентних рівнянь. Нерідко приходиться мати справу з розв‘язанням систем диференційних рівнянь, які не інтегруються в елементарних функціях.

Кількість таких задач значно зросла у зв‘язку з бурхливим розвитком науки і техніки з одного боку, і можливістю застосуванням розроблених теорій в машинних моделях, які формуються та функціонують у комп‘ютерному варіанті.

Комп‘ютерну техніку використовують не тільки для побудови математичних моделей, а і для ефективного розв‘язання задач, що пов‘язанні з функціонуванням даних моделей. У зв‘язку з цими потребами виділилась область математики, яка покликана розробляти методи отримання числових результатів основних задач математичного аналізу, алгебри та геометрії, а також шляхи використання з цією метою сучасних комп‘ютерних засобів. Ця область математики отримала назву чисельні методи.

З початку застосування комп‘ютерної техніки швидкість розрахунків зросла з 0, 1 = 10 ^-1 операцій в секунду при ручному розрахунку до 10⁹ ¸ 10¹¹ операцій в секунду на сучасній комп‘ютерній техніці [1].

У зв‘язку з бурхливим розвитком комп‘ютерної техніки постали задачі математизації різних розділів науки: хімії, біології, економіки, геології, географії, психології, медицини, численних галузей техніки. Процес математи­зації полягає у побудові математичних моделей процесів і явищ та в розробці методів їх дослідження.

Застосування комп‘ютерної техніки та розширення технічної і математичної освіти різко збільшило можливості побудови й дослідження математичних моделей. Все частіше результати розрахунків дозволяють виявити і передбачити явища, що раніше не спостерігалися, що можливо завдяки виникненню і розвитку машинного (комп‘ютерного) експерименту.

Вимоги до чисельних розв‘язків нових задач привели до появи великої кількості нових чисельних методів, систематизації та переосмислення давніх методів. Застосування комп‘ютерної техніки і технологій привело до:

· збільшення швидкості отримання розв‘язків, розширення пам‘яті, вдосконалення структури та технічних засобів обчислювальної техніки;

· розробки програмних засобів спілкування є комп‘ютером (операційні системи, мови програмування, бібліотеки і пакети прикладних програм);

· поглиблення розуміння процесів і явищ науки й техніки, природи і суспільства, створення їх математичних моделей;

· вдосконалення методів розв‘язання традиційних математичних і прикладних задач, створення методів розв‘язання нових задач;

· росту розуміння можливостей застосування комп‘ютерної техніки, розширення комп‘ютерної грамотності.

Ефект, що досягається вдосконаленням чисельних методів, за порядком дорівнює ефекту, що досягається за рахунок ефективності комп‘ютерної техніки. В наш час стрімко розвиваються багатопроцесорні та багатомашинні обчислювальні системи, що обумовлює необхідність розпаралелювання задач, в тому числі й задач, що реалізують чисельні методи. Тому перспективними є дослідження в області чисельних методів, що дозволять проводити ефективне розбиття задачі на підзадачі та будувати оцінки їх ефективності по часу та іншим критеріям.

1.1. Основні поняття

 

Розв‘язати задачу в класичній математиці означає довести існування розв‘язку і знайти його точне значення.

При чисельному розв‘язку задачі потрібно також довести існування розв‘язку і запропонувати ітераційний процес, який збігається до розв‘язку зі заданою точністю.

Рис. 1.1. Точність розв‘язання задачі чисельними методами

визначається e-околом.

 

Поняття заданої точності в чисельних методах продемонструємо графічно. Навколо точки А, що відображає точний розв‘язок задачі, окреслимо коло радіусом e, тобто e-окіл. При обчисленні чергового значення змінних х₅ та у₅, що визначають положення точки розв‘язку n₅ , яка першою з проміжних результатів обчислень n_і входить в e-окіл, отримуємо результат чисельного розрахунку задачі з точністю e.

Для прикладного математика і програміста, що працює у певній галузі науки чи техніки, важливо, щоб процес розв‘язку не потребував великих витрат часу і комп‘ютерної пам‘яті. Для нього важливі також питання, пов‘язані зі стійкістю результатів відносно збурень початкових даних і округленнями при обчисленнях.

 

1.2. Поняття стійкості та коректності задачі

 

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

Задача називається стійкою за вхідними даними, якщо її розв‘язок неперервно залежить від вхідних даних, тобто малому приросту вхідної величини відповідає малий приріст розв‘язку .

При невиконання даної умови задача вважається не стійкою, що означає – зміни, навіть незначні, у вхідних даних можуть привести до як завгодно великих похибок розв‘язку. Застосування до розв‘язання таких задач чисельних методів є недоцільним, оскільки поточні похибки будуть накопичуватися при виконанні ітерацій і не дозволять отримати розв‘язок із заданою (чи обмеженою) точністю.

Нестійким також може бути чисельний метод розв‘язання задачі. Для усунення такої нестійкості вносять зміни до алгоритму методу, чи пред‘являють жорсткі вимоги до обчислювальної похибки (похибки округлення). Наприклад, обчислимо інтеграл:

При інтегруванні за частинами отримаємо:

Обчислимо значення інтегралу для :

Значення є помилковим, оскільки підінтегральна функція у всіх точках відрізку є невід’ємною. Дана помилка викликана похибкою округлення: для ; …; для . Істинне значення з трьома значу­щими цифрами після коми дорівнює 0, 0916.

Ще одним важливим поняттям є коректність постановки задачі.

Задача називається коректно поставленою, якщо для будь-яких вхідних даних з деякого класу існує єдиний і стійкий за вхідними даними розв‘язок.

Для розв‘язку некоректно поставлених задач застосовувати звичайні чисельні методи не варто, оскільки похибки округлень при розрахунках можуть катастрофічно зростати, спотворюючи результати розв‘язання задачі. Для розв‘язання таких задач використовують так звані методи регуляризації [2], які замінюють дану задачу коректно поставленою.

 

1.3. Похибки результату чисельного розв‘язання задачі

 

Похибки результату чисельного розв‘язання задачі поділяються на три групи [1, 3], розподіл по яких обумовлений наступними причинами:

· математичний опис задачі є неточним (неточно задані початкові дані, не всі характеристики об‘єкта моделювання відображені в моделі, та ін.) – з цієї причини виникає незнищенна похибка,

· застосований для розв‘язання задачі метод не є точним – виникає похибка методу,

· при введенні даних, виконанні арифметичних операцій, при виведенні результатів проводяться округлення, що викликає обчислювальну похибку.

Наприклад, розглянемо модель математичного маятника (рис. 2), який починає рух в момент часу . Знайти кут відхилення j від вертикального положення в момент часу .

Диференційне рівняння, що описує коливання маятника записується у вигляді:

(1.1)

де – довжина маятника; – коефіцієнт тертя; – прискорення сили тяжіння. В описі задачі є незнищенна похибка – реальне тертя залежить від швидкості і не є лінійним (лише наближається до лінійного); визначення параметрів не є точним.

Рис. 1.2. Математичний маятник.

 

Незнищенна похибка , де – точне значення невідомої.

Диференційне рівняння (1.1) не розв‘язується в явному вигляді, тому для розв‘язку застосовуємо чисельний метод, що має похибку методу:

Обчислення проводяться з кінцевою кількістю розрядів чисел, що викликає обчислювальну похибку:

Повну похибку розв‘язку запишемо у вигляді:

.

Абсолютна і відносна похибки. Якщо а – точне значення деякої величини, й а* – відоме наближення до нього, то абсолютна похибка наближеного значення а* є . Відносна похибка наближеного значення розраховується як .

Відносну похибку часто виражають в процентах. Наведемо приклади з розрахунку абсолютної і відносної похибок:

1)

 

2)

 

3)

У першому прикладі різниця між значеннями абсолютної і відносної похибки невелика, тому можемо використовувати будь-яку з них.

У другому та третьому прикладах, в яких значення параметру значно відрізняється від одиниці в більший чи менший бік, відносна похибка d є кращим індикатором точності наближень, аніж абсолютна похибка D. Тому в таких випадках для оцінки точності наближень значень рекомендується використовувати відносну похибку [4].

Число р* є наближенням р з d знаками (цифрами) після коми, якщо d є найбільшим позитивним цілим числом, для якого виконується умова [5]:

.

Визначимо число значущих цифр для наближень у прикладах 1¸ 3:

1)

Наближення х* до точного значення х виконано з двома значущими цифрами: .

 

2)

Наближення у* до точного значення у виконано з п‘ятьма значущими цифрами: .

 

3)

Наближення z* до точного значення z виконано без значущих цифр: .

Контрольні питання

1. Яка причина виділення окремої області математики – чисельних методів?

2. В чому полягає відмінність розв‘язання задач класичними методами математики та чисельними методами?

3. Які чинники пов‘язують розвиток чисельних методів та комп‘ютерної техніки й технологій?

4. Що значить розв‘язати задачу з точністю e?

5. Яка задача називається стійкою за вхідними даними?

6. Яка задача є коректно поставленою?

7. На які групи поділяються похибки чисельних розв‘язків і які причини викликають їх виникнення?

8. В яких випадках і чому оцінка похибки проводиться за абсолютною похибкою?

9. В яких випадках оцінка похибки проводиться за відносною похибкою?

10. Що значить знайти розв‘язок задачі з n значущими цифрами?

Розділ 2. Розв‘язання функціональних рівнянь з однією змінною

 

Важливу задачу прикладного аналізу представляє розв’язок функціональних рівнянь з однією змінною, які застосовуються при описі математичних моделей у фізиці, механіці, економіці та інших науках та прикладних галузях.

У загальному вигляді функціональне рівняння записується у вигляді:

(2.1)

де F(х) визначена і неперервна на скінченому чи нескінченному інтервалі [a, b].

Число називається коренем r кратності, якщо воно задовольняє рівнянням:

(2.2)

Однократний корінь називається простим.

Два рівняння F(х) та G(х) називаються рівносильними, якщо будь-який розв’язок кожного з них є розв’язком і для другого.

Функціональні рівняння поділяються на алгебраїчні, якщо функція є алгебраїчною (наприклад: ), та трансцендентні, якщо функція вміщує логарифмічні, тригонометричні та інші неалгебраїчні функції (наприклад: ). Алгебраїчні рівняння поділяються на лінійні й нелінійні. У лінійних рівняннях змінна має лише перший ступінь, а у нелінійних – змінна представлена у першому, другому чи вищих ступенях.

Шляхом алгебраїчних перетворень із будь-якого алгебраїчного рівняння можна отримати рівняння в канонічній формі:

(2.3)

де n – ступінь алгебраїчного рівняння.

Кожне алгебраїчне рівняння має хоча б один дійсний корінь чи пару комплексних.

При зведенні алгебраїчного рівняння до канонічної форми отримаємо ті ж корені, що і для початкового рівняння, але при цьому можуть з’явитися сторонні корені. Наприклад:

(2.4)

Якщо функція F(х) не є алгебраїчною, то рівняння (2.1) називається трансцендентним. Наприклад:

(2.5)

В деяких випадках розв’язування трансцендентних рівнянь зводиться до розв’язання алгебраїчних.

Більшість функціональних рівнянь з однією змінною не розв’язуються точними методами шляхом аналітичних перетворень. До того ж, більшість функціональних рівнянь є математичними моделями певних об‘єктів чи явищ, вказати точні параметри (коефіцієнти) яких неможливо. Тому на практиці для їх розв’язання застосовують чисельні методи, більшість з яких є наближеними і дозволяє знайти розв‘язок з певною наперед заданою точністю.

У теорії чисельних методів розв’язати рівняння – значить встановити, чи має воно корені на вказаному проміжку, з‘ясувати кількість коренів, відшукати значення всіх виявлених коренів із заданою точністю, тобто корені мають знаходитися у e-околі точного розв‘язку.

Задача чисельного знаходження дійсних і комплексних коренів рівняння зазвичай складається з двох етапів:

· відокремлення коренів – знаходження достатньо малих околів у заданій області, в кожному з яких знаходиться тільки один корінь,

· уточнення коренів – обчислення коренів із заданим ступенем точності e в деякому околі (e-околі, п. 1.1.).

Для знаходження дійсних коренів рівняння (2.1) застосовується ряд методів, серед яких частіше використовують такі чисельні методи:

§ метод половинного ділення (бісекції);

§ метод хорд;

§ метод січних;

§ метод дотичних (Ньютона);

§ комбінований метод;

§ метод Рибакова, знаходження всіх дійсних коренів;

§ метод Ейткена-Стеффенсона;

§ метод зворотної квадратичної інтерполяції-екстраполяції;

§ метод порозрядного наближення;

§ метод простої ітерації.

При застосуванні вищенаведених методів важливо забезпечити збіжність їх до розв’язку. По швидкості збіжності до розв‘язку розрізняють:

· методи поступового обмеження інтервалу пошуку кореня (методи половинного ділення), ці методи повільно сходяться до розв‘язку;