Численные методы. Лекция 3. Методы решения нелинейных уравнений

1. ЧИСЛЕННЫЕ МЕТОДЫ

Лекция 3: Методы решения
нелинейных уравнений

2. Метод хорд (линейное интерполирование).

Пусть дано уравнение f(x)=0, где f(x) -
непрерывная функция, имеющая в интервале
(a, b) производные первого и второго
порядка. Корень отделен и находится на
отрезке [a, b], т.е. f(a) f(b)<0.
Идея метода заключается в том, что на
достаточно малом промежутке [a, b] дуга
кривой y=f(x) заменяется стягивающей ее
хордой. В качестве приближенного значения
корня принимается точка пересечения хорды
с осью Оx.

3.

1) f (x) f (x) > 0
y
B
a = x0
0
x1
A1
x2
A2
t
b
A0
f >0
x

4.

1) f (x) f (x) > 0
y
A0
A1
A2
t
0
a = x0
x1
x2
b
B
x

5. Вывод формулы метода хорд

• Уравнение хорды A0B: y f a x a
f b f a b a
из уравнения прямой, проходящей через две
y y1
x x1
точки:
y 2 y1 x 2 x1
• Найдем значение x=x1 для которого y=0.
f a b a
f ( x0 )(b x0 )
x1 x0
x1 a
f (b) f ( x0 ) (1)
f b f a или
Это формула метода хорд для первого шага.

6. Вывод формулы метода хорд

• Сейчас корень внутри отрезка [x1,b].
• Далее:
f xn b xn
xn 1 xn
f b f xn (2)
• Здесь В – неподвижный конец хорды.

7.

1) случай, когда f (x) f (x) < 0
y
f >0
A
x2
0
a
t
x1
b=x0
B2
B1
B0
x

8.

1) f (x) f (x) < 0
y
B0
B1
B2
a
t
x2
0
x1
b=x0
f <0
A
x

9. Вывод формулы метода хорд

• Уравнение хорды AB0: y f a x b
f b f a b a
• Найдем точку x1 при y=0.
f b b a
f x1 x1 a (3)
x1 b
; x2 x1
f b f a
f x1 f a
• Итак до (n+1)-го шага: f x x a
n
n
xn 1 xn
f xn f a (4)
• Здесь А-неподвижный конец хорды.

10. Правило выбора формул:

неподвижным концом отрезка
является тот, для которого знак
функции совпадает со знаком
второй производной.
Оценка погрешности метода:
t xn xn xn 1

11. Пример:

Методом хорд уточнить до =0,001
меньший корень уравнения:
x 3x 3 0.
3
2
Корни отделены и меньший
содержится на отрезке
2,75; 2,5

12. Решение:

M 2m
f x 3 x 6 x
2
• Процесс приближения к корню
следует продолжать до тех пор,
пока
не
будет
выполнено
условие:
x x
n
n 1

13. продолжение решения:

• Определим знак второй производной:
f x 6 x 6; f 2,75 0;
f 2,75 f x 0.
• Значит, за неподвижный конец отрезка
нужно принять x 2,75.
• Тогда вычисления ведём по
формулам (3), (4), где a 2,75 и
f a 1,111.

14. продолжение решения:

• Если записать (4) в виде:
f xn xn a
xn 1 xn
f xn f a
,
то сразу же можно будет получить разность
между последними приближениями и
проверять выполнение неравенства
xn 1 xn

15. продолжение решения:

x1 x0 0,001.
x2 x1 0,001.
x3 x2 0,0009 0,001.
• Условие выполнено.
• Ответ:
x3 2,5319 2,532 t

16. Метод Ньютона (метод касательных).

Пусть корень уравнения f(x)=0 отделен на
отрезке [a, b], причем f (x) и f (x)
непрерывны и сохраняют постоянные знаки
на отрезке [a, b].
Геометрический смысл метода Ньютона
состоит в том, что дуга кривой y=f(x)
заменяется касательной к этой кривой.

17.

1) случай, когда . f(a) f(b)<0 и f (x) f (x)>0
y
B0
a
0
t
x2 x1
A
b=x0
x

18. Уравнение касательной в точке B0:

