69318

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

Лекция

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

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

Украинкский

2014-10-03

542 KB

12 чел.

Лекція 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) і послідовно знаходимо:


 

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

20034. Новая Россия в 90 годы 20 века 16.18 KB
  В середине 1980 административные структуры в союзных республиках начали борьбу за усиление собственной власти начались трения между коренными жителями и русскоязычным населением рухнул миф о дружбе народов СССРвыступление в казахстане столкновение в фергане наколились взаимоотношения грузии с абхазией с целью прекратить эти волнения горбачев задумал подписание нового союзного договора подписание которого было назначено на 20 августа 1991 19 авг. Начался антигосударственный переворот по радио было объявлено об отстранение президента...
20035. Гражданская война (1918-1920). Причины, этапы, итоги, последствия войны 16.63 KB
  Причинами гражданской войны в России можно считать противостояние двух политических лагерей – красных и белых красные –большевики бедные крестьяне и рабочие белые – зажиточное крестьянство офицеры казаки дворянство студенчество. Войны являлась прежде всего участие иностранных держав они поддерживали белыхиностранная интервенция. Многочисленные хорошо вооруженные и организованные за счет Антанты армии белых генералов взяли ее в кольцо. Декабрь 19201922 гокончательный разгром белого движения на юге России Причины победы красных в...
20036. Советское общество в 1920-е года 10.88 KB
  Началось антибольшевистское движение: крестьяне выступали в Тамбовской и Воронежской губерниях рабочие в Москве и Петрограде матросы в Кронштадте НЭП экономическая политика проводившаяся в Советской России и СССР в 1920е годы Март 1921г. была провозглашена НЭП 1. Привлекался иностранный капитал Концессии для участия в российской промышленности Итог НЭПа: экономика страны достигла довоенного уровня. К концу 20х годов НЭП был свернут.
20037. Сталинская модернизация 15.15 KB
  Ее главными мероприятиями стали индустриализация коллективизация. Коллективизация Официально коллективизация началась 7 ноября 1929 г. Сталину становится ясно что коллективизация может привести к серьезному экономическому и политическому кризису . сплошная коллективизация возобновилась.
20038. Дайте оценку Мюнхенскому договору и его последствиям 7.29 KB
  23 августа 1939 Пакт о ненападении Германии и СССР. Получившее название МолотоваРиббентропа к пакту прилагаются секретные материалы и карта Европы распределяющая влияние СССР и Германии на страны Европы. СССР заявил о своей готовности помочь Чехословакии в случае начала войны. Руководители Англии и Франции боялись что Гитлер развяжет войну в Европе что приведет к резкому усилению влияния СССР.
20039. Рычажные механизмы. Классификация. Конструкции. Регулировка длин рычагов 852 KB
  Регулировка длин рычагов. Рычажные механизмы состоят из рычагов стержней ползунов соединенных в кинематические пары. Подвижные звенья конструктивно могут быть выполнены в виде рычагов пранок пластин пружин стержней соединяемых между собой высшими нисшими кинематическими парами. Стержневые чаще всего имеют круглое сечение пластинчатые – прямоугольное сечение объемных или профильных рычагов может быть любое.
20040. Фрикционные механизмы. Классификация.Расчет 33.5 KB
  К ним относятся фрикционные передачи фрикционные муфты тормозные регуляторы тормоза фиксаторы замедлители и т. В зависимости от расположения осей различают передачи с параллельными и пересекающимися осями. Передачи со скрещивающимися осями используются крайне редко в связи с повышенным износом. По взаимному расположению поверхностей трения существуют передачи с внешним и внутренним контактом.
20041. Опоры вращения с трением качения. Опоры с малым моментом трения 1.29 MB
  Опоры с малым моментом трения. Опоры на ножах Опора состоит из ножа 1 контактирующего с подшипником – подушкой 2. В любом варианте опоры этого типа представляют собой контакт двух цилиндрических поверхностей максимальный угол поворота 10 момент трения минимальный. Опоры на кернах Опора на керне состоит из цапфы конической формы на конце которой выполнена сферическая полированная поверхность радиусом 01 – 015 мм и подшипника с вогнутой сферической поверхностью с радиусом =4 – 12 .
20042. Направляющие прямолинейного движения с трением скольжения 1.8 MB
  Для обеспечения поступательного движения одной детали относительно другой применяют направляющие. Требования к направляющим: надёжность технологичность невысокая стоимость Направляющие с трением скольжения просты в изготовлении имеют небольшие габаритные размеры но чувствительны к изменению температуры и уступают направляющим с трением качения в плавности и лёгкости хода. По конструктивному признаку различают: цилиндрические призматические направляющие. Цилиндрические направляющие наиболее просты в изготовлении но в них трудно...