Практическое занятие Приближенные вычисления Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Дисциплины "ЯЗЫКИ ПРОГРАММИРОВАНИЯ" "ПРОГРАММИРОВАНИЕ"

Рекуррентные соотношения © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 В основе многих циклических алгоритмов (или их фрагментов) лежит фундаментальная идея о том, что результат вычислений на каждом шаге цикла должен зависеть от результатов предыдущего шага. Обобщенным математическим выражением этой идеи являются рекуррентные соотношения. Будем говорить, что последовательность a задана рекуррентным соотношением, если задан начальный ее элемент a 0, а также функциональная зависимость каждого последующего элемента от предыдущего: a k+1 = f(a k ) Рекуррентными соотношениями можно описать следующие ранее изученные алгоритмические элементы: 1. Изменение счетчика цикла: i 0 = 1, i k+1 = i k Вычисление суммы чисел входной последовательности: S = a 1 + a 2 + … + a N – 1 + a N s 0 = 0, s k+1 = s k-1 + a k, S = s N

Задача 1. Арифметическое извлечение квадратного корня © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Для квадратов чисел верны следующие равенства: 1 = = 4 = = 9 = = 16 = Используя данное свойство можно арифметически вычислить целую часть корня. Пусть x – число, для которого необходимо найти корень. 1. Если (x – 1) = 0, то x = 1, если (x – 1) < 0, то [x] = 0, иначе x = x – 1 2. Если (x – 3) = 0, то x = 2, если (x – 3) < 0, то [x] = 1, иначе x = x – 3 3. Если (x – 5) = 0, то x = 3, если (x – 5) < 0, то [x] = 2, иначе x = x – 5 4. Если (x – 7) = 0, то x = 4, если (x – 7) < 0, то [x] = 3, иначе x = x – 7 …. 1. Рекуррентное соотношение по которому изменяется вычитаемое и x! 2. Блок-схема алгоритма. 3. Программа.

Задача 2. Численное вычисление квадратного корня по формуле Герона вычисления. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Итерационная формула Герона задает убывающую (начиная со 2-го элемента) последовательность, которая при любом выборе быстро сходится к величине a (квадратный корень из числа). Рекуррентное соотношение, описывающее данную последовательность выглядит следующим образом: Вычисление прекращается, когда (x n – x n+1 ) < ε. Значения a и ε являются входными для алгоритма. Задача: 1. Записать блок-схему алгоритма вычисления квадратного корня по формуле Герона. 2. На основе предложенного алгоритма разработать программу.

Задача 3. Приближенное вычисление e x © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 Задача: Вычислить приближенное значение функции e x, используя приведенный выше ряд. Вычисление останавливается, когда относительная погрешность приближенного результата становится меньше наперед заданного значения ε: (E n – E n–1 )/E n–1 < ε. Входные данные: x, ε. 1. Выписать рекуррентные соотношения для числителя и знаменателя элементов ряда. 2. Реализовать приближенное вычисление e x на базе одного цикла, с применением полученных рекуррентных соотношений. 3. Реализовать приближенное вычисление e x на базе вложенных циклов, где внутренний цикл отвечает за вычисление i-го элемента суммы "с нуля".

Задача 4. Приближенное вычисление ln(1 – x) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Задача: Вычислить приближенное значение функции ln(1–x), используя приведенный выше ряд. Вычисление останавливается, когда относительная погрешность приближенного результата становится меньше наперед заданного значения ε: (L n (x) – L n–1 (x))/L n–1 (x) < ε. Входные данные: x, ε. 1. Выписать рекуррентные соотношения для числителя и знаменателя элементов ряда. 2. Реализовать приближенное вычисление ln(1–x) на базе одного цикла, с применением полученных рекуррентных соотношений. 3. Реализовать приближенное вычисление ln(1–x) на базе вложенных циклов, где внутренний цикл отвечает за вычисление i-го элемента суммы "с нуля".

Задача 5. Приближенное вычисление (1 + x) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Задача: Вычислить приближенное значение функции (1+x), используя приведенный выше ряд. Вычисление останавливается, когда относительная погрешность приближенного результата становится меньше наперед заданного значения ε: (S n (x) – S n–1 (x))/S n–1 (x) < ε. Входные данные: x, ε. 1. Выписать рекуррентные соотношения для числителя и знаменателя элементов ряда. 2. Реализовать приближенное вычисление (1+x) на базе одного цикла, с применением полученных рекуррентных соотношений. 3. Реализовать приближенное вычисление (1+x) на базе вложенных циклов, где внутренний цикл отвечает за вычисление i-го элемента суммы "с нуля".

Задачи для самостоятельной работы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 П.6.1. Вычисление корня n-й степени из числа A. Следующее рекуррентное соотношение для целого n и положительного A задает последовательность чисел, которая сходится к желаемому результату: Вычисление прекращается, когда (x k – x k+1 )/x k < ε. Значения A и ε являются входными для алгоритма. Задача: 1. Записать блок-схему алгоритма вычисления корня n-й степени. 2. На основе предложенного алгоритма разработать программу.

Задачи для самостоятельной работы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 П.6.2. Вычислить приближенное значение функции 1/(1 – x), условия решения аналогичны задачам 3 – 5 данного практического занятия. П.6.3. Вычислить приближенное значение функции 1/(1 – x), условия решения аналогичны задачам 3 – 5 данного практического занятия.