Размещено на http://www.allbest.ru/

Зміст

ВСТУП

РОДІЛ I. Основні поняття

РОЗДІЛ ІI. Методи розв'язання СЛАР

2.1 Метод простої ітерації

2.2 Метод Зейделя

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

2.4 Метод оберненої матриці

РОЗДІЛ ІІІ. Метод Гаусса

3.1.1 Метод Гаусса розв'язання загальної с-ми лін. рівнянь

3.1.2 Алгоритм Гаусса зведення с-ми до східчастого виду послідовним застосуванням елементарних перетворень

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

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

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

4.1 Метод LU факторизації

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

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

ВИСНОВОК

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

Вступ

Актуальність теми:

Метою дослідження: Дослідити методи факторизації матриць, зокрема LU розклад.

Завдання дослідження:

1.Розглянути основні поняття чисельних методів розв'язання СЛАР.

2. Розглянути метод Гауса.

3. Розглянути метод LU факторизації матриць.

5. Розв'язати задачі та проаналізувати.

Структура роботи: Робота складається із вступу, трьох розділів, висновку та списку використаної літераратури.

Розділ І. Основні поняття

Дана система m лінійних алгебраїчних рівнянь з n невідомими

(1. 1)

або, у матричній формі

(1.2)

, , . (1.3)

Означення 1. Розв'язком системи (1.1) називається n-компонентний вектор-стовбець , який перетворює матричне рівняння (1.2) у вірну числову тотожність.

Означення 2. Система називається сумісною, якщо є хоча б один розв'язок. У протилежному випадку система називається несумісною.

Означення 3. Дві системи еквівалентні, якщо множини їх розв'язків співпадає.

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

Теорема Крамера. Для того що б система лінійних неоднорідних рівнянь з невідомими мала единий розв'язок, необхідно і достатньо, щоб визначник матриці коефіцієнтів відрізнявся від нуля. У противному випадку неоднорідна система не має розв'язків або має їх безліч.

Методи розв'язання СЛАР

Методи розв'язування СЛАР можна досить чітко поділити на три групи: точні, ітераційні та ймовірнісні. Точні методи застосовні до систем з числом змінних до порядку 104, ітераційні -- 107.

Ітераційні методи

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

1. Метод простої ітерації

2. Метод Зейделя

Точні методи

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

1. Матричний метод - певна теоретична абстракція всіх інших точних методів.

2. Метод квадратного кореня -- квадратичний метод, який вимагає симетричної матриці системи.

3. Метод прогонки зручний для розв'язування систем з трьохдіагональною матрицею, які часто виникають в задачах математичної фізики.

4. Метод Гауса -- метод, найчастіше застосовуваний при ручному розв'язуванні СЛАР.

o Метод Гауса-Жордана - модифікація методу Гауса.

5. Метод Крамера -- чисто теоретичний метод, непридатний до практичного використання через обчислювальну складність (n! доданків у самому лише визначнику за Крамаром) і неточність.

Розділ ІІ. Методи розв'язання СЛАР

2.1 Метод простої ітерації

Дана система лінійних алгебраїчних рівнянь

. (1.3.1)

Зведемо систему (1.3.1) до виду:

, (1.3.2)

де - деяка матриця, а - вектор-стовбець.

Починаючи з вектора , будуємо ітераційних процес:

, , (1.3.3)

. (1.3.4)

Отримуємо послідовність векторів: .

Доведено, що якщо норма матриці менше за одиницю:

, (1.3.5)

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

2.2 Метод Зейделя

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

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

. (1.3.10)

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

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

Дана система n лінійних алгебраїчних рівнянь з n невідомими

(1.2.1)

Система (1.2.1), має єдиний розв'язок, якщо визначник цієї системи відрізняється від нуля: . Позначимо: - визначник, отриманий з заміною стовпця коефіцієнтів стовпцем коефіцієнтів (, ).

Наприклад,

. (1.2.2)

Тоді розв'язок системи рівнянь (1.2.1) отримуємо за формулами Крамера:

, . (1.2.3)

Якщо і не всі , то система (1.2.1) несумісна, тобто не має жодного розв'язку.

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

2.4 Метод оберненої матриці

Система (1.2.1) може бути записана у матричному вигляді:

, (1.2.4)

тоді, розв'язок системи (1.2.1):

, (1.2.4)

де - матриця, обернена до матриці .

РОЗДІЛ ІІІ. Метод Гаусса

Одним з найпоширеніших методів рішення систем лінійних рівнянь є метод Гауса. Цей метод (який також називають методом послідовного виключення невідомих) відомий в різних варіантах вже більше 2000 років.

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

3.1.1 Метод Гаусса розв'язування загальної системи лінійних рівнянь

Визначимо елементарні перетворення 1-го, 2-го та 3-го роду системи лінійних рівнянь таким чином:

домножити деяке рівняння на число, відмінне від 0.

поміняти два рівняння місцями.

додати до одного рівняння інше, помножене на деяке число.

