3_Equations_2

Методы решения нелинейных уравнений
Метод половинного деления
Метод хорд
Метод касательных
Метод секущих
Метод простой итерации
Метод половинного деления
Метод хорд
Метод касательных
Метод секущих
Метод простой итерации

Метод половинного деления (дихотомии)
В качестве первого приближения берем
Если f(x1)=0, то это корень, иначе переход к п.3.
Из двух половинок отрезка выбираем ту, на концах которой функция имеет разные знаки (роль a или b играет точка x1).
Если , то переход к п. 2., иначе закончить вычисления.

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ
0
Если то решение уравнения находится на
(2)

Погрешность половинного деления
На каждом шаге погрешность гарантированно уменьшается ровно вдвое. За n делений отрезок уменьшается в 2n раз. Например, при начальной длине отрезка 1, за 5 делений он уменьшается в 32 раза:

Можно априорно рассчитать по заданной погрешности количество шагов N(ε), необходимых для достижения точности ε:

Скорость сходимости метода половинного деления
В данном методе выполняется условие:
|x*-xi+1|≤ q |x*-xi| при q=½,
т.е. имеет место линейная сходимость.

Особенности метода половинного деления
Самый алгоритмически простой и надежный метод.
Гарантированно сходится и скорость приближения не зависит от гладкости функции.
Обеспечивает двустороннее приближение к корню.
Для увеличения точности приходится резко увеличивать объем вычислений в силу малой скорости сходимости.
+

Реализация метода дихотомии
Результат:
Найден корень x = 3.007, число итераций - 7

Метод хорд
Идея метода основана на том, чтобы использовать не только разность знаков функции на концах отрезка, но и сами значения в этих точках для построения очередного приближения к корню.
Очередным приближением выбирается не середина отрезка [a;b], а точка пересечение с осью ОХ отрезка, проходящего через точки (a, f(a)) и (b,f(b)).

x0=а
b
x1
x2
x3
МЕТОД ХОРД
x
y
0
x4
Уравнение хорды:
(3)

a
b=x0
x1
x2
x3
МЕТОД ХОРД
x
y
0
x4
Уравнение хорды:
(4)

Формулы метода хорд
двигается левый конец интервала
двигается правый конец интервала

Оценка погрешности

Оценка погрешности
Теорема Лагранжа. Пусть функция f определена на некотором промежутке и имеет на нем конечную производную f’. Если две точки x и x0 находятся в данном промежутке, то существует точка ξ между x и x0 такая, что
f(x)-f(x0)=f’(ξ)(x-x0)

f(x)-f(x0)=f’(ξ)(x-x0)
x0
ξ
x
f(x)
Δf
y
∆x

Погрешность метода хорд
Если f’ и f’’ непрерывны, а числа m и M такие, что
тогда погрешность оценивается формулой
(5)

Достижение точности
Для условия достижения заданной точности можно воспользоваться оценкой (5):
Однако, если интервал [a, b] небольшой, то можно предположить, что
Тогда для условия достижения заданной точности можно воспользоваться соотношением:

Особенности метода хорд
Обычно сходиться быстрее, чем метод половинного деления.
Не зависит от вида конкретной функции, хотя она должна быть дифференцируема.
Имеет линейную скорость сходимости.
Обладает односторонней сходимостью.
+

Метод касательных (метод Ньютона)
Основная идея состоит в построении очередного приближения не хордой, а касательной к графику функции y=f(x) в точке (xi, f(xi)).
Выбор начального приближения x0 зависит от вида графика функции на данном отрезке.

0
B0
B1
B2
B3
Метод касательных.
Уравнение касательной:
y
x

Анализ сходимости метода Ньютона
Формула Тейлора с остаточным членом в форме Лагранжа

Пусть x* - точный корень из [a;b], xn ≈ x*. Тогда между xn и x* найдётся точка ξn такая, что
Если xn достаточно близко к x*, то можно отбросить третье слагаемое и получить приближенное равенство:
Отсюда

Оценка погрешности метода касательных
Фактически в окрестности корня на каждой итерации погрешность возводиться в квадрат, т.е. число верных знаков удваивается. Но в эту окрестность еще надо попасть. Если область сходимости мала, то метод чувствителен к начальному приближению.

Достижение точности
Для условия достижения заданной точности ε и прекращения вычислений можно использовать оценку (7):

В этом методе выбор начального приближения может оказаться неудачным, и последовательность приближений не будет сходиться. Пример:
a
x*
x0=b
Y=f(x)
y
x1
x
Условие Фурье:

Особенности метода касательных
Наиболее быстро сходящийся метод (квадратичная скорость сходимости).
Необходимо вычислять в каждой точке приближения производную.
Сходимость метода односторонняя.
Требует хорошего начального приближения в случае малой области сходимости.
+

Недостатки метода Ньютона можно преодолеть следующим образом:
Для выхода в непосредственную близость корня сначала применяют гарантированный медленный метод, а затем переходят на метод Ньютона.
Затруднение с вычислением производной можно избежать, заменив ее конечно-разностным отношением:

Исторический пример использования метода
Эмпирически метод касательных применялся в древности для нахождения квадратного корня (длины гипотенузы).
Пусть f(x)=x2 - a,
тогда решением уравнения f(x)=0 является:

Пример
Составим рекуррентное соотношение:

Пример: a=9

Метод секущих
– это упрощение метода касательных, когда затруднительно найти производную. Заменим в методе касательных производную конечно-разностным отношением:

Особенности метода секущих
Не требует дифференцированной функции.
При его реализации на каждой итерации вычисляется только одно новое значение функции.
Требует два начальных приближения x0 и x1. Обычно это один из концов отрезка и близкая к нему точка.
Метод уступает в скорости сходимости методу касательных (сверхлинейная скорость с α=1.618).
+

Метод простой итерации
Рассмотренные методы решения уравнения f(x)=0 сводились к итерационной процедуре вида
xi+1=φ(xi) (9)
Основная идея метода простой итерации состоит в том, чтобы построить универсальный метод типа (9).

Исходное уравнение f(x)=0 заменяют эквивалентным ему x=φ(x).
После этого выбирается начальное приближение x0, которое подставляют в функцию φ(x):
x1= φ(x0)
x2= φ(x1)
……………
xi+1= φ(xi)
……………

Метод простой итерации.
xi+1= φ(xi)

Метод простой итерации.
xi+1= φ(xi)

Таким образом, получим последовательность x0 ,x1 , x2 ,… , xi ,…
Рассмотрим, в каком случае она сходится.
Условие сходимости:
Модуль φ’(x) в некоторой окрестности корня должен быть меньше 1, чтобы итерационный процесс сходился со скоростью геометрической прогрессии.

Приведение уравнения к итерационному виду
Пример 1.
f(x)=0
x=φ(x)

Приведение уравнения к итерационному виду
Пример 2.
f(x)=0
x=φ(x)

Приведение уравнения к итерационному виду
Способы приведения уравнения могут быть различными, но важно добиться выполнения условия сходимости:
в окрестности корня или на всем отрезке [a;b]. Рассмотрим универсальный способ приведения уравнения к итерационному виду.

В общем случае используется следующий алгоритм:
f(x)=0 умножим на константу λ
λ*f(x)=0 вычтем обе части из х
x - λ*f(x) = x
т.о., φ(x)= x- λ*f(x)
подберем λ т. о., чтобы на [a,b] выполнялось условие сходимости:

Пример.
Пусть
f(x)=x3-x2-1000=0. Это ур-е имеет один корень на [10,11].
Производная
f’(x)=3x2-2x на [10,11] монотонно возрастает:
m1= f’(10)=280
M1= f’(11)=341.
x0=10,
x1=10.3333333,
x3=10.3446913,
x4=10.3446910.

Подбор параметра λ
Пусть на отрезке [a;b] производная функции f(x) ограничена:
0 < m1 ≤ f’(x) ≤ M1.
Положим λ=2/(M1+ m1).
Тогда

Упражнение. На отрезке [1;2] привести к итерационному виду уравнение
x4-2x-3=0.
Производная
f’(x)=4x3-2 на [1;2] монотонно возрастает:
m1= f’(1)=2
M1= f’(2)=30.
λ=2/(M1+ m1)
λ=2/(30+ 2)=1/16
φ(x)= x- λ*f(x)
x = x – (x4-2x-3)/16
ϕ’ = 1 – (2x3-1)/8

Оценка погрешности приближений
Если
то на каждой итерации

Условие достижения заданной точности
Таким образом, если задана точность приближенного корня ε, то итерационный процесс необходимо закончить при выполнении условия

Особенности МПИ
Самый простой в реализации.
Скорость его сходимости зависит от конкретного вида (может быть линейной, может быть выше).
Требует приведения уравнения к итерационному виду, чтобы выполнялось условие сходимости.
+