Материал: Алгоритмы пособие
nut(x,E,m1,xn,n)
функция f(x)
функция f’(x)
n = 0
n = n+1
|
t = f(x)/f ’(x) |
|
|
x = x-t |
|
|
f2 = f(x) |
|
|
Вывод |
|
|
n, x, f(x) |
|
Не |
|f2| |
|
< E |
||
|
||
|
m1 |
|
|
Да |
|
|
xn = x |
Конец
Входные параметры x – начальное приближение Е – точность вычислений м1 - наименьшее значение |f’(x)| на отрезке [a,b] Выходной параметр xn – корень уравнения n – количество итераций
Рис.2.1-3. Алгоритм метода Ньютона
2.1.4. Метод хорд
Схема алгоритма процедуры, реализующей метод хорд, представленная на рис. 2.1.4.-1, требует дополнения процедуры-функции f(x), в которой вычисляется левая часть уравнения.
16
Рис.2.1-4. Алгоритм метода хорд Корень нелинейного уравнения f (x) 0 должен
отрезке [a;b], причем первая и вторая производные
непрерывны и знакопостоянны при х [a;b]. Рекурентная формула метода хорд [3]:
быть отделен на
( |
f ( x) |
и |
f ( x) |
) |
|
|
|
|
|
f(xn ) |
|
|
|
где |
|
|
|
|
|
|
|
|||
xn 1 xn |
|
|
(x xn ), |
|||||
|
|
|
||||||
|
|
|
||||||
f(x) f(xn ) |
||||||||
|
|
|
|
|
||||
x
- неподвижная точка.
Неподвижен тот конец отрезка [a;b], для которого знак функции f(x) совпадает со знаком ее второй производной. Тогда второй конец отрезка можно принять за начальное приближение к корню, то есть точку х0.
Оценка погрешности метода хорд можно определить одним из выражениями:
xn xn 1 |
|
ε m |
или |
f(xn ) |
ε. |
1 |
|
||||
|
|
M1 m1 |
|
m1 |
|
17
f (x)
где
при
m1и M1
x [a, b]
– соответственно, наименьшее и наибольшее значения
.
В случае, если M1<2m1, то для оценки погрешности метода может быть использована формула
| xn-xn-1| .
2.2.Алгоритмы методов интерполяции функции
2.2.1. Метод Лагранжа
Схемы алгоритмов, используемые при вычислении значения функции по формуле Лагранжа, представлены на рис.2.2-1 и 2.2-2.
Рис.2.2-1. Алгоритм интерполяции функции с заданной точностью
18
Рис.2.2-2. Алгоритм интерполяции функции с заданным количеством узлов
При интерполяции по методу Лагранжа функция f(x) может быть задана в (n+1)узлах, произвольно расположенных на отрезке [a;b]: y0 = f(x0), y1 = f(x1), … yn = f(xn).
Общий вид интерполяционной формулы[3]
n |
(x x0 )(x x1)...(x i 1)(x xi 1)...(x xn ) |
|
|
||||||||||||||||
Ln (x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
yi |
(x |
|
x |
|
)(x |
|
x )...(x |
|
x |
|
)(x |
|
|
)...(x |
|
x |
|
) |
||
i 0 |
i |
0 |
i |
i |
i 1 |
i |
i |
n |
|
||||||||||
|
|
|
1 |
|
|
i 1 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
Поскольку точность интерполяции функции зависит от количества используемых узлов, то оценку погрешности интерполяции в точке принято проводить по следующей формуле:
R |
| f(x) L |
m |
(x) | | L |
(x) L |
m |
(x) |, |
m |
|
|
m 1 |
|
где m– число узлов, используемое в формуле.
В этом случае, для того чтобы добиться заданной точности, при решении задачи интерполяции нужно использовать две процедуры (рис. 2.2-1 и 2.2-2). Если функция интерполируется при заданном количестве узлов, используется только процедура, представленная на рис. 2.2-2.
Для того чтобы уменьшить погрешность интерполяции, используется прием перенумерации узлов исходной таблицы [3].
2.2.2. Первая интерполяционная формула Ньютона
Первая интерполяционная формула Ньютона используется, если требуется найти значение функцииy=f(x), заданной в равноотстоящих узлах
так, что |
|
xi = x0 +ih, где h – |
шаг интерполяции, |
а i = 0, 1, …, n, в точке, |
|||||||||||||||||||||
расположенной в начале таблицы. |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
Формула имеет следующий вид [3]: |
|
|
y |
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
y |
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|||
P (x) y |
|
|
|
|
(x x |
) |
|
2 |
|
|
(x x |
)(x x |
) ... |
n |
|
|
(x x |
)...(x x |
|
). |
|||||
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
n |
|
|
0 |
|
1!h |
|
0 |
|
|
|
|
2 |
|
0 |
1 |
|
|
n |
0 |
|
n 1 |
|
|||
|
|
|
|
|
|
|
|
|
2!h |
|
|
|
|
|
n!h |
|
|
|
|
|
|||||
Здесь y0, |
2y0, … |
|
ny0 – соответствующие конечные разности. |
|
|||||||||||||||||||||
Если интерполируемая функция задана таблично, то оценку |
|||||||||||||||||||||||||
погрешности интерполяции можно произвести по формуле: |
|
|
|
||||||||||||||||||||||
R |
|
q(q 1)...(q n) |
|
n 1 |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
n |
|
|
|
(n 1)! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Схема алгоритма интерполяции в точкепо первой формуле Ньютона приведена на рис. 2.2-3. При необходимости получения значений интерполяционного полинома при разном количестве узлов, в процедуре рекомендуется вставить промежуточную печать.
20