Кафедра: АСОІ
Лабораторна Робота
На тему: ЗНАХОДЖЕННЯ КОРЕНЯ НЕЛІНІЙНОГО РІВНЯННЯ. МЕТОДИ РІШЕННЯ СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ
Москва, 2008 рік
ЗНАХОДЖЕННЯ КОРЕНЯ НЕЛІНІЙНОГО РІВНЯННЯ
1. Постановка завдання
Нехай задана функція
Дана задача розпадається на кілька підзадач. По-перше, необхідно визначити кількість коренів, дослідити їх характер і розташування. По-друге, знайти наближені значення коренів. По-третє, вибрати з них цікавлять нас коріння і обчислити їх з необхідною точністю e. Перша і друга завдання вирішуються, як правило, аналітичними або графічними методами. У випадку, коли шукаються тільки речові корені рівняння (1), корисно скласти таблицю значень функції
Знайдені наближені значення коренів можна уточнити з допомогою різних ітераційних методів. Розглянемо три методи: 1) метод дихотомії (або розподіл відрізка навпіл), 2) метод простої ітерації і 3) метод Ньютона.
2. Методи вирішення задачі
2.1 Метод поділу отpезка навпіл
Найбільш простим методом, який дозволяє знайти корінь нелінійного рівняння (1), є метод половинного ділення.
Нехай на відрізку [a, b] задана безперервна функція
Отже, алгоритм методу дихотомії:
1. Поставити відрізок [a, b] і похибка e.
2. Якщо f (a) і f (b) мають однакові знаки, видати повідомлення про неможливість відшукання кореня і зупинитися.
Рис.1. Метод поділу відрізка навпіл для рішення рівняння виду f (х) = 0.
3. В іншому випадку обчислити c = (a + b) / 2
4. Якщо f (a) і f (c) мають різні знаки, покласти b = c, у противному випадку a = c.
5. Якщо довжина нового відрізка
Так як за N кроків довжина відрізка [a, b] скорочується в 2 N раз, то задана похибка відшукання кореня e буде досягнута за ітерацій.
Як видно, швидкість збіжності мала, але до достоїнств методу відносяться простота і безумовна збіжність ітераційного процесу. Якщо відрізок [a, b] містить більше одного кореня (але непарне число), то завжди буде знайдений якийсь один.
Зауваження. Для визначення інтервалу, в якому лежить корінь, необхідний додатковий аналіз функції
2.2 Метод простої ітерації
При використанні цього методу вихідне нелінійне рівняння (1) необхідно переписати у вигляді
Позначимо корінь цього рівняння C *. Нехай відомо початкове наближення кореня
і т.д. Для (n +1) - кроку отримаємо наступне наближення
Таким чином, за формулою (3) отримуємо послідовність С 0, С 1, ..., С n +1, що прагнути до кореня З * при n ® ¥. Ітераційний процес припиняється, якщо результати двох послідовних ітерацій близькі, тобто виконується умова
Досліджуємо умова і швидкість збіжності числової послідовності {C n} при n ® ¥. Нагадаємо визначення швидкості збіжності. Послідовність {C n}, що сходиться до межі С *, має швидкість збіжності порядку a, якщо при n ® ¥ виконується умова
Припустимо, що
e n +1 »C n +1 - C * = g ¢ (C *) (C n-C *) + ¼ @ g ¢ (C *) e n + ¼
Таким чином, отримуємо, що при виконанні умови
çg ¢ (C *) ç <1 (6)
послідовність (3) буде сходитися до кореня з лінійною швидкістю a = 1. Умова (6) є умовою збіжності методу простої ітерації. Очевидно, що успіх методу залежить від того, наскільки вдало обрана функція
Наприклад, для витягання квадратного кореня, тобто рішення рівняння виду x = a 2, можна покласти
x = g 1 (x) = a / x (7а)
або
x = g 2 (x) = (x + a / x) / 2. (7б)
Неважко показати, що
½ g 1 '(C) ½ = 1,
½ g 2 '(C) ½ <1.
Таким чином, перший процес (7а) взагалі не сходиться, а другий (7б) сходиться при будь-якому початковому наближенні З 0> 0.
Рис. 2. Графічна інтерпретація методу простих ітерацій для вирішення рівняння виду x = g (х).
Побудова кількох послідовних наближень за формулою (3)
З 0, С 1, ..., С n = C *
наведено на малюнку 2.
2.3 Метод Ньютона
У літературі цей метод часто називають методом дотичних, а також методом лінеаризації. Вибираємо початкове наближення С 0. Припустимо, що відхилення З 0 від істинного значення кореня З * мало, тоді, розкладаючи f (C *) в ряд Тейлора в точці С 0, отримаємо
f (C *) = f (C 0) + f ¢ (C 0) (C *-C 0) + ¼ (8)
Якщо f ¢ (C 0) ¹ 0, то в (8) можна обмежиться лінійними по DC = CC 0 членами. Враховуючи, що f (C *) = 0, з (9) можна знайти таке наближення для кореня
C 1 = C 0 - f (C 0) / f ¢ (C 0)
або для (n +1)-го наближення
C n +1 = C n - f (C n) / f ¢ (C n) (9)
Для закінчення ітераційного процесу можна використовувати одну з двох умов
çC n +1 - C n ç <e
або
çf (C n +1) ç <e.
Дослідження збіжності методу Ньютона проводиться аналогічно попередньому випадку. Самостійно отримати, що при виконанні умови
½ f''(C) / 2f '(C) ½ <1.
метод Ньютона має квадратичну швидкість збіжності (
Рис. 3. Графічна інтерпретація методу Ньютона для вирішення рівняння виду f (х) = 0.
Побудова кількох послідовних наближень за формулою (9)
З 0, С 1, ..., С n = C *
наведено на малюнку 3.
Завдання
1. Для заданої функції f (x)
· Визначте число речових коренів рівняння f (x) = 0, місце їх розташування і наближені значення (побудуйте графік або роздрукуйте таблицю значень).
· Обчисліть один із знайдених коренів (будь-який) з точністю e = 0,5 * 10 -3.
Для обчислень використовуйте метод розподілу відрізка навпіл (визначте число ітерацій), а потім цей же корінь знайдіть за допомогою методу Ньютона (також визначивши кількість ітераційних кроків).
Порівняйте отримані результати.
Варіанти завдань
1. x 3-3x 2 +6 x - 5 = 0 2. x 3 + sin x-12x-1 = 0
3. x 3-3x 2-14x - 8 = 0 4. 3x + cos x + 1 = 0
5. x 2 +4 sin x -1 = 0 6. 4x-ln x = 5
7. x 6-3x 2 + x - 1 = 0 8. x 3 - 0.1x 2 +0.3 x -0.6 = 0
9.
11.
13. x 3-4x 2-10x -10 = 0 14.
15.
17.
19.
21.
23.
25. x квітня +2.83 x 3 - 4.5x 2-64x-20 = 0 26.
МЕТОДИ РІШЕННЯ СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ
1. Постановка завдання
Нехай потрібно розв'язати систему n нелінійних рівнянь:
Прямих методів розв'язання системи (1) не існує. Лише в окремих випадках цю систему можна вирішити безпосередньо. Наприклад, для випадку двох рівнянь іноді вдається висловити одну невідому змінну через іншу і таким чином звести задачу до вирішення одного нелінійного рівняння щодо одного невідомого.
Систему рівнянь (1) можна коротко записати у векторному вигляді:
Рівняння (2) може мати один або кілька коренів у галузі визначення D. Потрібно встановити існування коренів рівняння і знайти наближені значення цих коренів. Для знаходження коренів зазвичай застосовують ітераційні методи, в яких принципове значення має вибір початкового наближення. Початкове наближення іноді відомо з фізичних міркувань. У разі двох невідомих початкове наближення можна знайти графічно: побудувати на площині (x 1, x 2) криві f 1 (x 1, x 2) = 0 і f 2 (x 1, x 2) = 0 і знайти точки їх перетину. Для трьох і більше змінних (а також для комплексних коренів) задовільних способів підбору початкового наближення немає.
Розглянемо два основних ітераційних методу розв'язання системи рівнянь (1), (2) - метод простої ітерації та метод Ньютона.
2. Методи рішення системи нелінійних рівнянь
2.1.Метод простої ітерації
Уявімо систему (1) у вигляді
або у векторній формі:
Алгоритм методу простої ітерації полягає в наступному. Виберемо деякий нульове наближення
Наступне наближення знаходимо за формулами:
або більш докладно:
Ітераційний процес (5) продовжується до тих пір, поки зміни всіх невідомих у двох послідовних ітераціях не стануть малими, тобто
На практиці часто замість останнього умови використовують нерівність:
де
При використанні даного методу успіх багато в чому визначається вдалим вибором початкового наближення
2.2. Метод Ньютона
У перекладній літературі можна зустріти назву метод Ньютона-Рафсона. Цей метод має набагато більш швидкої збіжністю, ніж метод простої ітерації.
Нехай відомо деяке наближення
Тоді вихідну систему (2) можна записати наступним чином:
Розкладаючи рівняння (7) в ряд Тейлора в околі точки
або в координатній формі:
Систему (8) можна переписати у вигляді:
Отримана система (9) є системою лінійних алгебраїчних рівнянь щодо збільшень
Значення функцій F 1, F 2, ..., F n і їх похідні в (9) обчислюються при
Визначником системи (9) є якобіан J:
Для існування єдиного рішення системи рівнянь (9) він повинен бути відмінний від нуля. Вирішивши систему (9), наприклад, методом Гаусса, знайдемо нове наближення:
Перевіряємо умову (6). Якщо воно не задовольняється, знаходимо
Ітерації припиняються, як тільки виконається умова (6).
Завдання
Використовуючи метод Ньютона, знайдіть рішення системи нелінійних рівнянь із заданою точністю
Варіанти завдань
1
3
5
7
9
11
13
15.
17.
19.
21.
Лабораторна Робота
На тему: ЗНАХОДЖЕННЯ КОРЕНЯ НЕЛІНІЙНОГО РІВНЯННЯ. МЕТОДИ РІШЕННЯ СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ
Москва, 2008 рік
ЗНАХОДЖЕННЯ КОРЕНЯ НЕЛІНІЙНОГО РІВНЯННЯ
1. Постановка завдання
Нехай задана функція
Дана задача розпадається на кілька підзадач. По-перше, необхідно визначити кількість коренів, дослідити їх характер і розташування. По-друге, знайти наближені значення коренів. По-третє, вибрати з них цікавлять нас коріння і обчислити їх з необхідною точністю e. Перша і друга завдання вирішуються, як правило, аналітичними або графічними методами. У випадку, коли шукаються тільки речові корені рівняння (1), корисно скласти таблицю значень функції
Знайдені наближені значення коренів можна уточнити з допомогою різних ітераційних методів. Розглянемо три методи: 1) метод дихотомії (або розподіл відрізка навпіл), 2) метод простої ітерації і 3) метод Ньютона.
2. Методи вирішення задачі
2.1 Метод поділу отpезка навпіл
Найбільш простим методом, який дозволяє знайти корінь нелінійного рівняння (1), є метод половинного ділення.
Нехай на відрізку [a, b] задана безперервна функція
Отже, алгоритм методу дихотомії:
1. Поставити відрізок [a, b] і похибка e.
2. Якщо f (a) і f (b) мають однакові знаки, видати повідомлення про неможливість відшукання кореня і зупинитися.
Рис.1. Метод поділу відрізка навпіл для рішення рівняння виду f (х) = 0.
3. В іншому випадку обчислити c = (a + b) / 2
4. Якщо f (a) і f (c) мають різні знаки, покласти b = c, у противному випадку a = c.
5. Якщо довжина нового відрізка
Так як за N кроків довжина відрізка [a, b] скорочується в 2 N раз, то задана похибка відшукання кореня e буде досягнута за ітерацій.
Як видно, швидкість збіжності мала, але до достоїнств методу відносяться простота і безумовна збіжність ітераційного процесу. Якщо відрізок [a, b] містить більше одного кореня (але непарне число), то завжди буде знайдений якийсь один.
Зауваження. Для визначення інтервалу, в якому лежить корінь, необхідний додатковий аналіз функції
2.2 Метод простої ітерації
При використанні цього методу вихідне нелінійне рівняння (1) необхідно переписати у вигляді
Позначимо корінь цього рівняння C *. Нехай відомо початкове наближення кореня
і т.д. Для (n +1) - кроку отримаємо наступне наближення
Таким чином, за формулою (3) отримуємо послідовність С 0, С 1, ..., С n +1, що прагнути до кореня З * при n ® ¥. Ітераційний процес припиняється, якщо результати двох послідовних ітерацій близькі, тобто виконується умова
Досліджуємо умова і швидкість збіжності числової послідовності {C n} при n ® ¥. Нагадаємо визначення швидкості збіжності. Послідовність {C n}, що сходиться до межі С *, має швидкість збіжності порядку a, якщо при n ® ¥ виконується умова
Припустимо, що
e n +1 »C n +1 - C * = g ¢ (C *) (C n-C *) + ¼ @ g ¢ (C *) e n + ¼
Таким чином, отримуємо, що при виконанні умови
çg ¢ (C *) ç <1 (6)
послідовність (3) буде сходитися до кореня з лінійною швидкістю a = 1. Умова (6) є умовою збіжності методу простої ітерації. Очевидно, що успіх методу залежить від того, наскільки вдало обрана функція
Наприклад, для витягання квадратного кореня, тобто рішення рівняння виду x = a 2, можна покласти
x = g 1 (x) = a / x (7а)
або
x = g 2 (x) = (x + a / x) / 2. (7б)
Неважко показати, що
½ g 1 '(C) ½ = 1,
½ g 2 '(C) ½ <1.
Таким чином, перший процес (7а) взагалі не сходиться, а другий (7б) сходиться при будь-якому початковому наближенні З 0> 0.
Рис. 2. Графічна інтерпретація методу простих ітерацій для вирішення рівняння виду x = g (х).
Побудова кількох послідовних наближень за формулою (3)
З 0, С 1, ..., С n = C *
наведено на малюнку 2.
2.3 Метод Ньютона
У літературі цей метод часто називають методом дотичних, а також методом лінеаризації. Вибираємо початкове наближення С 0. Припустимо, що відхилення З 0 від істинного значення кореня З * мало, тоді, розкладаючи f (C *) в ряд Тейлора в точці С 0, отримаємо
f (C *) = f (C 0) + f ¢ (C 0) (C *-C 0) + ¼ (8)
Якщо f ¢ (C 0) ¹ 0, то в (8) можна обмежиться лінійними по DC = CC 0 членами. Враховуючи, що f (C *) = 0, з (9) можна знайти таке наближення для кореня
C 1 = C 0 - f (C 0) / f ¢ (C 0)
або для (n +1)-го наближення
C n +1 = C n - f (C n) / f ¢ (C n) (9)
Для закінчення ітераційного процесу можна використовувати одну з двох умов
çC n +1 - C n ç <e
або
çf (C n +1) ç <e.
Дослідження збіжності методу Ньютона проводиться аналогічно попередньому випадку. Самостійно отримати, що при виконанні умови
½ f''(C) / 2f '(C) ½ <1.
метод Ньютона має квадратичну швидкість збіжності (
Рис. 3. Графічна інтерпретація методу Ньютона для вирішення рівняння виду f (х) = 0.
Побудова кількох послідовних наближень за формулою (9)
З 0, С 1, ..., С n = C *
наведено на малюнку 3.
Завдання
1. Для заданої функції f (x)
· Визначте число речових коренів рівняння f (x) = 0, місце їх розташування і наближені значення (побудуйте графік або роздрукуйте таблицю значень).
· Обчисліть один із знайдених коренів (будь-який) з точністю e = 0,5 * 10 -3.
Для обчислень використовуйте метод розподілу відрізка навпіл (визначте число ітерацій), а потім цей же корінь знайдіть за допомогою методу Ньютона (також визначивши кількість ітераційних кроків).
Порівняйте отримані результати.
Варіанти завдань
1. x 3-3x 2 +6 x - 5 = 0 2. x 3 + sin x-12x-1 = 0
3. x 3-3x 2-14x - 8 = 0 4. 3x + cos x + 1 = 0
5. x 2 +4 sin x -1 = 0 6. 4x-ln x = 5
7. x 6-3x 2 + x - 1 = 0 8. x 3 - 0.1x 2 +0.3 x -0.6 = 0
9.
11.
13. x 3-4x 2-10x -10 = 0 14.
15.
17.
19.
21.
23.
25. x квітня +2.83 x 3 - 4.5x 2-64x-20 = 0 26.
МЕТОДИ РІШЕННЯ СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ
1. Постановка завдання
Нехай потрібно розв'язати систему n нелінійних рівнянь:
Прямих методів розв'язання системи (1) не існує. Лише в окремих випадках цю систему можна вирішити безпосередньо. Наприклад, для випадку двох рівнянь іноді вдається висловити одну невідому змінну через іншу і таким чином звести задачу до вирішення одного нелінійного рівняння щодо одного невідомого.
Систему рівнянь (1) можна коротко записати у векторному вигляді:
Рівняння (2) може мати один або кілька коренів у галузі визначення D. Потрібно встановити існування коренів рівняння і знайти наближені значення цих коренів. Для знаходження коренів зазвичай застосовують ітераційні методи, в яких принципове значення має вибір початкового наближення. Початкове наближення іноді відомо з фізичних міркувань. У разі двох невідомих початкове наближення можна знайти графічно: побудувати на площині (x 1, x 2) криві f 1 (x 1, x 2) = 0 і f 2 (x 1, x 2) = 0 і знайти точки їх перетину. Для трьох і більше змінних (а також для комплексних коренів) задовільних способів підбору початкового наближення немає.
Розглянемо два основних ітераційних методу розв'язання системи рівнянь (1), (2) - метод простої ітерації та метод Ньютона.
2. Методи рішення системи нелінійних рівнянь
2.1.Метод простої ітерації
Уявімо систему (1) у вигляді
або у векторній формі:
Алгоритм методу простої ітерації полягає в наступному. Виберемо деякий нульове наближення
Наступне наближення знаходимо за формулами:
або більш докладно:
Ітераційний процес (5) продовжується до тих пір, поки зміни всіх невідомих у двох послідовних ітераціях не стануть малими, тобто
На практиці часто замість останнього умови використовують нерівність:
де
При використанні даного методу успіх багато в чому визначається вдалим вибором початкового наближення
2.2. Метод Ньютона
У перекладній літературі можна зустріти назву метод Ньютона-Рафсона. Цей метод має набагато більш швидкої збіжністю, ніж метод простої ітерації.
Нехай відомо деяке наближення
Тоді вихідну систему (2) можна записати наступним чином:
Розкладаючи рівняння (7) в ряд Тейлора в околі точки
або в координатній формі:
Систему (8) можна переписати у вигляді:
Отримана система (9) є системою лінійних алгебраїчних рівнянь щодо збільшень
Значення функцій F 1, F 2, ..., F n і їх похідні в (9) обчислюються при
Визначником системи (9) є якобіан J:
Для існування єдиного рішення системи рівнянь (9) він повинен бути відмінний від нуля. Вирішивши систему (9), наприклад, методом Гаусса, знайдемо нове наближення:
Перевіряємо умову (6). Якщо воно не задовольняється, знаходимо
Ітерації припиняються, як тільки виконається умова (6).
Завдання
Використовуючи метод Ньютона, знайдіть рішення системи нелінійних рівнянь із заданою точністю
Варіанти завдань
1
3
5
7
9
11
13
15.
17.
19.
21.