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

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

На тему:

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

Введення

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

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

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

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

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<r

(18)

і при i>r

(19)

Таким чином,

(20)

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

=0 . (21)

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

(22)

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

. (23)

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

(24)

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

. (25)

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

(26)

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

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

. (26)

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

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

(28)

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

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

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

(29)

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

(30)

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

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

(31)

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

(32)

Також надходимо, відшукуючи коеф

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать