tify"> Припинити ітераційний процес слід, коли буде досягнута задана точність, тобто при виконанні умови
. (4)
Оскільки корінь належить відрізку, а - середина цього відрізка, то величина завжди буде менше половини довжини відрізка (див. рис. 2), тобто
. (5)
Отже, умова (4) буде виконано, якщо
. (6)
Таким чином, ітераційний процес потрібно продовжувати до тих пір, поки не буде виконана умова (6).
На відміну від більшості інших методів уточнення, метод половинного ділення сходиться завжди, тобто має безумовною збіжністю. Крім цього він надзвичайно простий, оскільки вимагає лише обчислення значень функції і, тому застосуємо для вирішення будь-яких рівнянь.
Однак метод половинного ділення досить повільний. З кожним кроком похибка наближеного значення зменшується у два рази, т.е.
, (7)
тому даний метод є методом з лінійною збіжністю.
Обчислимо кількість ітерацій N , необхідний для досягнення заданої точності e . Користуючись виразом (3) можна з'ясувати для яких значень k буде виконана умова (6), і взяти в якості N найменше з таких k :
,, (8)
де - ціла частина числа x . Наприклад, при і отримаємо.
Зауваження. При реалізації методу слід враховувати, що функція обчислюється з деякою абсолютною похибкою. Поблизу кореня значення функції малі за абсолютною величиною і можуть виявитися порівняти з похибкою її обчислення. Іншими словами, при підході до кореня ми можемо потрапити в смугу шумів і подальше уточнення кореня виявиться неможливим. Тому доцільно задати ширину смуги шумів і припинити ітераційний процес при попаданні в неї. Якщо прийняти, то ітераційний процес можна завершувати, коли значення функції після k -й ітерації стане меншим за модулем ? ., Т. е.
. (9)
Також необхідно мати на увазі, що при зменшенні інтервалу збільшуються похибки обчислення його довжини за рахунок віднімання близьких чисел [1, стор. 185].
1.3 Уточнення коренів методом хорд
Малюнок 3 - Метод хорд
Розглянутий метод так само, як і метод половинного ділення, призначений для уточнення кореня на інтервалі, на кінцях якого функція приймає значення різних знаків. Чергове наближення на відміну від методу половинного ділення беремо не в середині відрізка, а в точці, де перетинає вісь абсцис пряма лінія (хорда), проведена через точки А і У (рис. 3).
Запишемо рівняння прямої, що проходить через точки А і У :
.
Для точки перетину прямої з віссю абсцис () одержимо рівняння
. (10)
В якості нового інтервалу для продовження ітераційного процесу вибираємо той з двох і, на кінцях якого функція приймає значення різних знаків. Для розглянутого випадку (рис. 3) вибираємо відрізок, оскільки. Наступна ітерація полягає у визначенні нового наближення як точки перетину хорди з віссю абсцис і т.д.
Закінчуємо процес уточнення кореня, коли відстань між черговими приближениями стане менше заданої точності, т.е.
(11)
або при виконанні умови (9).
Малюнок 4 - Про збіжність методу хорд
Зауваження. Метод половинного ділення та метод хорд дуже схожі, зокрема, процедурою перевірки знаків функції на кінцях відрізка. При цьому другий їх них в ряді випадків дає більш швидку збіжність ітераційного процесу. Проте в деяких випадках метод хорд може збігатись істотно повільніше методу половинного ділення. Така ситуація показана на рис. 4. Обидва розглянутих методи не вимагають знання додаткової інформації про функції. Наприклад, не потрібно, щоб функція була дифференцируема. Навіть для розривних функцій розглянуті методи мають гарантовану збіжністю. Більш складні методи уточнення кореня використовують додаткову інформацію про функції, насамперед властивість дифференцируемости. Як результат вони зазвичай володіють більш швидкої збіжністю, але в той же час, застосовні для більш вузького класу функцій, і їх збіжність не завжди гарантована. Прикладом так...
