34663

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

Реферат

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

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

Русский

2013-09-08

41 KB

28 чел.

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

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

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

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

Реальный вычислительный процесс всегда должен заканчиваться при конечном значении 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.

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


 

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

84488. Механізми і закономірності передачізбудження в центральних синапсах 44.76 KB
  Аксосоматичні Аксоаксональні Аксодендритні Дендродендритичні Збудливі Гальмівні Хімічні Електричні Механізм передачі збудження через центральний аксосоматичний хімічний синапс полягає в наступному: ПД поширюється по мембрані аксона далі по мембрані пресинаптичній підвищення проникності пресинаптичної мембрани для іонів С2 вхід їх в нервове закінчення за градієнтом концентрації вихід медіатора в синаптичну щілину дифузія медіатора до постсинаптичної мембрани взаємодія з мембранними циторецепторами збільшення...
84489. Види центрального гальмування. Механізми розвитку пре- та постсинаптичного гальмування 43.78 KB
  Механізми розвитку пре та постсинаптичного гальмування. Гальмування активний фізіологічний процес. Гальмування в ЦНС Постсинаптичне Пресинаптичне За локалізацією За електрофізіологічною природою Гіперполяризаційне Деполяризаційне За будовою нейронних ланцюгів Зворотнє Пряме Постсинаптичне гіперполяризаційне гальмування.
84490. Сумація збудження і гальмування нейронами ЦНС 48.02 KB
  Взаємодія збудження та гальмування на тілі кожного окремого нейрона відбувається шляхом сумації просторової та часової. В залежності від переважання сумації ЗПСП чи ГПСП нейрон може перебувати в трьох станах: збудження характеризується генерацією ПД на мембрані аксонного горбика в результаті переважання сумації ЗПСП деполяризація мембрани дійшла до критичного рівня: чим інтенсивніше протікає сумація ЗПСП тим швидше деполяризація доходить до Екр тим частіше ПД в РРН тобто тим сильніше збудження нейрона. Таким чином за допомогою...
84491. Рухові рефлекси спинного мозку, їх рефлекторні дуги, фізіологічне значення 45.37 KB
  У складі задніх рогів спинного мозку переважають вставні нейрони. Біла речовина спинного мозку представлена волокнами висхідних та низхідних шляхів. Контроль на рівні спинного мозку Рецептори шкіри Вісцерорецептори ангіорецептори.
84492. Провідникова функція спинного мозку. Залежність спінальних рефлексів від діяльності центрів головного мозку. Спінальний шок 43.05 KB
  Біла речовина спинного мозку передні бокові та задні канатики складається з нервових волокон які формують провідні шляхи. Основними висхідними шляхами є: 1. Шлях Голя розташований в медіальній частині заднього канатика. Шлях Бурдаха розташований в латеральній частині заднього канатика.
84493. Рухові рефлекси заднього мозку, децеребраційна ригідність 48.79 KB
  Вони носять назву надсегментарних утворень так як впливають на мязи не прямо а через мотонейрони сегментарних структур рухові ядра спинного мозку і черепномозкових нервів. Задній мозок отримує і переробляє всю аферентну інформацію що надходить від спинного мозку оскільки всі специфічні висхідні шляхи від спинного мозку входячи в стовбур мозку задній та середній мозок віддають коллатералі гілочки до ретикулярної формації тут продовжується обробка аферентної інформації. В задньому мозку розміщені 4 вестибулярні ядра медіальне...
84494. Рухові рефлекси середнього мозку, їх фізіологічне значення 44.55 KB
  Середній мозок СрМ за участі сітчастої речовини опрацьовує аферентну інформацію яка поступає в спинний та задній мозок. Нова інформація поступає в СрМ від зорових та слухових рецепторів. На основі опрацьовання інформації від усіх цих рецепторів СрМ здійснює контроль за станом зовнішнього та внутрішнього середовища організма. Важливими надсегментарними руховими ядрами СрМ є: 1 червоні ядра від них інформація від нейронів спинного мозку передається по шляхах що перехрещуються руброспінальні шляхи елемент ЛНС; 2 ретикулярна формація;...
84495. Мозочок, його функції, симптоми ураження 44.3 KB
  Від вестибулорецепторів через вестибулярні ядра контроль за збереженням рівноваги при русі. Від всіх рухових ядер стовбуру ретикулярна формація краєві ядра. З руховими ядрами стовбуру ретикулярна формація вестибулярні ядра червоні ядра через які Мз здійснює вплив на мотонейрони і на мязи. З базальними ядрами.
84496. Таламус, його функції 43.44 KB
  Сенсорні перемикаючі специфічні ядра вони отримують інформацію від специфічних сенсорних шляхів переробляють її і передають в сенсорні зони КГМ. Неспецифічні вони отримують інформацію від ретикулярної формації стовбура мозку по шляхах больової чутливості. Вони передають інформацію до всіх зон КГМ здійснюючи на неї неспецифічний активуючий вплив. Асоціативні отримують інформацію від специфічних сенсорних перемикаючих ядер і від неспецифічних ядер таламуса.