МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
СУМСЬКИЙ госудаственной УНІВЕРСИТЕТ
кафедра інформатики
Курсова робота
ПО КУРСУ:
Чисельні методи
на тему:
В«Ітераційні методи розв'язання систем нелінійних рівняньВ»
Суми, 2006
Зміст
1. Методи розв'язування систем нелінійних рівнянь. Загальна інформація
2. Ітераційні методи розв'язання систем нелінійних рівнянь
2.1 Метод простих ітерацій
2.2 Перетворення Ейткена
2.3 Метод Ньютона
2.3.1 Модифікації методу Ньютона
2.3.2 Квазіньютоновскіе методи
2.4 Інші ітераційні методи розв'язування систем нелінійних рівнянь
2.4.1 Метод Пікара
2.4.2 Метод градієнтного спуску
2.4.3 Метод релаксацій
3. Реалізація ітераційних методів програмно і за допомогою математичного пакету Maple
3.1 Метод простих ітерацій
3.2 Метод градієнтного спуску
3.3 Метод Ньютона
3.4 Модифікований метод Ньютона
Висновки
Список використаної літератури
1. Методи рішення нелінійних рівнянь. Загальна інформація.
Нехай нам дана система рівнянь, де - деякі нелінійні оператори:
(1.1)
Вона може бути також представлена ​​в матричному вигляді:
(1.1)
<
p> Де
Її рішенням називається таке значення, для котрого
Дуже поширеною є обчислювальна задача знаходження деяких або всіх рішень системи (1.1) з n нелінійних алгебраїчних або трансцендентних рівнянь з n невідомими.
Позначимо через Х вектор-стовпець ( х 1 , х 2 , ..., х n ) T і запишемо систему рівнянь у вигляді формули (1.2): F ( Х ) = 0, де F = ( f 1 , f 2 , ..., f n ) T .
Подібні системи рівнянь можуть виникати безпосередньо, наприклад, при конструюванні фізичних систем, або опосередковано. Так, до Наприклад, при вирішенні завдання мінімізації деякої функції G ( х ) часто необхідно визначити ті точки, в яких градієнт цієї функції дорівнює нулю. Вважаючи F = grad G, отримуємо нелінійну систему.
На відміну від систем лінійних алгебраїчних рівнянь, для вирішення яких можуть застосовуватися як прямі (або точні ), так і ітераційні (Або наближені ) методи, рішення систем нелінійних рівнянь можна отримати тільки наближеними, ітераційними методами. Вони дозволяють отримувати послідовність наближень. Якщо ітераційний процес сходиться, то граничне значення є вирішенням даної системи рівнянь.
Для повноти уявлення про методи знаходження рішення системи необхідно роз'яснити таке поняття, як "швидкість збіжності". Якщо для послідовності x n , збіжної до межі х * , вірна формула
( k - позитивне дійсне число), то k називається швидкістю збіжності даної послідовності.
2. Ітераційні методи розв'язання систем нелінійних рівнянь
2.1 Метод простих ітерацій
Метод простих ітерацій (послідовних наближень) є одним з основних в обчислювальній математиці і застосовується для вирішення широкого класу рівнянь. Наведемо опис та обгрунтування цього методу для систем нелінійних рівнянь виду
f i (x 1 , x 2 , ... x n ) = 0, i = 1,2, .. n
Наведемо систему рівнянь до спеціального виду:
(2.1)
Або у векторному вигляді. (2.2)
Причому перехід до цієї системи повинен бути тільки за умови, що
є стискуючою відображенням.
Використовуючи деяке початкове наближення X (0) = (x 1 (0) , x 2 (0) , ... x n (0) )
побудуємо ітераційний процес X (k +1) = пЃ† (X (k ) ). Розрахунки тривають до виконання умови. Тоді рішенням системи рівнянь є нерухома точка відображення.
Проведемо обгрунтування методу в деякій нормі простору.
Наведемо теорему про збіжність, виконання умов якої призводить до знаходження рішення системи.
Теорема (про збіжність). Нехай
1). Вектор-функція Ф (х) визначена в області
;
2). Для виконується умова
3). Справедливо нерівність
Тоді в ітераційному процесі:
1.
2. ,
де - рішення системи рівнянь;
3. ,
Зауваження. Нерівність умови 2) є умова Ліпшиця для вектор-функції Ф (х) в області S з константою (умова стиснення). Воно показує, що Ф є оператором стиску в області S , тобто для рівняння (2.2) діє принцип стислих відображень. Твердження теореми означають, що рівняння (2.2) має рішення в області S , і послідовні наближення сходяться до цього рішення зі швидкістю геометричній послідовності зі знаменником q .
Доказ . Оскільки, то для наближення в силу припущення 3) маємо. Це означає, що. Покажемо, що, k = 2,3, ... причому для сусідніх наближень виконується нерівність
(2.3)
Будемо міркувати по індукції. При твердження справедливе, тому і. Припустимо, що наближення належать S, і нерівність (2.3) виконано для. Оскільки, то для з урахуванням умови 2) теореми маємо
.
За індуктивному припущенню
.
Отже,
,
тобто нерівність (2.3) справедливо для. Покажемо, що. Враховуючи властивість (2.3) при, отримуємо
Отже,, і перше твердження теореми доведено.
Покажемо, що послідовність є збіжної. З цією метою перевіримо ознака збіжності Коші (покажемо, що послідовність є фундаментальною).
За аналогією з попереднім для будь-яких р = 1,2, ... маємо
Оскільки, то, тому для знайдеться такий номер, що для буде
Це означає виконання ознаки Коші, що гарантує збіжність послідовності. Позначимо. Затвердження 2) теореми доведено.
Для доказу останнього твердження скористаємося одержаними вище нерівністю
Перейдемо тут до границі при. Враховуючи неперервність функції і той факт, що, отримуємо необхідний результат - утвердження 3).
Зауваження 2. В умовах теореми рішення рівняння (2.2) в області S є єдиним.
Дійсно, нехай є два рішення, причому. Тоді
,
Отримали протиріччя, що й потрібно було довести.
Обговоримо умова 2) доведеної теореми. Розглянемо рівняння (2.2) в покомпонентного запису
і припустимо, що функції безперервно-діфференцируєми в області S (тобто існують і неперервні в S приватні похідні
).
Тепер з'ясуємо достатня умова виконання нерівності 2) в цьому випадку.
Утворюємо матрицю Якобі системи функцій
.
Далі, будемо використовувати узагальнену теорему про середнє (узагальнення на випадок вектор-функції формули кінцевих збільшень Лагранжа)
Тут матрична норма погоджена з векторною,, - точка відрізка, що з'єднує х, у.
Оскільки S - опукле безліч, то. Припустимо, що має місце оцінка
, причому. (2.4)
Тоді згідно з попереднім виконується умова 2) теореми
.
Таким чином, у разі дифференцируемости умова (2.4) на матрицю Якобі гарантує умова стиснення для вектор-функції
2.2 Перетворення Ейткена
Оскільки збіжність методу простих ітерацій лінійна, то вона досить повільна. Тому корисно уточнювати результат процесом Ейткена по трьом останнім ітерація, щоб збільшити точність знайденого рі...
