Дослідження методу ортогоналізації й методу сполучених градієнтів (86168)

Посмотреть архив целиком












Курсова робота




На тему:



"Дослідження методу ортогоналізації й методу сполучених градієнтів"




Введення


До рішення систем лінійних алгебраїчних рівнянь приводяться багато задач чисельного аналізу.

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

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

Методи послідовних наближень характеризуються тим, що із самого початку задаються якимись наближеними значеннями невідомих. Із цих наближених значень тим або іншому способу одержують нові «поліпшені» наближені значення. З новими наближеними значеннями надходять точно також і т.д. Розглянемо два точних методи: метод ортогоналізації й метод сполучених градієнтів.



  1. Метод ортогоналізації


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


(18)


і при i>r


(19)


Таким чином,


(20)


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


=0 . (21)


Це побудова можна здійснити в такий спосіб. Виходимо з якоїсь системи лінійно незалежних векторів , наприклад із системи одиничних векторів, спрямованих по координатних осях:


(22)


Далі проводимо «ортогоналізацію». Приймаємо й шукаємо у вигляді


. (23)


З умови знаходимо:


(24)


Шукаємо у вигляді


. (25)


Умови спричиняють


(26)


Далі надходимо також.

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


. (26)


Неважко перевірити, що уведене таким способом скалярний добуток буде задовольняти всім вимогам, які до нього пред'являються.

При рішенні системи n рівнянь за справжньою схемою потрібно зробити


(28)


операцій множення й ділення.


    1. Метод ортогоналізації у випадку несиметричної матриці


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


(29)


Коефіцієнти визначаються із системи


(30)


Система у випадку несиметричної матриці буде трикутною.

Аналогічно будується система «біортогональних» векторів, тобто система 2n векторів, що задовольняють умові (12). При цьому – n довільних лінійно незалежних векторів, а вектори будуються послідовно у вигляді


(31)


Коефіцієнти перебувають із системи


(32)


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

При цьому одержимо дві системи:


(33)


з яких і визначаємо й .

Зупинимося ще на одному методі ортогоналізації. Будемо розглядати рядки матриці А як вектори:


(34)


Перше рівняння системи ділимо на . При цьому одержимо


(35)


де


(36)


Друге рівняння системи заміниться на


(37)


де

(38)


Аналогічно надходимо далі. Рівняння з номером i прийме вид


(39)


де



(40)


Процес буде здійсненний, якщо система рівнянь лінійно незалежна. У результаті ми прийдемо до нової системи , де матриця З буде ортогональної, тобто має властивість СС=I.

Таким чином, рішення системи можна записати у вигляді


. (41)


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



  1. Метод сполучених градієнтів


2.1 Перший алгоритм методу


Нехай потрібно вирішити систему лінійних алгебраїчних рівнянь


(1)


с позитивно певною матрицею A порядку n.

Розглянемо функціонала


, (2)


багаточлен, що представляє, другого порядку відносно x1, x2…, xn,… Позначимо через рішення системи (1), тобто . У силу симетричності й позитивної визначеності матриці, маємо:



При цьому знак рівності можливий лише при . Таким чином, задача рішення рівняння (1) зводиться до задачі відшукання вектора , що обертає в мінімум функціонал (2).

Для відшукання такого вектора застосуємо наступний метод.

Нехай – довільний початковий вектор, а


(4)


– вектор не в'язань системи. Покажемо, що вектор не в'язань має напрямок нормалі до поверхні в крапці . Справді, напрямок нормалі збігається з напрямком найшвидшої зміни функції в крапці . Це напрямок ми знайдемо, якщо знайдемо серед векторів , для яких , такий вектор, що



має найбільше значення. Але



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


. (5)


Вектор


(6)


і приймаємо за нове наближення до рішення.

У методі сполучених градієнтів наступне наближення перебуває так. Через крапку проведемо гіперплощину (n-1) – го виміру


(7)


і через позначимо нове не в'язання системи


. (8)


Вектор спрямований по нормалі до поверхні в крапці , а вектор паралельний дотичної площини в цій крапці. Тому


. (9)


Гіперплощина (7) проходить через крапку , тому що


.


При кожному вектор паралельний деякої нормальної площини до поверхні в крапці . Знайдемо серед них той, котрий лежить у гіперплощині (7), тобто ортогональний к. З умови ортогональності маємо:


,


або


. (10)


Вектор


(11)


має напрямок нормалі до перетину поверхні гіперплощини (7) у крапці . Будемо рухатися із крапки в напрямку вектора доти, поки функція досягне мінімуму. Це буде при


. (12)


Вектор



приймемо за нове наближення до рішення системи. Вектор не в'язань


(13)


має напрямок нормалі до поверхні в крапці . Покажемо, що він буде ортогональний до і . Справді, використовуючи (9), (11), (12), (13), маємо:


Случайные файлы

Файл
163287.rtf
4035-1.rtf
20843-1.rtf
28902.rtf
16364-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.