Ім'я файлу: 1.2 розділ.docx
Розширення: docx
Розмір: 169кб.
Дата: 24.04.2020
скачати

1 ОГЛЯД МЕТОДІВ ДЛЯ ПОШУКУ КОРЕНЯ РІВНЯННЯ

1.1 Методи уточнення дійсних коренів нелінійного рівняння


Методи відділення коренів дуже зручні і прості. Однак вони дають відповідь лише на питання локалізації кореня, і дозволяю знайти грубе наближення цього кореня. Якщо ж потрібно знайти більш точне значення кореня, то слід скористатися ітераційними методами.

Суть будь-якого ітераційного методу вирішення рівняння, полягає в наступному. Нехай відомий малий проміжок [, ], в якому міститься єдиний корінь x= рівняння (1). З досить малій околиці кореня вибирається довільна точка х0 – початкове наближення до кореня рівняння і будується послідовність точок - за допомогою рекурентного співвідношення:: , k=1, 2, … . При цьому послідовність - повинна сходитися до кореня x=, що забезпечується відповідним вибором .

Перевагою всіх ітераційних методів є те, що помилка обчислень не накопичується.

До основних ітераційних методам вирішення нелінійних рівнянь відносяться метод дотичних, метод хорд, метод половинного ділення, метод простих ітерацій і комбінований метод.

1.2 Метод хорд ( січних або метод лінійної інтерполяції)


Будемо вважати, що на відрізку функція неперервна разом з похідними і , які не міняють знак на і . У методі хорд (січних) точка перетину кривої з віссю на кожному кроці наближається точкою перетину хорди, що стягує кінці дуги , , з віссю . Послідовні наближення при цьому обчислюються за формулою
.
У формулі в якості береться той кінець відрізка , для якого виконується умова , а початкове наближення вибирається так, що .

Геометрична інтерпретація методу хорд:



Рисунок 1.Геометрична інтерпретація методу хорд.
Описаний метод називається також методом січних або методом лінійної інтерполяції. Послідовні наближення в методі хорд утворюють монотонну обмежену зверху чи знизу коренем послідовність. При цьому справедлива оцінка
,
де , .

Метод січних можна розглядати як метод ітерації для еквівалентного рівняння , де і початкове наближення береться так, що .

    1. Метод дотичних (Ньютона)



Нехай корень рівняння f(x) = 0 відділений на відрізку . Необхідною умовою збіжності методу є те, що похідні и неперервні і зберігають постійні знаки.

Алгоритм наближеного обчислення кореня методом дотичних.

Вихідні дані:

f(x) – функція;

f(x) – похідна заданої функції f(x);

ε – необхідна точність;

x0 – початкове наближення.

Результат: xпр. – наближений корінь рівняння f(x) = 0.

Метод рішення:

Розглянемо випадок, коли , тобто і мають однакові знаки. Тоді можливі два випадки побудови кривої на відрізку (див. рис. 2).

Проведемо дотичну до кривої y =f(x) в точці В0(b; f(b)). В курсі алгебри виводиться рівняння дотичної.

Рівняння дотичної в точці В0 має вигляд . В якості чергового наближення до кореня рівняння беремо точку перетину дотичної з віссю Оx. Вважаючи y = 0, знайдемо . Тепер . Застосовуючи метод ще раз для відрізка , отримаєм

.
Отримуємо рекурентну формулу обчислення наближень до кореня:



Рисунок 2.Геометрична інтерпретація методу дотичних для випадку .
Звернемо увагу, що в цьому випадку в якості початкового наближення до кореня вибираємо точку x0 = b. Наближення до кореня відбувається з правого боку, тому отримуємо наближене значення кореня з надлишком.

Нехай тепер , тобто і мають різні знаки. Тоді також можливі два випадки побудови кривої на відрізку (див. рис. 3)

Рисунок 3. Геометрична інтерпретація методу дотичних для випадку .
Якщо знову провести дотичну до кривої в точці В0, то вона перетне вісь Ох у точці, шо не належить відрізку . Тому проведемо дотичну в точці . Її рівняння . Знаходимо x1, вважаючи y = 0: . Корінь . Застосовуючи метод ще раз для відрізка , маємо .

Отримуємо рекурентну формулу обчислення наближень до кореня, аналогічну першому випадку:

В даному випадку в якості початкового наближення до кореня вибираємо точку x0 = a. Наближення до кореня відбувається з лівого боку, тому знаходимо наближене значення кореня з недоліком.

Зауважимо, що обчислювальні формули методу відрізняються один від одного тільки вибором початкового наближення: в першому випадку за x0 приймаємо кінець b відрізка, у другому – кінець a.

Переконайтеся самі, що при виборі початкового наближення кореня можна керуватися правилом: за вихідну точку слід вибрати той кінець відрізка , в якому знак функції збігається зі знаком другої похідної (див. рисунки 8,9).

Умова закінчення обчислювального процесу: , де ε – задана точність. Тоді xпр. = xn+1 з точністю ε.

  1. МЕТОД ДИХОТОМІЇ ТА ПОЛОВИННОГО ДІЛЕННЯ




2.1 Аналітичний розгляд методу дихотомії

2.1.1 Наближені методи розв’язування алгебраїчних та трансцендентних рівнянь методом дихотомії


Нехай функція f (x) визначена і неперервна при всіх x що належать [a; b] і на [a; b] змінює знак, тобто f (a) f (b) <0. Тоді згідно з теоремою Больцмана-Коші (Якщо неперервна на відрізку [a; b] функція f (x) на кінцях його має протилежні знаки, тобто f (a) f (b) <0, то на інтервалі (a; b ) вона хоча б один раз звертається в нуль) рівняння має на (a; b) хоча б один корінь.

Візьмемо довільну точку c що належить (a; b). Будемо називати в цьому випадку відрізок [а; b] проміжком існування кореня , А точку с - пробною точкою. Оскільки мова тут йде лише про функції дійсної змінної, то обчислення значення f (с) призведе до якої-небудь однієї з наступних взаємовиключних ситуацій:

  1. f (а) f (с) <0;

  1. f (с) f (b) <0;

  2. f (c) = 0.

Що стосується аналізованому завданню то їх можна інтерпретувати так:

а) корінь знаходиться на інтервалі (а;c);

б) корінь знаходиться на інтервалі (c;b);

в) точка c є шуканим коренем.

Таким чином, одне обчислення значення функції дозволяє зменшити проміжок [а; b] існування кореня (ситуація а чи б) або вказати його значення (ситуація в), малоймовірна в сенсі "прямого попадання" пробна точка с в корінь, але цілком реальна в сенсі виконання наближеної рівності f (с) ≈ 0, коли довжина проміжку існування кореня близька до довжини проміжку його невизначеності). Зрозуміло, що в залежності від того, має місце ситуація а чи б, описана процедура одного кроку звуження проміжку існування нуля неперервної функції f (x) може бути застосована до проміжку [а; с] що належить [а; b] або до [c; b] що належить [a; b] відповідно і далі повторюватися циклічно.

Такий простий і легко програмований процес називається методом дихотомії (Від грецького слова, що означає розподіл на дві частин ), методом бісекції, методом вилки,методом проб. Якщо спосіб завдання пробних точок с визначений так, що послідовність довжин, що виходять в цьому процесі проміжків існування кореня прагне до нуля, то методом дихотомії можна знайти будь-який корінь рівняння f (x) = 0 з наперед заданою точністю.

Найбільш популярним окремим випадком методу дихотомії є метод половинного ділення, який реалізує найпростіший спосіб вибору пробної точки - розподіл проміжку існування кореня навпіл. Виконати наближене обчислення з точністю (епсилон) кореня рівняння f (x) = 0 методом половинного ділення за умови, що f (x) неперервна на [а; b] і f (a) f (b) <0, можна, наприклад, за такою схемою:

Крок 0. Задати кінці відрізка а і b , функцію f, мале число > 0 (допустиму абсолютну погрішність кореня або півдовжину його проміжку невизначеності), мале число > 0 ( дельта, допущення, пов'язане з реальною точністю обчислення значень даної функції); обчислити (або ввести)f (a) .

Крок 1. Обчислити c: = 0,5 (а + b).

Крок 2. Якщо b - а <2 , то покласти ξ: ≈ с (ξ (ксі) - корінь) і зупинитися.

Крок 3. Обчислити f (с).

Крок 4. Якщо f (с) < , то покласти ξ: ≈ з і зупинитися.

Крок 5. Якщо f (а) f (с) <0, то покласти b: = з і повернутися до кроку 1;
інакше покласти а: = с, f (а): = f (с) і повернутися до кроку 1.

Зауваження. У спрощених варіантах схем реалізації методу половинного ділення обходяться без введення допуску . В такому випадку в кроці 4 замість нерівності | f (с) | < використовують рівність f (с) = 0. Тоді розгалуження алгоритму, що диктуються кроками 4 і 5, можна виконувати порівняння з нулем (з трьома наслідками) добутку f (а) f (с).

За один крок методу половинного ділення проміжок існування кореня скорочується рівно вдвічі. Тому, якщо за k - e приближення цим методом до кореня ξ рівняння f (x) = 0 приймемо точку хk, що є серединою отриманого на k-му кроці відрізка [ak; bk] В результаті послідовного звуження даного відрізка [а; b], вважаючи а1: = А, b1: = B, то прийдемо до нерівності

(*)

(Апріорі, ξ - будь-яка точка інтервалу (аk; bk), і відстань від неї до середини цього інтервалу не перевищує половини його довжини. Це як раз і бачимо в (*) при k = 1).

Нерівність (*), з одного боку, дозволяє стверджувати, що послідовність (хk) має межу - шуканий корінь ξ рівняння f (x) = 0; з іншого боку, будучи апріорної оцінкою абсолютної погрішності приблизної рівності хk ≈ ξ, дає можливість підрахувати число кроків (ітерацій) методу половинного ділення, достатню для отримання кореня ξ, з заданою точністю , для цього потрібно знайти найменше натуральне k, що задовольняє нерівності



Використовуваний в методі половинного ділення спосіб фіксування пробної точки можна охарактеризувати як пасивний, бо він здійснюється по заздалегідь жорстко заданому плану і ніяк не враховує обчислювані на кожному кроці значення функції.


2.2 Метод половинного ділення


Нехай дано рівняння: f (x) = 0.

Будемо вважати, що його корінь t відділений на відрізку [а; b]. Потрібно знайти приблизне значення кореня з точністю до , де - досить мале додатне число.

В основі методу половинного ділення лежить теорема про вкладені відрізки. Послідовність відрізків [a1; b1] [a2; b2] ...n; bn] ... називається вкладеною .

За умови, що довжини відрізків bn - аn→ 0 при n →нескінченності, це послідовність що стягується.

Теорема Кантора. Для будь-якої стисканої послідовності вкладених відрізків існує єдина точка t, що належить всім відрізкам цієї послідовності.

Допустим, що функція f неперервна на відрізку [а; b] і на його кінцях приймає значення різних знаків, навчимося визначати послідовність вкладених відрізків [a; b] [an; bn] (N = 1, 2, ...), стискають до кореню t. Тим самим ми отримали перший спосіб з методів уточнення коренів.

Отже, нехай f неперервна на [а; b] і f (а) ∙ f (b) <0 (див. рис. 2.1).


Рисунок2.1

Розділимо [a; b] навпіл точкою с = (а + b) / 2 і обчислимо f (с). Якщо f (с) = 0, то корінь t знайдений точно (а саме, t = с). Якщо ні, виберемо ту половину відрізка, на кінцях якої значення функції різних знаків, і позначимо її [а1 b1] (На рис. 1 права половина [а; b]). Потім відрізок [a1; b1] ділимо навпіл точкою c1 = (А1 + b1) / 2 і проводимо аналогічні дії. Вийде або точний корінь c1, Або відрізок [а2; b2] з властивістю f (а2) ∙ f (b2) < 0. І так далі.

Якщо на якомусь етапі виявиться точний корінь (що на практиці малоймовірно), то процес ділення навпіл закінчиться, якщо ж ні, то в результаті вийде нескінченна послідовність вкладених відрізків [a1; b1], [A2; b2], ..., [an; bn], ..., таких, що

f (an) ∙ f (bn) <0 при всіх n = 1, 2, .... (*)

Зрозуміло, що bn - аn → 0 при n → нескінченності. Отже, отримана послідовність відрізків є стисканою.

Теорема Кантора гарантує існування єдиної точки, що належить всім відрізкам цієї послідовності. Так як f неперервна на [а; b], з (*) випливає, що цією точкою є саме корінь t.

Для того щоб знайти приблизе значення кореня з точністю до > 0, необхідно зупинити процес половинного ділення на такому кроці n, на якому відрізок [an; bn] Матиме довжину

bn - an = (B - a) / 2n <2 (**)

