Алгоритм методу Бройдена

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Черкаський національний університет імені Богдана Хмельницького

Математичний факультет

Кафедра прикладної математики

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

Виконала студентка спец.

8.080202-«Прикладна математика»:

Гальцевої Альони Юріївни

Науковий керівник

стар.викл. Сердюк Олександр Анатолійович

Завідувач кафедри

прикладної математики

д.техн.н., доцент Головня Б.П.

Черкаси, 2010

Зміст

Вступ

Розділ 1

1.1 Зв'язані списки

1.2 Огляд чисельних методів розв'язування

1.3 Заміна нелінійного рівняння лінійною моделлю

1.4 Узагальнення методу січних в n-вимірному просторі. Метод Бройдена

Розділ 2. Алгоритм методу Бройдена

2.1 Вхідні дані для алгоритму методу січних

2.2 Зміст алгоритму

Розділ 3. Обчислювальні експерименти

3.1 Збіжність методу та його модифікація

3.2 Проведення обчислювальних експериментів

Висновки

Література

Вступ

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

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

В курсовій роботі розглядатимуться списки, двохзв'язні списки і стеки.

Розділ 1

1.1 Зв'язані списки

лінійний алгоритм бройден

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

Зв'язані списки, подібні масивам, використовуються для маніпуляцій зі списками елементів. Елементи зберігаються в вигляді вузлів зв'язаних списків.

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

1.2 Огляд чисельних методів розв'язування

Достатньо велика кількість інженерних задач на проміжному етапі вирішення зводиться до вирішення системи нелінійних рівнянь. Це одна з найважчих задач з точки зору реалізації її на ЕОМ. Одним із найбільш простих алгоритмів її рішення є метод Ньютона. Це найбільш розповсюджений метод розв'язання систем нелінійних рівнянь. Його популярність обумовлена тим, що в порівнянні з методом простої ітерації він забезпечує найбільш швидку збіжність. В основі методу Ньютона лежить представлення всіх n рівнянь у вигляді рядів Тейлора.

Розглянемо алгоритм методу Ньютона.

Нехай дана система нелінійних рівнянь виду

(1.2.1)

де - неперервно-диференційні функції.

Алгоритм методу базується на розкладі кожної функції системи в околі точки з координатами в ряд Тейлора.

члени рядів вищих порядків ( тощо).

Початкова система буде мати вигляд:

(1.2.2)

де - матриця Якобі.

Дану задачу можна розв'язати з будь-якої точки, вибравши вектор початкових наближень.

Процес розв'язання системи нелінійних рівнянь (1.2.1) з використанням системи лінійних алгебраїчних рівнянь (1.2.2) відносно - ітераційний, та буде продовжуватись до тих пір, поки всі координати вектору приростів не стануть менше за абсолютною величиною заданої похибки , тобто (див. Додаток А).

1.3 Заміна нелінійного рівняння лінійною моделлю

В процесі побудови методів Ньютона і січних вирішення нелінійного скалярного рівняння функція f(x) в околі поточної точки заміняється лінійною функцією (аффінною моделлю) .

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

Якщо замінюючи функцію f(x) поблизу точки афінної моделі мала в цій точці однакову з нею похідну, то, диференціюючи, набуваємо значення коефіцієнта , підстановка якого в приводить до відомого методу Ньютона. Якщо ж виходити з того, що поряд з рівністю повинно мати місце збіг функцій f(x) і в попередній точці тобто з рівності , отримуємо коефіцієнт, що перетворює на відому формулу січних

Рівність, переписану у вигляді

(1.3.1)

називають співвідношенням січних. Воно легко узагальнюється на n - мірний випадок і лежить в основі виведення методу Бройдена.

1.4 Узагальнення методу січних в n-вимірному просторі.Метод Бройдена

У n-мірному векторному просторі співвідношення січних для рівняння (1.4.1) представляється рівністю

, (1.4.2)

де - відомі n-мірні вектори, - дане нелінійне відображення, а - деяка матриця лінійного перетворення в .

Введемо позначення:

, (1.4.3)

Тоді співвідношення січних в набуде такого вигляду:

. (1.4.4)

Аналогічно одновимірному випадку, а саме, по аналогії з формулою, шукатимемо наближення до знаходження векторного рівняння (1.4.5) за формулою

. (1.4.5)

У формулі (1.4.5) матрицю в ній потрібно підібрати так, щоб вона задовольняла співвідношенню січних (1.4.3). Але це співвідношення не визначає однозначно матрицю : дивлячись на рівність, легко зрозуміти, що при n>1 існує безліч матриць, що перетворюють заданий n-мірній вектор в інший заданий вектор (звідси - ясність в розумінні того, що можуть бути різні узагальнення одновимірного методу січних).

Для знаходження матриці міркуватимемо таким чином. Перейдемо від лінійної моделі функції F(x) в точці

(1.4.6)

до такої ж моделі в точці

(1.4.7)

