Головна
1. Обчислювальна задача. Чисельні методи та їх особливості
2. Оцінка складності алгоритмів і обчислень
3. Похибки обчислень
4. Базові операції над матрицями і векторами
Розділ 1. Вступ до чисельних методів

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

1.1. Обчислювальна задача. Чисельні методи та їх особливості

   Серед інформаційних технологій, які лежать в основі всіх напрямів підготовки спеціалістів з комп'ютерних технологій, особливе місце займає математичне моделювання. При цьому під математичною моделлю фізичної системи, об'єкта або процесу звичайно розуміють сукупність математичних співвідношень (формул, рівнянь, логічних виразів), які визначають характеристики стану і властивості системи, об'єкта і процесу та їх функціонування залежно від параметрів їх ком-понентів, початкових умов, вхідних збуджень і часу. Загалом математична модель описує функціональну залежність між вихідними залежними змінними, через які відображається функціонування системи, незалежними (такими, як час) і змінюваними змінними (такими, як параметри компонентів, геометричні розміри та ін.), а також вхідними збудженнями, прикладеними до системи.
   Згадана функціональна залежність, що відображається математичною моделлю, може бути явною чи неявною, тобто може бути зображена або як просте алгебраїчне співвідношення, або ж як велика за розміром сумісна система диференціально-алгебраїчних рівнянь. До того, як обчислювальна техніка набула широкого розповсюдження, переважали явні функціональні моделі низьких порядків, пристосовані до можливостей розрахунків ручним способом або розрахунків з малим ступенем механізації (логарифмічна лінійка, арифмометр та ін.).
   Саме вони і є сьогодні теоретичною основою багатьох інженерних та природничих дисциплін, яка дозволяє під час проектування проводити наближені розрахунки з точністю до кількох десятих відсотка з подальшим обов'язковим макетуванням проектованого об'єкта та його експериментальним доведенням до потрібних параметрів, внаслідок чого розробка нового виробу розтягується на багато років.
   Сучасні комп'ютери дозволяють у багатьох випадках відмовитися від натурного макетування проектованих виробів, замінивши його математичним моделюванням (обчислювальним експериментом), що дуже важливо, коли натурне макетування складне або практично неможливе (наприклад, моделювання прориву дамби, переміщення всюдиходу поверхнею Марса та ін.). Але при цьому повинна бути істотно підвищена точність математичних моделей об'єктів та систем, що враховують багато фізичних ефектів та дестабілізуючих чинників, якими раніше нехтували. В результаті розмірність і складність математичних моделей істотно зростають, а їх розв'язання в аналітичному вигляді стає неможливим. Це звичайний для сучасної науки і техніки компроміс, що полягає в отриманні нової якості одного параметра (висока точність обчислювального експерименту і відмова від натурного макетування) за рахунок зменшення чи ускладнення іншого параметра (відмова від звичних для вищої математики аналітичних рішень).
   Для кожної математичної моделі звичайно формулюється математична задача. У загальному випадку, коли функціональна залежності для множини вхідних даних (значення незалежних та змінюваних змінних і вхідних збуджень), що виступають як множина аргументів, задана неявне, за допомогою математичної моделі необхідно визначити множину вихідних залежних змінних, що виступають як множина значень функцій. При цьому відповідно до виду математичної моделі розрізняють такі базові типи математичних задач:

  • розв'язання системи лінійних (в загальному випадку лінеаризованих) рівнянь;
  • розв'язання нелінійних алгебраїчних рівнянь;
  • апроксимація масиву даних або складної функції набором стандартних, більш простих функцій;
  • чисельне інтегрування і диференціювання;
  • розв'язання систем звичайних диференціальних рівнянь;
  • розв'язання диференціальних рівнянь в частинних похідних;
  • розв'язання інтегральних рівнянь.
  •    Прості математичні задачі малої розмірності, що вивчаються в курсі вищої математики, допускають можливість отримання аналітичних рішень. Складні математичні моделі великої розмірності вимагають застосування чисельних методів, що вивчаються в даному курсі.
       Чисельні методи - це математичний інструментарій, за допомогою якого математична задача формулюється у вигляді, зручному для розв'язання на комп'ютері. У такому разі говорять про перетворення математичної задачі в обчислювальну задачу. При цьому послідовність виконання необхідних арифметичних і логічних операцій визначається алгоритмом її розв'язання. Алгоритм повинен бутирекурсивним і складатися з відносно невеликих блоків, які багаторазово виконуються для різних вхідних даних.
       Слід зазначити, що з появою швидких та потужних цифрових комп'ютерів роль чисельних методів для розв'язання наукових та інженерних задач значно зросла. І хоча аналітичні методи розв'язання математичних задач, як і раніше, дуже важливі, чисельні методи істотно розширюють можливості розв'язання наукових та інженерних задач, не дивлячись на те, що самі рівняння математичних моделей з ускладненням структури сучасних виробів стають погано обумовленими та жорсткими, що істотно ускладнює їх розв'язування. Узявши виконання рутинних обчислень на себе, комп'ютери звільняють час вченого або інженера для творчості: формулювання задач і генерування гіпотез, аналізу та інтерпретації результатів розрахунку тощо.
       Чисельні методи забезпечують системний формалізований підхід до розв'язання математичних задач. Проте за умов їх ефективного використання окрім уміння присутня і деяка частка мистецтва, що залежить від здібностей користувача, оскільки для розв'язання кожної математичної задачі існує декілька можливих чисельних методів і їх програмних реалізацій для різних типів комп'ютерів. На жаль, для обрання ефективного способу розв'язання поставленої задачі лише інтуїції замало, потрібні глибокі знання і певні навички. Існує декілька переконливих причин, що мотивують необхідність глибокого вивчення чисельних методів майбутніми фахівцями у галузі комп'ютерно-системної інженерії та прикладної математики.
       Чисельні методи є надзвичайно потужним інструментарієм для розв'язання проблемних задач, що описуються довільними нелінійними диференціально-алгебраїчними рівняннями великої розмірності, для яких в даний час не існує аналітичних рішень. Освоївши такі методи, майбутній фахівець набуває здібностей до системного аналізу через математичне моделювання найскладніших задач сучасної науки і техніки.
       У своїй майбутній професійній діяльності такий фахівець у першу чергу орієнтуватиметься на використання пакетів сучасних обчислювальних програм, причому те, наскільки правильно він буде їх застосовувати, безпосередньо залежатиме від знання і розуміння ним особливостей і обмежень, властивих чисельним методам, що реалізовані в пакеті. Може трапитися, що одна й та сама математична задача за допомогою певного програмно-технічного комплексу буде одним фахівцем успішно розв'язана, а іншим — ні, оскільки в сучасних пакетах передбачено їх налагоджування для конкретної задачі.
       Може з'ясуватися, що низку задач неможливо розв'язати з використанням наявних пакетів програм. Якщо майбутній фахівець знає чисельні методи і володіє навичками програмування, він буде в змозі самостійно провести розробку необхідного алгоритму і програмне його реалізувати, вбудувавши в обчислювальний комплекс.
       Вивчення чисельних методів стимулює освоєння самих комп'ютерів, оскільки найкращим способом навчитися програмувати є написання комп'ютерних програм власноруч. Правильно застосувавши чисельні методи, майбутній фахівець зможе пересвідчитися у тому, що комп'ютери успішно розв'язують йогопрофесійні задачі. При цьому він сам відчує вплив похибок обчислень на результат і навчиться контролювати ці похибки.
       Вивчення чисельних методів сприяє також переосмисленню і більш глибокому розумінню математики в цілому, оскільки однією із задач чисельних методів є зведення методів вищої математики до виконання простих арифметичних операцій.
       Хоча існує безліч чисельних методів, усі вони (як і алгоритми, що їм відповідають) мають багато спільних властивостей і характеристик.

       Чисельні методи:

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

  • різною швидкістю збіжності, тобто числом ітерацій, виконання яких необхідне для отримання заданої точності розв'язку;
  • різною стійкістю, тобто збереженням достовірності розв'язку під час подальших ітерацій;
  • різною точністю отримуваного розв'язку в разі виконання однакового числа ітерацій або циклів обчислень.
  •    Чисельні методи розрізняються:

  • за широтою і легкістю застосування, тобто за ступенем своєї універсальності та інваріантності для розв'язання різних математичних задач;
  • за складністю їх програмування;
  • за можливостями використання у разі їх реалізації наявних бібліотек функцій і процедур, створених для підтримки різних алгоритмічних мов;
  • за ступенем чутливості до погано обумовлених (або некоректних) математичних задач, коли малим змінам вхідних даних можуть відповідати великі зміни розв'язку.
  • 1.2. Оцінка складності алгоритмів і обчислень

       У попередньому підрозділі було введено поняття алгоритму як сукупності операторів, що визначають суть і послідовність операцій, які потрібно виконати для отримання результату під час розв'язання математичної задачі. Побудова алгоритму може бути виконана розбиттям задачі на підзадачі у такий спосіб, щоб вихідні дані однієї підзадачі були вхідними для іншої.
       Найважливішою частиною підготовки задачі для комп'ютера є отримання рекурсивної формули для конкретного чисельного методу. Складність обчислень, передбачених алгоритмом, може бути оцінена за допомогою сигнальних функцій fA(n), які визначають час роботи алгоритму через кількість необхідних операцій, що використовуються алгоритмом у процесі обчислень. При цьому fA(n) — верхня межа кількості операцій; n — розмірність задачі.
       Залежно від складності розрізняють два типи алгоритмів.
      1. Поліноміальний алгоритм, сигнальна функція якого fA(n) зростає зі збільшенням п не швидше, ніж деякий поліном g(n). При цьому розрізняють оцінки двох типів (0-велике та о-маленьке) залежно від співвідношень:

    і

       Так, для алгоритму з кількістю необхідних операцій f(n) = 2n5 + 6n4 + 6n2 + 18 сигнальними можуть бути такі функції fA(n): 0(n5), о(en), о(nб), о(2n).
      2. Комбінаторний алгоритм, коли сигнальна функція fA(n) змінюється як експоненціальна функція або містить у собі оцінки операцій перебору, сполучень, визначення факторіалу n!.
       Щоб оцінити, що таке факторіал із погляду об'єму обчислень, спробуємо підрахувати час, необхідний для виконання п = 20! (20! = 24,329 • 1017) операцій, для комп'ютера з середнім часом виконання операції 10-7 с. Він становитиме більше 77 століть.
       Прикладом комбінаторного алгоритму може бути алгоритм розрахунку визначника матриці через алгебраїчну суму пі його членів, складених із усіх можливих добутків елементів матриці, взятих поодинці в кожному рядку і в кожному стовпці.
       Розглянемо п'ять різних алгоритмів за умови, що для виконання окремої операції потрібно 1 мс.
       Таблиця 1.1. Значення сигнальної функції для алгоритмів різної складності

       Припустимо, що швидкодія комп'ютера виросла в 10 разів, і перерахуємо дані таблиці.
       Таблиця 1.2. Зміна максимальних розмірностей задач у разі збільшення швидкості комп'ютера

       Зміна комп'ютера майже не відобразилася на властивостях алгоритму A5, тому слід завжди обирати для програмної реалізації найефективніший алгоритм із декількох альтернативних.
       Розглянемо процедуру оцінки складності алгоритму на прикладі рекурсивного обчислення значення полінома за схемою Горна:

    згідно з якою множина початкових коефіцієнтів полінома аi, і = 0,1,..., п перераховується в множину коефіцієнтів bi, і = 0,1,..., n відповідно до алгоритму:

    при цьому шукане значення полінома р(z) = b3.
       У разі обчислення значення полінома в загальному вигляді

    з урахуванням локальної процедури підвищення степеня його члена zі = zzi-1 кількість необхідних операцій дорівнює 2(n +1) множень і (п +1) додавань. Обчислюючи значення полінома за схемою Горна, необхідно виконати лише п множень і п додавань, тобто алгоритм Горна вдвічі ефективніший.

    1.3. Похибки обчислень

       Існують декілька джерел похибок обчислень.

  • Похибки вхідних даних і спрощення моделей компонентів.
  • Округлення під час обчислень, локальні відсікання.
  • Похибки зображення чисел у комп'ютері.
  •    Розрізняють також глобальну похибку, як різницю точного і обчисленого значень, і локальну похибку, як похибку методу, в основному обумовлену відсіканням частини ряду Тейлора, і тому обмежену значенням першого неврахованого члену цього ряду, пропорційного 0(/\x)р+1, де р — порядок методу обчислення.
       Нехай а — точне значення величини; а — наближене значення цієї величини, тоді

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

       Похибки в разі обчислення функції у = f(х) залежно від похибки аргументу Ах = x - x0 оцінюються відсіканням частини ряду Тейлора, внаслідок чого одержуємо оцінку абсолютної похибки як

    і відносної похибки як

       Для функції багатьох аргументів у = f(х1, х23,.,.,xn) формула максимальної абсолютної похибки набуває такого вигляду:

         (1.1)

       У комп'ютері числа з плаваючою комою зображуються у вигляді a = m • 10q, де 0,1 m 1 - мантиса числа, q - його порядок. Це число т розташовується у лівому краї машинного слова і містить t розрядів.
       У загальному випадку

         (1.2)

       Обумовленість конкретного алгоритму СА характеризує процес накопичення похибок під час обчислень і визначається як функція від u = 1/2 • 101-t.
       Розглядають окремо задачу прямого аналізу похибок, коли відомі: А — збурені вхідні дані та вихідні дані В = ф(A) як результат обробки за деяким точним алгоритмом Вt = ф(At), тоді М = Вt -В — похибка обчислення на комп'ютері даних В, яку потрібно оцінити. Існує і задача оберненого аналізу похибок, коли відомі дані Вt = ф(At) = ф(A + є) як результат обробки збурених даних А за точним алгоритмом і потрібно оцінити похибки вхідних даних є = At — А.
       Приклад 1.1
       Оцінимо похибку обчислення функції у = Х12 - Х2 за збурених аргументів х1 = 1,03 ±0,01, Х2 = 0,45 ± 0,01.
       Згідно з формулою (1.1)

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

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

       Як уже наголошувалося, результат обчислень залежить не тільки від обраного алгоритму розв'язання, але і від обумовленості самої обчислювальної задачі, під якою розуміють залежність максимально можливого відхилення результату від похибок вхідних даних:

         (1.3)

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

       Якщо зараз внести незначну похибку в коефіцієнт другого члена

    то серед кореній, знайдених за коефіцієнтами полінома, несподівано з'являться десять комплексних коренів.
       Для зменшення обумовленості задачі Cp необхідно змінювати форму зображення вхідних і вихідних величин математичної задачі.
       Під час реалізації практичних обчислень звичайно загально задана похибка розподіляється по кроках обчислень, а потім на кожному кроці здійснюється контроль похибки за локальною оцінкою, оскільки точні значення глобальної похибки не відомі. Тому в процедурах чисельних методів виділяють три рівноправні частини.
      1. Обчислення наближення розв'язку за рекурсивною формулою вибраного алгоритму.
      2. Оцінювання похибки.
      3. Управління продовженням розв'язування задачі.
       Згадане управління може зводитися до зміни кроку приросту аргументів не-явно заданої функціональної залежності (зокрема, часового кроку), заміни формули обчислення наближення розв'язку, зміни значень загальної заданої похибки розв'язку і допустимої кількості ітерацій. Зрозуміло, що за всіх інших умов найкращим буде розв'язок, отриманий у результаті виконання меншої кількості ітерацій. І цього можна досягти, зокрема, використовуючи так звану екстраполяцію Річардсона, яка здійснюється таким чином. Припустимо, що ми використовуємо певний алгоритм, що визначає для математичної задачі розв'язок F(h), похибка якого порівняно з точним значенням aо пропорційна кроку обчислення h у степені р. Якщо провести розрахунки двічі з різними кроками h і gh, то за допомогою отриманих рівнянь можна знайти точний розв'язок задачі, на-піть якщо кроки обчислень будуть великими:

         (1.4)

       З формул (1.4) можна отримати значення оцінки глобальної похибки обчислень через різницю двох приблизних розв'язків з урахуванням порядку р використаного методу:

         (1.5)

    1.4. Базові операції над матрицями і векторами

       Більшість математичних моделей складних об'єктів та систем зручно записувати у вигляді векторно-матричних рівнянь. Нагадаємо основні положення векторно-матричного аналізу, які будуть потрібні нам для подальшого розгляду чисельних методів.
       Система mхn чисел (дійсних чи комплексних), які розташовані у прямокутній таблиці, що складається з т рядків та n стовпчиків

    називається матрицею. Числа

       Якщо n = m, то матрицю називають квадратною порядку n, а в загальному випадку ЇЇ називають прямокутною розміром mхn.
       Квадратна матриця А називається симетричною, якщо aij = aji.
       Елементи одиничної матриці Е визначаються як

    де dji називають символом Кронекера.
       Визначник (детермінант) матриці обчислюється зі співвідношення:

         (1.6)

    де операція підсумовування поширена на всі можливі перестановки (a1, a2, ..., an) елементів послідовності 1, 2.....п і містить п! доданків, причому X = 0, якщо перестановка парна, і X ^ 0 (х = 1), якщо вона непарна. Квадратну матрицю А називають неособливою (несингулярною), якщо det А^0. У разі det A = 0 матриця А —особлива або вироджена.
       До матриць застосовні операції транспонування і обернення. Транспонуванням матриці називається заміна її рядків стовпцями. Транспонована матриця позначається як АT.
       Обернена матриця А-1 визначається як матриця, множення якої зліва або справа на матрицю А дає одиничну матрицю: А-1А = АА-1 = E.
       Елементи оберненої матриці А-1 підраховуються за формулою Якобі:

         (1.7)

    де A1 - приєднана матриця, що складається з алгебраїчних доповнень Aij елементів початкової матриці aij, які дорівнюють визначнику матриці, одержуваної з початкової матриці А викресленням рядка i і стовпця j, причому знак Aij визначається парністю суми індексів елемента i та j.
       Дійсна матриця А називається ортогональною, якщо ЇЇ транспонована матриця Ат збігається з оберненою матрицею А-1, тобто

    АT = А-1, або ААT = E.

       Дві матриці (А і В), які здійснюють однакові лінійні перетворення в різних базисах, називаються подібними (А ~ В). Дві матриці подібні тоді і лише тоді, коли одну можна отримати з іншої перетворенням за допомогою якоїсь ортогональної матриці Q, тобто В = Q-1AQ.
       Теорема. Якщо дана квадратна матриця порядку n має n лінійно незалежних власних векторів, то, взявши останні за базисні, отримаємо діагональну матрицю, подібну до даної.
       Наслідок. Будь-яку квадратну матрицю, власні значення якої попарно різні, перетворенням подібності можна звести до діагональної, тобто A = Q-1DQ, де D — діагональна матриця власних значень матриці А, причому власні значення Ai і власні вектори X1 матриці Апов'язані за допомогою відомого співвідношення: