34663

Итерационные алгоритмы

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-09-08

41 KB

25 чел.

Итерационные алгоритмы.

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

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

На каждом шаге вычислений происходит последовательное приближение к искомому результату и проверка условия достижения последнего. 

Реальный вычислительный процесс всегда должен заканчиваться при конечном значении k, поэтому всегда возникает проблема выбора условия окончания итераций – так называемого критерия сходимости.

Вот некоторые общие примеры, используемые на практике:

1. абсолютное изменение параметра на соседних шагах итерационного процесса:

2. относительное изменение на соседних шагах

Здесь - наперед заданное малое значение, определяющая точность нахождения решения.

В реализации конкретных численных методов возможно применение специфических критериев или комбинации нескольких критериев.

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

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

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

При составлении алгоритма нужно учесть, что знаки слагаемых чередуются и степень числа х в числителях слагаемых возрастает.

Решая эту задачу "в лоб" путем вычисления на каждом i-ом шаге частичной суммы

S:=S + ((-1)**(i-1)) * (x**i) / i ,

мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой р, то у следующего слагаемого числитель будет равен -р*х (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое m будет равно p/i, где i - номер слагаемого.

Сравните эти два подхода по числу операций.


Алгоритм на языке Паскаль

Блок-схема алгоритма

program Summa;

var e, m, p : real;

   i : integer;

   дано | 0 < x < 1

   надо | S = x - x**2/2 + x**3/3 - ...

Begin

 write(‘Введите x : ’);

 readln(x);

 write(‘Введите e : ’);

 readln(e);

 S := 0;

 i := 1;

  m := 1;

 p := -1

  while abs(m)>e do

 begin

   p:=-p*x; {p – числитель очередного слагаемого}

   m:=p/i; {m - очередное слагаемое}

   S:=S+m; {S - частичная сумма}

   inc(i); {i – номер очередного слагаемого}

  end;

 Write(s);

 readln;

End.

В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет "зацикливание" алгоритма, т.е. не будет выполняться основное свойство алгоритма — результативность.


 

А также другие работы, которые могут Вас заинтересовать

20650. Марксизм в России 40 KB
  Плеханов Георгий Валентинович 18561918 русский философмарксист сторонник революционных преобразований общества. Плеханов являлся ортодоксальным последователем учения Маркса и Энгельса о закономерностях развития общества. Но несмотря на сочувствие историческому материализму в марксизме Плеханов проявлял определённую творческую самостоятельность в размышлениях о социальных процессах. Плеханов предложил монистическое единое универсальное основание для любых форм хозяйственных и товарноденежных отношений социума географическую среду.
20651. Философский смысл проблемы бытия 63.5 KB
  Одна из первых по значению проблем философского исследования состоит в попытке дать ответ на такие онтологические вопросы как: что есть бытие существует ли оно и есть ли его противоположности попытка дать качественное определение категории бытие и рассмотреть его отношение с понятиями небытие и инобытие; где и когда оно существует проблемы пространства и времени; конечно ли всё сущее и есть ли его начало; как соотносятся между собой различные формы бытия как взаимосвязаны различные по степени конкретизации уровни форм бытия...
20652. Категория «материя» в философии 46 KB
  Рассматривая материю можно выделить ряд основных проблем формирующих предмет исследования данной категории: а вопрос о единстве материи б соотношение материи и идеального в диалектика материи то есть рассмотрение её через призму закона единства и борьбы противоположностей установка диалектических противоречий например исследование таких категорий как общее и специфическое целое и часть и т. Подобное ограниченное конкретновещественное понимание материи сохранялось как парадигма на протяжении многих столетий в философии...
20653. Дифференцированность материи существование различного типа систем структур и рассмотрение бытия как 44 KB
  Материя таким образом не существует вне изменений или вне движения. Любой предмет действительности реализует в себе формулу всё пребывает в вечном стремлении к иному состоянию и бытийствует лишь в форме определённого типа движения или изменяющиеся динамичные отношений. При разрушении собственного движения образующего качество объекта он переходит в состояния движения присущего другим классам объектов. Как и материя движение абсолютно то есть несотворимо и неуничтожимо и ни одна форма движения не берется ниоткуда.
20654. Пространство и время 38.5 KB
  Движение как на элементарном так и социальном уровне предполагает изменение положения объекта в пространстве осуществляемом во времени. Характеристиками времени являются длительность последовательности смены состояний осуществляемой благодаря взаимосвязи процессам развития или деградации объектов. Для того чтобы произвести отсчёт времени мы берём в качестве эталона повторяющийся по определённым критериям какойлибо процесс и с ним сопоставляем непериодические более сложные процессы. Время как и пространство существует лишь потому что...
20655. Основные исторические этапы становления диалектического учения 39.5 KB
  Сократовский диалог хотя и на первый взгляд не отличается от первых определений диалектики но в действительности становится одной из первых гносеологических формул в постижении человека и природы. Понимание диалектики как диалога спора противоречий продлилось и в средние века где казалось бы религиозный монизм должен исключить любое возможное несогласие с божественной догматикой. Рассмотрение диалектики как искусства вести беседу актуально и сейчас при столкновении мнений в области не просто частных споров но и в решении социальных...
20656. Основные принципы диалектики 62.5 KB
  Сложные связи разнообразных явлений пронизывают абсолютно всё мироздание и неразрывны в своей основе хотя материя и разнородна. Можно дать следующее определение связи – это атрибут материи являющийся общим выражением зависимости между явлениями отражением взаимообусловленности их существования и развития. Под отношением следует понимать одну из форм момент всеобщей взаимосвязи предметов и процессов раскрывающей существование объекта не только самого по себе но и для других речь идёт о том что отношения всегда устанавливаются между...
20657. Мировоззрение – понятие, структура и формы. Мировоззрение и философия 82 KB
  В более развёрнутом виде мировоззрение можно рассматривать как целостную самостоятельную социально детерминированную систему в которой сложно отражены и взаимосвязаны наиболее общие взгляды образы оценки принципы чувственные и рациональные представления индивида и коллектива о действительности в объективном природном общественном и субъективном индивидуальном состоянии и отношении к ним человека в его духовной деятельности. Основной проблемой мировоззрения выступает вопрос о специфики отношений связующих человека и мир. Раскрытие...
20658. Предмет, структура, функции философии. Философия и культура. Философия и наука 100 KB
  Определение философии. Подобное понимание лишает философское знание научной специфики создаёт ложное представление о философии как чистом мышлении способном существовать вне связей с объективной реальностью размывает уникальность её предмета целей задач и методов исследования а также ограничивает рамками личностного субъективного видения мира. Поэтому для определения философии можно использовать такой этимологический перевод как любовь к истине.