ЭВМ_Семестр3_МетодПособие
.pdf
|
y |
|
|
|
|
|
|
|
|
|
( 0 ) |
|
|
|
|
|
2 |
( 0 |
) |
|
|
|
|
1 |
|
|
|
|
|
|
|
< ′ |
< 1 |
|
|
0 |
0 |
|
|
0 |
x |
1 |
|
|
|
2 |
|
Рисунок 1.5 – При 0<φ’ x)<1 метод итераций сходится |
|||||
|
y |
|
|
|
|
|
|
( 0 |
) |
|
|
|
|
2 |
|
|
|
|
|
|
( |
0 ) |
|
|
|
|
1 |
|
|
|
|
|
φ'(x)>1 |
|
|
|
|
0 |
0 |
|
|
|
|
2 |
|
|
|
|
|
1 |
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
Рисунок 1.6 – При φ’ x)>1 метод итераций расходится |
|||||
y |
− < ′ |
|
|
|
|
|
< 0 |
||
|
( 0 |
) |
|
|
|
1 |
|
|
|
|
10 |
x |
|
|
Рисунок 1.7 - При -1<φ’ x)<0 метод итераций сходится
21
y |
|
|
φ'(x)<-1 |
0 |
|
1 |
x |
Рисунок 1.8 - При φ’ x)<-1 метод итераций расходится
Из приведенных рисунков видно, что процесс итераций сходится к искомому корню, если на участке, внутри которого имеется единственный корень, выполняется условие: 1 (x) 1.
При использовании преобразования исходного уравнения (1.1) к виду (1.3), с помощью введенного множителя можно обеспечить сходимость, выбрав его так, чтобы при всех x внутри интервала локализации данного корня модуль производной функции (x) был меньше единицы, т.е.
|
|
|
|
|
|
|
|
|
1 |
(1.6) |
|
|
|
|
|
||||||
|
|
(x) |
|
|
1 f (x) |
|
||||
Таким образом, −1 < 1 + ′ |
< 1 |
или −2 < ′ |
< 0 для |
|||||||
случая, когда ′ |
> 0 и 0 < ′ |
< 2 в случае ′ < 0. |
|
|||||||
Метод простых итераций имеет линейную скорость сходимости, правильный выбор начального приближения позволяет уменьшить количество итераций для достижения заданной точности вычисления корня.
В практических инженерных расчетах часто, в качестве критерия окончания итерационного процесса, применяют сравнение аргумен-
тов на текущей и предыдущей итерациях: |
|
( ) − ( −1) ≤ |
(1.7) |
22
1.1.3 Метод Ньютона (метод касательных)
Метод Ньютона является одним из наиболее эффективных численных методов решения самых разных нелинейных уравнений. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путѐм построения последовательных приближений и осно-
ван на принципах метода простых итераций. Метод Ньютона называют также методом касательных, т.к. новое приближение x(k+1) явля-
ется абсциссой точки пересечения касательной, проведенной в точке (x(k) , f(x(k)) к графику функции f(x), с осью Ox (см. рисунок 1.9).
Постановка задачи. Пусть уравнение f(x) имеет один корень на отрезке [a,b], причем первая и вторая производные ′ ( ) и ′′ ( ) на этом отрезке существуют, непрерывны и сохраняют на отрезке постоянные знаки. Требуется определить этот корень с заданной точностью .
y |
|
|
|
f (x0) |
|
|
|
y=f(x) |
|
|
|
|
|
f '(x0) |
|
a |
|
|
b=x0 |
0 |
|
x2 |
x1 |
x |
Рисунок 1.9 – Метод Ньютона (касательных)
Внутри отрезка локализации корня [a,b] назначаем (смотри рисунок 1.9) начальное приближение корня x0 . В точке x0 , f (x0 ) рассчитываем касательную к кривой y f (x). Уравнение этой касательной имеет вид:
y f (x0 ) f (x0 ) x x0
23
Абсциссу точки пересечения касательной с осью Ox принимаем за следующее приближение корня, т.е.
x1 |
x0 |
|
f (x0 ) |
|
f (x0 ) |
||||
|
|
|
Повторяем процесс: проводим касательную к кривой y f (x) в точке x1 , f (x1 ) , абсциссу точки пересечения касательной с осью Ox принимаем за следующее приближение корня:
x2 |
x1 |
|
f (x1) |
|
f (x1) |
||||
|
|
|
В общем виде формула метода касательных имеет вид:
xn 1 |
xn |
f (xn ) |
(1.8) |
|
f (xn ) |
||||
|
|
|
Процесс повторяется до тех пор, пока не будет выполнено условие нахождения корня с заданной точностью. В инженерной практике, берут один из следующих критериев останова:
1. f(x(n))< - значение функции на данной итерации стало меньше заданного .
2. ( ) − ( −1) ≤ изменение x(n) в текущей итерации стало меньше заданного .
Чаще всего используют критерий 2. Условие сходимости метода Ньютона:
1.функция f(x) на отрезке локализации корня [a,b] непрерывна;
2.первая и вторая производные ( f´(x) и f"(x) ) непрерывны на интервале [a,b] и могут быть вычислены в любой точке интервала, причем первая производная не обращается в ноль;
3.вторая производная на интервале [a,b] постоянна по знаку;
4.начальное приближение х0 выбирается так, чтобы выполнялось условие
( 0) ∙ "( 0) > 0
24
Метод Ньютона обладает только локальной сходимостью, т.е. областью его сходимостью является некоторая малая σ-окрестности корня и для гарантии сходимости необходимо вбирать хорошее начальное приближение, попадающее в эту σ-окрестность. Неудачный выбор начального приближения может дать расходящуюся последовательность итераций, например, представленную на рисунке
1.10.
y |
|
|
|
|
|
y=f(x) |
|
f(x1) |
|
|
|
|
|
|
x0=a |
b |
|
|
|
f |
f '(x0) |
x1 |
x2 |
x |
|
|
|||
Рисунок 1.10 – Метод Ньютона расходится при неправильном выборе x0 |
||||
Если вычисление первой производной функции на каждом шаге требует больших вычислительных затрат, можно использовать модифицированный метод Ньютона. Суть его заключается в том, что значение производной вычисляется один раз в начальной точке x(0) и это фиксированное значение подставляется в формулу (1.9):
xn 1 |
xn |
|
f (xn ) |
(1.9) |
|
f |
|
||||
|
|
|
(x0 ) |
|
|
Геометрическая интерпретация модифицированного метода Ньютона представлена на рисунке 1.11. В отличие от обычного метода касательных, в модифицированном методе предъявляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если 
. Однако, модифицированный метод имеет один существенный недостаток – резкое падение скорости сходимости.
25
y |
|
f(x0) |
|
|
|
|
f '(x0) |
f '(x0) |
|
|
|
0 |
|
|
|
x1 |
x |
Рисунок 1.11 – Модифицированный метод Ньютона
Формула (1.9) совпадает с формулой метода простых итераций, если определить
= − ′((µ)) = − ( ),
где μ – значение абсциссы в некоторой точке отрезка локализации корня с максимальным значением первой производной функции f(x) на отрезке локализации корня.
Как уже показано, этот процесс сходится, если (x) 1 в интервале, в котором находится один корень уравнения f (x) 0, т.е.
´ = |
1 − < 1 |
Значение λ следует принимать:
= |
( ′ |
|
) |
(1.10) |
max ( ′ |
|
) |
где ( ′ ) – знак первой производной f(x) на интервале локализации корня [a,b];
max ( ′ ) – максимальное значение первой производной f(x) на интервале локализации корня [a,b].
1.1.4 Метод деления отрезка пополам
Метод обеспечивает нахождение единственного корня в интервале локализации х[a,b] с заданной точностью >0. Наличие корня
26
уравнения на интервале [a,b] (или нечетного числа корней) предполагает, что на границах интервала функция f(x) имеет разные знаки, т.е. f(a)·f(b)<0. Метод уточняет (сужает) границы интервала, где распо-
ложен корень. В дальнейшем интервал [a,b] будет обозначаться с указанием номера итерации - [a(0),b(0)].
В методе деления интервала пополам (методе бисекций) отрезок
локализации корня делится пополам (0) = (0)+ (0). Перемещая одну
2
из границ в точку x(0) уменьшаем отрезок локализации в два раза, т. е. заменяем начальный отрезок [a(0),b(0)] отрезком [a(1),b(1)] меньшей
длины. В методе бисекций в качестве [a(1),b(1)] берут тот из отрезков [a(0),x(0)] и [x(0),b(0)] на концах которого выполняется условие
f(a(1))·f(b(1))≤0. Этот отрезок содержит искомый корень. Если данное произведение равно нулю, то корнем уравнения является одна из гра-
ниц. Неограниченное продолжение итерационного процесса дает последовательность отрезков [a(0),b(0)], [a(1),b(1)], … , [a(n),b(n)], содержа-
щих искомый корень. Каждый из них, за исключением начального, получен делением пополам предыдущего отрезка.
При повторении процедуры деления, длина отрезка становится настолько малой (меньше заданной допустимой погрешности в определении корня), что можно приближенно за значение корня принять абсциссу любой точки отрезка [a(n),b(n)]. Считая, что (b a) является
абсолютной погрешностью, а (b a) / a - относительной погрешно-
стью вычислений корня уравнений, мы получаем возможность гарантированно выбирать значение корня с недостатком (принимая x a ) или с избытком (принимая x b). Обычно за корень уравнения принимают значение x(n).
27
y |
|
|
|
|
|
шаг 1 |
|
|
|
|
|
|
x(1) |
|
|
|
|
a(0) |
|
|
b |
(0) |
x |
|
|
|
|||
|
|
|
|
||
y |
|
x(2) |
шаг 2 |
|
|
|
|
|
|
||
a(1) |
|
|
b(1)=b(0) |
x |
|
|
|
|
|||
y |
x(3) |
|
шаг 3 |
|
|
a(2)=a(1) |
|
b(2) |
|
|
x |
|
|
|
|
||
Рисунок 1.12 – Метод деления отрезка пополам |
|
||||
Пример 1.1
Используя графический способ отделения корней определить ин-
тервалы локализации корней уравнения sin x cos x 3x 0.
Данную задачу можно решить, используя электронную таблицу Excel и пакет Matlab. На рисунке 1.13 показан фрагмент электронной таблицы Excel (в режиме отображения функций) с графиком функции.
Для получения графика данной функции в пакете MATLAB, показанного на рисунке 1.14, необходимо выполнить следующую цепочку команд:
f=inline('sin(x)-cos(x)-x/3') figure;
fplot(f,[-3 3]); grid;
28
Рисунок 1.13 – Вид таблицы Excel с графиком функции sin x cos x 3x 0
Рисунок 1.14 – График функции sin x cos x 3x 0 построенный в пакете Matlab
29
Анализ графиков показывает три отрезка локализации корней:
[-2;-1], [0,5;1,5], [3;3,5].
Пример 1.2
Используя встроенную функцию fzero пакета MATLAB, найти корни уравнения f(x)=0. В квадратных скобках задаются левая и правая границы интервала, на котором расположен корень. Протокол работы в пакете Matlab представлен ниже.
»[x]=fzero(f,[-3 1]) x =
-1.8936
»[x]=fzero(f,[1 2]) x =
1.0308
Пример 1.3
Используя |
процедуру на VBA, найти два корня уравнения |
|
sin x cos x |
x |
0 с точностью =0.0001. |
|
||
3 |
|
|
Примечание. Вычисление третьего корня уравнения читателю предлагается выполнить самостоятельно.
Для реализации метода простых итераций необходимо преобразовать исходное уравнение к виду x (x) . Очевидно, что простейшее преобразование уравнения x=3·(sin(x)-cos(x)) (производная ′ =
3 · |
|
|
+ |
) не отвечает условию сходимости метода ите- |
||||||||||||||
раций. |
Поэтому, |
|
используем преобразование x x f (x), откуда |
|||||||||||||||
(x) x f (x) . |
|
|
|
|
|
|
|
|
|
|
||||||||
|
Значение |
λ |
выбираем |
из |
условия |
сходимости |
||||||||||||
|
|
|
|
|
|
|
1, |
т.е. |
|
|
|
|
|
1 |
|
решая нера- |
||
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
(x) |
|
|
1 f (x) |
|
(x) |
|
|
|1+ (cosx+sinx-3)|<1, |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
венство получим
30