Алгоритмы - Рабочая тетрадь 1. Дисциплина Алгоритмы решения прикладных задач Рабочая тетрадь Метод половинного деления. Метод хорд
 Скачать 320.3 Kb.
|
|
1 Дисциплина «Алгоритмы решения прикладных задач» Рабочая тетрадь 1. Метод половинного деления. Метод хорд Теоретический материал Метод половинного деления для нахождения квадратного корня и корня уравнения Квадратный корень в программах встречается очень часто, при этом его вычисление достаточно трудоемко. Еще в 1950-х годах соответствующая операция была вынесена в специальный математический сопроцессор — центральный процессор отправлял в него запрос и пока выполнялись вычисления он успевал обрабатывать другие важные команды. Метод половинного деления относится к серии алгоритмов, построенных по принципу «разделяй и властвуй». Он применяется для поиска корней уравнений. Допустим, есть у нас некоторая функция f(x), известно, что функция монотонна на некотором интервале [L,R]. Монотонность — обязательное требование для использования этого алгоритма, оно означает, что функция либо только возрастает на этом интервале, либо — убывает. В общем, на интервале нет перегибов функции, т.е. точек, в которых производная равна нулю. Тогда, если на концах интервала функция имеет разные знаки — она обязательно пересекает горизонтальную ось, т.е. имеет корень. Если f(L) * f(R) > 0 — значит функция на этом интервале корня не имеет. Как же найти где именно находится этот корень? — опять же итеративно. Возьмем точку посередине интервала (B = L + (R-L)/2) — по знаку f(B) можно определить где именно находится корень (правее этой точки или левее). Если f(L)*f(B) < 0 — то корень находится на интервале [L,B] при этом заменим R на B и повторим процесс. В противном случае корень находится на [B,R]. Вычисления продолжаются до тех пор, пока интервал поиска корня не сузится достаточно сильно, т.е. пока |R-L| > Eps (Eps – заданная погрешность, например 0.001). Схематически метод проиллюстрирован на рисунке ниже 2 Частный случай применения метода половинного деления – это поиск квадратного корня, для его вычисления достаточно решить уравнение типа x*x = A, т.е. f(x) = x*x - A = 0. Начальное значение интервала поиска — [1,A]. Программа для нахождения квадратного корня методом половинного деления представлена в примере 1.1. Метод хорд Метод хорд — итерационный численный метод приближённого нахождения корня уравнения. Половинное деление не учитывает никаких свойств функции F(x), а эта функция может нести в себе очень полезную информацию. Метод хорд предполагает следующее. От точек, ограничивающих кривую (заданные концы отрезка L и R), строится хорда, затем определяется точка её пересечения с осью абсцисс, точка пересечения становится новой границей отрезка, после чего строится новая хорда. Итерационный процесс задается следующей формулой: Точка пересечения касательной с осью X является точкой приближения (на рисунке точки приближения отмечены числами 1 и 2). 3 Пример 1.1 Задача: Написать на языке C++ программу для поиска квадратного корня числа методом половинного деления Решение: Ответ: 4 Задание 1.1 Задача: Решить методом половинного деления. Номер варианта соответствует номеру в списке (номеру в списке минус 15 для номеров 16-30 и номеру в списке минус 30 для номеров от 31 и далее). Оформить алгоритм на языке C++ (или каком-либо другом) Решение: Ответ: Задание 1.2 Задача: Решить задачу 1.1 методом хорд Решение: Ответ: 5 |