Алгоритм проектирования. рафик. Ташкенский университет информационных технологий имени мухаммада алхорезми нурафшанский филиал
 Скачать 0.56 Mb.
|
|
ТАШКЕНСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛ-ХОРЕЗМИ НУРАФШАНСКИЙ ФИЛИАЛ Кафедра. К.И.Ф Тема:Алгоритмы ветвления. Методы приближенного решения алгебраических и трансцендентных уравнений. Оценка эффективности. Итерационные циклы Названия группы: 620-21 Ф.И студента:Илесов Рафик Ташкент 2023 План: 1. Алгоритмы ветвления 2. Приближенные решения алгебраических и трансцендентных уравнений 3. Итерационные циклы 4. Литература Начало Ввод/вывод данных Условие Команда (действие) Счетчик цикла Конец Начало алгоритма, вход в программу Конец алгоритма, выход из программы Ввод исходных данных или вывод результата Выполнение действий Проверка логического условия Количество повторов цикла Общий вид блок-схем алгоритмической структуры “ветвление” Действие 1 Условие Действие 2 Условие
В Паскале ветвление организуется с помощью двух операторов: IF и CASE. условие действие1 действие2 условие действие1 Оператор IF Составить алгоритм планирования выходного дня студентом: если будет хорошая погода, он пойдет гулять, а если плохая − будет писать реферат. Входные данные: x (информация о погоде); Выходные данные: y (результат прошедшего выходного дня). program Student; var x, y; begin writeln(‘Хорошая погода?'); read ({Да}); if Y:={Да} then Y:={Студент идет гулять} else Y:={Студент пишет реферат}; writeln (‘Как студент провел свой выходной?’, Y); end. Постановка задачиРассмотрим способы решения нелинейных уравнений с одним неизвестным. Каждое такое уравнение можно представить в виде:f(x)=0 (1)Опр.1 Число t называется корнем уравнения (1) или нулем функции f, если при подстановке его вместо х уравнение превращается в верное равенствоПриближенные решения алгебраических и трансцендентных уравнений
2. Вычислить корни точно, если это возможно и имеет смысл, или приближенно с заданной степенью точности.Опр.2. Поиск приближенного значения корня с точностью до заданного достаточно малого числа ε>0 называется уточнением корня. Задача уточнения будет решена, если найдется число х* такое, что׀ t-x*׀ ≤ε. Тогда t≈ х* с точностью до εГеометрическая интерпретацияПусть дано уравнение y=f(x). Построим график функции y=f(x)x y t1 t2 t3 y = f(x) Абсциссы точек пересечения графика с осью Ох и являются корнями уравнения. На этом построен графический метод решения уравнений. Этот метод нагляден и прост, но позволяет получить лишь грубые приближения значения корней уравнения Найдем корни уравнения sin4x – lnx = 0 Преобразуем его к виду sin4x = lnx
x y t1 t2 t3 y = sin 4x y = ln x t1≈0,8 t2≈1,7 t3≈2,1
Отделение корнейОпр.3 Отделение корней- это определение их наличия, количества и нахождение для каждого из них достаточно малого отрезка [a,b], которому он принадлежитТеорема (о единственности корня). Если функция f(x) определена, непрерывна, монотонна на отрезке [a,b] и принимает на концах отрезка значения разных знаков, т.е f(a)f(b)<0, то существует единственная точка t(a,b), в которой значение функции равно нулюГрафически корни можно отделить 2-мя способами
y=f(x) x y x1* a b x2* x3* На графике 3 корня. Первый корень x* [a,b] 2 способ Отделение корней по графикам функций (x) и (x).Преобразовать f(x)=0 к виду (x) = (x), где (x) и (x) – элементарные функции, и определить абсциссу пересечений графиков этих функций.На графике 2 корня. Первый корень x1* [a,b] y x y=(x) y= (x) x1* a b x2* Уравнение имеет два корня: t1[0,5; 1], t2[2,5; 3].t1 1 2 t2 3 1 -1 -2 g(x)= -x2+3x-2 φ(x)=2cos(x+π/3) Блок-схема алгоритма отделения корней уравнения f(x)=0Метод половинного деленияПусть дано уравнение f(x)=0.Будем считать, что отделение корней произведено и на отрезке [a; b] расположен один корень t. Требуется найти приближенное значение корня с точностью до , где – достаточно малое положительное число.Разделим [a; b] пополам точкой с и вычислим f(c). Проверим следующие условия:
Геометрическая интерпретация метода половинного деленияx y y=f(x) a b c1 b1 a1 c t Если на каком-то шаге обнаружится точный корень (что практически маловероятно), то процесс деления пополам закончится нахождением точного значения. Если нет, то получится бесконечная последовательность вложенных отрезков
с точностью , так какx an bn x* t 2 Количество итераций n, требуемых для достижения заданной точности ε можно оценить заранее из соотношенияили Блок-схема алгоритма уточнения корня уравнения f(x)=0 на отрезке [a;b] с точностью методом половинного деленияСХОДИМОСТЬ АЛГОРИТМА [convergence of algorithm] — способность алгоритма приводить к результату за конечное число шагов. Скорость сходимость алгоритма один из важных показателей качества экономико - математических моделей, предназначенных для решения задач на ЭВМ. Обычно она оценивается количеством итераций, необходимых для получения искомого решения. Итерационные циклы Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа «пока». Выход из итерационного цикла осуществляется в случае выполнения заданного условия. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет "зацикливание" алгоритма, т.е. не будет выполняться основное свойство алгоритма — «результативность». Вычисление сумм — типичная циклическая задача. На каждом шаге вычислений происходит последовательное приближение к искомому результату и проверка условия достижения последнего. Вычисление сумм — типичная циклическая задача. Особенностью же нашей конкретной задачи является то, что число слагаемых (а, следовательно, и число повторений тела цикла) заранее неизвестно. Поэтому выполнение цикла должно завершиться в момент достижения требуемой точности. Литература:
2. http://www.myshared.ru/slide/1407140/ Спасибо за внимание! |