Общие сведения. Цель работы – познакомиться со структурным подходом разработки алгоритмов сложных вычислительных процессов

Лабораторная работа № 5

ПРОГРАММИРОВАНИЕ ИТЕРАЦИОННЫХ ЦИКЛОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ С УСЛОЖНЕННОЙ СТРУКТУРОЙ

Цель и порядок работы

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

Порядок выполнения работы:

· ознакомиться с описанием лабораторной работы;

· получить задание у преподавателя по вариантам;

· разработать схему алгоритма решения задачи;

· написать программу, соответствующую схеме алгоритма;

· ввести программу, отладить и выполнить ее на ЭВМ;

· оформить отчет.

·

Общие сведения

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

2.1 Итерационные циклы

Итерационным циклом называется такой, число повторений которого заранее неизвестно или его сложно рассчитать, а в процессе повторения тела цикла образуется последовательность значений y₁, y₂,…, y_n,…, сходящаяся к некоторому пределу а, т. е.

Lim y_n = a.

n ® ¥

Каждое новое значение y_n в такой последовательности определяется с учетом предыдущего y_n-1 и является по сравнению с ним более точным приближением к искомому результату. Итерационный цикл заканчивает свою работу в том случае, если для некоторого значения n выполняется условие:

| y_n - y_n-1 |£ e,

где e - допустимая погрешность вычисления результата.

В такой ситуации за результат принимают последнее значение y, т.е. считают, что y_n с заданной точностью представляет значение а.

Задача вычисления суммы бесконечного ряда может служить прекрасной иллюстрацией к пониманию итерационного циклического процесса. Естественно, вычислять сумму бесконечного ряда имеет смысл в том случае, когда бесконечный ряд является сходящимся. Известно, что ряд сходится, если его общий член z_n при беспредельном возрастании n стремится к нулю, т. е.

Lim z_n = 0; Lim (s_n – s_n-1) = 0.

n ® ¥ n ® ¥

А сумма

s_n = z₀ + z₁ + …+z_n

его первых (n + 1) слагаемых при этом стремится к некоторому пределу S, который и называется суммой ряда, т. е.

Lim s_n = S; Lim S z_n = S.

n ® ¥ n ® ¥

Алгоритм, реализующий подсчет суммы ряда, должен вырабатывать последовательность s₁, s₂, …, s_n, … при следующем условии окончания суммирования:

| z_n |£ e.

Пример 1. Вычислить значение функции cos x, используя разложение косинуса в ряд с заданной погрешностью e:

Cos x = 1 - + - + …+(-1)ⁿ +...

При построении алгоритма данной задачи необходимо:

- определить значение очередного слагаемого z _;

- осуществлять накопление суммы по итерационной формуле:

s = s + z.

Для определения значения очередного слагаемого z в данном примере целесообразно использовать не прямое его вычисление по общей формуле, а рекуррентное соотношение, которое позволяет существенно сократить количество операций при вычислении его значения:

z = z * f_n.

Определим сомножитель f _n:

f_{n = =.}

Для работы алгоритма (рис.1) весьма важно определить исходную информацию для работы цикла. Подставив в данную формулу n = 0,получим начальное значение z =1.

Рисунок 1 – Схема алгоритма к примеру 1

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

Листинг 1

using System;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

double x, eps,s,t,y,f;

Console.Write("Enter x ");

x = Convert.ToDouble(Console.ReadLine());

Console.Write("Enter eps ");

eps = Convert.ToDouble(Console.ReadLine());

s=0;

t=1;

int n=1;

while (Math.Abs(t) > eps)

{ //Начало цикла

s= s + t;

f= -x*x / (2*n*(2*n-1));

t= t*f;

n++;

} //Конец цикла

y= Math.Cos (x);

Console.WriteLine("х=" + x + " у=" + y+ " s="+s);

}

}

}

Для организации цикла по накоплению суммы используется оператор цикла с предусловием, в котором условие | z | > e является условием продолжения цикла.

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

Нахождение корней уравнений вида

f (x)= 0

осуществляется в два этапа.

Первый этап – этап локализации корня – определяется отрезок [a,b], в пределах которого находится один и только один корень уравнения. Часто локализация корня осуществляется построением «грубого» графика функции f (x).

Второй этап – этап уточнения корня – ведется поиск корня с заданной степенью точности с помощью некоторого итерационного алгоритма.

Наиболее простым методом уточнения корня является метод итераций, заключающийся в следующем. Исходное уравнение f (x)= 0, где f (x) - непрерывная функция на отрезке [a, b], заменяют эквивалентным уравнением вида:

x = j (x)

и, зная начальное приближение корня x₀ Î [a, b], каждое следующее приближение находят по формуле:

x_n = j (x_n-1).

Вычисления повторяют до тех пор, пока не выполнится условие | f(x_n)| £ e, где e - заданная погрешность вычислений. Отметим, что иногда используют другой способ контроля сходимости, состоящей в сравнении x_n и x_n-1. Процесс сходится, если на всем отрезке [a, b] |j¢(x)|< 1, где j¢(x) есть производная функции j (x).

Пример 2. Определить корень уравнения x – tg(x)= 0 с погрешностью e = 10^-3 при начальном значении корня x₀ = 4,5.

Преобразуем исходное уравнение следующим образом:

x = tg x,

тогда f(x)= x – tg x; j(x) = tg x.

Для определения x₀ удобно использовать следующие графические построения. Построить графики функций y₁= x; y₂= j(x)= tg x. Точки пересечения этих графиков и будут корнями исходного уравнения f(x)= 0. На графике выделить приближенные отрезки [a, b] локализации каждого корня. В качестве x₀ можно взять любую точку отрезка.

Рисунок 2 – Схема алгоритма к примеру 2

Программа уточнения корня по методу итераций представлена в листинге 2.

Листинг 2

using System;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

double x, xn, eps;

Console.Write("Enter xn ");

xn = Convert.ToDouble(Console.ReadLine());

Console.Write("Enter eps ");

eps = Convert.ToDouble(Console.ReadLine());

x=xn;

while (Math.Abs (x-Math.Sin(x)/Math.Cos(x))>eps)

x=Math.Sin(x)/Math.Cos(x);

Console.WriteLine("x=" + x);

}

}

}

В данной программе на печать в качестве результата выводится последнее значение x, которое удовлетворяет заданному значению Eps.

Для практического контроля сходимости итерационного процесса x_n=j(x_n-1) можно осуществлять печать промежуточных значений x, последнее из которых и будет корнем уравнения при заданной погрешности.