Курсовая работа: Дослідження методу ортогоналізації й методу сполучених градієнтів
⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
"Дослідження методу ортогоналізації й методу сполучених градієнтів"
До рішення систем лінійних алгебраїчних рівнянь приводяться багато задач чисельного аналізу.
Відоме з курсу вищої алгебри правило Крамера для рішення систем лінійних алгебраїчних рівнянь практично невигідно, тому що вимагає занадто великої кількості арифметичних операцій і записів. Тому було запропоновано багато різних способів, більше придатних для практики.
Використовувані практично методи рішення систем лінійних алгебраїчних рівнянь можна розділити на дві більші групи: так звані точні методи й методи послідовних наближень. Точні методи характеризуються тим, що з їхньою допомогою принципово можливо, проробивши кінцеве число операцій, одержати точні значення невідомих. При цьому, звичайно, передбачається, що коефіцієнти й праві частини системи відомі точно, а всі обчислення виробляються без округлень. Найчастіше вони здійснюються у два етапи. На першому етапі перетворять систему до того або іншого простого виду. На другому етапі вирішують спрощену систему й одержують значення невідомих.
Методи послідовних наближень характеризуються тим, що із самого початку задаються якимись наближеними значеннями невідомих. Із цих наближених значень тим або іншому способу одержують нові «поліпшені» наближені значення. З новими наближеними значеннями надходять точно також і т.д. Розглянемо два точних методи: метод ортогоналізації й метод сполучених градієнтів.
1.1 Метод ортогоналізації у випадку симетричної матриці
порядку n. Щоб уникнути надалі плутанини, над векторами поставимо риски. Рішення системи будемо розшукувати у вигляді
де – n векторів, що задовольняють умовам
Тут розглядається звичайний скалярний добуток векторів в n-мірному векторному просторі, тобто якщо й , те . Нехай такі вектори знайдені. Як це робиться, буде показано нижче. Розглянемо скалярний добуток обох частин системи (1) з
Отже, для визначення коефіцієнтів одержали систему із трикутною матрицею. Визначник цієї системи дорівнює
Отже, якщо , те можливо знайти й перебувають вони без праці.
Особливо легко визначаться , якщо матриця А симетрична. У цьому випадку, мабуть,
Тоді система для визначення прийме вид
Метод можна узагальнити. Нехай якимсь образом удалося знайти систему 2n векторів так, що
Множачи обидві частини рівності (1) на й використовуючи подання через , як і раніше, одержимо:
Знову вийшла система лінійних алгебраїчних рівнянь із трикутною матрицею для визначення . Трохи ускладнивши обчислення можна одержати систему діагонального виду. Для цього побудуємо три системи векторів , так що мають місце рівності:
Зупинимося докладніше на першому з описаних методів. Розглянемо випадок, коли матриця А симетрична й позитивно певна. Останнє означає, що для будь-якого вектора квадратична форма його компонент більше або дорівнює нулю, причому рівність нулю можливо в тім і тільки тім випадку, якщо вектор нульової. Як ми бачили раніше, потрібно побудувати систему векторів , що задовольняють умовам
Це побудова можна здійснити в такий спосіб. Виходимо з якоїсь системи лінійно незалежних векторів , наприклад із системи одиничних векторів, спрямованих по координатних осях:
Далі проводимо «ортогоналізацію». Приймаємо й шукаємо у вигляді
Процес буде здійсненний, тому що все . Це ж забезпечить нам можливість розв'язання системи для визначення коефіцієнтів . Помітимо, що в нашім випадку це буде процес справжньої ортогоналізації, якщо в просторі векторів увести новий скалярний добуток за допомогою співвідношення
Неважко перевірити, що уведене таким способом скалярний добуток буде задовольняти всім вимогам, які до нього пред'являються.
При рішенні системи n рівнянь за справжньою схемою потрібно зробити
1.2
Метод ортогоналізації у випадку несиметричної матриці
У випадку несиметричної матриці процес ортогоналізації проводиться точно також. Нехай вектори вже побудовані. Тоді шукається у вигляді
Коефіцієнти визначаються із системи
Система у випадку несиметричної матриці буде трикутною.
Аналогічно будується система «біортогональних» векторів, тобто система 2n векторів, що задовольняють умові (12). При цьому – n довільних лінійно незалежних векторів, а вектори будуються послідовно у вигляді
Коефіцієнти перебувають із системи
Також надходимо, відшукуючи коефіцієнти й , при побудові систем векторів (14) і (15), що задовольняють умовам (16).
Зупинимося ще на одному методі ортогоналізації. Будемо розглядати рядки матриці А як вектори:
Перше рівняння системи ділимо на . При цьому одержимо
Друге рівняння системи заміниться на
Аналогічно надходимо далі. Рівняння з номером i прийме вид
Процес буде здійсненний, якщо система рівнянь лінійно незалежна. У результаті ми прийдемо до нової системи , де матриця З буде ортогональної, тобто має властивість СС¢=I.
Таким чином, рішення системи можна записати у вигляді
Практично, внаслідок помилок округлення, СС¢ буде відмінна від одиничної матриці й може виявитися доцільним зробити кілька ітерацій для системи .
Нехай потрібно вирішити систему лінійних алгебраїчних рівнянь
с позитивно певною матрицею A порядку n.
багаточлен, що представляє, другого порядку відносно x
1, x
2…, x n
,… Позначимо через рішення системи (1), тобто . У силу симетричності й позитивної визначеності матриці, маємо:
При цьому знак рівності можливий лише при . Таким чином, задача рішення рівняння (1) зводиться до задачі відшукання вектора , що обертає в мінімум функціонал (2).
Для відшукання такого вектора застосуємо наступний метод.
Нехай – довільний початковий вектор, а
– вектор не в'язань системи. Покажемо, що вектор не в'язань має напрямок нормалі до поверхні в крапці . Справді, напрямок нормалі збігається з напрямком найшвидшої зміни функції в крапці . Це напрямок ми знайдемо, якщо знайдемо серед векторів , для яких , такий вектор, що
Але серед векторів постійний довжини досягає максимального значення, якщо має напрямок вектора або йому протилежне. Твердження доведене. Будемо рухатися із крапки в напрямку вектора доти, поки функція досягає мінімального значення. Це буде при , тобто при
і приймаємо за нове наближення до рішення.
У методі сполучених градієнтів наступне наближення перебуває так. Через крапку проведемо гіперплощину (n-1) – го виміру
і через позначимо нове не в'язання системи
Вектор спрямований по нормалі до поверхні в крапці , а вектор паралельний дотичної площини в цій крапці. Тому
Гіперплощина (7) проходить через крапку , тому що
При кожному вектор паралельний деякої нормальної площини до поверхні в крапці . Знайдемо серед них той, котрий лежить у гіперплощині (7), тобто ортогональний к. З умови ортогональності маємо:
має напрямок нормалі до перетину поверхні гіперплощини (7) у крапці . Будемо рухатися із крапки в напрямку вектора доти, поки функція досягне мінімуму. Це буде при
приймемо за нове наближення до рішення системи. Вектор не в'язань
має напрямок нормалі до поверхні в крапці . Покажемо, що він буде ортогональний до і . Справді, використовуючи (9), (11), (12), (13), маємо:
Розглянемо гіперплощину (n-2) – х вимірів
минаючу через крапку . Ця гіперплощина містить і , тому що ми раніше бачили, що , а
Вектор при кожному паралельний гіперплощини (7), тому що
Підберемо так, щоб він був паралельний і гіперплощини (14), тобто зажадаємо ортогональності до вектора . Будемо мати:
буде мати напрямок нормалі до перетину поверхні гіперплощиною (14) у крапці . Із крапки змістимося в напрямку цього вектора так, щоб функція досягла мінімального значення. Це буде при
приймемо за нове наближення к. Новий вектор не в'язань буде:
Продовжуючи процес, одержимо послідовності векторів , , , обумовлені рекурентними співвідношеннями:
Для цих векторів мають місце наступні співвідношення:
Справді, у силу самої побудови при i (j
Якщо i=j+1, то права частина дорівнює нулю, у силу визначення , якщо ж i>j+1, те , по доведеному, і
Продовжуючи зниження індексу у вектора , через кілька кроків прийдемо до скалярного добутку (по визначенню ). Таким чином, співвідношення (21) доведені. Для доказу (22), у силу рівноправності індексів i і j, припустимо, що i>j. Тоді
Тому що в n-мірному векторному простори не може бути більше n взаємно ортогональних векторів, то на деякому кроці одержимо , тобто буде рішенням системи (1).
На мал. 1 показана геометрична картина нашої побудови при n=3.
Приведемо інший алгоритм методу. Будемо позначати послідовні наближення до рішення через і введемо позначення:
Перші два наближення й візьмемо так, щоб
Припустимо, що вже відомо наближення (i³1), обчислена й справедливо рівність
Будемо шукати мінімум функціонала (2) на множині векторів
Дорівнюючи до нуля частки похідні від по й для визначення й , одержимо систему:
Позначимо через рішення цієї системи:
і за (i+1) – е наближення до рішення приймемо:
що буде доводити й збіжність, і кінцівка другого алгоритму.
т.ч. умова (24) виконано. Припустимо, що вже доведено рівності
а це й доводить коллінеарність векторів (36).
Вектор дає мінімум функціонала в площині, що проходить через і на вектори й , а ми показали, що цей мінімум лежить на прямій, що проходить через у напрямку вектора . Але на цієї прямий мінімум функціонала досягається на векторі . Це й означає, що
Це й доводить справедливість (34) при всіх i.
На перший погляд здається, що перший алгоритм краще, тому що на кожному кроці він вимагає лише одного множення матриці А на вектор , а в другому алгоритмі потрібно два множення матриці А на вектор і , але досвід показав, що застосування першого алгоритму приводить до швидкого нагромадження помилок округлення, так що для матриць великого порядку можливо істотне відхилення від точного рішення. Другий алгоритм менш чутливий до помилок округлення й тому вимагає меншого кількість кроків для одержання гарного наближеного рішення.
Метод сполучених градієнтів доцільно використовувати для рішення систем рівнянь, у яких матриця А має багато нульових елементів. При рішенні системи по цьому методі елементи матриці беруть участь в арифметичних операціях лише при множенні матриці на вектор, а множення матриці на вектор можна організувати так, щоб в арифметичних операціях брали участь тільки ненульові елементи.
У даній роботі були розглянуті метод ортогоналізації й метод сполучених градієнтів, а також представлена програма мовою програмування С++, що реалізує метод ортогоналізації на ЕОМ, і її результати роботи.
1. Березин І.С. і Жидков Н.П. Методи обчислень. – К., 2003
2. Воєводін В.В. Чисельні методи алгебри (теорія й алгоритми). – К., 2004
3. Подбельський В.В. і Фомін С.С. Програмування мовою С ++. – К., 2002
4. Каліткін М.М. Чисельні методи. – К., 2003
Название: Дослідження методу ортогоналізації й методу сполучених градієнтів
Раздел: Рефераты по математике
Тип: курсовая работа
Добавлен 09:35:31 24 декабря 2010 Похожие работы
Просмотров: 7
Комментариев: 12
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Ребятки, кто на FAST-REFERAT.RU будет заказывать работу до 26го мая - вводите промокод iphone, и тогда будете учавствовать в розыгрыше iphone xs)) сам только что узнал, что у них такие акции бывают (п.с. кстати не удивляйтесь что вас перекидывает на сайт с другим названием, так и должно быть)
Мне с моими работами постоянно помогают на FAST-REFERAT.RU - можете просто зайти узнать стоимость, никто вас ни к чему не обязывает, там впринципе всё могут сделать, вне зависимости от уровня сложности) у меня просто парень электронщик там какой то, тоже там бывает заказывает))
Спасибо, Оксаночка, за совет))) Заказал курсач, отчет по практике, 2 реферата и дипломную на REFERAT.GQ , все сдал на отлично, и нервы не пришлось тратить)
Я обычно любые готовые работы покупаю на сайте shop-referat.tk , и свои все там же на продажу выставляю, неплохой доп.заработок. А если там не нахожу то уже на referat.gq заказываю и мне быстро делают.
Да, но только в случае крайней необходимости.
Курсовая работа: Дослідження методу ортогоналізації й методу сполучених градієнтів
Реферат по теме Моделирование информационной системы бармена
Курсовая работа по теме Геоэкологическая характеристика Лысьвенского муниципального района Пермского края
Реферат: Жизнь и необычайные приключения солдата Ивана Чонкина
Реферат по теме Применение информационных технологий при моделировании процессов в чрезвычайных ситуациях
Страхование предпринимательской деятельности
Дипломная работа по теме Молодёжный экстремизм
Сочинение На Тему Мой Класс Кабинет
Доклад по теме Царь Иоанн Васильевич Грозный: за и против
Реферат Про Чувашский Драматический Театр
Доклад по теме Причины II мировой войны. Фашизм
Курсовая работа по теме Организация, планирование и управление железнодорожным строительством
Домашняя Контрольная Работа По Алгебре 9 Класс
Реферат по теме Вопросы экологии на уроках физики
Гроза И Бесприданница Сравнение Сочинение С Текстом
Практические Работы Социального Работника
Профессиональные Риски В Деятельности Социального Работника Реферат
Курсовая работа по теме Современная студенческая семья: проблемы, тенденции, перспективы (материал ТУСУР)
Пособие по теме Адольф Гитлер. Политическая биография (Adolf Hitler)
Учебное пособие: Методические указания по организации производственной практики и выполнению дипломного проектирования для студентов кафедры "Компьютерные системы и технологии"
Реферат: Подготовка менеджеров в США, в странах Западной Европы, в России
Реферат: Философия религии Канта.
Курсовая работа: Горнолыжные курорты
Реферат: Общая характеристика антропогенных источников токсикантов