Розв"язування нелінійних рівнянь (реферат)

Реферат на тему:

Розв’язування нелінійних рівнянь

1. Метод ділення проміжку навпіл (метод дихотомії)

Нехай $$fC[a,b],f(a)f(b)<0$$ і відомо, що рівняння (1) має єдиний корінь $$x_{}[a,b]$$. Покладемо a0=a, b0=b, x0=(a0+b0)/2. Якщо $$f(x_0)=0$$, то $$x_{}=x_0$$. Якщо $$f(x_0)=0$$, то покладемо.

$$\begin{array}{c}{x}_n,\text{якщо}\text{sign}f(a_n)=\text{sign}f(x_n),\\ a_n,\text{якщо}\text{sign}f(a_n)/=\text{sign}f(x_n),\\ \\ a_{n+1}=\begin{array}{c}\{\end{array}\\ \end{array}$$.

$$\begin{array}{c}{x}_n,\text{якщо}\text{sign}f(b_n)=\text{sign}f(x_n),\\ b_n,\text{якщо}\text{sign}f(b_n)/=\text{sign}f(x_n),\\ \\ b_{n+1}=\begin{array}{c}\{\end{array}\\ \end{array}$$.

$$x_{n+1}=\frac{a_{k+1}+b_{k+1}}{2},n=\mathrm{0,1,2,}\text{.}\text{.}\text{.},$$.

і обчислимо $$f(x_{n+1})$$. Якщо $$f(x_{n+1})=0$$, то ітераційний процес зупинимо і будемо вважати, що $$x_{}{x}_{n+1}$$. Якщо $$f(x_{n+1})/=0$$, то повторюємо розрахунки за формулами (2)-(4).

З формул (2), (3) видно, що $$\text{sign}f(a_{n+1})=\text{sign}f(a_n)$$ і $$\text{sign}f(b_{n+1})=\text{sign}f(b_n)$$. Тому $$f(a_{n+1})f(b_{n+1})<0$$, а отже шуканий корінь $$x_{}$$ знаходиться на проміжку $$[a_{n+1},b_{n+1}]$$. При цьому має місце оцінка збіжності.

$$|x_n-x_{}|<=\frac{b-a}{2^{n+1}}$$

. (5).

.

Звідси випливає, що кількість ітерацій. які необхідно провести для знаходження наближеного кореня рівняння (1) з заданою точністю адовольняє співвідношенню.

$$n>=\left[{\text{log}}_2\frac{b-a}{}\right]$$

. (6).

.

де [c] іла частина числа c.

Серед переваг даного методу слід відзначити простоту реалізації та надійність. Послідовність {xn} збігається до кореня $$x_{}$$ для довільних неперервних функцій f (x). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.

2. Метод простої ітерації

Метод простої ітерації застосовується до розв’язування нелінійного рівняння виду.

$$x=(x)$$

. (7).

.

Перейти від рівняння (1) до рівняння (7) можна багатьма способами, наприклад, вибравши.

$$(x)=x+(x)f(x)$$

(8).

.

де $$(x)$$ овільна знакостала неперервна функція.

Вибравши нульове наближення x0, наступні наближення знаходяться за формулою.

$$x_{n+1}=(x_n),n=\mathrm{0,1,2,}\text{.}\text{.}\text{.}$$

. (9).

.

Наведемо достатні умови збіжності методу простої ітерації.

Теорема 1. Нехай для вибраного початкового наближення x0 на проміжку.

$$S=\left\{x\mathrm{:}|x-x_0|<=\right\}$$ (10).

функція задовольняє умові Ліпшиця.

$$|(x^{\text{'}})-(x^{\text{'}\text{'}})|<=q|x^{\text{'}}-x^{\text{'}\text{'}}|,x^{\text{'}},x^{\text{'}\text{'}}S$$ (11).

де 0<q<1, і виконується нерівність.

$$|(x_0)-x_0|<=(1-q)$$

. (12).

.

Тоді рівняння (7) має на проміжку S єдиний корінь $$x_{}$$, до якого збігається послідовність (9), причому швидкість збіжності визначається нерівністю.

$$|x_n-x_{}|<=\frac{q^n}{1-q}|(x_0)-x_0|$$

. (13).

.

Зауваження: якщо функція має на проміжку S неперервну похідну $${}^{\text{'}}(x)$$, яка задовольняє умові.

$$|{}^{\text{'}}(x)|<=q<1$$

(14).

.

то функція буде задовольняти умові (11) теореми 1.

З (13) можна отримати оцінку кількості ітерацій. які потрібно провести для знаходження розв’язку задачі (7) з наперед заданою точністю p>

$$n>=\left[\frac{\text{ln}\frac{|(x_0)-x_0|}{(1-q)}}{\text{ln}(1/q)}\right]+1$$

. (15).

.

Наведемо ще одну оцінку. що характеризує збіжність методу простої ітерації:

$$|x_n-x_{}|<=\frac{q}{1-q}|x_n-x_{n-1}|$$

. (16).

.

3. Метод релаксації

Для збіжності ітераційного процесу (9) суттєве значення має вибір функції. Зокрема, якщо в (8) вибрати $$(x)==\text{const}$$, то отримаємо метод релаксації.

$$x_{n+1}=x_n+\mathit{}(x_n),n=\mathrm{0,1,2,}\text{.}\text{.}\text{.}$$

(17).

.

який збігається при.

$$-2<f^{\text{'}}(x)<0$$

. (18).

.

Якщо в деякому околі кореня виконуються умови.

$$f^{\text{'}}(x)<\mathrm{0,}0<m_1<|f^{\text{'}}(x)|<M_1$$

(19).

.

то метод релаксації збігаються при $$(\mathrm{0,2}/M_1)$$. Збіжність буде найкращою при.

$$={}_{\text{опт}}=2/(m_1+M_1)$$

. (20).

.

При такому виборі ля похибки $$z_n=x_n-x_{}$$ буде мати місце оцінка.

$$|z_n|<=q^n|z_0|,n=\mathrm{0,1,2,}\text{.}\text{.}\text{.}$$

(21).

.

де $$q=(M_1-m_1)/(M_1+m_1)$$ .

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

$$n>=\left[\frac{\text{ln}\left(|z_0|/\right)}{\text{ln}(1/q)}\right]+1$$

. (22).

.

Зауваження: якщо виконується умова $$f^{\text{'}}(x)>0$$, то ітераційний метод (17) потрібно записати у вигляді.

$$x_{n+1}=x_n-\mathit{}(x_n)$$

.

.

4. Метод Ньютона

Метод Ньютона застосовується до розв’язування задачі (1), де f (x) є неперервно-диференційованою функцією. На початку обчислень вибирається початкове наближення x0. Наступні наближення обчислюються за формулою.

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\text{'}}(x_n)},n=\mathrm{0,1,2,}\text{.}\text{.}\text{.},f^{\text{'}}(x_n)/=0$$

. (23).

.

З геометричної точки зору xn+1 є значенням абсциси точки перетину дотичної до кривої y=f (x) в точці (xn, f (xn)) з віссю абсцис. Тому метод Ньютона називають також методом дотичних.

Теорема 2. Якщо $$f(x)C^2[a,b],f(a)f(b)<\mathrm{0,}аf^{\text{'}\text{'}}(x)$$ не змінює знака на [a, b], то виходячи з початкового наближення $$x_0[a,b]$$, що задовольняє умові $$f(x_0)f^{\text{'}\text{'}}(x_0)>0$$, можна обчислити методом Ньютона єдиний корінь $$x_{}$$ рівняння (1) з будь-якою степінню точності.

Теорема 3. Нехай $$x_{}$$ ростий дійсний корінь рівняння (1) і $$f(x)C^2(S)$$, де $$S=\left\{x\mathrm{:}|x-x_{}|<=\right\}$$ ,.

$$0<m_1=\underset{xS}{\text{min}}|f^{\text{'}}(x)|,M_2=\underset{xS}{\text{max}}|f^{\text{'}\text{'}}(x)|$$

(24).

.

причому.

$$q=\frac{M_2|x_0-x_{}|}{2m_1}<1$$

. (25).

.

Тоді для $$x_{0}S$$ метод Ньютона збігається, причому для похибки справедлива оцінка.

$$|x_n-x_{}|<=q^{2^n-1}|x_0-x_{}|$$

. (26).

.

З оцінки (26) видно, що метод Ньютона має квадратичну збіжність, тобто похибка на (n+1)-й ітерації пропорційна квадрату похибки на n-й ітерації.

Модифікований метод Ньютона.

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\text{'}}(x_0)},n=\mathrm{0,1,2,}\text{.}\text{.}\text{.}$$ (27).

дозволяє не обчислювати похідну $$f^{\text{'}}(x)$$ на кожній ітерації, а отже і позбутися можливого ділення на нуль. Однак цей алгоритм має тільки лінійну збіжність.

Кількість ітерацій, які потрібно провести для знаходження розв’язку задачі (1) з точністю адовольняє нерівності.

$$n>=\left[{\text{log}}_2\left(\frac{\text{ln}(|x_0-x_{}|/)}{\text{ln}(1/q)}\right)+1\right]+1$$

. (28).

.

Приклад 1. Розв’язати рівняння.

$$x+\text{sin}x-1=0$$ (29).

методом ділення проміжку навпіл з точністю /p>

Розв’язання. Спочатку знайдемо проміжок, де рівняння має єдиний корінь. Оскільки похідна функції $$f(x)=x+\text{sin}x-1$$ не змінює знак, то корінь у рівнянні (29) буде один. Легко бачити, що f (0)=t-0, а $$f\left(\frac{}{2}\right)=\frac{}{2}>0$$. Отже корінь належить проміжку $$\left[\mathrm{0,}\frac{}{2}\right]$$. Виберемо $$a_0=\mathrm{0,}{b}_0=\frac{}{2}$$. Згідно з формулою (6), отримаємо, що для знаходження кореня з точністю 10необхідно провести 13 інтеграцій. Відповідні значення xn наведені в табл. 1.

Табл.1.

n.	xn.	f (xn).
	78 5398E+00.	49 2505E+00.
	39 2699E+00.	22 4617E+00.
	58 9049E+00.	14 4619E+00.
	49 0874E+00.	37 7294E-01.
	53 9961E+00.	54 0639E-01.
	51 5418E+00.	83 1580E-02.
	50 3146E+00.	14 6705E-01.
	50 9282E+00.	31 6819E-02.
	51 2350E+00.	25 7611E-02.
	51 0816E+00.	29 5467E-03.
	51 1583E+00.	11 4046E-02.
	51 1199E+00.	42 2535E-03.
	51 1007E+00.	63 5430E-04.
	51 0911E+00.	11 6016E-03.

Приклад 2. Знайти додатні корені рівняння.

x3 (30).

методом простої ітерації з точністю /p>

Розв’язання. Графічне дослідження рівняння (30) показує, що існує єдиний дійсний додатній корінь цього рівняння і він належить проміжку [1,2]. Оскільки на цьому проміжку $$x/=0$$, то рівняння (30) можна подати у вигляді.

$$x=\sqrt{\frac{1}{x}+1}$$

. (31).

.

Позначимо $$(x)={\left(\frac{1}{x}+1\right)}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}$$. Перевіримо виконання умов теореми про збіжність методу простої ітерації. Виберемо x0=1,5, тоді 5. Розглянемо.

$${}^{\text{'}}(x)=-\frac{1}{2\sqrt{x^3+x^4}}-\underset{1<=x<=2}{\text{max}}|{}^{\text{'}}(x)|=\frac{1}{2\sqrt{2}}$$

.

.

тобто $$q=\frac{1}{2\sqrt{2}}$$ .

тоді $$|(x_0)-x_0|=|\sqrt{\frac{2}{3}+1}-\mathrm{1,5}|=\mathrm{0,}\text{205},(1-q)=\mathrm{0,5}\left(1-\frac{1}{2\sqrt{2}}\right)\mathrm{0,}\text{3232}$$ ,.

а отже умова (12) виконується. З формули (15) маємо, що кількість ітерацій, які необхідно провести для знаходження кореня з точністю повинна задовольняти умові $$n>=8$$. Відповідні значення xn та xn (xn) наведені в табл.2.

Табл.2.

n.	xn.	xn (xn).
	15 0000E+01.	20 9006E+00.
	12 9099E+01.	41 1454E-01.
	13 3214E+01.	90 1020E-02.
	13 2313E+01.	19 3024E-02.
	13 2506E+01.	41 5444E-03.
	13 2464E+01.	89 2878E-04.
	13 2473E+01.	19 1927E-04.
	13 2471E+01.	41 7233E-05.
	13 2472E+01.	95 3674E-06.

Виходячи з нерівності (16) і отриманих результатів видно, що для досягнення заданої точності достатньо було провести 5 ітерацій (n=5). Взагалі слід відзначити, що апостеріорна оцінка (16) є більш точною і її використання може заощадити деяку кількість обчислень.

Приклад 3. Методом релаксації знайти найменший за модулем від'ємний корінь рівняння.

x3 (32).

з точністю /p>

Розв’язання. Спочатку виділимо корені рівняння (32) користуючись наступною таблицею Табл.3.

x.	p>	p>	p>	p>
signf (x).	>	>			>

З даної таблиці видно, що рівняння має три корені розташовані на проміжках [ [], [0−1]. Будемо знаходити корінь на проміжку []. Обчисливши значення f ()=75 можна уточнити проміжок існування кореня [].

Позначимо f (x)=x3Тоді $$f^{\text{'}}(x)=3x^2+6x<\mathrm{0,}x[-1--\mathrm{0,5}]$$ і є монотонно зростаючою функцією на [] (оскільки $$f^{\text{'}\text{'}}(x)=6x+6>=0$$).

Тому $$m_1=\underset{x[-1--\mathrm{0,5}]}{\text{min}}|f^{\text{'}}(x)|=|f^{\text{'}}(-\mathrm{0,5})|=\mathrm{2,}\text{25}$$ ,.

$$M_1=\underset{x[-1--\mathrm{0,5}]}{\text{max}}|f^{\text{'}}(x)|=|f^{\text{'}}(-1)|=3$$

.

.

Тоді, відповідно до формул (20) і (21), будемо мати вигляд.

$$x_{n+1}=x_n+{}_{\text{опт}}(x_n^3+3x_n^2-1)$$

. (33).

.

Вибравши за початкове наближення точку x0= будемо мати оцінку $$|z_0|<=\mathrm{0,5}$$, а кількість ітерацій, які потрібно провести для знаходження розв’язку з точністю буде дорівнювати 5 (див. (22)). В табл. 4 наведені відповідні дані ітераційної послідовності:

Табл.4.

n.	xn.	f (xn).
	50 0000E+00.	14 2857E+00.
	64 2857E+00.	98 5700E-02.
	65 2714E+00.	10 5500E-04.
	65 2704E+00.	59 6046E-07.
	65 2704E+00.	00E+00.
	65 2704E+00.	00E+00.

Із наведених даних видно, що необхідна точність досягається раніше 5-ї ітерації. Це досить характерно для апріорних оцінок типу (22).

Приклад 4. Методом Ньютона знайти найменший додатній корінь рівняння.

x3+3×2 (34).

з точністю /p>

Розв’язання. З табл. 3 видно, що рівняння (34) має єдиний додатній корінь, що належить проміжку [0−1]. обчислимо f (0,5)=25. Тепер будемо шукати корінь на проміжку [0,5−1]. Нехай f (x)=x3+3×2Тоді $$f^{\text{'}}(x)=3x^2+6x>\mathrm{0,}{f}^{\text{'}\text{'}}(x)=6x+6>\mathrm{0,}x[\mathrm{0,5}-1]$$ .

$$m_1=\underset{x[\mathrm{0,5}-1]}{\text{min}}|f^{\text{'}}(x)|=|f^{\text{'}}(\mathrm{0,5})|=\mathrm{3,}\text{75}$$

.

.

$$M_2=\underset{x[-1--\mathrm{0,5}]}{\text{max}}|f^{\text{'}\text{'}}(x)|=|f^{\text{'}\text{'}}(1)|=\text{12}$$

.

.

Виберемо x0=1, тоді $$|x_0-x_{}|<=\mathrm{0,5}$$. З формули (25) маємо.

$$q=\frac{\text{12}\mathrm{0,5}}{2\mathrm{3,}\text{75}}=\mathrm{0,8}<1$$

.

.

Тобто всі умови теореми про збіжність методу Ньютона виконані. З формули (28) маємо, що для досягнення заданої точності достатньо провести 7 ітерацій. Відповідні обчислення наведені в табл. 5.

Табл.5.

n.	xn.	f (xn).
	100 0000E+01.	300 0000E+01.
	666 6667E+00.	629 6297E+00.
	548 6111E+00.	680 4019E-01.
	532 3902E+00.	121 8202E-02.
	532 0890E+00.	439 5228E-06.
	532 0889E+00.	423 0802E-07.
	532 0889E+00.	423 0802E-07.
	532 0889E+00.	423 0802E-07.

Задачі

Знайти одним з ітераційних методів дійсні корені рівнянь з точністю наприклад.

1. 1) $$x^3-5x^2+4x+\mathrm{0,}\text{092}=0$$.

2. 2) $$x^3-4x^2-7x+\text{13}=0$$.

3. 3) $$x^4+x^3-6x^2+\text{20}x-\text{16}=0$$.

4. 4) $$x^3+\text{sin}x-\text{12}x+1=0$$.

5. 5) $$x^3-\text{10}{x}^2+\text{44}x+\text{29}=0$$.

6. 6) $$x+\text{sin}x-\text{12}x=\mathrm{0,}\text{25}$$.

7. 7) $$3x+\text{cos}x+1=0$$.

8. 8) $$x^3-3x^2-\text{17}x+\text{22}=0$$.

9. 9) $$x^4-2x^3-\mathrm{3,}\text{74}{x}^3+\mathrm{8,}\text{18}x-\mathrm{3,}\text{48}=0$$.

10. 10) $$x^2+4\text{sin}x-1=0$$.

11. 11) $$x^3+4\text{sin}x=0$$.

12. 12) $$x^4-\text{10}{x}^3+\text{48},\text{16}{x}^2+\text{108},\text{08}x+\text{70},\text{76}=0$$.

13. 13) $$x^4-3x^3+\text{20}{x}^2+\text{44}x+\text{54}=0$$.

14. 14) $$x^3-3x^2-\text{14}x-8=0$$.

15. 15) $$x^3-x-1=0$$.

16. 16) $$3x-\text{cos}x-1=0$$.

17. 17) $$3x^2-{\text{cos}}^2\mathit{}=0$$.

18. 18) $$x^2+4\text{sin}x=0$$.

19. 19) $$(x-1{)}^3+\mathrm{0,5}{e}^x=0$$.

20. 20) $$x^3+4x-6=0$$.

21. 21) $$x^3-2x^2+x+1=0$$.

