ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.07.2025
Просмотров: 224
Скачиваний: 0
7
Замечания:
1.В частности, в неравенстве (2) за m1 можно взять наименьшее значение | f ¢(x)| при a < x < b.
2.Оценка (2) значительно завышена. Каждый из ниже рассматриваемых методов уточнения приближенного корня имеет свою оригинальную оценку.
3.Если e>0 – погрешность приближенного корня и |f( x )|< e, то не следует считать, что x является хорошим приближенным точного корня x, и, наоборот, если |f( x )|>e – полагать, что x есть грубое значение точного корня x. Более того, если уравнение f(x) = 0 умножить на произвольное число N ¹ 0, то получается равносильное уравнение Nf(x) = 0, причем число |Nf(x)| можно сделать сколь угодно большим или сколь угодно малым за счет выбора множителя N. На рис. 2 демонстрируется это утверждение.
y y
e f () e
x x
xx
x
x
|f( x )| >e и |x – x | < e |
|f( x )| < e и |x – x | >e |
Рис. 2
1.2.3 Метод половинного деления
Для нахождения корня уравнения (1), принадлежащего отрезку [a; b], делим этот отрезок пополам. Если
æ |
a + |
b ö |
= 0, |
fç |
2 |
÷ |
|
è |
ø |
то по определению
8 |
|||
æ |
a + |
b ö |
|
x = ç |
2 |
÷ |
|
является корнем уравнения (1). Если |
è |
ø |
|
a + |
b ö |
||
æ |
¹ 0, |
||
fç |
2 |
÷ |
|
è |
ø |
||
то выбираем ту из половин |
|||||||
é |
a; |
a + |
bù |
é |
a + b |
ù |
, |
ê |
2 |
ú |
или ê |
2 |
; bú |
||
ë |
û |
ë |
û |
исходного отрезка, на концах которых функция f(x) имеет противоположные знаки. Новый суженный отрезок [a1; b1] снова делим пополам и проводим то же рассмотрение. В результате получаем на каком-то этапе или точный корень x уравнения (1) или бесконечную последовательность вложенных друг в друга отрезков
[a1; b1], [a2; b2], ..., [an; bn], ...
таких, что
sgn f(an)× sgn f(bn) < 0
и |
1 |
||||
bn – an = |
(b – a). |
(4) |
|||
2n |
|||||
Число x = liman |
= limbn |
является корнем уравнения (1). |
|||
n→ ∞ |
n→ ∞ |
||||
Оценку погрешности на n-м шаге вычисления можно получить из следующих рассуждений: так как и точный корень x и срединная точка xn лежит на интервале [an; bn], то расстояние между ними не может быть больше половины длины этого интервала. Поэтому
|x – xn| £ |
bn − an |
для всех n. |
|
2 |
|||
Объединив последний результат с результатом (4), получим
|x – xn| £ |
b − a |
для всех n. |
(5) |
2n+ 1 |
Достоинством метода деления пополам является то, что формула (5) дает предопределенную оценку точности вычисляемого решения. Например, если начальная длина интервала изоляции корня равна b – a = 2 и число повторяемых делений пополам равно 31, то в силу (5) ошибка ограничена значением
|e31| = 2232 = 2131
Можно показать, что n повторяемых делений пополам, необходимых для гарантии того, что n-я срединная точка xn является приближением к нулю функции и ошибка приближения меньше, чем наперед заданное значение e, равно
n = |
é |
ln( b - |
a ) - ln( e |
)ù |
, |
(6) |
ê |
ln( 2 ) |
ú |
||||
ë |
û |
9
где [ ] – операция взятия целой части числа.
1.2.3.1Алгоритм метода половинного деления
1.Ввести исходные данные: a, b – границы интервала изоляции корня уравнения (1); e – погрешность приближенного корня, . e >0; b > a.
2.Выполнить проверку применимости метода: если sgn f(a)×sgn f(b) > 0, то метод не применим; конец вычислений. Иначе выполнить 3.
3.Выполнить цикл пока b – a > e, т. е. длина отрезка изоляции корня больше
заданной точности e.
3.1. Вычислить x = (a + b)/2; x – срединная точка интервала [a;b] есть при-
ближение нуля f(x).
3.2. Если sgn f(x) = 0, то получено решение; выполнить выход из цикла.
Иначе |
3.3. Если sgn f(x)= sgnf(a), то |
принимаем a = x |
иначе принимаем b = x. |
||
4. |
Конец цикла. |
|
5. |
Вывод x – приближенного значения корня. |
|
6. |
Конец алгоритма. |
|
1.2.4 Метод итераций |
|
Заменим уравнение (1) равносильным уравнением |
|
x = j(x). |
(8) |
Если любая точка x0 интервала [a; b] изоляции корня есть приближение нуля функции f(x), то следующее приближение получается так:
x1 = j(x0).
Подставляя теперь в правую часть последнего равенства вместо x0 число x1, получим новое число
x2 = j(x1).
Повторяя этот процесс, будем иметь последовательность чисел xn = j(xn–1) n = 1, 2, …
Если эта последовательность сходящаяся, т.е.
lim xn = ξ ,
n→ ∞
то, переходя к пределу в равенстве (9) и предполагая функцию ной, найдем:
nlim→ ∞ xn = j( nlim→ ∞ xn–1).
В силу (10) получаем
x = j(x),
(9)
(10)
ϕ (x) непрерыв-
10
т.е. в пределе значения аргумента и функции совпадают. Таким образом, предел ξ является корнем уравнения (1) и может быть вычислен по формуле (9) с любой степенью точности.
Достаточные условия сходимости итерационного процесса дает теорема 3.
Теорема 3. Пусть функция ϕ(x) определена и дифференцируема на отрезке [a; b], причем все ее значения ϕ(x) [a; b]. Тогда, если существует правильная дробь q такая, что
при a < x < b, то: |
|ϕ ' (x) | ≤ q < 1 |
(11) |
||||||||||||||||
1) процесс итерации |
(9) сходится независимо |
от начального значения |
||||||||||||||||
x0 [a; b]; |
ξ = lim |
|||||||||||||||||
2) предельное значение |
xn |
является единственным корнем уравне- |
||||||||||||||||
ния (1) на отрезке [a; b]. |
n→ ∞ |
|||||||||||||||||
Для оценки приближения используется формула |
||||||||||||||||||
ξ − xn |
≤ |
qn |
x1 − x0 |
. |
(12) |
|||||||||||||
1 − |
q |
|||||||||||||||||
Если f(x) = x – ϕ(x), то оценку приближения можно выполнить по формуле |
||||||||||||||||||
ξ − xn |
≤ |
q |
xn − xn-1 |
, |
||||||||||||||
1 |
1 − |
q |
||||||||||||||||
откуда, в частности, при q = |
, получаем |
|||||||||||||||||
2 |
||||||||||||||||||
|ξ – xn| ≤ |xn – xn–1|.
Из последнего неравенства следует, что, если |xn – xn–1| < ε, то и |ξ – xn| < ε.
Метод итераций геометрически может быть пояснен следующим образом. Построим на плоскости xOy графики функций y = x и y = ϕ ( x ) . Каждый действительный корень ξ уравнения (8) является абсциссой точки М пересечения
кривой y = |
ϕ ( x ) с прямой y = x (рис. 3). |
Для |
ϕ ′(x) > 0 и ϕ ′( x ) < 1 кривая y = ϕ ( x ) пересекает биссектрису y = x |
(рис. 3а) слева направо и лежит под биссектрисой. Итерационный процесс, начи-
ная с точки x0 монотонно сходится, приближаясь справа к ξ. |
|||
В случае ϕ ′( x ) > 1 кривая |
y = ϕ ( x ) находится над биссектрисой y = x , |
||
пересекая ее слева направо, и процесс монотонно расходится (рис. 3б). |
|||
y |
y |
||
y=ϕ(x) |
y=ϕ(x) |
y=x |
|
y=x |
|||
M
M |
||
α ξ x2 x1 x0=β |
α ξ x0=β x1 x2 |
x |
а |
б |