Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методы построения конечных алгоритмов.

Читайте также:
  1. C) Методы стимулирования поведения деятельности
  2. II. Методы и источники изучения истории; понятие и классификация исторического источника.
  3. II. Методы исследования
  4. II. Методы исследования
  5. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  6. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  7. III. Латентная преступность: понятие и методы выявления.
  8. III. Методы развития речи учащихся
  9. III. Основные методы биологических исследований.
  10. III. Процедурные методы анализа

В математике существуют итерационные вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Численный метод, в котором производится последовательное, шаг за шагом, уточнение первоначально грубого приближения называется методом итераций. Каждый шаг в таком методе называется итерацией.

Итерационные процедуры описывают бесконечный вычислительный процесс, К ним относятся задачи, связанные с вычислением сумм рядов, численным интегрированием, решением уравнений итерационными методами и т.п. Алгоритм, реализующий в чистом виде такую процедуру, не представляет практического интереса, так как он не обладает свойством результативности. Однако если процесс прервать искусственно, например, введя условие вида "Закончить вычислительный процесс, когда погрешность результата будет меньше некоторого заданного малого числа", то получится алгоритм вычисления с заданной погрешностью.

На этом принципе основан общий метод построения многих вычислительных процессов: строится бесконечный, сходящийся к некоторому решению процесс; он обрывается на некотором шаге и полученное значение результата принимается за приближенное решение рассматриваемой задачи. Очевидно, что точность полученных результатов в такой вычислительной процедуре зависит от числа шагов. При этом возникает проблема, связанная со способом определения текущей пегрешности (обозначим ее ЕТ).

Замечание. При проведении расчетов на ЭВМ с использованием вещественных чисел результаты вычислений всегда получаются приближенными. Это связано с наличием погрешности округления Е0 вещественных чисел, обусловленной конечной длинной мантиссы. Погрешностью Е0 можно управлять путем изменения длины ячеек памяти, используемых для хранения переменных вещественного типа. Обычно эта погрешность настолько мала, что ею можно пренебречь. Поэтому при рассмотрении указанных выше алгоритмов нас будет интересовать только текущая погрешность, обусловленная методом решения задачи.

Различают два типа циклических процессов: арифметические и итерационные. Арифметическим называется циклический процесс для которого заранее известно количество циклов. К итерационным относятся циклические процессы, для которых заранее неизвестно, сколько циклов надо выполнить, и только в процессе выполнения цикла выясняется, когда он закончится. Алгоритмы, использующие принудительное окончание вычислительного процесса по текущей погрешности, реализуются в виде итерационных циклических процессов. Недостатком итерационного цикла является то, что он может потерять свойство конечности из-за ошибок в данных. Для повышения надежности программы в подобных циклах необходимо предусматривать средства контроля количества циклов.

С этой целью обычно итерационный цикл преобразуют в арифметический путем ограничения количества циклов достаточно большим числом. Если решение не будет найдено за установленное максимальное число шагов, то цикл завершается и вырабатывается признак ошибки. Этот признак можно использовать для принятия решения о дальнейшем ходе вычислительного процесса и, в частности, для вывода соответствующего диагностического сообщения.

Пусть ЕЗ – заданная погрешность. Тогда итерационный цикл прекращаем как только выполнится условие

| ЕТ | < | ЕЗ |.

При этом возникает проблема – как определить текущую погрешность ЕТ . В данном случае возможны две ситуации.

Ситуация 1 – для вычисления ЕТ известна аналитическая формула. Такая ситуация имеет место, в частности, при вычислении сумм рядов и решении нелинейных уравнений.

Ситуация 2 – нет аналитической формулы для определения текущей погрешности. Такая ситуация имеет место при численном расчете интегралов, численном решении дифференциальных уравнений и т.п. В этом случае можно использовать алгоритмический метод определения ЕТ, а именно, в качестве текущей погрешности брать разность значений искомой функции на двух соседних итерациях, то есть итерационный процесс продолжать до тех пор пока не выполнится условие

ЕТ = | YK+1-YK| < EЗ,

