Дослідження методу ортогоналізації й методу сполучених градієнтів
Курсова робота
На тему:
"Дослідження методу ортогоналізації й методу сполучених градієнтів"
Введення
До рішення систем лінійних алгебраїчних рівнянь приводяться багато задач чисельного аналізу.
Відоме з курсу вищої алгебри правило Крамера для рішення систем лінійних алгебраїчних рівнянь практично невигідно, тому що вимагає занадто великої кількості арифметичних операцій і записів. Тому було запропоновано багато різних способів, більше придатних для практики.
Використовувані практично методи рішення систем лінійних алгебраїчних рівнянь можна розділити на дві більші групи: так звані точні методи й методи послідовних наближень. Точні методи характеризуються тим, що з їхньою допомогою принципово можливо, проробивши кінцеве число операцій, одержати точні значення невідомих. При цьому, звичайно, передбачається, що коефіцієнти й праві частини системи відомі точно, а всі обчислення виробляються без округлень. Найчастіше вони здійснюються у два етапи. На першому етапі перетворять систему до того або іншого простого виду. На другому етапі вирішують спрощену систему й одержують значення невідомих.
Методи послідовних наближень характеризуються тим, що із самого початку задаються якимись наближеними значеннями невідомих. Із цих наближених значень тим або іншому способу одержують нові «поліпшені» наближені значення. З новими наближеними значеннями надходять точно також і т.д. Розглянемо два точних методи: метод ортогоналізації й метод сполучених градієнтів.
Метод ортогоналізації
1.1 Метод ортогоналізації у випадку симетричної матриці
Нехай дана система
(1)
порядку n. Щоб уникнути надалі плутанини, над векторами поставимо риски. Рішення системи будемо розшукувати у вигляді
, (2)
де – n векторів, що задовольняють умовам
при (3)
Тут розглядається звичайний скалярний добуток векторів в n-мірному векторному просторі, тобто якщо й , те . Нехай такі вектори знайдені. Як це робиться, буде показано нижче. Розглянемо скалярний добуток обох частин системи (1) з
(4)
Використовуючи (2) одержимо:
(5)
або, у силу вибору векторів ,
. (6)
Отже, для визначення коефіцієнтів одержали систему із трикутною матрицею. Визначник цієї системи дорівнює
. (7)
Отже, якщо , те можливо знайти й перебувають вони без праці.
Особливо легко визначаться , якщо матриця А симетрична. У цьому випадку, мабуть,
(8)
і, отже,
=0 при . (9)
Тоді система для визначення прийме вид
(10)
. (11)
Метод можна узагальнити. Нехай якимсь образом удалося знайти систему 2n векторів так, що
=0 при . (12)
Множачи обидві частини рівності (1) на й використовуючи подання через , як і раніше, одержимо:
. (13)
Знову вийшла система лінійних алгебраїчних рівнянь із трикутною матрицею для визначення . Трохи ускладнивши обчислення можна одержати систему діагонального виду. Для цього побудуємо три системи векторів , так що мають місце рівності:
(14)
(15)
(16)
Тоді
, (17)
тому що при i<r
(18)
і при i>r
(19)
Таким чином,
(20)
Зупинимося докладніше на першому з описаних методів. Розглянемо випадок, коли матриця А симетрична й позитивно певна. Останнє означає, що для будь-якого вектора квадратична форма його компонент більше або дорівнює нулю, причому рівність нулю можливо в тім і тільки тім випадку, якщо вектор нульової. Як ми бачили раніше, потрібно побудувати систему векторів , що задовольняють умовам
=0 . (21)
Це побудова можна здійснити в такий спосіб. Виходимо з якоїсь системи лінійно незалежних векторів , наприклад із системи одиничних векторів, спрямованих по координатних осях:
(22)
Далі проводимо «ортогоналізацію». Приймаємо й шукаємо у вигляді
. (23)
З умови знаходимо:
(24)
Шукаємо у вигляді
. (25)
Умови спричиняють
(26)
Далі надходимо також.
Процес буде здійсненний, тому що все . Це ж забезпечить нам можливість розв'язання системи для визначення коефіцієнтів . Помітимо, що в нашім випадку це буде процес справжньої ортогоналізації, якщо в просторі векторів увести новий скалярний добуток за допомогою співвідношення
. (26)
Неважко перевірити, що уведене таким способом скалярний добуток буде задовольняти всім вимогам, які до нього пред'являються.
При рішенні системи n рівнянь за справжньою схемою потрібно зробити
(28)
операцій множення й ділення.
Метод ортогоналізації у випадку несиметричної матриці
У випадку несиметричної матриці процес ортогоналізації проводиться точно також. Нехай вектори вже побудовані. Тоді шукається у вигляді
(29)
Коефіцієнти визначаються із системи
(30)
Система у випадку несиметричної матриці буде трикутною.
Аналогічно будується система «біортогональних» векторів, тобто система 2n векторів, що задовольняють умові (12). При цьому – n довільних лінійно незалежних векторів, а вектори будуються послідовно у вигляді
(31)
Коефіцієнти перебувають із системи
(32)
Також надходимо, відшукуючи коефіцієнти й , при побудові систем векторів (14) і (15), що задовольняють умовам (16).
При цьому одержимо дві системи:
(33)
з яких і визначаємо й .
Зупинимося ще на одному методі ортогоналізації. Будемо розглядати рядки матриці А як вектори:
(34)
Перше рівняння системи ділимо на . При цьому одержимо
(35)
де
(36)
Друге рівняння системи заміниться на
(37)
де
(38)
Аналогічно надходимо далі. Рівняння з номером i прийме вид
(39)
де
(40)
Процес буде здійсненний, якщо система рівнянь лінійно незалежна. У результаті ми прийдемо до нової системи , де матриця З буде ортогональної, тобто має властивість ССў=I.
Таким чином, рішення системи можна записати у вигляді
. (41)
Практично, внаслідок помилок округлення, ССў буде відмінна від одиничної матриці й може виявитися доцільним зробити кілька ітерацій для системи .
Метод сполучених градієнтів
2.1 Перший алгоритм методу
Нехай потрібно вирішити систему лінійних алгебраїчних рівнянь
(1)
с позитивно певною матрицею A порядку n.
Розглянемо функціонала
, (2)
багаточлен, що представляє, другого порядку відносно x1, x2…, xn,… Позначимо через рішення системи (1), тобто . У силу симетричності й позитивної визначеності матриці, маємо:
При цьому знак рівності можливий лише при . Таким чином, задача рішення рівняння (1) зводиться до задачі відшукання вектора , що обертає в мінімум функціонал (2).
Для відшукання такого вектора застосуємо наступний метод.
Нехай – довільний початковий вектор, а
(4)
– вектор не в'язань системи. Покажемо, що вектор не в'язань має напрямок нормалі до поверхні в крапці . Справді, напрямок нормалі збігається з напрямком найшвидшої зміни функції в крапці . Це напрямок ми знайдемо, якщо знайдемо серед векторів , для яких , такий вектор, що
має найбільше значення. Але
Але серед векторів постійний довжини досягає максимального значення, якщо має напрямок вектора