21.3. Розв’язання нелінійних та трансцендентних рівнянь.

Розв’язання нелінійних (зокрема, трансцендентних) рівнянь виду

F(x)=0 (2)

заключається у відшукуванні одного або всіх коренів на відрізку [a, b] зміни x. Зазвичай намагаються локалізувати кожен корінь у своєму відрізку [a, b]. Тоді знаходження всіх коренів зводиться до локалізації кожного кореня з послідуючим звуженням відрізків локалізації кореня [a, b] одним з описаних нижче методів.

Метод простих ітерацій заснований на представленні (2) у вигляді

x=f(x) (3)

і багатократному застосуванні ітераційної формули x_n+1=f(x_n) до того часу, доки дотримується умова

|x_n+1-x_n|≥ε,

де ε – задана погрішність обчислення кореня x. Ітераційний процес збігається (тобто ), якщо дотримується умова

Програма 7

10 PRINT ’ВВЕДІТЬ РІВНЯННЯ X=F(X) МЕТОДОМ’

15 PRINT ’ПРОСТИХ ІТЕРАЦІЙ’

20 INPUT ’ЗАДАЙТЕ ПОЧАТКОВЕ ЗНАЧЕННЯ X X0=’X

25 INPUT ’ЗАДАЙТЕ ПОГРІШНІСТЬ РЕЗУЛЬТАТУ E=’E

30 GOSUB 70

40 IF ABS(F-X)<E THEN 60

50 LETX=F:GOTO 30

60 PRINT ’КОРІНЬ X=’X: GOTO 20

65 REM ’ПІДПРОГРАМА ОБЧИСЛЕННЯ F(X)’

70 LETF=SIN(X)+.25

75 RETURN:END

В рядку 70 програми 7 записаний вираз f(x)=sin x+0,25 (підпрограма), що відповідає розв’язанню трансцендентного рівняння

F(x)=x – sin x – 0,25=0.

Для початкового значення x=x₀=1,2 та погрішності ε=E=1∙10^-6 отримаємо за часом рахунку біля 5 с.

Метод Ньютона (дотичних) заснований на заміні F(x) у точці початкового наближення x=x₀ дотичної, пересікання якої з осью x дає перше наближення x₁, тощо (рис.4). Таким чином, ітераційний процес сходження до кореня реалізується формулою

до того часу, поки дотримується умова. Метод забезпечує швидку (квадратичну) збіжність, якщо

У якості x₀ обирають той кінець відрізку [a, b], на якому знаки F(x₀) та співпадають. Виграш у часі обчислень за рахунок швидкої збіжності зменшується через необхідність обчислення окрім F(x_n) похідної Виключення складають приватні випадки, коли вираз, за яким обчислюється не складніше виразу для обчислення F(x_n) окремо.

Програма 8

10 PRINT ’РОЗВ’ЯЗАННЯ РІВНЯНЬ F(X)=0 МЕТОДОМ НЬЮТОНА’

20 INPUT ’ЗАДАЙТЕ ПОЧАТКОВЕ НАБЛИЖЕННЯ X0=’X

25 INPUT ’ЗАДАЙТЕ ПОГРІШНІСТЬ РЕЗУЛЬТАТУ E=’E

30 GOSUB 60:LETX=X-F

40 IF ABS(F)>E THEN 30

50 PRINT ’КОРІНЬ РІВНЯННЯ X=’X:GOTO 20

55 REM ’ПІДПРОГРАМА ОБЧИСЛЕННЯ F(X)/(DF/DX)’

60 LETF=(X-SIN(X)-.25)/(1-COS(X))

70 RETURN:END

П р и к л а д. Обчислити корінь рівняння (4) на відрізку [1,1; 1,2]. В данному випадку отож

Обчислення цього виразу оформлено підпрограмою, що записана з рядка 60. Оскільки та F(x)>0 при x=b, у якості початкового зближення візьмемо x₀=b=1,2.

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

де . Отже, ітераційна формула має вигляд

Значення Δx не обов’язково повинно дорівнювати ε. Рівність дозволяє зменшити кількість вихідних даних при вводі.

Програма 9

10 PRINT ’РОЗВ’ЯЗАННЯ РІВНЯНЬ F(X)=0 МОДИФІКОВАНИМ’

15 PRINT ’МЕТОДОМ НЬЮТОНА’

20 INPUT ’ЗАДАЙТЕ ПОЧАТКОВЕ НАБЛИЖЕННЯ X0=’X

25 INPUT ’ЗАДАЙТЕ ПОГРІШНІСТЬ РЕЗУЛЬТАТУ E=’E

30 GOSUB 70: LETL=F: LETX=X+E

40 GOSUB 70:LETL=E*L/(F-L):LETX=X-L-E

50 IF ABS(L)>E THEN 30

60 PRINT ’КОРІНЬ РІВНЯННЯ X=’X:GOTO 20

70 LETF=X-SIN(X)-.25

80 RETURN:END

Метод Рибакова також можна розглядати як модифікацію метода Ньютона при заміні деяким числом де ξ – значення x на відрізку [a, b], при якому максимальна. При збіжність не порушується, але уповільнюється. Метод Рибакова зручне для пошуку всіх коренів рівняння (2) на відрізку [a, b] з допомогою слідую чого алгоритму.

1. Задаємо початкові значення x=x₀=a.

2. Для кожної n-ої ітерації (n=0, 1, 2, ...) обчислюємо

(7)

і перевіряємо умову

(8)

Якщо (8) не виконується, виходить, знайдені всі корені. В противному випадку перевіряємо виконання умови Якщо вона виконується, повторюємо цикл обчислень по формулі (7). Якщо ця умова не виконана, значить, x_n+1 є одним з коренів і значення x_n+1 виводиться на друк. Після цього переходимо до виконання наступного пункту.

3. Задаємо початкове наближення до чергового кореня і, якщо x₀<b, йдемо до виконання п.2. Якщо x₀≥b, обчислення вважаємо завершеними.

Кількість ітерацій при реалізації методу Рибакова Функція F(x) на відрізку [a, b] може мати похідну з розривами першого роду.

Програма 10

10 PRINT ’ЗНАХОДЖЕННЯ ВСІХ КОРЕНІВ РІВНЯННЯ F(X)=0’

15 PRINT ’В ІНТЕРВАЛІ ВІД А ДО В МЕТОДОМ РИБАКОВА’

20 INPUT ’ВВЕДІТЬ ГРАНИЦІ ІНТЕРВАЛУ A, B ’A, B

25 INPUT ’ЗАДАЙТЕ ПОГРІШНІСТЬ ЗНАХОДЖЕННЯ КОРЕНЯ E=’E

30 INPUT ’ЗАДАЙТЕ ЧИСЛО M=’M:LETX=A:LETT=0:LETI=0

40 GOSUB 120:LETZ=X+ABS(F)/M

50 IF Z >=B GOTO 115

60 IF Z-X >=E GOTO 90

70 IF T=0 THEN LETW=Z

80 LETX=Z+E:LETY=Z:LETT=1:GOTO 40

90 IF T<>1 THEN 110

100 LETI=I+1:PRINT!2.0!’X’I’=’!F1.9! (Y+W)/2:LETT=0

110 LETX=Z:GOTO 40

115 PRINT ’КІНЕЦЬ ОБЧИСЛЕНЬ’:STOP

120 LETF=X^4-13*X^2+36

130 RETURN:END

Метод ділення відрізку [a, b] надвоє (метод дихотомії) реалізується наступним алгоритмом (для F(a)>0).

1. Знаходимо x=(a+b)/2.

2. Обчислюємо F(x).

3. Якщо F(x)>0, задаємо a=x, інакше b=x.

4. Перевіряємо умову b-a=ε; якщо вона виконується, йдемо до п.1, якщо не виконується, закінчуємо обчислення і рахуємо, що з заданою точністю ε.

Кількість ітерацій при використанні цього методу

значуще, і тому збіжність його повільна. Однак при будь-якій ширині відрізку [a, b] збіжність гарантована. Крім того, простота реалізації методу зменшує кількість допоміжних операцій і частково компенсує збільшення загального часу рахунку через повільну збіжність.

Метод порозрядного зближення для пошуку всіх коренів відрізку [a, b] реалізується наступним алгоритмом.

1. Задаємо крок c=h, x=a, k=0 і знаходимо W=sngF(x).

2. Задаємо значення x=(x+c)і перевіряємо умову (x-c)≥b. Якщо вона виконується, йдемо до п.2, інакше до п.4.

3. Обчислюємо F(x) І перевіряємо умову FW/c>0. Якщо вона виконується, йдемо до п.2, інакше до п.4.

