ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2025
Просмотров: 1077
Скачиваний: 1
13 |
|||
y |
y |
||
y=x |
y=ϕ(x) |
y=x |
|
y=ϕ(x)
α x1 ξ x2 |
x0=β |
x |
x3 x1 ξ x0 x2 |
x |
а |
б |
Рис. 4. Геометрическая интерпретация итерационного процесса
для уравнения x = ϕ( x ) при ϕ′( x )< 0: а) – для ϕ ′( x ) < 1; б) – для ϕ′( x ) > 1.
Уравнение (1) можно записать в виде равенства (8), выбирая различным образом функцию y = ϕ( x ) . Для метода итераций выгодно то представление (8),
при котором выполнено неравенство (11), причем, чем меньше q, тем быстрее, вообще говоря, последовательные приближения сходятся к корню (это следует из оценки приближения (12)).
Рассмотрим достаточно общий прием приведения уравнения (1) к виду (8), для которого обеспечено выполнение неравенства (11). Пусть искомый корень ξ уравнения лежит на отрезке [α; β], причем, f '(x)>0 и
0 < m ≤ f '(x) ≤ M |
(13) |
при α ≤ x ≤ β. В частности, за m можно взять наименьшее значение производной f '(x) на отрезке [α; β], а за M – наибольшее значение f '(x) на отрезке [α; β]. Если производная f '(x) на отрезке [α; β] отрицательна, то вместо уравнения f(x) = 0 рассматриваем уравнение –f(x) = 0. Заменим уравнение (1) эквивалентным ему уравнением
x = x – λf(x), λ > 0. |
(14) |
Правая часть в полученном уравнении в соответствии с (8) есть функция
ϕ(x)= x – λf(x).
Тогда
ϕ '(x) = 1 – λf '(x).
Подберем параметр λ таким образом, чтобы на интервале [α; β] выполнялось неравенство (11), т.е.
0 ≤ ϕ '(x) = 1 – λf '(x) ≤ q < 1.
Отсюда и на основании неравенства (13) получаем
14
0 ≤ 1 – λM ≤ 1 – λm ≤ q < 1.
Тогда, выбрав
λ = |
1 |
, |
(15) |
|
M |
||||
получим
q = 1 – Mm < 1,
и неравенство (11) выполнено.
Замечания:
1. За число q в теореме 3 можно принять наименьшее значение модуля производной |ϕ ' (x)| при a < x < b.
2. В случае ϕ '(x) < 0 и |ϕ '(x)| < 1 имеет место неравенство
ξ − xn |
≤ |
xn − xn-1 |
. |
(16) |
||||||||||||||||||||
3. В общем случае, из выполнения неравенства |xn – xn–1| < ε не следует вы- |
||||||||||||||||||||||||
полнение неравенства |ξ – xn| < ε (см. рис.5). |
||||||||||||||||||||||||
y |
||||||||||||||||||||||||
y=x |
||||||||||||||||||||||||
y=ϕ(x) |
||||||||||||||||||||||||
çξ-xnç |
||||||||||||||||||||||||
xn |
xn-1 |
|||||||||||||||||||||||
x |
ε |
x |
||||||||||||||||||||||
Рис. 5. Пример, что при |
xn |
- xn-1 |
< ε имеет место неравенство |
ξ - xn |
> ε . |
|||||||||||||||||||
4. Упрощенная оценка (16) может быть использована для случая |
ϕ '(x) < 0 и |
|||||||||||||||||||||||
|ϕ '(x)| < 1. Если же ϕ '(x) > 0 и |
ϕ '(x) < 1, то, вообще говоря, оценку (16) исполь- |
|||||||||||||||||||||||
зовать нельзя. Но учитывая, что в этом случае последовательные приближения xn = ϕ(xn–1), n = 1, 2, …, x0 [α; β]
сходится к корню ξ монотонно, можно организовать сужение интервала [α; β], последовательно получая приближения корня с недостатком и избытком. Тогда возможно применение оценки приближения (16).
15
1.2.4.1 Алгоритм метода итераций
Вычислительная схема решений имеет вид
xi = x0, x0 [α; β] xi+1 = ϕ(xi), i = 1, 2, …
и сводится к организации циклического процесса с неизвестным числом повторений до выполнения заданного уровня точности, который может быть оценен неравенством (12) или применением упрощенной оценки (16).
Выполним уточнение корня на отрезке [α; β], применив следующий алгоритм.
1.Установить значения α, β, ε – границы отрезка отделения корня и принятую точность приближения.
2.Определить точку (η, M = max| f ' ( x )|).
x [α ; β ]
3.Установить начальное значение x0 [α; β].
4.Вычислить λ = sgn f '(η) M2 .
5.Начать цикл уточнения корня.
5.1.Вычислить очередное приближение x1 = x0 – λf(x0).
5.2.Вычислить d = |x1 – x0|.
5.3.Принять x0 = x1.
6.Конец цикла, если d < ε .
7.Вывод результата x1.
8.Конец алгоритма.
Замечание. Выполнение п.4 алгоритма обеспечивает удовлетворение требований ϕ '(x) < 0 и |ϕ '(x)| < 1, при которых может быть применена упрощенная оценка (16).
1.2.5 Метод Ньютона
Пусть на отрезке [α; β] отделен корень уравнения (1), функция f(x) дважды дифференцируема, а f ′(x) и f ′′(x) сохраняют постоянные знаки на указанном интервале.
В методе Ньютона точное значение ξ корня уравнения (1) заменяется приближенным значением x [α; β], где x – абсцисса пересечения касательной,
проведенной к кривой y = f(x) в точке С [α; β]. Уравнение этой касательной |
|||
y – f(С) = f ′(С)(x – С). |
(17) |
||
Так как при x = x y = 0, то из (17) получаем |
|||
x = С – |
f ( C ) |
. |
(18) |
16
Остается решить вопрос о выборе точки С таким образом, чтобы x [a; b]. Выбор точки С определяется четырьмя случаями, изображенными на рис. 6.
y
f(x)
α
0 |
ξ x С=β x |
1) f ′(x)>0, f ′′(x)>0, C=β, f(C)>0
y
f(x)
x C=β
0 |
α |
ξ |
x |
2) f ′(x)<0, f ′′(x)<0, C=β, f(C)<0
y |
y |
f(x)
α |
x |
α |
ξ |
β |
||||
0 |
ξ |
β |
x |
0 |
x |
x |
||
3) f ′(x)>0, f ′′(x)<0, C=α, f(C)<0
Рис. 6
4) f ′(x)<0, f ′′(x)>0, C=α, f(C)>0
Обычно принимают C = a или C = b, смотря по тому, в какой из этих точек знак функции совпадает со знаком второй производной, т.е. выбирают так, чтобы произведение sgn f(C) × sgn f ¢¢ (C) было положительно. Можно показать, что в этом случае a < x < b. Полученное значение x можно использовать для дальнейшего уточнения корня, беря интервал [a; x ] (случаи 1 – 2) или интервал [ x ; b] (случаи
2 – 4).
Геометрический смысл метода Ньютона состоит в замене дуги y = f(x) касательной, проведенной к одной из крайних точек так, что имеет место итерационная формула
xk = xk–1 – |
f ( xk −1 ) |
(k = 1, 2, …), |
f '( xk −1 ) |
основанная на формуле (18).
17
Для оценки погрешности в методе Ньютона можно воспользоваться форму-
лой
|xk – ζ| ≤ |
M |
2 |
||
|xk – xk–1| , |
||||
2m |
||||
где m = min |
|f ′(x)|, M = |
max |f ′′(x)|. |
||
x [α; |
β] |
x [α;β] |
||
1.2.5.1 Алгоритм метода Ньютона
1.Установить значения α, β, ε – границы отрезка отделения корня и принятую точность приближения.
2.Определить точку (η, M = max | f '' (x) | ).
x [α; β]
3. Вычислить m = min |f '(x)|.
x [α; β]
4. Установить начальное приближение x0 [α; β]:
если sgn f ''(η) = sgn f(α), то x0 = α,
иначе x0 = β.
5.Начать цикл уточнения корня.
5.1.Вычислить очередное приближение x1 = x0 –
5.2.Вычислить d = (x1 – x0)2.
5.3.Принять x0 = x1.
6.Конец цикла, если d < 2Mm ε .
7.Вывод результата x1.
8.Конец алгоритма.
f ( x0 ) . f '( x0 )
1.2.6 Метод хорд
Пусть на отрезке [α; β] отделен корень уравнения (1), функция f(x) дважды дифференцируема, а f ′(x) и f ′′(x) сохраняют постоянные знаки на указанном интервале.
Метод заключается в том, что на интервале [a; b] отделения корня ξ уравнения (1) дуга кривой y = f(x) заменяется стягивающей ее хордой и в качестве приближенного значения корня x принимается точка пересечения хорды с осью абсцисс (рис. 7).