і обчислити х = (An + bn) / 2.Зрозуміло, що тоді можна взяти t ≈ x, причому | t - x | ≤ (див. рис. 2.2).


Рисунок2.2.

Корисно мати на увазі, що обчислюються при кожному n = 1,2, ... середини зn відрізків [an; bn] утворюють насправді послідовність наближень до кореня. При цьому зрозуміло, що

cn = (Bn - an) / 2 = (b - a) / 2n + 1

Метод половинного ділення дає простий і зручний алгоритм уточнення коренів з будь-яким напередзаданим ступенем точності. Він вимагає від функції f виконання легко перевірних властивостей: безперервності на відрізку ізоляції кореня і різних знаків значень на його кінцях.

Відмінною рисою методу є те, що швидкість наближення по ньому зовсім не пов'язана з властивостями функції в околиці кореня. Кількість кроків наближення залежить лише від відрізка [а; b] і заданої точності , при цьому на кожному кроці абсолютна погрішність приблизного значення кореня зменшується рівно вдвічі (і тільки!). Внаслідок цього збільшення точності завжди пов'язане з пропорційним зростанням обсягу обчислювальної роботи.

У правильності зроблених висновків переконує приклад.

Приклад. Єдиний корінь t рівняння х3- х - 1 = 0 розташований на відрізку [1; 2]. Для уточнення t можна застосувати метод половинного ділення, оскільки функція f: f (x) = х3 - х - 1 неперервна на цьому відрізку і на його кінцях приймає значення різних знаків: f (1) = - 1 <0, f (2) = 5> 0.

Знайдемо середину з = 1,5 відрізка [1; 2] і обчислимо значення функції f в цій точці: f (1,5) = 0,875. Значить, число 1,5 не є точним коренем. Якщо взяти t ≈ 1,5, то 1,5= (2 - 1) / 2 = 0,5. Точність наближення невисока, але цифра 1 вже є вірною.

Далі помічаємо, що f (1) <0, f (1,5)> 0 і, отже, корінь лежить на відрізку [a1; b1] = [1; 1,5]. Ділимо навпіл отриманий відрізок точкою c1= 1,25 і знаходимо f (1,25) = -0,3. Абсолютна погрішність наближеного кореня 1,25 дорівнює 0,25. Точність підвищилася, але незначно, так як вірних цифр у наближення не додалося.

На наступному кроці треба взяти [а2; b2] = [1,25; 1,5] і з2= 1,375. оскільки C2 = 0,125, знову гарантується тільки одна вірна цифра наближеного числа 1,375. І так далі. Бачимо, що уточнення йде повільно, а для пошуку наближеного кореня з двома вірними цифрами необхідно провести ще два кроки обчислень.

Зауваження. Якщо відрізок ізоляції кореня відомий, умова безперервності функції f перестає бути необхідним для методу половинного ділення. Треба лише, щоб функція була визначена на цьому відрізку і брала зліва від кореня значення одного знака, а праворуч - іншого.

    1. Формалізація і алгоритмізація моделі


Грунтуючись на аналітичному рішенні, було прийнято використовувати наступну формалізовану модель реалізації завдання.

  1. Введення даних (точки початкового наближення: a, b)

  1. Перевірка даних, введених користувачем

  2. Рішення задачі

    1. Перевіряємо, чи має завдання рішення взагалі (f (a) *f(b)

    2. Якщо завдання не має рішення, то припиняємо обчислення і виводимо користувачеві повідомлення про те, що рішення не може бути знайдено. інакше:

    3. шукаємо рішення

      1. Крок. Обчислити c: = 0,5 (а + b).

      2. Крок. Якщо b - а <2 , покласти ξ: ≈ с (ξ (ксі) - корінь) і зупинитися.

      3. Крок. Обчислити f (с).

      4. Крок. Якщо f (с) < , покласти ξ: ≈ з і зупинитися.

      5. Крок. Якщо f (а) f (с) < 0, покласти b: = з і повернутися до кроку 1;
        інакше покласти а: = с, f (а): = f (с) і повернутися до кроку 1 .

  3. Висновок результату

  4. Завершення роботи


На основі прийнятого формалізованого рішення побудуємо графічний алгоритм пошуку кореня рівняння методом дихотомії (див. рис. 2.3). Звідси випливає, що при написанні програми буде використаний процедурний підхід.



Рисунок2.3. Алгоритм функції пошуку кореня рівняння.



скачати

© Усі права захищені
написати до нас