69317

ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ ТА ЙОГО ЕТАПИ

Лекция

Математика и математический анализ

В результаті розміри і складність математичних моделей істотно зростають а їх розв’язок в аналітичному вигляді стає неможливим. розв’язок системи лінійних в загальному випадку лінеаризованих рівнянь; 2. розв’язок нелінійних алгебраїчних рівнянь...

Украинкский

2014-10-03

308 KB

0 чел.

Лекція 1.

ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ ТА ЙОГО ЕТАПИ.

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

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

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

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

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

1. розв’язок системи лінійних (в загальному випадку, лінеаризованих) рівнянь;

2. розв’язок нелінійних алгебраїчних рівнянь;

3. апроксимація масиву даних або складної функції набором стандартних, більш простих функцій;

4. чисельне інтегрування і диференціювання;

5. розв’язок систем звичайних диференціальних рівнянь;

6. розв’язок диференціальних рівнянь в частинних похідних;

7. розв’язок інтегральних рівнянь.

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

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

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

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

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

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

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

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

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

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

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

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

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

Чисельні методи характеризуються:

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

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

3. різною точністю отримуваного розв’язку при виконанні однакового числа ітерацій або циклів обчислень.

Чисельні методи розрізняються:

4. по широті і легкості застосування, тобто по ступеню своєї універсальності та інваріантності для розв’язку різних математичних задач;

5. по складності їх програмування;

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

7. по ступеню чутливості до погано обумовлених (або некоректних) математичних задач, коли малим змінам вхідних даних можуть відповідати великі зміни одержуваного розв’язку.

1.2. Оцінка складності алгоритмів і обчислень

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

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

По складності розрізняють два типи алгоритмів:

1. Поліноміальний алгоритм, сигнальна функція якого fA (n) росте від n не швидше, ніж деякий поліном g(n). При цьому розрізняють оцінки двох типів (Овелике та о–маленьке) залежно від співвідношень:

fA (n) = O [g(n)]  і fA (n) = о [g(n)] 

Так, для алгоритму з кількістю необхідних операцій f (n) = 2n5 + 6n4 + 6n2 + 18

сигнальною можуть бути такі функції fA (n): О(n5), o(en), о(n6), о(2n).

2. Комбінаторний алгоритм, коли сигнальна функція fA(n) змінюється як експоненціальна функція або містить в собі оцінки операцій перебору, сполучень, визначення факторіалу n!

Щоб оцінити, що таке факторіал з погляду об'єму обчислень, спробуємо підрахувати час, необхідний для виконання n = 20! операцій, для комп'ютера з середнім часом виконання операції 10 - 7сек: 20! = 21018сек (або 70 століть)

Прикладами комбінаторних алгоритмів може бути алгоритм розрахунку визначника матриці через алгебраїчну суму n! його членів, складених з всіх можливих добутків елементів матриці, узятих поодинці в кожному рядку і в кожному стовпці.

Розглянемо п'ять різних алгоритмів за умови, що окрема операція вимагає час 1 мс:


Алгоритм

Часова складність

Максимальний розмір задачі

1 с.

1 хв.

1 год.

A1

n

1000

6104

3.6106

A2

n log n

140

4893

2106

A3

n2

31

244

1897

A4

n3

10

39

153

A5

2n

9

15

21

Припустимо, що швидкодія комп'ютера виросла в 10 разів, і перерахуємо дані таблиці:

Алгоритм

Часова складність

Максимальний розмір задачі

До прискорення

Після прискорення

A1

n

S1

10S1

A2

n log n

S2

10S2

A3

n2

S3

3.6S3

A4

n3

S4

2.15S4

A5

2n

S5

S5 + 3.3

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

Розглянемо процедуру оцінки складності алгоритму на прикладі рекурсивного визначення значення полінома по схемі Горна:

,

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

при цьому шукане значення полінома p(z) = b3.

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

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

Дано: ai, z. Знайти: P(z).

Крок 0 (ініціалізація) b: = a0;

Крок 1 (перевірка). Якщо i : = n, то stop.

Крок 2 (визначення кожного числа). Для i від 1 до n з кроком 1 виконати bi: = ai + zbi - 1.

Таж інформація міститься у відображенні алгоритму за допомогою структурної схеми, яка майже співпадає із структурною схемою відповідної програми (Рис. 1.1)

Рис. 1.1. Структурна схема алгоритму Горна

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

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

1. Похибки вхідних даних і спрощення моделей компонентів;

2. Округлення під час обчислень, локальні відсікання;

3. Похибки представлення чисел в комп'ютері.

Розрізняють також глобальну похибку як різницю точного і обчисленого значень і локальну похибку як похибку методу, в основному обумовлену відсіканням частини ряду Тейлора, і тому обмежену значенням першого неврахованого члена цього ряду, пропорційного a1hp + 1, де р — порядок методу обчислення.

Нехай а точне значення величини;   наближене значення цієї величини, тоді

  абсолютна похибка;

— відносна похибка.

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

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

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

 (1.1)

В комп'ютері числа з плаваючою комою представляються у вигляді а = m10q, де
0,1  m  1  мантиса числа, q його порядок. Це число m розташовується по лівому краю машинного “слова” і містить t розрядів.

 В загальному випадку

 (1.2)

Обумовленість конкретного алгоритму CA характеризує процес накопичення помилок при обчисленнях і визначається як функція від u = 1/2∙101 - t.

Розглядають окремо випадок прямого аналізу помилок, коли відомі: А — збурені вхідні дані і вихідні дані В = (A) як результат обробки по деякому точному алгоритму \Bt = (At), тоді M = Bt - B — помилка обчислення на комп'ютері даних В, яку потрібно оцінити. Існує і випадок зворотного аналізу помилок, коли відомі дані Bt = (At) = (A + E) як результат обробки збурених даних А по точному алгоритму і потрібно оцінити помилки вхідних даних E = At - А.

Приклад 1.1.

Оцінимо похибку обчислення функції y = x12 - x2 при збурених аргументах
x
1 = 1,03  0,01; x2 = 0,45  0,01.

Згідно формули (1.1)

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

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

 (1.3)

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

Приклад 1.2.

Сформуємо слідом за Уїлкінсоном Д.[33] поліном 20–го порядку, вибравши його корені як числа натурального ряду:

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

а19 = 210  (210 + 2 - 23) = 210 000 000 119,

то серед коренів, знайдених по коефіцієнтах полінома, несподівано з'являться комплексні корені xi,i + 1 = 16,730737400  j 2,812624894.

Для зменшення обумовленості задачі Cp необхідно змінювати форму представлення вхідних і вихідних величин математичної задачі.

Розглянутий процес накопичення похибок з внесками в нього обумовленості алгоритму і самої задачі можна відобразити в графічному вигляді (Рис. 1.2).

Рис. 1.2. Складові процесу накопичення похибки

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

1. обчислення наближення розв’язку за рекурсивною формулою вибраного алгоритму;

2. оцінка похибки;

3. управління продовженням розв’язку задачі.

Згадане управління може зводиться до зміни кроку приросту аргументів неявно заданої функціональної залежності (зокрема, часового кроку), заміни формули обчислення наближення розв’язку, до зміни значень загальної заданої похибки розв’язку і допустимої кількості ітерацій. Зрозуміло, що за всіх інших умов найкращим буде розв’язок, отриманий за меншу кількість ітерацій. І цього можна досягти, зокрема, використовуючи так звану екстраполяцію Річардсона, яка полягає у наступному. Припустимо, що ми використовуємо певний алгоритм, що визначає для математичної задачі розв’язокF(h), який відрізняється від точного значення a0 на похибку, пропорційну кроку обчислення h в степені p. Якщо провести розрахунки двічі з різними кроками h і qh, то з отриманих рівнянь можна знайти точний розв’язок задачі навіть при значних за розміром кроках обчислень:


ao = F(h) + +  + 0((). (1.4)

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

= ao - F(h) =  (1.5)

Приклад 1.3.

Знайти значення інтеграла , користуючись формулою суми площ трапецій , на які розбивається при виборі кроку площа під графіком підінтегральної функції, для у = f(x) = x3. Проводячи розрахунки двічі при h = 1 і qh = 2, з урахуванням p = 2 (тому що трапецеїдальна апроксимація співпадає з методом першого порядку і її точність пропорційна квадрату кроку розбиття), одержуємо дані, зведені в таблицю 1.1.

Таблиця 1.1. Чисельне визначення інтегралу

f(x) = x3

f (x)

x3

f(10)

1000

f(11)

1331

f(12)

1728

Т| h = 1

2695

Т| h = 2

2728

Екстраполяція

2684

Точне значення

2684

Як бачимо, композиція двох дуже простих, але неточних апроксимацій площі під графіком (прямокутником при qh = 2 і сумою двох трапецій при h = 1) дала дуже пристойний результат.

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

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

Визначення. Нехай е1, е2., еn і 1 2. n два базиси одного лінійного простору Еn. Кожний вектор нового базису j має в старому (першому) базисі e деякі координати
s1j, s2j.., snj, тобто

j = s1j е1 + s2j е2 + … + snj еn (j = 1,2,…,n).

Неособлива матриця S = [sij] називається матрицею переходу від старого базису до нового. Нехай х вектор в старих координатах е1, е2,.., еn, а y  той же вектор в нових координатах 1 2.. n. Тоді x = Ау у = А - 1x, якщо існує обернена матриця переходу.

Матрицю А відображають у вигляді прямокутної таблиці чисел:

,

де елементи матриці aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) — числа з множини дійсних або комплексних чисел. Якщо n = m, то матрицю називають квадратною порядку n, а в загальному випадку її називають прямокутною розміром [m,n].

Квадратна матриця А називається симетричною, якщо

.

Елементи одиничної матриці Е визначаються як

, де

де δij називають символом Кронекера.

До матриць застосовні операції транспонування і обернення. Транспонуванням матриці називається заміна її рядків стовпцями. Транспонована матриця позначається AT.

Обернена матриця A - 1 визначається як матриця, множення якої як зліва, так і справа на матрицю А дає одиничну матрицю:

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

, (1.6)

де операція підсумовування поширена на всі можливі перестановки (a1, a2,…, an) елементів послідовності 1,2., n і містить n! доданків, причому χ = 0, якщо перестановка парна, і χ ≠ 0 ( = 1), якщо вона непарна. Квадратну матрицю А називають неособливою (несингулярною), якщо det A0. В разі det A = 0 матриця А  особлива або вироджена.

Елементи оберненої матриці A - 1 підраховуються за формулою Якобі:

, (1.7)

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

Визначення. Дійсна матриця А називається ортогональною, якщо її транспонована матриця AT співпадає із оберненою А - 1, тобто

= А - 1, або А = Е.

Ортогональна матриця має такі властивості:

1. Стовпці ортогональної матриці попарно ортогональні (їх скалярні добутки дорівнюють нулю).

2. Сума квадратів елементів кожного стовпця ортогональної матриці дорівнює одиниці.

3. Визначник ортогональної матриці дорівнює 1.

4. Транспонована і обернена матриці ортогональної матриці також ортогональні.

Визначення Дві матриці (А і В), які здійснюють однакові лінійні перетворення в різних базисах, називаються подібними (АВ). Дві матриці подібні тоді і тільки тоді, коли одну можна отримати з іншої шляхом перетворення за допомогою якоїсь ортогональної матриці Q, тобто В = Q - 1АQ.

Властивості перетворення:

