ОБЛАСНИЙ КОМУНАЛЬНИЙВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД “ІНСТИТУТ ПІДПРИЄМНИЦТВА «СТРАТЕГІЯ»
КАФЕДРА ЕКОНОМІЧНОЇКІБЕРНЕТИКИ
Курсова робота
З дисципліни: «Обчислювальніметоди»
На тему: «Рішеннясистем нелінійних рівнянь. Метод ітерацій. Метод Ньютона — Канторовича.»
Студента Іощенка І.Г.
группа С-05-51
Керівник Андрейшина Н.Б.
Філімоненко М.І.
м. Жовті Води 2007
/>Зміст
Вступ
1. Рішення системнелінійних рівнянь
1.1 Метод ітерацій
1.1.1 Приклад рішеннясистеми нелінійних рівнянь методом ітерацій
1.2 Метод найшвидшогоспуску
1.2.1 Приклад рішеннясистеми нелінійних рівнянь методом спуска
1.3 МетодНьютона-Канторовича
/>Вступ
При рішенні систем нелінійних і трансцендентних рівнянь дуже складнознайти точне рішення, тому точним рішення рівняння не є. Задача пошуку коренясистеми рівняння може вважатися практично вирішеною, якщо ми зуміємо визначитикорінь з потрібним ступенем точності і вказати межі можливої погрішності. Умовизбіжності метода Ньютона для системи досліджувалися Виллерсом, Стениним,Канторовичем.
У наш час рішення систем нелінійних рівнянь досить актуальна тема, аджеїї можна застосовувати на практиці для рішення кола задач. Прикладом цього єзадачі, які виникають у геодезії.
Цілю моєї курсової роботи є опис методів рішення систем нелінійнихрівнянь, а також продемонструвати на практиці рішення системи рівнянь методомНьютона — Канторовича та написання програми до цього методу.
/>1. Рішеннясистем нелінійних рівнянь
Задачі, які виникають при математичній обробці результатів вимірювання,як правило, зводяться до рішення нелінійних систем алгебраїчних аботрансцендентних рівнянь:
/>
або у векторній формі
F (X) = 0.
Як і у випадку одного рівняння, рішення нелінійних систем рівняньподіляється на два етапи:
знаходження приблизного рішення системи;
уточнення приблизного рішення.
Для знаходження приблизного значення коренів системи рівнянь не існуєзагальних методів. Завжди кожна нелінійна система повинна розглядатися як спеціальназадача.
Для уточнення коренів розробленні загальні методи. Найбільшрозповсюдженні в нинішній час є метод ітерацій, метод спуска, метод Ньютона тадеякі їх модифікації./>1.1 Методітерацій
Нехай дана система нелінійних рівнянь спеціального виду
/> (1)
де функції />, />,… ., /> дійсно визначенні та непереривніна деякій області/> ізольованогорішення /> цієї системи.
Розглядаючи вектори /> і /> (x) = (/>1 (x), />2 (x), …. .,/>n (x)), систему(1) можна записати у виді:
x = /> (x) (2)
Наприклад, для рішення системи двох нелінійних рівнянь з двоманевідомими
/>
потрібно перейти до рівностей:
/>
Нехай вибрано початкове приближення (/>,/>), тоді
/>
і k+1 приближення буде розраховуватися за формулами
/>
Відомо, що процес ітерації зводиться до рішення системи, якщо усі числаматриці
/>
по модулю менше одиниці. Більш простою вимогою, використовуваною напрактиці, є наступне: сума модулів частних похідних по кожному стовбці матриціповинна бути менша одиниці
/>
У випадку використання методу ітерацій до системи n рівнянь, k+1ітерація буде будуватися по формулам
/>
Тоді вимога сходження матиме вигляд:
/>
/>
Слід відмітити, що ця вимога виповняється для дуже малого числафункцій, і тому метод ітерації дуже рідко використовується на практиці, недивлячись на його простоту./>1.1.1 Прикладрішення системи нелінійних рівнянь методом ітерацій
Рішить систему рівнянь
/>
Ця система еквівалентна системі рівнянь:
/>
Виберемо початкові приближення /> тапровіримо умови
сходження процесу. Часні похідні мають вигляд
/>
Маємо
/>
Звідси слідує, що процес сходиться. Розрахунки на правому приближеннідають:
x(1) =1+0.85=1.85
y(1) =0.842-1.32=-0.478
x(2) =0.888+0.85=1.738
y(2) =0.961-1.32=0.359
x(3) =0.936+0.85=1.786
y(3) =0.986-1.32=0.334
x(4) =0.945+0.85=1.795
y(4) =0.977-1.32=0.343
x(5) =0.9408+0.85=1.7908
y(5) =0.9750-1.32=- 0.3450
x(6) =0.9411+0.85=1.7911
y(6) =0.9759-1.32=0.3441
x(7) =0.9414+0.85=1.7914
y(7) =0.9758-1.32=-0.3442./>1.2 Методнайшвидшого спуску
Нехай маємо систему рівнянь:
/>
або в матричному вигляді:
/>
де
/>
Допустимо, що функція /> дійсно непереривната непреривно диференційована в загальній області визначення. Розглянемофункцію
/>
Тоді рішення даної системи зводиться до мінімізації цієї функції.
Для мінімізації по методу спуску вибирається початковий вектор Х0,а потім шукається напрямлення спуска до рішення />,таке щоб
/>
для векторів Х(1) виду />.Тут /> – скалярна величина, постійнадля даної ітерації і знаходить величину шагу за напрямом />.
Методи спуску розрізняються в залежності від вибору напрямлення спуска.Одним із найкращих направлень є напрямлення градієнта
/>
Функція Ф (Х(і)) задається в n-мірному просторі сімействагіперповерхонь і градієнт вирішує напрям найшвидшого спуска. Тому саме воновикористовується у методі найшвидшого спуска для мінімізації функції.
Другою проблемою в методах найшвидшого спуску є вибір величини шагу />, на який потрібно продвинутися вздовж напряму зменшення функції.
Спробуємо вибрати оптимальний шаг /> для/> – ітерації методунайшвидшого спуска і побудувати вектор
/>
для якого функція /> приймаєменше значення, чим />. Розкладемофункцію
/>
в ряд Тейлора та обмежившись членами другого порядку меншості получимо
/>/> (3)
/>Тоді значення/>, для якого функція /> прийме мінімальне значення,визначається із умови /> Продиференціювавши рівняння (3) по />івраховуючи, що /> получимо
/> (4)
Оскільки в методі найшвидшого спуску компоненти градієнта мають вигляд
/>
/>
то формула (4) після підстановки цих рівнянь перейде до вигляду
/> (5)
Формула (5) дуже складна оскільки потребує рахування других часних похідних.
На практиці завжди використовується наступний варіант знаходження />.
Нехай значення Ф (Х) змінюється вздовж напрямку градієнта />. Розглянемо точкупересікання кривої /> та касатільної вточці /> з осю />.
Вона буде розраховуватися наступним чином:
/>. (6)
Як бачимо, в цьому випадку /> рахуєтьсяпросто, але сходження метода може бути дуже повільно. Тому інколи на практицівикористовують наступну модифікацію.
Для кожної ітерації метода рахують значення функціонала при />, а потім при /> і будують квадратичненаближення функціонала, який проходить через три точки />. Продиференціювавши отриманерівняння по />та прирівнявши похідну,получимо наступне рівняння для />
/> (7)
Практика показує, що хоча цей варіант більш громіздкий, так як упорівнянні з формулою (5) доводиться додатково рахувати два значення функції />, але метод сходитьсянабагато швидше.
Інколи характер Ф (Х) такий, що аналітичне рівняння для частних похіднихмає надто складний вигляд і рахувати їх надто складно.
Також слід відмітити, що якщо в області шуканого рішення є локальнімінімуми, то метод спуска може не привести до шукаємого рішення, а можутьзійтися до одного з цих мінімумів. Практично часто спуск буває дуже повільнимнавіть при відсутності локальних мінімумів.
Порядок рахування в методі найшвидшого спуска наступний:
знаходиться аналітичне рівняння для градієнта />;
вибирають початкове приближення вектора невідомих />;
вираховують координати градієнта />вточці />;
вираховують шаг по градієнту />поформулам (6) або (7);
вираховують уточнений вектор невідомих />.
Далі процес повторюється з пункту 3 до сходження./>1.2.1 Прикладрішення системи нелінійних рівнянь методом спуска
Методом найшвидшого спуска приблизно розрахувати корені системи
/>
розміщенні в області початку координат.
Маємо:
/> Тут /> та
/>
Підставляємо нульове приближення, будемо мати:
/>та />
по формулам получимо перше приближення
/>
Аналогічно находимо друге приближення />.Маємо:
/>
/>
/>/>
/>
/>
/>.
1.3 Метод Ньютона-Канторовича
Метод Ньютона-Канторовича, придатний для проведення розрахунків в Excel.Як і в методі Ньтона для нелінійних рівнянь для знаходження кореня системи нелінійнихрівнянь необхідно спочатку якимсь чином знайти початкове наближення до цього кореня(тобто вектор
/>),
а потім вже використовуються ітераційні формули методу проводиться йогоуточнення до досягнення заданої точності. Виклад методу (і його використання) зручнішепроводити в матричній формі запису. При цьому, окрім векторів, />, /> и /> (. (i — номер ітерації,,i ³ 0)) використовується також матриця A (розмірності n ´ n), що складається з приватнихпохідних по всіх компонентах вектора />:
/>:
Розглянемо ці методи для випадку n=2, тобто коли рівнянь в системі два іневідомих теж дві. В цьому випадку
/>,та />.
Ідея методу полягає в розкладанні вектор-функції в ряд Тейлора в околиціпочаткового наближення із збереженням тільки доданків першого ступеня. Позначимонайдене (якимсь чином) початкове приближення до шуканого кореня через />. Тоді можна приблизно записати
/>,(8)
На основі формула (8) будується ітараційна формула. А саме, /> вибирається так, щоб />.
Тоді (у загальному вигляді) ітераційна формула матиме вигляд
/> (9)
В методі Ньютона цю ітераційну формулу перетворять до вигляду
/> (10)
У координатному вигляді формула (10) представляє систему з двох рівняньщодо двох невідомих xi+1 и yi+1.
У матричному вигляді рішення її матиме вигляд
/>
допоміжний вектор-стовпець z, що містить n елементів.
/> (11)
Ітераційна формула методу в матричному записі має наступний вигляд
zj= — A-1 (xj)×F(xj)
xj +1 = xj + zj, (12)
тут j — номер ітерації, /> – початковенаближення шуканого кореня. Процес ітерацій завершується, якщо всі елементи останньоговектора z по абсолютній величині стануть менше заданої точності (кажучи точніше,коли норма вектора z стане менше заданої точності).
Обчислення даним методом зручно проводити в Excel з використанням функційматричної алгебри. Результати розрахунків представляються у вигляді таблиці.
Для випадку n=2 система рівнянь найчастіше має такий вигляд:
/>
Як змінна х1 тут виступає змінна х,а як змінна х2 — змінна y. Матриця А, вектори F і z вцьому випадку приймуть вигляд:
А = />, F = />, z = />,
Порядок рішення системи нелінійних рівнянь методом Ньютона-Канторовича полягаєв послідовному виконанні наступних дій:
Знайти початкове (нульове) наближення х0 шуканогокореня заданої системи рівнянь. Для випадку n=2 це можна зробити графічним методом,побудувавши графіки кожної з функцій і приблизно визначивши координати точок перетинівграфіків. В цьому випадку вектор початкового наближення може мати вигляд />;
Привести задану систему до вигляду (1), перенести все з правої частини рівнянняв ліву;
Записати в аналітичному вигляді матрицю А, використовуючи формулу (8);
Приймемо j=0;
Підставимо значення хjв аналітичні вирази дляматриці А і вектора F;
Знайдемо зворотну матрицю А-1;
По формулах (12) знайдемо вектор zj і вектор хj+1;;;
Знайдемо норму вектор zj;
Якщо норма вектора zj більше заданої точності обчислення(норма більша за ε) — наростимо значення j на одиницю і повернемося до пункту5 цього переліку;
За знайдене рішення приймемо останнього набутого значення вектора х.