22. 22) $$x^2\text{lg}x-1=0$$.

23. 23) $$x^3+6x^2+9x+2=0$$.

24. 24) $$\text{sh}x-\text{12}\text{th}x-\mathrm{0,}\text{311}=0$$.

25. 25) $$e^x-2(x-1{)}^2=0$$.

26. 26) $$e^{-x}+x^2-2=0$$.

27. 27) $$x^4+4x-2=0$$.

28. 28) $$x^4+2x-1=0$$.

29. 29) $$x^3-x^2+x-3=0$$.

30. 30) $$x^5+x-3=0$$.

31. 31) $$x^7+x+4=0$$.

32. 32) $$2^x+x^2-\mathrm{1,}\text{15}=0$$.

33. 33) $$3^{-x}-x^2+1=0$$.

34. 34) $$x^4-2x^3+x^2-2x+1=0$$.

35. 35) $$x^5-5x+2=0$$.

36. 36) $$x^7+6x-5=0$$.

37. 37) $$x^4+2x-2=0$$.

38. 38) $$(x-1{)}^2-\text{sin}2x=0$$.

39. 39) $$x^4+2x^2-6x+2=0$$.

40. 40) $$x^5-3x^2+1=0$$.

41. 41) $$5x^3+2x^2-\text{15}x-6=0$$.

42. 42) $$x^6-3x^2+x-1=0$$.

43. 43) $$(x-1{)}^2-\mathrm{0,5}{e}^x=0$$.

44. 44) $$3x^4+4x^3-\text{12}{x}^2-5=0$$.

45. 45) $$x^2\text{cos}2x=1$$.

46. 46) $$x^2-3+{\mathrm{0,5}}^x=0$$.

47. 47) $$x^2-\text{10}\text{sin}x=0$$.