Головна |
Для відділення коренів можна скористатися методом лінійного пошуку, в якому діапазон пошуку проходиться з кроком при виконанні умови приймається рішення про наявність кореня в проміжку . У загальному випадку в діапазоні пошуку може виявитися кілька коренів ( ), До кожного з яких слід застосувати операцію уточнення. Ілюстрація та алгоритм відділення коренів представлені відповідно на рис.1.1 і 1.2 додатка.
уточнення коренів
Існує кілька основних методів уточнення коренів рівнянь.
1. Метод поділу навпіл (метод дихотомії, метод бисекции)
Це найбільш надійний алгоритм, особливо коли про поведінку відомо тільки, що - Функція дійсної змінної x і відомий інтервал , на якому змінює знак (рис.1.3). Отже, між и існує точка, в якій функція звертається в нуль. Якщо розділити інтервал навпіл і дізнатися, більше
Рис.1.1 - ілюстрація до відокремлення коренів
нуля або менше нуля функція в точці поділу, то можемо вказати подинтервал, в якому функція змінює знак. Наступним розподілом вказуються подинтервалов можна як завгодно близько підійти до кореня: наприклад, за 10 кроків інтервал з коренем буде зменшений в 1024 рази. При заданій абсолютної точності e алгоритм методу розподілу навпіл складається з наступних кроків (рис.1.4).
1.обчислити и . Витрати машинного часу на уточнення кореня оцінюють побічно, за кількістю звернень до функції - , Отже, буде інкрементіровать двічі.
2.якщо знаки и не збігаються, т. е. , і , То потрібно замінити на і перейти до п.1.
3.Якщо ж при , Слід припинити обчислення, т. К. Досягнута задана точність.
4.якщо , и , То потрібно замінити на і перейти до п.1; в іншому випадку - припинити обчислення, так як досягнута задана точність. Будь-який з кінців відрізка , А краще його середина, може бути використана в якості кореня рівняння .
Відзначимо основні переваги методу розподілу навпіл: 1) абсолютно надійний; 2) швидкість збіжності не залежить від виду .
Рис.1.2 - алгоритм відділення коренів
2. Метод хорд
Метод поділу навпіл буде покращено, якщо для наступного обчислення використовувати не середину відрізка , А то значення в якому дає нуль лінійна інтерполяція між двома відомими значеннями функції протилежного знака (рис.1.5).
Геометрично спосіб лінійної інтерполяції еквівалентний заміні кривої хордою, що проходить через точки и
Рис.1.3, б - ілюстрації до методу розподілу навпіл
Рівняння хорди:
вважаючи и отримуємо наближення до кореня:
. (1)
Алгоритм методу хорд (рис.1.6):
1.обчислити и
2.обчислити за формулою (1) і
3.якщо знаки и збігаються, т. е. то кінець нерухомий. В цьому випадку прийняті: якщо . Потім перейти до п.2. В іншому випадку, тобто. Е. При обчислення завершені, т. к. задана точність досягнута.
4.якщо нерухомий кінець . В разі : Потім перейти до п.2. Інакше - обчислення завершені. значення використовується як корінь рівняння.
Переваги методу хорд: 1) абсолютно надійний; 2) в більшості випадків має більш швидку збіжність, ніж метод поділу навпіл.
Недолік: швидкість збіжності залежить від виду , і тому для деяких функцій число кроків на уточнення кореня може виявитися більшим, ніж в методі поділу навпіл.
Рис.1.4 - алгоритм методу розподілу навпіл
3. Метод дотичних (метод Ньютона)
якщо має одну і більш безперервних похідних (т. е. досить гладка), то можна застосувати метод Ньютона (метод дотичних) і метод січних, що дозволяють скоротити число обчислень функції в порівнянні з методом розподілу навпіл і методом хорд, т. е. зменшити витрати машинного часу.
У методі Ньютона кожне нове наближення обчислюється як єдиний нуль дотичній прямій до функції в точці :
.
Це итерационная формула методу Ньютона. Кожна ітерація вимагає обчислення не тільки , але і її похідної .
Ілюстрація до методу дотичних представлена ??на рис.1.7, а алгоритм методу - на рис.1.8.
Метод Ньютона має гарну збіжність. Основна складність полягає у виборі початкового наближення яке веде до Сходячих ітераційного процесу. Тому методу Ньютона часто передує якийсь глобально сходиться алгоритм типу ділення навпіл.
Рис.1.5 - ілюстрація до методу хорд
4. Метод січних
Даний метод замінює похідну першої різницею, знайденої по двох останніх итерациям. Ітераційна формула методу має вигляд
У цьому алгоритмі починають з двома вихідними числами и На кожному кроці отримують як єдиний нуль січною прямий до функції що проходить через точки з абсциссами и (Рис.1.9). Алгоритм методу січних наведено на рис.1.10.
Метод січних має хорошу збіжність. Недолік - в призначенні и , досить близьких до кореня для того, щоб могла початися збіжність.
Рис.1.6 - алгоритм методу хорд
5. Метод ітерацій
рівняння замінюють рівносильним Вибирають будь-яким способом наближене значення кореня і по ньому знаходять Повторюючи процес, отримують послідовність чисел:
Якщо ця послідовність - сходиться, то межа є коренем равносильного рівняння і може бути обчислений по ітераційної формулою з будь-яким ступенем точності.
Процес ітерацій слід продовжувати до тих пір, поки для двох послідовних наближень не буде виконано нерівність де - Задана абсолютна точність обчислення кореня і
Тому в методі ітерацій при переході від рівняння до рівняння слід вибирати таке уявлення , за якого що є умовою збіжності методу. чим менше , Тим швидше послідовні наближення сходяться до кореня . Ілюстрації до методу ітерацій дані на рис.1.11, алгоритм - на рис.1.12
На закінчення слід зазначити, що не існує методу, який мав би явну перевагу перед іншими для довільного класу функцій.
5. Комбіновані методи рішень нелінійних рівнянь
Методи комбінують для підвищення ефективності: комбінований метод повинен забезпечити при тій же величині помилки менші витрати машинного часу в порівнянні з будь-яким з комбінованих методів. Приклади алгоритмів комбінованих методів представлені на рис.1.13 і 1.14.
Ріс.1.7 - ілюстрація до методу дотичних
Рис.1.8 - алгоритм методу дотичних
Рис.1.9 - ілюстрація до методу січних
Ріс.1.10 - алгоритм методу січних
Короткі відомості | Рішення нелінійних рівнянь в системі Mathcad
нелінійних рівнянь | Приклад побудови графіка функції і рішення нелінійного рівняння | ЗАВДАННЯ | Короткі відомості | Виділіть форму, клацнувши на ній лівою кнопкою миші, і в властивість Caption (напис) впишіть тригонометричним ІНТЕРПОЛЯЦІЯ. | алгебра матриць | Алгоритми формування матриць | Методи розкладання матриць | Методи звернення матриць | Операції з векторами і матрицями в системі Mathcad |