PDF / lecture_9
.pdf(С) ИиКМ РХТУ апрель 2004г. Калинкин Владимир Николаевич |
1 |
Решение уравнения с одним неизвестным |
|
Дано уравнение в виде f(x)=0, где f(x) некоторая функция переменной x. Число x* называется |
|
корнем или решением данного уравнения, если при подстановке x= x* |
в уравнение последнее |
обращается в тождество. f(x*)=0. Число x* называют также нулем функции y=f(x). |
В общем случае уравнение может иметь одно или несколько корней, как действительных, так и комплексных. Нахождение действительных корней с заданной точностью можно разбить на два этапа. Сначала корни отделяются, т.е. определяются отрезки, которые содержат по оному корню уравнения; а затем вычисляются с требуемой точностью ε. Отделение корней уравнения f(x)=0, в области определения, непрерывной функции f(x), можно осуществлять несколькими способами: табулированием - составлением таблицы из равноотстоящих значений независимой переменной и соответствующих значений функции и определение отрезков в которых смежные значения функции имеют различные знаки и следовательно содержат нулевые значения функции. строим график функции на и определяем минимальные отрезки, включающие точки пересечения графика функции с осью 0x.
уравнение f(x) заменяем равносильным ψ(x)= φ(x) строят графики функций ψ(x) и φ(x). Определяют минимальный отрезок содержащий точку пересечения графиков функций.
пример f(x) = 3*sin(2*x)-1.5*x-1=0 ψ(x)=3*sin(2*x) φ(x)=1.5*x+1
x |
f(x) |
ψ(x) |
φ(x) |
-2,000 |
4,270 |
2,270 |
-2,000 |
-1,600 |
1,575 |
0,175 |
-1,400 |
-1,200 |
-1,226 |
-2,026 |
-0,800 |
-0,800 |
-2,799 |
-2,999 |
-0,200 |
-0,400 |
-2,552 |
-2,152 |
0,400 |
0,000 |
-1,000 |
0,000 |
1,000 |
0,400 |
0,552 |
2,152 |
1,600 |
0,800 |
0,799 |
2,999 |
2,200 |
1,200 |
-0,774 |
2,026 |
2,800 |
1,600 |
-3,575 |
-0,175 |
3,400 |
|
|
|
4 |
|
|
|
|
|
|
|
|
3 |
5 |
|
|
|
|
|
|
|
2 |
4 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
-3 |
-2 |
-1 |
0 |
01 |
|
1 |
2 |
|
|
|
|
-1 |
0 |
|
|
ψ(x) |
|
-3 |
-2 |
-1 |
-2 |
-1 |
0 |
1 |
φ(x) |
2 |
|
|
|
-3 |
-2 |
|
f(x) |
|
|
|
|
|
-4 |
-3 |
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
-4 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
3 |
|
|
|
|
|
2 |
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
|
-3 |
-2 |
-1 |
-1 0 |
1 |
2 |
|
|
|
|
|
ψ(x) |
|
|
|
-2 |
|
φ(x) |
|
|
|
-3 |
|
|
|
|
|
-4 |
|
|
Уточнение корня на отрезке [a,b], в котором локализован только один корень, осуществляется итерационными методами, в которых последовательно, шаг за шагом, производится уточнение начального приближения корня. Итерацией называется совокупность вычислительных операций, приводящих к новому приближенному значению корня. Если каждое последующее значение находится все ближе к точному значению, говорят, что метод сходится. В противном случае метод расходится. Поэтому возникает необходимость исследования сходимости итерационного метода. Общая итерационная формула вычисления очередного приближения имеет следующий вид xk+1=xk+h, где k=0,1,2,3,… За начальное приближение x0 принимают значение внутри заданного отрезка. Все методы уточнения корней различаются способами вычисления поправки h.
(С) ИиКМ РХТУ апрель 2004г. Калинкин Владимир Николаевич |
2 |
Метод половинного деления.
В этом методе на каждой итерации отрезок содержащий корень делится пополам и за новый отрезок для уточнения принимается одна из половин.
Алгоритм.
1.Задаем функцию f(x), отрезок [a,b] и точность ε.
2.За начальное приближение принимаем левую границу отрезка [a,b] т.е. x =a.
3.Вычисляем поправку h=(b-a)/2 и новое приближение x=x+h
4.Если f(x) = 0, то x – корень.
5.В противном случае, определяем новый отрезок [a,b]. Проверяем, если f(a)*f(x)>0, то a=x и b=b, иначе (f(a)*f(x)<0), то a=a и b=x. Далее проверяем условие окончания, если | h | ≤ 2ε, то за ответ принимаем значение равное x=(a+b)/2 и переходим на пункт 6, иначе переходим на пункт 2.
6.выводим x и f(x).
Блок-схема
начало
a, b, ε || f(x).
x := a
f(a)*f(x)>0
h := (b-a)/2 x := x+h
b := x |
|
|
|
a=x |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f(x) = 0
| h | ≤ 2ε
x := (b+a)/2
|
|
|
|
x, f(x) |
|||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
конец |
|||
Решим предыдущий пример при a= -1.6 |
b= -1.2 и ε= 0.01 т.е. 2ε = 0.02 |
||||||
|
|
|
|
|
|
|
|
a |
b |
h |
x |
f(a) |
f(x) |
|
|
-1,6 |
-1,2 |
0,2 |
-1,4 |
1,575 |
|
0,095 |
|
-1,4 |
-1,2 |
0,1 |
-1,3 |
0,095 |
|
-0,597 |
|
-1,4 |
-1,3 |
0,05 |
-1,35 |
0,095 |
|
-0,257 |
|
-1,4 |
-1,35 |
0,025 |
-1,375 |
0,095 |
|
-0,082 |
|
-1,4 |
-1,375 |
0,0125 |
-1,3875 |
0,095 |
|
0,006 |
|
-1,3875 |
-1,375 |
|
-1,38125 |
|
|
-0,038 |
|
x=-1,38125±0.01 |
f(x) = -0,038 (невязка) |
|
(С) ИиКМ РХТУ апрель 2004г. Калинкин Владимир Николаевич |
3 |
Метод Ньютона или касательных.
В этом методе, на каждой итерации, за новое приближение к корню xk+1 принимается точка пересечения касательной к графику, построенной в точке f(xk) с осью x. За начальное приближение к корню x0 принимаем одну из границ отрезка [a; b], содержащего один корень. Если новое приближение выходит за границы интервала, то надо выбрать новое начальное приближение и если это не помогает надо попробовать уменьшить отрезок поиска в два раза и повторить поиск методом Ньютона.
Графическая иллюстрация.
40 |
|
|
|
|
|
|
|
30 |
|
|
|
|
f(x0) |
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
10 |
|
f(x2) |
f(x1) |
|
|
|
|
|
|
β |
|
|
|
||
|
|
|
|
|
|
||
0 |
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
-10 |
|
x2 |
x1 |
|
x0 |
|
|
-20 |
|
|
|
|
|
|
|
-30 |
|
|
|
|
|
|
|
-40 |
|
|
|
|
|
|
|
Вычислим значение приближения x1. |
|
|
|
|
Обозначим h0 = x0-x1 и x1 = x0-h0, тогда тангенс угла β (касательной в точке f(x0) и осью x) равен
tg(β) = |
f (x0 ) |
= f '(x ) и h = |
f (x0 ) |
и окончательно x1 = x0 – h0 = x0 - |
f (x0 ) |
|
|
||||||
|
|
|
||||
|
h |
0 |
0 |
f '(x0 ) |
f '(x0 ) |
|
|
|
|
аналогично рассчитываются последующие приближения к корню x2, x3, x4, ……..
алгоритм
1.Задаем функцию f(x) отрезок [a;b] и точность ε. За начальное приближение x принимаем одну из границ заданного отрезка [a,b] x=b.
2.Вычисляем приращение значение шага h, как h = ff '((xx)) и новое приближение, как x = x-h.
3.Проверяем если a ≥ x ≥ b , то x = a и повторяем с пункта 2.
4.Иначе проверяем условие окончания если | h | ≤ ε, то выводим последнее значение x и f(x). Иначе перейдем на пункт 2
(С) ИиКМ РХТУ апрель 2004г. Калинкин Владимир Николаевич |
4 |
Блок схема:
начало
x, ε || f(x).
h :=f(x)/f’(x) x := x-h
|
нет |
да |
|
|
|
нет |
да |
||||||
|
|
|
|
|
a≤ x ≤b |
|
|
|
|
|
| h | ≤ ε |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Задать новое |
|
|
|
x, f(x) |
|
|
|||||||
начальное |
|
|
|
|
|
|
|
|
|
||||
приближение |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
конец
Пример a = -1.6 b = -1.2 ε = 0.01 f(x)=3sin(2x)-1.5x-1 f'(x)=6cos(2x)-1.5 x=a=1.6
x |
f(x) |
f'(x) |
h |
(x) |
-1,6 |
1,57512243 |
-7,48976865 |
-0,21030322 |
-1,38969678 |
-1,389696780,02155069 |
-7,11071928 |
-0,00303073 |
-1,38666605 |
Ответ: x = 1,38666605 0.01 f(x)=0,0000012
Метод простых итераций.
Пусть задано нелинейное уравнение f(x)=0, отрезок [a;b], который включает корень данного уравнения, т.е. f(a)*f(b)<0 и точность ε, с которой требуется уточнить значения корня. Преобразуем исходное уравнение к эквивалентному виду x=ϕ(x). Последовательность x0, x1, x2, ……,xi,… называть итерационной, где xi+1 выражается через элемент xi по рекуррентной формуле xi = ϕ (xi-1), т.е. x1 = ϕ (x0), x2 = ϕ (x1), x3 = ϕ (x2),…… за x0 принимают любое число на заданном отрезке [a;b]. Говорят, что итерационный метод сходится, если последовательность {xi} имеет
предел при i → ∞. Для определения условия сходимости определим ∆xi = xi+1 - xi = ϕ(xi)- ϕ(xi-1) и применим теорему о среднем, тогда xi+1 - xi = ϕ’(ξ)*(xi - xi-1). Необходимо чтобы модуль разности
|xi+1 - xi| был меньше чем |xi - xi-1|, а это справедливо только при |ϕ’(ξ)| < 1, т.е. максимальная производная на заданном отрезке должна быть меньше единицы. Так для решения квадратного
уравнения x2=a можно положить ϕ(x)=a/x или ϕ(x)=(1/2)(x+a/x) и соответствующие итерационные формулы будут иметь вид xi+1=a/xi и xi+1=(1/2)(xi +a/xi). В первом случаи метод не сходится, а во втором сходится.
(С) ИиКМ РХТУ апрель 2004г. Калинкин Владимир Николаевич |
5 |
Общий подход для получения итерационной формулы f(x)=0; помножим обе части |
|
уравнения на множитель β, получим βf(x)=0 и прибавим к обеим частям по x. Окончательная |
|
итерационная формула будет иметь вид x= x+βf(x). Функция ϕ(x)= x+βf(x); |
ϕ’(x)=1+βf’(x); |
|1+βf’(x)|<1;
-1 < 1+βf’(x) < 1; -2 < βf’(x) < 0. Мы должны выбрать максимальную по модулю производную на
заданном отрезке. Тогда, если |f'(b)|>|f'(a)| |
β = -2/f’(b), |
|||||||||||
иначе β = -2/ f”(a) |
|
|
|
|||||||||
|
|
|
|
|
начало |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a,b,ε || f(x),f’(x) |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|f’(b)|>|f’(a)| |
|
|
|
||||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
β := -2/f’(a) |
|
β := -2/f’(b) |
|||||||||
|
x:=a |
|
|
|
|
x:=b |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
h:= βf(x) x := x+h
a≤ x ≤b
Задать новое
начальное | h | ≤ ε приближение
x, f(x)
конец
Пример: |
|
|
|
|
|
f(x) = 3sin(2x)-1.5x-1 |
f'(x)=6cos(2x)-1.5 |
ε=0.01 a = -1,6 |
b = -1,2 |
||
f'(a) = -7,489 |
f'(b) = -5,924 |
λ = 0,267 ≈ 0.2 |
|
||
xi+1 = xi +λ(3sin(2x)-1.5x-1) |
|
|
|
||
|
|
|
|
|
|
|
i |
xi |
f(xi) |
h |
ϕ(xi) |
0-1,6 1,57512243 0,315024486-1,28497551
1-1,28497551-0,69557695 -0,13911539 -1,4240909
2-1,4240909 0,2684794250,053695885-1,37039502
3-1,37039502-0,11487989 -0,02297598 -1,393371
4-1,393371 0,0477055050,009541101-1,3838299 -1,3838299 -0,02009317
Ответ: x = -1,384±0.01 |
f(x) = -0,020 |