где к – номер итерации.

 

3.9.1. Вычисление сумм рядов.

Если требуется найти сумму заданного числа членов ряда (например, N; причем N вводится извне или вычисляется заранее), то никаких проблем с погрешностью не возникает и алгоритм решения такой задачи можно представить в. виде арифметического циклического процесса, в котором N раз используется формула последовательного суммирования, т.е. S = S+P, где Р — значение очередного члена ряда.

В случае, когда необходимо найти сумму ряда с погрешностью, не хуже заданной ЕЗ, также используется формула последовательного суммирования, но после каждого добавления к полученной сумме очередного члена ряда необходимо проверять текущую погрешность. Это можно сделать по-разному в зависимости от типа ряда.

Способ 1. В случае монотонно убывающего ряда (т.е. ряда, для которого последующий член ряда меньше предыдущего) суммирование проводят до тех пор, пока значение очередного члена ряда не станет меньше, чем заданная погрешность ЕЗ.

Пример. Составить алгоритм вычисления суммы ряда

с заданной погрешностью EPS.

Фрагмент алгоритма решения данной задачи приведен на рис. 3.9.1. Для возведения переменной X в степень и вычисления факториала используется формула последовательного умножения, причем обе эти функции совмещены в одной формуле для вычисления значения очередного члена ряда (Р). В блоке 3 в каждом цикле модуль очередного члена ряда сравнивается с заданным значением погрешности (сравнивать надо модуль очередного ряда потому, что в общем случае значения X могут быть отрицательными).

Способ 2. Рассмотренный выше способ определения погрешности нельзя непосредственно использовать, если ряд является периодически убывающим (например, если ряд содержит тригонометрическую функцию). В таких случаях

Рис.3.9.1 используется более общий способ завершения циклического процесса, суть которого состоит в том, что процесс суммирования членов ряда прекращается, если модуль очередного члена ряда несколько раз подряд окажется меньше заданного значения погрешности.

 

 

Этот способ является наиболее общим, его можно применять к любым рядам. Однако за эту общность приходится расплачиваться снижением эффективности алгоритма и увеличением сложности алгоритма (необходимо организовать проверку и запоминание значений нескольких членов ряда). Поэтому этот способ анализа погрешности используют в случаях, когда заранее неизвестен тип ряда (например, при создании подпрограммы общего назначения).

Алгоритм, приведенный на рис. 3.9.1, является итерационным циклом, поэтому в таком цикле необходимо предусмотреть средства для контроля количества циклов, иначе алгоритм может потерять свойство результативности. Например, если в алгоритме рис. 3.9.1 ошибочно будет задано значение погрешности EPS<0, то условие в блоке 3 будет всегда ложно.

Модифицировать алгоритм рис. 3.9.1

Рис.3.9.2 можно путем введения ограничения на допустимое количество циклов, как показано на рис. 3.9.2. Для фиксации ошибки в алгоритме рис. 3.9.2 предусмотрена переменная ER. Если цикл завершается при выходе из блока 3 по пути «Да» (это происходит, как только выполняется условие |P|<EPS), то ER = 0, что означает нормальное завершение вычислительного процесса. Если же будет выполнено КМ циклов и указанное условие не выполнится, то выход из цикла осуществляется через блок 6 и индикатор ошибки получит значение ER = 1, что является признаком ситуации «Требуемая точность не может быть получена за КМ шагов». Очевидно, что в алгоритмах, использующих подобный способ контроля ошибок после точки А (рис. 3.9.2.), необходимо предусматривать анализ значения ER для принятия решения о дальнейшем развитии вычислительного процесса. Значение КМ зависит от конкретной задачи и выбирается из разумных соображений.

Недостатком алгоритма рис. 3.9.2 является его неструктурированность, из цикла есть специальный выход (по пути «Да» из блока 3). Структурировать алгоритмы можно различными способами. Из всех возможных способов надо выбрать тот, который потребует минимальных вычислительных затрат. Один из способов структурирования алгоритма рис. 3.9.2 приведен на рис. 3.9.3. Проверка погрешности в данном случае осуществляется с помощью конструкции «Развилка» (блоки 3, 4), причем если |Р| <=EPS, то счетчик циклов получает значение КМ, что обеспечивает прекращение циклического процесса при | Р | <=EPS.

 

3.9.2. Решение нелинейных уравнений.

Любое нелинейное уравнение можно записать в виде

F1(y) = 0, (3.9.1)

либо в форме

Y= F2(Y). (3.9.2)

Существует много различных численных методов решения нелинейных уравнений [2, 3]: метод простой итерации, метод деления отрезка пополам, метод хорд, метод Ньютона и т.п. При численном определении корней решение проводится в два этапа. Первый этап называется отделением корней, т.е. определением отрезка аргумента, на котором расположен корень уравнения. Отделение корней может проводится различны

Рис.3.9.3. ми способами — выбором отрезка из физических соображений, из решений подобной задачи и т.п.

В любом случае на концах выделенного отрезка функция F(y) должна иметь различные знаки, чтобы корень располагался внутри этого отрезка. На втором этапе проводится решение уравнения тем или иным итерационным численным методом.

В общем случае процедура решения уравнения заключается в следующем. Выбирая начальное значение корня уравнения уН из выделенного отрезка находят первое приближение у1, которое используют для определения второго приближения у2 и т.д. Так как обычно точное решение найти невозможно, то процесс решения продолжают до тех пор, пока текущая погрешность не станет меньше некоторой заданной малой величины ЕЗ. Типичные значения ЕЗ лежат в диапазоне 10-4— 10-6.

Для оенки текущей погрешности в данном случае используется аналитическое выражение – запись уравнения в виде (3.9.1), а именно:

ЕТ = F1(YK),

где к- номер итерации.

 

3.9.3. Метод простой итерации.

 

В этом методе исходное уравнение записывается в форме (3.9.2):

YK+1 = F2(YK) (3.9.3).

В правую часть (3.9.3) подставляем начальное приближение YH и вычисляем первое приближение Y1

Y1 = F2(YH) (3.9.4)..

Затем полученное значение Y1 подставляют в правую часть (3.9.3).и вычисляют второе приближение. На каждой итерации вычисляют текущую погрешность ЕТ

ЕТ = F1(YK).

Процесс продолжается до тех пор пока не выполнится условие

ЕТ < Е З.

Пример. Решение уравнения a sin(y) +y-b = 0 методом простой итерации.

Запишем уравнение в виде

у=b-a sin(y) (2.7)

и будем предполагать, что начальное приближение ун известно. При решении уравнения методом простой итерации значение у, найденное на очередной итерации из выражения (2.7), используется в правой части (2.7) на следующей итерации, т.е. вычисления проводятся в сле­дующем порядке:

yi=b-a sin(yн),

y2 = b-a sin(y1),

yк+1 = b-a sin(yк),

 

Нетрудно заметить, что расчетная формула на каждой итерации остается неизменной, изменяются только значения данных, поэтому вычисления можно организовать в виде циклического процесса. Для этого достаточно расчетную формулу записать в виде

y=b-a sin(yн)

и в каждом цикле после вычисления очередного значения У выполнять операцию

YH = Y.

Выражение для оценки текущей погрешности в данном случае имеет вид

ET = Y- b+a sin(yн)

 

Схема алгоритма решения этой задачи приведена на рис. 3.9.4, где обозначено: YH— значение у с предыдущей итерации (на первой итерации YH— это началь­ное приближение, задаваемое извне); У — значение корня, вычисленное на очередной итерации; Ет — текущая погрешность; EPS — заданная погрешность.

Для простоты на рис. 3.9.4 не показаны средства контроля количества циклов, которые в данном случае обязательно надо предусматривать, так как, во-первых, цикл итерационный, а во-вторых, при неудачном выборе YH процесс решения вообще может расходиться. Заметим, что метод простой итерации сходится, если |f '(yH)| < 1.

 

 

Рис.3.9.3




Дата добавления: 2014-12-18; просмотров: 35 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав