Курсова робота
На тему:
«Дослідженняметоду ортогоналізації й методу сполучених градієнтів»
Введення
До рішення систем лінійних алгебраїчних рівняньприводяться багато задач чисельного аналізу.
Відомез курсу вищої алгебри правило Крамера для рішення систем лінійних алгебраїчнихрівнянь практично невигідно, тому що вимагає занадто великої кількостіарифметичних операцій і записів. Тому було запропоновано багато різнихспособів, більше придатних для практики.
Використовувані практично методи рішення системлінійних алгебраїчних рівнянь можна розділити на дві більші групи: так званіточні методи й методи послідовних наближень. Точні методи характеризуються тим,що з їхньою допомогою принципово можливо, проробивши кінцеве число операцій,одержати точні значення невідомих. При цьому, звичайно, передбачається, щокоефіцієнти й праві частини системи відомі точно, а всі обчислення виробляютьсябез округлень. Найчастіше вони здійснюються у два етапи. На першому етапіперетворять систему до того або іншого простого виду. На другому етапі вирішуютьспрощену систему й одержують значення невідомих.
Методипослідовних наближень характеризуються тим, що із самого початку задаютьсяякимись наближеними значеннями невідомих. Із цих наближених значень тим абоіншому способу одержують нові «поліпшені» наближені значення. З новиминаближеними значеннями надходять точно також і т.д. Розглянемо два точнихметоди: метод ортогоналізації й метод сполучених градієнтів.
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.2 Метод ортогоналізації у випадку несиметричної матриці
У випадку несиметричної матриці процесортогоналізації проводиться точно також. Нехай вектори /> вже побудовані. Тоді /> шукається у вигляді
/> (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) у крапці />. Будемо рухатися із крапки/> в напрямку вектора /> доти, поки функція /> досягне мінімуму. Це будепри
/>. (12)
Вектор
/>
приймемо за нове наближення до рішення /> системи. Вектор не в'язань
/> (13)
має напрямок нормалі до поверхні /> в крапці />. Покажемо, що він будеортогональний до /> і />. Справді, використовуючи(9), (11), (12), (13), маємо:
/>
Розглянемо гіперплощину (n-2) – хвимірів
/>, (14)
минаючу через крапку />. Ця гіперплощина містить і/>, тому що ми раніше бачили,що />, а
/>.
Вектор /> прикожному /> паралельний гіперплощини(7), тому що
/>.
Підберемо /> так,щоб він був паралельний і гіперплощини (14), тобто зажадаємо ортогональності довектора />. Будемо мати:
/>,
або
/> (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)
Припустимо, що вже відомо наближення /> (i³1), обчислена /> йсправедливо рівність
/>. (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