Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
358
\
V,
библиотечная программа В4А1. Например, для уравнения агс1§д:=0 поиск корня с точностью е (смысл 8 поясняется в описании В4А1) можно выполнить с помощью следующей программы:
REAL X,R,D,X0,E INTEGER N,I EXTERNAL F
С ВВОД НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ К КОРНЮ ХО
С ВВОД ТОЧНОСТИ Е, ВВОД МАКСИМАЛЬНОГО ЧИС-
С ЛА ИТЕРАЦИЙ N
READ (5,1) X0,E,N
1 FORMAT (2F9.6,I5)
С ОБРАЩЕНЙЕ К ПРОГРАММЕ В4А1
CALL B4A1(X,R,D,F,X0,E,N,I)
С ВЫВОД НА ТЕРМИНАЛ ЗНАЧЕНИЯ КОРНЯ X И
С ИНДЕКСА ОШИБОК I
WRITE (5,2) ХД
2 FORMAT (2Х,'Х = ',Е13.6/1=',12)
END
С ПОДПРОГРАММА F, ВЫЧИСЛЯЮЩАЯ ЗНАЧЕНИЕ
С ФУНКЦИИ И ЕЕ ПРОИЗВОДНОЙ
SUBROUTINE F(X,R,D)
REAL X,R,D R=ATAN(X)
D=1./(1.+X*X)
RETURN
END
9.3.4. Метод Ньютона для векторного уравнения. Пусть имеется векторное уравнение
f(x)=0,
которое эквивалентно системе п скалярных уравнений
Л(*1> *2, ••• , *и) = 0,
/2(*1, *2, -,*») = О, /Q о Q4
/„(*!> *2, - , Хи) = 0.
Будем рассматривать (9.3.9) в шаре 5= {л:: || л: — л:(0) || <г}. Предположим, что в любой точке лгеЗ' матрица А(х) с элементами
ланЦк*1» •••>*«)
невырождена.
Тогда метод Ньютона для (9.3.9) по аналогии с (9.3.4) записывается следующим образом:
= к=09 х9 _ (9.3.Ю)
359
На каждом шаге к итерационного процесса (9.3.10) решаются линеаризованные уравнения, полученные из (9.3.9).
Условия сходимости последовательности {х(к)} к решению (9.3.9) можно получить из теоремы 9.5, рассматривая (9.3.10) Как метод простой итерации с
<р(х) = Ех-А ~1 (x)f(x), х<*+1> = ср (*<*>).
Здесь Е—единичная матрица. При этом следует потребовать, чтобы функции fi(xu были дважды непрерывно дифферен-
цируемы по своим аргументам в шаре S.
9.3.5. Прилфнение программы В4А2. Для определения корней системы уравнений (9.3.9) методом Ньютона может использоваться библиотечная программа В4А2. Например, пусть имеем систему уравнений >
x1-0,05e_XtJC2 = o,
х2—0,05е~(*1 +Х2)=0.
Точность вычислений е определена в описании В4А2. Поиск приближенного значения корня х=(х1, х2) с точностью е можно выполнить с помощью следующей программы:
REAL X(2),F(2),E,W(10)
INTEGER N,K,I EXTERNAL R DATA I/0/,N/2,K/10/
С ВВОД НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ К КОРНЮ
С ВВОД ТОЧНОСТИ Е
READ (5.1) Х,Е
1 FORMAT (3F9.6)
С ОБРАЩЕНИЕ К ПРОГРАММЕ В4А2
CALL B4A2(R,N,X,F,E,W,K,I)
С ВЫВОД НА ТЕРМИНАЛ ЗНАЧЕНИЙ КОМПОНЕНТ
С КОРНЯ И ИНДЕКСА ОШИБОК I
WRITE (5.2) ХД
2 FORMAT (2Х,2Е13.6,Т-'Д2)
END
С ПОДПРОГРАММА, ВЫЧИСЛЯЮЩАЯ ЗНАЧЕНИЯ
С ФУНКЦИЙ
SUBROUTINE R(N,X,F,J)
REAL X(2),F(2)
INTEGER N,J DATA J/0/
F(1)=X(1)—0.05 *EXP(—X( 1 )*X(2))
F(2)=X(2) - 0.05*EXP( - (X(l)+X(2)))
RETURN
END
В программе В4А2 необходимые значения про-
ИЗВОДНЫХ -г-1- для опреде-
дХ]
ления матрицы А вычисляются с помощью формул численного дифференцирования (см. гл. 10).
# 9.4. Метод бисекции
Метод бисекции (или метод деления отрезка пополам) отличается от рассмотренных выше способов приближенного определения корня уравнения Дх)=0 тем, что для его сходимости не требуется, чтобы f\x) была дифференцируемой, достаточно только непрерывности f{x).
9.4.1. Алгоритм метода бисекции. Пусть задана непрерывная на интервале [а0, Ь0 ] функция f(x). Пусть известно, что на [я0, Ь0] имеется единственный корень уравнения
/(*) = 0. (9.4.1)
Тогда в силу непрерывности f(x) значения f(a0) и f(b0) имеют разные знаки (рис. 9.13). Разделим отрезок [a0/b0] пополам точкой с0 — (ао+Ь0)/2. Сохраняем для дальнейшего деления ту половину отрезка, на концах которого f(x) имеет разные знаки. Введем следующие обозначения:
fc0, если f(a0)f(c0) > 0,
1 |?0, если f(a0)f(c0)<0;
fс0, если f(b0)f(c0) > 0,
ji0, если /(*0)/(с0) < °.
Разделим оставшийся отрезок [ах, Ьг] пополам и повторим приведенную систему обозначений. Для произвольного к-ro деления имеем
Л _ак+Ьк Ск — ? ’
*1 =
ак+1 —
Ьк+1~
к= 1, 2, ...
\ск, если Да*)/(с*)> 0,
|аь если /(ак)/(ск) < 0;
[с*, если/(*ц)/(ск) > 0,
|Ьк, если /(Ьк)/(ск) < 0.
Алгоритм завершается, если для какого-либо к оказывается /(ск) = 0. Тогда значение корня х = ск. Если задана абсолютная точность определения корня є, то алгоритм завершается при условии
Ьк ~ ак _ Ьо — ао ^ „
« — СБ.
361
Со =(а0+Ь0)/2 |
Ь, <- Ь0 |
м-'Г
Ь, Со |
стоп Со - КОРЕНЬ С ТОЧНОСТЬЮ Є
Рис. 9.14
В этом случае за приближенное значение корня л; принимается значение ск; очевидно, что
9.4.2. Схема алгоритма бисекции. Отличительной особенностью алгоритма метода бисекции являете^ его логическая структура.
362 ' \
В блок-схеме, представленной на рис. 9.14, имеется четыре логических элемента типа альтернативы (см. гл. 2). Концы интервала до деления пополам обозначаются а0, й0, после деления—al9 bv
9.4.3. Применение библиотечной программы В4А0. Для определения корня непрерывной функции f(x) методом бисекции можно использовать программу В4А0, которая реализует схему алгоритма, приведенного на рис. 9.17, с ограничением на допустимое число делений пополам исходного интервала [а, b ]. Пусть ищется корень уравнения
л;—е-* = 0
на интервале [0, 1] с точностью в=10"5, максимальное число делений интервала пополам положим равным 20. Тогда программа может иметь следующий вид:
