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

,

або

(15)

Вектор

(16)

буде мати напрямок нормалі до перетину поверхні гіперплощиною (14) у крапці . Із крапки змістимося в напрямку цього вектора так, щоб функція досягла мінімального значення. Це буде при

, (17)

(18)

приймемо за нове наближення к. Новий вектор не в'язань буде:

. (19)

Продовжуючи процес, одержимо послідовності векторів , , , обумовлені рекурентними співвідношеннями:

(20)

Для цих векторів мають місце наступні співвідношення:

(21)

(22)

Справді, у силу самої побудови при i (j

Далі, при i>j

Якщо i=j+1, то права частина дорівнює нулю, у силу визначення , якщо ж i>j+1, те , по доведеному, і

.

Продовжуючи зниження індексу у вектора , через кілька кроків прийдемо до скалярного добутку (по визначенню ). Таким чином, співвідношення (21) доведені. Для доказу (22), у силу рівноправності індексів i і j, припустимо, що i>j. Тоді

.

Тому що в n-мірному векторному простори не може бути більше n взаємно ортогональних векторів, то на деякому кроці одержимо , тобто буде рішенням системи (1).

На мал. 1 показана геометрична картина нашої побудови при n=3.

Мал. 1

2.2 Другий алгоритм методу

Приведемо інший алгоритм методу. Будемо позначати послідовні наближення до рішення через і введемо позначення:

. (23)

Перші два наближення й візьмемо так, щоб

. (24)

Припустимо, що вже відомо наближення (i1), обчислена й справедливо рівність

. (25)

Будемо шукати мінімум функціонала (2) на множині векторів

. (26)

Дорівнюючи до нуля частки похідні від по й для визначення й , одержимо систему:

(27)

або, з огляду на (25),

(28)

Позначимо через рішення цієї системи:

(29)

і за (i+1) – е наближення до рішення приймемо:

(30)

Із системи (27) треба, що

, (31)

а тому що

те з (31) треба:

(32)

Доведемо, що якщо

(33)

те при всіх i

(34)

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

Справді, при умовах (33)

т.ч. умова (24) виконано. Припустимо, що вже доведено рівності

(35)

і доведемо рівність

При припущенні (35) і, отже,

Але зі співвідношень (20) маємо:

Доведемо коллінеарність векторів

і (36)

З (20) і (29) маємо:

а це й доводить коллінеарність векторів (36).

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

Це й доводить справедливість (34) при всіх i.

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

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

Висновок

У даній роботі були розглянуті метод ортогоналізації й метод сполучених градієнтів, а також представлена програма мовою програмування С++, що реалізує метод ортогоналізації на ЕОМ, і її результати роботи.

Список літератури

1. Березин І.С. і Жидков Н.П. Методи обчислень. – К., 2003

2. Воєводін В.В. Чисельні методи алгебри (теорія й алгоритми). – К., 2004

3. Подбельський В.В. і Фомін С.С. Програмування мовою С ++. – К., 2002

4. Каліткін М.М. Чисельні методи. – К., 2003