Xreferat.com » Рефераты по математике » Дослідження методу ортогоналізації й методу сполучених градієнтів

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

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


На тему:


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


Введення


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

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

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

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


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


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)


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


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


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


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


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

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


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

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


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


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


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


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

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


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


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

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

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


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


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


де


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


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


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


де

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


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


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


де

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


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


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

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


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


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


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


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


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


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


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

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


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


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


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


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

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

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


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

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


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


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


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


Але серед векторів Дослідження методу ортогоналізації й методу сполучених градієнтів постійний довжини Дослідження методу ортогоналізації й методу сполучених градієнтів досягає максимального значення, якщо Дослідження методу ортогоналізації й методу сполучених градієнтів має напрямок вектора Дослідження методу ортогоналізації
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: