Методи рішення систем лінійних рівнянь
1. Рішення системи лінійних рівнянь методом Гаусса
Завдання апроксимації функції, а також безліч інших завдань прикладної математики м обчислювальної фізики зводяться до задач про рішення систем лінійних рівнянь. Самим універсальним методом розв'язання системи лінійних рівнянь є метод послідовного виключення невідомих, званий методом Гаусса.
Для ілюстрації сенсу методу Гаусса розглянемо систему лінійних рівнянь:
(1)
Цю систему запишемо в матричному вигляді:
(2)
Як відомо, обидві частини рівняння можна помножити на ненульове число, а також можна з одного рівняння відняти інше. Використовуючи ці властивості, постараємося привести матрицю системи (2) до трикутного виду, тобто до вигляду, коли нижче головної діагоналі всі елементи - нулі. Цей етап рішення називається прямим ходом.
На першому кроці прямого ходу помножимо перше рівняння на і віднімемо з другого, тоді виключиться мінлива
з другого рівняння. Потім, помножимо перше рівняння на
і віднімемо з третього, тоді система (2) перетворюється в систему види:
(3)
На другому кроці прямого ходу з третього рівняння виключаємо , Тобто з третього рівняння віднімаємо друге, помножене, на
, Що приводить систему (3) до трикутного вигляду (4)
(4)
Систему (4) переписуємо у звичному вигляді:
(5)
Тепер, із системи (5) можемо знаходити рішення в зворотному порядку, тобто спочатку знаходимо з третього рівняння , Далі, підставляючи в друге рівняння, знаходимо
. Підставляючи
і
в перше рівняння системи (5), знаходимо
. Знаходження рішення
з системи (5) називають зворотним ходом.
Тепер, на основі розглянутого прикладу, складемо загальний алгоритм методу Гаусса для системи:
(6)
Метод Гаусса складається з двох етапів:
а) прямий хід - коли матриця системи (6) приводиться до трикутного вигляду;
б) зворотний хід - коли послідовно обчислюються невідомі в зворотному порядку, тобто в послідовності: .
а) Прямий хід: для приведення системи (6) до трикутного вигляду, рівняння з ненульовими коефіцієнтами при перемінної переставляються таким чином, щоб вони були вищі, ніж рівняння з нульовими коефіцієнтами
. Далі, віднімаємо перше рівняння, помножене на
, З другого рівняння, віднімаємо перше рівняння, помножене на
, З третього рівняння і т.д. Загалом, віднімаємо перше рівняння, помножене на
, З
- Го рівняння при
, Якщо
. Внаслідок цієї процедури, ми обнулили всі коефіцієнти при перемінної
в кожному з рівнянь, починаючи з другого, тобто система (6) набуває вигляду:
(7)
Далі, застосовуємо тугіше саму процедуру, для рівнянь системи (7), починаючи з другого рівняння, тобто перше рівняння виключається з «гри». Тепер намагаємося обнулити коефіцієнти при перемінної , Починаючи з третього рівняння і т.д., поки не наведемо систему до трикутного виду. Якщо
, То система завжди приводиться (теоретично) до трикутного виду. Загальний алгоритм прямого ходу можна представити у вигляді:
(8)
б) Зворотній хід: Обчислюємо невідомі за формулами:
(9)
Зауваження: для обчислення визначника системи можна використовувати трикутну форму отриманої матриці, тоді визначник цієї матриці дорівнює добутку діагональних елементів, тобто
(10)
2. Метод Гаусса з вибором головного елемента
Метод Гаусса настільки універсальний, що для деяких систем виходять практично «погані» результати, тому розробляються різні хитрі виходи із ситуації. У випадку, коли деякі коефіцієнти матриці системи близькі між собою, як відомо відносні похибки сильно зростають при вирахуванні, тому класичний метод Гаусса дає великі похибки. Щоб обійти ці труднощі, намагаються в прямому ході Гаусса вибрати те рівняння, у якого коефіцієнт при максимальний і в якості основного «гравця» вибирають саме це рівняння, тим самим обминаючи труднощі віднімання близьких чисел (якщо це можливо). Далі, коли потрібно обнулити всі коефіцієнти змінної
, Крім одного рівняння - цим особливим рівнянням знову вибирають то рівняння, у якого коефіцієнт при
максимальний і т.д., поки не отримаємо трикутну матрицю.
Зворотний хід відбувається так само, як і в класичному методі Гаусса.
3. Оцінка похибки при вирішенні системи лінійних рівнянь
Для того, щоб оцінити похибки обчислень рішення системи лінійних рівнянь, нам потрібно ввести поняття відповідних норм матриць.
Перш за все, згадаємо три найбільш часто вживані норми для вектора :
(11)
(Евклідова норма) (12)
(Чебишевская норма) (13)
Для будь-якої норми векторів можна ввести відповідну норму матриць:
(14)
яка узгоджена з нормою векторів в тому сенсі, що
(15)
Можна показати, що для трьох наведених вище випадків норми матриці задаються формулами:
(16)
(17)
(18)
Тут - Є сингулярними числами матриці
, Тобто це позитивні значення квадратних коренів
- Матриці
(Яка є позитивно-певної матрицею, при
).
Для речових симетричних матриць - Де
- Власні числа матриці
.
Абсолютна похибка рішення системи:
(19)
де - Матриця системи,
- Матриця правих частин, оцінюється нормою:
(20)
Відносна похибка оцінюється за формулою:
(21)
де .
4. Ітераційні методи рішення систем лінійних рівнянь
Розглянемо систему лінійних рівнянь, яка погано вирішується методами Гауса. Перепишемо систему рівнянь у вигляді:
(22)
де - Задана числова матриця
-Го порядку,
- Заданий постійний вектор.
4.1 Метод простої ітерації Якобі
Цей метод полягає в наступному: вибирається довільний вектор (Початкове наближення) і будується Ітераційна послідовність векторів за формулою:
,
(23)
Наведемо теорему, яка дає достатня умова збіжності методу Якобі.
Теорема. Якщо , То система рівнянь (22) має єдине рішення
і ітерації (23) сходяться до рішення.
Легко помітити, що ця теорема є простим узагальненням теореми про стислих відображеннях вивчених нами раніше для однокрокового ітераційного процесу в загальному вигляді. Всі оцінки, отримані раніше, переносяться і для системи рівнянь, різниця лише в поняттях відповідних норм. Узагальнюючи метод простої ітерації Якобі для випадку системи рівнянь:
(24)
Будуємо алгоритм рішення:
а) переписуємо рівняння (24) в однорідному вигляді і множимо на постійну - Яку далі знайдемо з умов збіжності ітераційного процесу:
(25)
б) додаємо до обох частин (25) і отримуємо:
(26)
в) будуємо итерационную формулу Якобі:
(27)
де постійну знаходимо з умов збіжності ітераційного процесу (27), який в даному випадку має вигляд:
(28)
де - Вектор-функція з (26) або виходячи з теореми про стислих відображеннях
, Де
- Одинична матриця.
Розглянемо числовий приклад:
Нехай маємо систему рівнянь:
Переписуємо систему у вигляді:
Складаємо итерационную формулу:
Коефіцієнт вибираємо з умов:
, Тобто
.
4.2 Метод Гаусса-Зейделя
Для вирішення лінійної системи рівнянь розроблено безліч ітераційних методів. Тим більше, що метод простої ітерації Якобі сходиться повільно. Одним з таких методів є метод Гаусса-Зейделя.
Для ілюстрації методу розглянемо числовий приклад:
(29)
Рівняння переписані таким чином, що на головній діагоналі стоять максимальні для кожного рівняння коефіцієнти.
Починаємо з наближення . Використовуючи перше рівняння, знаходимо для
нове значення
за умови
.
(30)
Беручи це значення і
з другого рівняння, знаходимо
, Далі з третього рівняння знаходимо
,
. Ці три величини дають нове наближення і можна повторити цикл з початку, отримуємо:
,
,
і т.д. Ітерації продовжуються до виконання нерівності
.
Загальний алгоритм методу Гаусса-Зейделя має вигляд:
Нехай
(31)
де у матриці - Все діагональні елементи відмінні від нуля, тобто
(Якщо
, Тоді переставляємо рядка так, щоб домогтися умови
). Якщо
-Е рівняння системи (31) розділити на
, А потім всі невідомі крім
- Перенести в праву частину, то ми прийдемо до еквівалентної системі види:
(32)
де ,
,
(33)
Метод Гаусса-Зейделя полягає в тому, що ітерації проводяться за формулою:
(34)
де - Номер ітерації, а
.
Зауваження: для збіжності методу (34) достатньо виконання хоча б однієї з умов:
а)
,
(35)
б) - Симетрична і позитивно-визначена матриця.
5. Рішення системи лінійних рівнянь методом Рітца
Якщо - Симетрична і позитивно-визначена матриця, то завдання вирішення лінійної системи рівнянь:
(36)
еквівалентна задачі знаходження точки мінімуму функції багатьох змінних:
(37)
де скалярні твори розуміються в сенсі , Тобто
(38)
Інакше кажучи, рішення системи лінійних рівнянь (36) доставляє мінімум функції багатьох змінних:
(39)
І навпаки, точка мінімуму функції (39) є рішенням системи лінійних рівнянь (36).
Таким чином, метод Рітца дозволяє рішення лінійної системи рівнянь з симетричною і позитивно-певної матрицею звести до задачі знаходження точки мінімуму функцій багатьох змінних. А це завдання ми вже вміємо вирішувати.
6. Рішення системи лінійних рівнянь з трехдіаганальной матрицею методом прогонки Томаса
При вирішенні завдань кінцево-різницевими методами або методом кінцевих елементів, часто вирішення завдання зводиться до вирішення лінійної системи рівнянь з трехдіаганальной матрицею коефіцієнтів, тобто з матрицею, де всі елементи нулі, крім трьох діагоналей (в околиці головної діагоналі); розглянемо систему з трехдіаганальной матрицею:
(40)
для вирішення цієї лінійної системи рівнянь, звичайно, можна застосовувати метод Гаусса, але тоді довелося б робити багато необов'язкових операцій з нулями. Щоб заощадити час обчислень і не працювати зайвий раз з нулями, Томас (1949 рік) розробив спеціальний алгоритм розрахунку. Розраховуючи за алгоритмом Томаса елементи одержуваної трикутної матриці, ми слідуємо методу Гаусса, з уточненням, що з нулями ніяких дій не виробляємо; алгоритм Томаса називають - методом прогонки.
Для рішення системи (40) методом прогонки - Томаса діємо наступним чином:
а) прямий хід:
(41)
Зауваження: після проведення прямого ходу передбачається, що всі , І
- Незмінні (що очевидно).
б) зворотний хід:
(42)
Таким чином, для системи лінійних рівнянь з трехдіаганальной матрицею найбільш економним є алгоритм прогонки - Томаса, який є «відфільтрованим» методом Гаусса.
Метод мінімізації нев'язки для вирішення лінійної системи рівнянь (метод найменших квадратів).
При проведенні експериментів, часто доводиться вирішувати таку завдання: визначити відомих
, Що безпосередньо не вимірюються, а вимірюються величини
пов'язані з обумовленими змінними
. Вимірювання не вільні від випадкових помилок, якими не можна нехтувати.
Число спостережуваних величин більше числа невідомих . Нехай відомо, що величини
пов'язані між собою лінійною залежністю:
,
,
. (43)
Коефіцієнти - Вважаються відомими і необтяжених випадковими помилками. Система (43) називається системою умовних рівнянь.
Якби всі числа були точними, то невідомі
,
могли б бути визначені з будь-яких
- Рівнянь системи
. Але так, як
- Визначені з помилками, то система умовних рівнянь несовместна (перевизначена, т.к.
), Існують «нев'язки»:
,
(44)
завдання тепер полягає в тому, щоб знайти такі значення , При яких функція нев'язки
- Мінімально за деякою нормі, тобто ми шукаємо такі
, При яких норма нев'язності
- Мінімальна.
У методі найменших квадратів, як норми розглядають дискретну норму Гаусса:
(45)
Очевидно, що ця норма мінімальна тоді, коли мінімально подкоренное вираз, тобто сума квадратів нев'язок .
(46)
Умови існування мінімуму для функцій спеціального виду мають вигляд:
,
, (47)
тобто задача зводиться, як і в загальній теорії наближень, до розв'язання системи нормальних рівнянь.
Для прикладу розглянемо рівнянь з трьома невідомими, система умовних рівнянь має вигляд:
(48)
Тоді система відповідних нормальних рівнянь має вигляд:
(49)
Рішення системи (49) дає рішення задачі (48) найкращим наближенням, в сенсі дискретної норми Гаусса.
Зауваження:
1) класичний метод Гаусса, метод Гауса з вибором головного елемента, метод Якобі і метод мінімізації нев'язки є загальними методами і застосовуються для визначення рішення невироджених систем лінійних рівнянь, коли провідні (великі по модулю) елементи матриці системи розташовані в околиці головної діагоналі (система добре обумовлена), якщо ж система погано обумовлена, тоді потрібно міняти відповідну модель, щоб вона приводила до прийнятної системи рівнянь;
2) для прискорення збіжності методів розроблені спеціальні методи - метод Гауса-Зейделя, методи релаксації та інші, які застосовуються лише для вузького класу систем - з симетричної, позитивно-певної матрицею; з ненульовими діагональними елементами;
3) для потреб різницевих рівнянь розроблені спеціальні алгоритми прогонки Томаса, які є «економними» методами Гауса для трехдіагональних матриць системи лінійних рівнянь.
Література
Т. Шуп. Рішення інтегральних завдань на ЕОМ. Світ., М., 2002
Л. Коллатц, Ю. Альберхт. Завдання з прикладної математики. Світ., М., 1998.
Т.А. Обгадзе. Елементи математичного моделювання. Навчальний посібник. Грузинський Політехнічний Інститут ім. В.І. Леніна, Тбілісі, 1999.