Введение в информатику. Хамухин А.А. - 134 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

133
4.7.2. Метод последовательных приближений
Метод последовательных приближений (итераций) базируется на известном в
математике (теория множеств) принципе сжатых отображений. Этот принцип
определяет так называемый оператор сжатия, для которого выполняется условие:
1212
)()( xxaxFxF
,
)1,0(a
. (4.42)
Из этого определения следует теорема, согласно которой в замкнутом
множестве для такого оператора сжатия существует неподвижная точка и она
единственная.
Эта неподвижная точка, в приложении к численным методам расчета, и есть
точное решение, к которому на каждой итерации производится приближение. Метод
дает только приближенное решение с некоторой погрешностью, которая
уменьшается на каждом шаге, пока в этом уменьшении имеется разумный смысл.
Но решение приближается не всегда, поэтому существуют понятия сходимость,
скорость сходимости, условия сходимости.
Сходимость – это свойство алгоритма обеспечивать приближение к точному
решению.
Условия сходимости – это математические соотношения величин,
участвующих в итерационном процессе, которые обеспечивают алгоритму свойство
сходимости.
Скорость сходимости – это степень приближения к точному решению на
каждой итерации, обычно она бывает линейной или квадратичной.
В зависимости от того или иного способа реализации метод последовательных
приближений подразделяется на целый ряд методов, имеющих собственные
названия в специальной литературе. В качестве примеров рассмотрим некоторые из
них.
4.7.3. Метод дихотомии (деления пополам)
Существует теорема, которая гласит, что если непрерывная функция f(x) на
концах отрезка [a;b] имеет разные знаки, то она имеет корень (нулевое значение) на
этом отрезке. Поэтому первым этапом метода дихотомии является табуляция
исследуемой функции или разделение ее на такие отрезки, на концах которых ее
значения противоположны. Затем каждый из найденных отрезков поочередно
подвергается делению пополам. После разделения из двух вновь полученных
отрезков выбирается тот, на концах которого значения исследуемой функции
противоположны. Выбранный из двух отрезок вновь делится пополам, и эта
процедура повторяется до тех пор, пока значение функции на середине отрезка не
станет меньше заранее заданного сколь угодно малого числа, которое является
погрешностью метода дихотомии.
Формулы дихотомии представлены в математических выражениях (4.43), а сам
процесс демонстрируется на рис. 4.8.

Страницы