Теорема 1. Елементарні перетворення переводять систему (1) в систему, еквівалентну даній.

Доведення.

Очевидно, що перетворення 1-го та 2-го роду не змінюють множину розв'язків системи.

Доведем, що перетворення 3-го роду не змінюють множину розв'язків системи. Нехай система (2) одержана з системи (1) так: до j-го рівняння додали і-те, помножене на число . Всі рівняння, крім j-го не зміняться, j-те запишеться так:

Покажемо, що довільний розв"язок ( системи (1) є також розв'язком системи (2). Дійсно, ( задовольняє всім рівнянням системи (2), крім j-го. Підставимо ( в j-те рівняння:

Оскільки ( - розв'язок системи (1), то

отже маємо

лінійний алгебраїчний рівняння перетворення

Остання рівність показує, що також задовольняють j-те рівняння системи (2).

Покажемо, що будь-який розвязок системи (2) задовольняє систему (1). Систему (1) одержимо з (2), віднявши від j-го рівняння i-те, помножене на , тобто за допомогою елементарного перетворення 3-го виду. За доведеним, будь-який розвязок вихідної системи (2) є також розвязком результуючої системи (1).

Отже, розв'язки систем (1) та (2) співпадають.

Теорема 2. Будь-яка система (1) за допомогою елементарних перетворень зводиться до східчастого виду.

В якості доведення теореми наведемо

3.1.2 Алгоритм Гаусса зведення системи до східчастого виду послідовним застосуванням елементарних перетворень

1-ий крок. Перевіряємо, чи ? Якщо так, то ставимо на перше місце рівняння, в якому коефіцієнт при х1 відмінний від 0. Далі вважаємо, що

. Далі відніматимемо від i-го рівняння перше рівняння, помножене на такий коефіцієнт, щоб після віднімання коефіцієнт при х1 став рівним 0 ( елементарне пертворення 2-го типу)

До 2-го рівняння додаєм перше, помножене на :

одержуємо: .

До 3-го рівняння додаємо перше, помножене на і т.д.

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

Після першого кроку може виявитися, що друга невідома також не входить в усі рівняння з номером i>1. Нехай xk - невідома з найменшим номером, яка входить в деяке рівняння, крім першого. Ми одержали систему

2-ий крок. Перше рівняння залишаємо без змін.

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

До 3-го рівняння додаємо 2-ге, помножене ,

до 4-го рівняння додаємо 3-є, помножене і т.д.

Таким чином вилучаємо невідому xk з 3-го, 4-го, … m-го рівняння.

3-й крок - аналогічно.

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

(3)

Тут відмінні від 0 (

Теорему доведено.

Про систему виду (3) кажуть, що вона має східчастий вид.

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

Рівняння, що йдуть після r-го, можуть бути суперечливими (якщо хоча б одне з чисел dr+1,…, dm відмінне від 0). В цьому випадку система (3), а отже і система (1), розв'язку не має.

Очевидна

Теорема 3. Система (1) є сумісною після приведення до східчастого виду вона не містить рівнянь виду , де

Якщо , то останні m-r рівнянь не несуть інформації і можуть бути відкинуті.

Означення5.

Невідомі , з яких починаються 1-е, 2-е,…, r-те рівняння системи, зведеної до східчастого виду (3), будемо називати головними, а інші, якщо такі є - вільними.

Вільним невідомим можемо надавати довільні значення. Значення головних невідомих однозначно виражаються через вільні невідомі з системи (3).

Означення6.

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

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

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

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

Алгоритм

Обирається перша зліва колонка, що містить хоч одне ненульове значення.

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

Усі елементи першого рядка діляться на верхній елемент обраної колонки.

Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання у якості першого елемента кожного рядка (крім першого) нуля.

Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.

Після повторення операцій n-1 разів отримаємо верхню трикутну матрицю.

Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.

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

Приклад

Розв'яжемо систему рівнянь:

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

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

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

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

Отримаємо:

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

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

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

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

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

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

.

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

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

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



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

(5)

Приклад.

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

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



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

Приклад.

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

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



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

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

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

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

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

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

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

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

A ? x = b (1*)

A - матриця розміру nn із сталими коефіцієнтами;

b - n-мірний вектор вільних членів;

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

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

А =L ? U, де

,

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

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

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

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

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

U ? x = у (3*)

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

L ? у = b. (4*)

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

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

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

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

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

 (5*)

для

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

x1 + u12x2 + u13x3 + … + u1nxn = y1

x2 + u23x3 + … + u2nxn = y2

x3 + … + u3nxn = y3

………………………………

xn = yn

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

для (6*)

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

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

де , де ()

, де ()

 , де ().

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

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

Для всіх

де (7*)

де (8*)

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

Крім того, .

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

для всіх

для всіх .



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

Алгоритм

1) k =1

Обчислюємо

для всіх

для всіх .

2) 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) визначаємо послідовно стовпці матриць К і М :

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

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

Приклад

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

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

і тоді:

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru