Дослідження методу ортогоналізації й методу сполучених градієнтів (стр. 2 из 4)
(29)Коефіцієнти
визначаються із системи
(30)Система у випадку несиметричної матриці буде трикутною.
Аналогічно будується система «біортогональних» векторів, тобто система 2n векторів, що задовольняють умові (12). При цьому
– n довільних лінійно незалежних векторів, а вектори 
будуються послідовно у вигляді 
(31)Коефіцієнти
перебувають із системи 
(32)Також надходимо, відшукуючи коефіцієнти
й 
, при побудові систем векторів (14) і (15), що задовольняють умовам (16).При цьому одержимо дві системи:
(33)з яких і визначаємо
й .Зупинимося ще на одному методі ортогоналізації. Будемо розглядати рядки матриці А як вектори:
(34)Перше рівняння системи
ділимо на 
. При цьому одержимо 
(35)де
(36)Друге рівняння системи заміниться на
(37)де
(38)Аналогічно надходимо далі. Рівняння з номером i прийме вид
(39)де
(40)Процес буде здійсненний, якщо система рівнянь лінійно незалежна. У результаті ми прийдемо до нової системи
, де матриця З буде ортогональної, тобто має властивість СС¢=I.Таким чином, рішення системи можна записати у вигляді
. (41)Практично, внаслідок помилок округлення, СС¢ буде відмінна від одиничної матриці й може виявитися доцільним зробити кілька ітерацій для системи
.2. Метод сполучених градієнтів
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) у крапці . Будемо рухатися із крапки в напрямку вектора 
доти, поки функція 
досягне мінімуму. Це буде при