69318

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

Лекция

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

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

Украинкский

2014-10-03

542 KB

10 чел.

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


 

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

80954. План вивчення теми: «Українські землі наприкінці ХУІІ— у першій половині ХУІІІ ст.» (8 клас) 36.43 KB
  Першою темою Гетьманщина наприкінці XVII на початку XVIII ст. Метою цього уроку характеризувати політичне становище Гетьманщини наприкінці XVII на початку XVIIІ ст.№2 Правобережна Україна наприкінці XVII на початку XVIII ст.
80956. Теоретичний матеріал в історичних курсах 34.9 KB
  Пояснюючий виклад історичних даних теоретичного характеру орієнтує учнів на репродуктивний спосіб роботи на просте відтворення їх з допомогою прийомів якими при викладенні користувався вчитель. Перші навчають учнів засвоювати і відтворювати в образній формі зовнішні ознаки історичних подій. Другі сприяють формуванню уміння осмислювати сутність фактичного матеріалу засвоювати теоретичні дані у вигляді історичних понять різної складності.
80957. Проведення тематичного оцінювання знань учнів з історії України 35.46 KB
  Тема на вибір студента Основною навчальною метою уроку є проведення тематичного оцінювання рівня знаньумінь і навичок. При цьому оцінювані доцільно використовувати такі форми оцінюванняякі не вимагають від п’ятикласників довгих розгорнутих відповідей. Тематичне оцінювання розглядають як підсумкову роботу кожного учня.
80958. Емпіричний і теоретичний рівні засвоєння учнями навчального історичного матеріалу 35.82 KB
  Емпіричний (від гр. еmреіrіа – досвід) рівень знання – це знання, отримане безпосередньо з досвіду з деякою раціональною обробкою властивостей і відношень обєкта, що пізнається. На емпіричному рівні школярі працюють з фактами, представленими в підручниках
80959. Методика написання плану-конспекту з історії 36.2 KB
  Молоді вчителі у конспекті зазначають: способи прийоми актуалізації опорних знаньосновних понять визначень висновків формул які учні засвоїли раніше і застосовують у практичній діяльності необхідних для сприймання учнями нового змісту; Після підготовчого етапу в конспекті описують зміст активного навчання шляхом взаємодії вчителя та учнів: виділяють логічно пов’язані етапи організації спільної навчально пізнавальної діяльності вчителя та учнів; зазначають нові факти положення уміння та навички якими повинні оволодіти школярі;...
80960. Поняття про вміння в методиці навчання історії 36.44 KB
  Пізнавальні вміння в методиці навчання історії визначають як підготовленість до свідомих і точних дій розумових і практичних і здатність учня послідовно застосовувати всю сукупність навчальних і розумових дій. Ознакою сформованого вміння є здатність учнів переносити відомі їм навчальні або розумові дії прийом в нову ситуацію вибирати і використовувати адекватні прийоми для розвязання оригінальних задач. У будьякому випадку вміння завжди буде свідомою дією адекватною цілям її застосування і змісту навчального історичного матеріалу.
80961. Складіть календарний план з історії України (Вступ до історії України, 5 клас) 36.37 KB
  Вступ до історії у 5 класі Головною метою курсу є підготовка учнів до успішного опанування систематичних курсів історії України та всесвітньої історії прищеплення інтересу до історії отримання знань у наступних класах через формування в них початкових уявлень про історію як науку та про історію України як складову світової історії елементарних вмінь з історії; поглиблення загальних дидактичних вмінь необхідних для успішного засвоєння історичної інформації в подальшому; прагнення викликати захоплення минулим України. Зміст курсу...
80962. Види пізнавальних умінь, що формуються у шкільних курсах історії 37.59 KB
  Більш складною є класифікація пізнавальних умінь за змістом. До спеціальних умінь належать ті що потрібні у навчанні конкретного предмета споріднених навчальних дисциплін. Загальновизнаною і стабільною групою спеціальних пізнавальних умінь у навчанні історії є хронологічні і картографічні вміння.