Q - 1(А + В)Q = Q - 1АQ + Q - 1ВQ;
Q - 1(АВ)Q = S - 1АQ Q - 1ВQ;
Q - 1АnQ = (Q - 1АQ)n.

Теорема 1: Якщо дана квадратна матриця порядку n має n лінійно незалежних власних векторів, то, взявши останні за базисні, отримаємо діагональну матрицю, подібну даній.

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

А = Q - 1DQ (1.8)

де D  діагональна матриця власних чисел матриці А:

при чому власні числа λi і власні вектори Xi матриці А пов’язані відомим співвідношенням: AXi = λiXi, i - 1,…,n.

Оцінку і порівняння векторів і матриць проводять, звичайно, через їх норми. Норма p–порядку вектора x описується виразом

Для випадку p = 2 одержуємо квадратичну норму

 (1.9)

Для випадку p = одержуємо максимальну норму

 (1.10)

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

 (1.11)

Визначають такі головні властивості норм векторів або матриць:





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

 (1.12)

Над матрицями виконують такі дії [6]:

1. Підсумовування, віднімання, коли операції проводяться над елементами з однаковими індексами матриць одного типу;

2. множення матриці на дійсне число , коли множаться всі елементи матриці, при цьому

3. множення матриць, виконуване за умови, що число стовпців матриці А дорівнює числу рядків матриці В:
С[q,m] = A[q,n]B[n,m],
при цьому елементи матриці
С визначаються виразом:
,
i = 1,2.,q; j = 1,2..,m,
який відповідає операції множення двох векторів (
i - го рядка матриці А і j - го стовпця матриці В) і вимагає для виконання n множень і n - 1 складань, тобто 2n - 1 операцій. Для всієї процедури множення матриць з урахуванням числа елементів qm матриці С буде потрібно множень,  - 1) складань, що у разі множення квадратних матриць (n = q = m) дасть верхню оцінку сигнальної функції відповідного поліноміального алгоритму, рівну fA (n) = О (n3).

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

1.6. Програмне забезпечення. Математичні пакети

За багато років в світі накопичено великі бібліотеки комп'ютерних підпрограм, написаних, в першу чергу, мовами FORTRAN та C, і призначених для розв’язку типових математичних задач (розв’язок систем лінійних та нелінійних рівнянь, розв’язок диференціальних рівнянь, апроксимація функцій і т. д.). Крім того, є цілий ряд різних універсальних математичних пакетів, які реалізують різноманітні чисельні методи, а також здатні виконувати аналітичні перетворення і розв’язувати багато відомих математичних задач аналітично.

Мабуть, найбільш відомими сьогодні є наступні пакети: Mathematica (фірма Wolfram Research), Maple (фірма Waterloo Maple Inc), Matlab (фірма MathWorks), Mathcad (фірма MathSoft Inc). Вони вторгнулися навіть в інтелектуальну сферу діяльності вчених різних спеціальностей, які займаються розв’язком задач теорії поля, аеродинаміки, космонавтики, математичного моделювання.

Пакет Mathematica, мабуть, є сьогодні найпопулярнішим в наукових колах, особливо серед теоретиків [12,37]. Пакет надає широкі можливості в проведенні символічних (аналітичних) перетворень, проте вимагає значних ресурсів комп'ютера. Пакет Mathematica дозволяє швидко і ефективно розв’язувати багато задач лінійної алгебри, теорії чисел, дискретної математики, математичного аналізу, диференціальних рівнянь. Вміє виконувати складні алгебраїчні перетворення і спрощення з різними математичними виразами: багаточленами, раціональними виразами, елементарними і спеціальними функціями, алгебраїчними і тригонометричними виразами. Знаходить кінцеві і нескінченні суми, добутки, границі та інтеграли. Розв’язує в символьному вигляді і чисельно алгебраїчні і трансцендентні системи рівнянь. Розв’язує аналітично і чисельно системи звичайних диференціальних рівнянь і деякі класи рівнянь в частинних похідних. В пакеті Mathematica розв’язок більшості задач проводиться в діалоговому режимі, без традиційного програмування, з використанням стандартних операторів. Однак, є також і сучасна мова програмування високого рівня. Характерною особливістю пакету є те, що він дозволяє конвертувати документи у формат LaTeX — стандартний формат переважної більшості наукових видавництв світового класу.