4. Задаємо c=-c/R, де R – показник розрядності (зменшення кроку c), і перевіряємо виконання умови |c|>ε/R, де ε – задана погрішність обчислення кореня. Якщо ця умова виконується, йдемо до п.2, інакше до п.5.

5. Задаємо k=k+1 і виводимо на друк (індикацію) значення k-го кореню x_k=x. Тоді уважаємо c=h, W= -W і йдемо до п.2.

Програма 11

01 PRINT ’РОЗВ’ЯЗАННЯ РІВНЯНЬ F(X)=0 МЕТОДОМ ДИХОТОМІЇ’

05 INPUT ’E, R, I0, D’ E, R, I0, D

10 INPUT ’A, B, H’ A, B, H

20 LETX=(A+B)/2

30 GOSUB 90

40 IF F>0 THEN 60

50 LETB=X: GOTO 70

60 LETA=X

70 IF B-A>H THEN 20

80 PRINT ’КОРІНЬ=’X: STOP

90 LETF=E-X-R*I0*(EXP(D*X)-1)

100 RETURN: END

Програма 12

10 PRINT ’ОБЧИСЛЕННЯ ВСІХ КОРЕНІВ НЕЛІНІЙНОГО РІВНЯННЯ F(X)=0’

20 PRINT ’В ІНТЕРВАЛІ (A,B) МЕТОДОМ ПОРОЗРЯДНОГО НАБЛИЖЕННЯ’

30 INPUT ’ЗАДАЙТЕ ГРАНИЦІ ІНТЕРВАЛУ A, B ’A,B

40 INPUT ’ЗАДАЙТЕ ПОГРІШНІСТЬ ОБЧИСЛЕННЯ КОРЕНІВ E=’E

50 INPUT ’ЗАДАЙТЕ КРОК ПОЧАТКОВОГО ПОШУКУ H=’H

60 LETC=H:LETK=0:LETX=A:GOSUB 120:LETW=SGN(F)

70 LETX=X+C”IF X-C>=B THEN PRINT ’КІНЕЦЬ’:STOP

80 GOSUB 120:IF F*W/C>0 THEN 70

90 LETC=-C/4:IF ABS(C)>E/4 THEN 70

100 LETK=K+1:PRINT!2.0!’X’K!F1.9!’=’X

110 LETC=H:LETW=-W:GOTO 70

120 LETI=.2718*X*EXP(-10*X)+1E-8*(EXP(20*X)-1)

130 LETF=(1-X)/125-I:RETURN:END

Метод хорд (рис. 5.а). При цьому методі кожне значення x_n+1 знаходиться як точка перетину осі абсцис з хордою, яка проведена через точки F(a) та F(b) , при чому одна з цих точок фіксується – та, для якої знаки F(x) та однакові. Якщо нерухомий кінець хорди x=a, то

а якщо нерухомий кінець хорди x=b, то

Якщо

|x_n+1-x_n|>ε,

то в першому випадку вважаємо b=x_n+1, в другому a=x_n+1 і повторюємо обчислення. При використанні методу хорд вважається, що корінь знаходиться на відрізку [a, b].

Метод січних (рис.5.б) реалізується алгоритмом, описаним вище, якщо абсциси a та b взяті з однієї сторони від кореня і не фіксуються.

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

Комбінований метод січних – хорд забезпечує гарантовану збіжність при виборі у межах відрізку [a, b] двох наближень: нульового x₀ та першого x₁. Він реалізується алгоритмом, описаним для методу Ньютона з заміною похідної її наближеним значенням – множник перед F(x_n):

Програма 13.

01 PRINT ‘Рішення рівняння F(x)=0 комбінованим’

02 PRINT ‘Методом перетину-хорд’

05 INPUT ‘E,R,10,,D’E, R,10,D

10 INPUT ‘X0,X1,H’ X0, X1, H

20 LET X=X0: GOSUB 80

30 LET A=F: LET X=X1: GOSUB 80

40 LET B=F: LET Y=X0-A*(X1-X0)/(B-A)

50 LET X0=X1: LET X1=Y

60 IF ABS(X1-X0)>H THEN 20

70 PRINT ‘Корень=’X1: STOP

80 LET F=E-X-R*10*(EXP(D*X)-1)

90 RETURN: END

100 RETURN: END