Для матриці лінійного перетворення маємо лише співвідношення січних (1.4.3). Тому виходимо з того, що при переході від (1.4.6) до (1.4.7) зміни в моделі мають бути мінімальними. Ці зміни характеризує різниця . Віднімемо (1.4.7) від (1.4.6) і використаємо співвідношення січних . Маємо:

Представимо вектор у вигляді лінійної комбінації фіксованого вектора визначеного в , і деякого вектора t, йому ортогонального: ,

У цьому виразі перший доданок не може бути змінений, оскільки - фіксований вектор при фіксованому k. Тому мінімальній зміні афінної моделі відповідатиме випадок, коли другий доданок в буде нуль-вектором при всяких векторах t, ортогональних векторам , тобто слід знаходити з умови

(1.4.8)

Якщо матричну поправку взяти у вигляді однорангової nхn-матриці, то умова (1.4.7) буде виконуватись. Таким чином, прийдемо до так званої формули перерахунку С. Бройдена

. (1.4.9)

Формула (1.4.9) дозволяє простими обрахунками перейти від старої матриці до нової такої, щоб виконувалось співвідношення січних (1.4.3) в новій точці і при цьому зміни в лінійній моделі (1.4.6) були мінімальними.

Сукупність формул: (1.4.3),(1.4.6), (1.4.9) називають методом січних Бройдена або просто методом Бройдена розв'язування систем нелінійних рівнянь.

Розділ 2. Алгоритм методу Бройдена

2.1 Вхідні дані для алгоритму методу січних

Хоча в методах січних звичайним є завдання двох початкових векторів (,), для методу Бройдена властивий інший початок ітераційного процесу. Потрібно задати один початковий вектор (наближений розв'язок), початкову матрицю і далі в циклі послідовно виконують наступний алгоритм.

2.2 Зміст алгоритму

1) Розв'язати лінійну систему (2.1)відносно вектора

2) Знайти ветори та

, (2.2)

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

4) В якості матриці для запуску ітераційного процесу Бройдена беруть матрицю Якобі .

Реалізація даного методу в середовищі Matlab подано в ДодаткуБ.

Розділ 3. Обчислювальні експерименти

3.1 Збіжність методу та його модифікація

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

Модифікація методу Бройдена.

Формулі перерахунку (2.3) в ітераційному процесі Бройдена можна надати інший більш простий вигляд. Так як та , , то , а , то, підставивши ці значення у формулу (2.3) отримаємо модифіковану формулу перерахунку

(3.1)

яку можна використати замість (2.3) без обрахунку вектора . Таке перетворення ітераційного процесу дещо скорочує об'єм обрахунків (на одне матрично-векторне множення на кожній ітерації). Але не потрібно забувати, що при заміні формули (2.3) аналогічною (3.1) може змінитися ситуація з обчислювальною стійкістю методу.

3.2 Проведення обчислювальних експериментів

Приклад 1 Розв`язати систему рівнянь:

function Z=F(X)

x=X(1);

y=X(2);

Z=zeros(1,2);

Z(1)=x^2-2*x-y+0.5;

Z(2)=x^2+4*y^2-4;

Задаємо матрицю Якобі для цієї системи:

function W=JF(X)

x=X(1);

y=X(2);

W=[2*x-2 -1; 2*x 8*y];

Будуємо графік функції.

clear all;

x=[-2:0.01:2];

y1=x.^2-2*x+0.5;

y2=sqrt(1-(x.^2)/4);

y3=-sqrt(1-(x.^2)/4);

plot(x,y1,'b', x,y2, 'r', x,y3, 'r')

grid on



З графіка видно,що корені лежать в околах точок (-0.5;1) та(2; 0,5).

Беремо ці точки як початкове наближення.

Нехай допустиме відхилення дорівнює1е-6

Таблиця 1

Метод	P1	iter	err	P2	iter	err	Р
Ньютона	[-0.5 1]	3	3.5889e-004	[2 0.5]	3	4.8398e-004	[-0.2222 0.9938], [1.9007 0.3112]
Бройдена		5	1.5368e-008		9	1.7264e-006
Модифікований Бройдена		5	1.5368e-008		6	2.6389e-007

Отже, розв'язком системи рівнянь є точки (-0.2222; 0.9938) та

(1.9007; 0.3112). За методом Ньютона ми знайшли корені за 3 кроки,а за методом Бройдена за 5, проте з більшою точністю.

Приклад 2

Розв`язати систему рівнянь:



Задаємо матрицю Якобі для цієї сисеми: W=[-8*x-3 6; 6*x-8 1].

Будуємо графік функції.

З графіка видно,що корені лежать в околотах точок (0.5;1) та(1.5;2). Беремо ці точки як початкове наближення. Нехай допустиме відхилення дорівнює1е-6

Таблиця 2

