18. Организация вычислений, способ 2 (цикл выполняет заданное количество итераций).

Перед вычислительным циклом вычисляется число итераций n, за которое отрезок уменьшается в ширине настолько, что становится меньше заданной точности вычислений. Далее выполняется цикл вычислений, описанный п.п. 17, за исключением п.п. в), который определяет момент завершения алгоритма. Цикл реализуется в виде оператора for. После завершения цикла функция метода возвращает значение X.

В основной функции нужно добавить код для вызова функции метода номер 2 и вывода результатов, например:

Варианты решаемых функций

1.e2x = 0

2.ex + x = 0

3.cos x – x = 0

4.cos 2x + cos x + 3 = 0

5.1/x – x = 0

6.ln x + x = 0

7.

Практическое задание №2. Метод простых итераций

Краткое описание задания: задано некоторое число a. Методом простых итераций найти квадратный корень из этого числа с заданной точностью ε.

Методические указания

1. Программа ничего не принимает с клавиатуры. Все исходные данные задаются в коде программы, как правило, в основном модуле, во время вызова функции метода (внутри функции main).

11

2.Программа решает задачу двумя способами: а) с помощью итераций; б) с помощью рекурсии.

3.Название модуля (файла типа .h) для функции метода — msimiter.

4.Название функции метода — simiter.

5.Сигнатура (прототип) функции метода имеет следующий вид:

double simiterN(pef ef, double X0, double eps, int* success);

Здесь:

-N — номер способа (1 или 2);

-pef — тип решаемой функции;

-X0 — начальное (приближенное) значение;

-eps — заданная точность решения;

-success — возвращаемый признак успешного выполнения алгоритма.

-возвращаемое значение функции метода — результат вычисления аргумента x решаемой функции, при котором решаемая функция равна аргументу с заданной точностью eps.

6. Тип решаемой функции задается следующим описанием:

typedef double (*pef)(double);

Это описание уже должно быть выполнено в модуле mhalfint.

7. Решаемая функция описывается в основном модуле следующим образом:

// Решаемая функция для метода простых итераций double f2(double x) {

/* код функции */

}

8. Функция метода вызывается в основной функции.

После вызова выводятся три строчки результата, например:

SUCCESS=4

EPSILON=0.001

RESULT1=2.236

Здесь:

SUCCESS — успешность выполнение алгоритма (значение success); EPSILON — заданная точность вычисления (значение EPS); RESULT1 — результат вычислений способом 1, вывод должен соот-

ветствовать заданной точности.

12

Порядок выполнения задания

1.Сначала выполните действие 1, описанное выше в разделе «Общий порядок выполнения очередного (не первого) задания».

2.Добавьте в решение новый модуль типа .h (заголовочный) с названием msimiter. Процесс добавления нового модуля описан в практическом задании №1.

3.Добавьте в новый модуль файловый комментарий, например:

4.Основной модуль. Добавьте описание решаемой функции f2. Сигнатура функции f2 описана в методических указаниях.

Для начала будем вычислять корень из двух, равный, как известно,

1.414 с точностью 0.001.

На самом деле нам нужно найти решение уравнения x2 = 2.

Метод простых итераций предполагает вычисление очередного значе-

ния xn+1 по формуле xn+1 = f(x). Поэтому исходное уравнение нужно привести к виду x = f(x). Делается это с помощью замены уравнения вида xk = a на уравнение вида x = (a + (k –1)xk) / (kxk–1). Так, для нашего исходного уравнения x2 = 2 получим решаемую функцию x = (2 + x2) / 2x.

Именно эту функцию и нужно описать как функцию f2. При этом x слева от знака "=" — это возвращаемое значение функции f2, а справа от знака "=" описано «тело» функции f2.

5.Модуль msimiter. Добавим в модуль функцию метода для решения задания способом 1, например:

//Метод простых итераций, способ 1

double simiter1(pef ef, double X0, double eps, int* success) { *success = 0;

double X = 0.0; return X;

}

Здесь устанавливается начальное значение признака успешного завершения алгоритма success, определяется переменная для результата X и возвращается значение результата.

6. Основной модуль. В основной функции необходимо закомментировать решение первого задания, например:

13

Либо перед закомментированным блоком, либо после него нужно описать вызов функции simiter1 и вывести результаты, например:

/* Основная функция */ void _tmain() {

int success = 0; double result = 0.0; /*

. . .

*/

result = simiter1(f2, 1, EPS, &success); printf("SUCCESS=%d\n", success); printf("EPSILON=%0.3f\n", EPS); printf("RESULT1=%0.3f\n", result);

}

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

Убедитесь в правильности кода на настоящий момент, скомпилировав его, например, при помощи сочетания клавиш Ctrl+Shift+B. При необходимости устраните ошибки.

Запустите проект на исполнения Ctrl+F5. Убедитесь, что выводятся правильные на настоящий момент результаты:

SUCCESS=0

EPSILON=0.001

RESULT1=0.000

7. Организация вычислений, способ 1. Договоримся, что признак успешного выполнения алгоритма считает итерации (см. раздел «Признак успешности выполнения алгоритма»).

Реализация метода простых итераций способом итераций (то есть с помощью цикла) ну очень проста. Казалось бы, нет особой необходимости

14

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

Сейчас функция метода ничего не делает и просто возвращает значение решения X:

double simiter1(pef ef, double X0, double eps, int* success) { *success = 0;

double X = 0.0; return X;

}

Нам нужно вычислить это X. Это итеративный процесс, поэтому нам нужен цикл. Можно использовать, например, цикл while (1). Поэтому добавляем в функцию метода этот цикл (серым цветом отмечен текст, который уже существует):

double simiter1(pef ef, double X0, double eps, int* success) { *success = 0;

double X = 0; while ( 1 ) {

}

return X;

}

Внутри цикла прежде всего нужно выполнить проверку на зацикливание (то есть на достижение максимального числа итераций). Как это сделать, описано в разделе «Признак успешности выполнения алгоритма». В случае, если значение признака достигло максимального значения, нужно выйти из цикла при помощи break.

Далее нужно вычислить новое приближение решения X, используя решаемую функцию (которая обозначена внутри функции метода как ef), при этом аргументом функции является начальное значение X0.

Затем нужно проверить условие завершения. Оно звучит так: если абсолютная величина разности нового значения X и начального значения X0 меньше заданной точности eps, то нужно выйти из цикла при помощи оператора break (при этом решение найдено и равно X).

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

И это все. Сразу после того, как правильный код будет написан, программа вычислит значение корня из двух с заданной точностью. Весь код внутри цикла — четыре строки. Результат вычислений:

SUCCESS=4

EPSILON=0.001

RESULT1=1.414

8. Организация вычислений, способ 2. Прежде всего нужно добавить новую функцию в модуль msimiter:

15

double simiter2(pef ef, double X0, double eps, int* success) { double X = 0.0;

return X;

}

Далее в основной функции нужно добавить вызов новой функции и вывод результатов:

/* Основная функция */ void _tmain() {

int success = 0; double result = 0.0; /*

. . .

*/

result = simiter1(f2, 1, EPS, &success); printf("SUCCESS=%d\n", success); printf("EPSILON=%0.3f\n", EPS); printf("RESULT1=%0.3f\n", result); success = 0;

result = simiter2(f2, 1, EPS, &success); printf("SUCCESS=%d\n", success); printf("EPSILON=%0.3f\n", EPS); printf("RESULT1=%0.3f\n", result);

}

Заметим, что перед вызовом функции simiter2 нужно обнулить значение признака успешного завершения success.

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

Новая функция выглядит примерно так:

/* Заданная точность вычислений */ #define EPS 0.001

/* вывод результатов */

void printr(int success, double eps, double result, int method) { printf("SUCCESS=%d\n", success);

printf("EPSILON=%0.3f\n", eps); printf("RESULT%d=%0.3f\n", method, result);

}

Последний параметр функции задает номер способа. В случае, если используется только один способ, можно задать значение "0" или "1".

В результате мы можем значительно упростить вид основной функции, заменив выводы результатов вызовами функции printr:

16

/* Основная функция */ void _tmain() {

int success = 0; double result = 0.0; /*

result = halfint1(f1, -2, 3, EPS, &success); printr(success, EPS, success, 1);

success = 0;

result = halfint2(f1, -2, 3, EPS, &success); printr(success, EPS, success, 2);

*/ // метод простых итераций

result = simiter1(f2, 1, EPS, &success); printr(success, EPS, success, 1); success = 0;

result = simiter2(f2, 1, EPS, &success); printr(success, EPS, success, 2);

}

Вернемся к реализации метода простых итераций с помощью рекурсии. Во-первых, нужно понимать, что формула xn+1 = f(x) является рекуррентной, а значит, решаемой с помощью рекурсивной функции. Рекурсивная функция отличается от обычной тем, что вызывает в своем теле саму себя. Здесь важным является момент завершения рекурсивных вызовов.

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

Перейдем в модуль mhalfint. Здесь определена константа, задающая максимальное количество циклов. Ее значение нужно установить сейчас равным ста, потому что большее число рекурсивных вызовов может привести к исключению «Переполнение стека» (Stack overflow). Мы также принимаем во внимание, что реально требуемое количество итераций находится в пределах десятков.

Вернемся в функцию simiter2. Внутри этой функции нельзя установить начальное значение признака успешности выполнения алгоритма, равным нулю, потому что рекурсивные вызовы будут обнулять его и смысл признака потеряется. Вместо этого мы установили передаваемое значение признака равным нулю в основной функции.

Как было сказано, для рекурсивной функции важно определить момент завершения рекурсии. В нашем случае этим моментом является уменьшение абсолютного значения разности начального X0 и нового значений X до величины, меньшей заданной точности eps.

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

17