y f b f b x b
полагая y=0, x=x1 получим:
f b
f x1
x1 b
x2 x1
f b
f x1
продолжая этот процесс, получаем
последовательность {xn}, определённую с
помощью рекуррентной формулы:
f xn
xn 1 xn
f xn
(1)

19.

1)случай, когда . f(a) f(b)<0 а f (x) f (x)<0
y
B
a=x0 x2 x3
0
x1
A0
t
b
x

20. Уравнение касательной в точке A0:

y f a f a x a , при y=0, x=x1
f a
x1 a
f a
,
f x1
x 2 x1
f x1
И наконец, формула метода Ньютона:
f xn
xn 1 xn
f xn

21. Теорема о сходимости метода Ньютона:

Пусть x=t - принадлежит отрезку [a, b] и
является корнем уравнения f(x)=0, а
функция f(x) дважды непрерывно
дифференцируема на данном отрезке.
Тогда найдется такая -окрестность точки
x=t, что при любом выборе начального
приближения x0 на отрезке
[t- , t+ ] [a, b]

22. Теорема о сходимости метода Ньютона:

существует бесконечная итерационная
последовательность (1) и эта последовательность сходится к корню t.
Достаточное условие сходимости метода
Ньютона:
f(x) f (x) <[ f (x)]2 .

23. Правило выбора начального приближения:

• за исходную точку (нулевое
приближение) следует
выбирать тот конец отрезка
[a, b], в котором знак функции
совпадает со знаком второй
производной.

24. Критерий окончания итерационного процесса:

при заданной точности >0
вычисления следует вести до тех
пор, пока не окажется выполненным неравенство:
xn – xn-1 < .
Оценка погрешности метода:
t xn
f xn
m
,
где
m min f x
a , b

25. ПРИМЕР 1:

• Найти методом касательных
приближенное значение корня
уравнения
f(x) = x - cosx = 0
на интервале [0,5;1].

26. Решение:

• Рекуррентная формула метода
касательных принимает в данном
случае вид:
xn cos xn
xn 1 xn
1 sin xn

27. продолжение решения:

• Выберем в качестве
нулевого
приближения x0=0,5
и подсчитаем
следующие
приближения.
Результаты
вычислений
приведены в
таблице:
N
xn
0
0,500000000000
1 0,755222417106
2
0,739141666150
3
0,739085133921
4
0,739085133215
5
0,739085133215
После двух шагов мы достигли точности 10-4.

28. ПРИМЕР 2:

Рассмотрим вычисление a как задачу
решения уравнения:
x2 - a = 0 в
области
x>0.
Написать
для
вычисления
корня
уравнения
итерационную
последова-тельность
2
по методу касательных. Вычислить
с
её помощью
.

29. Решение:

Рекуррентная формула метода касательных для уравнения x a принимает вид:
x a 1
a
x n 1 x n
x n ( )
2xn
2
xn *
2
n

30. продолжение решения:

Перейдём к вычислению 2 .
2 1,414214.
Вспомним, что
Выбирая x0=2, делаем несколько
итераций по формуле (*):
x0=2;
x1=1,5;

31. продолжение решения:

1 3 4
x 2 1,416666
2 2 3
1 17 24
x3
1,414216
2 12 17
Третий шаг определяет
ностью:
2 с погреш-
2 x3 0,000002

32. Лабораторная работа: Метод бисекции.

Текст программы:
bis ec f a b
3
f( x) x cos ( x) 1
an a
bn b
k 0
while ( bn an ) 2
xn
an bn
2
fa f( an )
fb f( bn )
fxn f( xn )
bn xn
if fa fxn 0
an xn
otherwis e
k k 1
xn
an bn
2
xn
res
k
res

33. Лабораторная работа: Метод бисекции.

a 0.6
b 0.4
0.4900726384
bisec f a b
30
10
10
0.1
0.018
0.6
f( x)
0.4
0.1
0.108
0.2
0.7
x
0.3

34. Метод Ньютона:

3
f( x) x cos ( x) 1
mN f x0
mN_step ( f x) x
xold x0
k 1
xnew mN_step ( f xold )
while
xnew xold
xold xnew
xnew mN_step ( f xold )
k k 1
xnew
res
k 1
res
f( x)
d
f( x)
dx

35. Метод Ньютона:

10
10
x0 0.4
0.4900726385
mN f x0
5
x0 0.6
0.4900726385
mN f x0
5