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

Методи факторизації матриць

Зміст

ВСТУП

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

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

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

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

.3 Метод Крамера

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

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

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

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

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

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

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

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

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

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

ВИСНОВОК

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

Вступ

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

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

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

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

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

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

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

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

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

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

     (1. 1)

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

    (1.2)

, , .       (1.3)

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

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

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

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

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

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

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

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

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

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

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

Точні методи

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

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

.        Метод квадратного кореня <#"878153.files/image008.gif">.     (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.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 - невідома з найменшим номером, яка входить в деяке рівняння, крім першого. Ми одержали систему

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

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

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

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

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

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

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

                               (3)

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

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

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

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

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

Очевидна

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

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

Означення5.

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

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

Означення6.

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