Численное
решение уравнений. На практике многие алгебраические
и трансцендентные уравнения не могут быть решены аналитически.
Существует довольно многр приемов численного решения данной зада-
чи. Рассмотрим некоторые из них.
Пусть имеется непрерывная функция
У = Г(х),
%
(1.111)
у которой на отрезке [а, Ь] существует единственный корень
Ш)=0, (1.112)
который требуется найти с точностью е.
Положим для определенности, что у = ! (х) является возрастающей
функцией и, таким образом, / (а) С 0, /
(Ь)
> 0. Решить данную зада-
чу — значит найти такое значение х, для которого \х — | [ < е.
В методе половинного деления (дихотомии) поступают так. Рас-
считывают координату середины отрезка [а, Ь] с = (а + Ь) 12. Вычис-
ляют функцию / (с) в этой точке. Если / (с) > 0, то ясно, что корень
находится между а и с. Если / (с) < 0, то корень расположен между
точками с и
Ъ.
После выяснения, на каком из отрезков [а, с] или [с, Ь]
находится корень уравнения, половину, не содержащую корень, отбра-
сывают, а к другой, содержащей корень, применяют тот же метод поло-
винного деления и т. д. После п операций деления пополам длина от-
резка, содержащего корень, станет (Ь — а)12
п
и будет выполнено не-
равенство (Ь — а)/2
п
< е. Это означает, что любая точка полученного
отрезка будет отстоять от I на расстоянии, меньшем или равном е, и,
например, его середину можно принять за приближенное значение*
корня.
На рис. 1.43 приведена блок-схема для решения данной задачи.
Блок-схемы удобны и обычно используются для последующего перево-
/ да алгоритма на язык ЭВМ.
Дадим некоторые пояснения. В прямоугольниках показаны блоки
ввода данных, расчета средней точки отрезка, значения функции в
ней, присвоения значения с правому (Ь) или левому (а) концу нового
отрезка половинной длины, вывода приближенного значения корня.
Ромбами показаны блоки условных переходов» В зависимости от вы-
полнения цли невыполнения указанных в них условий дальнейшие
расчеты передаются в разные участки программы. Так, если при про-
верке условия |Ь — а\ < е окажется, что оно выполняется* расчеты
заканчивают и (Ь + а)/2 — приближенный корень уравнения. Если
нет, то рассчитывают координаты точки середины отрезка [а, Ь] и т.д .
После проверки условия / (с) > 0 точка с становится правой (Ь) или
левой (а) точкой нового отрезка [а, Ь] половинной длины.
Заметим, что при составлении алгоритма данной задачи предпола-
галось, что на исходном отрезке имеется только один корень и / (а)<0,
а /
(Ь)
> 0. Для других более общих случаев необходимо усложнить
блок-схему и соответственно программу. Так, например, если / (х)
является убывающей функцией и, следовательно, на отрезке [а, Ь]
12
! (а)> 0, /
(Ь)
< 0, то программа, составленная по приведенной блок-
схеме, не сможет дать правильного решения задачи. Чтобы избежать
таких осложнений, в блок-схему между блоком ввода исходных дан-
ных и блоком проверки условия
\Ь
— а\ < е следует вставить блок
проверки значений / (х) на концах отрезка
[а,.Ь]
"(или на одйом из кон-
цов). Если / (а) < 0 (функция возрастающая), то дальнейшие расчеты
идут без изменения. Если же функция убывающая [/ (а) > 0], то, что-
Вбод а,Ь,
е
хф+а)/2
\нет
с=(а+Ь)/2
8ыбод
х
6= с а=с
да .
Расчет-Г(с)
%
Рис. 1.43. Блок-схема программы: поиска единственного
корня возрастающей функции */=/ (*) на отрезке
[а, Ь]
бы не менять блок-схе^у программы, / (х) следует заменить на —/ (*),
которая явлйется возрастающей и, таким образом, удовлетворяет ус-
ловиям задачи.
Метод дихотомии можно распространить и на случаи, когда исход-
ная функция у = / (х) на отрезке [а, Ь] имеет несколько корней
..., Ъ
пу
причем заранее не известно сколько. Требуется найти все
..., х
П1
являющиеся приближенными значениями ..., |
п
с точностью
е, т. е. для любого I
\х%
— ! < е.
Для решения задачи выберем в качестве начального шага /1
0
<С
< пип — ||_х|.. Вычислим / (а) и р (а + Н
0
) и найдем произведе-
ние О =/ (а) / (а + Н
0
). Если Ь > 0, то очевидно, что первый корень
^ расположен правее (а +
Н
0
)
и, присваивая а новое значение (а +
+й
0
), повторяем вычисления. Если О С 0, то находится между а
и а + /г
0
, следовательно, первый корень оказывается локализованным
на отрезке 1а, а + Н
0
] и для его уточнения можно воспользоваться
методом последовательного деления этого отрезка пополам. После то-
го как необходимое приближение первого корня будет найдено, еле-
324 12$