Метод	P1	iter	err	P2	iter	err	Р
Ньютона	[0.5 1]	3	3.5889e-004	[1.5;2]	3	4.8398e-004	[ 0.5455 0.4711], [ 1.5000 2.2500]
Бройдена		4	7.8154e-007		2	0
Модифікований Бройдена		4	6.7466e-007		2	0

Отже, розв'язком системи рівнянь є точки (0.5455 0.4711) та

(1.5000 2.2500).За методом Ньютона ми знайшли корені за 3 кроки,а за методом Бройдена перший корінь за 4 і другий за 2 з більшою точністю.

Приклад 3

Розв`язати систему рівнянь:

Задаємо матрицю Якобі для цієї сисеми: W=[4*cos(x) 2*y; 2*x-1 3].

Будуємо графік функції.

З графіка видно,що корені лежать в околотах точок (-2.5;2) та(0.2;1). Беремо ці точки як початкове наближення.

Нехай допустиме відхилення дорівнює1е-6

Таблиця 3

Метод	P1	iter	err	P2	iter	err	Р
Ньютона	[-2.5 -2]	3	3.5889e-004	[0.2 1]	3	1.2182e-004	[-2.3514 -1.9601], [ 0.1266 0.7035]
Бройдена		4	2.2049e-007		6	2.9563e-009
Модифікований Бройдена		4	2.2049e-007		6	2.9563e-009

Отже, розв'язком системи рівнянь є точки (2.3514 -1.9601) та

(0.1266 0.7035). За методом Ньютона ми знайшли корені за 3 кроки з точністю 1е-4,а за методом Бройдена одну точку за 4 кроки з точністю1е-7,а іншу за 6 з точністю 1е-9.

Приклад 4

Розв`язати систему рівнянь:

Задаємо матрицю Якобі для цієї сисеми: W=[-4*x+4 3; 2*x-8 6].

Будуємо графік функції.

З графіка видно,що корені лежать в околотах точок (0.5;0) та(2.7;2). Беремо ці точки як початкове наближення.

Нехай допустиме відхилення дорівнює1е-6

Таблиця 4

Метод	P1	iter	err	P2	iter	err	Р
Ньютона	[0.5 0]	3	5.1787e-005	[2.7 2]	3	5.1787e-005	[0.3510 -0.0525], [ 2.8490 1.9459]
Бройдена		5	5.9605e-010		5	1.4989e-009
Модифікований Бройдена		5	5.9605e-010		5	1.4989e-009

Отже, розв'язком системи рівнянь є точки (0.3510 -0.0525) та

(2.8490 1.9459). За методом Ньютона ми знайшли корені за 3 кроки з похибкою 1е-5,а за методом Бройдена за 5,проте з меншою похибкою err=1e-2.

Приклад 5

Розв`язати систему рівнянь:

Задаємо матрицю Якобі для цієї сисеми: W=[-4*x+4 3; 2*x-8 6].

Будуємо графік функції.



З графіка видно,що корені лежать в околотах точок (-1;-2) та(0.5;2). Беремо ці точки як початкове наближення.

Нехай допустиме відхилення дорівнює1е-6

Таблиця 4

Метод	P1	iter	err	P2	iter	err	Р
Ньютона	[0.5 0]	3	5.1787e-005	[2.7 2]	3	5.1787e-005	[-1.1248 -2.0652], [ 0.4316 1.7850]
Бройдена		6	3.7513e-007		8	3.2960e-008
Модифікований Бройдена		6	3.7513e-007		8	3.2960e-008

Отже, розв'язком системи рівнянь є точки (0.3510 -0.0525) та

(2.8490 1.9459). За методом Ньютона ми знайшли корені за 3 кроки з похибкою 1е-5,а за методом Бройдена за 5,проте з меншою похибкою err=1e-2.

Висновки

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

Метод Ньютона має хорошу збіжність, але при цьому необхідний розрахунок зворотної матриці Якобі на кожній ітерації, що приводить до великих витрат машинного часу. Метод Бройдена, будучи розвитком методу Ньютона, позбавлений цього недоліку.

Якщо початкове наближення вибране досить близько до рішення і якщо початкова апроксимація матриці Якобі досить точна, то метод Бройдена володіє надлінійною збіжністю, але не квадратичною, як метод Ньютона.

Список використаних джерел

1. Майка Ласло Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. - М.: Издательство «Бином», 1997.- 304с.: ил.

2. Бьерн Страустроп Язык програмирования на С++, специальное издание: Пер. с англ. - М.: Издательство «Бином», 2004.- 1104с.: ил.

3. Дейтел Х.М., Дейтел П. Дж. Как программировать на С++ (4-е изд.): Пер. с англ. - М.: Издательство «Бином-Пресс», 2005.- 1191с.: ил.

4. Вит Н. Алгоритмы + структуры данных = программы: Пер. с англ. - М.: Издательство «Мир», 1985.- 406с., ил.

5. http://valera.asf.ru/cpp/book

6. http://ru.wikipedia.org/wiki/C%2B%2B

Размещено на Allbest.ru