Пакет Maple, будучи найстарішим серед пакетів символьної математики, також дуже популярний в наукових колах [7,13]. Окрім аналітичних перетворень пакет може розв’язувати задачі чисельно. Наприклад, ядро пакету Maple–6 в студентській версії містить понад три тисячі математичних функцій і правил їх перетворення. Графічний редактор пакету дозволяє одержувати зображення тривимірних фігур з перетинами з функціональним забарвленням. Також він дозволяє конвертувати документи у формат LaTeX — стандартний формат переважної більшості наукових видавництв світового класу. Крім того, ряд інших програмних продуктів використовують інтегрований символічний процесор Maple. Наприклад, пакет підготовки наукових публікацій Scientific WorkPlace (фірма TCI Software Research) дозволяє звертатися до символічного процесора Maple, проводити аналітичні перетворення і вбудовувати отримані результати в документ.

Подібно згаданим вище пакетам, Matlab фактично представляє з себе своєрідну мову програмування високого рівня, орієнтовану переважно на інженерні розрахунки теорії управління, електро– і радіотехніки, а також на моделювання технічних систем [24]. Характерною особливістю пакету є те, що він дозволяє зберігати документи у форматі мови програмування C.

Виник MatLab як пакет для матричних обчислень. Потім він був оснащений сучасним графічним редактором і доповнений символічним процесором Maple. Matlab став фактично міжнародним стандартом сучасного учбового програмного забезпечення і використовується в багатьох провідних університетах світу і в технічних університетах Росії та України [26].

Пакет Mathcad теж популярний, однак, більше в інженерному, ніж в науковому середовищі [25]. Характерною особливістю пакету є використання звичних стандартних математичних позначень, тобто документ на екрані виглядає так само, як звичайний математичний розрахунок. Пакет орієнтований, в першу чергу, на проведення чисельних розрахунків, але має вбудований символічний процесор Maple, що дозволяє виконувати аналітичні перетворення. В останніх версіях передбачена можливість створювати зв'язки документів Mathcad з документами Mathlab. На відміну від згаданих вище пакетів, Mathcad є середовищем візуального програмування, тобто не вимагає знання специфічного набору команд.

Останнім часом намітилася тенденція до зближення та інтеграції різних математичних пакетів. Наприклад, останні версії пакетів Mathematica і Maple мають потужні засоби для візуального програмування; в Matlab включена бібліотека аналітичних перетворень Maple; Mathcad дозволяє працювати спільно з Matlab і т.д. Тому для організації практичних занять з чисельних методів можливий вибір будь–якого з перелічених вище пакетів, виходячи з можливостей і традицій конкретного навчального закладу.

В даному підручнику використовується математичний пакет Mathematica5, перш за все, для виконання обчислень і наочного представлення результатів розв’язку. В ряді глав, і перш за все у вправах, наводяться також задачі на виведення розрахункових формул, їх обґрунтування, отримання оцінок точності і стійкості. Запрограмувати і вирішити їх пропонується студентам за допомогою системи Mathematica5 у вигляді самостійної роботи. Це сприятиме розвитку у майбутніх фахівців напряму «Комп'ютерні науки» навичок самостійної розробки спеціалізованих чисельних процедур і програмних розширень як однієї із задач їх професійної підготовки. Для охочих професійно освоїти пакет Mathematica–5 і повторити приклади її застосування, приведені в підручнику, рекомендується додаткова учбова література [12].

Звичайно, наявність пакету Mathematica у майбутніх читачів не є обов'язковою умовою використання даного підручника, оскільки всі завдання і приклади чисельного розв’язку можуть бути реалізовані на будь–якій алгоритмічній мові або за допомогою інших наявних математичних пакетів, а приведені символьні перетворення повторені вручну.

Слід відзначити, що розглянуті математичні пакети (Mathematica, Maple, MatLab, Mathcad) дозволяють ефективно розв’язувати порівняно невеликі за розмірами математичні задачі, що містять десятки змінних, але не більше. Тому для науковців та інженерів вони є незамінним персональним інструментарієм і не можуть замінити собою інженерні програмні комплекси комп'ютерного моделювання і проектування виробів і об'єктів сучасної науки і техніки, такі як системи Cadence, AutoCAD, ANSYS, HSPICE і багато інших, які не тільки обробляють математичні задачі великої і дуже великої розмірності, але і самі їх формують за вхідною інформацією про структуру об'єкту і параметри його компонент [21].

PAGE  7

EMBED Equation.3


 

А также другие работы, которые могут Вас заинтересовать

69779. СОВЕРШЕНСТВОВАНИЕ ТЕХНОЛОГИЙ РАСЧЕТОВ С ИСПОЛЬЗОВАНИЕМ ПЛАСТИКОВЫХ КАРТ 231.61 KB
  Рассмотреть теоретические аспекты пластиковых карт, как платёжного средства, виды пластиковых карт и их характеристики Исследовать порядок расчетов с использованием пластиковых карт в России; Исследовать платежные системы, используемые для расчетов пластиковыми картами...
69780. СТАНОВЛЕНИЕ ПРОФЕССИОНАЛЬНОЙ ИДЕНТИЧНОСТИ СТУДЕНТОВ ПЕДАГОГИЧЕСКОГО ВУЗА 55.03 KB
  Актуальность исследования. Традиционно в качестве основных критериев профессионального развития личности выступали критерии эффективности деятельности, но уже в работах Е.А. Климова отмечается недостаточность этих критериев для оценки уровня профессионализации.
69781. Личностные особенности больных с гипертонической болезнью 61.09 KB
  Клиническая картина гипертонической болезни. Стадии гипертонической болезни. Диагностика гипертонической болезни. Несмотря на успехи в лечении и профилактике гипертонической болезни за последние годы она еще пока продолжает оставаться объектом прицельного исследования медицины и смежных с ней областей.
69782. ОСНОВНЫЕ НАПРАВЛЕНИЯ ОРГАНИЗАЦИИ ОПЛАТЫ ТРУДА РАБОТНИКОВ УП «УКС МИНГОРИСПОЛКОМА» 221.78 KB
  Цель исследования: определить и проанализировать формы и системы оплаты труда выявить направления их совершенствования на предприятии. Задачи исследования: изучить экономическое содержание оплаты труда на предприятии; провести анализ форм и систем оплаты труда в УП УКС Мингорисполкома...
69783. Принципы подготовки газетных изданий к печати 103.45 KB
  Так как внешний вид стиль красота газеты зависит от того как вы создадите макет: поместите колонки вставите рисунки выберете шрифт для текста насколько сделаете его красочным и многое другое. Этим термином обозначают цифровую подготовку текста и изображения пригодных...
69785. Социально-педагогическая профилактика агрессивного поведения подростка в информационно-игровой деятельности 226.31 KB
  Актуальность этого вопроса заключается в том что в последнее время стало популярным ругать во всем компьютеры и видеоигры СМИ массово транслируют как очередной подросток в американской школе убил своих одноклассников якобы изза того что он увлекался видеоиграми.
69786. Основные эволюционные алгоритмы 169.92 KB
  В общем виде эволюционный алгоритм – это оптимизационный метод, базирующийся на эволюции популяции “особей”. Каждая особь характеризуется приспособленностью – многомерной функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности.