69318

Розв’язування СЛАР на основі LU-розладу матриці

Лекция

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

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

Украинкский

2014-10-03

542 KB

13 чел.

Лекція 2. Розв’язування СЛАР на основі LU-розладу матриці

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

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

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

(2.1)

або 

Систему лінійних алгебраїчних рівнянь часто записують в матричній форм

Ах = b, (2.2)
д
е

матриця коефіцієнтів;

 

— вектор стовпців вільних членів і вектор стовпців невідомих відповідно.

Якщо матриця А неособлива, тобто

то система (2.1) має єдиний розв’язок.

В лінійній алгебрі звичайно використовують спосіб розв’язування системи (2.2), заснований на використанні оберненої матриці A - 1, Помножимо обидві частини рівняння (2.2) на матрицю A - 1, отримаємо розв’язок рівняння у вигляді

x = A - 1b. (2.3)

Якщо при цьому передбачається, що елементи зворотної матриці a(1)ij обчислюються згідно відомої формули (1.7)

,

де Aji - алгебраїчне доповнення елемента aji матриці А і |A| — визначник цієї матриці, то для обчислення всіх її елементів потрібно буде знайти значення n2 визначників порядку n. Остання задача настільки трудомістка, що розв’язати її навіть для n = 10 практично неможливо.

Менш трудомістким є метод Крамера, відповідно до якого значення невідомих xi , i = 1,2,…n можуть бути отримані з допомогою формули

(2.4)

де матриця Ai отримується з матриці A заміною її i–го стовпця стовпцем вільних членів. Але такий спосіб розв’язування лінійної системи з n невідомими призводить до обчислення n + 1 визначників порядку n, що є дуже трудомісткою операцією при великому n, оскільки для розв’язку лінійної системи з n невідомими буде потрібно nn! арифметичних операцій на одно процесорному комп'ютері. Вже при n = 50 такий об'єм обчислень практично недоступний сучасним комп'ютерам.

Методи чисельного розв’язку системи (2.1) діляться на дві групи: прямі та ітераційні. В прямих (або точних) методах розв’язок x системи (2.1) знаходиться за скінчене число арифметичних дій. Прикладом прямого методу є метод Гауса. Ітераційні методи полягають в тому, що розв’язок x системи (2.1) знаходиться як границя послідовних наближень x(k) при k, де k номер ітерації.

Розглянемо більш детально алгоритми, реалізовані цими матричними операціями.

2.2. Метод виключення Гаусса

Припустимо, що визначник матриці А відмінний від нуля. Тоді для кожного вектора b система (2.1) має єдиний розв’язок. Розв’язування системи методом Гаусса полягає в послідовному виключенні невідомих x1,x2,…,xn з цієї системи. Припускатимемо, що a110 Поділивши перше рівняння (2.1) на a11, отримаємо:

x1 + c12 x2 + … + c1n xn = y1,  (2.5)

де

.

Розглянемо тепер решту рівнянь системи (2.1):

(2.6)

Помножимо (2.5) на ai1 і віднімемо отримане рівняння з i–го рівняння системи (2.6), i = 2,…,n. 

В результаті отримаємо таку систему рівнянь:

Тут позначено

 (2.8)

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

  (2.9)

Саме цим здійснено перший крок методу Гаусса. Якщо a(1)22  0, то з системи (2.9) абсолютно аналогічно можна виключити x2 і прийти до системи, яка еквівалентна (2.1). При цьому перше рівняння системи (2.7) залишиться без змін.

Виключаючи в такий спосіб невідомі x3,x4,…, xn прийдемо остаточно до системи рівнянь вигляду

,  (2.10)

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

Отримання системи (2.10) являє собою прямий хід методу Гаусса. Зворотний хід полягає в знаходженні невідомих x1,x2,…,xn з системи (2.10). Оскільки матриця система має трикутний вигляд, можна послідовно, починаючи з x, знайти всі невідомі. Загальні формули зворотного ходу мають вигляд

 (2.11)

Виведемо розрахункові формули прямого ходу. Нехай виконані перші k - 1 кроків, тобто вже виключені змінні x1,x2,…,xn. Тоді для виключення матимемо аналогічну (2.9) скорочену систему:

 (2.12)

Нехай a(k - 1)kk  0. Поділивши обидві частини k–го рівняння на a(k - 1)kk, отримаємо

 (2.13)

де

Помножимо рівняння (2.13) на a(k - 1)ik і віднімемо отримане співвідношення з i–го рівняння скороченої системи (2.12), де i = k + 1,k + 2,…n. В результаті група рівнянь (2.12) набуде вигляду

Отже, в прямому ходу методу Гаусса коефіцієнти рівнянь перетворяться за таким правилом:

 (2.14)
.
(2.15)

Обчислення правих частин системи (2.10) здійснюється за формулами

(2.16)

Основним обмеженням методу є припущення про те, що всі елементи a(k - 1)kk, на які проводиться ділення, відмінні від нуля. Число a(k - 1)kk називається ведучим елементом на k–му кроці виключення. Навіть якщо якийсь ведучий елемент не дорівнює нулю, а просто близький до нього, в процесі обчислень може відбуватися значне накопичення похибок. Уникнути цього дозволяє метод Гаусса з вибором головного елемента. Ідея методу полягає в тому, щоб на черговому кроці виключати не наступне за номером невідоме, а те невідоме, коефіцієнт при якому є найбільшим по модулю. Отже, ведучим елементом тут вибирається головний, тобто найбільший по модулю елемент. Тим самим, якщо detA0, то в процесі обчислень не відбуватиметься ділення на нуль.

Для зменшення помилок округлення чинять так. Серед елементів першого рядка a(k)k j кожної проміжної матриці (2.12) вибирають найбільший по модулю елемент max|a(k)kj|, j = k,k + 1,…,n, роблять головний елемент ведучим. Вказаний спосіб виключення називається методом Гаусса з вибором головного елемента по рядку. Він еквівалентний застосуванню звичайного методу Гаусса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерація змінних.

Застосовується також метод з вибором головного елемента по стовпцю max|a(k)kj|, i = k,k + 1,…,n (рис.2.1, а) Він еквівалентний застосуванню звичайного методу Гаусса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерація рівнянь.

Проте головний елемент може вибиратися і по всьому полю неперетвореної частини матриці (рис.2.1,б).

(2.17)
(2.18)

 

Рис. 2.1. Вибір головного елемента серед елементів стовпця матриці (а) і серед елементів неперетвореної частини матриці (б)

Підрахуємо складність алгоритму, що реалізує метод Гаусса на однопроцесорній ЕОМ. Розглянемо задачу розв’язку системи лінійних рівнянь з р правими частинами:Ax1 = b1,…,Axp = bp..

На кожному k–му кроці прямого ходу Гаусса необхідно виконати (n - k) ділень, (n - k)(n - k + p + 1) множень та складань. Використовуючи формулу для ряду 12 + 22 + 32 + … + m2 = m(m + 1)(2m + 1)/6, отримаємо

На зворотному ходу необхідно виконати n ділень та  множень і складань, тому fA(n) = n3/3 + n2 = O(n3) при р = 1.(2.19)

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

Таблиця 2.1. Залежність часу прямого і зворотного ходів від розміру задачі

n

Прямий хід, с

Зворотний хід, с

10

0.005

0.0008

100

5

0.075

1000

5000 (1.5 год.)

7.5

Алгоритм Гаусса є послідовним алгоритмом, орієнтованим на виконання на одно процесорній ЕОМ

2.3. Трикутний розклад матриці

2.3.1. Зв'язок методу Гаусса з розкладанням матриці на множники

Алгоритм Гаусса можна компактно записати в матричних позначеннях. Він відповідає розкладанню матриці A на добуток більш простих матриць. Розглянемо для наочності спочатку систему Ax = b, що складається з трьох рівнянь:

(2.20)

Виключення невідомого x1 з двох останніх рівнянь системи (2.20) здійснюється такими операціями: 1) діленням першого рівняння на a11  0, 2) відніманням перетвореного першого рівняння, помноженого на a11, з рівнянь i = 2,3. Перша операція рівносильна множенню системи рівнянь зліва на діагональну матрицю

;

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

.

Звідси випливає, що виключення x1 рівносильне множенню системи зліва на матрицю

, (2.21)

яку називають елементарною нижньою трикутною матрицею.

Перетворимо за допомогою L1 початкову систему, тобто запишемо її у вигляді:

. (2.22)

Перепишемо систему (2.22) у вигляді

(2.23)

де c1,j, y1,a(1)ij,b(1)ij,i,j = 2,3 визначаються формулами (2.14), (2.15) и (2.16), і здійснимо другий крок методу Гаусса, тобто виключимо невідоме x2 з останнього рівняння. Це виконується множенням системи (2.23) зліва на елементарну матрицю

, (2.24)

внаслідок чого отримуємо:

. (2.25)

Отже, після другого кроку виключення ми приходимо до системи (2.25), яку можна записати у вигляді

, (2.26)

де матриці L1 і L2 визначені згідно (2.21), (2.24). Нарешті, множачи (2.26) на матрицю

, (2.27)

одержуємо систему 

L3L2L1Ax = L3L2L1b, (2.28)

матриця якої

. (2.29)

Запишемо систему рівнянь (2.28) в остаточній формі

.

З виразу (2.29) випливає, що

A = U, (2.30)

де = L1 - 1L - 12 L - 13 нижня трикутна матриця.

Отже, U  розкладання матриці A може бути отримано за допомогою елементарних трикутних матриць: спочатку будуються матриці L1, L2, L3 і обчислюється U = L3L2L1A і потім знаходиться = L1 - 1L - 12 L - 13. Відзначимо, що обернені матриці  мають простий вигляд:

.

При цьому матриця  є нижньою трикутною матрицею:

,

на головній діагоналі якої розташовані ведучі елементи методу виключення.

2.3.2. Умови застосовності методу Гаусса

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

LnLn - 1L1Ax = LnLn - 1L1b, (2.31)

де елементарна нижня трикутна матриця Lk на kому кроці має вигляд

(2.32)

Елементарна нижня трикутна матриця Lk здійснює виключення невідомого xk з рівнянь з номерами (k + 1), (k + 2), …, n. Матриці Lk - 1 існують і мають вигляд:

(2.33)

Очевидно, що матриці Lk існують, якщо a(k - 1)kk  0 для кожного k = 1,2,…,n. Остання умова буде виконана, якщо всі кутові мінори матриці A відмінні від нуля. Переконаємося в цьому. Позначимо через |Am| кутовий мінор матриці A порядку m :

Нехай Am, m,Um — матриці кутового мінору m–го порядку матриць A, ,U тобто:

, .

Згідно (2.30)

Am = mUm.

Оскільки

,

то

.

Отже,

оскільки всі кутові мінори матриці A відмінні від нуля. Якщо хоча б один з кутових мінорів матриці A дорівнює нулю, то розглянуте вище U–розкладання неможливе. Це легко бачити на прикладі матриць другого порядку. Отже, метод Гаусса можна застосовувати тільки тоді, коли всі кутові мінори матриці A відмінні від нуля.

Запис методу Гаусса у вигляді (2.29) детально описує процес виключення. Тепер його можна застосувати іншим чином. Нехай дані матриця A і вектор b. Спочатку проводиться розкладання A в добуток двох трикутних матриць, A = U. Початкова система набуває вигляду Ux = b, розв’язок якої рівносильний послідовному розв’язку двох наступних систем рівнянь

y = b, (2.34)
Ux = y (2.35)

з трикутними матрицями, звідки і знаходиться шуканий вектор x. Розкладання A = U відповідає прямому ходу методу Гаусса, а розв’язок системи (2.34)–(2.35) — зворотному ходу.

Розглянутий вище алгоритм (2.29) приведення системи рівнянь до системи з верхньою трикутною формою ефективно реалізується на паралельних процесорах. Відомо, що систоличний алгоритм перемноження двох матриць розмірності n n на SIMD матричного типу реалізується за час, який рівний виконанню n множень, n - 1складань і 3(n - 1) зсувів (параграф 1.5), тому приведення системи до вигляду (2.29), тобто прямий хід методу Гауса, може бути реалізовано за 5n2 + n машинних операцій на матричному процесорі.

Приклад 2.2.

Розв’язати лінійну систему рівнянь

,

використавши елементарні нижні трикутні матриці Lk для виключення невідомих при реалізації методу Гаусса.

У відповідності з формулами (2.21), (2.24) і (2.27) обчислюємо:

,

а по формулі (2.29) обчислимо матрицю U:

.

Далі визначимо матрицю = L1 - 1L - 12 L - 13:

.

І, нарешті, по формулі (2.34) знайдемо вектор y:

,

а по формулі (2.35) — вектор розв’язку х:

.

2.3.3. Матрична форма методу Гауса з вибором головного елемента

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

Матрицею перестановок P називається квадратна матриця, у якої в кожному рядку і в кожному стовпці лише один елемент відмінний від нуля і рівний одиниці.

Елементарною матрицею перестановок Pki називається матриця, отримана з одиничної матриці перестановкою k–го і i–го рядків.

Наприклад, елементарними матрицями перестановок третього порядку є матриці

,  , .

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

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

.

2. Для будь–якої квадратної матриці A матриця Pki відрізняється від A перестановкою k–го і i–го рядків.

3. Для будь–якої квадратної матриці A матриця APkiвідрізняється від A перестановкою k–го і i–го стовпців. Нижче наведені відповідні приклади:

Приклад 2.3.

Розв’яжемо систему методом Гауса з вибором головного елемента по стовпцю:

В першому стовпці найбільший елемент знаходиться в третьому рядку. Переставимо ці рядки за допомогою матриці P13

.

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

,

де введені позначення для початкової матриці Q і вектора правої частини початкової системи рівнянь f. Після підстановки відповідних значень знаходимо:

.

Виключимо невідоме x1 з двох останніх рівнянь. Для цього утворимо елементарну нижню матрицю L1:

і перетворимо систему з її допомогою. В результаті перейдемо до системи

або 

.

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

.

З її допомогою отримаємо таку систему

 

або 

.

Виключимо невідоме x2 з останнього рівняння. Для цього утворимо елементарну нижню матрицю L2:

і перетворимо систему з її допомогою. Вона набуде вигляду

або 

.

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

,

внаслідок чого остаточно одержуємо:

.

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

. (2.36)

При цьому матриця

 (2.37)

є верхньою трикутною матрицею з одиничною головною діагоналлю.

Відмінність від звичайного методу Гаусса полягає в тому, що як співмножники в (2.37) разом з елементарними трикутними матрицями Lk можуть бути присутні елементарні матриці перестановок Pki.

Покажемо, що з (2.37) випливає розкладання

PQ = LU, (2.38)

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

 (2.39)

По властивості 2 матриця P23L1 отримується з матриці L1 перестановкою другого і третього рядків: 

.

Матриця  згідно властивості 3, отримується з P23L1 перестановкою другого і третього стовпців:

,

тобто   нижня трикутна матриця, що має обернену.

З (2.39), враховуючи рівність P23 = P - 123, отримаємо

 (2.40)

Звідси і з (2.39) бачимо, що

де позначено .

Оскільки P  матриця перестановок і L  нижня трикутна матриця, розкладання (2.38) доведено. Воно означає, що метод Гаусса з вибором головного елемента по стовпцю еквівалентний звичайному методу Гаусса, застосованому до матриці PQ, тобто до системи, отриманої з початкової системи перестановкою деяких рівнянь. В даному прикладі матриця перестановок P має вигляд: 

.

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

Загальний висновок. Результат, отриманий тут для окремого прикладу, справедливий і для будь–якої системи рівнянь. Взагалі метод Гаусса з вибором головного елемента по стовпцю можна записати у вигляді

(2.41)

де Pk,Ii елементарні матриці перестановок такі, що k jk n і Lk елементарні нижні трикутні матриці.

Звідси, використовуючи співвідношення перестановок, аналогічні (2.40), можна показати, що метод Гаусса з вибором головного елемента по стовпцю еквівалентний звичайному методу Гаусса, застосованому до системи

PAx = Pb, (2.42)

 де P деяка матриця перестановок.

Отже, якщо, detA то існує матриця перестановок P така, що матриця PA має відмінні від нуля кутові мінори.

Наслідок 1. Якщо detA ≠ 0 то існує матриця перестановок P така, що справедливе розкладання

PA = LU, (2.43)

де L — нижня трикутна матриця з відмінними від нуля діагональними елементами і U — верхня трикутна матриця з одиничною головною діагоналлю.

2.4. Алгоритми LU–розкладу без операцій матричного множення

2.4.1. Базові формули перетворення

Трикутні матричні множники у формулі (2.30) A = U, на які розкладається матриця A, на однопроцесорних ЕОМ одержують не приведеною вище процедурою матричних перетворень, заснованих на використанні послідовності елементарних нижніх трикутних матриць Lk , а з допомогою прямих рекурентних формул перетворення, отриманих на основі формул множення матриць. Дійсно,

, (2.44)
, (2.45)

тому що

,

при цьому ;lsk = 0 для k > s і ukj = 0 для k>j.

Оскільки вибрані значення l33 = 1 то з виразу (2.44) випливає:

 звідки .

З виразу (2.45) знаходимо:

         звідки    ,  s = j + 1,...,

Отже, елементи нижньої = L і верхньої U матриць обчислюються по формулах:

(2.46)

де uss ≠ 0. Нижче в параграфі 2.5.3 буде показано можливість застосування формул (2.46) і для випадку uss = 0.

Формули (2.34), (2.35) зводяться до

,   (2.47)

Порядок віднімання попарних добутків елементів lsk і ukj, розташованих в рядку s і стовпці j, при перетворенні елемента початкової матриці А в елемент матриць L або U показано на рис.2.2. При цьому елемент asj, розташований на діагоналі матриці А або справа від неї, перетворюється в відповідний елемент матриці U шляхом віднімання з його початкового значення вказаних попарних добутків елементів lsk і uk ( рис.2.2, а), а елемент asj, розташований нижче діагоналі матриці А, перетворюється у відповідний елемент матриці L шляхом віднімання з його початкового значення вказаних попарних добутків елементів lsk і uk і нормування результату по значенню ujj (рис. 2.2,б).

 

Рис. 2.2. Порядок перетворення елементів матриці А в елементи матриці U і матриці L

Неважко бачити, що формули (2.46) обчислення елементів матриць L і U практично співпадають з формулами (2.14) і (2.15) методу Гаусса для перерозрахунку значень елементів матриці А при послідовному обнуленні елементів стовпців, що лежать нижче від діагонального елементу, особливо для випадку, коли віднімання попарних добутків елементів lsk і uk здійснюється для всіх елементів неперетвореної частини матриці А на кожному кроці, пов'язаному з перетворенням елементів поточного рядка (стовпця) матриці А. Тому складність LU–розкладу при виконанні на однопроцесорній ЕОМ оцінюється також величиною fA(n) = n3/3 + n2 = O(n3), до якої добавляється складність розв’язку двох систем лінійних рівнянь з трикутними матрицями (2.47), що складає приблизно n2 операцій множення/ділення. 

Цей показник набагато менший, ніж у випадку знаходження трикутних матричних множників за формулою (2.31) на однопроцесорній ЕОМ, який вимагає виконання  множень двох матриць, або в цілому n4 операцій множення/ділення, якщо врахувати складність процедури множення двох матриць (1.18).

Основна перевага LU–розкладу в порівнянні з методом Гаусса, яка випливає з формул (2.47), це можливість при знайдених L і U та різних векторах правої частини b по результатах попереднього розкладу багаторазово повторювати тільки зворотний хід розв’язку системи лінеаризованих рівнянь.

Приклад 2.4.

Нехай задана матриця А розмірності [3х3].

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

  

де

Для заданих чисельних значень елементів матриці одержуємо:

 

У відповідності з формулами розв’язку (2.47)

Звідки y1 = 1, y2 = 4 - 1/2 = 7/2, y3 = 1 - 3/2 - 1/5∙7/2 = - 6/5.


2.4.2. Метод Дуллітла і Краута

Є декілька методик організації процедури перетворення елементів матриці А при LU–перетворенні. У більшості випадків початкова матриця розгортається по змінним напрямам «рядок–стовпець»:

Тому формули (2.46) використовуються так: спочатку перший рядок початкової матриці А переноситься без змін як перший рядок до матриці U, а елементи першого стовпця матриці А, нормовані по значенню діагонального елемента, переносяться в перший стовпець матриці L. Потім елементи другого рядка a2s початкової матриці перетворюються в елементи матриці U (шляхом віднімання отриманих раніше попарних добутків елементів l21 і u1s) і елементи другого стовпця as2 в елементи другого стовпця матриці L (шляхом віднімання отриманих раніше попарних добутків елементів lsk і uk і діленням результату на u22) і т.д.

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

Спочатку перший рядок матриці А переноситься як перший рядок до матриці U, потім елементи asj наступних рядків, які стоять до діагональної позиції, перетворюються в елементи матриці L, а елементи, що займають діагональні позиції і розташовані праворуч від діагоналі, перетворяться в елементи матриці U згідно формул (2.46).

В методі Краута матриця розгортається по стовпцях:

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

(2.48)

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

2.4.3. Метод Холецького

Використовується для розв’язку систем лінійних рівнянь з симетричними додатними матрицями (aij = aji). В цих випадках вважатимемо, що ukk = lkk., usj = ljs.

З добутку двох матриць

за правилами матричного множення знаходимо співвідношення між елементами матриць знаходимо:

 

З формули (2.46) маємо:

,

. (2.49)

Тому перетворення Холецького для симетричних матриць набуває вигляду:

 (2.50)

 (2.51)

Приклад 2.5.

Користуючись методом Холецького, розкласти матрицю

Згідно формул (2.50) і (2.51) знаходимо:


Приклад 2.6.

Повторимо, користуючись співвідношеннями (2.46), розв’язок системи лінійних рівнянь з прикладу 2.2, отриманий раніше за допомогою послідовності елементарних матриць виключення для матричного варіанту метода Гауса.

Початкова система

Після LU–розкладу отримаємо

 

У відповідності з формулами розв’язку (2.47):

Звідки y1 = 6, y2 = - 4 + 6/3 = - 2, y3 = 5 - (8/3)∙(6) + 2/15∙(2) = - 3/5.


2.4.4. Знаходження оберненої матриці через LU–розклад

Знаючи розкладання A = LU, можна визначити обернену матрицю з умови A - 1 = U - 1L - 1. Позначивши K = L - 1 і M = U - 1, знаходимо ці матриці К і М з умов:



У відповідності з (2.47) визначаємо послідовно стовпці матриць К і М :

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

fA(n) = 2/3n3що робить її однією з найефективніших процедур обертання матриць.

Приклад 2.7.

Знайдемо обернену матрицю для

Спочатку знайдемо матриці

і

Тоді


3.2.2. Метод прогонки

Ефективним для розв’язку лінійних систем рівнянь із стрічковими матрицями є також метод прогонки. Розглянемо його застосування на тому ж прикладі тридіагональної системи, яка розв'язувалася раніше LU–розкладанням (3.2). Запишемо систему у вигляді:

 (3.11)

Розв’яжемо систему (3.11), виконавши аналог прямого ходу Гаусса

 (3.12)

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

 (3.13)

Знаходження прогоночних коефіцієнтів по (313) з урахуванням початкових значень w1 = ( - c1/a1),ν1 = d1/a1 називають прямим ходом методу прогону.Після цього з (3.12) визначають значення невідомих:

 (3.14)

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

Приклад 3.4.

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

.

Знайдемо прогоночні коефіцієнти , скористувавшись формулами (3.13) і враховуючи значення елементів діагоналей матриці: головної :a = [2 3 4 5 3], верхньої c = [1 1 1 1 0] , нижньої діагоналей b = [0 1 1 1 1], а також вектор правої частини d = [1 - 1 2 - 3 2]t.Послідовно обчислимо:





Тепер використаємо формулі (3.14) і послідовно знаходимо:


 

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

84544. Місцеві міогенні механізми регуляції серцевої діяльності 48.71 KB
  Залежність ССС від вихідної довжини КМЦ. Залежність ССС від опору вигнанню рівня артеріального тиску. Залежність ССС від ЧСС. Тому суть цього механізму можна викласти так: чим більше крові притікає до серця під час діастоли тим більша вихідна довжина КМЦ тим більша ССС СО.
84545. Характер і механізми впливів симпатичних нервів на діяльність серця. Роль симпатичних рефлексів в регуляції серцевої діяльності 44.58 KB
  Характер впливів симпатичної нервової системи на серце: позитивний інотропний вплив посилює силу серцевих скорочень; позитивний хронотропний вплив посилює ЧСС; позитивний дромотропний вплив посилює швидкість проведення збудження по елементам провідної системи серця особливо по передсердношлуночковому вузлу структурам провідної системи шлуночків; позитивний батмотропний вплив збільшення збудливості. Медіатор норадреналін взаємодіє переважно з βадренорецепторами оскільки αадренорецепторів тут майже немає при цьому...
84546. Характер і механізми впливів парасимпатичних нервів на діяльність серця. Роль парасимпатичних рефлексів в регуляції серцевої діяльності 44.78 KB
  Механізм впливів блукаючого нерва на серце повязаний із дією медіатора ацетилхоліну на мхолінорецептори КМЦ типових і атипових. В результаті підвищується проникність мембран КМЦ для йонів калію посилення виходу йонів із клітини за градієнтом концентрації що в свою чергу веде до: розвитку гіперполяризації мембран КМЦ; найбільше цей ефект виражений в клітинах з низьким вихідним рівнем мембранного потенціалу найбільше в вузлах АКМЦ: пазуховопередсердному та передсердношлуночковому де МПС = 60мВ; менше в КМЦ передсердь; найменше ...
84547. Гуморальна регуляція діяльності серця. Залежність діяльності серця від зміни йонного складу крові 44.41 KB
  Залежність діяльності серця від зміни концентрації йонів в плазмі крові. Найбільше клінічне значення має вплив йонів калію. При гіпокаліємії зниження концентрації йонів калію в плазмі крові нижче 1ммоль л розвиваються різноманітні електрофізіологічні зміни в КМЦ. Характер змін в КМЦ залежить від того що переважає: втрата йонів калію клітинами чи міжклітинною рідиною.
84548. Особливості структури і функції різних відділів кровоносних судин у гемодинаміці. Основний закон гемодинаміки 52.71 KB
  При такому підході видно що кровоносна система є замкненою системою в яку послідовно входять два насоси і судини легень і паралельно судини решти областей. Судини у системі крові виконують роль шляхів транспорту. Рух крові по судинам описує основний закон гемодинаміки: де Р1 тиск крові на початку судини Р2 в кінці судини R тиск який здійснює судина току крові Q обємна швидкість кровотоку обєм який проходить через поперечний переріз судини за одиницю часу. Отже рівняння можна прочитати так: обєм крові що проходить...
84549. Значення в’язкості крові для гемодинаміки. Особливості структури та функції різних відділів судинної системи 44 KB
  Вязкість крові залежить від таких 2ох факторів. Від зміни лінійної швидкості руху крові. Вязкість крові складає 45 50 умовних одиниць а плазми 17 23 гривні.
84550. Лінійна і об’ємна швидкості руху крові у різних ділянках судинного русла. Фактори, що впливають на їх величину 41.83 KB
  Обємна швидкість руху крові той обєм крові котрий проходить через поперечний переріз судини за одиницю часу. Замкнута система кровообігу може нормально функціонувати лише при умові що обємна швидкість кровотоку в будьякій ділянці однакова. Лінійна швидкість руху крові швидкість руху частинок крові відносно стінок судини. Оскількм ХОК в різних ділянках однаковий лінійна швидкість кровотоку визначається площею поперечного перерізу.
84551. Кров’яний тиск і його зміни у різних відділах судинного русла 41.24 KB
  Головним фактором який впливає на формування кровяного тиску є ЗПОзагальний периферичний опір сумарний опір всіх судин великого кола кровообігу. Він забезпечує падіння тиску крові з 100 в аорті до 0 мм рт. Оцінити внесок судин різних областей в його створення можна по падінню тиску ΔР крові на рівні цих судин так як ΔР = Q R а Q в даний момент часу однаковий в будьякій ділянці судинної системи аорта всі артеріоли всі капіляри всі венули і т. Загальне зниження тиску на ділянці аорта нижня порожниста вена складає 100 мм.
84552. Артеріальний тиск, фактори, що визначають його величину. Методи реєстрації артеріального тиску 43.25 KB
  Методи реєстрації артеріального тиску.; 4 Середньодинамічний рівень тиску який забезпечував би ту ж величину ХОК Q яка має місце в реальних умовах якби не було б коливань артеріального тиску. Фактори що визначають величину артеріального тиску: 1. ХОК нагнітальна функція лівого серця більше впливає на рівень систолічного тиску; 2.