Тема 3. Чисельні методи алгебри Теоретична частина

Лінійні рівняння.

Розв'язок систем лінійних алгебраїчних рівнянь (СЛАР) належить до тих задач, які виникають майже у всіх обчислювальних проектах. Необхідно знайти n-вимірний вектор, який є рішенням СЛАР

,

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

AX=B.

Метод виключення Гауса є найбільш універсальним и поширеним методом рішення задач цього класу і використовується для систем з матрицями довільної структури. В результаті застосування методу матриця системи набуває трикутної форми

,

,

……………………………………………. (3.1)

,

.

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

.

Повторивши цю операцію до включно отримуємо, що для зведення матриці до вигляду (3.1) потрібно перерахувати її елементи і компоненти вектора правої частини за формулами

, . (3.2)

Ця частина алгоритму називається прямою ходою метода. Коефіцієнт у (3.2) називаєтьсь провідним елементом і в тому випадку, коли на якомусь кроці виключення його величина по модулю близька до нуля, необхідно поміняти місцями рядки матриці з номерами і , щоб виконувалась умова . Якщо ж жодна з таких перестановок не дає потрібного результату, то це значить, що матриця системи є виродженою і система рішень не має.

На оберненій ході визначаються власне компоненти вектора рішення

, . (3.3)

Слід відзначити, що ідея Гаусових виключень використовується не тільки для розв'язку СЛАР. Цей підхід є дуже ефективним при обчислення визначників та обернених матриць.

Після приведення матриці до трикутного вигляду її визначник може бути обчислено розкриттям по елементам першого стовпця. Так чином отримуємо формулу .

Нехай вектори, що отримані в результаті розв'язку СЛАР

,

у яких праві частини визначені наступним чином

, ,…, . (3.4)

Якщо тепер утворити матриці і , яких стовпцями відповідно будуть вектори і , то . Постільки згідно з (5.1.3) матриця є одиничною, то маємо . При розв'язку цієї задачі за допомогою класичної формули лінійної алгебри

необхідно обчислити один визначник -го порядку і для визначення алгебраїчних доповнень - визначників -го порядку. Легко бачити, що обсяг обчислень за цією формулою є набагато більшим, ніж в описаному методі. Метод простої прогонки є частковим випадком методу Гауса, для систем з трьох діагональними матрицям, тобто які мають форму (рис. 3.1),

,

Рис. 3.1

а відповідні їм системи записуються у вигляді

(3.5)

Процес рішення тут теж розбивається на два етапи. Якщо припустити, що невідомі зв’язані співвідношенням

, (3.6)

то з (5.1.4) (3.1) і (5.1.5) (3.1) можна отримати рекурентні формули для визначення прогоночних коефіцієнтів (пряма хода метода)

, ,

.

Після цього визначається невідома

.

На оберненій ході за формулою

обчислюються невідомі, що залишилися: .

Ітераційні методи розв’язку СЛАР є особливо ефективними, коли початкове наближення близьке до дійсного рішення. У випадку СЛАР це відбувається коли кілька разів необхідно розв’язувати системи, у яких елементи матриць відрізняються на малі величини. Крім цього застосування ітераційних методів доцільне у наступних випадках:

– система має настільки високий вимір, що елементи матриці не зберігаються в пам’яті ЕОМ, а обчислюються безпосередньо в процесі розв'язку СЛАР;

– матриця системи має розріджену структуру.

Нехай у першому рівнянні системи всі невідомі окрім рівні відповідно , тоді

.

Аналогічно з другого рівняння маємо

.

Легко бачити, що обсяг обчислень можна набагато скоротити, якщо попередньо поділити кожний рядок СЛАР на діагональний елемент, і таким чином виключити операцію ділення з ітераційного процесу. Таким чином, маємо формулу метода простої ітерації

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

.

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

, (3.7)

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

Задачі на власні значення.

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

, (3.8)

то називається власним числом матриці , а – власним вектором. Умова (3.8) може бути зображена у вигляді СЛАР

де – одинична матриця. Ця система є однорідною і має рішення відмінні від нуля тільки тоді коли

.

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

На практиці визначення власних значень шляхом пошуку коренів поліному використовується або ж для матриць невисоких вимірів, а в основному для обчислення комплексних . Для побудови методів рішення проблеми власних чисел використовуються наступні властивості власних чисел і векторів:

1) симетрична матриця, елементи якої є дійсними числами, має тільки дійсні власні значення;

2) власні вектори, що відповідають різним власним числам, ортогональні;

3) власні значення подібних матриць і рівні між собою, а власні вектори зв’язані співвідношенням . (Матриці і називаються подібними, якщо існує не вироджена матриця така, що ).

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

, .

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

Формально схема методу дається формулою

(3.9)

На кожній ітерації з матриці вилучається найбільший за модулем недіагональний елемент , Для цього матриця вибирається так, щоб у неї відмінні від нуля були тільки чотири елементи

, , . . (3.10)

Після підстановки (3.10) в (3.9) отримуємо рівняння для визначення величини :

.

У випадку симетричної матриці значення визначається безпосередньо:

.

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

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

Застосуємо до разів матрицю і з врахуванням визначення (3.8) будемо мати

.

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

(3.11)

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

1. Вибирається початкове наближення для вектора і обчислюється вектор

.

2. Наступне наближення визначається як

,

де – найбільша по абсолютній величіні компонента . Умовою зупинки алгоритму може бути як досягнення збіжності по власному числу зупинки

так і по власному вектору

Швидкість цього методу, як і всіх ітераційних, у значній мірі визначається початковим наближенням. Але слід відмітити, що у випадку , як витікає з (3.11), збіжність методу може суттєво уповільнитися. Щоб знайти найменше власне число, цей же алгоритм застосовується до матриці, оберненої даній.

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

(3.12)

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

Якщо , то маємо , оскільки . При (в силу властивості ортогональності власних векторів і ). Тобто, всі власні числа і вектори вихідної і модифікованої матриць крім першого співпадають. Тобто, щоб знайти друге за модулем власне число і відповідний йому вектор, розглянутий метод визначення першого числа слід застосувати до модифікованої матриці (3.12). Оскільки цей процес можна повторювати до тих пір, поки не буде розв’язана повна матрична проблема (в загальному випадку, тільки теоретично), метод називається методом вичерпування.

Нелінійні рівняння.

В залежності від вигляду функції нелінійні рівняння

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

Спочатку розглянемо трансцендентні рівняння. Інтервалом невизначеності називається інтервал, який містить корінь даного рівняння. Кінці інтервалу знаходяться з умови .

Метод половинного ділення зводиться до зменшення на кожній ітерації довжини інтервалу не визначеності до виконання умови точності де n номер ітерації де n номер ітерації.

Рис 3.1

Формування інтервалу невизначеності на ітерації проводиться за формулами

,

,

де тобто на кожній ітерації довжина інтервалу зменшується в два рази (рис 3.1).

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

,

яке є рівнянням січної (рис. 3.2), і визначається корінь цього наближення

.

Рис. 3.2

В методі Ньютона (методі дотичних) визначається безпосередньо сам корінь рівняння, а не інтервал до якого він належить (рис. 3.3). Якщо в околі точки функцію наблизити за допомогою лінійної частини ряду Тейлора

,

то і ітераційний процес будується за формулою

.

Рис. 3.3

У тому разі, коли обчислення похідної пов’язане з труднощами, використовується її скінчено-різницева апроксимація

Для збіжності методу необхідно виконання наступних умов:

1) початкове наближення мусить бути достатньо близьким до точного;

2) друга похідна повинна бути обмеженою ;

3) перша похідна не повинна бути надто малою .

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

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

ЛАБОРАТОРНА РОБОТА № 5