Курсовая работа (т): Методи факторизації матриць

Теорема 4. Сумісна система є визначеною  після приведення її до східчастого виду .

3.2.1 Метод Ґаусса-Жордана

використовується для розв'язання систем лінійних алгебраїчних рівнянь <#"878153.files/image078.gif">

Запишемо її у вигляді матриці 3×4, де останній рядок є вільним членом:

Виконаємо такі дії:

До рядка 2 додамо: -4 * рядок 1.

До рядка 3 додамо: -9 * рядок 1.

Отримаємо:

До рядка 3 додамо: -3 * рядок 2.

Рядок 2 ділимо на -2

До рядка 1 додамо: -1 * рядок 3.

До рядка 1 додамо: -1 * рядок 2.

У правому стовпчику отримаємо рішення:

.

3.2.2 Зворотній хід методу Жордана-Гауса

Щоб одержати вираз головних невідомих  через вільні, віднімемо від попередніх останнє -те рівняння, , помножене на такий коефіцієнт, щоб після віднімання коефіцієнт при став рівним 0. Далі, віднімемо від попередніх передостаннє -е рівняння, , помножене на такий коефіцієнт, щоб після віднімання коефіцієнт при відповідному головному невідомому став рівним 0.

Через скінчене число кроків система (1) набуде вигляду

де  - вільні невідомі,  відмінні від 0 (. Розділивши кожне рівняння на відповідні коефіцієнти, одержимо:

       (5)

Приклад.

Дослідити систему лінійних рівнянь.

Розв’язання.

Відповідь: Система несумісна.

Приклад.

Знайти загальний і деякий частковий розв’язок системи

Розв’язання.

Головні невідомі ;

вільні невідомі .

Головні невідомі виражаються через вільні:

Надаючи вільним невідомим довільні значення , одержимо загальний розв’язок системи:

Надаючи вільним невідомим конкретних значень, наприклад, : одержимо частковий розв’язок:

Розділ ІV. LUрозклад матриці

.1 Метод LU - факторизації

Алгоритми цього методу досить близькі до методу Гауса. Основна перевага методу LU - факторизації в порівнянні з методом Гауса є можливість більш простого одержання розв’язку для різних векторів b системи лінійних алгебраїчних рівнянь

· x = b                                                        (1*)

- матриця розміру nn із сталими коефіцієнтами;- n-мірний вектор вільних членів;

х - n-мірний вектор невідомих.

Матриця системи А представляється у вигляді добутку двох трикутних матриць L та U

А =L · U, де

 ,

- нижня трикутна матриця, U - верхня трикутна матриця.

Зауважимо, що на головній діагоналі матриці U стоять одиниці. Це в свою чергу означає, що визначник матриці А дорівнює добутку діагональних елементів lii матриці L. (det U = 1; det L = l11l22…lnn; det A = det L).

Отже, систему (1) можна записати у вигляді

L · U · x = b.                                                       (2*)

Введемо допоміжний вектор у як

· x = у                                                        (3*)

Тоді можна записати, що

· у = b.                                                     (4*)

Розв’язування системи (1) або (2) відбувається в два етапи: спочатку розв’язується система L · у = b, а потім U · x = у.

Така послідовність розв’язку дає перевагу методу (в порівнянні з методом Гауса) - якщо потрібно розв’язати декілька систем з однією і тією ж матрицею А, задача суттєво спрощується, оскільки зберігаються матриці L та U.

Розв’язок системи L · у = b називається прямим ходом, а системи U · x = у - оберненим ходом.

Розглянемо прямий хід. Завдяки спеціальній формі матриці L вектор у можна легко визначити. Для цього (4*) перепишемо у вигляді системи рівнянь

Звідси можна одержати, що в загальному вигляді

                                              (5*)

 для

При оберненому ході вектор х визначається з системи рівнянь (3*)

+ u12x2 + u13x3 + … + u1nxn = y1+ u23x3 + … + u2nxn = y2+ … + u3nxn = y3

………………………………= yn

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

 для                                   (6*)

Тепер розглянемо LU - розклад матриці А.

Елементи матриці L та U визначаються за наступними формулами:

 де  , де ()

 , де ()

 , де ().

Ці ж самі формули можна записати у більш зручному вигляді (метод Краута).

У варіанті методу, що називається методом Краута, використовується наступна послідовність знаходження елементів матриць L та U () - де k - крок.

Для всіх

 де                      (7*)

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

Крім того, .

Тобто, при k =1

 для всіх

 для всіх .

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

Алгоритм

) k =1

Обчислюємо

 для всіх

 для всіх .

) k = k + 1

 де

 де .

Продовжуємо до тих пір, доки k = n.

Матрицю А можна розкласти на дві трикутні матриці L та U при умові, що головні діагональні мінори матриці А відмінні від нуля. Якщо ця умова не виконується, наприклад, для k-го головного діагонального мінора, то при обчисленні елемента lkk матриці L за формулою (7*) він стане рівним нулю. Це в свою чергу призведе до неможливості обчислення елементів ukj матриці U (ділення на нуль). Усунути таку ситуацію можна було б шляхом перевірки умов нерівності нуля головних діагональних мінорів до розкладу А = L U . Однак така перевірка пов’язана із значними затратами машинного часу, що перевищує затрати часу пов’язані із розкладом А = L U (крім того перевірка - це обчислення тих самих визначників).

Тому доцільніше проводити перевірку умови lkk = 0 безпосередньо в процесі обчислення елементів lij та uij. Тоді при виконанні цієї умови потрібно переставляти відповідний k-й рядок матриці А з наступними k + s рядками (), до тих пір, доки не виконається умова

4.2 Метод Холецького

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

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

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

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

,

.       (2.49)

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

         (2.50)

     (2.51)

Приклад

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

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

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

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

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

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

Приклад

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

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

 і  тоді:

Список використаної літератури

1. Кострикин А.И. Введение в алгебру. - М.: Наука, 1977,- 496 с.

. Фаддеев Д.К. Лекции по алгебре. - М.: Наука, 1984,- 416 с.

. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. - М.: Наука, 1977,- 521 с.

. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ. - 2013,- 582с.

. Стренг Г. - Линейная алгебра и ее применения. - М.: Наука, 1980, - 11 с.

. В. И. Приклонский, Лекции по численным методам, М., Издательство МГУ, 2000.

. В. А. Буслов, С. Л. Яковлев, Численные методы, I, II, М., Издательство СпбГУ, 2001.

. С. М. Єжов, Методи обчислень, К. ВПЦ ``Київський університет'', 2000.

. А. А. Самарский, Введение в численные методы, М., Наука, 1987.

. Е. А. Волков, Численные методы, М., Наука, 1987