лекція 6

Метод зважених нев'язок

Метод зважених нев'язок

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

тут - деяка система «вагових» функцій. Звідси, до речі, і назва «метод зважених нев'язок».

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

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

Запишемо систему (28) стосовно до розглянутого прикладу (1):

Тобто, знову, як і в методі найменших квадратів, завдання зводиться до вирішення системи лінійних рівнянь. Але елементи матриці і вектора мають інший вигляд:

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

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

Підставляючи (18) і (31) в (30), отримаємо

,

і рішення системи:

Підставляючи знайдені значення коефіцієнтів в (17), отримаємо

Таблиця 3

x	точне рішення	Метод зважених нев'язок (вагові функції: 1, x,x 2)
0.25	-0.0716449	-0.0611209
0.5	-0.1013212	-0.0780438
0.75	-0.0716449	-0.0565199

Відповідний графік на малюнку 9.

рис.9

Як бачимо, результати виявилися гіршими, ніж при використанні, як методу скінченних різниць, так і методу найменших квадратів. Причина такої неприємності не в тому, що поганий метод зважених нев'язок. Справа в тому, що система вагових функцій була обрана невдало. Як вже говорилося, в «Математичному відступі» (другому пункті цього параграфа) ці функції і не нормовані, і не ортогональні. Там же була отримана за методом Грама-Шмідта ортонормированном система функцій, еквівалентна (31). Спробуємо тепер в якості вагових функцій використовувати функції цієї системи:

В цьому випадку матриця і вектор:

а рішення системи:

В результаті підстановки цих значень в (17):

Таблиця 4

x	точне рішення	Метод зважених нев'язок (ортонормированном система статечних функцій)
0.25	-0.0716449	-0.0717608
0.5	-0.1013212	-0.1010489
0.75	-0.0716449	-0.717608

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

Ю.Я. ЛЕДЯНКІН

МЕТОДИ зважених нев'язок, колокація, МОМЕНТІВ. СПОСІБ паралельно РЕАЛІЗАЦІЇ В ЄДИНОМУ обчислювальних потоків РІШЕННЯ ЗАДАЧ МАТЕМАТИЧНОЇ ФІЗИКИ

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

Ключові слова: Паралельні обчислення, єдиний обчислювальний потік, СКЛАДНІ Структури Даних, задачі математичної фізики, метод кінцевіх елементів.

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

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

Abstract. The idea of ​​a parallel implementation of the methods of weighted residuals, collocations, moments in a single computational flow of solutions to the problems in mathematical physics with data processing in a form of complex structures based on processor elements including scalar multiplier is developed. The proposed method is described and reviewed on the specific test examples. It will be useful for mathematicians and developers of methods and structures of specially designed processors for solutions to the problems in mathematical physics and other problems.

Keywords: parallel computing, single computational flow, compound data structures, problems in mathematical physics, finite elements method.

1. Вступ

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

Перехід до нових технологій обробки інформації передбачає і новий підхід до опису та способам реалізації МВН. Слід розглянути основні МВН, до яких, крім базової постановки, відносяться методи найменших квадратів (МНК), моментів (ММ), колокацій (МК), Гальоркіна (МГ), та ін., Описані в. З першого розділу її взяті підхід до вирішення завдань МВН, а також приклади для оцінки отриманих результатів і порівняння їх з результатами, отриманими авторами в.

© Ледянкін Ю.Я., 2012

ISSN 1028-9763. Математичні машини і системи, 2012, № 2

Мета автора - розробка МВН для паралельної реалізації при вирішенні задач математичної фізики методом скінченних елементів (МСЕ) з обробкою даних на рівні складних структур в ідеології єдиного обчислювального потоку.

Реалізації цілей, викладених вище, і присвячена дана робота (а вірніше, цикл

2. Основа методів зважених нев'язок

На послідовності функцій виду

01 (х), Ф2 (x), ..., Ф п (x) (1)

скалярний твір< Ф, ф >виду

< Ф1, Ф2>= J Ф1 (x) * Ф2 (x) dx (2)

для системи пробних (базисних) функцій Ф. з коефіцієнтами ai

а Ф, + а 2 Ф2 + ... + ап Фп = 0 (3)

можливо

li u - ^ а * ф. li< e. (4)

Якщо визначити оператор L () як дію, яке при застосуванні його до даної функції і призводить до появи деякої іншої функції p

то для лінійного оператора L, позитивно певного для всіх x, може бути складено скалярний твір оператора L (u) і іншої функції v:

< L(u), v >=< и, L* (v) + J dS, (6)

де S - обмежує поверхню;

F, G - диференціальні оператори, форма яких визначається при інтегруванні частинами;

L - оператор, пов'язаний до оператора L (якщо L * = L, то L самосопряженних);

F (v) - містить члени з v, що з'являються на 1 -й стадії інтегрування частинами;

G (u) - аналогічно, але містить члени з u;

F (v) - визначає головні граничні умови (ГУ);

G (u) - визначає несуттєві або природні ГУ.

Якщо для L * = L, F (u) на S 1, G (u) - заданий S2 і S1 + S2 = S< L(u), а также

u> ..> 0 для всіх нетривіальних u (які задовольняють однорідним ГУ), то працює

метод зважених нев'язок.

Можна встановити чисельні процедури наближеного рішення системи диференціальних (інтегральних) рівнянь виду

L (u) = p, x e V з ГУ; (7)

F (u) = g, x e S, (8)

де £ - зовнішня межа області;

і - точне рішення, яке апроксимують набором функцій фк ():

і = X ак фк; (9)

ак - невідомі параметри;

фк - лінійно незалежні функції.

Після підстановки (9) в (7) отримують функцію помилки е (невязку):

е = Ь (і) - р = 0. (10)

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

< е, w >= 0, I = 1,2, ..., N, (11)

де w 1 - набір вагових функцій.

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

3. Сутність запропонованого підходу з РКК

Пропонований спосіб використання МВН орієнтований на реалізацію єдиного технологічного потоку (ЄТП) по обробці складних структур даних (ССД) при вирішенні класу задач МФ і ін. В паралельних структурах, процесорні елементи (ПЕ) яких містять скалярний множник (СУ). Використання РМП дозволяє записати поліноми в матричному вигляді, зручному для обробки за допомогою СУ.

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

Для вирішення поставленого завдання необхідно зробити наступне:

1. Описати в матричному вигляді пробні функції (сплайни) і визначити операції над сплайнами, представленими у вигляді РМП.

2. Диференціювати і інтегрувати поліноми в матричному або векторному вигляді.

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

4. Виконувати операції по пп. 2, 3 аналітично і в чисельному вигляді.

5. Обчислювати отримані вирази.

Записуємо поліноми / (X) і / 2 (X) у вигляді РМП:

і твір у полиномов

7 = / (Х) = / (X) / (Х) = Уо + УІ Х1 + У2 Х2 + ^ =

Ао Ьо + (а Ьо + а про Ь) + (а про Ь2 + ах ^ + ^ 2 Ь0) + ...

в матричної формі

(АоЬо) (а, Ьо + аоЬ1) (аоЬ1 + а1Ь1 + а1Ьо) - 1 X0

У = / (X) * [Ф 1] * [Ф 2] = (аоЬо) (а1Ьо + аоЬ1) --- Xі- (15)

_ (АоЬо) ---] X2

Основним недоліком матричного уявлення і виконання над ними операцій типу множення, додавання і ін. В матричної формі є надмірність як в поданні, так і при виконанні процедур над ними. Так, при множенні матриць АТТ і X тт треба виконати Т3 операцій, а для виконання матричного множення треба

мати т2 СУ. Тому для скорочення витрат обладнання та скорочення часу виконання операцій множення пропонується замість матричного уявлення полінома X використовувати векторне. Це скоротить в т разів кількість СУ, а операцій потрібно

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

Процедуру множення векторів / (X) в СУ (записаних за допомогою РМП в матричному вигляді [Ф]), можна замінити на процедуру множення матриці на вектор. Для виконання її як операції множення матриці на вектор в (15) треба замінити уявлення функції / X на транспоновану / 1 (X) (в матричному вигляді [Ф1] на [Ф1] Т):

/ Т (X) * [Ф 1] Т = а1 ат

а в (13) подати у вигляді / 2 (X ") (в матричному вигляді [Ф 2]) як вектор стовпця:

Представляючи завжди перший поліном (множимое) у вигляді / 1Т (X), а другий поліном (множник) у вигляді стовпчика / 2 * (Х), визначимо твір двох поліномів в загальному вигляді:

7 = / (X) * / 2 (X) - * / Т (X) * Ш = [Ф 1] т * [Ф 2]

і в матричному вигляді:

a0 b ■ (a0b0)> 0 "

g = aj a0 * b = (aA + a0b1) = g = [Ф *] * f * (X),

1 про Ö sT 2 a2 и А _ _ (a2b0 + a1b1 + a0b2) 1 _ g _

[F: (X)] Г =.

Постановка задачі

Стосовно до одного з МВН - методу колокацій - покажемо можливість використання РМП, описаного вище.

метод коллокацій

Розглянемо на прикладі підставі рішення рівняння виду

L (u) - p = Д2 і / д x2 + і + x = 0 (20)

на проміжку 0< x < 1 с ГУ, и = 0 при x = 0, и = 0 при x = 1. (21)

Значення диференціального рівняння задовольняються в декількох точках колокації.

Вибирається апроксимація у вигляді виразу

і = x (1-x) (a1 + a2 x + ...),

яке задовольняє ГУ при будь-яких а ..

Залишаючи в апроксимується рівнянні (22) тільки 2 члени, запишемо його і за допомогою РМП:

і = x (1-x) (a1 + a2 x) = a1 (x-x2) + a2 (x2 -x3) ^ a

А1 г + а2г. (23)

Для отримання помилки обчислюємо першу похідну від апроксимуючої функції:

Е і / Е х = Е (а1 х -а1 х 2 + а 2 х 2 -а2 х3) Е х = (а 1-2а1 х + 2А2 х-3а2х2) =

А1 (1 - 2 х) + А2 (2 х - 3х2) (24)

і другу похідну

д 2 і / д x 2 = д (a j -2 a 1 x +2 a 2 x 2 -3 a2 x3) dx =

Д (a1 - 2a1 x) dx + д (2a2x - 3a2x) dx = (- 2 a j + 2 a 2 x -6 a 2 x).

Після завдання апппроксімірующей функції (23) з рівняння (10) визначимо помилку е, використовуючи запис її у вигляді РМП:

е = Ь (і) -р = х + а 1 (-2+ х-х 2) + А2 (2-6х + х2-х3) ^

1 про 0 0 1 "- 2 1 -10" 1 -1 6 - 2 1

0 1 0 - 2 1 -1 2 - 6 1

Ь (і) - р = (-2 а 1 +2 А2 х -6 А2 х 2) + а1 (х - х2) + А2 (х2 - х3) + х = 0. (27)

х = (2А1 - 2А2 + 6а2х) - (а1 (х - х2) + (А2 (х2 - х3) =

А1 (2 - х + х 2) + А2 (-2 + 6 х - х2 + х3). (27а)

Для обраних точок колокації х 1 = 1/4, х 2 = 1/2 складається система рівнянням

I (2 - х1 + х1) а1 (-2 + 6х1 - х1 + х1) 2 = 1/4,

[(2-х2 + х22) а1 (-2 + 6х2 -х22 + х ^) 2 = 1/2.

Зрозумівши значення коефіцієнтів при невідомих а1 і А2 шляхом вирішення систе-

"29/16 - 35/64" * Ь 1 = 11/41 або "0,8125 - 2,1875"

7/4 7/8 ґ 2 11 / 2І 1,75 0,875 _

визначимо значення ^ = 6/31 (0,193548), а 2 = 40/217 (0,184332). Це забезпечить обчислення з (23) необхідних нам значенні і:

і = х (1-х) (а 1 + а 2 х) = а 1 (х -х2) + а 2 (Х2 х 3) = (х (1-х) (6/31 + 40/217 х ). (30)

Для хі = 1,2,3 маємо

х 1 = 1/4, и1 = 1/4 * (1-1 / 4) * (6/31 + 40/217 * 1/4) = 0,0436,

х 2 = 1/2, і 2 = 1/2 * (1-1 / 2) * (6/31 + 40/217 * 1/2) = 0,0703,

х 3 = 3/4, і3 = 3/4 * (1-3 / 4) * (6/31 + 40/217 * 3/4) = 0,0618.

Рішення поставленого завдання опишемо поетапно.

Подання полиномов аппроксимирующих функцій (22) у вигляді

А1 (х-х) + А2 (х - х) ^ а1

0 1 -1 0 0 1 -1 01 0

0 0 1 -1 0 0 1 00 0

а оператора [А] матричного диференціювання у вигляді

Е / Е х = [А] =

00200 0 0 0 3 0 00004

обчислимо:

Аналітично першу похідну від функції і з (24):

Е і / Е х = Е (а1 х- а1 х2 + а2 х2-А2 х3) / Е х = (а1-2а1 х) + (2А2 х3 А2 х2);

Е і / Е х = [А] * а 1

х1 Ех + [А] * а

х1 Ех + [А] * а х2

х1 Ех = а 1 "2

1 0 0 2 - 1 про 1 ю - 6 0 "

0 2 - х1 + а 2 2 -

1 - 2 1 х 2 + 2 1 2

і другу похідну від функції і (25) з записом у вигляді РМП:

Е 2 і / Е х 2 = Е / Е х (-2 а1 + 2 А2 -6 А2 х) =

і 0 0 2 - и х0 1 0 6 - 2 1

[А] а 1 0 2 - х1 Ех + [А] а2 2 - 6

х1 Ех + [А] А2

Обчислимо помилку (е) із записом рівняння (26) у вигляді РМП:

"0 1 0 0" "- 2 1 -1 0" "2 - 6 1 -1"

0 1 0 - 2 1 -1 и 1

0 1 1 - 2 1 2 2 - 6

Вважаючи е = 0 для обраних точок колокації х1 = 1/4, х2 = 1/2 з рівнянь

х і + (- 2 + х і х 2) а 1+ (2-6х і + х 2 х 3) 2 = 0, (36)

х і = (2-х і + х 2) а 1 + (- 2 + 6х і-х 2 + х 3) а 2, (36а)

складаємо систему. Уявімо поліноми при а1 і А2 у вигляді циркулянт (регулярного матричного подання):

/ (Х а1) = а 1 (2-х і + х 2) ^ а 1

А 1 * [х х х х] ^ / (х "),

I (х) = а 2 (-2 + 6 хі - х2 + х3) ^ а

А 2 [-2 6-1 1] * [х х х х] ^ I (х).

Для обраних точок колокації рівнянь системи (28) значення функції / * (ха) у векторній записи можуть бути обчислені в такий спосіб:

для х2 = 1/2:

х = 1 х1 = 1/4 х 2 = 1/16

А1 [(2-1 1] * [х 0 х; х 2] т = а1 (2-1 / 4 + 1/16) = а11,8125; (37)

а 1 * [х 2 = 1 х 2 = 1/2 х 2 = 1/4] т = а 1 (2 * 1-1 * 1/2 + 1 * 1/4) = а 17/4 = а 11 , 75;

а 2 [-2 6-1 1] * [х 0 = 1 х 1 = 1/4 х 2 = 1/16 х 3 = 1/64] т = а 2 (-2 * 1 + 6 * 1/4 -1 * 1/16 + 1 * 1/64) =

А 2 35/64 = -а 2 0,5469;

для х2 = 1/2:

а 2 [-2 + 6-11] * [х 2 = 1 х 2 = 1/2 х 2 = 1 / 4х 2 = 1/8] т = а 2 (-2 * 1 + 6 * 1/2 1 * 1/4 + 1 * 1/8) =

А 2 7/8 = а 2 0,875.

Тоді система рівнянь (28) з обчисленими в (35) - (39) коефіцієнтами для раніше визначених точок колокації в чисельному вигляді може бути записана так:

1,8125 0,5469 1,75 0,875

[А.1 =] 0,25 I а І 10,50 и

і її рішення по схемі виключення

"1,8125 - 0,5469 0,25 "

0 2,542968 0,46875

Ь 22 = 1 / 2,542968 = 0,393241, Ь "= 1 / 1,8125 = 0,5517

2 = Ь 22 * ​​0,46875 = 0,1843,

а = Ь 11 * (0,25 + 0,1843 * 0,5469) = 0,1935.

За обчисленими значеннями коефіцієнтів а1 і А2 для рівняння (23) у варіанті записи рівняння (30) можна представити у вигляді регулярного матричного уявлення:

і = а 1 (х-х 2) + а 2 (х 2 х 3) =

що дозволяє за допомогою СУ обчислити значення коефіцієнтів для обраних точок колокації:

а (х 1-х 2) = а * T = а10,1875 (для х1 = 1/4), (43)

а (х 2-х 2) = а1 * T = а10,25 (для х2 = 1/2), а 2 (х 2-х 3) = А2 * T = а20,0469 (для х1 = 1,4), (44)

А2 (х 2-х 2) = А2 * T = а20,1406 (для х2 = 1/2).

Після цього обчислюємо значення функції і:

і = а10,1875 + А2 0,0469 = 0,1935 * 0,1875 + 0,1843 * 0,0469 = 0,0449, (45)

і = а10,25 + А2 0,1406 = 0,1935 * 0,25 + 0,1843 * 0,1406 = 0,0742.

Для нової точки колокації х = 3/4 обчислюємо (з варіантами в обчислювальному процесі):

і = а1 * T + А2 * T = а1 (3 / 4-9 / 16) + А2 (9 / 16-27 / 64) = = (а10,75-а10,5625) + (А2 0,5625-А20 , 4219) = 0,0346 + 0,0259 = 0,0605. (46)

метод моментів

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

< e, w >= 0, i = 1,2, ..., N, (47)

де wi - вагові функції. Ними може бути будь-який набір лінійно незалежних функцій,

наприклад, 1, х, х2, х3, ....

Якщо виконується умова звернення в нуль моментів невязки більш високого порядку

< е, х^ >= 0, i = 0,1, (48)

то така процедура називається методом моментів.

Розглядається приклад з в запису (20) - (22):

L (u) - p = Е2u / Е х2 + і + х = 0, і = х (1 х) а1 + х 2 (1 х) А2

і функція помилки в ньому ортогоналізуется по відношенню до 1 і х:

j е * 1 * йх = 0, (49)

j е * х * йх = 0 (49а)

з підстановкою помилки е в систему (49), (49а)

е = а j (-2+ х - х 2) + а 2 (2-6 х + х 2 - х 3) + х, (50)

х1 дх + А2 [А] *

х1 дх + а 2 [А]:

А 1 (2х + х 2 / 2х 3/3) | 0 + а 2 (2х-6х 2/2 + х 3/3-х 4/4) | "0 + х 2/2 |" 0 : = а 1 (-2 + 1/2 -1/3) + а 2 (2-3 + 1 / 3-1 / 4) +1 / 2 =

11/6 а, -11 / 12 а 2 + 1/2 = 0.

11/6 а 1 + 11/12 а 2 = 1/2, де [А] - матриця інтегрування в запису РМП, рівна

Зауваження. Слід пам'ятати, що при інтегруванні функцій (із записом РМП) у вигляді твору матриці [А] на вектор стовпця I * (х) кількість стовпців т матриці має дорівнювати кількості рядків т вектора, а розмірність результуючого вектор стовпця тк - на одиницю більше: тк = т +1.

За аналогією з (51) обчислимо другий (49а) інтеграл:

| Є * х * дх = | (Х + а 1 (-2+ х-х 2)) дх +1 а 2 (2-6х + х2-х 3) дх =

= | (Х 2) дх +1 а 1 (-2 х + х 2 х 3) дх +1 а 2 (2 х -6 х 2+ х 3 х 4) дх =

Х 3/3 | 0 + а 1 (2х 2/2 + х 3/3-х 4/4) | 0 + а 2 (х 2-2х 3 + 1 / 4х 4-1 / 5 х 5) | 0 =

= [А] * т дх + а 1 [А] * т дх + а 2 [А] * т дх =

х2 + а -1 + а 2 х 3

Т | 0 + а 1 т | 0 + а 2 т | = = 1/3 + а1 (-1 + 1 / 3-1 / 4) + А2 (1-2 + 1 / 4-1 / 5) = 1/3 + А111 / 12- а219 / 20. (11/12 а1 + 19/20 2 = 1/3).

Звідси система рівнянь щодо а1 і А2:

"11/6 11/12". І а-1 або "1,8333 0,91667"

11/12 19/20 1А2 1.1 / 3І 0,91667 0,95

Вирішуємо систему (54) за методом виключення:

1,8333 0,91667 0,5

0 0,9014 0,1526_

Х11 = 1 / 1,18333 = 0,54546, Ь22 = 1 / 0,9014 = 1,1094, а 2 = 0,1695, а 1 = 0,18796.

Звідси з х (1 х) (а1 + а2 х) для обраних точок колокації маємо і 1 = 0,25 * 0,75 (0,18796 + 0,1695 * 0,25) = 0,04319, і 2 = 0 , 5 * 0,5 (0,18796 + 0,1695 * 0,5) = 0,06816, і3 = 0,75 * 0,25 (0,18796 + 0,1695 * 0,75) = 0,0590 .

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

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

Запис вихідних рівнянь у вигляді РМП дозволяє:

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

Распараллеліть обчислювальний процес, виконуючи операції в ПЕ за допомогою вхідних в його структуру скалярних умножителей, тобто в паралельному спецпроцесорі на структурі, призначеної для обчислення матриць жорсткості кінцевих елементів (КЕ), а потім і глобальної матриці з вектором навантажень стосовно використання МСЕ при вирішенні задач МФ.

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

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

Вважаю, що до ініціаторів роботи автора під кутом бачення, визначеним у моєму циклі статей по застосуванню МВН для вирішення завдань МФ за допомогою МСЕ, можна віднести Дж. Коннора і К. Бреббія, що випустили книгу, необхідну для роботи математикам і інженерам. Запропоновані вище методи можна з успіхом застосувати при вирішенні завдань, описаних ними в своїй книзі, на СП або векторних процесорах архітектури CUDA серії Tesla фірми nVidia, наприклад, або AMD в складі GPU - CPU (графічних і центральних кластерних процесорів), що виконують векторні операції.

СПИСОК ЛІТЕРАТУРИ

1. Коннор Дж. Метод кінцевих елементів в механіці рідини / Дж. Коннор, К. Бреббія; пер. з англ. - Л .: Суднобудування, 1979. - 264 с.

2. Єдиний технологічний потік в організації обчислень - спосіб підвищення продуктивності паралельних структур на процесорних елементах транспьютерном типу / Ледянкін Ю.Я.

Київ, 1989. - 20 с. - (Препринт / АН УРСР, Ін-т кібернетики ім. В.М. Глушкова; 89-57).

3. Ледянкін Ю.Я. До питання перетворення і паралельного введення граничних умов при вирішенні крайових задач в єдиному обчислювальному потоці / Ю.Я. Ледянкін // Математичні машини і системи. - 2012. - № 1. - С. 28 - 35.

4. Адінец А. Графічний виклик суперкомп'ютерів / А. Адінец, В. Воєводін // Відкриті системи. - 2008. - № 4. - С. 35 - 41.

Велика група методів наближеного рішення диференціальних

рівнянь базується на математичному формулюванні, пов'язаної з

інтегральним поданням зваженої невязки. Цю групу методів називають методами зважених нев'язок .

Нехай є диференціальне рівняння і гранична умова до нього:

тут Lдиференціальне оператор; x i- просторові координати; Vі S- обсяг і зовнішня межа досліджуваної області; u 0- точне рішення.

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

У методах невязки ця процедура складається з двох послідовних етапів. На першому етапі підстановкою наближеного рішення (2.1.3) в рівняння (2.1.1) знаходиться функція помилка, або невязка, Яка характеризує ступінь відмінностівід точногорішення:

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

На другому етапі на функцію нев'язки (2.1.4) накладаються вимоги, які мінімізують або саму невязку (метод колокацій), або зважену невязку (метод найменших квадратів і метод Гальоркіна).

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

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

У методі найменших квадратів - методі Релея-Рітца - як ваговій функції вибирається сама помилка, тобто , І потрібно, щоб отримана таким способом величина (функціонал) була мінімальна:

Для цього має виконуватися умова:

що приводить до системи алгебраїчних рівнянь щодо невідомих коефіцієнтів.

У методі Гальоркіна в якості вагових функцій беруться самі функції, звані базисними, І потрібно їх ортогональность невязке :

Якщо - лінійний оператор, то система (2.1.9) переходить в систему алгебраїчних рівнянь щодо коефіцієнтів.

Розглянемо метод Гальоркіна на конкретному прикладі. Дано рівняння на проміжку:

Зіставлення наближених результатів, отриманих різними методами, з точним рішенням дано в таблиці 1.

Кафедра физхимии ПФУ (РГУ)

ЧИСЕЛЬНІ МЕТОДИ І ПРОГРАМУВАННЯ

Матеріали до лекційного курсу

Системи лінійних рівнянь

Системи n лінійних рівнянь з n невідомими x 1, x 2, ..., x n в загальному випадку прийнято записувати в такий спосіб:

де а ij і b i - довільні константи. Число n невідомих називається порядком системи.

Рішенням рівняння є така сукупність значень змінних х 1, х 2, ..., х n, яка одночасно звертає всі рівняння системи в тотожність.

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

Еквівалентної (і дуже зручною !!!) записом системи лінійних рівнянь є матричний запис

або скорочено ,

у чому легко переконається, якщо скористатися правилами множення матриць: елемент, що стоїть на перетині i -го рядка і j-го стовпця матриці-результату є скалярний твір i -й вектор-рядка першої матриці і j -го вектор-стовпця другого матриці.

Коефіцієнти при невідомих утворюють квадратну матрицю розміром n x n, (A), змінні і вільні члени рівнянь - вектори-стовпці довжиною n(Х) і (В), відповідно.

Рішення системи рівнянь є вектор (X *), який звертає це матричне рівняння в тотожність.

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

Оцінити близькість будь-якого вектора (Х) i до вирішення системи рівнянь можна оцінивши близькість вектора нев'язок, що обчислюється наведеним нижче чином, до нульового вектору:

Для вираження міри близькості у вигляді числа використовується будь-яка нормавектора, наприклад, Евклидова норма або довжина вектора в nвимірному просторі (інше визначення - це корінь квадратний зі скалярного добутку вектора на себе):

Іноді використовуються інші векторні норми: норма-максимум (дорівнює найбільшою за абсолютною величиною компоненті вектора)

або норма-сума (дорівнює сумі абсолютних величин компонентів вектора)

Обумовленість лінійних алгебраїчних систем

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

Наведемо такий приклад:

Система рівнянь

Має, як неважко переконатися підстановкою, єдине рішення x = 1, y = 1.

Припустимо, що при підготовці системи до вирішення, права частина першого рівняння була визначена з невеликою абсолютною похибкою в +0.01, тобто, права частина першого з рівнянь замість 11 була взята рівною 11,01.

Єдиним рішення цієї системи рівнянь вже буде вектор x = 11,01 y = 0.

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

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

якщо вектор (X)є точним рішенням рівняння з "точним" вектором (В) .

то при наявності похибки в правій частині (ΔВ) рішення системи рівнянь буде відрізнятися від (X) на деякий вектор (ΔX) , що можна записати в такий спосіб:

Розкриємо дужки в правій частині

І врахуємо точне рівняння

, Множачи обидві частини рівності на матрицю, зворотну матриці коефіцієнтів

отримаємо

тобто абсолютна похибка (ΔX) обчислення вектора рішення (X) дорівнює добутку матриці, зворотної матриці коефіцієнтів системи рівнянь, на вектор абсолютної похибки (ΔВ).

Якщо перейти від матриць і векторів до відповідних норм, то отримаємо, що норма вектора (ΔX) буде менше або дорівнює добутку норм зворотної матриці і норми вектора похибки

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

Оцінимо, як будуть при цьому співвідноситися відноснапохибка рішення і відносною похибкою коефіцієнтів. Для цього пронорміруем два отриманих раніше рівняння:

Перемножимо окремо ліві і праві частини нерівностей, що, очевидно, не змінить знак нерівності і розділимо обидві частини на і, остаточно отримаємо:

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

Аналогічний аналіз можна провести і для випадку наявності похибки завдання матриці коефіцієнтів системи (ΔA). І в цьому випадку, так само, виникає число обумовленості.

Для розглянутого числового прикладу

і

Якщо взяти, наприклад, матричну норму-максимум,

, То отримаємо

для матриці (А) норму 1011 а для матриці, зворотної (А) - (А) -1 - 1101. Таким чином, число обумовленості виявляється рівним більше 1000000!

Прямі (точні) методи

Метод Гаусса і Гаусса-Жордана

Алгоритм рішення полягає у приведенні розширеної матриці системи рівнянь до трикутного вигляду (метод Гаусса) або псевдодіагональному увазі (метод Гаусса-Жордана).

метод Крамера

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

I = 1, 2, ..., n

Тут в знаменнику стоїть визначник матриці коефіцієнтів системи. У чисельнику - визначник матриці, отриманої з матриці коефіцієнтів шляхом заміни i-го стовпця на вектор-стовпець вільних членів системи.

Для системи, записаної в загальному вигляді :

Метод звернення матриці

Рішення системи рівнянь, записаної в матричної формі, легко знайти, якщо скористатися визначенням оберненої матриці:

(A) (A) -1 = (A) -1 (A) = (1),

де (1) - одинична діагональна матриця.

дійсно,

Помножимо зліва обидві частини рівняння на зворотну матрицю коефіцієнтів системи (A) -1

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

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

Наближені (ітераційні) методи

Метод простих ітерацій, метод Зейделя

Дані методи розглянуті на прикладі систем нелінійних рівнянь.

Метод мінімальних нев'язок

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

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

Функцію f 0 зазвичай намагаються вибирати так, щоб вона максимально точно (по можливості) задовольняла початковим і граничним умовам. Аппроксимирующие (пробні) функції f j передбачаються відомими. Математики придумали кілька вимог до таких функцій, але їх тут обговорювати не будемо. Обмежимося фактом, що поліноми і тригонометричні функції цим вимогам задовольняють. Ще кілька прикладів наборів подібних функцій будуть розглянуті при описі конкретних методів.

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

У рівнянні, яке передбачається вирішити, всі члени переписуються в ліву частину, в правій частині залишається лише нуль. Таким чином, рівняння приводиться до вигляду

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

де величина R називається нев'язкої. У загальному випадку невязка є функцією x, y, z і t. Завдання зводиться до знаходження таких коефіцієнтів a j, щоб невязка залишалася малою у всій розрахунковій області. Під поняттям «малої» в даних методах розуміють, що інтеграли по розрахункової області від невязки, помноженої на деякі вагові функції, дорівнюють нулю. Тобто

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

Наведемо кілька прикладів найпростіших методів з цього класу.

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

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

Метод Колокація.Як вагових функцій використовуються дельта-функція Дірака

де x =(X, y, z). Нагадую, що функція Дірака - це хитра функція, рівна нулю всюди, крім початку координат. Але на початку вона приймає невідоме науці значення таке, що будь-який інтеграл по області, що містить початок координат, дорівнює одиниці. Говорячи простіше: задаємо деяку кількість точок (часто в даному підході званих вузлами). Початкове рівняння буде задовольнятися в цих точках. Існують підходи до вибору цих точок і пробних функцій, що дозволяють максимізувати точність при обмеженому числі вузлів. Але тут їх обговорювати не будемо.

Метод найменших квадратів.Метод заснований на мінімізації величини

Але неважко показати, що він теж належить до класу методів зважених нев'язок. Ваговими функціями для нього є функції виду

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

Метод Гальоркіна.У цьому методі в якості вагових функцій беруться аппроксимирующие (пробні) функції. Тобто

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

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

Граничні умови задані у вигляді

Будемо шукати рішення у вигляді

Тоді нев'язка буде записуватися у вигляді

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

Метод Колокація. Вибираємо дві точки на кінцях балки. Прирівнюємо в них невязку до нуля

отримуємо

Як бачимо, метод Колокація досить простий в реалізації, однак поступається по точності іншим методам.

Метод подобластей. Розбиваємо всю довжину балки на дві підобласті. У кожній з них інтеграл від невязки прирівнюємо до нуля.

Метод Гальоркіна. Беремо інтеграли від невязки, помноженої на пробні функції.

Метод найменших квадратів.

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