Алгоритми уточнення коренів

Програма методу перебору

x³ – 4x² + 2 = 0

A = 2

B = 5

H = 0.2

F(U) = (U - 4)U×U +2

READ (5,13) A,B,H

13 FORMAT (2F5.1, F4.1)

X=A

V=F(X)

4 X=X+H

W=F(X)

IF (V×W) 7,9,9

7 P=X-H/2

WRITE (6,14) P,X

14 FORMAT (‘ ‘,2F5.1)

9 V = W

IF (X-B) 4,11,11

11 PRINT 15

15 FORMAT (‘ ‘, ‘ВІДРІЗОК ПРОЙДЕНИЙ’)

STOP

END

2.0 5.0 0.2

Для алгебраїчного рівняння

a₀xⁿ + a₁x^n-1+…+a_n-1x+a_n =0 (a₀ ¹ 0)

границі коренів

A = max { |a₁|,|a₂|…|a_n|}

B = max { |a₀|,|a₁|…|a_n-1|}

Тоді всі корені цього рівняння задовольняють нерівності

r = < |x| < 1+ = R

1. Алгоритм уточнення кореня методом половинного ділення.

Нехай яким-небудь методом знайдений відрізок ізоляції кореня [а;b] рівняння F(x) = 0, де F(x) неперервна на [а;b], і F(a)×F(b)< 0. Потрібно звузити цей відрізок так, щоб його довжина стала не більшою наперед заданої точності обчислення кореня, тобто |b - а|≤ε. Цей процес звуження інтервалу, що містить ізольований корінь, називається уточненням кореня. В цьому алгоритмі відрізок ізоляції кореня [а;b] ділять навпіл точкою Х = і обчислюють значення F(Х). Якщо F(Х) = 0, то Х – значення шуканого кореня рівняння і задача розв’язана. Якщо F(Х) ¹ 0, то шуканий корінь знаходимо на одному із двох відрізків [а;Х] або [Х;b], на кінцях якого функція F(Х) приймає значення різних знаків. Позначимо цей відрізок через [а₁;b₁], його довжина b₁ – a₁ = . З відрізком [а₁;b₁] чинять так само як із відрізком [а;b]. Цей процес послідовного ділення відрізка навпіл продовжують до тих пір, поки не буде одне із двох:

1. або знайдеться така точка Х_n = , в якій F(Х_n) = 0

(що малоймовірно) і задача розв’язана;

2. або такої точки не знайдеться, але при деякому n прийдемо до відрізка [а_n;b_n] довжини b_n – a_n = ≤ε, що містить в собі шуканий корінь. Тоді числа а_n і b_n є наближеними значеннями шуканого кореня з недостачею і надлишком, відповідно.

Dx_n= (b-a)/2ⁿ ≤ε

n = ln((b-a)/ε) / ln2

Кількість ітерацій для знаходження коренів.

Дата добавления: 2015-05-23