Метод Гаусса

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

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

1. Основні поняття

гаусс матриця множина

Загальний вигляд системи лінійних рівнянь:

11x1+12x2+ … +1nxn=1

21x1+22x2+ … +2nxn=2 (1)

m1x1+m2x2+ … +mnxn=m

З системою (1) пов'язують дві матриці: основну матрицю (матрицю коефіцієнтів)

та розширену

Означення 1.

Впорядкована множина n чисел називається розв'язком системи (1), якщо при підстановці чисел в систему (1) замість x1,…, xn відповідно одержуємо справедливі рівності.

Означення 2.

Система лінійних рівнянь називається сумісною, якщо вона має розв'язок.

Означення 3.

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

Означення 4.

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

Приклад.

Остання система еквівалентна системі з двох рівнянь

Виразимо х1 та х2 через х3

Якщо х3 надамо довільного значення с, тобто положимо х3=с, то одержимо: х1=с, х2=-2 с. Всі можливі розв'язки даної системи ми одержимо, надаючи параметру с всіх можливих значень.

Співвідношення х1=с, х2=-2с, х3=с задають загальний розв'язок системи. Загальний розв'язок надалі будемо подавати у векторній формі: (с, -2с, с).

Якщо надамо деякого конкретного значенняя. наприклад, с=2,73, одержимо частковий розв'язок даної системи: (2,73, -5,46, 2,73).

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

Нагадаємо основні поняття, що використовуються в цьому розділі. Систему лінійних алгебраїчних рівнянь представимо у вигляді:

(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. Метод Гаусса

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

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

2.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) за допомогою елементарних перетворень зводиться до східчастого виду.

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

2.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. Сумісна система є визначеною після приведення її до східчастого виду .

2.3 Зв'язок методу Гаусса з розкладанням матриці на множники

Алгоритм Гаусса можна компактно записати в матричних позначеннях. Він відповідає розкладанню матриці 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.4 Умови застосовності методу Гаусса

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

LnLn - 1…L1Ax = LnLn - 1…L1b, (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 машинних операцій на матричному процесорі.

Приклад

Розв'язати лінійну систему рівнянь

,

використавши елементарні нижні трикутні матриці Lk для виключення невідомих при реалізації методу Гаусса.

У відповідності з формулами (2.21), (2.24) і (2.27) обчислюємо:

,

а по формулі (2.29) обчислимо матрицю U:

.

Далі визначимо матрицю = L1 - 1L - 12 L - 13:

.

І, нарешті, по формулі (2.34) знайдемо вектор y:

,

а по формулі (2.35) - вектор розв'язку х:

.

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

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

Алгоритм

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

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

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

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

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

Після повторення операцій 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.

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

.

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

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

...