Лабораторная работа № 5
ПРОГРАММИРОВАНИЕ ИТЕРАЦИОННЫХ ЦИКЛОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ С УСЛОЖНЕННОЙ СТРУКТУРОЙ
Цель и порядок работы
Цель работы – познакомиться со структурным подходом разработки алгоритмов сложных вычислительных процессов, получить практические навыки программирования подобного рода задач.
Порядок выполнения работы:
· ознакомиться с описанием лабораторной работы;
· получить задание у преподавателя по вариантам;
· разработать схему алгоритма решения задачи;
· написать программу, соответствующую схеме алгоритма;
· ввести программу, отладить и выполнить ее на ЭВМ;
· оформить отчет.
·
Общие сведения
В данной лабораторной работе приводится ряд подходов с подробными рассуждениями к решению некоторых задач различных типов.
2.1 Итерационные циклы
Итерационным циклом называется такой, число повторений которого заранее неизвестно или его сложно рассчитать, а в процессе повторения тела цикла образуется последовательность значений y1, y2,…, yn,…, сходящаяся к некоторому пределу а, т. е.
Lim yn = a.
n ® ¥
Каждое новое значение yn в такой последовательности определяется с учетом предыдущего yn-1 и является по сравнению с ним более точным приближением к искомому результату. Итерационный цикл заканчивает свою работу в том случае, если для некоторого значения n выполняется условие:
| yn - yn-1 |£ e,
где e - допустимая погрешность вычисления результата.
В такой ситуации за результат принимают последнее значение y, т.е. считают, что yn с заданной точностью представляет значение а.
Задача вычисления суммы бесконечного ряда может служить прекрасной иллюстрацией к пониманию итерационного циклического процесса. Естественно, вычислять сумму бесконечного ряда имеет смысл в том случае, когда бесконечный ряд является сходящимся. Известно, что ряд сходится, если его общий член zn при беспредельном возрастании n стремится к нулю, т. е.
Lim zn = 0; Lim (sn – sn-1) = 0.
n ® ¥ n ® ¥
А сумма
sn = z0 + z1 + …+zn
его первых (n + 1) слагаемых при этом стремится к некоторому пределу S, который и называется суммой ряда, т. е.
Lim sn = S; Lim S zn = S.
n ® ¥ n ® ¥
Алгоритм, реализующий подсчет суммы ряда, должен вырабатывать последовательность s1, s2, …, sn, … при следующем условии окончания суммирования:
| zn |£ e.
Пример 1. Вычислить значение функции cos x, используя разложение косинуса в ряд с заданной погрешностью e:
Cos x = 1 - + - + …+(-1)n +...
При построении алгоритма данной задачи необходимо:
- определить значение очередного слагаемого z ;
- осуществлять накопление суммы по итерационной формуле:
s = s + z.
Для определения значения очередного слагаемого z в данном примере целесообразно использовать не прямое его вычисление по общей формуле, а рекуррентное соотношение, которое позволяет существенно сократить количество операций при вычислении его значения:
z = z * fn.
Определим сомножитель f n:
fn = =.
Для работы алгоритма (рис.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)
и, зная начальное приближение корня x0 Î [a, b], каждое следующее приближение находят по формуле:
xn = j (xn-1).
Вычисления повторяют до тех пор, пока не выполнится условие | f(xn)| £ e, где e - заданная погрешность вычислений. Отметим, что иногда используют другой способ контроля сходимости, состоящей в сравнении xn и xn-1. Процесс сходится, если на всем отрезке [a, b] |j¢(x)|< 1, где j¢(x) есть производная функции j (x).
Пример 2. Определить корень уравнения x – tg(x)= 0 с погрешностью e = 10-3 при начальном значении корня x0 = 4,5.
Преобразуем исходное уравнение следующим образом:
x = tg x,
тогда f(x)= x – tg x; j(x) = tg x.
Для определения x0 удобно использовать следующие графические построения. Построить графики функций y1= x; y2= j(x)= tg x. Точки пересечения этих графиков и будут корнями исходного уравнения f(x)= 0. На графике выделить приближенные отрезки [a, b] локализации каждого корня. В качестве x0 можно взять любую точку отрезка.
Рисунок 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.
Для практического контроля сходимости итерационного процесса xn=j(xn-1) можно осуществлять печать промежуточных значений x, последнее из которых и будет корнем уравнения при заданной погрешности.